首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号