Article ID: | iaor2006452 |
Country: | Netherlands |
Volume: | 138 |
Issue: | 1 |
Start Page Number: | 21 |
End Page Number: | 52 |
Publication Date: | Sep 2005 |
Journal: | Annals of Operations Research |
Authors: | Artigues Christian, Lopez Pierre, Ayache Pierre-Dimitri |
Keywords: | job shop |
We consider the job-shop problem with sequence-dependent setup times. We focus on the formal definition of schedule generation schemes (SGSs) based on the semi-active, active, and non-delay schedule categories. We study dominance properties of the sets of schedules obtainable with each SGS. We show how the proposed SGSs can be used within single-pass and multi-pass priority rule based heuristics. We study several priority rules for the problem and provide a comparative computational analysis of the different SGSs on sets of instances taken from the literature. The proposed SGSs significantly improve previously best-known results on a set of hard benchmark instances.