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 条

[41] On-line multi-threaded scheduling [J].

Feuerstein, E ;

Mydlarz, M ;

Stougie, L .

JOURNAL OF SCHEDULING, 2003, 6 (02) :167-181

[42] Competitive on-line scheduling with level of service [J].

Chang, EC ;

Yap, C .

JOURNAL OF SCHEDULING, 2003, 6 (03) :251-267

[43] Improved on-line broadcast scheduling with deadlines [J].

Stanley P. Y. Fung ;

Feifeng Zheng ;

Wun-Tat Chan ;

Francis Y. L. Chin ;

Chung Keung Poon ;

Prudence W. H. Wong .

Journal of Scheduling, 2008, 11 :299-308

[44] On-line scheduling with monotone subsequence constraints [J].

Luo, Kelin ;

Xu, Yinfeng ;

Zhang, Huili .

THEORETICAL COMPUTER SCIENCE, 2019, 786 :13-25

[45] Semi-on-line scheduling on two parallel processors with an upper bound on the items [J].

Angelelli, E ;

Speranza, MG ;

Tuza, Z .

ALGORITHMICA, 2003, 37 (04) :243-262

[46] Semi-On-line Scheduling on Two Parallel Processors with an Upper Bound on the Items [J].

Enrico Angelelli ;

Maria Grazia Speranza ;

Zsolt Tuza .

Algorithmica , 2003, 37 :243-262

[47] On-line scheduling of equal-length intervals on parallel machines [J].

Fung, Stanley P. Y. ;

Poon, Chung Keung ;

Yung, Duncan K. W. .

INFORMATION PROCESSING LETTERS, 2012, 112 (10) :376-379

[48] A Flexible On-line Scheduling Algorithm for Batch Machine with Infinite Capacity [J].

Chung Keung Poon ;

Wenci Yu .

Annals of Operations Research, 2005, 133 :175-181

[49] A flexible on-line scheduling algorithm for batch machine with infinite capacity [J].

Poon, CK ;

Yu, WC .

ANNALS OF OPERATIONS RESEARCH, 2005, 133 (1-4) :175-181

[50] On-Line Scheduling on a Single Bounded Batch Processing Machine with Restarts [J].

Chen, Hua ;

Zhang, Yuan-ping ;

Yong, Xue-rong .

PROCEEDINGS OF THE FIRST INTERNATIONAL WORKSHOP ON EDUCATION TECHNOLOGY AND COMPUTER SCIENCE, VOL I, 2009, :868-+

← 1 2 3 4 5 →