Analysis of modification of the evolutionary algorithm for sequencing production tasks

Piotr Ciepliński, Sławomir Golak, Tadeusz Wieczorek

Department of Industrial Computer Science, Faculty of Materials Engineering, Silesian University of Technology, Katowice, Poland.

DOI:

https://doi.org/10.7494/cmms.2022.3.0783

Abstract:

Evolutionary algorithms are one of the heuristic techniques used to solve task sequencing problems. An important example of such a problem is the issue of sequencing production tasks. The combinatorial optimization of task sequences allows the minimization of the cost or time of a set of production tasks by reducing the components of these values which are present in the transitions between tasks.
This paper aims to analyze the influence of the production nature expressed by a set of production task parameters and a definition of the task transition cost on the effectiveness of the modification of the evolutionary algorithm based on new directed stochastic mutation operators. The research carried out included the influence of the space dimension of the task parameters, the number of levels of the value of the cost function, and a definition of this function. The results obtained allow us to assess the effectiveness of the directed mutation in task sequencing for productions of various natures.

Cite as:

Ciepliński, P., Golak, S., & Wieczorek, T. (2022). Analysis of modification of the evolutionary algorithm for sequencing production tasks. Computer Methods in Materials Science, 22(3), 157-166. https://doi.org/10.7494/cmms.2022.3.0783

Article (PDF):

Keywords:

Evolutionary algorithm, Task sequencing, Mutation operator

References:

Abdoun, O., Abouchabaka, J., & Tajani, C. (2012). Analyzing the performance of mutation operators to solve the travelling salesman problem. International Journal of Emerging Sciences, 2(1), 61–77. https://doi.org/10.48550/arXiv.1203.3099.

Bang-Jensen, J., Gutin, G., & Yeo, A. (2004). When the greedy algorithm fails. Discrete Optimization, 1(2), 121–127. https://doi.org/10.1016/j.disopt.2004.03.007.

Banzhaf, W. (1990). The “molecular” traveling salesman. Biological Cybernetics, 64(1), 7–14. https://doi.org/10.1007/BF00203625.

Deep, K., & Mebrahtu, H. (2011). Combined mutation operators of genetic algorithm for the travelling salesman problem. International Journal of Combinatorial Optimization Problems and Informatics, 2(3), 1–23. https://www.redalyc.org/pdf/2652/265219635002.pdf.

Englert, M., Röglin, H., & Vöcking, B. (2014). Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica, 68(1), 1295–1304. https://doi.org/10.1007/s00453-013-9801-4.

Fogel, D.B. (1988). An evolutionary approach to the traveling salesman problem. Biological Cybernetics, 60(2), 139–144. https://doi.org/10.1007/BF00202901.

Fogel, D.B. (1990). A parallel processing approach to a multiple travelling salesman problem using evolutionary programming. In L.H. Canter (Ed.), Proceedings of the Fourth Annual Symposium on Parallel Processing (pp. 318–326). IEEE Orange County Computer Society.

Gao, K., Huang, Y., Sadollah, A., & Wang, L. (2020). A review of energy-efficient scheduling in intelligent production systems. Complex & Intelligent Systems, 6(2), 237–249. https://doi.org/10.1007/s40747-019-00122-6.

García-Martínez, C., Cordón, O., & Herrera, F. (2007). A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP. European Journal of Operational Research, 180(1), 116–148. https://doi.org/10.1016/j.ejor.2006.03.041.

Hassanat, A.B., Alkafaween, E.A., Al-Nawaiseh, N.A., Abbadi, M.A., Alkasassbeh, M., & Alhasanat, M.B. (2016). Enhancing genetic algorithms using multi mutations: Experimental results on the travelling salesman problem. International Journal of Computer Science and Information Security, 14(7), 785–801. https://arxiv.org/ftp/arxiv/papers/1602/1602.08313.pdf.

Holland, J.H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology. The MIT Press. https://doi.org/10.7551/mitpress/1090.001.0001.

Kentli, A., Dal, V., & Alkaya, A.F. (2013). Minimizing machine changeover time in product line in an apparel industry. Textile and Apparel, 23(2), 159–167.

Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 231–247. https://doi.org/10.1016/0377-2217(92)90192-C.

Levin, A., & Yovel, U. (2014). Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees. Journal of Combinatorial Optimization, 28(4), 726–747. https://doi.org/10.1007/s10878-012-9580-x.

Malik, A. (2019). A study of genetic algorithm and crossover techniques. International Journal of Computer Science and Mobile Computing, 8(3), 335–344.

Michalewicz, Z. (2013). Genetic algorithms + data structures = evolution programs. Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-662-03315-9.

Nirmala, G., & Ramprasad, D. (2012). Innovative PMX – CX- operators for GA TO TSP. International Journal of Scientific and Research Publications, 2(10). https://www.ijsrp.org/research-paper-1012/ijsrp-p1094.pdf.

Ramstorfer, F., & Delane de Souza, M. (2022). Reduction of incompatible intermixing of different steel grades in continuous casting by optimizing the casting sequence. International Journal of Cast Metals Research, 35(1–3), 43–50. https://doi.org/10.1080/13640461.2022.2078550.

Singh, A., Yadav, A., & Rana, A. (2013). K-means with three different distance metrics. International Journal of Computer Applications, 67(10), 13–17. http://doi.org/10.5120/11430-6785.

Shi, Y., & Liu, S. (2021). Very large-scale neighborhood search for steel hot rolling scheduling problem with slab stack shuffling considerations. IEEE Access, 9, 47856–47863. https://doi.org/10.1109/ACCESS.2021.3058328.

Syswerda, G. (1991). Scheduling optimization using genetic algorithms. In L. Davis (Ed.), Handbook of Genetic Algorithms (pp. 332–349). Van Nostrand Reinhold.

Vijayaram, T.R. (2014). Metallurgy of continuous casting technology. International Journal of Manufacturing & Industrial Engineering, 1(1), 17–36.

Wan, Y., Zuo T.-J., Chen, L., Tang, W.Ch., & Chen, J. (2020). Efficiency-oriented production scheduling scheme: an ant colony system method. IEEE Access, 8, 19286–19296. https://doi.org/10.1109/ACCESS.2020.2968378.

Zhang, H., & Xu, Y. (2018). Online covering salesman problem.