Scheduling a Scheduling Competition

SSC@ICAPS'07

 Overview 

 Topics of Interest 

 Download CfP 

 Format 

 Submissions 

 Important Dates 

 Accepted Papers 

 Program 

 Organisation 

Overview

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 research 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.

Why Now?   Many fields have benefited from the organization of a competition. The international competitions in planning (IPC), SAT and QBF, knowledge engineering for planning and scheduling (ICKEPS), as well as more distant domains such as robotics (RoboCup) have fostered measurable advancements in their respective fields. Whether this will be the case in scheduling remains to be seen, although it is likely that a competitive approach to evaluation in a field as fragmented as scheduling could greatly foster cross-fertilization and synergy among researchers with different backgrounds. In addition to the generic benefits a competition can bring to the scientific community, the event can also help to further bridge the gap between theory and practice in scheduling by introducing benchmarks that are grounded on application problems posed by industry. The feasibility of this applications focus stems from the already strong bias in some areas of scheduling towards industrial problems. 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. Specifically, the aim of the discussion is to:

• collectively discuss 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;
• assess the feasibility of a common evaluation framework for different scheduling approaches;
• identify common features of problems and algorithms which derive from traditionally different scheduling contexts.

[ Back to top ]

Download CfP

Download the Call for Papers [PDF].

[ Back to top ]

Topics of Interest

This workshop will strive to establish the feasibility as well as the key issues concerning the establishment of a scheduling competition at the ICAPS venue. We will invite contributions and encourage discussion on topics related to the theoretical, organizational and practical challenges entailed by a scheduling competition. These include, but are not limited to, the following.

• Classification of scheduling problems, categorization of scheduling algorithms, and proposals for tracks.
• Metrics and benchmarks for evaluating scheduling techniques.
• Domains/problems suited for competition evaluation.
• Knowledge representation for scheduling and the need (or not) for a common reference problem formalism.
• Computational aspects of benchmarking for scheduling.
• Lessons learned and ideas from other competitions (e.g., IPC, SAT, QBF and ICKEPS competitions).

[ Back to top ]

Format

The workshop is oriented towards accepting papers that are strongly projected towards concrete proposals for realizing the scheduling competition. The workshop will be structured to allow ample time for discussion and interaction. The workshop will last one full day, with an agenda including the following:

• An invited talk from a senior member of the scheduling community, intended to give a cross-area perspective on competition criteria.
• Selected papers accepted by the program committee will be presented in short sessions (2-3 papers) on a common theme.
• To foster interaction and comparisons, a member of the PC will be assigned to each theme and provide a brief commentary at the end of the workshop on the collection of contributions pertaining to that theme.

[ Back to top ]

Submission Information

We welcome original papers which bring forth and motivate proposals for the operational implementation of the competition, including but not limited to the topics listed above. We particularly welcome papers which provide a cross-area perspective. Participants are requested to submit one of the following:

• Full Paper - Technical papers addressing one or more of the workshop topics indicated above. Full papers can be up to 8 pages in length.
• Position Paper - Shorter papers which bring forth strong but not yet fully developed ideas related to the topics above. Position papers can be up to 4 pages in length.
• Statement of Interest - Although first preference will be given to full and position paper submissions, we anticipate room for a restricted number of additional attendees and request that these individuals contribute with a one-page statement of interest.

Accepted full papers will appear in the workshop proceedings. One desired outcome of the workshop is to produce a special issue on a major journal focusing on the fundamental issues related to implementing a scheduling competition. Authors of accepted papers will be invited to submit expanded versions of their workshop papers for consideration in this special issue.

Authors are encouraged to submit papers electronically in postscript or PDF format. Papers should be formatted using the ICAPS conference style (see ICAPS '07 conference call).

Please send your submissions by email to ssc07@istc.cnr.it no later than June 15th, 2007 using the subject line "SSC-07 Workshop Submission". Confidentiality of submissions will be maintained during the review process. All submitted materials for rejected papers will be kept confidential in perpetuity. All submitted materials for accepted papers will be kept confidential until the date of the workshop, September 22nd, 2007. Submissions should not include information that will be confidential or proprietary at the time of publication.

[ Back to top ]

Important Dates

The schedule of important dates for the workshop is as follows:

[ Back to top ]

Accepted Papers

• L. V. Barbulescu, L. A. Kramer, and S. F. Smith. Benchmark Problems for Oversubscribed Scheduling
• M. Benedetti, F. Pecora, and N. Policella. Anatomy of a Scheduling Competition
• M. S. Boddy. Position Paper: Designing a Scheduling Competition
• A. Cesta, N. Policella, and R. Rasconi. Analysis of a Benchmark Generator for the Reactive Scheduling Problem
• V. A. Cicirello. The Challenge of Sequence-Dependent Setups: Proposal for a Scheduling Competition Track on One Machine Sequencing Problems
• L. Di Gaspero, A. Schaerf, and B. McCollum. The Second International Timetabling Competition (ITC-2007): Curriculum-based Course Timetabling (Track 3)
• C. Ghersi, L. Pulina, and A. Tacchella. Which system should I buy? A case study about the QBF solvers competition
• A. Guerri, M. Lombardi, and M. Milano. Challenging Scheduling Problem in the field of System Design
• C. Le Pape. A Test Bed for Manufacturing Planning and Scheduling: Discussion of Design Principles
• S. Petrovic. Towards the Benchmarks for Scheduling Problems
• E. Romero and M. Oglietti. Space Operations as a Guide for a Real-World Scheduling Competition
• M. Sarkarati, N. Policella, A. Wolf, and K. Brieß. Planning the Operations of the Scientific Instruments of a Spacecraft on a Planetary Mission
• T. Walsh. Designing a Scheduling Competition
• T. Zimmerman. What Good is a Scheduling Competition? Insights from the IPC

[ Back to top ]

Workshop program

Download the PDF version. The presentations (PPT or PDF) are linked in the program below.

Session A Chair: C. Beck

Sesison B Chair: R. Bartak

Panel and discussion

Following the ICAPS model, which is implementing the session commentator mechanism this year, the workshop includes a 10 minute wrap-up at the end of the two paper presentation sessions. The session chair will pinpoint the aspects of the talks that are most relevant for the scheduling competition theme of the workshop, and reiterate them during the short wrap-up.

In addition, we have also reserved the last session of the workshop for discussion. Specifically, this session includes a one hour panel discussion, and concludes with an open discussion on "what to do next". The panel will be driven by a few questions addressing the fundamental issues related to designing and implementing a scheduling competition.

The workshop will also include two invited contributions: a long talk in the first session by prof. J. Hooker (Tepper School of Business, CMU) on the empirical evaluation of algorithms, and a short invited speech by prof. P. van Hentenryck (Brown University) on challenges for the scheduling competition.

[ Back to top ]

Organization

Workshop Chairs

• Federico Pecora (ISTC-CNR)
• Nicola Policella (ESA, European Space Agency)

Programme Committee

• 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à of Genova)
• Claude Le Pape (ILOG S.A.)
• Sanja Petrovic (University of Nottingham)
• David E. Smith (NASA Ames Research Center)
• Stephen F. Smith (Carnegie Mellon University)
• Pascal van Hentenryck (Brown University)

[ Back to top ]