Інформаційні технології багаторівневого планування В організаційно-виробничих системах з обмеженими ресурсами

Краткое описание

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ «КИЇВСЬКИЙ ПОЛІТЕХНИЧНИЙ ІНСТИТУТ»

На правах рукопису

Мельников Олег Валентинович

Інформаційні технології багаторівневого планування
В організаційно-виробничих системах з обмеженими ресурсами

05.13.06 – Інформаційні технології

Дисертація на здобуття наукового ступеня кандидата технічних наук

Науковий керівник:
Павлов Олександр Анатолійович
Доктор технічних наук, професор

Київ – 2013
ЗМІСТ
стор.
1  Багаторівневе ПЛАНУВАННЯ в організаційно-виробничих системах з обмеженими ресурсами......................................... 17
1.1   Загальний опис систем, що мають мережне представлення технологічних процесів та обмежені ресурси.................................................................................. 17
1.2   Вимоги до створення інформаційних технологій планування в організаційно-виробничих системах з обмеженими ресурсами...................................... 20
1.3   Особливості побудови багаторівневих моделей виробничого планування.. 23
1.4   Обгрунтування вибору критеріїв оптимізації.......................................... 28
1.5   Аналітичний огляд методів складання розкладів, застосовуваних у системах планування у складних системах з мережним представленням технологічних процесів та обмеженими ресурсами......................................................... 31
1.5.1    Представлення задач складання розкладів виробництва.................... 31
1.5.2    Оптимальне складання розкладів......................................................... 33
1.5.3    Евристичне складання розкладів.......................................................... 34
1.5.4    Складання розкладів на основі обмежень............................................ 37
1.5.5    Складання розкладів з підходами нечітких множин........................... 38
1.5.6    Складання розкладів з підходами нейро-мережі................................. 39
1.5.7    Методи ітеративного поліпшення......................................................... 40
1.5.8    Нові точні алгоритми з поліноміальною та декомпозиційною складовими        45
1.6   Сучасні системи планування у складних системах.................................. 46
1.7   Мета та задачі дослідження...................................................................... 50
1.8   Висновки по розділу 1.............................................................................. 51
2  Математичне ЗАБЕЗПЕЧЕННЯ ДРУГОГО РІВНЯ багаторівневОЇ моделІ планування у складних системах............................................ 52
2.1   Багаторівнева модель планування у складних системах з мережним представленням технологічних процесів та обмеженими ресурсами..... 52
2.2   Загальна схема реалізації математичного забезпечення багаторівневої моделі планування в складних системах БМПСС................................................ 63
2.3   Ключові рішення, прийняті при розробці математичного забезпечення багаторівневої моделі планування у складних системах......................... 66
2.4   Основні евристики, використані при розв’язанні задач першого рівня багаторівневої моделі планування............................................................ 71
2.5   Евристики, використані при реалізації другого рівня моделі................ 78
2.6   Розробка математичного забезпечення узгодження моделей першого й другого рівня відповідно до результатів розподілу.............................................. 80
2.7   Реалізація третього рівня моделі.............................................................. 83
2.8   Дослідження властивостей  та розв’язання задачі «Мінімізація сумарного випередження і запізнення відносно директивних строків при виконанні незалежних завдань одним приладом».................................................... 83
2.9   Висновки по розділу 2.............................................................................. 94
3  Обгрунтування інваріантності математичного пред­ста­в­­лення багаторівневої моделі планування для різних кла­сів складних систем, що мають Мережне пред­ста­влення технологічних процесів та обмежені ресурси...................................................... 95
3.1   Планування дрібносерійного виробництва.............................................. 95
3.2   Планування виробництва «на замовлення»........................................... 100
3.3   Планування виробництва в робочому цеху........................................... 103
3.4   Планування виробництва по виготовленню партій............................... 105
3.5   Планування робіт з будівництва складних об’єктів.............................. 113
3.6   Планування та управління проектами.................................................... 116
3.7   Висновки по розділу 3............................................................................ 119
4  ІНФОРМАЦІЙНА ТЕХНОЛОГІЯ багаторівневОГО ПЛАНУВАННЯ у складних системах на прикладі дрібносерійного ви­роб­ництва...................................................................................................................... 120
4.1   Загальна характеристика системи........................................................... 120
4.2   Опис бізнес-процесу................................................................................ 121
4.3   Концептуальна модель предметної області............................................ 125
4.4   Функціональна структура системи......................................................... 132
4.5   Опис функціональних вимог................................................................... 134
4.5.1    Підсистема попереднього планування................................................ 134
4.5.2    Підсистема узгодженного планування................................................ 135
4.5.3    Підсистема точного планування......................................................... 135
4.5.4    Підсистема аналізу плану виконання агрегованих робіт.................. 135
4.5.5    Сервер баз даних................................................................................. 135
4.5.6    Графічна оболонка роботи з програмою........................................... 136
4.6   Опис структурної схеми системи............................................................ 136
4.7   Діаграма класів........................................................................................ 139
4.8   Математичне забезпечення системи СПУСК.......................................... 141
4.9   Структура комплексу технічних засобів................................................ 142
4.10 Дослідження ефективності роботи системи............................................ 144
4.11 Задача адаптації ІТ для різних класів складних систем........................ 145
4.12 Висновки по розділу 4............................................................................ 147
ВИСНОВКИ   ................................................................................................. 149
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ........................................................ 151
Додаток А   структури таблиць бази даних автома­ти­зо­ва­ної системи «СПУСК» для дрібносерійного виробниц­тва..... 167
Додаток Б    опис Алгоритмів побудови інформаційних мо­делей та розв’язання задач в системі СПУСК......................................... 171
Б.1   Побудова інформаційної моделі............................................................. 171
Б.1.1    Завантаження файлів вхідної моделі................................................... 171
Б.1.2    Перевірка коректності моделі............................................................. 172
Б.2   Побудова моделі технологічної та конструкторської агрегації............ 176
Б.2.1    Алгоритм технологічної агрегації...................................................... 178
Б.2.2    Алгоритм конструкторської агрегації................................................ 183
Б.3   Побудова алгоритмічної та вихідної моделей....................................... 183
Б.3.1    Блок 1 – побудова допоміжних таблиць алгоритмічної моделі для організації швидкого доступу до інформації........................................................ 187
Б.3.2    Блок 2 – побудова критичних шляхів виробів................................... 189
Б.3.3    Блок 3 – пошук загальних вершин на критичних шляхах і формування графа на критичних шляхах виробів................................................................. 192
Б.3.4    Блок 4 – побудова припустимого розкладу....................................... 194
Б.3.5    Блок 5 – побудова оптимального розкладу....................................... 195
Б.3.6    Блок 6 – розбивка загальних вершин на ланцюжки вершин по критичних шляхах і формування нового графа................................................... 198
Б.3.7    Блок 7 – розподіл отриманого розкладу на новому графі на критичних шляхах по комірках із прив’язкою до планового періоду. Реализація процедур розподілу виробничої програми та узгодження першого і другого рівней моделі................................................................................................... 199
Б.3.8    Блок 8 – перевизначення набору загальних вершин відповідно до фактичної інформації про розподіл..................................................................... 205
Б.3.9    Блок 9 – формування графа на критичних шляхах з новим набором загальних вершин і повторне виконання кроків 4 і 5.......................................... 205
Б.3.10  Блок 10 – доповнення оптимального розкладу, побудованого на критичних шляхах, коміркокомплектами, що не лежать на критичних шляхах 206
Б.3.11  Блок 11 – розподіл отриманого розкладу по комірках з розбивкою коміркокомплектів на партії і з прив’язкою до планового періоду.. 207
Б.4   Реалізація процедур третього рівня багаторівневої моделі планування 209
Додаток В   Ілюстративний приклад розв’язання задачі планування в системі СПУСК на прикладі дрібно­серій­но­го виробництва......................................................................................... 212
Додаток Г    акти впровадження..................................................... 230

