Studying the parallel task scheduling problem with conventional and evolutionary algorithms

Abstract

This work summarizes results when facing the problem of allocating a number of nonidentical tasks in a parallel system. The model assumes that the system consists of a number of identical processors and that only one task may be executed on a processor at a time. All schedules and tasks are non-preemptive. Graham’s [8] well-known list scheduling algorithm (LSA) was contrasted with different evolutionary algorithms (EAs), which differ on the representations and the recombinative approach used. Regarding the representation, direct and indirect representations of schedules were used. Concerning recombination, the conventional single crossover per couple (SCPC), and multiple crossovers per couple (MCPC) [3], [4] were implemented. Latest improvements in evolutionary computation include multirecombinative variants. Multiple crossovers multiples on parents (MCMP) provides a means to exploit good features of more than two parents selected according to their fitness by repeatedly applying any crossover method: a number prq of crossovers is applied on a number sut of selected parents. Performance enhancements were clearly demonstrated in single and multicriteria optimisation [5], [6] under this approach. The use of a stud is a well-known practice in breeding by which a breeding animal due to its special features is selected more often for reproduction. This model of reproduction is being implemented for the Parallel Task Scheduling Problem.