Scalable mathematical model for distribution of production orders

Abstract

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

The 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 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.