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] 
  • F. Eisenbrand, M. Niemeier, M. Skutella, J. Verschae and A. Wiese. "Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods". 18th Annual European Symposium on Algorithms (ESA 2010). 2010. [More] 
  • B. Peis, M. Skutella and A. Wiese. "Packet Routing on the Grid". 9th Latin American Theoretical Informatics Symposium (LATIN 2010). 2010. pp. 120-130. [More] 
  • F. Eisenbrand, N. Hähnle, M. Niemeier, M. Skutella, J. Verschae and A. Wiese. "Scheduling periodic tasks in a hard real-time environment". 37th International Colloquium on Automata, Languages and Programming (ICALP 2010). 2010. pp. 299-310. [More] 
  • F. Eisenbrand and T. Rothvoß. "EDF-schedulability of synchronous periodic task systems is coNP-hard". 21st {S}ymposium on {D}iscrete {A}lgorithms ({SODA} 2010). 2010. pp. 1029-1034. [More] 
  • B. Peis, S. Stiller and A. Wiese. "Policies for Periodic Packet Routing". Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010). 2010. pp. 266-278. [More] 
  • B. Peis, M. Skutella and A. Wiese. "Packet Routing: Complexity and Algorithms". Berlin : Springer. 2010. pp. 217-228. [More] 
  • R. I. Davis, T. Rothvoß, S. K. Baruah and A. Burns. "Exact quantification of the suboptimality of uniprocessor fixed priority pre-emptive scheduling", Real-Time Systems, Vol. 43. 2009. [More] 
  • A. Karrenbauer and T. Rothvoß. "An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling". 17th Annual European Symposium on Algorithms (ESA 2009). 2009. pp. 432-443. [More] 
  • F. Eisenbrand and T. Rothvoß. "New Hardness Results for Diophantine Approximation". Proceedings of the 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009). 2009. pp. 98-110. [More] 
  • R. Koch, B. Peis, M. Skutella and A. Wiese. "Real-Time Message Routing and Scheduling". 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009). 2009. pp. 217-230. [More] 
  • F. Eisenbrand and T. Rothvoß. "Static-priority real-time scheduling: Response time computation is NP-hard". 29th IEEE Real-Time Systems Symposium (RTSS 2008). 2008. pp. 397-406. [More] 
  • F. Eisenbrand and T. Rothvoß. "A PTAS for static priority real-time scheduling with resource augmentation". 35th international Colloquium on Automata, Languages and Programming (ICALP 2008). 2008. pp. 246-257. [More] 
View less
[ Back ]