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