×

Solving an avionics real-time scheduling problem by advanced IP-methods. (English) Zbl 1287.90021

de Berg, Mark (ed.) et al., Algorithms – ESA 2010. 18th annual European symposium, Liverpool, UK, September 6–8, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-15774-5/pbk). Lecture Notes in Computer Science 6346, 11-22 (2010).
Summary: 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.
For the entire collection see [Zbl 1194.68069].

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI