Abstract
From the computational point of view, the job shop scheduling problem (JSP) is one of the most notoriously intractable NP-hard optimization problems. This paper applies an effective hybrid genetic algorithm for the JSP. We proposed three novel features for this algorithm to solve the JSP. Firstly, a new full active schedule (FAS) procedure based on the operation-based representation is presented to construct a schedule. After a schedule is obtained, a local search heuristic is applied to improve the solution. Secondly, a new crossover operator, called the precedence operation crossover (POX), is proposed for the operation-based representation, which can preserve the meaningful characteristics of the previous generation. Thirdly, in order to reduce the disruptive effects of genetic operators, the approach of an improved generation alteration model is introduced. The proposed approaches are tested on some standard instances and compared with other approaches. The superior results validate the effectiveness of the proposed algorithm.
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
Davis L (1985) Job shop scheduling with genetic algorithms. In: Proceedings of the International Conference on Genetic Algorithms and their Applications, Hillsdale, pp 136–149
Bierwirth C (1995) A generalized permutation approach to job shop scheduling with genetic algorithms. OR Spektrum 17:87–92
Croce FD, Tadei R, Volta G (1995) A genetic algorithm for the job shop problem. Comput Oper Res 22(1):15–24
Laarhoven PV, Aarts E, Lenstra JK (1992) Job shop scheduling by simulated annealing. Oper Res 40(1):113–125
Taillard ED (1994) Parallel taboo search techniques for the job-shop scheduling problem. ORSA J Comput 6(2):108–117
Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Manag Sci 42(6):797–813
Jain AS, Meeran S (1999) Deterministic job-shop scheduling: Past, present and future. Eur J Oper Res 113:390–434
Blazewicz J, Domschke W, Pesch E (1996) The job shop scheduling problem: Conventional and new solution techniques. Eur J Oper Res 93:1–33
Leung Y, Gao Y, Xu ZB (1997) Degree of population diversity -a perspective on premature convergence in genetic algorithms and its Markov-chain analysis. IEEE Trans Neural Netw 8(5):1165–1176
Cheng R, Gen M, Tsujimura Y (1999) A tutorial survey of job shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies. Comput Ind Eng 36:343–364
Pinedo M (2002) Scheduling Theory, Algorithms, and System, 2nd edn. Prentice Hall, Upper Saddle River, New Jersey
Gen M, Tsujimura Y, Kubota E (1995) Solving job-shop scheduling problems by genetic algorithm. In: Proceedings of the 1995 IEEE International Conference on Systems, Man, and Cybernetics, Vancouver, pp 1577–1582
Shi GY, IIMA H, Sannomiya N (1996) A new encoding scheme for job shop problems by genetic algorithm. In: Proceedings of the 35th Conference on Decision and Control, Kobe, Japan, pp 4395–4400
Baker KR (1974) Introduction to sequencing and scheduling. Wisely, NewYork
Cheng R, Gen M, Tsujimura Y (1996) A tutorial survey of job-shop scheduling problems using genetic algorithms -I. representation. Comput Ind Eng 30(9):83–97
Jain AS, Rangaswamy B, Meeran S (2000) New and “stronger” job-shop neighborhoods: A focus on the method of Nowicki and Smutnicki (1996). Journal of Heuristics 6:457–480
Gonçalves JF and et al (2002) A hybrid genetic algorithm for the job sShop scheduling problem. AT&T Labs Research Technical Report, doi:optimization-online.org/DB_FILE/2002/09/538.pdf
Kobayashi S, Ono I, Yamamura M (1995) An efficient genetic algorithm for job shop scheduling problems. In: Proceedings of the 6th International Conference on Genetic Algorithms, pp 506–511
Ono I, Kobayashi S (1998) A genetic algorithm taking account of characteristics preservation for job shop scheduling problems. In: Proceedings of the 5th Conference on Intelligent Autonomous Systems, pp 711–718
Aiex RM, Binato S, Resende MGC (2003) Parallel GRASP with path-relinking for job shop scheduling. Parallel Comput 29:393–430
Pezzella F, Merelli E (2000) A tabu search method guided by shifting bottleneck for the job shop scheduling problem. Eur J Oper Res 120:297–310
Balas E, Vazacopoulos A (1998) Guided local search with shifting bottleneck for job-shop scheduling. Manag Sci 44(2):262–275
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhang, C., Rao, Y. & Li, P. An effective hybrid genetic algorithm for the job shop scheduling problem. Int J Adv Manuf Technol 39, 965–974 (2008). https://doi.org/10.1007/s00170-007-1354-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-007-1354-8