Scheduling single-machine problems for on-time delivery

This paper presents several heuristics for the single-machine scheduling pr oblem with the objective of minimizing the number of tardy jobs for the sin gle due-date case and the number of early/tardy (E/T) jobs for the due-date window case. Insights from the Moore/Hodgson Algorithm are used to develop a general algorithmic approach (GAA) that performs significantly better th an dispatching rules for a large class of single due-date problems. A backw ard scheduling procedure based on a modification of this approach is: devel oped and shown to also yield excellent results for a general class of E/T p roblems. Several optimal properties derived for these problems along with e xperimental results are included. (C) 2001 Elsevier Science Ltd. All rights reserved.