A Genetic Algorithm for Multiprocessor Scheduling

Research output: Contribution to journalArticlepeer-review

519 Scopus citations

Abstract

The problem of multiprocessor scheduling can be stated as finding a schedule for a general task graph to be executed on a multiprocessor system so that the schedule length can be minimizEd., This scheduling problem is known to be NP-hard, and methods based on heuristic search have been proposed to obtain optimal and suboptimal solutions. Genetic algorithms have recently received much attention as a class of robust stochastic search algorithms for various optimization problems. In this paper, an efficient method based on genetic algorithms is developed to solve the multiprocessor scheduling problem. The representation of the search node is based on the order of the tasks being executed in each individual processor. The genetic operator proposed is based on the precedence relations between the tasks in the task graph. Simulation results comparing the proposed genetic algorithm, the list scheduling algorithm, and the optimal schedule using random task graphs, and a robot inverse dynamics computational task graph for various are presented.

Original languageEnglish (US)
Pages (from-to)113-120
Number of pages8
JournalIEEE Transactions on Parallel and Distributed Systems
Volume5
Issue number2
DOIs
StatePublished - Feb 1994

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • Direct acyclic graph
  • NP-hard
  • genetic algorithms
  • genetic operators
  • multiprocessor scheduling
  • optimization
  • stochastic search algorithms

Fingerprint

Dive into the research topics of 'A Genetic Algorithm for Multiprocessor Scheduling'. Together they form a unique fingerprint.

Cite this