Optimal preemptive semi-online scheduling to minimize makespan on two related machines

被引：31

作者：

Epstein, L ^{[1
]}

Favrholdt, LM

机构：

[1] Interdisciplinary Ctr, Sch Comp Sci, Herzliyya, Israel

[2] Univ So Denmark, Dept Math & Comp Sci, Odense, Denmark

来源：

OPERATIONS RESEARCH LETTERS | 2002年 / 30卷 / 04期

关键词：

semi-online; scheduling;

D O I：

10.1016/S0167-6377(02)00179-7

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study a preemptive semi-online scheduling problem. Jobs with non-increasing sizes arrive one by one to be scheduled on two uniformly related machines. We analyze the algorithms as a function of the speed ratio (q greater than or equal to 1) between the two machines. We design algorithms of optimal competitive ratio for all values of q, and show that for q > 2, idle time needs to be introduced. This is the first preemptive scheduling problem over list, where idle time is provably required. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：269 / 275

页数：7

共 17 条

[1] An optimal algorithm for preemptive on-line scheduling [J].

Chen, B ;

vanVliet, A ;

Woeginger, GJ .

OPERATIONS RESEARCH LETTERS, 1995, 18 (03) :127-131

[2] SCHEDULING INDEPENDENT TASKS ON UNIFORM PROCESSORS [J].

DOBSON, G .

SIAM JOURNAL ON COMPUTING, 1984, 13 (04) :705-716

[3] Randomized on-line scheduling on two uniform machines [J].

Epstein, L ;

Noga, J ;

Seiden, S ;

Sgall, J ;

Woeginger, G .

JOURNAL OF SCHEDULING, 2001, 4 (02) :71-92

[4] A lower bound for on-line scheduling on uniformly related machines [J].

Epstein, L ;

Sgall, J .

OPERATIONS RESEARCH LETTERS, 2000, 26 (01) :17-22

[5] Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios [J].

Epstein, L .

OPERATIONS RESEARCH LETTERS, 2001, 29 (02) :93-98

[6]

EPSTEIN L, IN PRESS P 27 INT S

[7] TIGHTER BOUNDS FOR LPT SCHEDULING ON UNIFORM PROCESSORS [J].

FRIESEN, DK .

SIAM JOURNAL ON COMPUTING, 1987, 16 (03) :554-560

[8] AN ONLINE SCHEDULING HEURISTIC WITH BETTER WORST CASE RATIO THAN GRAHAM LIST SCHEDULING [J].

GALAMBOS, G ;

WOEGINGER, GJ .

SIAM JOURNAL ON COMPUTING, 1993, 22 (02) :349-355

[9] BOUNDS ON MULTIPROCESSING TIMING ANOMALIES [J].

GRAHAM, RL .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1969, 17 (02) :416-&

[10] BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES [J].

GRAHAM, RL .

BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09) :1563-+

← 1 2 →