ON SCHEDULING TO MINIMIZE EARLINESS - TARDINESS AND BATCH DELIVERY COSTS WITH A COMMON DUE-DATE

In this paper, we consider a single-machine scheduling problem where a ll jobs have a common due date. The problem is to minimize the sum of earliness and tardiness penalties and the delivery costs of the tardy jobs, where the tardy jobs are delivered in batches with a fixed cost per batch. Our approach is to use a pseudo-polynomial dynamic programm ing algorithm to solve the problem. We also discuss some special cases that are solvable in polynomial time and show that for a given schedu le of tardy jobs, the problem of scheduling the batch deliveries is eq uivalent to the dynamic lot sizing problem. We describe how the genera l problem is much more difficult. Finally, we present the results of e mpirical testing of the dynamic program and a number of heuristics dev eloped.