Efficacite des Heuristiques et du Recuit Simule pour l'Ordonnancement de TachesConcurrentes: Une Comparaison Empirique (Effectiveness of Heuristics and Simulated Annealing for the Scheduling of Concurrent Tasks: An Empirical Comparison)

摘要

The scheduling of concurrent tasks with precedence constraints in parallelsystems in order to minimize the makespan is known to be NP complete. The average effectiveness and the average efficiency of 27 heuristic and 7 simulated annealing algorithms used for the minimization of makespan are studied. A computational experiment showed that the simulated annealing algorithms are very effective compared with the heuristics, provided these algorithms converge. It turns out that some heuristics are quite effective on average, and that the heuristics, provided they are used together, have qualitative behavior not much worse than that of the simulated annealing and are much more efficient.