| Affiliation: | (1) Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong;(2) Department of Computer Science, Shandong University, Jinan, China;(3) Computer Science Department, University of Toronto, Toronto, Ontario, M5S 1A1, Canada;(4) Qufu Normal University, Qufu, Shandong, China;(5) Department of Computer Science, Fudan University, Shanghai, China |
| Abstract: | We consider batch processing jobs to minimize the mean completiontime. A batch processing machine can handle up to $B$ jobssimultaneously. Each job is represented by an arrival time and aprocessing time. Jobs processed in a batch have the samecompletion time, i.e., their common starting time plus theprocessing time of their longest job. For batch processing,non-preemptive scheduling is usually required and we discuss thiscase. The batch processing problem reduces to the ordinaryuniprocessor system scheduling problem if $B=1$. We focus on theother extreme case $B=+infty$. Even for this seemingly simpleextreme 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 aspecial case when there are only a constant number of job processing times.Finally, we give a polynomial time approximation scheme for the general case. |
