Can I read Scheduling with Unexpected Machine Breakdowns on EtoBox?
Scheduling with Unexpected Machine Breakdowns by Susanne Albers; Günter Schmidt is a Computer Science article available to read on EtoBox.
What is Scheduling with Unexpected Machine Breakdowns about?
We investigate an online version of a basic scheduling problem 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 non-continuously available, i.e., they can break down and recover at arbitrary time instances not known in advance. New machines may be added as well. Thus machine availabilities change online. We ÿrst show that no online algorithm can construct optimal schedules. We also show that no online algorithm can achieve a bounded 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 OPT max if a 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 OPT max + , for any ¿ 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.
Who reads Scheduling with Unexpected Machine Breakdowns?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Susanne Albers; Günter Schmidt
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0166-218X)
- Published
- 2001
- Language
- EN
- Field
- Computer Science (Physical Sciences)