A Decomposition Approach in the Problem of Distribution-Type Planning with Priority Constraints

В статье рассматривается задача планирования распределительного типа с приоритетами ограничений. Для заданного множества требований и ресурсов с установленными параметрами использования необходимо построить план назначений, удовлетворяющий системе приоритетных ограничений. При этом различают две очереди ограничений на количественные и качественные характеристики соответственно. На этапе решения задачи с первой очередью ограничений разрабатывается базовая модель целочисленного линейного программирования (ЦЛП) и динамическая схема ее формирования. В рамках такого подхода исходная задача сводится к решению последовательности аналогичных задач существенно меньшей размерности, что позволяет учитывать приоритеты использования ресурсов непосредственно по построению и гарантирует сходимость базовой модели ЦЛП на финальной итерации динамической схемы. На этапе реализации второй очереди ограничений для полученного базового решения вводится интегральный критерий в форме верхней оценки и рассматривается модифицированная модель ЦЛП. Процедура модификации модели опирается на метод штрафных функций и включает дооснащение системы ограничений, целевого функционала и функционального пространства подмножеством вспомогательных булевских переменных. При этом доказано, что модифицированная модель гарантировано разрешима и определяет при этом максимальную (по включению) совместную подсистему ограничений второй очереди для исходной задачи. В рамках анализа работоспособности и эффективности предложенного подхода проводится вычислительный эксперимент с использованием данных реальной размерности.

Ключевые слова

теория расписаний; целочисленное линейное программирование; дискретное производство; система планирования производственных процессов; декомпозиционный подход.

Литература

. Борисовский, П.А. Построение расписаний многопродуктового производства с использованием целочисленного линейного программирования и эволюционных вычислений / П.А. Борисовский, А.В. Еремеев // Информационные технологии. - 2015. - Т. 21, № 6. - С. 412-421.
2. Janak, S.L. Production scheduling of a large-scale industrial batch plant: short-term and medium-term scheduling / S.L. Janak, C.A. Floudas, J. Kallrath, N. Vormbrock // Industrial and Engineering Chemistry Research. - 2006. - V. 45, № 25. - P. 8234-8252.
3. Славянов, А.С. Анализ и практическое применение моделей распределения ресурсов // Бюллетень науки и практики. - 2018. - Т. 4, № 9. - С. 228-244.
4. Menshikh, V.V. Models of resource allocation optimization when solving the control problems in organizational systems / V.V. Menshikh, A.F. Samorokovsky, O.S. Avsentev // Journal of Physics: Conference Series. - 2018. - Vol. 973, № 1. - P. 12-40.
5. Rezig, S. Mathematical model for production plan optimization: a case study of descrete event systems / S. Rezig, W. Ezzeddine, S. Turki, N. Rezg // Mathematics. - 2020. - № 8(6). - P. 955-971. DOI: 10.3390/math8060955
6. Ганичева, А.В. Метод решения задачи оптимизации распределения целочисленного ресурса / А.В. Ганичева, А.В. Ганичев // Прикладная математика и вопросы управления. - 2021. - № 4. - С. 42-55. DOI: 10.15593/2499-9873/2021.4.03
7. Lazarev, A.A. Integer Statements of the Problem of Forming Railway Trains and Schedules of Their Movement / A.A. Lazarev, E.G. Musatova // Management of Large Systems. - 2012. - V. 38. - P. 161-169.
8. Gainanov, D.N. On Track Procession Assignment Problem at the Railway Network Sections / D.N. Gainanov, A.N. Ignatov, A.V. Naumov, V.A. Rasskazova // Automation and Remote Control. - 2020. - V. 81, № 6. - P. 967-977.
9. Kabulova, E.G. Intelligent Management of Multi-Stage Systems of Metallurgical Production // Modeling, optimization, and information technology. - 2018. - V. 7, № 1(24). - P. 341-351.
10. Gitman, M.B. On Optimization of Metal Forming with Adaptable Characteristics / M.B. Gitman, P.V. Trusov, S.A. Fedoseev // Journal of Applied Mathematics and Computing. - 2020. - V. 7, № 2. - P. 387-396.
11. Gainanov, D.N. Algorithm for Predicting the Quality of the Product of Metallurgical Production / D.N. Gainanov, D.A. Berenov // CEUR Workshop Proceedings. - Petrovac, 2017. - V. 1987. - P. 194-200.
12. Qiu, Y. Scheduling a Realistic Hybrid Flow Shop with Stage Skipping and Adjustable Processing Time in Steel Plants / Y. Qiu, L. Wang, X. Xu, X. Fang, P. Pardalos // Applied Soft Computing. - 2018. - V. 64. - P. 536-549.
13. Kong, Min. A Robust Optimization Approach for Integrated Steel Production and Batch Delivery Scheduling with Uncertain Rolling Times and Deterioration Effect / Min Kong, Jun Pei, Jin Xu, Xinbao Liu, P. Pardalos // International Journal of Production Research. - 2020. - V. 58, № 17. - P. 5132-5154.
14. Long, Jianyu. A Robust Dynamic Scheduling Approach Based on Release Time Series Forecasting for the Steelmaking Continuous Casting Production / Jianyu Long, Zhenzhong Sun, P. Pardalos, Yun Bai, Shaohui Zhang, Chuan Li // Applied Soft Computing. - 2020. - V. 92. - Article ID: 106271.
15. Gainanov, D.N. Heuristic Algorithm for Finding the Maximum Independent Set with Absolute Estimate of the Accuracy / D.N. Gainanov, N. Mladenovic, D. Urosevic, V.A. Rasskazova // CEUR-WS Proceedings. - Omsk, 2018. - V. 2098. - P. 141-149.