Scheduling and common due date assignment with earliness–tardiness penalties and batch delivery costs

We consider a single machine scheduling problem involving both the scheduling of job processing and the scheduling of job delivery. A common due date for all the jobs and a delivery date for each job need to be determined in order to minimize the sum of earliness penalties, tardiness penalties, due date penalty, and delivery costs. Finished jobs are delivered in batches. There is no capacity limitation on a batch delivery and the cost per batch delivery is fixed and independent of the number of jobs in the batch. All the jobs completed before or at the due date are delivered in one batch at the due date. We present in this paper a polynomial dynamic programming algorithm for solving this problem.