Performance of Evolutionary Approaches for Parallel Task Scheduling under Different Representations

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.