Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-1354
Main Title: Mehrdimensionale Multiressourcenplanung mit Constraintlösern
Translated Title: Multidimensional Multiresource Planning with Constraint Solvers
Author(s): Matzke, Dirk
Advisor(s): Jähnichen, Stefan
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: German
Language Code: de
Abstract: In der Dissertation wird ein Constraintlöser für diskrete mehrdimensionale Multiressourcenprobleme vorgestellt. Zu diesen Problemen gehören Planungs- und Platzierungsprobleme aus den Bereichen Produktionsplanung, Personalplanung, Stundenplanung, Kursplanung, Containerpackung, Routenplanung oder Fahrplanerstellung für Verkehrunternehmen. Mit zur Zeit verfügbaren kommerziellen Constraintlösern steigt der Lösungsaufwand von Multiressourcenproblemen mit der Problemgröße exponentiell an. Durch den entwickelten und in dieser Arbeit beschriebenen Constraintlöser für Multiressourcenprobleme wird dieser Aufwand für eine wesentlich erweiterte Problemgröße signifikant verringert. In der Dissertation wird an einem realen Anwendungsbeispiel gezeigt, dass die starke Verringerung des Anstiegs des Lösungsaufwands auch für große Probleme realisierbar wird durch eine Problemzerlegung des mehrdimensionalen Multiressourcenproblems in mindestens einer Dimension, durch die Einführung einer zentralen Konsistenzsicherung und Bereichsverwaltung in speziellen Werterepräsentationen der Domänenvariablen und durch die Implementierung von speziellen globalen Constraints für die Modellierung von Ressourcen und Reihenfolgebeziehungen. Bei der Problemzerlegung eines mehrdimensionalen Multiressourcenproblems werden die Vernetzung und die Struktur des Lösungsraums analysiert. Der Lösungsraum wird an geeigneten markanten Stellen, an denen sich weitgehend unabhängige Teillösungsräume ergeben, aufgeteilt. In einzelnen Teillösungsräumen wird separat und nacheinander entsprechend der ursprünglichen Anordnung eine Lösung gesucht. Eventuelle Auswirkungen der Lösung eines Teillösungsraums auf einen oder mehrere andere nachfolgende Teillösungsräume werden weitergegeben. Zur Konsistenzsicherung der Daten bei der Lösungssuche und der Propagation auf den Wertebereichen der Ressourcen erfolgt, wie in herkömmlichen Constraintlösern üblich, kein Wechsel zur komplexitätsreduzierenden Intervallpropagation mit ausschließlicher Einschränkung der Werte an den Intervallgrenzen, sondern es wird auch bei großen Wertebereichen die wertgenaue Einschränkungsmethode angewendet. Dadurch werden auch kleinste Inkonsistenzen (Löcher) in sonst geschlossenen Wertebereichen erkannt. Der Constraintlöser für Multiressourcenprobleme beinhaltet nur einige einfache Constraints und zwei globale Constraints, um mit einer möglichst geringen Anzahl von Constraints auszukommen. Damit verringert sich der Verwaltungsaufwand der Constraints. Zu den globalen Constraints gehören das Reihenfolgeconstraint RC, womit die Abfolge von Ereignissen festgelegt werden kann und das Constraint diffn2D(), welches die überlappungsfreie Zuordnung zu Ressourcen sicherstellt. Das globale Constraint diffn2D() kann in der derzeitigen Auslegung zweidimensionale Wertebereiche mit einer jeweiligen Ausdehnung von bis zu 10 Millionen Werten je Dimension ohne Intervallverarbeitung bei geringem Speicherverbrauch verwalten. Zur Lösung von Multiressourcenproblemen kann das zweidimensionale globale Constraint diffn2D() mehrfach kombiniert werden. Hierbei wird eine Dimension als Bezugsdimension genutzt. Die Erweiterung der Problemgröße zur Verarbeitung großer Multiressourcenprobleme wird mit Hilfe des Übergangs zur 64 Bit-Technik für die Datenspeicherung und für die Adressierung innerhalb des Constraintlösers erreicht. Der entwickelte Constraintlösers kann deshalb unmittelbar die Vorteile einer Hardware mit 64 Bit Architektur nutzen und damit zu einer weiteren Beschleunigung des Planungsprozesses beitragen. In der vorliegenden Dissertation werden die Eigenschaften des Constraintlöser für mehrdimensionale Multiressourcenprobleme am Problem der mehrjährigen Kursplanung für Weiterbildungseinrichtungen erläutert. Die Implementierung des Constraintlösers erfolgte in C++. Der Constraintlöser ist außer an der Kursplanung auch, in Zusammenarbeit mit der Deutschen Bahn AG, für das sehr komplexe Problem der Fahrplan- und Betriebssimulation in Eisenbahnnetzen erfolgreich getestet worden.
The thesis introduces a constraint solver for discrete multidimensional multiresource problems. Such problems include planning and order problems from the areas of production and personnel planning, timetabling and course planning, container packing, route planning or timetable generation for transport companies. Using currently available commercial constraint solvers, the effort required to solve multiresource problems increases exponentially with problem size. This effort is significantly reduced for a much larger problem size by the constraint solver for multiresources problems developed and described in this thesis. In the thesis, a real application example is used to show that the increase in problem-solving effort can be drastically reduced for large problems too by decomposing the multidimensional multiresource problem in at least one dimension, by introducing central consistency-checking and range-management mechanisms in special value representations of the domain variables and by implementing special global constraints for modelling resources and order relations. When decomposing a multidimensional multiresource problem, the interlinking and the structure of the solution space are analyzed. The solution space is split at suitable points, where largely independent partial solution spaces occur. In individual partial solution spaces, a solution is sought separately and successively following the original order. Possible effects of the solution of a partial solution space on one or more other subsequent partial solution spaces are passed on. For data consistency checking during the solution search and the propagation on the resource’s value ranges, there is – unlike when using conventional constraint solvers – no change to complexity-reducing interval propagation with exclusive restriction of the values at the interval borders. Instead, the value-exact restriction method is used, even for large value ranges. Even minimal inconsistencies (holes) are thus detected in otherwise closed value ranges. To keep the number of constraints to a minimum, the constraint solver for multiresource problems manages with only a few simple constraints and two global constraints. This reduces constraint management effort. The global constraints include the order constraint RC, which enables the sequence of events to be fixed, and the constraint diffn2D(), which ensures the non-overlapping allocation of resources. In its current form, the global constraint diffn2D() can manage two-dimensional value ranges of up to 10 million values per dimension without interval processing and with low memory consumption. To solve multiresource problems, the two-dimensional global constraint diffn2D() can be multipally combined. Here, a dimension is used as a reference dimension. The extension of problem size for processing large multiresource problems can be achieved by transition to 64-bit technology for data storage and addressing within the constraint solver. The developed constraint solver can thus directly exploit the advantages of hardware with 64-bit architecture, thus helping to further speed up the planning process. The thesis illustrates the characteristics of the constraint solver for multidimensional multiresource problems using as a concrete example the problem of long-term course planning for further-education institutions. The constraint solver was implemented in C ++. The constraint solver was successfully tested not only for course planning but also – in cooperation with the Deutschen Bahn AG – for the highly complex problem of timetable and operation process simulation in rail networks.
URI: urn:nbn:de:kobv:83-opus-12831
http://depositonce.tu-berlin.de/handle/11303/1651
http://dx.doi.org/10.14279/depositonce-1354
Exam Date: 19-Dec-2005
Issue Date: 26-May-2006
Date Available: 26-May-2006
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): Constraintlöser
Globale Constraints
Multiressourcenplanung
Constraint solver
Global constraints
Multiresource planning
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_11.pdf3,29 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.