TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)Complex Scheduling

COGA 5-Wheel

Page Content

to Navigation

Algorithms for Complex Scheduling Problems


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.


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.


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).



On the performance of Smith's rule in single-machine scheduling with nonlinear cost
Citation key HoehnJacobs2012b
Author Höhn, Wiebke and Jacobs, Tobias
Title of Book Proc. of the 10th Latin American Theoretical Informatics Symposium (LATIN)
Pages 482-493
Year 2012
DOI 10.1007/978-3-642-29344-3_41
Volume 7256
Publisher Springer
Series LNCS
Abstract We consider the problem of scheduling jobs on a single machine. Given some continuous cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each individual job is determined by the cost function value at the job's completion time. This problem is closely related to scheduling a single machine with nonuniform processing speed. We show that for piecewise linear cost functions it is strongly NP-hard. The main contribution of this article is a tight analysis of the approximation factor of Smith's rule under any particular convex or concave cost function. More specifically, for these wide classes of cost functions we reduce the task of determining a worst case problem instance to a continuous optimization problem, which can be solved by standard algebraic or numerical methods. For polynomial cost functions with positive coefficients it turns out that the tight approximation ratio can be calculated as the root of a univariate polynomial. To overcome unrealistic worst case instances, we also give tight bounds that are parameterized by the minimum, maximum, and total processing time.
Link to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe