Article ID: | iaor20114717 |
Volume: | 38 |
Issue: | 12 |
Start Page Number: | 1760 |
End Page Number: | 1765 |
Publication Date: | Dec 2011 |
Journal: | Computers and Operations Research |
Authors: | Lee Wen-Chiung, Hsu Chou-Jung, Cheng T C E, Huang Yi-Chi |
Keywords: | programming: branch and bound |
In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper, we consider a single‐machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch‐and‐bound algorithm to solve this problem. Computational experiments show that the algorithm can solve instances up to 1000 jobs in reasonable time.