Оптимизационные модели GERT - сетевого планирования и управления производственными процессами тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Ермолаева, Любовь Викторовна

• Ермолаева, Любовь Викторовна
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Ермолаева, Любовь Викторовна

Введение.

1. ДЕТЕРМИНИРОВАННЫЕ МОДЕЛИ ФОРМИРОВАНИЯ ПРОИЗВОДСТВЕННЫХ ПРОГРАММ

1.1. Формальная модель задачи объемно-календарного планирования производства.

1.2. Формальная модель задачи распределения производственной программы предприятия по плановым периодам.

1.3. Задачи формирования производственной программы при мелкосерийном производстве.

1.4. Модели планирования финансирования выполнения производственных программ.

2. МОДЕЛЬНЫЕ КОМПОНЕНТЫ СТОХАСТИЧЕСКОЙ СТРУКТУРЫ ПРОИЗВОДСТВЕННЫХ ПРОЦЕССОВ

2.1. Модельные средства детерминированного формирования распределенных процессов.

2.1.1. Классификация моделей.

2.1.2. Одноресурсные модели.

2.1.3. Мультиресурсные модели.

2.1.4. Периодичные задачи при формировании планов.

2.1.4.1. Ограничения на классы ресурсов.

2.1.4.2. Периодичные задачи с бинарным частотным распределением.

2.1.4.3. Периодичные задачи с независимым распределением частоты.

2.1.4.4. Учет пределов.

2.2. Стохастическое представление моделей формирования.

2.2.1. вЕЯТ-сетевая модель стохастической структуры.

2.2.2Минимизация затрат ресурсов.

2.2.3. Случайные акции при реализации процессов.

2.2.4. Многократное исполнение операций.

2.2.5. Минимизация по времени.

2.3. Стохастическая модель определения нормативных времен выполнения операций в условиях неопределенности.

2.3.1. СЕИТ-сетевое представление моделей.

2.3.2. Определение вероятностных нормативных времен для процессов, реализуемых в условиях неопределенности.

3. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ ЗАТРАТ

РЕСУРСОВ И ВРЕМЕНИ РЕАЛИЗАЦИИ

3.1. Анализ задач оптимизации.

3.2. Метод изменяющихся вероятностей.

3.3. Применение метода ветвей и границ.

Введение диссертации (часть автореферата) на тему «Оптимизационные модели GERT - сетевого планирования и управления производственными процессами»

Актуальность. Современная экономическая ситуация диктует жесткие требования участникам рыночных отношений. Выживают только высокоорганизованные предприятия, в основу управления которыми положен принцип быстрой реакции на непрерывно изменяющиеся требования рынка. Мировая практика показала, что динамичные и гибкие производства строятся на базе современных информационных систем управления класса MES (Manufacturing Execution System - производственные исполнительные системы) [10, 30-32, 51, 54-63]. Развернутым смысловым определением MES систем, соответствующим отечественной практике и терминологии (АСУ ПП - автоматизированные системы управления производственными процессами), можно считать следующее: системы оперативного планирования, оптимизации и управления производственными процессами.

Эти системы определяют точные сроки выполнения заказов, степень загрузки оборудования, оптимальные маршруты обработки продукции, рациональное использование финансовых ресурсов, энергоресурсов и играют важную роль в эффективном производстве для снижения себестоимости выпускаемой продукции; сокращения издержек и производственных потерь; сокращения объемов материально-технических запасов и ресурсосбережения.

Диссертационная работа посвящена построению математического аппарата расчета производственных расписаний и распределения ресурсов различного характера. Данный инструментарий может быть применен в системах класса MES. Его основой является циклическая стохастическая сетевая модель (GERT-сеть) [33-35, 64-66], являющаяся обобщением таких методов сетевого планирования как метод критического пути, PERT -сетей, обобщенных сетевых моделей [50-53, 67-76].

Выбор вЕИТ-сетей как основы для разработки алгоритмов ресурсно-временного анализа производственных процессов обоснован тем, что по сравнению со своими предшественниками СЕЯТ-сеть позволяет использовать многократное имитационное моделирование производственных процессов, временные параметры и внутренние логические связи которых могут иметь стохастическую природу.

Цель исследования. Построение модельного описания производственных процессов, позволяющего принимать обоснованные управленческие решения в условиях риска и неопределенности.

Указанная цель определила необходимость решения следующих задач.

