Отримано 04.03.2025, Доопрацьовано 13.06.2025, Прийнято 28.08.2025

Масштабована математична модель розподілу замовлень на виробництво

Костянтин Гріщенко, Олексій Писарчук

У статті запропонована математична модель оптимізаційної задачі планування виробничих замовлень за умов обмежених ресурсів. Зростання варіативності виробництва зумовлює потребу у високопродуктивних і ефективних алгоритмах та моделях, які здатні обробляти велику кількість замовлень і мають високу адаптивність до нових критеріїв, правил та факторів. Метою дослідження був синтез масштабованої математичної моделі, що враховує правила побудови розкладів і дає змогу розв’язувати задачі великої розмірності в прийнятних часових межах. У роботі запропоновано дискретну математичну модель, що включає систему обмежень та критерій оптимізації. Модель відповідає реальним вимогам виробництва, зокрема враховує порядок обробки задач у межах одного замовлення та унеможливлює одночасне виконання задач на одному ресурсі. Для пошуку рішень моделі застосовано алгоритм CP-SAT, що входить до пакету Google Or-Tools і який визнано одним із найбільш продуктивних алгоритмів для задач дискретної оптимізації. Для наборів вхідних даних розмірністю від 5 до 40 проведено вимірювання часових і просторових затрат на розв’язання створеної моделі та знаходження оптимального рішення. З метою підвищення масштабованості підходу розроблено ітеративну модель розподілу замовлень частинами контрольованого розміру. У ній розмір підзадачі визначається параметром, який обмежує кількість замовлень, що включаються до базової моделі, дозволяючи регулювати обчислювальну складність. Результати експериментів продемонстрували, що масштабована модель забезпечила ефективне розв’язання задач розмірністю 60 замовлень за прийнятний для такого роду систем час. Порівняння базової моделі та покращеної засвідчило зниження часових затрат, а також споживання пам’яті для задач великої розмірності. При цьому зафіксовано лінійне масштабування як за часом розрахунку, так і за споживанням пам’яті при зростанні кількості замовлень, що гарантує ефективне застосування цієї моделі також для більших розмірностей. Отриманий результат досліджень створив підґрунтя для практичного застосування розробленої масштабованої моделі в інформаційних системах планування виробництва на підприємствах із високим навантаженням та великими обсягами замовлень

оптимізація; програмування обмеженнями; дискретне лінійне програмування; математична модель; розподіл ресурсів; планування
85-95
Hrishchenko, K, & Pysarchuk, O. (2025). Scalable mathematical model for distribution of production orders. Information Technologies and Computer Engineering, 22(2), 85-95. https://doi.org/10.31649/vitce/2.2025.85

Використані джерела

[1] Andrade-Pineda, J.L., Canca, D., Gonzalez-R, P.L., & Calle, M. (2020). Scheduling a dual-resource flexible job shop with makespan and due date-related criteria. Annals of Operations Research, 291, 5-35. doi: 10.1007/s10479-01903196-0.

[2] Azad, T., Rahman, H.F., Chakrabortty, R.K., & Ryan, M.J. (2022). Optimization of integrated production scheduling and vehicle routing problem with batch delivery to multiple customers in supply chain. Memetic Computing, 14, 355-376. doi: 10.1007/s12293-022-00372-x.

[3] Bit-Monnot, A. (2023). Enhancing hybrid CP-SAT search for disjunctive scheduling. In 26th European conference on artificial intelligence (ECAI 2023) (article number hal-04174800). Krakow: PSSI.

[4] Bondariev, S.I. (2020). Optimization methods of operating costs on road transport in international transportation. Machinery & Energetics, 11(3), 129-133.

[5] Briskorn, D., Boysen, N., & Zey, L. (2024). Scheduling of e-commerce packaging machines: Blocking machines and their impact on the performance – waste tradeoff. Journal of Scheduling, 28, 101-120. doi: 10.1007/s10951-02400826-9.

[6] Camisa, A., Notarnicola, I., & Notarstefano, G. (2020). Distributed primal decomposition for large-scale MILPs. ArXiv. doi: 10.48550/arXiv.2010.14446.

[7] Çetinkaya, F., Yeloğlu, P., & Akkocaoğlu Çatmakaş, H. (2021). Customer order scheduling with job-based processing on ̇ a single-machine to minimize the total completion time. International Journal of Industrial Engineering Computations, 12, 273-292. doi: 10.5267/j.ijiec.2021.3.001.

[8] Feng, Y., Yan, F., & Luo, J. (2020). Memory scaling of cloud-based big data systems: A hybrid approach. IEEE Transactions on Big Data, 8(5), 1259-1272. doi: 10.1109/TBDATA.2020.3035522.

