DOI: https://doi.org/10.20998/2079-0023.2018.44.04

ДОСЛІДЖЕННЯ ЕФЕКТИВНОСТІ ТРИРІВНЕВОЇ МОДЕЛІ ПЛАНУВАННЯ ДРІБНОСЕРІЙНОГО ВИРОБНИЦТВА

Taras Nikolayevich Lisetsky

Анотація


Розглядається задача знаходження портфеля замовлень, який максимізує сумарний прибуток за одним з п’яти критеріїв оптимізації та при якому дотримано початок планового періоду і директивні строки, задані замовниками. Також потрібно побудувати для цього портфеля за­мовлень допустимий (що не порушує директивних строків) поопераційний план виконання робіт, якому відповідав би мінімально можливий час виконання всього портфеля замовлень. Показано, що задача в такій постановці є багатоетапною задачею календарного планування. Опи­сується раніше розроблена методологія розв’язання задачі – трирівнева модель планування виробництва. Обґрунтовується можливість за­стосування методології для будь-якого виду дрібносерійного виробництва за одним з даних п’яти критеріїв оптимальності. Показано, що для будь-якого виду виробництва, при будь-якій вихідній технології виконання виробів і при будь-якій реалізації багатоетапної задачі календар­ного планування, розв’язання задачі планування за одним з цих п’яти критеріїв оптимальності зводиться до отримання припустимого розв’язку багатоетапної задачі календарного планування за критерієм максимізації моменту запуску найбільш ранньої роботи. Показано, що ефективність розв’язання багатоетапної задачі календарного планування залежить від ефективності розв’язання першого рівня трирівневої моделі. Тому, статистично досліджується і обґрунтовується ефективність розв’язання задачі мінімізації сумарного зваженого моменту закінчення виконання робіт з відносинами передування на одному приладі. Показана ефективність ПДС-алгоритму розв’язання задачі для випадку, коли ваги всіх вершин графа передування, крім кінцевих, дорівню­ють нулю. Показано, що наближений алгоритм розв’язання цієї задачі дозволяє розв’язувати реальні практичні задачі великої розмірності (перевірялися розмірності до 10,000 робіт). Розв’язки, отримані наближеним алгоритмом, збіглися з отриманими точним ПДС-алгоритмом в 99.97 % випадків.

Ключові слова


планування виробництва; ПДС-алгоритм; точний алгоритм; наближений алгоритм; комбінаторна оптимізація; складання розкладів

Повний текст:

PDF (English)

Посилання


Zgurovsky M. Z., Pavlov A. A. Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications. Cham (Switzerland): Springer, 2019. 526 p. Chapter 9, The four-level model of planning and decision making, pp. 347–406. doi: 10.1007/978-3-319-98977-8_8

Bitran G. R., Haas E. A., Hax A. C. Hierarchical production planning: a single stage system. Operations Research, 1981, vol. 29, pp. 717–743. doi: 10.1287/opre.29.4.717

Bitran G. R., Hax A. C. Disaggregation and resource allocation using convex knapsack problems. Management Science, 1981, vol. 27. pp. 431–441. doi: 10.1287/mnsc.27.4.431

Bitran G. R., Hax A. C. On the design of hierarchical production planning systems. Decision Science, 1977, vol. 8, pp. 28–55. doi: 10.1111/j.1540-5915.1977.tb01066.x

Bitran G. R., Tirupati D. Hierarchical production planning / S. C. Graves, A. H. G. Rinnooy Kan, P. H. Zipkin (eds.). Handbooks in Operations Research and Management Science, 1993, vol. 4, pp. 523–568. doi: 10.1016/s0927-0507(05)80190-2

Hax A. C., Meal H. C. Hierarchical integration of production planning and scheduling. Studies in Management Sciences, 1975, vol. 1, pp. 53–69.

Zgurovsky M. Z., Pavlov A. A. Prinyatie resheniy v setevykh sistemakh s ogranichennymi resursami [Decision making in network systems with limited resources]. Kiev, Nauk. dumka Publ., 2010. 573 p.

Pavlov O. A., Misura O. B., Melnikov O. V., Shcherbatenko O. V., Mykhaylov V. V. Zahal'na skhema planuvannya ta upravlinnya skladnymy ob'yektamy, shcho mayut' merezhne predstavlennya tekhnolohichnykh protsesiv y obmezheni resursy [The general scheme of planning and management of complex objects that represent network processes and have limited resources]. Vestnik Nats. tekhn. un-ta Ukr. "KPI". Seriya: Informatyka, upravlinnya ta obchyslyuval'na tekhnika [Bulletin of the National Technical University of Ukraine "KPI". Series: Informatics, operation and computer science]. Kiev, VEK+ Publ., 2009, no. 49, pp. 77–87.

Pavlov O. A., Misura O. B., Melnikov O. V., Arakelyan G. A., Shcherbatenko O. V., Mykhaylov V. V., Lisetsky T. N. Informatsiyna tekhnolohiya iyerarkhichnoho planuvannya ta pryynyattya rishen' v orhanizatsiyno-vyrobnychykh systemakh [The system of hierarchical planning and decision making in organizational and production systems]. Vestnik Nats. tekhn. un-ta Ukr. "KPI". Seriya: Informatyka, upravlinnya ta obchyslyuval'na tekhnika [Bulletin of the National Technical University of Ukraine "KPI". Series: Informatics, operation and computer science]. Kiev, VEK+ Publ., 2010, no. 52, pp. 3–14.

Zgurovsky M. Z., Pavlov A. A. Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications. Cham (Switzerland): Springer, 2019. 526 p. Chapter 9, Algorithms and software of the four-level model of planning and decision making, pp. 407–518. doi: 10.1007/978-3-319-98977-8_9

Zgurovsky M. Z., Pavlov A. A., Misura E. B., Melnikov O. V., Lisetsky T. N. Metodologiya postroeniya chetyrekhurovnevoy modeli planirovaniya, prinyatiya resheniy i operativnogo plani-rovaniya v setevykh sistemakh s ogranichennymi resursami [Implementation of the methodology of the four-level model of planning, decision-making and operational management in networked systems with limited resources]. Vestnik Nats. tekhn. un-ta Ukr. "KPI". Seriya: Informatyka, upravlinnya ta obchyslyuval'na tekhnika [Bulletin of the National Technical University of Ukraine "KPI". Series: Informatics, operation and computer science]. Kiev, VEK+ Publ., 2014, no. 61, pp. 60–84.

Pavlov A. A., Lisetsky T. N. Nestatsionarnyy metod analiza ierarkhiy v zadachakh ierarkhicheskogo planirovaniya i prinyatii resheniy. Vestnik Nats. tekhn. un-ta Ukr. "KPI". Seriya: Informatyka, upravlinnya ta obchyslyuval'na tekhnika [Bulletin of the National Technical University of Ukraine "KPI". Series: Informatics, operation and computer science]. Kiev, VEK+ Publ., 2011, no. 54, pp. 82–86.

Zgurovsky M. Z., Pavlov A. A. Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications. Cham (Switzerland): Springer, 2019. 526 p. Chapter 7, The total weighted completion time of tasks minimization with precedence relations on a single machine, pp. 291–344. doi: 10.1007/978-3-319-98977-8_7


Пристатейна бібліографія ГОСТ