Article ID: | iaor20063299 |
Country: | United Kingdom |
Volume: | 32 |
Issue: | 12 |
Start Page Number: | 3273 |
End Page Number: | 3281 |
Publication Date: | Dec 2005 |
Journal: | Computers and Operations Research |
Authors: | Schaller Jeffrey |
Keywords: | programming: branch and bound |
This note considers the problem of sequencing jobs to minimize total tardiness in a two-machine flowshop. The note shows how three dominance conditions and a lower bound previously developed for this problem can be improved. The note also proposes a new dominance condition. A branch-and-bound algorithm is developed that uses the improvements and new dominance condition. The algorithm is tested on randomly generated problems and the results of the test show that the improvements and new dominance condition improves the branch-and-bound algorithm's efficiency.