On-line scheduling to minimize average completion time revisited

Nicole Megow; Andreas S. Schulz

doi:10.1016/j.orl.2003.11.008

On-line scheduling to minimize average completion time revisited

Nicole Megow, Andreas S. Schulz

Research output: Contribution to journal › Article › peer-review

64 Scopus citations

Abstract

We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.

Original language	English
Pages (from-to)	485-490
Number of pages	6
Journal	Operations Research Letters
Volume	32
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2003.11.008
State	Published - Sep 2004
Externally published	Yes

Keywords

Approximation algorithm
Competitive analysis
On-line algorithm
Scheduling

Access to Document

10.1016/j.orl.2003.11.008

Cite this

@article{6bd7167508ec4316943ae494e7341869,

title = "On-line scheduling to minimize average completion time revisited",

abstract = "We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.",

keywords = "Approximation algorithm, Competitive analysis, On-line algorithm, Scheduling",

author = "Nicole Megow and Schulz, {Andreas S.}",

year = "2004",

month = sep,

doi = "10.1016/j.orl.2003.11.008",

language = "English",

volume = "32",

pages = "485--490",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - On-line scheduling to minimize average completion time revisited

AU - Megow, Nicole

AU - Schulz, Andreas S.

PY - 2004/9

Y1 - 2004/9

N2 - We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.

AB - We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.

KW - Approximation algorithm

KW - Competitive analysis

KW - On-line algorithm

KW - Scheduling

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

U2 - 10.1016/j.orl.2003.11.008

DO - 10.1016/j.orl.2003.11.008

M3 - Article

AN - SCOPUS:2342628519

SN - 0167-6377

VL - 32

SP - 485

EP - 490

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

On-line scheduling to minimize average completion time revisited

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this