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 less than or equal to U for any variable U greater than or equal to 2 or if B greater than or equal to U for any constant U greater than or equal to 2. The problem is proved to be ordinary NP-hard even if the set-up time is zero and B less than or equal to 2. For the case B less than or equal to U, a dynamic programming algorithm is presented, which is pseudopolynomial for any constant U greater than or equal to 2. Algorithms with O(n(2)) 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.