31. Mai – 04. Juni 2004, Dagstuhl Seminar 04231
Scheduling in Computer and Manufacturing Systems
Auskunft zu diesem Dagstuhl Seminar erteilt
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
- 02231: "Scheduling in Computer and Manufacturing Systems" (2002)
- 99431: "Scheduling in Computer and Manufacturing Systems" (1999)
- 9723: "Scheduling in Computer & Manufacturing Systems" (1997)
- 9520: "Scheduling in Computer & Manufacturing Systems" (1995)