de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Scheduling with unexpected machine breakdowns

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons43989

Albers,  Susanne
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Schmidt,  Günter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

1998-1-021
(beliebiger Volltext), 11KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Albers, S., & Schmidt, G.(1998). Scheduling with unexpected machine breakdowns (MPI-I-1998-1-021). Saarbrücken: Max-Planck-Institut für Informatik.

We investigate an online version of the scheduling problem $P, NC|pmtn|C_{\max}$, where a set of jobs has to be scheduled on a number of identical machines so as to minimize the makespan. The job processing times are known in advance and preemption of jobs is allowed. Machines are {\it non-continuously\/} available, i.e., they can break down and recover at arbitrary time instances {\it not known in advance}. New machines may be added as well. Thus machine availabilities change online. We first show that no online algorithm can construct optimal schedules. We also show that no online algorithm can achieve a constant competitive ratio if there may be time intervals where no machine is available. Then we present an online algorithm that constructs schedules with an optimal makespan of $C_{\max}^{OPT}$ if a {\it lookahead\/} of one is given, i.e., the algorithm always knows the next point in time when the set of available machines changes. Finally we give an online algorithm without lookahead that constructs schedules with a nearly optimal makespan of $C_{\max}^{OPT} + \epsilon$, for any $\epsilon >0$, if at any time at least one machine is available. Our results demonstrate that not knowing machine availabilities in advance is of little harm.