PARALLEL-MACHINE BATCHING AND SCHEDULING TO MINIMIZE TOTAL COMPLETION-TIME

We consider a scheduling problem in which n independent and simultaneo usly available jobs are to be processed on m identical parallel machin es. The jobs have to be batched as well as scheduled. The completion t ime 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. Th e problem is to batch and schedule jobs so that the total completion t ime of the jobs is minimized. We first present some properties and the n develop a dynamic programming algorithm to solve this problem. The r unning time of our algorithm is O(mn(m+1)). When job processing times are identical, we show that the problem reduces to the corresponding s ingle-machine problem, which has been well solved in the literature.