СКОРОЧЕНЬ

Скорочення

Пояснення

MRP

Material Requirement Planning – планування потреби в матеріалах і ресурсах

UML

Unified Modelling Language – уніфікований язик моделювання

В/З

Мінімізація випередження і запізнення

БМПСС

Багаторівнева модель планування у складних системах

ІТ

Інформаційна технологія

МВЗ

Мінімізація сумарного випередження і запізнення відносно директивних строків при виконанні незалежних завдань одним приладом

МЗМ

Мінімізація сумарного зваженого моменту закінчення виконання завдань

МПТПОР

Мережне представлення технологічних процесів та обмежені ресурси

МСЗ

Мінімізація сумарного запізнення завдань від­но­сно директивних строків

НРТ

Час навантажування/розвантажування/транспортування

ОКМ

Оптимізація колонії мурах (мурашиний метод)

ПДС-алгоритм

Алгоритм з поліноміальною та експоненційною складовими

ПМП

Підпослідовність максимального пріоритету

ПЗ

Програмне забезпечення

СОППР

Система оперативного планування та прийняття рішень

СПУДВ

Система планування та управління дрібносерійним виробництвом в умовах ринку

СПУСК

Система планування та управління у складних системах

ТР

Теорія розкладів

ВСТУП
Актуальність роботи
Постановкам задач планування у складних системах та методам їх розв’язання в останні десятиліття приділяється істотна увага з боку багатьох дослідників. Цей інтерес збільшується природно, оскільки ефективне розв’язання задач планування забезпечує збільшення продуктивності, підвищення рівня обслуговування та гнучкості, а також зниження витрат. Передбачаєт

