Assigning sporadic tasks to unrelated machines

Abstract : We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled. Despite its importance for modern real-time systems, this problem has not been studied before. We present a polynomial-time algorithm which approximates the problem with a constant speedup factor of 8+26‾√≈12.98+26≈12.9 and show that any polynomial-time algorithm needs a speedup factor of at least 22, unless P == NP. In the case of a constant number of machines we give a polynomial-time approximation scheme. Key to these results are two new relaxations of the demand bound function, the function that yields a sufficient and necessary condition for a task system on a single machine to be feasible. In particular, we present new methods to approximate this function to obtain useful structural properties while incurring only bounded loss in the approximation quality. For the constant speedup result we employ a very general rounding procedure for linear programs (LPs) which model assignment problems with capacity-type constraints. It ensures that the cost of the rounded integral solution is no more than the cost of the optimal fractional LP solution and the capacity constraints are violated only by a bounded factor, depending on the structure of the matrix that defines the LP. In fact, our rounding scheme generalizes the well-known 2-approximation algorithm for the generalized assignment problem due to Shmoys and Tardos.
Type de document :
Article dans une revue
Mathematical Programming, Springer Verlag, 2015, 152 (1-2), pp.247-274 〈10.1007/s10107-014-0786-9〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger
Contributeur : Marie-France Sagot <>
Soumis le : mardi 4 juillet 2017 - 14:31:05
Dernière modification le : mercredi 11 avril 2018 - 01:52:31
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 00:13:57


Fichiers produits par l'(les) auteur(s)




Alberto Marchetti-Spaccamela, Cyriel Rutten, Suzanne Van Der Ster, Andreas Wiese. Assigning sporadic tasks to unrelated machines. Mathematical Programming, Springer Verlag, 2015, 152 (1-2), pp.247-274 〈10.1007/s10107-014-0786-9〉. 〈hal-01249101〉



Consultations de la notice


Téléchargements de fichiers