Scalable mathematical model for distribution of production orders
Kostiantyn Hrishchenko, Oleksii PysarchukThe article proposed a mathematical model of the optimisation problem of planning production orders under conditions of limited resources. The growth in production variability necessitates highly productive and efficient algorithms and models that are capable of processing large numbers of orders and are highly adaptable to new criteria, rules and factors. The aim of the study was to synthesise a scalable mathematical model that takes into account the rules for constructing schedules and allows solving large-scale problems within acceptable time limits. The study proposed a discrete mathematical model that includes a system of constraints and an optimisation criterion. The model meets the real requirements of production, in particular, it takes into account the order of processing tasks within a single order and makes it impossible to perform tasks simultaneously on one resource. To find solutions to the model, the CP-SAT algorithm was used, which is part of the Google Or-Tools package and is recognised as one of the most productive algorithms for discrete optimisation tasks. For input data sets ranging from 5 to 40 dimensions, measurements were taken of the time and space costs of solving the created model and finding the optimal solution. In order to improve the scalability of the approach, an iterative model for distributing orders in controlled-size parts was developed. In it, the size of the subtask is determined by a parameter that limits the number of orders included in the base model, allowing the computational complexity to be adjusted. The results of the experiments showed that the scalable model provided an effective solution to problems with a dimension of 60 orders in a time acceptable for this type of system. A comparison of the basic model and the improved model showed a reduction in time consumption and memory consumption for large-scale tasks. At the same time, linear scaling was observed in both calculation time and memory consumption as the number of orders increased, which guarantees the effective application of this model for larger scales as well. The results of the research laid the foundation for the practical application of the developed scalable model in production planning information systems at enterprises with high loads and large order volumes
References
[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.