1. Проведение анализа подходов к оптимизации планирования и управления производственными процессами.

2. Разработка модельных средств детерминированного формирования распределенных производственных процессов.

3. Стохастическое представление моделей формирования производственных процессов.

4. Построение стохастической модели определения нормативных времен выполнения операций в условиях неопределенности.

5. Построение алгоритмов решения оптимизационных задач.

Методы исследования. Системный анализ и методы теории оптимизации. Методы теории вероятностей и теории потоковых графов. Методы детерминированного и стохастического анализа сетей. Теория множеств, комбинаторика и теория графов.

Научная новизна работы.

1. Разработана многокомпонентная сетевая модель с унифицированной СЕЯТ-подобной узловой логикой для формального представления и автоматизированного формирования операций распределенных производственных процессов.

2. Показана возможность использования метода критического пути для ресурсно-временного анализа распределенного производственного процесса и его реализации за минимальное время.

3. Предложены три группы эвристических схем формирования распределенных производственных процессов, включающих периодичные операции с независимым распределением частоты, и проведено их относительное сравнение с применением моделирования.

4. Доказано существование допустимой реализации распределенного процесса, если сетевая модель его формирования ациклична и ее параметры удовлетворяют условиям GERT-подобной узловой логики.

5. Предложен новый алгоритм условной оптимизации псевдобулевых функций на несвязных областях с адаптацией по средней вероятности по схеме метода изменяющихся вероятностей

Практическая ценность. Реализация предложенного формального аппарата GERT-сетевого моделирования производственных процессов в автоматизированных системах поддержки принятия решений при планировании и управлении производственными процессами позволит повысить эффективность и обоснованность принимаемых управленческих решений.

Апробация работы. Результаты диссертационного исследования обсуждались на международной научно-практической конференции «Математическое моделирование в образовании, науке и производстве»; Тирасполь, 2001, на Всероссийской научно-технической конференции «Перспективные материалы, технологии, конструкции, экономика», Красноярск, 2003, на II конференции «Фундаментальные и прикладные исследования», Рим, 2004, на III Международной конференции «Инновационные процессы в управлении предприятиями и организациями», Пенза, 2004, на заочной электронной конференции Российской академии естествознания 20-25 февраля 2005, на IV Всероссийской конференции по финансово-актуарной математике и смежным вопросам, Красноярск, 2005, на научно-технических советах и научных семинарах НИИ СУВПТ и ЦКБ «Геофизика».

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Ермолаева, Любовь Викторовна

Основные результаты диссертации опубликованы в работах [72-82].

Список литературы диссертационного исследования кандидат технических наук Ермолаева, Любовь Викторовна, 2007 год

1. Дегтерев Д.А. Модельное и алгоритмическое обеспечение объемно-календарного планирования на предприятиях ВПК в условиях конверсии / Д.А.Дегтерев // Дис. на соиск. уч. ст. канд. техн. наук / Красноярск: НИИ СУВПТ, 2003,- 118 с.

2. Ильина Т.Р. Модели и алгоритмы оптимизации загрузки ресурсов в условиях мелкосерийного производства / Т.Р.Ильина // Дис. на соиск. уч. степени канд. техн. наук. / Красноярск: НИИ СУВПТ, 2001.- 149 с.

3. Семенкина О.Э., Формализация задачи планирования загрузки ресурсов мелкосерийного производства / О.Э.Семенкина, Т.Р.Ильина, С.П.Коробейников // Интеллектуальные технологии и адаптация / Красноярск: НИИ СУВПТ, 1999- С. 31-40.

4. Семенкина О.Э. Метод обобщенного локального поиска для задач принятия решений в управлении сложными системами / О.Э.Семенкина // Дис. на соиск. уч. степени доктора техн. наук / Красноярск: НИИ СУВПТ, 2002.- 330 с.

5. Сумароков А.Д. Совершенствование управления и принятия решений по инновационной деятельности предприятий ВПК / А.Д.Сумароков // Дис. на соиск. уч. степени канд. техн. наук / Красноярск: СибГАУ, 2005. 129 с.

6. Внедрение и управление проектами. Электронный ресурс. Режим доступа: www.pmforum.org,www.choice.da.ru.

7. Абдулаев Д.А. Моделирование локальных вычислительных сетей с учетом вероятностно-временных характеристик / Д.А.Абдулаев, У.Б.Амирсаидов // Автоматика и вычислительная техника. 2004. № 3. - С. 151-160.

