Computing schedules for time-triggered control using genetic algorithms

Truong Nghiem, Georgios E. Fainekos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this work, we study the optimal scheduling problem for embedded control systems. Given a number of numerical computation tasks that must be executed on an embedded computer, the goal is to find a periodic schedule that minimizes the error of the implementation with respect to the ideal system. In this paper, we pose two open problems: the decidability of the optimal scheduling problem for timed-triggered controllers (OSTTC) and the time complexity of the corresponding bounded version of the problem. We conjecture that the former is undecidable and that the latter is NP-Complete. In view of the previous conjectures, we present a Genetic Algorithm (GA) for the OSTTC problem. Initial experimental results of GA-OSTTC are very promising when compared to random search and exhaustive bounded search.

Original languageEnglish (US)
Title of host publicationProceedings of the 18th IFAC World Congress
PublisherIFAC Secretariat
Number of pages6
Edition1 PART 1
ISBN (Print)9783902661937
StatePublished - 2011
Externally publishedYes

Publication series

NameIFAC Proceedings Volumes (IFAC-PapersOnline)
Number1 PART 1
ISSN (Print)1474-6670


  • Digital control
  • Genetic algorithms
  • Scheduling

ASJC Scopus subject areas

  • Control and Systems Engineering


Dive into the research topics of 'Computing schedules for time-triggered control using genetic algorithms'. Together they form a unique fingerprint.

Cite this