Les Problèmes d'ordonnancement à machines parallèles de taches dépendantes

Abstract

Nous considérons les problèmes d’ordonnancement NP-difficiles, de tâches dépendantes sur des machines parallèles identiques, afin de minimiser la longueur d’ordonnancement appelée makespan. Six listes de priorités ont été définies, implémentées et comparées. Elles sont basées sur le chemin critique, la durée d’exécution la plus courte d’abord, le nombre de successeurs immédiats d’une tâche le plus grand d’abord, l’ordre aléatoire et une variante du plus court chemin. La performance des méthodes est reproduite graphiquement. Nous mesurons la qualité et l’efficacité de chaque liste. Un algorithme génétique, noté AG, basé sur deux types de croisement, est implémenté et comparé avec les listes. Après de nombreuses expériences numériques et suite à des tests, les meilleurs résultats sont obtenus avec des variantes utilisant les listes comme population initiale de l’AG. Un second graphe comparatif avec les listes est obtenu. Les temps de calculs des six listes et de quatre variantes de l’AG sont donnés sous forme d’un tableau récapitulatif.