Back to activities
“Meet a GERAD researcher!” seminar

Ordonnancement des graphes de type diviser et régner

iCalendar

Oct 27, 2021   11:00 AM — 12:00 PM

Djamal Rebaïne Full Professor, Department of Computer Sciences and Mathematics, Université du Québec à Chicoutimi, Canada

Djamal Rebaïne

Presentation on 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 organizer

Location

Online meeting
Zoom
Montréal Québec
Canada