Throughput optimization for micro-factories subject to task and machine failures

Abstract : In this paper, we study the problem of optimizing the throughput for micro-factories subject to failures. The challenge is to map several tasks of different types onto a set of machines. The originality of our approach is the failure model for such applications in which not only the machines are subject to failures but the reliability of a task may depend on its type. The failure rate is unrelated: a probability of failure is associated to each couple (task type, machine). We consider different kind of mappings: in one-to-one mappings, each machine can process only a single task, while several tasks of the same type can be processed by the same machine in specialized mappings. Finally, general mappings have no constraints. The optimal one-to-one mapping can be found in polynomial time for particular problem instances, but the problem is NP- hard in most of the cases. For the most realistic case of specialized mappings, which turns out to be NP-hard, we design several polynomial time heuristics and a linear program allows us to find the optimal solution (in exponential time) for small problem instances. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput achieved with a random mapping. Moreover, we obtain a throughput close to the optimal solution in the particular cases where the optimal throughput can be computed.
Type de document :
[Research Report] RR-7479, INRIA. 2010
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
Contributeur : Anne Benoit <>
Soumis le : mardi 7 décembre 2010 - 13:45:45
Dernière modification le : vendredi 6 juillet 2018 - 15:06:07
Document(s) archivé(s) le : lundi 5 novembre 2012 - 12:31:04


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


  • HAL Id : inria-00544146, version 1


Anne Benoit, Alexandru Dobrila, Jean-Marc Nicod, Laurent Philippe. Throughput optimization for micro-factories subject to task and machine failures. [Research Report] RR-7479, INRIA. 2010. 〈inria-00544146〉



Consultations de la notice


Téléchargements de fichiers