Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Master's Thesis |
| Scope | Discipline-based scholarship |
| Title | Distributed scheduling using DCOPs in Signal/Collect |
| Organization Unit | |
| Authors |
|
| Supervisors |
|
| Language |
|
| Institution | University of Zurich |
| Faculty | Faculty of Economics, Business Administration and Information Technology |
| Date | 2015 |
| Abstract Text | Distributed constraint optimization allows to solve problems in domains like scheduling, traffic flow management or sensor network management. It is a well-researched field and various algorithms have been proposed. However, the dynamic nature of some of these problems in the real world have been overlooked by researchers and problems are often assumed to be static during the course of the computation. The benchmarking of distributed constraint optimization algorithms (DCOP) with changing problem definitions currently lacks a solid theoretical foundation and standardized protocols. This thesis aimed to measure the performance of different types of DCOP algorithms on dynamic problems with a focus on local-iterative algorithms and especially on the MaxSum algorithm and possibly contribute to the field. A complete, a local-iterative message-passing and a local-iterative approximate best-response algorithm for distributed constraint optimization have been implemented for comparison. In the implementation of the MaxSum algorithm, a variation of the usual graph structure has been attempted. As a real-world use case for benchmarking, the meeting scheduling problem has been mapped as distributed constraint optimization problem. A framework has been designed that allows dynamic changes to constraints, variables and the problem domain during run-time. The algorithms have been benchmarked in a static, as well as in a dynamic environment with various parameters and with a focus on solution quality over time. This thesis further proposes a solution to store, further process and monitor the results of the computation in real-time without affecting the performance of the algorithms. |
| Zusammenfassung | Distributed Constraint Optimization (DCOP) erm{\"o}glicht Probleml{\"o}sungen in beispielweise Terminplanung, Verkehrsflusskontrolle oder dem Management von Sensor Netzwerken. Es ist ein gut erforschtes Feld und es wurden viele verschieden Algorithmen zur Berechnung vorgestellt. Allerdings wird h{\"a}ufig von einer statischen Problemdefinition ausgegangen und der Aspekt von in der Realit{\"a}t h{\"a}ufig auftretenden {\"A}nderungen an der Problemstellung findet oft wenig Beachtung. Ausserdem fehlt es an einem soliden theoretischen Fundament und standardisierten Verfahren um die Performanz von DCOP Algorithmen hinsichtlich sich {\"a}ndernder Probleme zu erfassen. Diese Arbeit hatte das Ziel das Verhalten und die Leistung von verschieden Arten von DCOP Algorithmen in dynamischen Umgebungen mit einem Fokus auf lokale, iterative Algorithmen und Hauptaugenmerk auf den MaxSum Algorithmus zu untersuchen. Zum Vergleich wurde eine komplette und eine lokal, iterative "message-passing" sowie eine "best-response" Variante implementiert. W{\"a}hrend der Implementation des MaxSum Algorithmus wurde eine Variation von der {\"u}blichen Graphenstruktur ausprobiert. Zum Test eines realen Problems wurde Terminplanung ausgew{\"a}hlt und als DCOP formuliert. Es wurde ausserdem ein Framework entwickelt, welches die dynamische {\"A}nderung von Constraints, Variablen und der Problemdom{\"a}ne erm{\"o}glicht. Die Algorithmen wurden mit Fokus auf L{\"o}sungs-Qualit{\"a}t {\"u}ber Zeit, sowohl in einer statischen wie auch in einer dynamischen Umgebung getestet. Diese Arbeit schl{\"a}gt ausserdem eine L{\"o}sung zur Speicherung, Weiterverarbeitung und {\"U}berwachung der Resultate der Berechnungen in Echtzeit vor, welche die Performanz der Algorithmen nicht beeinflusst. |
| PDF File |
Download
|
| Export |
BibTeX
|