Список литературы

Створено прогресивну інформаційну технологію (ІТ) багаторівневого планування у складних системах на основі комплексу взаємозв’язаних моделей і критеріїв дискретної оптимізації. Усі цілі дослідження досягнуто, а всі поставлені завдання виконано.
1 Виконано дослідження особливостей побудови багаторівневих моделей планування у складних системах, що мають мережне представлення технологічних процесів та обмежені ресурси, та дослідження методів плану­вання. Зроблено критичний огляд існуючих систем планування, методів агрегації моделі планування. Визначено проблеми створення ІТ багаторівневого планування у складних системах. Показано, що для ефективного впровадження нових алгоритмів планування необхідно створити нову ІТ планування в ринкових умовах та розширити область її застосування на інші класи систем, що мають мережне представлення технологічних процесів та обмежені ресурси.
2 Розроблена та обґрунтована багаторівнева модель планування складними системами з мережним представленням технологічних процесів та обмеженими ресурсами, яка відповідає сучасним вимогам до планування. Створено та обґрунтовано моделі та методи погодженого планування виконання робіт другого рівня моделі на другому рівні багаторівневої моделі планування у складних системах, що дозволило реалізувати стратегію пошуку глобального оптимуму з метою одержувати роз­в’язки, близькі до оптимальних. Створена та системно обґрунтована ергатична (інтерактивна) процедура адаптації моделі агрегації й дезагрегації першого й другого рівня моделі.
3 Визначено реальні класи систем, що мають мережне представлення технологічних процесів та обмежені ресурси, для яких адекватні розроблені моделі планування. Для цього формалізовано загальну математичну модель багаторівневого планування для різних класів складних систем, що мають мережне представлення технологічних процесів та обмежені ресурси та спрямовані на максимізацію прибутку та виконано адаптацію моделі на прикладі планування у таких класах складних систем: планування дрібносерійного виробництва, планування виробництва «на замовлення», планування виробництва в робочому цеху, планування виробництва по виготовленню партій, планування робіт з будівництва складних об’єктів, планування та управління проектами.
4 Досліджено властивості NP-складної в сильному розумінні задачі другого рівня моделі «Мінімізація сумарного випередження і запізнення відносно директивних строків при виконанні незалежних завдань одним приладом». Розроблено ефективний метод розв’язання задачі, наведено приклад його роботи та експериментальні дослідження, які показали, що він може ефективно знаходити розклади, близькі до оптимальних, за короткий час. Досліджено задачі з розмірністю до 500 завдань. Для 873 прикладів із 1000 з розмірністю до 25 було знайдено оптимальну послідовність. Також метод працював не менш, ніж двічі швидше за конкуруючих методів. Максимальний зафіксований час розв’язання для прикладу розмірності 500 завдань склав 330 секунд.
5 На основі запропонованих математичних моделей і методів створена ІТ багаторівневого планування у складних системах, що мають мережне представлення технологічних процесів та обмежені ресурси, яка застосована при розробці автоматизованої системи планування та управління у складних системах (СПУСК). Показано роботу системи на прикладі дрібносерійного виробництва. Систему СПУСК частково впроваджено на дослідному виробництві ДП НДІ «Квант» (м. Київ). Система СПУСК працює з даними реальних виробничих розмірів – сотні тисяч детале-операцій. Також ця інформаційна технологія використана як окремий випадок для створення автоматизованої системи планування та управління дрібносерійним виробництвом в умовах ринку (СПУДВ). Систему СПУДВ, як один з компонентів гіперсистемної технології обробки інформації та управління комп’ютери­зова­ними інтегрованими виробництвами, впроваджено на дочірньому підприємстві «АСУ АЕС» ВАТ «Атомсервіс» (м. Південно-Українськ). 

