Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delays
verfasst von : Aleksei V. Fishkin, Klaus Jansen, Sergey V. Sevastyanov, René Sitters
Erschienen in: Algorithms – ESA 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present hardness and approximation results for the problem of scheduling
n
independent jobs on
m
identical parallel machines subject to a migration delay
d
so as to minimize the makespan. We give a sharp threshold on the value of
d
for which the complexity of the problem changes from polynomial time solvable to NP-hard. We give initial results supporting a conjecture that there always exists an optimal schedule in which at most
m
– 1 jobs migrate. Further, we give a
O
(
n
) time
O
(1+1/log
2
n
)-approximation algorithm for
m
= 2, and show that there is a polynomial time approximation scheme for arbitrary
m
.