Static Multiprocessor Task Graph Scheduling in the Genetic Paradigm: A Comparison of Genotype Representations

In the NP-hard multiprocessor scheduling problem a set of precedence constrained tasks are allocated onto processors in a processing order in order to minimise the makespan. Many heuristic methods for finding solutions exist, but they are all sub-optimal on general task graphs. To improve these solutions, genetic algorithms have successfully been applied to the problem and the results reported have been superior to the list-scheduling approaches. However, the application of genetic algorithms to the multiprocessor scheduling problem have predominantly followed two main paths of developments, namely the use of direct and indirect representations. In the direct chromosome representation the schedule is represented and manipulated directly by the genetic operators, and the genotype is identical to the phenotype. In the indirect representation only the decisions on how to build the schedule is encoded in the chromosome. The genetic operators affect the schedules implicitly, and the genotype is different to the phenotype. In this paper these two main approaches to genetic scheduling are compared by evaluating their respective quality of results and time of convergence.Dans le problème NP-dur de l'ordonnancement sur machine parallèle, un ensemble de tâches avec des contraintes de précédences sont ordonnancées sur un ensemble de processeurs afin de minimiser la durée totale d'exécution. Plusieurs méthodes heuristiques existent pour trouver des solutions sous-optimales. Pour améliorer ces solutions, les algorithmes génétiques ont été utilisés avec succès et les résultats sont meilleurs que ceux obtenus avec des algorithmes de listes. Cependant, cette utilisation d'algorithmes génétiques pour le problème de l'ordonnancement sur machine parallèle s'est fait suivant deux voies principales: la représentation directe et celle indirecte. Dans le cas de la représentation directe, l'ordonnancement est représenté directement par le chromosome et manipulé aussi de manière directe par les opérateurs génétiques. Le génotype est donc identique au phénotype. Par contre, dans le cas de la représentation indirecte, le chromosome code seulement des décisions sur comment construire la solution. Les opérateurs génétiques affectent donc la solution de manière implicite, indirecte et donc le génotype est différent du phénotype. Dans ce rapport, les deux méthodes sont comparées