рус eng
«ИЗВЕСТИЯ ИРКУТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА». СЕРИЯ «МАТЕМАТИКА»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

Список выпусков > Серия «Математика». 2025. Том 53

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

Автор(ы)

П. А. Борисовский1,  А. О. Захаров1, Ю. В. Захарова1

1 Институт математики им. С. Л. Соболева СО РАН, Омский филиал, Омск, Российская Федерация


Аннотация
Исследуется задача составления расписаний выполнения заказов клиентов. Заказ клиента состоит из нескольких продуктов. Рассматривается случай с одной машиной и случай с несколькими машинами. В первом случае, когда машина переключается с одного продукта на другой, возникает переналадка. Во втором случае используются специализированные машины для производства продуктов без переналадок. Изучается критерий суммарного времени завершения. Предложены генетический алгоритм с оптимизированными операторами и гибридный алгоритм итеративного локального поиска в сочетании с подходом «Иди с победителями». Результаты экспериментального исследования анализируются на серии тестовых примеров и сравниваются с современными метаэвристиками.
Об авторах

Борисовский Павел Александрович, канд. физ.-мат. наук, Институт математики им. С. Л. Соболева СО РАН (Омский филиал), Омск, 644099, Российская Федерация, pborisovsky@ofim.oscsbras.ru

Захаров Алексей Олегович, канд. физ.-мат. наук, Институт математики им. С. Л. Соболева СО РАН (Омский филиал), Омск, 644099, Российская Федерация, azakharov@ofim.oscsbras.ru

Захарова Юлия Викторовна, канд. физ.-мат. наук, Институт математики им. С. Л. Соболева СО РАН (Омский филиал), Омск, 644099, Российская Федерация, yzakharova@ofim.oscsbras.ru


