Résolution du problème d'ordonnancement P/prec/Cmax par un algorithme de colonie de fourmis

Abstract

Le difficile problème étudié est celui de l’ordonnancement de tâches sur des machines parallèles identiques à contraintes de précédence afin de minimiser la longueur d’ordonnancement. Il est noté P prec Cmax. Une recherche bibliographique a été entreprise. Une adaptation d’un algorithme de colonies de fourmis est réalisée pour le résoudre. Son application nous fournit une meilleure affectation de tâches aux machines. En face de chaque machine, les tâches sont exécutées selon trois règles de priorité PLC, VPLC et MAX. Avec ces trois règles et les deux informations heuristiques statiques et dynamiques appelées « visibilité », six versions de cet algorithme de colonies de fourmis ont été obtenues, étudiées et comparées. La justification et la finitude de l’algorithme sont exposées Son implémentation est discutée. De nombreuses expérimentations ont été effectuées sur des données de problèmes générées aléatoirement. L’étude comparative de quatre métaheuristiques de type recuit simulé, recherche taboue, algorithme génétique et la version colonie de fourmis STA_MAX est réalisée. Les solutions obtenues par la version STA_MAX ont les meilleures. Un simulateur conçu par nos soins est présenté. Il permet de tester les différentes métaheuristiques.