An evolutionary approach to the parallel task scheduling problem

Abstract

A parallel program, when running, can be conceived a set of parallel components (tasks) which can be executed according to sorne precedence relationship. In this case efficient scheduling of tasks permits to take full.advantage of the computational power provided by a multiprocessor or a multicomputer system. This involves the assignment of partially ordered tasks onto the system architecture processing components. Ihis work shows the problem of allocating a number of nonidentical tasks in a multiprocessor or multicomputer system. Ihe 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 nonpreeptive. Ihe well-known Grabam's [8] list scheduling algorithm (LSA) is contrasted with an evolutionary approach using the indirect-decode representation.