Cоставление расписаний как задача удовлетворения ограничений (на примере планирования открытых горных работ)
- Авторы: Зуенко А.А1, Олейник Ю.А1
-
Учреждения:
- ИИММ КНЦ РАН
- Выпуск: Том 23, № 5 (2024)
- Страницы: 1290-1310
- Раздел: Искусственный интеллект, инженерия данных и знаний
- URL: https://ogarev-online.ru/2713-3192/article/view/265751
- DOI: https://doi.org/10.15622/ia.23.5.1
- ID: 265751
Цитировать
Полный текст
Аннотация
Описываемые в статье исследования направлены на развитие методов составления расписаний. Принципиальным недостатком существующих методов смешано- целочисленного линейного программирования в применении к рассматриваемым задачам является то, что они слишком требовательны к объемам оперативной памяти. Сложность же применения процедур локального поиска к подобным задачам высокой размерности состоит в разработке эффективного способа нахождения приемлемого первоначального приближения и определении функции перехода в соседнее состояние, которая бы позволила достаточно быстро достичь оптимума. В теории исследования операций добавление к задаче дополнительных условий может привести к принципиальному изменению используемой схемы решения задачи. Предлагаемые в статье методы реализованы в рамках парадигмы программирования в ограничениях, что позволяет более экономно с точки зрения оперативной памяти представлять зависимости предметной области, а также обеспечивает возможность поэтапного учета разнородных условий задачи без принципиального изменения схемы поиска решений. Существенная часть исследований посвящена использованию методов логического вывода на ограничениях для снижения размерности пространства поиска и ускорения процесса вычислений. Подход к составлению расписаний проиллюстрирован на задаче оптимизации планирования открытых горных работ, которую впервые предложено решать как задачу удовлетворения ограничений. Для нахождения первого допустимого решения предложен метод «жадного» поиска, результат применения которого затем может быть улучшен с помощью разработанного гибридного метода. Оба метода опираются на оригинальные процедуры вывода на ограничениях. Предложенный подход доказал свою эффективность для блочных моделей размерностью в десятки и сотни тысяч блоков.
Об авторах
А. А Зуенко
ИИММ КНЦ РАН
Email: zuenko@iimm.ru
улица Ферсмана 24А
Ю. А Олейник
ИИММ КНЦ РАН
Email: yoleynik@iimm.ru
улица Ферсмана 24А
Список литературы
- Baptiste Ph., Le Pape C., Nuijten W. Constraint-based scheduling: applying constraint programming to scheduling problems // Kluwer Academic Publishers. 2001. 198 p.
- Patidar M., Bhardwaj R., Choudhary S. The study of linear programming approach for optimal scheduling of work in a corporation with different models // Materials Today: Proceedings. 2020. vol. 29. no. 2. pp. 661–667.
- Ulaga L., Durasevic M., Jakobovic D. Local search based methods for scheduling in the unrelated parallel machines environment // Expert Systems with Applications. 2022. vol. 199.
- Chen, Y., Lu J., He R., Ou J. An efficient local search heuristic for earth observation satellite integrated scheduling // Applied Sciences. 2020. vol. 10. no. 16.
- Belaid M., Bessiere C., Lazaar N. Constraint Programming for Association Rules // Proceedings of the International Conference on Data Mining. Society for Industrial and Applied Mathematics. 2019. pp. 127–135.
- Russell S., Norvig P., Davis E. Artificial intelligence: a modern approach –3 ed. // Upper Saddle River: Prentice Hall. 2010. 1132 p.
- Narvaez D. Constraint Satisfaction Techniques for Combinatorial Problems // Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence. 2018. vol. 32. no. 1. pp. 8028–8029.
- Alipour A., Khodaiari A., Jafari A., Tavakkoli-Moghaddam R. An integrated approach to open-pit mines production scheduling // Resources Policy. 2022. vol. 75.
- Novitasari R., Rosyidi C., Aisyati A. A Cut-off Grade Optimization Model in Multi Product Open Pit Mining Considering Reclamation and Valuable Waste Materials // IOP Conference Series: Materials Science and Engineering. 2021. vol. 1096. no. 1. doi: 10.1088/1757-899X/1096/1/012021.
- Tolouei K., Moosavi E., Tabrizi A., Afzal P., Bazzazi A. An optimization approach for uncertainty-based long-term production scheduling in open-pit mines using meta-heuristic algorithms // International Journal of Mining, Reclamation and Environment. 2021. vol. 35. no. 2. pp. 115–140.
- Caccetta L. Application of Optimization Techniques in Open Pit Mining // Handbook of Operations Research in Natural Resources. Boston: Springer US, 2007. vol. 99. pp. 547–559.
- Espinoza D., Goycoolea M., Moreno E., Newman A. MineLib: a library of open pit mining problems // Annals of Operations Research. 2013. vol. 206. no. 1. pp. 93–114.
- Oleynik Y., Zuenko A. Open Pit Mine Production Scheduling using New Global Constraint // Proceedings of IEEE International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON). 2022. pp. 1700–1704.
- Regin J. Global Constraints: A Survey // Hybrid Optimization: The Ten Years of CPAIOR. 2011. pp. 63–134.
- Mara S., Norcahyo R., Jodiawan P., Lusiantoro L., Rifai A. A survey of adaptive large neighborhood search algorithms and applications // Computers Operations Research. 2022. vol. 146.
- Audemard G., Lecoutre C., Prudhomme C. Guiding Backtrack Search by Tracking Variables during Constraint Propagation // Proceedings of the 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs). 2023. vol. 280. pp. 9:1–9:17.
- Kozik M. Solving CSPs using weak local consistency // SIAM Journal on Computing. 2021. vol. 50. no. 4. pp. 1263–1286.
- Fathollahzadeh K., Mardaneh E., Cigla M., Waqar Ali Asad M. A mathematical model for open pit mine production scheduling with Grade Engineering and stockpiling // International Journal of Mining Science and Technology. 2021. vol. 31(4). pp. 717–728.
Дополнительные файлы
