Single Machine Scheduling to Minimize Batch Delivery and Job Earliness Penalties

We study a problem in which a set of n jobs has to be batched as well as scheduled for processing on a single machine. A constant machine set-up time is required before the first job of each batch is processed. A schedule specifies the sequence of batches, where each batch comprises a sequence of jobs. The batch delivery time is defined as the completion time of the last job in a batch. The earliness of a job is defined as the difference between the delivery time of the batch to which it belongs and the job completion time. The objective is to find a number B of batches and a schedule so as to minimize the sum of the total weighted job earliness and mean batch delivery time. The problem is shown to be strongly NP-hard. It remains strongly $NP$-hard if the set-up time is zero and $B\le U$ for any variable $U\ge 2$ or if $B\ge U$ for any constant $U\ge 2$. The problem is proved to be ordinary NP-hard even if the set-up time is zero and $B\le 2$. For the case $B\le U$, a dynamic programming algorithm is presented, which is pseudopolynomial for any constant $U\ge 2$. Algorithms with O(n¹) running times are derived for the cases when all weights are equal or all processing times are equal. For the general problem, a family of heuristics is suggested. Computational experiments on the proposed heuristic algorithm are conducted. The results suggest that the heuristics are effective in generating near-optimal solutions quickly.