Article ID: | iaor2002699 |
Country: | United States |
Volume: | 29 |
Issue: | 11 |
Start Page Number: | 1001 |
End Page Number: | 1006 |
Publication Date: | Nov 1997 |
Journal: | IIE Transactions |
Authors: | Webster S., Azizoglu M. |
We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due window to minimize total weighted earliness and tardiness cost. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. Earliness or tardiness cost is assessed when a job completes outside the due window, which may be an instant in time or a time increment defining acceptable job completion. In this paper we present properties that characterize the structure of an optimal schedule, present a lower bound, propose a two-step branch and bound algorithm, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for medium-sized problem instances.