1
Akturk M.S. A New Lower Bounding Scheme for the Total Weighted Tardiness Problem [Текст] / M.S. Akturk, M.B. Yildirim // Computers & Operations Research. – 1998. – Vol. 24. – № 4. – P.265–278.

2

Baker K.R. Sequencing with earliness and tardiness penalties: a review [Текст] / K.R. Baker, G.D. Scudder // Operations Research. – 1990. – Vol.1. – №38. – Р.22–36.

3

Baptiste P. Constraint-based Scheduling : Applying Constraint Programming to Scheduling Problems Series [Текст] / Philippe Baptiste, Claude Le Pape, Wim Nuijten. – Kluwer Academic Publishers, 2001. – 198 p. (International Series in Operations Research & Management Science; 39)

4

Baptiste P. Incorporating Efficient Operations Research Algorithms in Constraint-Based Scheduling [Текст] / P. Baptiste, C. Le Pape, W. Nuijten // First International Joint Workshop on Artificial Intelligence and Operations Research, Timberline Lodge, Oregon. – 1995.

5

Beck J.C. A Generic Framework for Constraint-Directed Search and Scheduling [Текст] / J.C. Beck, M.S. Fox // AI Magazine. – 1998. – Vol.19. – №4. – P. 101–130.

6

Bitran G.R. Disaggregation and Resource Allocation Using Convex Knapsack Problems [Текст] / G.R. Bitran, A.C. Hax // Management Science. – 1981. – Vol. 27. – P.431–441.

7

Bitran G.R. Hierarchical Production Planning  [Текст] / G.R. Bitran, D. Tirupati //  Handbooks in Operations Research and Management Science, Vol. 4 :  Logistics of Production and Inventory [edited by S.C. Graves, A.H.G. Rinnooy Kan, P. H. Zipkin]. – Amsterdam : Elsevier Science Publishers B. V., 1993. – P. 523–568.

8

Bitran G.R. Hierarchical Production Planning: A Single Stage System [Текст] / G.R. Bitran, E.A. Haas, A.C. Hax // Operations Research. – 1981. – Vol. 29, №4. – P.717–743.

9

