Parallel machine scheduling with batch delivery costs

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on m parallel machines. The jobs are delivered in batches and the delivery date of a batch is equal to the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total flow time and delivery cost. We first show that the problem is NP-complete in the ordinary sense even when m = 2, and NP-complete in the strong sense when m is arbitrary. Then we develop a dynamic programming algorithm to solve the problem. The algorithm is pseudopolynomial when m is constant and the number of batches has a fixed upper bound. Finally, we identify two polynomially solvable cases by introducing their corresponding solution methods.