Hybrid Solving Techniques for Project Scheduling Problems
| dc.contributor.advisor | Möhring, Rolf | en |
| dc.contributor.author | Schulz, Jens | en |
| dc.contributor.grantor | Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften | en |
| dc.date.accepted | 2012-12-14 | |
| dc.date.accessioned | 2015-11-20T22:16:35Z | |
| dc.date.available | 2013-05-24T12:00:00Z | |
| dc.date.issued | 2013-05-24 | |
| dc.date.submitted | 2013-05-24 | |
| dc.description.abstract | 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. | de |
| dc.description.abstract | Resource-constrained Project Scheduling problems (RCPSP) contain practically relevant and combinatorial optimization problems as they occur e.g., in manufacturing. Already single characteristics of these problems are known to belong to the class of NP-hard problems such that people from theory and practice developed sophisticated solving techniques to approach such kinds of problems. Constraint Integer Programming is a hybrid branch-and-bound framework, that integrates techniques from Constraint Programming (CP), Integer Programming (IP) and SAT solving. Given this framework, the different techniques can be applied in each node of the search tree such as propagation of the variable domains, computation of lower bounds from the LP relaxation as well as conflict analysis. In this thesis, techniques for RCPSP are developed in such a framework. We introduce an approximative criterion to identify promising intervals for propagation algorithms such as energetic reasoning. Using this result algorithmically, we are able to reduce the average running time to 1/4. This work is the first to perform an in-depth complexity study for explaining infeasibilities and bound changes as detected by the propagation algorithms of the cumulative constraint. Based on this study, explanation algorithms of different strengths are developed and evaluated. The size of the search tree can be reduced by up to 90%, while the average running time can be reduced by 2/3. Furthermore, we propose a continuous relaxation of the cumulative constraint which enables the solver to apply techniques from IP without adding additional (time-indexed) variables. On average we experience a reduction of half of the nodes and decrease running times by 1/3. The idea to apply coefficient strengthening on the cumulative constraint, enables us to solve some of the hard highly cumulative instances for the first time. A generalization of this technique to other global constraints from CP leaves ample room for future research. In total, or computational results are competitive to those reported in the literature and sometimes better on highly cumulative Pack instances. In the last two chapters, the gained knowledge and techniques are applied to problems coming from practical applications. Among them are net present value problems from the mining industry and labor constrained scheduling problems from chemical manufacturing. Finally, we apply a Dantzig-Wolfe decomposition to obtain tight dual bounds on the optimal solution for a Turnaround Scheduling problem. | en |
| dc.identifier.uri | urn:nbn:de:kobv:83-opus-39956 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/3899 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-3602 | |
| dc.language | English | en |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | Hybride Lösungsverfahren | de |
| dc.subject.other | Projektscheduling | de |
| dc.subject.other | Constraint Integer Programming | en |
| dc.subject.other | Scheduling | en |
| dc.title | Hybrid Solving Techniques for Project Scheduling Problems | en |
| dc.title.translated | Hybride Lösungstechniken für Projektschedulingprobleme | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | publishedVersion | en |
| tub.accessrights.dnb | free | * |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.identifier.opus3 | 3995 | |
| tub.identifier.opus4 | 3720 | |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1