Scheduling

Abstract

In scheduling one is given a set of jobs which has to to be distributed on machines or processors. The problem types in this field are numerous. Jobs may be equipped with release times,deadlines and precedence constraints and may be scheduled with preemptive or non-preemptive policies. The objective can be e.g. to minimize the makespan, the number of needed machines, the (weighted) sum of completion times and so on and so forth.

In real-time scheduling the input consists of a set of tasks that release jobs periodically or sporadically.

We work on algorithmic aspects in this field as well as on complexity issues.

Apart from the obvious application in computer science, scheduling is also of high practical impact in operations research.

Members

Friedrich Eisenbrand

Martin Niemeier

Andreas Karrenbauer

Thomas Rothvoß

Selected Publications

Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods

F. Eisenbrand; K. Kesavan; R. Mattikalli; M. Niemeier; A. Nordsieck et al. 

2010. 18th Annual European Symposium on Algorithms (ESA2010), Liverpool, United Kingdom, September 6-8, 2010.

Scheduling periodic tasks in a hard real-time environment

F. Eisenbrand; N. Hähnle; M. Niemeier; M. Skutella; J. Verschae et al. 

2010. 37th International Colloquium on Automata, Languages and Programming (ICALP2010), Bordeaux, France, July 5-10, 2010. p. 299-311.

Exact quantification of the sub-optimality of uniprocessor fixed-priority pre- emptive scheduling

R. Davis; T. Rothvoß; S. Baruah; A. Burns 

Real-Time Systems. 2009. Vol. 43, num. 3, p. 211–258. DOI : 10.1007/s11241-009-9079-4.

Static-priority Real-time Scheduling: Response Time Computation is NP-hard

F. Eisenbrand; T. Rothvoß 

2008. IEEE Real-Time Systems Symposium (RTSS), Barcelona, Nov. 30-3 Dec., 2008. p. 397-406. DOI : 10.1109/RTSS.2008.25.

A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation

F. Eisenbrand; T. Rothvoß 

2008. Automata, Languages and Programming, 35th International Colloquium (ICALP 2008), Reykjavik, Iceland, July 7-11, 2008.

Mapping task-graphs on distributed ECU networks: Efficient algorithms for feasibility and optimality

W. Damm; A. Metzner; F. Eisenbrand; G. Shmonin; R. Wilhelm et al. 

2006.  p. 87-90. DOI : 10.1109/RTCSA.2006.42|.