TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 08071

Scheduling

( Feb 10 – Feb 15, 2008 )


Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/08071

Organizers

Contact


Impacts

Summary

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.


Participants
  • 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 G. 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)

Classification
  • optimization / scheduling

Keywords
  • Scheduling
  • Real-time
  • Supply chain