Мінімізація сумарного зваженого моменту випередження виконання завдань на одному приладі
Анотація
Розглядається задача побудови допустимого розкладу виконання завдань з різними директивними строками на одному приладі, оптимального за критеріями: перший – максимально пізній момент запуску приладу, другий – мінімізація сумарного зваженого моменту випередження виконання завдань допустимого розкладу. Критерії задані в лексикографічному порядку, тобто момент запуску приладу максимально пізній, і при виконанні цієї умови на допустимому розкладі досягається мінімально можливе значення сумарного зваженого моменту випередження виконання завдань. Автори показали, що ця задача є якісно більш складною, ніж сформульована вище задача з рівними додатними вагами. В цій роботі пропонується точний метод, що ґрунтується на побудові дерев допустимих розв’язків. Принципово новими є сформульовані обмеження на множину вершин кожного рівня та теоретично обґрунтовані ефективні правила відсікання гілок, що статистично значимо починають реалізовуватися на перших рівнях дерева допустимих розв’язків. Практичне значення запропонованого методу ілюструється можливістю його застосування в багаторівневій моделі управління інноваційними проектами на останньому рівні її ієрархії.
Посилання
Wang, Z.Y., Lu, C. (2021). An integrated job shop scheduling and assembly sequence planning approach for discrete manufacturing. Journal of Manufacturing Systems, 61, 27-44. doi: 10.1016/j.jmsy.2021.08.003
Li, X., Gao, L. (2020). Introduction for Integrated Process Planning and Scheduling. In: Effective Methods for Integrated Process Planning and Scheduling. Engineering Applications of Computational Methods, vol 2. Springer, Berlin, Heidelberg. doi: 10.1007/978-3-662-55305-3_1
Tuo, L., Dai, L., Chen, X. (2014). Scheduling of Discrete Manufacturing Process for Energy Saving. In: Applied Mechanics and Materials (Vols. 556–562, pp. 4248–4254). Trans Tech Publications, Ltd. doi: 10.4028/www.scientific.net/amm.556-562.4248
Kulcsár, G., & Kulcsárné, F.M. (2009). Solving multi-objective production scheduling problems using a new approach. Production Systems and Information Engineering, A Publication of the University of Miskolc, 5, 81–94.
Pavlov, A.A. (2021). Long-Term Operational Planning of a Small-Series Production Under Un¬cer¬tainty (Theory and Practice). In: Hu, Z., Petoukhov, S., Dychka, I., He, M. (eds) Advances in Com¬puter Science for Engineering and Education III. ICCSEEA 2020. Advances in Intelligent Systems and Computing, vol 1247, pp. 167-180. Springer, Cham. doi: 10.1007/978-3-030-55506-1_15
Pavlov, A.A., Khalus, E.A., Borysenko, I.V. (2019). Planning Automation in Discrete Systems with a Given Structure of Technological Processes. In: Hu, Z., Petoukhov, S., Dychka, I., He, M. (eds) Advances in Computer Science for Engineering and Education. ICCSEEA 2018. Advances in Intelligent Systems and Computing, vol 754, pp. 177-185. Springer, Cham. doi: 10.1007/978-3-319-91008-6_18
Pavlov, A.A., Misura, E.B., Melnikov, O.V., Mukha, I.P. (2019). NP-Hard Scheduling Problems in Planning Process Automation in Discrete Systems of Certain Classes. In: Hu, Z., Petoukhov, S., Dychka, I., He, M. (eds) Advances in Computer Science for Engineering and Education. ICCSEEA 2018. Advances in Intelligent Systems and Computing, vol 754, pp. 429-436. Springer, Cham. doi: 10.1007/978-3-319-91008-6_43
Zgurovsky, M.Z., Pavlov, A.A. (2019). Optimal Scheduling for Two Criteria for a Single Machine with Arbitrary Due Dates of Tasks. In: Combinatorial Optimization Problems in Planning and Decision Making. Studies in Systems, Decision and Control, vol 173, pp. 17-38. Springer, Cham. doi: 10.1007/978-3-319-98977-8_2
Zgurovsky, M.Z., Pavlov, A.A. (2019). Algorithms and Software of the Four-Level Model of Planning and Decision Making. In: Combinatorial Optimization Problems in Planning and Decision Making. Studies in Systems, Decision and Control, vol 173, pp. 407-518. Springer, Cham. doi: 10.1007/978-3-319-98977-8_9
Авторське право (c) 2023 Олександр Павлов, Олена Халус, Михайло Медведєв (Автор)
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
