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

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 significant number of researchers. A lot of literature has been published, but no efficient 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 efforts have been made in order to give an efficient 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 fine-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 flexible manufacturing systems and other difficult-to-solve combinatorial optimization problems.