2002 | OriginalPaper | Buchkapitel
Performance of Evolutionary Approaches for Parallel Task Scheduling under Different Representations
verfasst von : Susana Esquivel, Claudia Gatica, Raúl Gallard
Erschienen in: Applications of Evolutionary Computing
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Task scheduling is known to be NP-complete in its general form as well as in many restricted cases. Thus to find a near optimal solution in, at most, polynomial time different heuristics were proposed. The basic Grahamś task graph model [1] was extended to other list-based priority schedulers [2] where increased levels of communication overhead were included [3]. Evolutionary Algorithms (EAs) have been used in the past to implement the allocation of the components (tasks) of a parallel program to processors [4], [5]. In this paper five evolutionary algorithms are compared. All of them use the conventional Single Crossover Per Couple (SCPC) approach but they differ in what is represented by the chromosome: processor dispatching priorities, tasks priority lists, or both priority policies described in a bipartite chromosome. Chromosome structure, genetic operators, experiments and results are discussed.