A multirecombinative evolutionary approach to solve the parallel task scheduling problem

Abstract

Allocation of the components (tasks) of a parallel program to processors in a multiprocessor or a multicomputer system take full advantage of the computational power provided by the system. Evolutionary approaches has been used in the past to implement efficiently this type of scheduling. Those approaches showed their advantages when contrasted against conventional approaches and different chromosome representations were proposed. Latest improvements in evolutionary computation include multirecombinative variants allowing multiplicity of crossovers on the selected couple of parents. Multiple crossovers per couple (MCPC) exploits good parents' features in the creation of offspring. Performance enhancements were clearly demonstrated in single and multicriteria optimization under this approach. This paper shows three 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. This involves the assignment of partially ordered tasks onto the system architecture processing components. Two evolutionary algorithms using a direct representation, are contrasted with the well-known Graham's [12] list scheduling algorithm (LSA). The first one makes use of the conventional single crossover per couple (SCPC) approach while the second, following cunent trends in evolutionary computation, uses (MCPC) a multirecombinated approach. Chromosome structure, genetic operators, experiments and results are discussed.