Zusammenfassung
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.
Nutzer