Groupe d’études et de recherche en analyse des décisions

Ordonnancement des graphes de type diviser et régner

Djamal Rebaïne Professeur titulaire, Département d’informatique et de mathématique, Université du Québec à Chicoutimi, Canada

Djamal Rebaïne

Lien pour le webinaire
ID de réunion : 872 8448 5331
Code secret : 117253

Dans cette présentation, les graphes de type diviser et régner sont introduits. En plus de la question de leur reconnaissance, il sera essentiellement question de l'optimalité de la règle du plus haut niveau d'abord (Highest Level First - HLF) pour ordonnanceer un ensemble de n tâches, de durée unitaire, soumises à des précédence de type diviser et régner, sur un ensemble de m machines identiques. Le critère à minimiser est celui du temps total d'accomplissement de ces n tâches (Makespan). Cette solution répond à la conjecture de Rayward-Smith et Clark (1989). Il sera aussi question de l'extension de cette règle au même problème mais sur une machine avec des temps minimum de latence. Un temps minimum de latence représente le temps mimimal que doit séparer une tâche avec son successeur dans le graphe étudié.