An optimal algorithm for preemptive on-line scheduling

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 m m /( m m − ( m − 1) m ) for every m ⩾ 2, which increasingly tends to e/( e − 1) ≈...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 1995-10, Vol.18 (3), p.127-131
Main Authors: Chen, Bo, van Vliet, André, Woeginger, Gerhard J.
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
On-line algorithms
Operational research and scientific management
Operational research. Management science
Preemption
Scheduling
Scheduling, sequencing
Worst-case bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 m m /( m m − ( m − 1) m ) for every m ⩾ 2, which increasingly tends to e/( e − 1) ≈ 1.58 as m → ∞. Moreover, we prove that for no m ⩾ 2 there does exist any approximation algorithm with a better worst-case guarantee.
ISSN:0167-6377
1872-7468
DOI:10.1016/0167-6377(95)00039-9