A new algorithm for online uniform-machine scheduling to minimize the makespan

Edwin Tai Chiu Cheng; Chi To Ng; Vladimir Kotov

doi:10.1016/j.ipl.2006.02.012

A new algorithm for online uniform-machine scheduling to minimize the makespan

Edwin Tai Chiu Cheng, Chi To Ng, Vladimir Kotov

Research output: Journal article publication › Journal article › Academic research › peer-review

11 Citations (Scopus)

Abstract

We consider the online scheduling problem with m - 1, m {greater than or slanted equal to} 2, uniform machines each with a processing speed of 1, and one machine with a speed of s, 1 {less-than or slanted equal to} s {less-than or slanted equal to} 2, to minimize the makespan. The well-known list scheduling (LS) algorithm has a worst-case bound of frac(( 3 m - 1 ), ( m + 1 )) [Y. Cho, S. Sahni, Bounds for list schedules on uniform processors, SIAM J. Comput. 9 (1980) 91-103]. An algorithm with a better competitive ratio was proposed in [R. Li, L. Shi, An on-line algorithm for some uniform processor scheduling, SIAM J. Comput. 27 (1998) 414-422]. It has a worst-case bound of 2.8795 for a big m and s = 2. In this note we present a 2.45-competitive algorithm for m {greater than or slanted equal to} 4 and any s, 1 {less-than or slanted equal to} s {less-than or slanted equal to} 2.

Original language	English
Pages (from-to)	102-105
Number of pages	4
Journal	Information Processing Letters
Volume	99
Issue number	3
DOIs	https://doi.org/10.1016/j.ipl.2006.02.012
Publication status	Published - 16 Aug 2006

Keywords

Competitive ratio
Multi-machine scheduling
Online algorithms
Uniform machines

ASJC Scopus subject areas

Computational Theory and Mathematics

More information

10.1016/j.ipl.2006.02.012

http://hdl.handle.net/10397/474

Cite this

@article{b4a7bd0b724249198f3c4f964ef29f41,

title = "A new algorithm for online uniform-machine scheduling to minimize the makespan",

abstract = "We consider the online scheduling problem with m - 1, m {greater than or slanted equal to} 2, uniform machines each with a processing speed of 1, and one machine with a speed of s, 1 {less-than or slanted equal to} s {less-than or slanted equal to} 2, to minimize the makespan. The well-known list scheduling (LS) algorithm has a worst-case bound of frac(( 3 m - 1 ), ( m + 1 )) [Y. Cho, S. Sahni, Bounds for list schedules on uniform processors, SIAM J. Comput. 9 (1980) 91-103]. An algorithm with a better competitive ratio was proposed in [R. Li, L. Shi, An on-line algorithm for some uniform processor scheduling, SIAM J. Comput. 27 (1998) 414-422]. It has a worst-case bound of 2.8795 for a big m and s = 2. In this note we present a 2.45-competitive algorithm for m {greater than or slanted equal to} 4 and any s, 1 {less-than or slanted equal to} s {less-than or slanted equal to} 2.",

keywords = "Competitive ratio, Multi-machine scheduling, Online algorithms, Uniform machines",

author = "Cheng, {Edwin Tai Chiu} and Ng, {Chi To} and Vladimir Kotov",

year = "2006",

month = aug,

day = "16",

doi = "10.1016/j.ipl.2006.02.012",

language = "English",

volume = "99",

pages = "102--105",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - A new algorithm for online uniform-machine scheduling to minimize the makespan

AU - Cheng, Edwin Tai Chiu

AU - Ng, Chi To

AU - Kotov, Vladimir

PY - 2006/8/16

Y1 - 2006/8/16

N2 - We consider the online scheduling problem with m - 1, m {greater than or slanted equal to} 2, uniform machines each with a processing speed of 1, and one machine with a speed of s, 1 {less-than or slanted equal to} s {less-than or slanted equal to} 2, to minimize the makespan. The well-known list scheduling (LS) algorithm has a worst-case bound of frac(( 3 m - 1 ), ( m + 1 )) [Y. Cho, S. Sahni, Bounds for list schedules on uniform processors, SIAM J. Comput. 9 (1980) 91-103]. An algorithm with a better competitive ratio was proposed in [R. Li, L. Shi, An on-line algorithm for some uniform processor scheduling, SIAM J. Comput. 27 (1998) 414-422]. It has a worst-case bound of 2.8795 for a big m and s = 2. In this note we present a 2.45-competitive algorithm for m {greater than or slanted equal to} 4 and any s, 1 {less-than or slanted equal to} s {less-than or slanted equal to} 2.

AB - We consider the online scheduling problem with m - 1, m {greater than or slanted equal to} 2, uniform machines each with a processing speed of 1, and one machine with a speed of s, 1 {less-than or slanted equal to} s {less-than or slanted equal to} 2, to minimize the makespan. The well-known list scheduling (LS) algorithm has a worst-case bound of frac(( 3 m - 1 ), ( m + 1 )) [Y. Cho, S. Sahni, Bounds for list schedules on uniform processors, SIAM J. Comput. 9 (1980) 91-103]. An algorithm with a better competitive ratio was proposed in [R. Li, L. Shi, An on-line algorithm for some uniform processor scheduling, SIAM J. Comput. 27 (1998) 414-422]. It has a worst-case bound of 2.8795 for a big m and s = 2. In this note we present a 2.45-competitive algorithm for m {greater than or slanted equal to} 4 and any s, 1 {less-than or slanted equal to} s {less-than or slanted equal to} 2.

KW - Competitive ratio

KW - Multi-machine scheduling

KW - Online algorithms

KW - Uniform machines

UR - http://www.scopus.com/inward/record.url?scp=33646841815&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2006.02.012

DO - 10.1016/j.ipl.2006.02.012

M3 - Journal article

SN - 0020-0190

VL - 99

SP - 102

EP - 105

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

A new algorithm for online uniform-machine scheduling to minimize the makespan

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this