Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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 metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:12:42 AM
Last modification on : Saturday, September 11, 2021 - 3:19:16 AM


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