Article ID: | iaor19992343 |
Country: | United Kingdom |
Volume: | 49 |
Issue: | 10 |
Start Page Number: | 1101 |
End Page Number: | 1106 |
Publication Date: | Oct 1998 |
Journal: | Journal of the Operational Research Society |
Authors: | Tadei R., Croce F. Della, Baracco P., Grosso A. |
Keywords: | programming: branch and bound |
This paper deals with the single machine total tardiness problem. From Emmons' basic dominance conditions a new partition theorem is derived which generalises Lawler's decomposition rule and leads to a new double decomposition procedure. This procedure is embedded into a branch and bound method which applies a new lower bound based on due dates reassignment. The branch and bound method is tested on problems with size up to 150 jobs.