May 31 – June 4 , 2004, Dagstuhl Seminar 04231

Scheduling in Computer and Manufacturing Systems


Jacek Blazewicz (Poznan University of Technology, PL)
Klaus Ecker (TU Clausthal, DE)
Erwin Pesch (Universität Siegen, DE)
Denis Trystram (INRIA Grenoble Rhône-Alpes, FR)

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants
Dagstuhl's Impact: Documents available


The objective of the seminar was to provide a forum for the discussion of ongoing research in scheduling. The seminar promoted an exchange of ideas covering the entire spectrum from case studies of real applications to recent advances in mathematical foundations. The various aspects of scheduling were covered by 39 lectures that addressed classical application areas such as distributed processing, operating systems, dependable systems, and flexible manufacturing. It is worth pointing out that many lectures were motivated by practical considerations, as for example machine break-downs, batch scheduling, synchronous production, robotic cell scheduling, real-time scheduling, and resource investment problems. But also exciting new areas emerged such as those in modern communications systems, examples being wireless networks, multimedia networks, and the internet.

The seminar proceeded along three broad fronts: applications, which include empirical studies of existing systems as well as numerical studies of the analysis and simulation of system models. Most of the application studies came from the area of production scheduling and planning, such as just-in-time scheduling, due date assignment and project control, including special problems dealing with machine break-downs, robotic cells, assembly scheduling, load balancing, minimizing the number of workers (human resources). Other presentations considered special problems from chemistry and oceanography, the design of schedulers, e.g. for web applications, and planning examination sessions. Algorithms were presented for various problems such as batch scheduling, resource scheduling, tardiness problems, shop problems, deadline and due date scheduling, real-time scheduling, on-line scheduling, single machine problems, time lags, scheduling with communication delays. The main concern in these presentations was the design and analysis of algorithms ranging from simple and tractable on-line and greedy rules to methods based on semi-enumerative approaches, branch and bound, local neighborhood search, and LP formulations. New theoretical developments included recent results in the analysis of new and classical problems under novel (or multiple) criteria, dealing with particular assumptions on machines, tasks (e.g., release dates, precedence constraints, communication delays, multiprocessor tasks, bi-processor tasks), and other problems such as assembly scheduling problems and on-line scheduling. Typical questions discussed were the structure of problems and their relation to graph theory, complexity of problems including polynomial solvability, the design of algorithms and performance analysis, and the approximability of optimal solutions.

The participants were delighted with the outstanding local organization and the marvelous facilities that created the atmosphere for a successful seminar.

Dagstuhl Seminar Series


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

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.


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