Article ID: | iaor20043064 |
Country: | United Kingdom |
Volume: | 31 |
Issue: | 3 |
Start Page Number: | 397 |
End Page Number: | 414 |
Publication Date: | Mar 2004 |
Journal: | Computers and Operations Research |
Authors: | Bilge mit, Kra Furkan, Kurtulan Mjde, Pekgn Pelin |
Keywords: | heuristics |
In this study, we consider the problem of scheduling a set of independent jobs with sequence dependent setups on a set of uniform parallel machines such that total tardiness is minimized. Jobs have non-identical due dates and arrival times. A tabu search (TS) approach is employed to attack this complex problem. In order to obtain a robust search mechanism, several key components of TS such as candidate list strategies, tabu classifications, tabu tenure and intensification/diversification strategies are investigated. Alternative approaches to each of these issues are developed and extensively tested on a set of problems obtained from the literature. The results obtained are considerably better than those reported previously and constitute the best solutions known for the benchmark problems as to date.