A BEST POSSIBLE ONLINE ALGORITHM FOR SCHEDULING TO MINIMIZE MAXIMUM FLOW-TIME ON BOUNDED BATCH MACHINES

被引：5
作者：
Jiao, Chengwen [1 ,2 ]
Li, Wenhua [1 ]
Yuan, Jinjiang [1 ]
机构：
[1] Zhengzhou Univ, Sch Math & Stat, Zhengzhou 450001, Peoples R China
[2] Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
来源：
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH | 2014年 / 31卷 / 04期
关键词：
Scheduling; online algorithm; parallel batch; maximum flow-time; competitive ratio; SEMICONDUCTOR INDUSTRY; MODELS;
D O I：
10.1142/S0217595914500304
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We consider online scheduling of unit length jobs on m identical parallel-batch machines. Jobs arrive over time. The objective is to minimize maximum flow-time, with the flow-time of a job being the difference of its completion time and its release time. A parallel-batch machine can handle up to b jobs simultaneously as a batch. Here, the batch capacity is bounded, that is b < infinity. In this paper, we provide a best possible online algorithm for the problem with a competitive ratio of root 5+1/2 approximate to 1.618.
引用
收藏
页数：10
相关论文
共 13 条
[1]   Control of a batch-processing machine: a computational approach [J].
Avramidis, AN ;
Healy, KJ ;
Uzsoy, R .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1998, 36 (11) :3167-3181
[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]  
Lawler E., 1993, LOGISTICS PRODUCTION, DOI 10.1016/S0927-0507(05)80189-6
[5]   Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time [J].
Li, Wenhua ;
Yuan, Jinjiang .
INFORMATION PROCESSING LETTERS, 2011, 111 (18) :907-911
[6]   A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines [J].
Liu, Peihai ;
Lu, Xiwen ;
Fang, Yang .
JOURNAL OF SCHEDULING, 2012, 15 (01) :77-81
[7]   Scheduling one batch processor subject to job release dates [J].
Liu, ZH ;
Yu, WC .
DISCRETE APPLIED MATHEMATICS, 2000, 105 (1-3) :129-136
[8]   A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor [J].
Mathirajan, M. ;
Sivakumar, A. I. .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2006, 29 (9-10) :990-1001
[9]   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
[10]   Online scheduling on unbounded parallel-batch machines to minimize the makespan [J].
Tian, Ji ;
Cheng, T. C. E. ;
Ng, C. T. ;
Yuan, Jinjiang .
INFORMATION PROCESSING LETTERS, 2009, 109 (21-22) :1211-1215
12