https://www.dagstuhl.de/20081

February 16 – 21 , 2020, Dagstuhl Seminar 20081

Scheduling

Organizers

Nicole Megow (Universität Bremen, DE)
David Shmoys (Cornell University – Ithaca, US)
Ola Svensson (EPFL – Lausanne, CH)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 10, Issue 2 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl Seminar Schedule [pdf]

Summary

This seminar was the sixth in a series of Dagstuhl "Scheduling" seminars (since 2008). Scheduling is a major research field that is studied from a practical and theoretical perspective in computer science, mathematical optimization, and operations research. Applications range from traditional production scheduling and project planning to the newly arising resource management tasks in the advent of internet technology and shared resources.

This edition of the seminar focused on the interplay between scheduling problems and problems that arise in the management of traffic. There are several notable aspects of the scheduling problems that arise particularly in this context:

  • the role of dynamic decision-making in which data-driven approaches emerge (especially those that have stochastic elements in modelling multi-stage decision-making);
  • the interplay between scheduling aspects and what might be viewed as routing aspects, providing a spacial component to the nature of the scheduling problem;
  • the tension between questions of coordination and competition that arise from the fact that, for many of the issues in this domain, there are significant questions that depend on the extent to which the traffic can be centrally coordinated.

Since the community working on the intersection of scheduling and traffic is itself rather broad, the seminar focused on researchers whose methodological focus relies on tools from the theoretical design of algorithms, on mathematical optimization methods, and on the combination of optimization and game-theoretic approaches.

Organization of the Seminar. The workshop brought together $59$ researchers from theoretical computer science, mathematical optimization and operations research. The participants consisted of both senior and junior researchers, including a number of postdocs and advanced PhD students.

During the five days of the workshop, 31 talks of different lengths took place. Four keynote speakers gave an overview of the state-of-the art of the respective area in 60 minutes:

  • Shuchi Chawla: Mechanisms for resource allocation
  • Benjamin Moseley: Combinatorial Optimization Augmented with Machine Learning
  • Éva Tardos: Learning in Games and in Queueing Systems
  • Vera Traub: Approximation algorithms for traveling salesman problems.

The remaining slots were filled with shorter talks of $30$ minutes on various topics related to scheduling, routing, transportation, mechanism design, learning, and applications in practice. Another highlight of the workshop was a historical note given by Jan Karel Lenstra with his view on the dynamic development of the area of scheduling in the past 60 years. Further, in the beginning of the week, open problem sessions were held. Throughout the week, a few sessions with spotlight talks of $8$ minutes gave participants the chance to announce recent results and invite for discussions. The schedule left ample free time that was actively used for fruitful discussions and joint research.

Outcome. Organizers and participants regard the workshop as a great success. The workshop achieved the goal to bring together the related communities, share the state-of-the art research and discuss the current major challenges. The talks were excellent and very stimulating; participants actively met in working groups in the afternoon and evenings. It was remarked very positively that a significant number of younger researchers (postdocs and PhD students) participated and integrated very well.

The organizers wish to express their gratitude towards the Scientific Directorate and the administration of the Dagstuhl Center for their great support for this workshop.

Summary text license
  Creative Commons BY 3.0 Unported license
  Nicole Megow, David Shmoys, and Ola Svensson

Dagstuhl Seminar Series

Classification

  • Optimization / Scheduling

Keywords

  • Scheduling
  • Traffic
  • Routing
  • Approximation algorithms
  • Mechanism design

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.