Algorithm Engineering for Real-time Scheduling and Routing
Description
Prof. Dr. Friedrich Eisenbrand; École Polytechnique Fédérale de Lausanne
Prof. Dr. Martin Skutella; Technische Unversität Berlin
Project website
While 20 years ago, microprocessors have mostly been used in desktop computer workstations and large-scale computers they have meanwhile become ubiquitous. They are used in nearly all areas of technology and specifically in safety and mission critical applications. The future vision of the automotive and avionics industry is complete, safe and reliable drive-by-wire and fly-by-wire respectively. Such industrial applications gave rise to the field of computer science which is called real-time scheduling and routing. Whereas classical scheduling deals with the distribution of a finite set of tasks to a set of machines, real-time scheduling deals with recurring tasks which are often periodic and thus appear infinitely often. Since the processors in a real-time system communicate by passing messages, the messages have to be routed through the architecture (modeled as a directed graph) additionally.
The goal of the project is to develop, implement, analyze and test algorithms for real-time scheduling and routing problems using methods of linear and integer programming as well as various scheduling and routing techniques from discrete optimization.
Publications
- M. Niemeier and A. Wiese. "Scheduling with an Orthogonal Resource Constraint". 10th Workshop on Approximation and Online Algorithms (WAOA2012). 2012. [More]
- B. Peis and A. Wiese. "Universal packet routing with arbitrary bandwidths and transit times". Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization (IPCO 2011). 2011. [More]
- M. Niemeier, A. Wiese and S. Baruah. "Partitioned real-time scheduling on heterogeneous shared-memory multiprocessors". Proceedings of the 23rd Euromicro Conference on Real-Time Systems (ECRTS 2011). 2011. [More]
- B. Peis and A. Wiese. "Throughput Maximization for Periodic Packet Routing on Trees and Grids". 8th Workshop on Approximation and Online Algorithms (WAOA 2010). 2011. [More]
- A. Karrenbauer and T. Rothvoß. "A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks". Proceedings of the 8th International Workshop on Approximation and Online Algorithms (WAOA 2010). 2011. pp. 166-177. [More]