Randomized on-line scheduling on three processors

被引：2
作者：
Tichy, T [1 ]
机构：
[1] AS CR, Inst Math, CZ-11567 Prague 1, Czech Republic
来源：
OPERATIONS RESEARCH LETTERS | 2004年 / 32卷 / 02期
关键词：
scheduling; makespan; competitive analysis; on-line algorithm; lower bound;
D O I：
10.1016/j.orl.2003.05.003
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We consider a randomized on-line scheduling problem where each job has to be scheduled on any of m identical processors. The objective is to minimize the expected makespan. We show that the competitive ratio of any randomized algorithm for 27 m = 3 processors must be strictly greater than 27/19. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码：152 / 158
页数：7
相关论文
共 50 条
[31]   On-line integrated production and outbound distribution scheduling to minimize the maximum delivery completion time [J].
Ng, C. T. ;
Lu, Lingfa .
JOURNAL OF SCHEDULING, 2012, 15 (03) :391-398
[32]   Randomized algorithms for on-line scheduling problems: how low can't you go? [J].
Stougie, L ;
Vestjens, APA .
OPERATIONS RESEARCH LETTERS, 2002, 30 (02) :89-96
[33]   On-line machine scheduling with batch setups [J].
Zhang, Lele ;
Wirth, Andrew .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 20 (03) :285-306
[34]   Improved on-line broadcast scheduling with deadlines [J].
Fung, Stanley P. Y. ;
Zheng, Feifeng ;
Chan, Wun-Tat ;
Chin, Francis Y. L. ;
Poon, Chung Keung ;
Wong, Prudence W. H. .
JOURNAL OF SCHEDULING, 2008, 11 (04) :299-308
[35]   On-line Multi-threaded Scheduling [J].
Esteban Feuerstein ;
Marcelo Mydlarz ;
Leen Stougie .
Journal of Scheduling, 2003, 6 :167-181
[36]   On an on-line scheduling problem for parallel jobs [J].
Naroska, E ;
Schwiegelshohn, U .
INFORMATION PROCESSING LETTERS, 2002, 81 (06) :297-304
[37]   On-line machine scheduling with batch setups [J].
Lele Zhang ;
Andrew Wirth .
Journal of Combinatorial Optimization, 2010, 20 :285-306
[38]   Competitive Analysis of On-Line Disk Scheduling [J].
Theory of Computing Systems, 1998, 31 :491-506
[39]   An optimal algorithm for preemptive on-line scheduling [J].
Chen, B ;
vanVliet, A ;
Woeginger, GJ .
OPERATIONS RESEARCH LETTERS, 1995, 18 (03) :127-131
[40]   Competitive On-Line Scheduling with Level of Service [J].
Ee-Chien Chang ;
Chee Yap .
Journal of Scheduling, 2003, 6 :251-267
12345