Minimizing Mean Completion Time in a Batch Processing System

• DOI: 10.1007/s00453-003-1053-2
• Publication Date: 2004-02-20T11:57:08Z
• Authors: Xiaotie Deng; Haodi Feng; Pixing Zhang; Yuzhong Zhang; Hong Zhu
• Keywords: Batch processing; Uniprocessor system; Theory of computation; Polynomial-time approximation scheme

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.