标题:A PTAS for minimizing total completion time of bounded batch scheduling
作者:Cai, Mao-Cheng ;Deng, Xiaotie ;Feng, Haodi ;Li, Guojun ;Liu, Guizhen
通讯作者:Cai, MC
作者机构:[Cai, Mao-Cheng ] Institute of Systems Science, Academy of Siences, Beijing, China;[Li, Guojun ;Liu, Guizhen ] School of Mathematics and System Scienc 更多
会议名称:9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002
会议日期:27 May 2002 through 29 May 2002
来源:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
出版年:2002
卷:2337 LNCS
页码:304-314
摘要:We consider a batch processing system {p i : i = 1, 2,..., n} where p i is the processing time of job i, and up to B jobs can be processed together such that the handling time of a batch is the longest processing time among jobs in the batch. The number of job types m is not fixed and all the jobs are released at the same time. Jobs are executed nonpreemptively. Our objective is to assign jobs to batches and sequence the batches so as to minimize the total completion time. The best previously known result is a 2-approximation algorithm due to D. S. Hochbaum and D. Landy [6]. In this paper, we establish the first polynomial time approximation scheme (PTAS) for the problem. © 2002 Springer-Verlag Berlin Heidelberg.
收录类别:EI;SCOPUS
Scopus被引频次:12
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-23044534094&partnerID=40&md5=af6661891fd45b44f75a398378c0c6d3
TOP