Une heuristique pour l’ordonnancement sur machines parallèles minimisant le retard total

Session : SS13-2 / SS13 : Méthodes d'optimisation pour l'ordonnancement et la planification
Vendredi 12 février 10:30 - 11:30 Salle : CI2-05
Benjamin Vincent, Nikolay Tchernev et Christophe Duhamel

Le problème auquel nous nous intéressons dans ce travail est l’ordonnancement d’une liste de jobs à effectuer sur un ensemble de machines parallèles identiques. L’objectif est de minimiser le retard total des différents jobs.Une heuristique basée sur la méthode du recuit simulé a été développée pour ce problème. Cette heuristique utilise notamment plusieurs règles de dominance connues sur ce problème qui sont usuellement utilisées pour des méthodes exactes de branchement de type Branch And Bound.

Mots clés : Machines parallèles, Retard total, Recuit simulé