W4. Scheduling a Scheduling Competition

List of Papers


Nicola Policella, European Space Agency (ESA)
Federico Pecora, Institute for Cognitive Science and Technology (ISTC-CNR)


Scheduling is an important capability for managing many real-world applicative contexts, such as manufacturing, engineering and resource management in general. Research in automated scheduling has led to a large number of support tools, which have had a major impact on productivity and cost-effectiveness of various processes. Automated scheduling tools greatly out-perform manual scheduling approaches. The different contexts within which such technology has been deployed have fostered specific research in a variety of fields.

The broad range of application areas that have inspired research in scheduling is reflected in the equally wide range of distinct approaches and research communities working in the area. This work conceals distinct problems, some of which are related, and others which are rather different in nature. The reality is that scheduling is made up of a fragmented array of research communities, from widely different backgrounds, all of whom focus on proposing efficient algorithmic solutions for solving scheduling-related combinatorial optimization problems. Distinct research in fields such as AI and OR has led to a rich portfolio of approaches, such as constraint programming or integer linear programming techniques.

This workshop attempts to understand if and how it is possible to compare such approaches in a common competition, to be held regularly at the ICAPS venue. Given the heterogeneous nature of scheduling, the premises for a successful competition need to be discussed and agreed upon by a critical mass of researchers in these distinct fields. The composition of this workshop's Program Committee reflects the multi-disciplinary nature of scheduling, as do the topics covered by the accepted papers.

Specifically, the papers focus on topics that include categorization of scheduling problems and algorithms, proposals for tracks, metrics and benchmarks for evaluating scheduling techniques, real-world application scenarios for possible inclusion in the competition, and knowledge representation for scheduling. Also, a number of papers put forth lessons learned and ideas from other relevant computer science competitions. The contributions to the workshop constitute a sound basis for collectively discussing the prospect of a scheduling competition in terms of its potential benefits to the research community on one hand, and to industry on the other. With this material, we hope to establish a fruitful and constructive discussion leading to the implementation of a regular scheduling competition.

We look forward to seeing you in Providence!


Roman Bartak, Charles University
Chris Beck, University of Toronto
Peter Brucker, Universität Osnabrück
Amedeo Cesta, ISTC-CNR
Erik Demeulemeester, K.U. Leuven
Enrico Giunchiglia, Università di Genova
Claude Le Pape, ILOG
Sanja Petrovic, University of Nottingham
David E. Smith, NASA Ames Research Center
Stephen F. Smith, Carnegie Mellon University
Pascal van Hentenryck, Brown University

List of Papers

L. V. Barbulescu, L. A. Kramer, and S. F. Smith

M. Benedetti, F. Pecora, and N. Policella

M. S. Boddy

A. Cesta, N. Policella, and R. Rasconi

V. A. Cicirello

L. Di Gaspero, A. Schaerf, and B. McCollum

C. Ghersi, L. Pulina, and A. Tacchella

A. Guerri, M. Lombardi, and M. Milano

C. Le Pape

S. Petrovic

E. Romero and M. Oglietti

M. Sarkarati, N. Policella, A. Wolf, and K. Brieß

T. Walsh

T. Zimmerman

Ome © Marjorie Mikasen 2005