|Project director:||Prof. Dr. Rolf H.
researchers:||Torsten Gellert |
Felix G. König 
Dr. Marco E. Lübbecke 
Jens Schulz 
|Support:||DFG Priority Programme
1307 "Algorithm Engineering" |
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:
- © COGA
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.
- © COGA
Basis Sequencing  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.
- © 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, 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).
|Author||Höhn, Wiebke and König, Felix G. and Lübbecke, Marco E. and Möhring, Rolf H.|
|Note||Finalist for the EURO Excellence in Practice Award 2009|
|Abstract||We consider a complex planning problem in integrated steel production. A sequence of coils of sheet metal needs to be color coated in consecutive stages. Different coil geometries and changes of colors necessitate time-consuming setup work. In most coating stages one can choose between two parallel color tanks. This can either reduce the number of setups needed or enable setups concurrent with production. A production plan comprises the sequencing of coils and the scheduling of color tanks and setup work. The aim is to minimize the makespan for a given set of coils. We present an optimization model for this integrated sequencing and scheduling problem. A core component is a graph theoretical model for concurrent setup scheduling. It is instrumental for building a fast heuristic that is embedded into a genetic algorithm to solve the sequencing problem. The quality of our solutions is evaluated via an integer program based on a combinatorial relaxation, showing that our solutions are within 10% of the optimum. Our algorithm is implemented at Salzgitter Flachstahl GmbH, a major German steel producer. This has led to an average reduction in makespan by over 13% and has greatly exceeded expectations.|