рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2025. Vol 53

Evolutionary Algorithms for Customer Order Scheduling

Author(s)

Pavel A. Borisovsky1,  Aleksey O. Zakharov1, Yulia V. Zakharova1

1 Sobolev Institute of Mathematics SB RAS, Omsk Department, Omsk, Russian Federation

Abstract
The problem of customer order scheduling is investigated. The order of a customer consists of several products. We consider single-machine case and multi-machine case. In the first case when the unit is switched from one product to another a setup operation arises. In the second case dedicated machines are used for producing products without setup times. We consider the total completion time criterion. A genetic algorithm with optimized operators and a hybrid iterated local search combined with the “Go with the winners” approach are proposed. The results of the experimental evaluation are analysed on a series of benchmark instances and compared with state-of-the-art metaheuristics.
About the Authors

Pavel A. Borisovsky, Cand. Sci. (Phys.Math.), Sobolev Institute of Mathematics SB RAS (Omsk Department), Omsk, 644099, Russian Federation, pborisovsky@ofim.oscsbras.ru

Aleksey O. Zakharov, Cand. Sci. (Phys.Math.), Sobolev Institute of Mathematics SB RAS (Omsk Department), Omsk, 644099, Russian Federation, azakharov@ofim.oscsbras.ru

Yulia V. Zakharova, Cand. Sci. (Phys.Math.), Sobolev Institute of Mathematics SB RAS (Omsk Department), Omsk, 644099, Russian Federation, yzakharova@ofim.oscsbras.ru

For citation

Borisovsky P. A., Zakharov A. O., Zakharova Yu. V. Evolutionary Algorithms for Customer Order Scheduling. The Bulletin of Irkutsk State University. Series Mathematics, 2025, vol. 53, pp. 3–17. https://doi.org/10.26516/1997-7670.2025.53.3

Keywords
scheduling, production, setup time, model, evolutionary algorithm
UDC
004.023, 519.854.2
MSC
90C27, 90C59, 68W50
DOI
https://doi.org/10.26516/1997-7670.2025.53.3
References
  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

Full text (english)