Algorithm Engineering für Real-Time Scheduling und Routing

• Antragsteller: Professor Dr. Friedrich Eisenbrand; Professor Dr. Martin Skutella
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 47960878

• Erstellungsjahr: 2014

Zusammenfassung der Projektergebnisse

The goal of the project was the development of efficient algorithms for solving real-time scheduling and routing problems. Such problems occur, e.g., in the design of drive-by-wire and fly-by-wire systems in modern vehicles and aircrafts. In these applications, timely execution of instructions in the embedded computer systems is of vital importance. Mathematically, these systems are modeled as multi-processor real-time scheduling problems, in which each processor is represented by a machine and the instructions are modeled as jobs. Each job has a processing time, that might depend on the machine on which it is processed. Jobs of the same type that have to be carried out on a regular basis are grouped into tasks, each tasks emitting a new job within a specified time interval. For the communication between the different entities of the system, communication packets have to be routed along specified paths in the network. Packet routing problems ask for efficient routing schemes describing the path of these data packages within the network, preventing congestion from colliding packages and minimizing the time needed for the transmissions. The optimization problems for real-time scheduling and packet routing resulting from these applications are particularly challenging, as they exhibit—beyond the challenges found in standard scheduling and routing problems - aspects of periodicity, shared memory usage across multiple machines, and a temporal dimension in routing. The main expertise of the two collaborating groups at TU Berlin and EPFL lies in classical scheduling and routing on the one hand and in algorithms for non-combinatorial integer programming on the other hand. We believed and expected that these competences must be combined to achieve significant progress in tackling difficult real-time scheduling and routing problems. This expectation has been strongly confirmed throughout the course of the project. Our results answer some long-standing open questions in the field and set foot into interesting new areas that had not yet been covered by research previously. As most real-time scheduling problems are NP-hard, exact solution methods are unlikely to solve these problems efficiently. We therefore developed approximation algorithms that compute solutions with a provable approximation guarantee, i.e., the value of the computed solution is within a small factor of the optimal solution. We derived such algorithms for several fundamental real-time scheduling problems and packet routing problems, improving previous results and extending them to more general problems that had not been considered previously. In particular, we successfully adressed the challenges mentioned above by resolving the hard periodicity constraints using new insights from algorithmic number theory, by solving scheduling problems with shared memory requirements with the help of advanced configuration LP formulations, and by tackling the temporal dimension of packet routing using techniques from the theory network flows over time. Another important aspect of the project was the algorithm engineering paradigm of design, analysis, implementation, and evaluation of the developed algorithms. Using observations obtained through frequent computational experiments, we were able to significantly improve our algorithms and remove computational bottlenecks. Notably, our project also featured a practical cooperation with partners from avionics industry. Here, we implemented an integer programming based solution framework for a hard periodic maintenance problem. Our approach outperformed previous stateof-the-art methods by several orders of magnitude. Our computational experiments also revealed an unexpected answer to a long-standing open question: a counter-example to a famous conjecture of Schrijver, Seymour, and Winkler on the relation between routing splittable and unsplittable packets on a ring. Our work has resulted in numerous publications in top journals and conferences, not only in the field of combinatorial optimization and integer programming but also in the area of real time systems. The project thus represented an important step in bringing this two fields of research closer together.

Projektbezogene Publikationen (Auswahl)

• Static-priority Real-time Scheduling: Response Time Computation is NP-hard. In IEEE Real-Time Systems Symposium (RTSS), 2008
  F. Eisenbrand and T. Rothvoß
  
• An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA 2009), volume 5757 of Lecture Notes in Computer Science, pages 432–443. Springer, 2009
  A. Karrenbauer and T. Rothvoß
  
• Exact quantification of the sub-optimality of uniprocessor fixed-priority preemptive scheduling. Real-Time Systems, 43(3):211–258, 2009
  R. Davis, T. Rothvoß, S. Baruah, and A. Burns
  
• Real-time message routing and scheduling. In Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009), volume 5687 of Lecture Notes in Computer Science, pages 217–230. Springer, 2009
  R. Koch, B. Peis, M. Skutella, and A. Wiese
  
• EDF-schedulability of synchronous periodic task systems is coNP-hard. In Proceedings of the the 26th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 1029–1034, 2010
  F. Eisenbrand and T. Rothvoß
  
• Packet routing: Complexity and algorithms. In Proceedings of the 7th Workshop on Approximation and Online Algorithms (WAOA 2009), volume 5893 of Lecture Notes in Computer Science, pages 217–228. Springer, 2010
  B. Peis, M. Skutella, and A. Wiese
  
• Scheduling periodic tasks in a hard real-time environment. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), volume 6198 of Lecture Notes in Computer Science, pages 299–311. Springer, 2010
  F. Eisenbrand, N. Hähnle, M. Niemeier, M. Skutella, J. Verschae, and A. Wiese
  
• Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA 2010), volume 6346 of Lecture Notes in Computer Science, pages 11–22. Springer, 2010
  F. Eisenbrand, K. Kesavan, R. Mattikalli, M. Niemeier, A. Nordsieck, M. Skutella, J. Verschae, and A. Wiese
  
• A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks. In Proceedings of the 8th International Workshop on Approximation and Online Algorithms (WAOA 2010), volume 6534 of Lecture Notes in Computer Science, pages 166–177. Springer, 2011
  A. Karrenbauer and T. Rothvoß
  
• Partitioned real-time scheduling on heterogeneous shared-memory multiprocessors. In Proceedings of the 23rd Euromicro Conference on Real-Time Systems (ECRTS 2011), pages 115–124, 2011
  M. Niemeier, A. Wiese, and S. Baruah
  
• Throughput maximization for periodic packet routing on trees and grids. In Proceedings of the 8th Workshop on Approximation and Online Algorithms (WAOA 2010), volume 6534 of Lecture Notes in Computer Science, pages 213–224. Springer, 2011
  B. Peis and A. Wiese
  
• Universal packet routing with arbitrary bandwidths and transit times. In Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2011), volume 6655 of Lecture Notes in Computer Science. Springer, 2011
  B. Peis and A. Wiese
  
• Universal sequencing on a single unreliable machine. SIAM Journal on Computing, 41(3):565–586, 2012
  L. Epstein, A. Levin, J. Mestre, A. Marchetti-Spaccamela, N. Megow, M. Skutella, and L. Stougie
  
• Approximation algorithms for facility location with capacitated and length-bounded tree connections. In Proceedings of the 21th Annual European Symposium on Algorithms – ESA 2013, volume 8125 of Lecture Notes in Computer Science, pages 707–718. Springer, 2013
  J. Matuschke, A. Bley, and B. Müller
  
• Scheduling with an orthogonal resource constraint. In Approximation and Online Algorithms (WAOA 2012), volume 7846 of Lecture Notes in Computer Science, pages 242–256. Springer, 2013
  M. Niemeier and A. Wiese
  
• Strong LP formulations for scheduling splittable jobs on unrelated machines. In Proceedings of the 17th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2014), volume 8494 of Lecture Notes in Computer Science, pages 249–260. Springer, 2014
  J. R. Correa, A. Marchetti-Spaccamela, J. Matuschke, L. Stougie, O. Svensson, V. Verdugo, and J. Verschae
  
• Extended formulations, nonnegative factorizations, and randomized communication protocols. Mathematical Programming B., October 2015, Volume 153, Issue 1, pp 75–94
  Y. Faenza, S. Fiorini, R. Grappe, and H.R. Tiwary