[9] Gao, K., Yang, F., Zhou, M., Pan, Q., & Suganthan, P.N. (2019). Flexible job-shop rescheduling for new job insertion by using discrete Jaya algorithm. IEEE Transactions on Cybernetics, 49(5), 1944-1955. doi: 10.1109/ TCYB.2018.2817240.

[10] Guzman, E., Andres, B., & Poler, R. (2021). Models and algorithms for production planning, scheduling and sequencing problems: A holistic framework and a systematic review. Journal of Industrial Information Integration, 27, article number 100287. doi: 0.1016/j.jii.2021.100287.

[11] Heydar, M., Mardaneh, E., & Loxton, R. (2021). Approximate dynamic programming for an energy-efficient parallel machine scheduling problem. European Journal of Operational Research, 302(1), 363-380. doi: 10.1016/j. ejor.2021.12.041.

[12] Hoffmann, J., Neufeld, J. S., & Buscher, U. (2024). Minimizing the earliness – tardiness for the customer order scheduling problem in a dedicated machine environment. Journal of Scheduling, 27, 525-543. doi: 10.1007/s10951024-00814-z.

[13] Hozhabr Pour, H., Ciortuz, G., Lüers, A., & Fudickar, S. (2025). Performance analysis of a data stream processing system for online activity classification via wearable sensor data. In Proceedings of the 18th international joint conference on biomedical engineering systems and technologies – HEALTHINF (Vol. 2, pp. 571-578). Porto: SciTePress. doi: 10.5220/0013166100003911.

[14] Jiang, X., Chen, Y., Chen, X., & Zhang, H. (2024). An optimal batch size determination method for time series deep learning models. Sustainability, 16(14), article number 5936. doi: 10.3390/su16145936.

[15] Lunardi, W.T., Birgin, E.G., Ronconi, D.P., & Voos, H. (2021). Metaheuristics for the online printing shop scheduling problem. European Journal of Operational Research, 293(2), 419-441. doi: 10.1016/j.ejor.2020.12.021.

[16] Musiał, K., Balashov, A., Burduk, A., & Rysińska-Wojtasik, D. (2023). Solving manufacturing orders scheduling problem using annealing simulation. In J. Machado, F. Soares, J. Trojanowska, E. Ottaviano, P. Valášek, M. Reddy, E.A. Perondi & Y. Basova (Eds.), Innovations in mechanical engineering II. ICIENG 2022. Lecture notes in mechanical engineering (pp. 279-288). Cham: Springer. doi: 10.1007/978-3-031-09382-1_25.

[17] Ofoghi, B., Mak, V., & Yearwood, J. (2020). A knowledge representation approach to automated mathematical modelling. ArXiv. doi: 10.48550/arXiv.2011.06300.

[18] Tomesh, T., Saleem, Z.H., Perlin, M.A., Gokhale, P., Suchara, M., & Martonosi, M. (2023). Divide and conquer for combinatorial optimization and distributed quantum computation. In 2023 IEEE international conference on quantum computing and engineering (QCE) (pp. 1-12). Bellevue: IEEE. doi: 10.1109/QCE57702.2023.00009.

[19] Ulrich-Oltean, F., Nightingale, P., & Walker, J.A. (2023). Learning to select SAT encodings for pseudo-Boolean and linear integer constraints. Constraints, 28, 397-426. doi: 10.1007/s10601-023-09364-1.

[20] Wang, L., Liu, H., Xia, M., Wang, Y., & Li, M. (2023). Research on a multilevel scheduling model for multi variety and variable batch production environments based on machine learning. Frontiers in Energy Research, 11. doi: 10.3389/ fenrg.2023.1251335.

[21] Wessén, J., Carlsson, M., Schulte, C., & Syberfeldt, A. (2023). A constraint programming model for the scheduling and workspace layout design of a dual-arm multi-tool assembly robot. Constraints, 28, 71-104. doi: 10.1007/s10601-02309345-4.

[22] Yang, H., Zhao, M., Yuan, L., Yu, Y., Li, Z., & Gu, M. (2023). Memory-efficient transformer-based network model for traveling salesman problem. Neural Networks, 161, 589-597. doi: 10.1016/j.neunet.2023.02.014.

[23] Zhang, M., Lu, Y., Hu, Y., Amaitik, N., & Xu, Y. (2022). Dynamic scheduling method for job-shop manufacturing systems by deep reinforcement learning with proximal policy optimization. Sustainability, 14, article number 5177. doi: 10.3390/su14095177.