Scheduling about an unrestricted common due window with arbitrary earliness/tardiness penalty rates

1997-11-01
Azizoğlu, Meral
Webster, S
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 rnd that optimal solutions can be quickly obtained for medium-sized problem instances.

Citation Formats
M. Azizoğlu and S. Webster, “Scheduling about an unrestricted common due window with arbitrary earliness/tardiness penalty rates,” IIE TRANSACTIONS, vol. 29, no. 11, pp. 1001–1006, 1997, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/47714.