General parametric scheme for the online uniform machine scheduling problem with two different speeds

被引：5

作者：

Dolgui, Alexandre ^{[1
]}

Kotov, Vladimir ^{[3
,4
]}

Nekrashevich, Aliaksandr ^{[3
]}

Quilliot, Alain ^{[2
]}

机构：

[1] IMT Atlantique, LS2N, UMR CNRS 6004, 4 Rue Alfred Kastler,BP 20722, F-44307 Nantes 3, France

[2] ISIMA, LIMOS, UMR CNRS 6158, Complexe Sci Cezeaux, F-63173 Aubiere, France

[3] Belarusian State Univ, FPMI DMA Dept, 4 Nezavisimosti Ave, Minsk 220030, BELARUS

[4] Vilnius Gediminas Tech Univ, Fac Fundamental Sci, Dept Informat Technol, Sauletekio Al 11, LT-10223 Vilnius, Lithuania

来源：

INFORMATION PROCESSING LETTERS | 2018年 / 134卷

关键词：

Approximation algorithms; Online algorithms; Scheduling; ALGORITHM; REARRANGEMENT;

D O I：

10.1016/j.ipl.2018.01.009

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we consider the online uniform machine scheduling problem on m processors when speed s(i) = 1 for i = k + 1, m and s(i) = s, s > 1, for i = 1, .....k. The objective is to minimize makespan. We propose a parametric scheme with the worst-case performance 2.618 when 1 < s <= 2, and with the asymptotic worst-case performance 1/2(1 + s + root 5-2s-s(2)) for all s > 1 when the ratio m/k tends to infinity. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：18 / 23

页数：6

共 15 条

[1] Semi-online scheduling on two uniform processors
Angelelli, Enrico
Speranza, Maria Grazia
Tuza, Zsolt
[J]. THEORETICAL COMPUTER SCIENCE, 2008, 393 (1-3) : 211 - 219
[2] Online scheduling with reassignment on two uniform machines
Cao, Qian
Liu, Zhaohui
[J]. THEORETICAL COMPUTER SCIENCE, 2010, 411 (31-33) : 2890 - 2898
[3] A new algorithm for online uniform-machine scheduling to minimize the makespan
Cheng, T. C. E.
Ng, C. T.
Kotov, Vladimir
[J]. INFORMATION PROCESSING LETTERS, 2006, 99 (03) : 102 - 105
[4] BOUNDS FOR LIST SCHEDULES ON UNIFORM PROCESSORS
CHO, Y
SAHNI, S
[J]. SIAM JOURNAL ON COMPUTING, 1980, 9 (01) : 91 - 103
[5] Dolgui A., 2015, B ACAD STIINTE REPUB, V79, P102
[6] Online scheduling with rearrangement on two related machines
Dosa, Gyoergy
Wang, Yuxin
Han, Xin
Guo, He
[J]. THEORETICAL COMPUTER SCIENCE, 2011, 412 (8-10) : 642 - 653
[7] Graham R L., 1969, SIAM J APPL MATH, V17, P263
[8] An efficient algorithm for semi-online multiprocessor scheduling with given total processing time
Kellerer, Hans
Kotov, Vladimir
Gabay, Michael
[J]. JOURNAL OF SCHEDULING, 2015, 18 (06) : 623 - 630
[9] An efficient algorithm for bin stretching
Kellerer, Hans
Kotov, Vladimir
[J]. OPERATIONS RESEARCH LETTERS, 2013, 41 (04) : 343 - 346
[10] Online scheduling on two uniform machines subject to eligibility constraints
Lee, Kangbok
Leung, Joseph Y. -T.
Pinedoa, Michael L.
[J]. THEORETICAL COMPUTER SCIENCE, 2009, 410 (38-40) : 3975 - 3981

← 1 2 →