1/1997 : Solving NP-Complete Problems in Real-Time System Design by Multichromosome Genetic Algorithms

RR Number

1/1997

Conference

In Proceedings of the SIGPLAN 1997 Workshop on Languages, Compilers, and Tools for Real-Time Systems, pages 68-76, ACM SIGPLAN, June 1997

Author(s)

Roman Nossal, Thomas Galla

Abstract

Most problems in the design of real-time applications like task allocation or scheduling belong to the class of NP-complete problems and can be solved efficiently only by heuristics. Genetic Algorithms are a relatively new method to attack these problems. Conventional Genetic Algorithms, however, have a number of drawbacks that reduce their applicability to design problems of real-time systems.

The Genetic Algorithm presented in this paper implements enhancements to standard Genetic Algorithms to eliminate these problems. It allows arbitrary gene values and supports multiple chromosomes per individuum. The paper focuses on the advantages of the use of Genetic Algorithms in real-time system design in comparison to other heuristic problem solving techniques. The applicability of the enhanced algorithm is shown by solving a typical problem of real-time system design, the determination of a bus access schedule for a real-time LAN.

Bibtex

@article{ nossal:1997-1,
  author =       "Roman Nossal and Thomas Galla",
  title =        "Solving NP-Complete Problems in Real-Time System Design by Multichromosome Genetic Algorithms",
  journal =      "In Proceedings of the SIGPLAN 1997 Workshop on Languages, Compilers, and Tools for Real-Time Systems, pages 68-76, ACM SIGPLAN, June 1997",
  year =         "1997",
  month =        "Jun."
}

Download

Get rr-01-1997.pdf - Adobe PDF-format, (225.12 KB; posted at August 20 2001)