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 条
[21]   On-line resource management with application to routing and scheduling [J].
Leonardi, S ;
Marchetti-Spaccamela, A .
ALGORITHMICA, 1999, 24 (01) :29-49
[22]   New bounds and algorithms for on-line scheduling: two identical processors, known sum and upper bound on the tasks [J].
Angelelli, E ;
Speranza, MG ;
Tuza, Z .
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2006, 8 (01) :1-15
[23]   An Improved Randomized On-Line Algorithm for a Weighted Interval Selection Problem [J].
Hiroyuki Miyazawa ;
Thomas Erlebach .
Journal of Scheduling, 2004, 7 :293-311
[24]   An improved randomized on-line algorithm for a weighted interval selection problem [J].
Miyazawa, H ;
Erlebach, T .
JOURNAL OF SCHEDULING, 2004, 7 (04) :293-311
[25]   On the on-line maintenance scheduling problem [J].
Shamsaei, Fahimeh ;
Telha, Claudio ;
Van Vyve, Mathieu .
OPTIMIZATION LETTERS, 2018, 12 (02) :387-397
[26]   On the on-line maintenance scheduling problem [J].
Fahimeh Shamsaei ;
Claudio Telha ;
Mathieu Van Vyve .
Optimization Letters, 2018, 12 :387-397
[27]   On-line scheduling with tight deadlines [J].
Koo, CY ;
Lamb, TW ;
Ngan, TW ;
Sadakane, K ;
To, KK .
THEORETICAL COMPUTER SCIENCE, 2003, 295 (1-3) :251-261
[28]   On-line scheduling of unit time jobs with rejection: minimizing the total completion time [J].
Epstein, L ;
Noga, J ;
Woeginger, GJ .
OPERATIONS RESEARCH LETTERS, 2002, 30 (06) :415-420
[29]   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
[30]   On-Line Scheduling Algorithms for a Batch Machine with Finite Capacity [J].
Chung Keung Poon ;
Wenci Yu .
Journal of Combinatorial Optimization, 2005, 9 :167-186
12345