max planck institut
informatik
informatik
MPI-I-98-1-021. September 1998, 15 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry
Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:
| To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |
|---|---|
| 235 KBytes | |
| Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView | |
BibTeX