×

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.

MSC:

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

References:

[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, (Lecture Notes in Comput. Sci., vol. 4513 (2007), Springer-Verlag), 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, (Lecture Notes in Comput. Sci., vol. 3351 (2005), Springer-Verlag), 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, (Lecture Notes in Comput. Sci., vol. 3801 (2005)), 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; 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, (Proceedings of the Fifth International Conference on Genetic Algorithms (1993), Morgan Kaufmann), 155-162
[13] G.P. Erick, Designing Scalable Multi-Population Parallel Genetic Algorithm, IlliGAL Report No. 98009, Illinois Genetic Algorithm Laboratory, 1998; 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, (Proceedings of the Fifth International Conference on Genetic Algorithms (1993), Morgan Kaufmann), 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, (ICIC 2006, Part II. ICIC 2006, Part II, Lecture Notes in Comput. Sci., vol. 3645 (2005), Springer-Verlag: Springer-Verlag Berlin), 636-644
[17] Han, K. H.; Park, K. H.; Lee, C. H.; Kin, J. H., Parallel quantum-inspired genetic algorithm for combinatorial optimization problem, (Proceedings of the 2001 IEEE Congress on Evolutionary Computation, Seoul, Korea (May 2001)), 1422-1429
[18] Gu, J.; Gu, X. S.; Jiao, B., Solving stochastic earliness and tardiness parallel machine scheduling using quantum genetic algorithm, (Proceedings of the 7th World Congress on Intelligent Control and Automation, WCICA’08 (2008)), 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, (Proceeding of the 17th IFAC World Congress (2008)), 63-68
[20] Liu, B. D., Theory and Practice of Uncertain Programming (2002), Physica-Verlag: Physica-Verlag Heidelberg · Zbl 1029.90084
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.