Evolutionary approaches for the parallel task scheduling problem : the representation issue

Abstract

The problem of how to find a schedule on m > 2 processors of equal capacity that minimises the whole processing time of independent tasks has been shown as belonging to the NP-complete class (Horowitz and Sahni [12]). Evolutionary Algorithms (EAs) have been used in the past to implement the allocation of the components (tasks) of a parallel program to processors [12], [13], [14], [16], [17]. Those approaches showed their advantages when contrasted against conventional approaches and different chromosome representations were proposed. This paper shows four algorithms to solve the problem of allocating a number of non-identical related tasks in a multiprocessor or multicomputer system. The model assumes that the system consists of a number of identical processors and only one task may execute on a processor at a time. All schedules and tasks are non-preemptive. Three evolutionary algorithms, using an indirect-decode representation, are contrasted with the well-known Graham’s [11] list scheduling algorithm (LSA). All of them use the conventional Single Crossover Per Couple (SCPC) approach and indirectdecode representation but they differ in what is represented by the decoders. In the first representation scheme, decoders represent processor dispatching priorities, in the second decoders represent tasks priority lists, and in the third decoders represent both processor dispatching priorities and tasks priority lists in a bipartite chromosome. Chromosome structure, genetic operators, experiments and results are discussed.