A tabu method for multiprocessor scheduling with communication delays

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