Hybrid Solving Techniques for Project Scheduling Problems

Ressourcenbeschränkte Scheduling-Probleme umfassen viele praktische, kombinatorische Optimierungsprobleme, wie sie u.a. in Produktionsbetrieben entstehen. Bereits einzelne Charakteristika dieser Probleme sind auf stark NP-schweren Probleme zurückkzuführen, so dass sowohl Theoretiker als auch Praktiker neue und ausgeklügeltere Lösungstechniken entwickelt haben. Constraint Integer Programming ist ein hybrides Branch-and-Bound-Verfahren, das Techniken aus dem Constraint Programming (CP), Integer Programming (IP) und von SAT-Lösern eng miteinander verknüpft. Es ermöglicht die Anwendung dieser Techniken in jedem Knoten des Branch-and-Bound-Baumes, wie z.B. dem Propagieren der Variablendomains, der Berechnung von unteren Schranken mittels einer LP-Relaxierung und dem Generieren von Konfliktklauseln. In dieser Arbeit werden Techniken für Ressourcen-beschränkte Scheduling-Probleme in diesem Framework entwickelt. Wir stellen ein approximatives Resultat zum Identifizieren relevanter Intervalle für den Propagieralgorithmus energetic reasoning vor. Eine algorithmische Anwendung dieses Resultats senkt die Laufzeit auf ein Viertel. Diese Arbeit ist die erste, in der ausführliche Komplexitätsbetrachtungen für die Erklärung von Unzulässigkeiten im Zuge der Propagieralgorithmen des kumulativen Constraints durchgeführt werden und auf denen aufbauend Algorithmen entwickelt und evaluiert werden. Die Größe des Branching-Baumes kann um bis zu 90% im Durchschnitt verringert werden und die Laufzeit wird um ca. 2/3 gesenkt. Desweiteren stellen wir eine kontinuierliche Relaxierung des kumulativen Constraints vor, die dem B&B-Framework IP-Techniken zur Verfügung stellt, ohne zusätzliche Variablen einzuführen. Eine Reduktion der Knoten um die Hälfte und eine Laufzeitersparnis von 1/3 sind durchschnittlich zu beobachten. Die Verallgemeinerung des coefficient strengthening aus dem IP auf CP sorgt dafür, dass einige schwere hoch-kumulative Instanzen zum ersten Mal optimal gelöst werden können. Eine Verallgemeinerung dieser Technik auf andere globale CP-Constraints lässt Raum für weitere Arbeiten. Insgesamt sind unsere Rechenresultate kompetitiv zu anderen Verfahren auf den Instanzen aus der PSPLib und teils besser auf den hoch-kumulativen Pack-Instanzen. In den letzten beiden Kapiteln werden die gewonnenen Erkenntnisse auf drei verschiedene Praxisprobleme angewendet. Darunter fallen Net Present Value-Probleme, wie sie im Bergbau auftreten, und Labor-beschränkte Scheduling Probleme, wie sie in der chemischen Industrie auftreten. Abschließend nutzen wir das Konzept der Dantzig-Wolfe Dekomposition, um scharfe Schranken an die Optimallösung von Turnaround Scheduling Problemen zu ermitteln.

Author dc:creator

• Schulz, Jens

Advisor dc:contributor.advisor

• Möhring, Rolf

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en, English

Identifier URI

urn:nbn:de:kobv:83-opus-39956
http://dx.doi.org/10.14279/depositonce-3602

OAI identifier oai:identifier

oai:depositonce.tu-berlin.de:11303/3899