### Page Content

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:

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

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

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

## Publications

Citation key | HoehnJacobs2012a |
---|---|

Author | Höhn, Wiebke and Jacobs, Tobias |

Title of Book | Proc. of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX) |

Pages | 103-117 |

Year | 2012 |

Publisher | SIAM |

Abstract | We consider the problem of scheduling jobs on a single machine. Given a quadratic cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is defined as the cost function value at the job's completion time. Throughout the past decades, great effort has been made to develop fast exact algorithms for the case of quadratic costs. The efficiency of these methods heavily depends on the utilization of structural properties of optimal schedules such as order constraints, i.e., sufficient conditions for pairs of jobs to appear in a certain order. A considerable number of different kinds of such constraints have been proposed. In this work we enhance the map of known order constraints by proving an extended version of a constraint that has been conjectured by Mondal and Sen more than a decade ago. Besides proving this conjecture, our main contribution is an extensive experimental study where the influence of different kinds order constraints on the performance of exact algorithms is systematically evaluated. In addition to a best-first graph search algorithm, we test a Quadratic Integer Programming formulation that admits to add order constraints as additional linear constraints. We also evaluate the optimality gap of well known Smith's rule for different monomial cost functions. Our experiments are based on sets of problem instances that have been generated using a new method which allows us to adjust a certain degree of difficulty of the instances. |

Back [20]

ebseite/AG_DiskAlg/FG_KombOptGraphAlg/logos/dfg-algorit

hm-engineering-long.jpg

dr_rolf_h_moehring/parameter/en/minhilfe/

e_hoehn/wiebke_hoehn/parameter/en/minhilfe/

rsten_gellert/parameter/en/minhilfe/

_koenig/felix_koenig/parameter/en/minhilfe/

schulz/parameter/en/minhilfe/

ebseite/AG_DiskAlg/FG_KombOptGraphAlg/projects/Coil-Coa

ting/rec-coil-coiting-line.gif

plex_scheduling/sequencing_scheduling/parameter/en/minh

ilfe/

Webseite/AG_DiskAlg/FG_KombOptGraphAlg/projects/SPP-Com

plex-Scheduling/rec-comparability-map.gif

plex_scheduling/basic_sequencing/parameter/en/minhilfe/

Webseite/AG_DiskAlg/FG_KombOptGraphAlg/projects/TA-Cook

/rec-cat-cracker.jpg

plex_scheduling/turnaround_scheduling/parameter/en/minh

ilfe/

Webseite/AG_DiskAlg/FG_KombOptGraphAlg/logos/dfg_scienc

etv_banner_deutsch.jpg

optimisers

optimierer

ad/AG_DiskAlg/FG_KombOptGraphAlg/paper/2012/HoehnJacobs

2012a.pdf

plex_scheduling/parameter/en/minhilfe/?no_cache=1&t

x_sibibtex_pi1%5Bdownload_bibtex_uid%5D=263669&tx_s

ibibtex_pi1%5Bcontentelement%5D=tt_content%3A404590

plex_scheduling/parameter/en/minhilfe/