8. Емельянов C.B. Технология системного моделирования. / С.В.Емельянов, Е.Ф.Аврамчук.- М.: Машиностроение; Берлин: Техник, 1988. 520 с.

9. Алимханов А.М. Обзор современных методологий автоматизированного управления производством / А.М.Алимханов, Н.Н.Джиоева // Вестник НИИ СУВПТ.-./ Красноярск: НИИ СУВПТ. 2003.-Вып. 12.-С. 111-120.

10. Антамошкин А.Н. Оптимизация функционалов с булевыми переменными / А.Н. Антамошкин. Томск: Изд-во Том. ун-та, 1987. - 104 с.

11. Воеводин В.В. Математические модели и методы в параллельных процессах / Воеводин B.B. М.: Наука, 1986. - 328 с.

12. Методы анализа и синтеза структур управляющих систем / под ред. Б.Г.Волика.- М.: Энергоатомиздат, 1988. 296 с.

13. Введение в системный анализ / под ред. JI. А. Петросяна.- JL: ЛГУ, 1988. 232 с.

14. Зыков A.C. Роль информационных технологий на предприятии / А.С.Зыков // Современные проблемы информатизации в технике и технологиях: Сб. трудов. Вып. 9. Под ред. д.т.н., проф. О.Я. Кравца.-Воронеж: Изд-во «Научная книга», 2006, с. 228-229.

15. Калянов Г.Н. CASE-технологии: консалтинг в автоматизации бизнес-процессов / Г.Н.Калянов. М.: Горячая линия-Телеком, 2002. - 418 с.

16. Калянов Г.Н. Современные CASE-технологии / Г.Н.Калянов. М.: ИПУ, 2003. - 397 с.

17. Ковалев И.В. Моделирование и оптимизация параллельных процессов в информационно-управляющих системах / И.В.Ковалев, Р.Ю.Царев. Красноярск: ИПЦ КГТУ, 2005. - 111 с.122

18. Колесников С. Из истории автоматизации методологий управления предприятием / С.Колесников // Открытые системы.- 2006. № 4. - С. 44-56. http://www.osp.ru/os/1999/04/09.htm

19. Коржов В. Адекватные системы / В.Коржов // Открытые системы. -2006.-№ 12-С. 118-124.

20. Корячко В.П. Численный метод нахождения закона распределения выходной величины GERT-сети / В.П.Корячко // Информационные технологии. 2006.- № 7.- С. 16-21.

21. Ковальчук Е.Р. Основы автоматизации машиностроительного производства/ под ред. Ю.М. Соломенцева.- М.: Высш. шк., 1999. 349 с.

22. Руководство по методологии ABC. М.: Метатехнология, 1997. 230с.

23. Системный анализ: Проектирование, оптимизация и приложения. В 2 т./ под общ. ред. Антамошкина А.Н. Красноярск, CAA, 1996. 206 с.

24. Слепцов А.И. Автоматизация проектирования управляющих систем / Слепцов А.И. Киев: Техника, 1996. - 393 с.

25. Тихонов А.Н. Методы и системы поддержки принятия решений / А.Н.Тихонов, В.Я. Цветков М.: МАКС Пресс, 2001.-314 с.

26. Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х томах. Т. 2.: пер. с англ. / Феллер В. М.: Мир. 1984. 738 с.

27. Филлипс Д. Методы анализа сетей / Д.Филлипс, Д.Гарсиа-Диас -М.: Мир, 1984.-496 с.

28. Шибанов А.П. Нахождение закона распределения выходной величины GERT-сети большой размерности / А.П.Шибанов // Информационные технологии.- 2007. № 1. - С. 42-45.

29. Яппаров Т.Г. Комплексные автоматизированные системы управления предприятием / Т.Г.Яппаров // Средства и системы компьютерной автоматизации сервер АСУТП. Электронный ресурс. -Режим доступа: http://www/asutp.ru/?p=600330.

30. CSRP. Электронный ресурс. Режим доступа: www.symix.com. Русский перевод по адресу: [e-mail].

