A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies

✍ Scribed by Runwei Cheng; Mitsuo Gen; Yasuhiro Tsujimura

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 224 KB
• Volume: 36
• Category: Article
• ISSN: 0360-8352
• DOI: 10.1016/s0360-8352(99)00136-9

✦ Synopsis

Job-shop scheduling problem is one of the well-known hardest combinatorial optimization problems. During the last three decades, this problem has captured the interest of a signi®cant number of researchers. A lot of literature has been published, but no ecient solution algorithm has been found yet for solving it to optimality in polynomial time. This has led to recent interest in using genetic algorithms to address the problem.

How to adapt genetic algorithms to the job-shop scheduling problems is very challenging but frustrating. Many eorts have been made in order to give an ecient implementation of genetic algorithms to the problem. During the past decade, two important issues have been extensively studied. One is how to encode a solution of the problem into a chromosome so as to ensure that a chromosome will correspond to a feasible solution. The other issue is how to enhance the performance of genetic search by incorporating traditional heuristic methods. Because the genetic algorithms are not well suited for ®ne-tuning of solutions around optima, various methods of hybridization have been suggested to compensate for this shortcoming. The purpose of the paper is to give a tutorial survey of recent works on various hybrid approaches in genetic job-shop scheduling practices.

The research on how to adapt the genetic algorithms to the job-shop scheduling problem provide very rich experiences for the constrained combinatorial optimization problems. All of the techniques developed for the problem are very useful for other scheduling problems in modern ¯exible manufacturing systems and other dicult-to-solve combinatorial optimization problems.