8481 articles  [english version]

inria-00544146, version 1

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

Anne Benoit () a12, Alexandru Dobrila () 13, Jean-Marc Nicod () 3, Laurent Philippe () 3

N° RR-7479 (2010)

Résumé : 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.

  • a –  École normale supérieure de Lyon - ENS Lyon
  • 1 :  GRAAL (INRIA Grenoble Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme)
  • CNRS : UMR5668 – INRIA – École Normale Supérieure - Lyon – Université Claude Bernard - Lyon I – Laboratoire d'informatique du Parallélisme
  • 2 :  Laboratoire de l'Informatique du Parallélisme (LIP)
  • Université de Lyon – CNRS : UMR5668 – INRIA – École Normale Supérieure - Lyon – Université Claude Bernard - Lyon I
  • 3 :  Laboratoire d'Informatique de Franche-Comté (LIFC)
  • Université de Franche-Comté : EA4269
  • Domaine : Informatique/Calcul parallèle, distribué et partagé
  • Mots-clés : distributed systems – fault tolerance – scheduling – optimization heuristics.
  • Référence interne : RR-7479
 
  • inria-00544146, version 1
  • oai:hal.inria.fr:inria-00544146
  • Contributeur : 
  • Soumis le : Mardi 7 Décembre 2010, 13:45:45
  • Dernière modification le : Jeudi 9 Décembre 2010, 08:52:03