Article ID: | iaor20042595 |
Country: | Netherlands |
Volume: | 145 |
Issue: | 1 |
Start Page Number: | 45 |
End Page Number: | 56 |
Publication Date: | Feb 2003 |
Journal: | European Journal of Operational Research |
Authors: | Bulfin R.L., M'Hallah Rym |
Keywords: | optimization, programming: branch and bound |
In this paper, we describe an exact algorithm to solve the single machine weighted number of tardy jobs scheduling problem. The algorithm uses branch-and-bound with the bounds obtained from a surrogate knapsack. Extensive computational experiments are carried out. These experiments validated previous work on what constitutes a difficult instance and show that even difficult instances with 2500 jobs can be solved optimally in a reasonable amount of time.