A tabu search algorithm for the Open Problem

Autores: David Alcaide López de Pablo , Joaquín Sicilia Rodríguez , Daniele Vigo
Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 5, Nº. 2, 1997, págs. 283-296
Idioma: inglés
DOI: 10.1007/bf02568554
Enlaces
- Texto completo
Resumen
- 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.