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).
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
plex_scheduling/parameter/en/minhilfe/?tx_sibibtex_pi1%
5Bcontentelement%5D=tt_content%3A404590&tx_sibibtex
_pi1%5BshowUid%5D=294759&cHash=dc6a155cd1eb3d2df715
78a8ad79bf2e
d/AG_DiskAlg/FG_KombOptGraphAlg/paper/2014/GuentherKoen
igMegow2014.pdf
plex_scheduling/parameter/en/minhilfe/?tx_sibibtex_pi1%
5Bcontentelement%5D=tt_content%3A404590&tx_sibibtex
_pi1%5BshowUid%5D=238208&cHash=cbd39633c8637a6327eb
983b18705d87
d/AG_DiskAlg/FG_KombOptGraphAlg/paper/2012/HoehnJacobsM
egow2012.pdf
plex_scheduling/parameter/en/minhilfe/?tx_sibibtex_pi1%
5Bcontentelement%5D=tt_content%3A404590&tx_sibibtex
_pi1%5BshowUid%5D=263669&cHash=ca9619b3af6cef8e577b
468da87b0629
d/AG_DiskAlg/FG_KombOptGraphAlg/paper/2012/HoehnJacobs2
012a.pdf
plex_scheduling/parameter/en/minhilfe/?tx_sibibtex_pi1%
5Bcontentelement%5D=tt_content%3A404590&tx_sibibtex
_pi1%5BshowUid%5D=263670&cHash=92acb69dd3efa09cb877
9fadf78fe80a
d/AG_DiskAlg/FG_KombOptGraphAlg/paper/2012/HoehnJacobs2
012b.pdf
plex_scheduling/parameter/en/minhilfe/?tx_sibibtex_pi1%
5Bcontentelement%5D=tt_content%3A404590&tx_sibibtex
_pi1%5BshowUid%5D=238264&cHash=cc38059d14e442fdb215
26d747c5e78e
d/AG_DiskAlg/FG_KombOptGraphAlg/paper/2011/MegowMoehrin
gSchulz2011.pdf
plex_scheduling/parameter/en/minhilfe/?tx_sibibtex_pi1%
5Bcontentelement%5D=tt_content%3A404590&tx_sibibtex
_pi1%5BshowUid%5D=238193&cHash=ff25aa99e6b1172eab72
e80a5bf6a436
plex_scheduling/parameter/en/minhilfe/?tx_sibibtex_pi1%
5Bcontentelement%5D=tt_content%3A404590&tx_sibibtex
_pi1%5BshowUid%5D=238210&cHash=2cd2c08007e6cd5560c8
62e495a59c87
wnload/AG_DiskAlg/FG_KombOptGraphAlg/paper/2011/HoehnKo
enigLuebbecke_2011.pdf
plex_scheduling/parameter/en/minhilfe/?tx_sibibtex_pi1%
5Bcontentelement%5D=tt_content%3A404590&tx_sibibtex
_pi1%5BshowUid%5D=238188&cHash=817235512752dd751faa
016ef51618e8
d/AG_DiskAlg/FG_KombOptGraphAlg/paper/2010/GuentherKoen
igMegow2010.pdf
plex_scheduling/parameter/en/minhilfe/?tx_sibibtex_pi1%
5Bcontentelement%5D=tt_content%3A404590&tx_sibibtex
_pi1%5BshowUid%5D=238190&cHash=bf117c5ccb94df9d73fa
d69f70b0c3d7
d/AG_DiskAlg/FG_KombOptGraphAlg/eguenth/guentherKM09-ma
psp.pdf
plex_scheduling/parameter/en/minhilfe/?tx_sibibtex_pi1%
5Bcontentelement%5D=tt_content%3A404590&tx_sibibtex
_pi1%5BshowUid%5D=265904&cHash=cf100c91509ee664fa05
0b1d8e6f4bb0