On-line scheduling of equal-length intervals on parallel machines

Stanley P.Y. Fung; Chung Keung Poon; Duncan K.W. Yung

doi:10.1016/j.ipl.2012.01.015

On-line scheduling of equal-length intervals on parallel machines

Stanley P.Y. Fung
, Chung Keung Poon
, Duncan K.W. Yung

City University of Hong Kong

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

11 Citations (Scopus)

Abstract

We consider the on-line preemptive scheduling of weighted equal-length intervals on multiple machines to maximize the total weight of completed intervals. We design an algorithm that is 2-competitive when the number of machines m is even; and (2+2/2m-1)-competitive when m is an odd number at least 3. For example, when m=3, it is 2.4-competitive. As m increases, the competitive ratio approaches 2. © 2012 Elsevier B.V. © 2012 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	376-379
Journal	Information Processing Letters
Volume	112
Issue number	10
DOIs	https://doi.org/10.1016/j.ipl.2012.01.015
Publication status	Published - 31 May 2012

Research Keywords

Competitive analysis
Interval scheduling
On-line algorithm
Parallel scheduling

Access Output

10.1016/j.ipl.2012.01.015

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{d2bb0bc8138f4fd8bb03bb06b3cd5f04,

title = "On-line scheduling of equal-length intervals on parallel machines",

abstract = "We consider the on-line preemptive scheduling of weighted equal-length intervals on multiple machines to maximize the total weight of completed intervals. We design an algorithm that is 2-competitive when the number of machines m is even; and (2+2/2m-1)-competitive when m is an odd number at least 3. For example, when m=3, it is 2.4-competitive. As m increases, the competitive ratio approaches 2. {\textcopyright} 2012 Elsevier B.V. {\textcopyright} 2012 Elsevier B.V. All rights reserved.",

keywords = "Competitive analysis, Interval scheduling, On-line algorithm, Parallel scheduling",

author = "Fung, \{Stanley P.Y.\} and Poon, \{Chung Keung\} and Yung, \{Duncan K.W.\}",

year = "2012",

month = may,

day = "31",

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

language = "English",

volume = "112",

pages = "376--379",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "10",

}

TY - JOUR

T1 - On-line scheduling of equal-length intervals on parallel machines

AU - Fung, Stanley P.Y.

AU - Poon, Chung Keung

AU - Yung, Duncan K.W.

PY - 2012/5/31

Y1 - 2012/5/31

N2 - We consider the on-line preemptive scheduling of weighted equal-length intervals on multiple machines to maximize the total weight of completed intervals. We design an algorithm that is 2-competitive when the number of machines m is even; and (2+2/2m-1)-competitive when m is an odd number at least 3. For example, when m=3, it is 2.4-competitive. As m increases, the competitive ratio approaches 2. © 2012 Elsevier B.V. © 2012 Elsevier B.V. All rights reserved.

AB - We consider the on-line preemptive scheduling of weighted equal-length intervals on multiple machines to maximize the total weight of completed intervals. We design an algorithm that is 2-competitive when the number of machines m is even; and (2+2/2m-1)-competitive when m is an odd number at least 3. For example, when m=3, it is 2.4-competitive. As m increases, the competitive ratio approaches 2. © 2012 Elsevier B.V. © 2012 Elsevier B.V. All rights reserved.

KW - Competitive analysis

KW - Interval scheduling

KW - On-line algorithm

KW - Parallel scheduling

UR - https://www.scopus.com/pages/publications/84857382019

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84857382019&origin=recordpage

U2 - 10.1016/j.ipl.2012.01.015

DO - 10.1016/j.ipl.2012.01.015

M3 - RGC 21 - Publication in refereed journal

SN - 0020-0190

VL - 112

SP - 376

EP - 379

JO - Information Processing Letters

JF - Information Processing Letters

IS - 10

ER -

On-line scheduling of equal-length intervals on parallel machines

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this