30/1997 : An Evolutionary Approach to Multiprocessor Scheduling of Dependent Tasks

RR Number

30/1997

Conference

1st International Workshop on Biologically Inspired Solutions to Parallel Processing Problems, March 1998, Orlando, Florida, USA

Author(s)

Roman Nossal

Abstract

The scheduling of application tasks is a problem that occurs in all multiprocessor systems. This problem becomes even more complicated if the tasks are not independent but are interrelated by mutual exclusion and precedence constraints.

This paper presents an approach for pre-runtime scheduling of periodic tasks on multiple processors for a real-time system that must meet hard deadlines. The tasks can be related to each other bymutual exclusion and precedence forming an acyclic graph. The proposed scheduler is based on Genetic Algorithms, which relieves the user from knowing how to construct a solution. Consequently, the paper focuses on the problem encoding, i.e., the representation of the problem by genes and chromosomes, and the derivation of an appropriate fitness function. The main benefit of the approach is that it is scalable to any number of processors and can easily be extended to incorporate further requirements.

Bibtex

@article{ nossal:1997-30,
  author =       "Roman Nossal",
  title =        "An Evolutionary Approach to Multiprocessor Scheduling of Dependent Tasks",
  journal =      "1st International Workshop on Biologically Inspired Solutions to Parallel Processing Problems, March 1998, Orlando, Florida, USA",
  year =         "1998",
  month =        "Mar."
}

Download

Get rr-30-1997.pdf - Adobe PDF-format, (185.88 KB; posted at August 21 2001)