A LINEAR COMPOUND ALGORITHM FOR UNIFORM MACHINE SCHEDULING

Authors
BURKARD RE HE Y KELLERER H
Citation
Re. Burkard et al., A LINEAR COMPOUND ALGORITHM FOR UNIFORM MACHINE SCHEDULING, Computing, 61(1), 1998, pp. 1-9
Citations number
10
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
Journal title
Computing → ACNP
ISSN journal
0010485X
Volume
61
Issue
1
Year of publication
1998
Pages
1 - 9
Database
ISI
SICI code
0010-485X(1998)61:1<1:ALCAFU>2.0.ZU;2-R
Abstract
In this paper, we consider the classical two uniform machine schedulin g problem. We present a compound algorithm which consists of three Gre edy-like subprocedures running independently. We prove that the algori thm has a worst-case bound of 7/6 and runs in linear time.