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 条

[11] An on-line algorithm for some uniform processor scheduling
Li, RH
Shi, LJ
[J]. SIAM JOURNAL ON COMPUTING, 1998, 27 (02) : 414 - 422
[12] Online scheduling on two uniform machines to minimize the makespan
Liu, Ming
Xu, Yinfeng
Chu, Chengbin
Zheng, Feifeng
[J]. THEORETICAL COMPUTER SCIENCE, 2009, 410 (21-23) : 2099 - 2109
[13] Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines
Min, Xiao
Liu, Jing
Wang, Yuqing
[J]. INFORMATION PROCESSING LETTERS, 2011, 111 (09) : 423 - 428
[14] Online scheduling with one rearrangement at the end: Revisited
Wang, Yuxin
Benko, Attila
Chen, Xin
Dosa, Gyorgy
Guo, He
Han, Xin
Lanyi, Cecilia Sik
[J]. INFORMATION PROCESSING LETTERS, 2012, 112 (16) : 641 - 645
[15] Preemptive on-line scheduling for two uniform processors
Wen, JJ
Du, DL
[J]. OPERATIONS RESEARCH LETTERS, 1998, 23 (3-5) : 113 - 116

← 1 2 →