Abstract
To solve the job-shop scheduling problem more effectively, a method based on a novel scheduling algorithm named immune genetic algorithm (IGA) was proposed. In this study, the framework of IGA was presented via combining the immune theory and the genetic algorithm. The encoding scheme based on processes and the adaptive probabilities of crossover and mutation were adopted, while a modified precedence operation crossover was also proposed to improve the performance of the crossover operator. On the other hand, the “shortest processing time” principle was selected to be the vaccine of IGA and the design method of the immune operator was given at the same time. Finally, the performance of IGA for solving JSP was validated by applying the IGA to Muth and Thompson’s benchmark problems.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Garey MR, Johnson DS, Sethi R (1976) The complexity of flow-shop and job-shop scheduling. Math Oper Res 1(2):117–129
Jain AS, Meeran S (1999) Deterministic job-shop scheduling: past, present and future. Eur J Res 113(2):390–434
Lenstra JK, Rinnooy Kan AHG, Brucker P (1997) Complexity of machine scheduling problem. Ann Discr Math 1:343–362
Wang S-F, Zou Y-R (2003) Techniques for the job shop scheduling problem: a survey. Syst Eng Theor Pract 23(1):49–55
Ponnambalam SG, Aravindan P, Rajesh SV (2000) A tabu search algorithm for job shop scheduling. Int J Adv Manuf Technol 16:765–771
Deng Z, Huang W, Zhou L (2003) Fast taboo search algorithm for solving job shop scheduling problem. J Huazhong Univ of Sci & Tech (Nature Science Edition) 31(11):1–3
Qi H-Y, Huang M, Li R (2005) A fast taboo search algorithm for solving job shop problem. J DaLian Railway Institute 26(3):46–48
Suresh RK, Mohanasundaram KM (2005) Pareto archived simulated annealing for job shop scheduling with multiple objectives. Int J Adv Manuf Technol 29(1–2):184–196
Wu D-W, Lu T-D, Liu X-B, Meng Y-S (2005) Parallel simulated annealing algorithm for solving job-shop scheduling problem. Comput Integr Manuf Syst 11(6):847–850
Wang C-Q, Cao Y-F, Dai G-Z (2004) Bi-directional convergence ACO for job-shop scheduling. Comput Integr Manuf Syst 10(7):820–824
Zhou P, Li X-P, Zhang H-F (2004) An ant colony algorithm for job shop scheduling problem. Proceedings of the 5th world congress on intelligent control and automation, Hangzhou, People’s Republic of China, 15–19 June 2004, pp 2899–2903
Jiao L, Wang L (2000) A novel genetic algorithm based on immunity. IEEE Trans Syst Man Cybern 30(5):552–561
Wang J, Ma K, Feng T (2005) The application of adaptive immune genetics algorithms on hybrid-process job-shop schedule. Journal of Xi, University of Engineering Science and Technology 19(1):79–81
Muth JF, Thompson L (1963) Industrial scheduling. Prentice-Hall, Englewood Cliffs, NJ
Wang L, Jiao L (1998) The immune genetic algorithm and its convergence. Proceedings of the fourth international conference on signal processing, Beijing, China, pp 1347–1350
Wang L (2003) Job-shop scheduling and genetic algorithm. Tsinghua University Press, Beijing
Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, New York
Srinivas M, Patnaik LM (1994) Adaptive probabilities of crossover and mutation in genetic algorithm. IEEE Trans Syst Man Cybern 24(4):656–667
Guoyong S, Hitoshi II MA, Nobuo S (1996) A new encoding scheme for job shop problems by genetic algorithm. Proceedings of the 35th conference on decision and control, Kobe, Japan, pp 4395–4400
Chen X, Kong Q, Wu Q (2002) Hybrid algorithm for job-shop scheduling problem. Proceeding of the 4th congress on intelligent control and automation. East China University of S&T Press, Shanghai, pp 1739–1743
Zhang C-Y, Rao Y-Q, Li P-G, Liu X-J (2004) An improved genetic algorithm for job-shop scheduling. Comput Integr Manuf Syst 10(8):966–970
Yun Q-X (2000) Evolution algorithm. Metallurgical Industry Press, Beijing
Tsujimura Y, Mafune Y, Gen M (2001) Effects of symbiotic evolution in genetic algorithms for job-shop scheduling. In: Proceedings of the IEEE 34th international conference on system sciences, Hawaii, pp 1–7
Wang L, Zheng DZ (2001) An effective hybrid optimization strategy for job-shop scheduling problems. Comput Oper Res 28:585–596
Wang L, Zheng DZ (2002) A modified genetic algorithm for job shop scheduling. Int J Adv Manuf Technol 20:72–76
Liu T-K, Tsai J-T, Chou J-H (2006) Improved genetic algorithm for the job-shop scheduling problem. Int J Adv Manuf Technol 27(9–10):1021–1029
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Xu, Xd., Li, Cx. Research on immune genetic algorithm for solving the job-shop scheduling problem. Int J Adv Manuf Technol 34, 783–789 (2007). https://doi.org/10.1007/s00170-006-0652-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-006-0652-x