Solving an avionics real-time scheduling problem by advanced IP-methods

Friedrich Eisenbrand, Karthikeyan Kesavan, Raju S. Mattikalli, Martin Niemeier, Arnold W. Nordsieck, Martin Skutella, José Verschae, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

25 Scopus citations


We report on the solution of a real-time scheduling problem that arises in the design of software-based operation control of aircraft. A set of tasks has to be distributed on a minimum number of machines and offsets of the tasks have to be computed. The tasks emit jobs periodically starting at their offset and then need to be executed on the machines without any delay. Also, further constraints in terms of memory usage and redundancy requirements have to be met. Approaches based on standard integer programming formulations fail to solve our real-world instances. By exploiting structural insights of the problem we obtain an IP-formulation and primal heuristics that together solve the real-world instances to optimality and outperform text-book approaches by several orders of magnitude. Our methods lead, for the first time, to an industry strength tool to optimally schedule aircraft sized problems.

Original languageEnglish
Title of host publicationAlgorithms, ESA 2010 - 18th Annual European Symposium, Proceedings
Number of pages12
EditionPART 1
StatePublished - 2010
Externally publishedYes
Event18th Annual European Symposium on Algorithms, ESA 2010 - Liverpool, United Kingdom
Duration: 6 Sep 20108 Sep 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6346 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th Annual European Symposium on Algorithms, ESA 2010
Country/TerritoryUnited Kingdom


Dive into the research topics of 'Solving an avionics real-time scheduling problem by advanced IP-methods'. Together they form a unique fingerprint.

Cite this