Minimizing total weighted completion time on identical parallel batch machines

被引：10

作者：

Li, Shuguang ^{[1
]}

Li, Guojun

Qi, Xingqin

机构：

[1] Shandong Univ, Sch Math & Syst Sci, Jinan 250100, Peoples R China

[2] Yantai Univ, Dept Math & Informat Sci, Yantai 264005, Peoples R China

[3] Chinese Acad Sci, Inst Software, Beijing 100080, Peoples R China

[4] Shandong Univ Weihai, Dept Appl Math, Weihai 264213, Peoples R China

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2006年 / 17卷 / 06期

关键词：

approximation algorithms; batch scheduling; total weighted completion time; polynomial time approximation scheme;

D O I：

10.1142/S0129054106004509

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the problem of scheduling n jobs with release dates on m identical parallel batch machines to minimize the total weighted completion time of the jobs. A batch machine with capacity B (B < n) is able to process a batch of up to B jobs simultaneously and the time needed is equal to the maximum processing time among the jobs in the batch. This model is motivated by applications in the manufacturing of integrated circuits. In this paper, we present a polynomial time approximation scheme (PTAS) for this problem.

引用

页码：1441 / 1453

页数：13

共 20 条

[1]

Afrati F., 1999, 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), P32, DOI 10.1109/SFFCS.1999.814574

[2]

Brucker P., 1998, Journal of Scheduling, V1, P31, DOI 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO

[3]

2-R

[4]

Cai M., 2002, LECT NOTES COMPUTER, V2337, P304

[5] MINIMIZING TOTAL COMPLETION-TIME ON BATCH PROCESSING MACHINES [J].

CHANDRU, V ;

LEE, CY ;

UZSOY, R .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1993, 31 (09) :2097-2121

[6]

Chekuri Chandra, 2004, HDB SCHEDULING ALGOR

[7] On-line scheduling a batch processing system to minimize total weighted job completion time [J].

Chen, B ;

Deng, XT ;

Zang, W .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2004, 8 (01) :85-95

[8] A PTAS for semiconductor burn-in scheduling [J].

Deng, XT ;

Feng, HD ;

Li, GJ ;

Shi, BY .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2005, 9 (01) :1-13

[9]

Graham R. L., 1979, Discrete Optimisation, P287

[10] APPROXIMATION SCHEMES FOR CONSTRAINED SCHEDULING PROBLEMS [J].

HALL, LA ;

SHMOYS, DB .

30TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 1989, :134-139

← 1 2 →