DFG Algorithms for Complex Scheduling Problems

Project director: Prof. Dr. Rolf H. Möhring
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - 314 24594
e-mail: rolf.moehring [at] tu-berlin.de
Researcher: Wiebke Höhn
email: hoehn [at] math.tu-berlin.de
For address, see above.
Support: Deutsche Forschungsgemeinschaft (DFG)
within Priority Programme 1307 "Algorithm Engineering"

Project Overview

Real-world scheduling problems are usually much more complex than most of the models that were considered in algorithm theory so far. Typically, optimal solutions cannot be found in reasonable computing time. However in practice, good solutions have to be computed fast. To meet the runtime requirements, mostly (simple) heuristics are established in industry, not taking into account results and techniques that are know for related theoretical problems. We aim to start filling this gap between theory and practice for the following fields of scheduling:

Integrated Sequencing and Scheduling,
a class of problems typically arising in production planning: For a given set of goods, a minimum cost processing sequence has to determined. The cost of a sequence highly depends on the corresponding (non-trivial) scheduling decisions taken, e.g. the scheduling of setup work.

© www.eia.doe.gov
Turnaround Scheduling,
a field of scheduling problems which result from shutting down industrial plants for maintenance. These problems are characterized by time-cost tradeoff, precedence constraints, hiring external resources, resource leveling, different working shifts, and risk analysis.

We seek for insights into the structure and complexity of these problems, which then need to be transferred into efficient algorithms, aiming to produce provably good solutions also for large real-world problems within an appropriate computing time. Realistic data is available from cooperations with T.A. Cook Consultants, Berlin, PSI Business Technology and Salzgitter Flachstahl GmbH, and Sachsenmilch AG, respectively (10.000 - 100.000 activities for turnaround scheduling, and two examples from sequencing and scheduling, one from coil coating with 20-40 coils, and another one from dairy industry with 30-40 jobs).

Additionally, results in machine scheduling can be found here.


[P1] Torsten Gellert, Wiebke Höhn, and Rolf H. Möhring.
Sequencing and Scheduling for Filling Lines in Dairy Production.
Optimization Letters (Special Issue of SEA 2011), to appear.
[P2] Elisabeth Günther, Felix G. König, and Nicole Megow.
Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width.
In Proceedings of the 7th International Workshop on Approximation and Online Algorithms (WAOA '09), p. 170-181, Lecture Notes in Computer Science, Vol. 5893, 2010.
[P3] Elisabeth Günther, Felix G. König, and Nicole Megow.
The Bin Scheduling Problem.
In Proceedings of 9th Workshop on Models and Algorithms for Planning and Scheduling (MAPSP 2009), Abbey Rolduc, Netherlands, June 29 - July 3, 2009.
[P4] Wiebke Höhn, Tobias Jacobs, and Nicole Megow.
On Eulerian Extensions and their Application to No-wait Flowshop Scheduling.
Journal of Scheduling, to appear. (Corresponding Tech-Report 008-2009)
[P5] Wiebke Höhn and Tobias Jacobs.
Single Machine Scheduling with Weighted Nonlinear Cost.
Tech-Report 008-2011. Submitted.
[P6] Wiebke Höhn, Felix G. König, Marco E. Lübbecke and Rolf H. Möhring.
Integrated Sequencing and Scheduling in Coil Coating.
Management Science 57(4), pp. 647-666, 2011. (Available as Tech-Report 001-2009)
[P7] Nicole Megow, Rolf H. Möhring, and Jens Schulz.
Turnaround Scheduling in Chemical Manufacturing.
In Proceedings of 8th Workshop on Models and Algorithms for Planning and Scheduling (MAPSP 2007), Istanbul, Turkey, July 2-6, 2007. [pdf]
[P8] Nicole Megow, Rolf H. Möhring, and Jens Schulz.
Decision Support and Optimization in Shutdown and Turnaround Scheduling.
INFORMS Journal on Computing 23, pp. 189-204, 2011. (Available as Tech-Report 009-2009)