Efficient methods and techniques for the open-shop scheduling problem. (c2006)

Abstract

In this paper we investigate the use of two different heuristic techniques to the openshop scheduling problem and we make a comparison between them. The open-shop scheduling problem is NP hard and due to that it's very important to find heuristic approaches that can generate better approximate solutions. This work first focuses on solving the open-shop scheduling problem using genetic algorithms. We present an interesting implementation of genetic operators that combines the use of deterministic moves and pure random moves. We then perform tuning and testing of our approach and present detailed results for each problem instance of the Taillard benchmarks. We also compare our results with those obtained in other recent research works on the subject. In the second part of our work we focus on an approach based on simulated annealing. We perform tuning and testing for our annealing approach and present detailed result comparisons for all the Taillard Benchmarks. Finally we compare both the results obtained by ga and annealing and conclude that even though all results are good, in general our annealing implementation seems to perform better than our GA implementation, especially for larger problem sizes. We also justify the reasons why we think our ga approach didn't perform as good as the annealing.