The Effect of Crossover and Mutation Operators on Genetic Algorithm for Job Shop Scheduling Problem

Abstract:

Job Shop Scheduling Problem (JSSP) is a famous NP-hard problem in scheduling field. The concentration of JSSP is to find a feasible scheduling plan to figure out the earliest completion time under machine and processing sequence constraints. At present, genetic algorithm has been widely adopted in varies of operation research problems including JSSP, and good performance have been achieved. However, few work have stress the selection of varies operators when implemented for JSSP. Using benchmark problems, this paper compares the effect of crossover and mutation operators on genetic algorithm for JSSP.

• Periodical: Advanced Materials Research (Volumes 542-543)
• Pages: 1251-1259
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.542-543.1251
• Online since: June 2012
• Authors: Long Xu, Wen Bin Hu
• Keywords: Crossover Operator, Genetic Algorithm (GA), JSSP, Mutation Operator

References

[1] Byung Joo Park, Hyung Rim Choi, Hyun Soo Kim, A hybrid genetic algorithm for the job shop scheduling problems, Computers & Industrial Engineering, Vol. 45 (2003), pp.597-613

DOI: 10.1016/s0360-8352(03)00077-9

[2] Chao Yong Zhang, PeiGen Li, YunQing Rao, ZaiLin Guan, A very fast TS/SA algorithm for the job shop scheduling problem, Computers & Operations Research, Vol.35 (2008), pp.282-294

DOI: 10.1016/j.cor.2006.02.024

[3] Tsung-Lieh Lin et al., An efficient job-shop scheduling algorithm based on particle swarm optimization, Expert Systems with Applications, Vol.37 (2010), pp.2629-2636

DOI: 10.1016/j.eswa.2009.08.015

[4] J. Heinonen et al., Hybrid ant colony optimization and visibility studies applied to a job-shop scheduling problem, Applied Mathematics and Computation, Vol.187 (2007), p.989–998

DOI: 10.1016/j.amc.2006.09.023

[5] Holland, J. H. Adaption in natural and artificial systems. Ann Arbor: The University of Michigan Press, (1975)

[6] Davis L. Job shop scheduling with genetic algorithms. Proceedings of the first International Conference on Genetic Algorithms (1985), pp.136-140

[7] Leila Asadzadeh, Kamran Zamanifar, An agent-based parallel approach for the job shop scheduling problem with genetic algorithms, Mathematical and Computer Modelling, Vol.52 (2010), pp.1957-1965

DOI: 10.1016/j.mcm.2010.04.019

[8] Ren Qing-dao-er-ji, Yuping Wang, A new hybrid genetic algorithm for job shop scheduling problem, Computers & Operations Research, Vol.39 (2012), pp.2291-2299

DOI: 10.1016/j.cor.2011.12.005

[9] Goncalves, J. F., Mendes, J. J. D. M., & Resende, M. G. C. A hybrid genetic algorithm for the job shop scheduling problem, European Journal of Operational Research, Vol.167 (2005), p.77–95

DOI: 10.1016/j.ejor.2004.03.012

[10] Beasley, D., Bull, D.R., Martin, R.R., An overview of genetic algorithms: Part 1, Fundamentals, University Computing, vol.15 (1993), p.58–69

[11] Runwei Cheng, A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies, Computers & Industrial Engineering, Vol.36 (1999), pp.343-364

DOI: 10.1016/s0360-8352(99)00136-9

[12] Arno Sprecher, Rainer Kolisch, Andreas Drexl, Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem, European Journal of Operational Research, Vol.80 (1995), pp.94-102

DOI: 10.1016/0377-2217(93)e0294-8

[13] Talip Kellegöz, Bilal Toklu, John Wilson, Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem, Applied Mathematics and Computation, Vol.199 (2008), pp.590-598

DOI: 10.1016/j.amc.2007.10.013

[14] Bierwirth, C., Mattfeld, D., & Kopfer, H. In H. M. Voigt (Ed.), On permutation representations for scheduling problems, Proceedings of Parallel Problem Solving from Nature IV, Berlin, Germany: Springer (1996), pp.310-318

DOI: 10.1007/3-540-61723-x_995

[15] Andreas C Nearchou, The effect of various operators on the genetic search for large scheduling problems, International Journal of Production Economics, Vol.88 (2004), pp.191-203

DOI: 10.1016/s0925-5273(03)00184-1