Scheduling

Summary

Scheduling is a form of decision making that involves allocating scarce resources over time to achieve some objective. The primary objectives of this seminar were to bring together leading researchers working on scheduling problems in three different research communities – operations research, theoretical computer science, and real-time systems – to expose each community to the important problems addressed by the other communities; to enable and encourage cooperation among the researchers; and to facilitate a transfer of solution techniques from each community to the others. This is the second Dagstuhl seminar organized to further these objectives (the first – Dagstuhl Seminar 08071 – was held two years ago, in February 2008).

There were approximately sixty participants at the seminar, roughly evenly split between the three communities. Several of these participants had also attended the previous seminar. There was one common session each morning and one each afternoon of the seminar. During the first morning, there were presentations describing some of the research outcomes of the previous scheduling seminar. These presentations highlighted the success of the previous seminar in fostering collaborations between the communities. These talks also provided succinct snapshots of the remaining open problems in the domains addressed in these projects. The remaining sessions mostly consisted of one tutorial/survey talk presenting a line of research or a solution technique of a particular community in a manner that is accessible to researchers from the other communities, and many open problem talks, in which multiple short (5-10 minute) presentations that invited collaboration with the speaker on one of his/her favorite open problems. Write-ups of these open problems were collected and published.

Several clusters of seminar participants formed around common research interests. Ample time was built into the schedule to enable these clusters to meet multiple times to get to know each other better, to work on problems together, and to develop plans for continuing some of these collaborations after the seminar. We expect that, as happened in the last seminar, that several successful collaborations will have been formed that result in publications in prestigious conferences and journals.

In essence, this seminar continued the process initiated in Seminar#08071, of getting the real-time systems community on the one hand, and the operations research and theoretical CS communities on the other, better acquainted with each others’ formal models, interesting problems, and solution techniques. We consider these objectives to have largely been met.