Une méthode tabou pour l'ordonnancement multiprocesseur avec délais de communication

¹ Institut Supérieur de Gestion, 41 rue de Liberté, Cité Bouchoucha, Le Bardo, Tunis, Tunisie.
² Laboratoire d'Informatique de Paris, Université de Paris VI, Paris, France

Received: June 1999

Abstract

This paper deals with the problem of scheduling n tasks on m identical processors in the presence of communication delays. A new approach of modelisation by a decision graph and a resolution by a tabu search method is proposed. Initial solutions are constructed by list algorithms, and then improved by a tabu algorithm operating in two phases. The experiments carried on arbitrary graphs show the efficiency of our method and that it outperformed the principle existent heuristics.

Résumé

Cet article traite des problèmes d'ordonnancement de n tâches sur m processeurs identiques, en présence de délais de communication. Une nouvelle approche de modélisation par un graphe d'arbitrage et de résolution par une méthode tabou est proposée. Des solutions initiales sont construites par des algorithmes de liste, qui sont ensuite améliorées par un algorithme tabou opérant en deux phases. Des expérimentations effectuées sur des graphes générés aléatoirement montrent que notre méthode est performante et qu'elle se comporte mieux que les principales heuristiques existantes.