Article ID: | iaor20083044 |
Country: | United Kingdom |
Volume: | 58 |
Issue: | 10 |
Start Page Number: | 1375 |
End Page Number: | 1388 |
Publication Date: | Oct 2007 |
Journal: | Journal of the Operational Research Society |
Authors: | Potts C.N., Whitehead J.D. |
Keywords: | combinatorial optimization, heuristics, heuristics: local search, heuristics: tabu search |
In this paper, we study a strongly NP-hard single machine scheduling problem in which each job consists of two operations that are separated by a time delay which lies within a specified range. The objective is to minimize the makespan. Determining the feasibility and, if applicable, makespan of any proposed permutation of the operations is non-trivial, requiring a longest path algorithm with