Minimizing Mean Completion Time in a Batch Processing System |
| |
Authors: | Email author" target="_blank">Xiaotie?
DengEmail author Haodi?Feng Pixing?Zhang Yuzhong?Zhang Hong?Zhu |
| |
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 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. |
| |
Keywords: | Mean completion time Batch processing |
本文献已被 SpringerLink 等数据库收录! |
|