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([mn.sup.m + 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.
1. Introduction There are n independent non-preemptive jobs j [element of] N = {1, ..., n} to be processed on m identical parallel machines. Each job j has a processing [...]