Minimizing mean completion time in a batch processing system

We consider batch processing jobs to minimize the mean completion time. A batch processing machine can handle up to B jobs simultaneously. Each job is represented by an arrival time and a processing time. Jobs processed in a batch have the same completion time, i.e., their common starting time plus the processing time of their longest job. For batch processing, non-preemptive scheduling is usually required and we discuss this case. The batch processing problem reduces to the ordinary uniprocessor system scheduling problem if B=1. We focus on the other extreme case B=+\infty. Even for this seemingly simple extreme case, we are able to show that the problem is NP-hard for the weighted version. In addition, we establish a polynomial time algorithm for a special case when there are only a constant number of job processing times. Finally, we give a polynomial time approximation scheme for the general case. © 2003 Springer-Verlag New York Inc.