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.

Selected Publications

[6]
F. Eisenbrand; K. Kesavan; R. Mattikalli; M. Niemeier; A. Nordsieck et al. : Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods. 2010. 18th Annual European Symposium on Algorithms (ESA2010), Liverpool, United Kingdom, September 6-8, 2010.
[5]
F. Eisenbrand; N. Hähnle; M. Niemeier; M. Skutella; J. Verschae et al. : Scheduling periodic tasks in a hard real-time environment. 2010. 37th International Colloquium on Automata, Languages and Programming (ICALP2010), Bordeaux, France, July 5-10, 2010. p. 299-311.
[4]
R. Davis; T. Rothvoß; S. Baruah; A. Burns : Exact quantification of the sub-optimality of uniprocessor fixed-priority pre- emptive scheduling; Real-Time Systems. 2009. DOI : 10.1007/s11241-009-9079-4.
[3]
F. Eisenbrand; T. Rothvoß : Static-priority Real-time Scheduling: Response Time Computation is NP-hard. 2008. IEEE Real-Time Systems Symposium (RTSS), Barcelona, Nov. 30-3 Dec., 2008. p. 397-406. DOI : 10.1109/RTSS.2008.25.
[2]
F. Eisenbrand; T. Rothvoß : A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation. 2008. Automata, Languages and Programming, 35th International Colloquium (ICALP 2008), Reykjavik, Iceland, July 7-11, 2008.
[1]
W. Damm; A. Metzner; F. Eisenbrand; G. Shmonin; R. Wilhelm et al. : Mapping task-graphs on distributed ECU networks: Efficient algorithms for feasibility and optimality. 2006. p. 87 - 90. DOI : 10.1109/RTCSA.2006.42|.