A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem. (English) Zbl 1177.90199

Summary: A novel competitive co-evolutionary quantum genetic algorithm (CCQGA) is proposed for a stochastic job shop scheduling problem (SJSSP) with the objective to minimize the expected value of makespan. Three new strategies named as competitive hunter, cooperative surviving and the big fish eating small fish are developed in population growth process. Based on improved co-evolution idea of multi-population and concepts of quantum theory, this algorithm could not only adjust population size dynamically to increase the diversity of genes and avoid premature convergence, but also accelerate the convergence speed with Q-bit representation and quantum rotation gate. FT benchmark-based problems where the processing times are subjected to independent normal distributions are solved effectively by CCQGA. The experiment results achieved by CCQGA are compared with quantum-inspired genetic algorithm (QGA) and standard genetic algorithm (GA), which shows that CCQGA has better feasibility and effectiveness.


90B36 Stochastic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI


[1] Angeline PJ, Pollack JB. Competitive environments evolve better solutions for complex tasks. In: Proceedings of the fifth international conference on genetic algorithms, 1993. p. 264-70.
[2] Bulkan S. A genetic algorithm approach to job shop scheduling. PhD thesis, Cleveland State University, USA; 1999.
[3] Bierwirth, C., A generalized permutation approach to job shop scheduling with genetic algorithms, OR spektrum, 17, 87-92, (1995) · Zbl 0843.90056
[4] Chen, S.; Ren, C.; Wu, Q., Optimizing fuzzy neural network using gause competitive coevolution algorithm, Microprocessors, 1, 33-36, (2005)
[5] Darwin C. The origin of species by means of natural selection or the preservation of favored races in the struggle for life. The Book League of America; 1929.
[6] Ehrlich, P.R.; Raven, P.H., Butterflies and plants: a study in coevolution, Evolution, 18, 4, 586-608, (1964)
[7] Giordano, F.R.; Weir, M.D.; Fox, W.P., A first course in mathematical modeling, (1997), Brooks/Cole London, UK
[8] Gu, M.; Lu, X., Preemptive stochastic online scheduling on two uniform machines, Information processing letters, 109, 369-375, (2009) · Zbl 1191.68100
[9] Gu J, Gu X, Jiao B. A quantum genetic based scheduling algorithm for stochastic flow shop scheduling problem with random breakdown. In: Proceeding of the 17th IFAC world congress, 2008. p. 63-8.
[10] Gu J, Gu X, Jiao B. Solving stochastic earliness and tardiness parallel machine scheduling using quantum genetic algorithm. In: Proceedings of the seventh world congress on Intelligent Control and Automation, WCICA’08; 2008. p. 4148-53.
[11] Gourgand, M.; Grangeon, N.; Norre, S., A contribution to the stochastic flow shop scheduling problem, European journal of operational research, 151, 2, 415-433, (2003) · Zbl 1053.90036
[12] Gen M, Tsujimura Y, Kubota E. Solving job-shop scheduling problems by genetic algorithm. In: Proceedings of the 1995 IEEE international conference on systems, man, and cybernetics, Vancouver, 1995. p. 1577-82.
[13] Hillis, W.D., Co-evolving parasites improve simulated evolution as an optimization procedure, Physica D, 42, 228-234, (1990)
[14] Han, K.H.; Kim, J.H., Quantum-inspired evolutionary algorithm for a class of combinatorial optimization, IEEE transactions on evolutionary computation, 6, 6, 580-593, (2002)
[15] Janzen, D.H., When is it co-evolution, Evolution, 34, 611-612, (1980)
[16] Liu B, Wang L, Jin Y. Hybrid particle swarm optimization for flow shop scheduling with stochastic processing time. In: Lecture notes in computer science, vol. 3801; 2005. p. 630-7.
[17] Lei D, Xiong H. An efficient evolutionary algorithm for multi-objective stochastic job shop scheduling. In: Proceedings of the sixth international conference on machine learning and cybernetics, ICMLC, 2007. p. 867-72.
[18] Liu, B., Theory and practice of uncertain programming, (2002), Physica-Verlag Heidelberg · Zbl 1029.90084
[19] Megow N, Uetz M, Vredeveld T. Stochastic online scheduling on parallel machines. In: Lecture notes in computer science, vol. 3351; 2005. p. 167-80. · Zbl 1124.90325
[20] Megow, N.; Uetz, M.; Vredeveld, T., Models and algorithms for stochastic online scheduling, Mathematics of operations research, 31, 3, 513-525, (2006) · Zbl 1278.90182
[21] Potter MA, Jong KAD. A cooperative coevolutionary approach to function optimization. In: Proceedings of the third conference on parallel problem solving from nature, 1994. p. 249-57.
[22] Skutella, M.; Uetz, M., Stochastic machine scheduling with precedence constraints, SIAM journal on computing, 34, 4, 788-802, (2005) · Zbl 1075.68008
[23] Shi GY, IIMA H, Sannomiya N. A new encoding scheme for job shop problems by genetic algorithm. In: Proceedings of the 35th conference on decision and control, Kobe, Japan, 1996. p. 4395-400.
[24] Tavakkoli-Moghaddam, R.; Jolai, F.; Vaziri, F.; Ahmed, P.K.; Azaron, A., A hybrid method for solving stochastic job shop scheduling problems, Applied mathematics and computation, 170, 1, 185-206, (2005) · Zbl 1091.90026
[25] Wang L, Wu H, Tang F, Zheng D. A hybrid quantum-inspired genetic algorithm for flow shop scheduling. In: ICIC2006, Part II, lecture notes in computer science, vol. 3654; 2005. p. 636-44.
[26] Wu, X.; Zhou, X., Stochastic scheduling to minimize expected maximum lateness, European journal of operational research, 190, 1, 103-115, (2008) · Zbl 1146.90431
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.