Comparative evaluation of genetic algorithms for job-shop scheduling

• Published in: Production planning & control 2001-09, Vol.12 (6), p.560-574
• Main Authors: Ponnambalam, S. G., Aravindan, P., Rao, P. Sreenivasa
• Format: Article
• Language: English
• Subjects: Genetic Algorithms; Heuristics; Job-SHOP Scheduling
• ISSN: 0953-7287; 1366-5871
• DOI: 10.1080/095372801750397680

Many optimization problems from the industrial engineering world, in particular the manufacturing systems, are very complex in nature and quite hard to solve by conventional optimization techniques. There has been increasing interest in imitating living beings to solve such kinds of hard optimization problems. Simulating the natural evolutionary process of human beings results in stochastic optimization tech niques called evolutionary algorithms, which can often outperform conventional optimization methods when applied to difficult real-world problems. There are currently three main avenues of this research: genetic algorithms (GAs), evolutionary programming (EP) and evolution strategies (ESs). Among them, genetic algorithms are perhaps the most widely known types of evolutionary algorithms today. During the past years, several GAs for the job-shop scheduling problems have been proposed, each with different chromosome representation. In this paper, the different GAs are collected from the literature and an attempt has been made to evaluate them. The benchmark problems available in open literature are used for evaluation and the performance measure considered is makespan. The algorithms are coded in C+ +.