Algorithms for Complex Scheduling Problems


Prof. Dr. Rolf H. Möhring; Technische Universität Berlin


Project website


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 fill this gap between theory and practice, considering the following fields of scheduling:

  • Combined Sequencing and Scheduling
  • Turnaround Scheduling

This necessitates investigations on the structure and complexity of these problems. In a second step, the insights need to be transferred into efficient algorithms that 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).



  • W. Höhn and T. Jacobs. "On the performance of Smith's rule in single-machine scheduling with nonlinear cost". Proc. of the 10th Latin American Theoretical Informatics Symposium (LATIN). 2012. pp. 482-493. [More] 
  • W. Höhn and T. Jacobs. "An experimental and analytical study of order constraints for single machine scheduling with quadratic cost". Proc. of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX). 2012. pp. 103-117. [More] 
  • W. Höhn, T. Jacobs and N. Megow. "On Eulerian Extensions and their Application to No-wait Flowshop Scheduling", Journal of Scheduling, Vol. 15. 2012, pp. 295-309. [More] 
  • T. Gellert, W. Höhn and R. H. Möhring. "Sequencing and Scheduling for Filling Lines in Dairy Production", Optimization Letters, Vol. 5. 2011, pp. 491-504. [More] 
  • W. Höhn, F. G. König, M. E. Lübbecke and R. H. Möhring. "Integrated Sequencing and Scheduling in Coil Coating", Management Science, Vol. 57. 2011, pp. 647-666. [More] 
  • N. Megow, R. H. Möhring and J. Schulz. "Decision Support and Optimization in Shutdown and Turnaround Scheduling", INFORMS Journal on Computing, Vol. 23. 2011, pp. 189-204. [More] 
  • E. Günther, F. G. König and N. Megow. "Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width". Proceedings of the 7th International Workshop on Approximation and Online Algorithms (WAOA '09). 2010. pp. 170-181. [More] 
  • E. Günther, F. G. König and N. Megow. "The Bin-Scheduling Problem". Proceedings of MAPSP '09. 2009. [More] 
  • N. Megow, R. H. Möhring and J. Schulz. "Turnaround Scheduling in Chemical Manufacturing". Proceedings of MAPSP '07. 2007. [More] 
View less
[ Back ]