Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-24T11:43:26.488Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  15 August 2002

Dalila Tayachi ,
Philippe Chrétienne  and
Khaled Mellouli
Dalila Tayachi
Affiliation:
Institut Supérieur de Gestion, 41 rue de Liberté, Cité Bouchoucha, Le Bardo, Tunis, Tunisie.
Philippe Chrétienne
Affiliation:
Laboratoire d'Informatique de Paris, Université de Paris VI, Paris, France
Khaled Mellouli
Affiliation:
Institut Supérieur de Gestion, 41 rue de Liberté, Cité Bouchoucha, Le Bardo, Tunis, Tunisie.
Get access

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.

Keywords

Scheduling problemscommunication delaysdecision graphtabu searchlist algorithm.
Type
Research Article
Information
RAIRO - Operations Research , Volume 34 , Issue 4 , October 2000 , pp. 467 - 485
Copyright
© EDP Sciences, 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)