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 条

[1] Scheduling a batch processing machine with incompatible job families [J].

Azizoglu, M ;

Webster, S .

COMPUTERS & INDUSTRIAL ENGINEERING, 2001, 39 (3-4) :325-335

[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] Approximation algorithms in batch processing [J].

Deng, XT ;

Poon, CK ;

Zhang, YZ .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2003, 7 (03) :247-257

[5] On-line scheduling on a batch machine to minimize makespan with limited restarts [J].

Fu, Ruyan ;

Tian, Ji ;

Yuan, Jinjiang ;

He, Cheng .

OPERATIONS RESEARCH LETTERS, 2008, 36 (02) :255-258

[6] Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families [J].

Koh, SG ;

Koo, PH ;

Kim, DC ;

Hur, WS .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2005, 98 (01) :81-96

[7]

LAWLER EL, 1993, HDB OPERATIONS RES, V4

[8] Minimizing makespan on a single batch processing machine with dynamic job arrivals [J].

Lee, CY ;

Uzsoy, R .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1999, 37 (01) :219-236

[9] EFFICIENT ALGORITHMS FOR SCHEDULING SEMICONDUCTOR BURN-IN OPERATIONS [J].

LEE, CY ;

UZSOY, R ;

MARTINVEGA, LA .

OPERATIONS RESEARCH, 1992, 40 (04) :764-775

[10] Minimizing total weighted completion time on identical parallel batch machines [J].

Li, Shuguang ;

Li, Guojun ;

Qi, Xingqin .

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2006, 17 (06) :1441-1453

← 1 2 →