A novel parallel quantum genetic algorithm for stochastic job shop scheduling. (English) Zbl 1174.90006

The paper investigates the so-called job-shop-scheduling problem, i.e., there is a certain number of jobs that have to be completed on a given number of machines according to a given sequence of operations. The processing times of the jobs on the machines are assumed to be normally distributed. The objective is to find a strategy that minimizes the sum of the expected completion times for the jobs. To solve this problem a parallel quantum genetic algorithm is proposed. The performance of the algorithm is tested by means of three “standard benchmark problems” using simulations.


90B36 Stochastic scheduling theory in operations research
68W10 Parallel algorithms in computer science
Full Text: DOI


[1] Gu, X.S., A survey of production scheduling under uncertainty, J. east China univ. sci. technol., 26, 5, 441-446, (2000)
[2] Bertsekas, D.P.; Castanon, D.A., Rollout algorithms for stochastic scheduling problems, J. heuristics, 5, 1, 89-108, (1999) · Zbl 0997.90037
[3] Skutella, M.; Uetz, M., Stochastic machine scheduling with precedence constraints, SIAM J. comput., 34, 4, 788-802, (2005) · Zbl 1075.68008
[4] Shmoys, D.B.; Sozio, M., Approximation algorithms for 2-stage stochastic scheduling problems, (), 145-157 · Zbl 1136.90358
[5] Gourgand, M.; Grangeon, N.; Norre, S., A contribution to the stochastic flow shop scheduling problem, European J. oper. res., 151, 2, 415-433, (2003) · Zbl 1053.90036
[6] Megow, N.; Uetz, M.; Vredeveld, T., Models and algorithms for stochastic online scheduling, Math. oper. res., 31, 3, 513-525, (2006) · Zbl 1278.90182
[7] Megow, N.; Uetz, M.; Vredeveld, T., Stochastic online scheduling on parallel machines, (), 167-180 · Zbl 1124.90325
[8] Wu, X.; Zhou, X., Stochastic scheduling to minimize expected maximum lateness, European J. oper. res., 190, 1, 103-115, (2008) · Zbl 1146.90431
[9] Liu, B.; Wang, L.; Jin, Y., Hybrid particle swarm optimization for flow shop scheduling with stochastic processing time, (), 630-637
[10] Tavakkoli-Moghaddam, R.; Jolai, F.; Vaziri, F.; Ahmed, P.K.; Azaron, A., A hybrid method for solving stochastic job shop scheduling problems, Appl. math. comput., 170, 1, 185-206, (2005) · Zbl 1091.90026
[11] D.M. Lei, H. Xiong, 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, pp. 867-872
[12] Baluja, S., Structure and performance of fine-grain parallelism in genetic search, (), 155-162
[13] G.P. Erick, Designing Scalable Multi-Population Parallel Genetic Algorithm, IlliGAL Report No. 98009, Illinois Genetic Algorithm Laboratory, 1998
[14] Gordon, V.S.; Whitley, D., Serial and parallel genetic algorithms as function optimizers, (), 177-183
[15] Han, K.K.; Kim, J.H., Quantum-inspired evolutionary algorithm for a class of combinatorial optimization, IEEE trans. evol. comput., 6, 6, 580-593, (2002)
[16] Wang, L.; Wu, H.; Tang, F.; Zheng, D., A hybrid quantum-inspired genetic algorithm for flow shop scheduling, (), 636-644
[17] Han, K.H.; Park, K.H.; Lee, C.H.; Kin, J.H., Parallel quantum-inspired genetic algorithm for combinatorial optimization problem, (), 1422-1429
[18] Gu, J.; Gu, X.S.; Jiao, B., Solving stochastic earliness and tardiness parallel machine scheduling using quantum genetic algorithm, (), 4148-4153
[19] Gu, J.; Gu, X.S.; Jiao, B., A quantum genetic based scheduling algorithm for stochastic flow shop scheduling problem with random breakdown, (), 63-68
[20] Liu, B.D., Theory and practice of uncertain programming, (2002), Physica-Verlag Heidelberg
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.