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. p. 11-22. DOI : 10.1007/978-3-642-15775-2_2. 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. DOI : 10.1007/978-3-642-14165-2_26. 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. p. 246-257. DOI : 10.1007/978-3-540-70575-8_21.
