Article ID: | iaor2002738 |
Country: | Spain |
Volume: | 5 |
Issue: | 2 |
Start Page Number: | 283 |
End Page Number: | 296 |
Publication Date: | Jul 1997 |
Journal: | TOP |
Authors: | Vigo Daniele, Sicilia Joaqun, Alcaide David |
Keywords: | tabu search |
In this paper we consider the minimum makespan Open Shop problem without preemption. It is well-known that the case with only two machines can be optimally solved in linear time, whereas the problem with an arbitrary number of machines is NP-hard in the strong sense. We propose a tabu search algorithm for the solution of the problem which uses simple list scheduling algorithms to build the starting solutions. The algorithm is extensively tested on randomly generated instances.