A hybrid genetic algorithm for the open shop scheduling problem

A hybrid genetic algorithm for the open shop scheduling problem

0.00 Avg rating0 Votes
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:
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.