Dagstuhl Seminar 08071
Scheduling
( Feb 10 – Feb 15, 2008 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/08071
Organizers
- Jane W. S. Liu (Academica Sinica - Taipei, TW)
- Rolf H. Möhring (TU Berlin, DE)
- Kirk Pruhs (University of Pittsburgh, US)
Contact
- Annette Beyer (for administrative matters)
Impacts
- A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling : article pp. 210-221 - Bonifaci, Vincenzo; Marchetti-Spaccamela, Alberto; Stiller, Sebastian - Berlin : Springer, 2008 - (Lecture notes in computer science : 5193 ; pp. 210-221). DOI: 10.1007/978-3-540-87744-8_18.
- A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation : article pp. 246-257 - Eisenbrand, Friedrich; Rothvoß, Thomas - Berlin : Springer, 2008 - (Lecture notes in computer science : 5125 : article : pp. 246-257). ISBN: 978-3-540-70574-1. DOI: 10.1007/978-3-540-70575-8.
- Algorithms and Complexity for Periodic Real-Time Scheduling : article : ACM-SIAM Symposium on Discrete Algorithms (SODA10): pp. 1350 - 1359 - Bonifaci, Vincenzo; Chan, Ho-Leung; Marchetti Spaccamela, Alberto; Megow, Nicole - Philadelphia : SIAM, 2010 - (ACM-SIAM Symposium on Discrete Algorithms : SODA10 : pp. 1350 - 1359).
- An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling : article pp. 432-443 - Karrenbauer, Andreas; Rothvoß, Thomas - Berlin : Springer, 2008 - (Lecture notes in computer science ; 5757 : article : pp. 432-443). ISBN: 978-3-642-04127-3. DOI: 10.1007/978-3-642-04128-0_39.
- EDF-schedulability of synchronous periodic task systems is coNP-hard : article : pp. 1029-1034 - Eisenbrand, Friedrich; Rothvoß, Thomas - New York : ACM, 2010 - (SODA '10 Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms ; pp. 1029-1034).
- Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems : article : pp. 230-241 - Bonifaci, Vincenzo; Marchetti-Spaccamela, Alberto - Berlin : Springer, 2010 - (Lecture notes in computer science : 6347 ; pp. 230-241). DOI: 10.1007/978-3-642-15781-3_20.
- Implementation of a Speedup-Optimal Global EDF Schedulability Test : article pp. 259-268 - Baruah, Sanjoy K.; Bonifaci, Vincenzo; Marchetti Spaccamela, Alberto; Stiller, Sebastian - Los Alamitos : IEEE, 2009 - (2009 21st Euromicro Conference on Real-Time Systems ; pp. 259-268).
- Open problems in real-time scheduling : article : S. 577-582 - Baruah, Sanjoy K.; Pruhs, Kirk R. - Berlin : Springer, 2010 - (Journal of Scheduling : 13. 2010, 6). DOI: 10.1007/s10951-009-0137-5.
- Scheduling Periodic Tasks in a Hard Real-Time Environment : article pp. 299-311 - Eisenbrand, Friedrich; Hähnle, Reiner; Niemeier, Martin; Skutella, Martin; Verschae, Jose; Wiese, Andreas - Berlin : Springer, 2010 - (Lecture notes in computer science : 6198 ; pp. 299-311). DOI: 10.1007/978-3-642-14165-2_26.
- Scheduling Real-Time Mixed-Criticality Jobs : article pp. 90-101 - Baruah, Sanjoy K.; Bonifaci, Vincenzo; D'Angelov, Gianlorenzo; Megow, Haohan; Stougie, Leen - Berlin : Springer, 2010 - (Lecture notes in computer science : 6281 ; pp. 90-101). DOI: 10.1007/978-3-642-15155-2_10.
- Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods : article pp. 11-22 - Eisenbrand, Friedrich; Kesavan, Karthikeyan; Mattikalli, Raju S.; Niemeier, Martin; Nordsieck, Arnold W.; Skutella, Martin; Verschae, Jose; Wiese, Andreas - Berlin : Springer, 2010 - (Lecture notes in computer science : 6346 ; pp. 11-22). DOI: 10.1007/978-3-642-15775-2_2.
- Static-Priority Real-Time Scheduling : Response Time Computation Is NP-Hard : article pp. 397-406 - Eisenbrand, Friedrich; Rothvoß, Thomas - Los Alamitos : IEEE, 2008 - (RTSS 2008 Real-Time Systems Symposium ; pp. 397-406).
Scheduling is a form of decision making that involves allocating scarce resources to achieve some objective. The study of scheduling dates back to at least the 1950’s when operations research researchers studied problems of managing activities in a workshop. Computer systems researchers started studying scheduling in the 1960’s in the development of operating systems and time-critical applications.
Several of these scheduling problems proved to be closed linked to fundamental concepts in theoretical computer science (such as approximability, intractability, and NP-completeness), thereby attracting the attention of theoretical computer scientists as well. Today, scheduling is widely studied as parts of the disciplines of mathematical programming and operations research; algorithmics and theoretical computer science; and computer systems, particularly real-time and embedded systems. The specific scarce resources, as well as the objectives to be optimized, differ in the different disciplines; nevertheless, there are remarkable similarities (as well as significant differences) in the general framework adopted by researchers in scheduling theory in these disparate disciplines.
The primary objectives of the seminar were to bring together leading and promising young researchers in the different communities to discuss scheduling problems that arise in current and future technology; to expose each community to the important problems addressed by the other communities; and to facilitate a transfer of solution techniques from each community to the others.
There were approximately fifty participants at the seminar, approximately evenly split between the three areas. The first morning consisted of three introductory talks by Ted Baker on real-time scheduling, Andreas Schulz on mathematical programming techniques and by Nikhil Bansal on online scheduling. During the the first afternoon each participant gave a short talk about their research interests. The participants were then broken up into about ten clusters, of six people each, by the organizers based on research interests. Some of the clusters were:
- Game Theoretic Scheduling: This research line consider situations each user is motivated to try to optimize the performance for this users task. So for example, the user might not truthfully state the resources required by his/her task. The general goal is to study the effect of such selfish behavior and to design mechanisms to align players incentives with the global good.
- Stochastic Scheduling: This research line assumes that only probabilistic information is known about the resource requirements for a job. The goal is to try to find schedules that are good in expectation.
- Power Aware Scheduling: Modern processors can change their speed as a way of managing power. This research line focuses on designing speed changing policies that will be the most effective.
- Periodic Scheduling: This line of research is distinguished by the fact that jobs much be executed periodically over along period of time. Periodic scheduling occurs frequently in real-time applications. The resulting scheduling problems are notoriously difficult.
These clusters meet periodically through the week to discuss research problems, and to organize talks from within the cluster. The clusters organized 32 medium length talks on various recent research results. There was a plenary session on Thursday afternoon to discuss interesting directions for future research and future collaborations.
This seminar was essentially a first meeting of the real-time community with the operations research and theoretical computer science community. The general consensus was that both communities learned a lot about the other communities. And at least some collaborations between the communities were born from this seminar.
- James H. Anderson (University of North Carolina at Chapel Hill, US) [dblp]
- Theodore P. Baker (Florida State University, US)
- Nikhil Bansal (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
- Sanjoy Baruah (University of North Carolina at Chapel Hill, US) [dblp]
- Enrico Bini (Scuola Superiore Sant'Anna - Pisa, IT) [dblp]
- Alan Burns (University of York, GB) [dblp]
- Marco Caccamo (University of Illinois - Urbana-Champaign, US)
- Marek Chrobak (University of California - Riverside, US) [dblp]
- José R. Correa (University of Chile - Santiago de Chile, CL) [dblp]
- Liliana Cucu-Grosjean (INRIA - Nancy, FR) [dblp]
- Christoph Dürr (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Friedrich Eisenbrand (EPFL - Lausanne, CH) [dblp]
- Thomas Erlebach (University of Leicester, GB) [dblp]
- Gerhard Fohler (TU Kaiserslautern, DE) [dblp]
- Hans Hansson (Mälardalen University - Västerås, SE)
- Wiebke Höhn (TU Berlin, DE) [dblp]
- Han Hoogeveen (Utrecht University, NL)
- Klaus Jansen (Universität Kiel, DE) [dblp]
- Chang-Gun Lee (Seoul National University, KR)
- Insup Lee (University of Pennsylvania - Philadelphia, US) [dblp]
- Jan Karel Lenstra (CWI - Amsterdam, NL)
- Jane W. S. Liu (Academica Sinica - Taipei, TW)
- Alberto Marchetti-Spaccamela (University of Rome "La Sapienza", IT) [dblp]
- Monaldo Mastrolilli (IDSIA - Manno, CH) [dblp]
- Nicole Megow (MPI für Informatik - Saarbrücken, DE) [dblp]
- Rolf H. Möhring (TU Berlin, DE) [dblp]
- Britta Peis (TU Berlin, DE) [dblp]
- Christopher Potts (University of Southampton, GB) [dblp]
- Kirk Pruhs (University of Pittsburgh, US) [dblp]
- Maurice Queyranne (University of British Columbia - Vancouver, CA)
- Julien Robert (ENS - Lyon, FR)
- Thomas Rothvoss (EPFL - Lausanne, CH) [dblp]
- Guido Schäfer (CWI - Amsterdam, NL) [dblp]
- Andreas S. Schulz (MIT - Camridge, US)
- Jens Schulz (TU Berlin, DE)
- Uwe Schwiegelshohn (TU Dortmund, DE) [dblp]
- Jiri Sgall (Charles University - Prague, CZ) [dblp]
- Chi-Sheng Shih (National Taiwan University, TW)
- Martin Skutella (TU Berlin, DE) [dblp]
- Francis Sourd (UPMC - Paris, FR)
- Alexander Souza (HU Berlin, DE)
- Frits C. R. Spieksma (KU Leuven, BE) [dblp]
- Clifford Stein (Columbia University, US) [dblp]
- Marc Uetz (University of Twente, NL) [dblp]
- Steef van de Velde (Erasmus University - Rotterdam, NL)
- Rob van Stee (MPI für Informatik - Saarbrücken, DE) [dblp]
- Tjark Vredeveld (Maastricht University, NL) [dblp]
- Joel Wein (Polytechnic Institute of NYU - Brooklyn, US)
- Matthias Westermann (RWTH Aachen, DE)
- Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
- Prudence W. H. Wong (University of Liverpool, GB) [dblp]
Related Seminars
- Dagstuhl Seminar 10071: Scheduling (2010-02-14 - 2010-02-19) (Details)
- Dagstuhl Seminar 13111: Scheduling (2013-03-10 - 2013-03-15) (Details)
- Dagstuhl Seminar 16081: Scheduling (2016-02-21 - 2016-02-26) (Details)
- Dagstuhl Seminar 18101: Scheduling (2018-03-04 - 2018-03-09) (Details)
- Dagstuhl Seminar 20081: Scheduling (2020-02-16 - 2020-02-21) (Details)
- Dagstuhl Seminar 23061: Scheduling (2023-02-05 - 2023-02-10) (Details)
- Dagstuhl Seminar 25121: Scheduling (2025-03-16 - 2025-03-21) (Details)
Classification
- optimization / scheduling
Keywords
- Scheduling
- Real-time
- Supply chain
