Single machine scheduling with batch deliveries

The single machine batch scheduling problem is studied. The jobs in a batch are delivered to the customer together upon the completion time of the last job in the batch. The earliness of a job is defined as the difference between the delivery time of the batch to which it belongs and its completion time. The objective is to minimize the sum of the batch delivery and job earliness penalties. A relation between this problem and the parallel machine scheduling problem is identified. This enables the establishment of complexity results and algorithms for the former problem based on known results for the latter problem.