Throughput optimization for micro-factories subject to failures

Abstract : In this report, we study the problem of optimizing the throughput for micro-factories subject to failures. The challenge consists in mapping several tasks onto a set of machines. One originality of the approach is the failure model for such applications, in which tasks are subject to failures rather than machines. If there is exactly one task per machine in the mapping, then we prove that the optimal solution can be computed in polynomial time. However, the problem becomes NP-hard if several tasks can be assigned to the same machine. Several polynomial time heuristics are presented for the most realistic specialized setting, in which tasks of a same type can be mapped onto a same machine. Experimental results show that the best heuristics obtain a good throughput, far from the throughput obtained with a random mapping. Moreover, we obtain a throughput close to the optimal solution in the particular cases on which the optimal throughput can be computed.
Type de document :
[Research Report] RR-6896, INRIA. 2009, pp.24
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
Contributeur : Alexandru Dobrila <>
Soumis le : mercredi 8 avril 2009 - 11:20:01
Dernière modification le : vendredi 6 juillet 2018 - 15:06:07
Document(s) archivé(s) le : vendredi 12 octobre 2012 - 16:26:03


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


  • HAL Id : inria-00374304, version 1


Anne Benoit, Alexandru Dobrila, Jean-Marc Nicod, Laurent Philippe. Throughput optimization for micro-factories subject to failures. [Research Report] RR-6896, INRIA. 2009, pp.24. 〈inria-00374304〉



Consultations de la notice


Téléchargements de fichiers