Retour aux activités
Séminaire “Un(e) chercheur(-euse) du GERAD vous parle!”

Ordonnancement des graphes de type diviser et régner

iCalendar

27 oct. 2021   11h00 — 12h00

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

Djamal Rebaïne

Présentation sur YouTube

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é.

Olivier Bahn responsable

Lieu

Webinaire
Zoom
Montréal Québec
Canada