|
|||||
|
|
Some dominance properties for single-machine tardiness problems with sequence-dependent setup |
|
| Authors: | Xiaochuan Luo Chengbin Chu Chengen Wang |
| Affiliation: | 1. Key Laboratory of Process Industry Automation , Ministry of Education , Shenyang 110004, China;2. LOSI , Universite de Technologie de Troyes , Troyes Cedex 10010, France luoxch@mail.neu.edu.cn;4. LOSI , Universite de Technologie de Troyes , Troyes Cedex 10010, France;5. Key Laboratory of Process Industry Automation , Ministry of Education , Shenyang 110004, China |
| Abstract: | Some dominance properties are proposed for the NP-hard problems of scheduling N jobs on a single machine with due dates, and sequence-dependent setup times. The algorithms based on Ragatz's branch and bound scheme with the dominance properties are developed to minimize the maximum tardiness or the total tardiness. Computational experiments demonstrate the effectiveness of the dominance rules. |
| Keywords: | Dominance property Sequence-dependent setup Due date Single machine Branch and bound |