A survey on approximation algorithms for scheduling with machine unavailability

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 : Wednesday, March 13, 2019 - 3:02:07 PM

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