On-line scheduling on an unbounded parallel batch machine to minimize makespan of two families of jobs

被引：20

作者：

Fu, Ruyan ^{[1
]}

Tian, Ji ^{[1
]}

Yuan, Jinjiang ^{[1
]}

机构：

[1] Zhengzhou Univ, Dept Math, Zhengzhou 450052, Henan, Peoples R China

来源：

JOURNAL OF SCHEDULING | 2009年 / 12卷 / 01期

关键词：

On-line scheduling; Batch machine; Job families; Competitive ratio; PROCESSING MACHINES; ALGORITHMS;

D O I：

10.1007/s10951-008-0084-6

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

We study the on-line scheduling on an unbounded parallel batch machine to minimize makespan of two families of jobs. In this model, jobs arrive over time and jobs from different families cannot be scheduled in a common batch. We provide a best possible on-line algorithm for the problem with competitive ratio (root 17+ 3)/4 approximate to 1.7808.

引用

页码：91 / 97

页数：7

共 19 条

[11] The single-machine parallel-batching on-line scheduling problem with family jobs to minimize makespan [J].

Nong, Qingqin ;

Yuan, Jinjiang ;

Fu, Ruyan ;

Lin, Lin ;

Tian, Ji .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2008, 111 (02) :435-440

[12] On-line scheduling algorithms for a batch machine with finite capacity [J].

Poon, CK ;

Yu, WC .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2005, 9 (02) :167-186

[13] Minimizing makespan in batch machine scheduling [J].

Poon, CK ;

Zhang, PX .

ALGORITHMICA, 2004, 39 (02) :155-174

[14] Scheduling with batching: A review [J].

Potts, CN ;

Kovalyov, MY .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 120 (02) :228-249

[15] SCHEDULING BATCH PROCESSING MACHINES WITH INCOMPATIBLE JOB FAMILIES [J].

UZSOY, R .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1995, 33 (10) :2685-2708

[16]

Yuan JJ, 2004, THEOR COMPUT SCI, V320, P199, DOI [10.1016/j.tcs.2004.01.0387, 10.1016/j.tcs.2004.01.038]

[17]

YUAN JJ, 2007, BEST ON LINE A UNPUB

[18]

Zhang GC, 2003, IIE TRANS, V35, P175, DOI [10.1080/07408170304378, 10.1080/07408170390116751]

[19]

Zhang GC, 2001, NAV RES LOG, V48, P241, DOI 10.1002/nav.5

← 1 2 →