Ссылка для цитирования
Borisovsky P. A., Zakharov A. O., Zakharova Yu. V. Evolutionary Algorithms for Customer Order Scheduling // Известия Иркутского государственного университета. Серия Математика. 2025. Т. 53. C. 3–17. https://doi.org/10.26516/1997-7670.2025.53.3
Ключевые слова
расписание, производство, переналадка, модель, эволюционный алгоритм
УДК
004.023, 519.854.2
MSC
90C27, 90C59, 68W50
DOI
https://doi.org/10.26516/1997-7670.2025.53.3
Литература
  1. Aldous D., Vazirani U. “Go with the winners” algorithms. In Proceedings of 35th Annual Symposium on Foundations of Computer Science. IEEE, 1994, pp. 492–501. https://doi.org/10.1109/SFCS.1994.365742 
  2. Borisovsky P.A. A parallel “Go with the winners” algorithm for some scheduling problems. Jour. Appl. Indust. Math., 2023, vol. 17, no. 4, pp. 687–697. https://doi.org/10.1134/S1990478923040014 
  3. Borisovsky P., Eremeev A., Kallrath J. Multi-product continuous plant scheduling: combination of decomposition, genetic algorithm, and constructive heuristic. International Journal of Production Research, 2020, vol. 58, no. 9, pp. 2677–2695. https://doi.org/10.1080/00207543.2019.1630764 
  4. Borisovsky P., Kovalenko Y. A Memetic algorithm with parallel local search for flowshop scheduling problems. In Proceedings of Bioinspired Optimization Methods and Their Applications, Springer, Cham, 2020, LNCS, vol. 12438, pp. 201–213. https://doi.org/10.1007/978-3-030-63710-1_16
  5. Cetinkaya F.C., Yeloglu P., Catmakas H.A. Customer order scheduling with job-based processing on a single-machine to minimize the total completion time. Inter. Jour. Indust. Engin. Comput., 2021, vol. 12, no. 3, pp. 273–292. https://doi.org/10.5267/j.ijiec.2021.3.001
  6. Doerr B., Doerr C., Ebel F. From black-box complexity to designing new genetic algorithms. Theoretical Computer Science, 2015, vol. 567, pp. 87–104. https://doi.org/10.1016/j.tcs.2014.11.028. 
  7. Erel E., Ghosh J.B. Customer order scheduling on a single machine with family setup times: Complexity and algorithms. Applied Mathematics and Computation, 2007, vol. 185, no. 1, pp. 11–18. https://doi.org/10.1016/j.amc.2006.06.086
  8. Eremeev A.V. Genetic algorithm with tournament selection as a local search method. J. Appl. Industr. Math., 2012, vol. 6, no. 3, pp. 286–294. https://doi.org/10.1134/S1990478912030039 
  9. Eremeev A. Kovalenko Y. Optimal recombination in genetic algorithms for combinatorial optimization problems: part II. Yugoslav. J. Oper. Res., 2014, vol. 24, no. 2, pp. 165–186. https://doi.org/10.2298/YJOR131030041E 
  10. Framinan J.M., Perez-Gonzalez P. New approximate algorithms for the customer order scheduling problem with total completion time objective. Computers & Operations Research, 2017, vol. 78, pp. 181–192. https://doi.org/10.1016/j.cor.2016.09.010 
  11. Hazir O., Gunalay Y., Erel E. Customer order scheduling problem: a comparative metaheuristics study. The International Journal of Advanced Manufacturing Technology, 2008, vol. 37, pp. 589–598. https://doi.org/10.1007/s00170-007-0998-8 
  12. Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbo, University of Michigan Press, 1975. 
  13. Kellegoz T., Toklu B., Wilson J. Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem. Applied Mathematics and Computation, 2008, vol. 199, no. 2, pp. 590–598. https://doi.org/10.1016/j.amc.2007.10.013 
  14. Kovalenko Y.V., Zakharov A.O. The Pareto set reduction in bicriteria customer order scheduling on a single machine with setup times. Journal of Physics: Conference Series, 2020, vol. 1546, 8 p. https://doi.org/10.1088/1742-6596/1546/1/012087 
  15. Roemer T.A. A note on the complexity of the concurrent open shop problem. Journal of scheduling, 2006, vol. 9, pp. 389–396. https://doi.org/10.1007/s10951-006-7042-y 
  16. Rudolph G. Finite markov chain results in evolutionary computation: A tour d’horizon. Fundamental Informaticae, 1998, vol. 35, no. 1–4, pp. 67–89. https://10.3233/FI-1998-35123405 
  17. Shi Zh., Wang L., Liu P., Sci L. Minimizing Completion Time for Order Scheduling: Formulation and Heuristic Algorithm. IEEE Transactions on Automation Science and Engineering, 2017, vol. 14, no. 4, pp. 1558–1569. https://10.1109/TASE.2015.2456131 
  18. Shi Zh., Ma H., Ren M., Wu T., Yu A.J. A learning-based two-stage optimization method for customer order scheduling. Comput. Oper. Res., 2021, vol. 136, 18 p. https://doi.org/10.1016/j.cor.2021.105488 
  19. Wang G., Cheng T.C.E. Customer order scheduling to minimize total weighted completion time. Omega, 2007, vol. 35, no. 5, pp. 623–626. https://doi.org/10.1016/j.omega.2005.09.007 
  20. Wu Ch.-Ch., Bai D., Zhang X. A robust customer order scheduling problem along with scenario-dependent component processing times and due dates. Journal of Manufacturing Systems, 2021, vol. 58(A), pp. 291–305. https://doi.org/10.1016/j.jmsy.2020.12.013 
  21. Yagiura M., Ibaraki T.: The use of dynamic programming in genetic algorithms for permutation problems. Euro. Jour. Oper. Res., 1996, vol. 92, no. 2, pp. 387–401. https://doi.org/10.1016/0377-2217(94)00301-7 
  22. Zakharov A., Zakharova Yu. Integer programming models and metaheuristics for customer order scheduling. In Proceedings of Mathematical Optimization Theory and Operations Research, CCIS, 2024, vol. 2239 (accepted) 
  23. Zakharova Yu. Hybrid evolutionary algorithm with optimized operators for total weighted Tardiness Problem. In Proceedings of Mathematical Optimization Theory and Operations Research, Springer, Cham, 2023, LNCS, vol. 13930, pp. 224–238. https://doi.org/10.1007/978-3-031-35305-5_15

Полная версия (english)