On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date

In this paper, the authors consider a single-machine scheduling problem where all 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. The present approach is to use a pseudo-polynomial dynamic programming algorithm to solve the problem. The authors also discuss some special cases that are solvable in polynomial time and show that for a given schedule of tardy jobs, the problem of scheduling the batch deliveries is equivalent to the dynamic lot sizing problem. They describe how the general problem is much more difficilt. Finally, the authors present the results of empriical testing of the dynamic program and a number of heuristics developed.