Article ID: | iaor2008173 |
Country: | United Kingdom |
Volume: | 6 |
Issue: | 6 |
Start Page Number: | 533 |
End Page Number: | 549 |
Publication Date: | Nov 2003 |
Journal: | Journal of Scheduling |
Authors: | Sourd Francis, Kedad-Sidhoum Safia |
Keywords: | programming: transportation |
We address the one-machine problem in which the jobs have distinct due dates, earliness costs, and tardiness costs. In order to determine the minimal cost of such a problem, a new lower bound is proposed. It is based on the decomposition of each job in unary operations that are then assigned to the time slots, which gives a preemptive schedule. Assignment costs are defined so that the minimum assignment cost is a valid lower bound. A branch-and-bound algorithm based on this lower bound and on some new dominance rules is experimentally tested.