Skip to Main content Skip to Navigation
Book sections

A survey on approximation algorithms for scheduling with machine unavailability

Florian Diedrich 1 Klaus Jansen 2 Ulrich M. Schwarz Denis Trystram 3
2 Theory of Parallelism
Department of Computer Science
3 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble [2007-2015]
Abstract : In this chapter we present recent contributions in the field of sequential job scheduling on network machines which work in parallel; these are subject to temporary unavailability. This unavailability can be either unforeseeable (online models) or known a priori (offline models). For the online models we are mainly interested in preemptive schedules for problem formulations where the machine unavailability is given by a probabilistic model; objectives of interest here are the sum of completion times and the makespan. Here, the non-preemptive case is essentially intractable. For the offline models we are interested in non-preemptive schedules where we consider the makespan objective; we present approximation algorithms which are complemented by suitable inapproximability results. Here, the preemptive model is polynomial-time solvable for large classes of settings.
Complete list of metadatas
Contributor : Grégory Mounié <>
Submitted on : Wednesday, March 13, 2013 - 4:22:13 PM
Last modification on : Thursday, July 9, 2020 - 9:44:31 AM

Links full text




Florian Diedrich, Klaus Jansen, Ulrich M. Schwarz, Denis Trystram. A survey on approximation algorithms for scheduling with machine unavailability. Lerner, J. and Wagner, D. and Zweig, K. Algorithmics, 2009, 5515, Springer, pp.50-64, 2009, LNCS, ⟨10.1007/978-3-642-02094-0_3⟩. ⟨hal-00800428⟩



Record views