direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Algorithms for Complex Scheduling Problems

Lupe [1]
© DFG
Project director:
Prof. Dr. Rolf H. Möhring [2]
Researcher:
Wiebke Höhn [3]
Associated researchers:
Torsten Gellert [4]
Felix G. König [5]
Dr. Marco E. Lübbecke [6]
Jens Schulz [7]
Support:
DFG Priority Programme 1307 "Algorithm Engineering" [8]
Since:
2007

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:

Lupe [9]
© COGA

Integrated Sequencing and Scheduling [10],  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.

Lupe [11]
© COGA

Basis Sequencing [12]  aims for a minimum cost sequence of a set of given items. In contrast to the previous problem class, the cost incurred by an item solely depends on the neighboring items or on the item's completion time. Basic sequencing problems often occur as a subproblem in integrated sequencing and scheduling, and hence, insights on these problems are of great value.

Lupe [13]
© eia.doe.gov

Turnaround Scheduling [14],  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, PSI Metals and Salzgitter Flachstahl, and Sachsenmilch, 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).

Lupe [15]
© DFG

Also within this project:

DFG Science TV  (English) [16]

DFG Science TV  (German) [17]

Publications

Günther, Elisabeth and König, Felix G. and Megow, Nicole
Scheduling and Packing Malleable and Parallel Tasks with Precedence Constraints of Bounded Width [18].
Journal of Combinatorial Optimization, Vol. 27, pp. 164-181, 2014.  [pdf] [19]

Höhn, Wiebke and Jacobs, Tobias and Megow, Nicole
On Eulerian extensions and their application to no-wait flowshop scheduling [20].
Journal of Scheduling, Vol. 15, pp. 295-309, 2012.  [pdf] [21]

Höhn, Wiebke and Jacobs, Tobias
An experimental and analytical study of order constraints for single machine scheduling with quadratic cost [22].
In Proc. of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 103-117, SIAM, 2012.  [pdf] [23]

Höhn, Wiebke and Jacobs, Tobias
On the performance of Smith's rule in single-machine scheduling with nonlinear cost [24].
In Proc. of the 10th Latin American Theoretical Informatics Symposium (LATIN), LNCS, Vol. 7256, pp. 482-493, Springer, 2012.  [pdf] [25]

Megow, Nicole and Möhring, Rolf H. and Schulz, Jens
Decision Support and Optimization in Shutdown and Turnaround Scheduling [26].
INFORMS J. on Computing, Vol. 23, pp. 189–204, 2011.  [pdf] [27]

Gellert, Torsten and Höhn, Wiebke and Möhring, Rolf H.
Sequencing and scheduling for filling lines in dairy production [28].
Optimization Letters, Vol. 5, pp. 491–504, 2011.
Special issue of SEA 2011.

Höhn, Wiebke and König, Felix G. and Lübbecke, Marco E. and Möhring, Rolf H.
Integrated Sequencing and Scheduling in Coil Coating [29].
Management Science, Vol. 57, pp. 647–666, 2011.
Finalist for the EURO Excellence in Practice Award 2009.  [pdf] [30]

Günther, Elisabeth and König, Felix G. and Megow, Nicole
Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width [31].
In Approximation and Online Algorithms: 7th International Workshop, WAOA 2009, Lecture Notes in Computer Science, Vol. 5893, pp. 170-181, Springer, 2010.  [pdf] [32]

Günther, Elisabeth and König, Felix G. and Megow, Nicole
The Bin Scheduling Problem [33].
In Proceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2009), 2009.  [pdf] [34]

Megow, Nicole and Möhring, Rolf H. and Schulz, Jens
Turnaround Scheduling in Chemical Manufacturing [35].
In Proceedings of the 8th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2007), 2007.

------ Links: ------

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

Copyright TU Berlin 2008