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 :
Reports
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102041
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:12:42 AM
Last modification on : Sunday, April 28, 2019 - 1:23:08 AM

File

RR1998-25.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102041, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

13

Files downloads

10