Bitran G.R. One the Design of Hierarchical Production Planning Systems [Текст] / G.R. Bitran, A.C. Hax // Decision Science. – 1977. – Vol. 8. – P.28–55.

10

Brucker P. Improving local search heuristics for some scheduling problems, part I [Текст] / P. Brucker, J. Hurink, F. Werner // Discrete Applied Mathematics. – 1996. – Vol. 65. – №1–3. – P.97–122.

11

Brucker P. Improving local search heuristics for some scheduling problems part II [Текст] / P. Brucker, J. Hurink, F. Werner // Discrete Applied Mathematics. – 1997. – Vol.72. – №1/2. – P.47–69.

12

Caseau Y. Disjunctive scheduling with task intervals. [Текст] / Y. Caseau, F. Laburthe. – LIENS Technical Report №95–25. – 1995. – Paris : Laboratoire d’Informatique de l’Ecole Nor­male Superieure Departement de Mathematiques et d’Informatique. – 35 p.

13

Chen B. A Review of Machine Scheduling: Complexity, Algorithms and Approximability [Текст] / B. Chen, C.N. Potts, G.J. Woeginger // Handbook of Combinatorial Optimization, Vol. 3 [editors D.-Z. Du, P. Pardalos]. – 1998. – Kluwer Academic Publishers. – P. 21–169.

14

Datta B. A comparative study of annealing methods for batch scheduling problems [Текст] / B. Datta, V.K. Jayaraman, B.D. Kulkarni // Chemical Engineering Research & Design. – 2001. – Vol.79 (A6). – P. 673–683.

15

Davis J.S. Single-machine scheduling with early and tardy completion costs [Текст] / J.S. Davis, J.J. Kanet // Naval Research Logistics. – 1993. – №40.– Р. 85–101.

16

Dincbas M. Solving large combinatorial Problems in Logic Programming [Текст] / M. Dincbas, H. Simonis, P. Van Hentenryck // Journal of Logic Programming. – 1990. – Vol. 8. – №1–2. – P. 75–93.

17

Dorn J. Iterative Improvement Methods for Knowledge-Based Scheduling. [Текст] / AI Communications. – 1995. – Vol. 8. – №1. – P. 20–34.

18

Dorn J. Scheduling of Production Processes [Текст] / J. Dorn, K.A. Froeschl. –1993. – Ellis Horwood. – 181 p.

19

Dorndorf U. Evolution based learning in a job-shop scheduling environment [Текст] / U. Dorndorf, E. Pesch // Computers and Operations Research. – 1995. – Vol. 22. – №1. – P. 25–40.

20

Feldmann M. Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches [Текст] / M. Feldmann, D. Biskup // Computers & Industrial Engineering. – 2003. – №44. – P.307–323.

21

Fisher H. Probabilistic learning combinations of local job-shop scheduling rules [Текст] / H. Fisher, G.L. Thompson // Industrial Scheduling / J.F. Muth, G.L. Thompson. – 1963. – Englewood Cliffs: Prentice-Hall. – P. 225–251.

22

Fisher M.L. A dual algorithm for the one-machine scheduling problem [Текст] /  Math. Programming. – 1976. – №11. – P. 229–251.

23

Fox M. S. Constraint Directed Search: A Case Study of Job-Shop Scheduling [Текст].– 1987. – London: Pitman Publishers. – 184 p.

24

Fox M.S. ISIS: A constraint-directed reasoning approach to job-shop scheduling [Текст] / M.S. Fox, S. Smith, B. Allen [et al.] // Proc. of the IEEE Trends and Applications Conference. – 1983. – P. 76–81.

25

Garey M.R. One-processor scheduling with symmetric earliness and tardiness penalties [Текст] / M.R. Garey, R.E. Tarjan, G.T. Wilfong // Mathematics of Operations Research. – 1988. – №13. – Р.330–348.

26

