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.
Type de document :
Chapitre d'ouvrage
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〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00800428
Contributeur : Grégory Mounié <>
Soumis le : mercredi 13 mars 2013 - 16:22:13
Dernière modification le : jeudi 11 janvier 2018 - 06:22:01

Lien texte intégral

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

180