Approximation algorithms in batch processing

被引：114

作者：

Deng, XT ^{[1
]}

Poon, CK

Zhang, YZ

机构：

[1] City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China

[2] Qufu Noram Univ, Inst Operat Res, Shandong, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2003年 / 7卷 / 03期

关键词：

scheduling; batch; release time; makespan; on-line;

D O I：

10.1023/A:1027316504440

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

A polynomial approximation scheme for minimizing makespan in a batch processing system under dynamic job arrivals is presented. A lower bound of (root5 + 1)/2 on the competitive ratio of any on-line algorithm is proved. This is matched by an on-line algorithm for the special case of unbounded machine capacity.

引用

页码：247 / 257

页数：11

共 14 条

[1] BATCHING AND SCHEDULING JOBS ON BATCH AND DISCRETE PROCESSORS [J].

AHMADI, JH ;

AHMADI, RH ;

DASU, S ;

TANG, CS .

OPERATIONS RESEARCH, 1992, 40 (04) :750-763

[2]

Bartholdi J.J., 1988, UNPUB

[3]

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

[4]

2-R

[5] MINIMIZING TOTAL COMPLETION-TIME ON A BATCH PROCESSING MACHINE WITH JOB FAMILIES [J].

CHANDRU, V ;

LEE, CY ;

UZSOY, R .

OPERATIONS RESEARCH LETTERS, 1993, 13 (02) :61-65

[6] 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

[7]

Dobson G., 1992, BATCH LOADING SCHEDU

[8] DYNAMIC BATCHING HEURISTIC FOR SIMULTANEOUS PROCESSING [J].

GLASSEY, CR ;

WENG, WW .

IEEE TRANSACTIONS ON SEMICONDUCTOR MANUFACTURING, 1991, 4 (02) :77-82

[9]

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

[10] EFFICIENT SCHEDULING ALGORITHMS FOR A SINGLE BATCH PROCESSING MACHINE [J].

IKURA, Y ;

GIMPLE, M .

OPERATIONS RESEARCH LETTERS, 1986, 5 (02) :61-65

← 1 2 →