31. MRP-ERP. Электронный ресурс. Режим доступа: plant.da.ru (http://www.geocities.com/WallStreet/2907/), erp.da.ru.

32. Neumann К. Stochastic Project Network / K.Neumann // Lecture Notes in Economics and Mathematical Systems, No. 34, Springer Verlag, 1995. 327 p.

33. Neumann, K. An Optimality Equation for Stochastic Decision Networks. Wiss / K.Neumann // Zeitschrift Techn. Hochschule Leipzig, No. 8, 1984. Pp. 7987.

34. GERT: Graphical Evaluation and Review Technique Part.l, Fundamentals / A.A.Pritsker // The Journal of Industrial Engineering (May 1966). -Pp. 67-101.

35. Supply Chain. Электронный ресурс. Режим доступа: www-rcf.usc.edu/~xin/supplychainbookmarks.htm.

36. Семенкин Е.С. Оптимизация технических систем / Е.С.Семенкин, О.Э.Семенкина, С.П.Коробейников Красноярск: Сибирский институт бизнеса, управления и психологии, 1996. - 285 с.

37. Кузнецов А.В. Высшая математика: Математическое программирование / А.В. Кузнецов.: — Мн.: Выш. шк., 2001. — 351с.

38. Хедли Д. Нелинейное и динамическое программирование / Д.Хедли — М.:Мир, 1967. —213с.

39. System Analysis, Design and Optimization. An Introduction/General Editing by A.Zhilinskas. Krasnoyarsk: Krasnoyarsk Spase Technology University, 1993. - 203 p.

40. Берсенев В.А., Гимади Э.Х., Дементьев B.T. Экстремальные задачи стандартизации / В.А.Берсенев, Э.Х.Гимади, В.Т.Дементьев. Новосибирск: Наука, 1978. - 333с.

41. Деордица Ю.С. Исследование операций в планировании и управлении / Ю.С.Деордица, Ю.М.Нефедов. Киев: Выща Школа, 1991. -79с.

42. Системы оперативного управления производством Электронный ресурс. Режим доступа: http://www.mesa.ru/.

43. Маклаков С. Имитационное моделирование с Arena Электронный ресурс. Режим доступа: http://www.interface.ru/fset.asp?Url=/sysmod/arl.htm.

44. Воропаев В.И., Гельруд Я.Д. Циклические альтернативные сетевые модели и их использование при управлении проектами Электронный ресурс. Режим доступа: http://www.sovnet.ru/pages/casml.doc.

45. Дубова. Н. Системы управления производственной информацией / Н.Дубова // Открытые системы. 2006. - №3. С. 18-26.

46. Абакумов. В. Система сопровождения проектных данных IMAN / В.Абакумов. // Открытые системы. 2006. - № 5. -С. 76-83.

47. Краюшкин В. Система Optegra управление производственными данными / В.Краюшкин // Открытые системы. - 2007. - №1 - С. 54-60.

48. Клишин В. Интегрированные технологии CV / В.Клишин,B.Климов, М.Пирогова // Открытые системы. 2005. - №2. - С.42-50.

49. Куцевич И.В. Введение в LIMS / И.В.Куцевич // Мир компьютерной автоматизации. 2002. - № 4. - С. 83-89.

50. Colin Thurston, Integrating LIMS Into a Large-Scale Manufacturing Environment American Laboratory.- March 2004.- Pp. 33-50.

51. Нуцков Ю.В. Интеграция LabWare LIMS и SAP R/3 QM / Ю.В.Нуцков, Б.Хиллхауз // Мир компьютерной автоматизации.- 2003.- № 4.C.101-111.

52. Синенко О.В. Подход к анализу производственных процессов и созданию комплексных систем управления ресурсами / О.В.Синенко, Н.А.Куцевич // Мир компьютерной автоматизации, 2006. № 4. - С. 56-71.

53. Гребнев С.А. Современные подходы к интеграции АСУ / С.А.Гребнев, В.И.Кузякин, Синенко // Мир компьютерной автоматизации, 2005. № 5. - С.101-111.

54. Шибанов А.П. Нахождение плотности распределения времени исполнения GERT-сети на основе эквивалентных упрощающих преобразований / А.П.Шибанов // Автоматика и телемеханика, 2006. № 2. -С. 117-126.

55. Корячко В.П. Численный метод нахождения закона распределения выходной величины GERT-сети / В.П.Корячко, А.П.Шибанов, В.А.Шибанов Информационные технологии, 2004. № 7. - С. 16 - 21.

56. Прицкер А. Введение в имитационное моделирование и язык СЛАМII / А.Прицкер: М.: Мир, 1987. - 646 с.

57. Мазур И.И. Управление проектами / И.И.Мазур, В.Д.Шапиро // Справочник для профессионалов. Москва: Высшая школа, 2001. 875 с.

58. Шапиро В.Д. Project management. Управление проектами / В.Д.Шапиро // Толковый англо-русский словарь-справочник. Москва: Высшая школа, 1999. 379 с.

59. Решке X., Шелле X. Мир Управления Проектами / Х.Решке, Х.Шелле. Москва: Алане, 1994. - 303 с.

60. Voropaev V.I. Project Management in Russia / V.I.Voropaev. N.Y.: PMI, 1997. - 240 p.

61. Бурков B.H. Как управлять проектами: научно-практическое издание / В.Н.Бурков, Д.А.Новиков. М.: СИНТЕГ, 1997. - 188 с.

62. Воропаев В.И., Гельруд Я.Д. Циклические альтернативные сетевые модели и их использование при управлении проектами. Электронный ресурс. Режим доступа: http://sovnet.ru/pages/public/casm.htm.

63. Воропаев В.И., Гельруд Я. Д. Применение циклических альтернативных сетевых моделей при управлении проектами. Электронный ресурс. Режим доступа: http://sovnet.ru/pages/public/casm.htm.126

64. Воропаев В.И., Гельруд Я.Д. Использование ЦАСМ при управлении проектами. Электронный ресурс. Режим доступа: http://sovnet.ru/pages/public/casm.htm.

65. Авербах Л.И., Воропаев В.И., Гельруд Я.Д. Планирование работ проекта с учетом приведенной стоимости. Электронный ресурс. Режим доступа: http://sovnet.ru/pages/public/casm.htm.

66. Сопов Е.А. Эволюционные алгоритмы моделирования и оптимизации сложных систем / Е.А.Сопов // Дис. на соиск. уч. ст. канд. техн. наук / Красноярск: СибГАУ, 2004. 118 с.

67. Масич И.С. Поисковые алгоритмы решения задач условной псевдобулевой оптимизации / И.С.Масич // Дис. на соиск. уч. ст. канд. физ.-мат. наук / Красноярск: СибГАУ, 2004,126 с.

68. Попов A.A. Оптимизационные методы формирования мультиверсионного программного обеспечения критичных по надежности систем управления / А.А.Попов // Дис. на соиск. уч. ст. канд. техн. наук / Красноярск: НИИ СУВПТ, 2002,196 с.

69. Ермолаева Л.В. GERT-сетевая модель формирования производственных процессов / Л.В.Ермолаева // Управление стратегией развития производства: Заочная электронная конференция РАЕ, 2006.

70. Ермолаева Л.В. Модель планирования производственной программы конверсионного предприятия по выпуску гражданской продукции / Л.В. Ермолаева // Управление стратегией развития производства: Заочная электронная конференция РАЕ, 2007.

71. Формирование производственной программы при мелкосерийном • производстве / Л.В.Ермолаева // Управление стратегией развитияпроизводства: Заочная электронная конференция РАЕ, 2006.

72. Ермолаева Л.В. Применение информационных систем в производстве / Л.В.Ермолаева // Теория и практика коммерческой деятельности: мат-лы VII региональной конференции./ Красноярск: КГТЭИ, 2005. С. 40-45.

73. Ермолаева Л.В. Моделирование планирования производственных процессов предприятий ВПК в условиях конверсии / Л.В.Ермолаева // Вестник НИИ СУВПТ. Красноярск: НИИ СУВПТ.- 2005.- Вып. 3(17). С. 94101.

74. Ермолаева Л.В. Методы решения задачи оптимизации загрузки технологического оборудования предприятия / Л.В.Ермолаева // Вестник НИИ СУВПТ / Красноярск: НИИ СУВПТ, 2006.- Вып. 7(21). С. 176-184.

75. Ермолаева Л.В. Ресурсно-временной анализ при составлении производственных расписаний / Л.В.Ермолаева // Системы управления и информационные технологии 2007,- № 3.2(29).- С. 214-223.

76. Ермолаева Л.В., Сенашов С.И. GERT-сетевой анализ производственных процессов / Л.В.Ермолаева, С.И.Сенашов // Вестник СибГАУ / Красноярск: СибГАУ, 2007.- Вып. 3(16). С. 101-110.