Parallel-Machine Batching and Scheduling to Minimize Total Completion Time

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on m identical parallel machines. The jobs have to be batched as well as scheduled. The completion time of a job is defined as the completion time of the batch containing it. A constant set-up time is incurred whenever a batch is formed. The problem is to batch and schedule jobs so that the total completion time of the jobs is minimized. We first present some properties and then develop a dynamic programming algorithm to solve this problem. The running time of our algorithm is O(mnm+1). When job processing times are identical, we show that the problem reduces to the corresponding single-machine problem, which has been well solved in the literature.