A tabu method for the problem of scheduling tasks on processors in the presence of communication delays

This paper deals with the problem of scheduling n tasks on m identical processors in the presence of communication delays. A new approach 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.