Skip to Main content Skip to Navigation

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

Abstract : 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.
Document type :
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:12:42 AM
Last modification on : Wednesday, March 18, 2020 - 4:26:53 PM


Files produced by the author(s)


  • HAL Id : hal-02102041, version 1



Pascal Rebreyend, F. E. Sandnes, G. M. Megson. Static Multiprocessor Task Graph Scheduling in the Genetic Paradigm: A Comparison of Genotype Representations. [Research Report] LIP RR-1998-25, Laboratoire de l'informatique du parallélisme. 1998, 2+15p. ⟨hal-02102041⟩



Record views


Files downloads