TY - GEN
T1 - Solving an avionics real-time scheduling problem by advanced IP-methods
AU - Eisenbrand, Friedrich
AU - Kesavan, Karthikeyan
AU - Mattikalli, Raju S.
AU - Niemeier, Martin
AU - Nordsieck, Arnold W.
AU - Skutella, Martin
AU - Verschae, José
AU - Wiese, Andreas
N1 - Funding Information:
This work was partially supported by Berlin Mathematical School, by DFG research center Matheon in Berlin, by DFG Focus Program 1307 within the project “Algorithm Engineering for Real-time Scheduling and Routing”, and by the Swiss National Science Foundation.
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=78249240578&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-15775-2_2
DO - 10.1007/978-3-642-15775-2_2
M3 - Conference contribution
AN - SCOPUS:78249240578
SN - 3642157742
SN - 9783642157745
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 11
EP - 22
BT - Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings
T2 - 18th Annual European Symposium on Algorithms, ESA 2010
Y2 - 6 September 2010 through 8 September 2010
ER -