Approximation algorithms for scheduling with reservations

Florian Diedrich 1 Klaus Jansen 2 Fanny Pascual 3 Denis Trystram 4
2 Theory of Parallelism
Department of Computer Science
3 RO - Recherche Opérationnelle
LIP6 - Laboratoire d'Informatique de Paris 6
4 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : We study the problem of non-preemptively scheduling n independent sequential jobs on a system of m identical parallel machines in the presence of reservations, where m is constant. This setting is practically relevant because for various reasons, some machines may not be available during specified time intervals. The objective is to minimize the makespan C max, which is the maximum completion time. The general case of the problem is inapproximable unless P=NP ; hence, we study a suitable strongly NP -hard restriction, namely the case where at least one machine is always available. For this setting we contribute approximation schemes, complemented by inapproximability results. The approach is based on algorithms for multiple subset sum problems; our technique yields a PTAS which is best possible in the sense that an FPTAS is ruled out unless P=NP . The PTAS presented here is the first one for the problem under consideration; so far, not even for well-known special cases approximation schemes have been proposed. Furthermore we derive a low cost algorithm with a constant approximation ratio and discuss FPTASes for special cases as well as the complexity of the problem if m is part of the input.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2010, 58 (2), pp.391-404. 〈10.1007/s00453-008-9271-2〉
Liste complète des métadonnées
Contributeur : Grégory Mounié <>
Soumis le : vendredi 8 mars 2013 - 15:31:48
Dernière modification le : samedi 15 décembre 2018 - 01:45:05

Lien texte intégral




Florian Diedrich, Klaus Jansen, Fanny Pascual, Denis Trystram. Approximation algorithms for scheduling with reservations. Algorithmica, Springer Verlag, 2010, 58 (2), pp.391-404. 〈10.1007/s00453-008-9271-2〉. 〈hal-00798443〉



Consultations de la notice