Gastek D.M. Managing MRP-II [Текст] // Management Automation. – 1986. – №1. – P. 39–41.

27

Glover F. Future paths for integer programming and links to artificial intelligence [Текст] // Computers and Operations Research. – 1986. – Vol.13. – №5. – P. 533–549.

28

Glover F. Heuristics for integer programming using surrogate constraints  [Текст] // Decision Sciences. –1977. – Vol.8. – №1. – P. 156–166.

29

Glover F. Tabu search – Part I [Текст] // ORSA Journal on Computing. – 1989. – №1(3). – P. 190–206.

30

Glover F. Tabu search – Part II [Текст] // ORSA Journal on Computing. – 1990. – №2 (1). – P. 4–32.

31

Goldman R.P. A constraint-based scheduler for batch manufacturing. [Текст] / R.P. Goldman, M.S. Boddy // IEEE Expert 12 (1). – 1997. – P. 49–56.

32

Grabot B. Dispatching rules in scheduling: A fuzzy approach [Текст] / B. Grabot, L. Geneste // International Journal of Production Research. – 1994. – Vol. 32. – №4. – P. 903–915.

33

Graham R.L. Optimization and approximation in deterministic sequencing and scheduling: a survey [Текст] / R.L. Graham, E.L. Lawler, J.K. Lenstra, A.E.G.   Rinnooy Kan // Ann. Discrete Math. – 1979. – №5. – P. 287–326.

34

Grau R. Completion times in multipurpose batch plants with set-up, transfer and clean-up times [Текст] / R. Grau, A. Espuna, L. Puigjaner // Computers and Chemical Engineering. – 1996. – Vol. 20. – P.1143–1148.

35

Graves S.C. A review of production scheduling [Текст] // Operations Research, 29. – 1981. – P.646–675.

36

Graves S.C. Manufacturing Planning and Control. Massachusetts Institute of Technology: Working paper [Текст] / S.C. Graves // In: Handbook of Applied Optimization [ed. by P. Pardalos and M. Resende]. – 1999. – 26 p.

37

Grefenstette J.J. Incorporating problem specific knowledge into genetic algorithms. [Текст] / J.J. Grefenstette // In: Davis L. Genetic Algorithms and Simulated Annealing. – London: Pitman, 1987. – P. 42–60.

38

Grossmann I.E. Mixed integer optimization techniques for the design and scheduling of batch processes. [Текст] / [I.E. Grossmann, I. Quesada, R. Raman, V.T. Voudouris]. – NATO Advanced Study Institute – Batch process system engineering. Antalya, Turkey, 1992. – 47 p.

39

Hans E.W. Resource Loading by Branch-and-Price Techniques: PhD thesis [Текст] / Elias Willem Hans // Twente University, Enschede, 2001. – 164 p.

40

Haupt R.A Survey of Priority Rule-Based Scheduling. [Текст] / R. Haupt // OR Spektrum. – 1989. – №11. – P. 3–16.

41

Hax A.C. Hierarchical Integration of Production Planning and Scheduling [Текст] / A.C. Hax, H.C. Meal // Studies in Management Sciences. – Vol. 1: Logistics [ed. by M.A. Geisler]. – North Holland-American Elsevier, New York, 1975.

42

Henseler H. REAKTION: A System for Event Independent Reactive Scheduling. [Текст] / H. Henseler // In: Artificial Intelligence in Reactive Scheduling [ed. by R.M. Kerr and E. Szelke]. – Chapman & Hall. – 1995

43

Hindi K.S. Detailed scheduling of batch-production in a cell with parallel facilities and common renewable resources. [Текст] / K.S. Hindi, E. Toczylowski // Computers & Industrial Engineering, 28 (4), 839–850. – 1995.

44

Hopfield J.J. Neural Computation of Decisions in Optimization Problems [Текст] / J.J. Hopfield, D.W. Tank // Biological Cybernetics. – 1985. – Vol.52. –