Article ID: | iaor20011296 |
Country: | Netherlands |
Volume: | 124 |
Issue: | 1 |
Start Page Number: | 28 |
End Page Number: | 42 |
Publication Date: | Jul 2000 |
Journal: | European Journal of Operational Research |
Authors: | Liaw Ching-Fang |
Keywords: | heuristics |
This paper examines the development and application of a hybrid genetic algorithm (HGA) to the open shop scheduling problem. The hybrid algorithm incorporates a local improvement procedure based on tabu search (TS) into a basic genetic algorithm (GA). The incorporation of the local improvement procedure enables the algorithm to perform genetic search over the subspace of local optima. The algorithm is tested on randomly generated problems, and benchmark problems from the literature. Computational results show that the HGA is able to find an optimum solution for all but a tiny fraction of the test problems. Some of the benchmark problems in the literature are solved to optimality for the first time. Moreover, the results are compared to those obtained with list scheduling heuristic, insertion heuristic (IH), simulated annealing and pure TS algorithms. The HGA significantly outperforms the other method in terms of solution quality.