An optimal algorithm for preemptive on-line scheduling

B. Chen; A. Vliet, van; G.J. Woeginger

doi:10.1016/0167-6377(95)00039-9

An optimal algorithm for preemptive on-line scheduling

B. Chen, A. Vliet, van, G.J. Woeginger

Research School EIDMA

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

58 Citations (Scopus)

Abstract

We investigate the problem of on-line scheduling jobs on m identical parallel machines where preemption is allowed. The goal is to minimize the makespan. We derive an approximation algorithm with worst-case guarantee mm/(mm - (m - 1)m) for every m 2, which increasingly tends to e/(e - 1) ˜ 1.58 as m ¿ 8. Moreover, we prove that for no m 2 there does exist any approximation algorithm with a better worst-case guarantee.

Original language	English
Pages (from-to)	127-131
Number of pages	5
Journal	Operations Research Letters
Volume	18
Issue number	3
DOIs	https://doi.org/10.1016/0167-6377(95)00039-9
Publication status	Published - 1995

Access to Document

10.1016/0167-6377(95)00039-9

Fingerprint Dive into the research topics of 'An optimal algorithm for preemptive on-line scheduling'. Together they form a unique fingerprint.

Cite this

@article{8be23343f67b4bb3b1a017be3ed36152,

title = "An optimal algorithm for preemptive on-line scheduling",

abstract = "We investigate the problem of on-line scheduling jobs on m identical parallel machines where preemption is allowed. The goal is to minimize the makespan. We derive an approximation algorithm with worst-case guarantee mm/(mm - (m - 1)m) for every m 2, which increasingly tends to e/(e - 1) ˜ 1.58 as m ¿ 8. Moreover, we prove that for no m 2 there does exist any approximation algorithm with a better worst-case guarantee.",

author = "B. Chen and {Vliet, van}, A. and G.J. Woeginger",

year = "1995",

doi = "10.1016/0167-6377(95)00039-9",

language = "English",

volume = "18",

pages = "127--131",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - An optimal algorithm for preemptive on-line scheduling

AU - Chen, B.

AU - Vliet, van, A.

AU - Woeginger, G.J.

PY - 1995

Y1 - 1995

N2 - We investigate the problem of on-line scheduling jobs on m identical parallel machines where preemption is allowed. The goal is to minimize the makespan. We derive an approximation algorithm with worst-case guarantee mm/(mm - (m - 1)m) for every m 2, which increasingly tends to e/(e - 1) ˜ 1.58 as m ¿ 8. Moreover, we prove that for no m 2 there does exist any approximation algorithm with a better worst-case guarantee.

AB - We investigate the problem of on-line scheduling jobs on m identical parallel machines where preemption is allowed. The goal is to minimize the makespan. We derive an approximation algorithm with worst-case guarantee mm/(mm - (m - 1)m) for every m 2, which increasingly tends to e/(e - 1) ˜ 1.58 as m ¿ 8. Moreover, we prove that for no m 2 there does exist any approximation algorithm with a better worst-case guarantee.

U2 - 10.1016/0167-6377(95)00039-9

DO - 10.1016/0167-6377(95)00039-9

M3 - Article

VL - 18

SP - 127

EP - 131

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 3

ER -