Large-scale multi-agent meeting scheduling using an altruistic matching heuristic

Abstract

Das Problem eine große Anzahl an Treffen für mehrere Parteien zu planen tritt in vielen Szenarien auf. Dies geht von der Organisation privater Treffen über Social Media bis hin zur Planung von Geschäftsterminen oder dem Erstellen eines Stundenplans in der Schule. Normalerweise ist es nötig für jedes dieser Szenarios eine große Anzahl an Bedingungen zu berücksichtigen. Dies macht es für gewöhnlich schwer exakte Lösungen für solche Probleme zu finden. Aus diesem Grund fokussieren wir uns in dieser Arbeit auf einen heuristischen Zugang. Wir gehen das Problem an indem wir zuerst eine Formulierung angeben, welche geeignet ist, um eine große Zahl an Terminplanungsproblemen (meeting scheduling problems) zu modellieren. Als nächstes bringen wir einen verteilten Algorithmus vor, welcher solche Probleme heuristisch lösen kann. Er ist mithilfe eines Multiagentensystems implementiert um die teilnehmenden Parteien zu simulieren. Der Algorithmus hat den Vorteil, dass er gut auf größere Probleminstanzen skaliert, gleichzeitig gute Resultate liefert und dabei einen gewissen Grad an Privatsphäre ermöglicht. Um dies praktisch zu testen, wurde ein Instanzengenerator entwickelt. Die so generierten Instanzen basieren auf Daten aus Studien zu Geschäftsterminen in Amerika. Das bedeutet, dass gewisse Schlüsseleigenschaften, wie Beispielsweise die Länge der Termine, aus Verteilungen entnommen werden, welche auf den erwähnten Daten basieren. Die Resultate der Auswertung unseres Algorithmus auf den generierten Instanzen sind vielversprechend. Sie zeigen, dass unser Algorithmus gute Ergebnisse erzielen kann und gleichzeitig auch in der Praxis gut auf größere Probleminstanzen skaliert. Die Resultate erlauben auch eine genauere empirische Analyse des Algorithmus selbst. In diesem Kontext tragen wir auch Methoden vor, um den Algorithmus an spezielle Problemstellungenm anzupassen.

The problem of scheduling a large number of meetings for multiple parties can be found in many scenarios from organizing private events via social media to planning business meetings or timetabling in school. Usually each of those scenarios requires to take into consideration a large number and variety of constraints, which usually makes it hard to find exact solutions to such problems. Therefore, we focus on a heuristic approach in this thesis. We start to tackle this issue by first providing a formulation which is suitable to model a large number of meeting scheduling problems. We further propose a distributed algorithm to tackle the meeting scheduling problem using a heuristic approach. It is implemented through the means of a multi-agent system simulating the different participating parties in an instance. The algorithm has the benefit of scaling well to larger instances while still providing decent privacy and social welfare. In order to test that, an instance generator is further developed. The generated instances are based on data from real-life studies on meetings in corporate America. Meaning that key properties, such as the meeting length, are generated from distributions based on that data. The results of an evaluation of the aforementioned algorithm using the generated instances are promising. They show a high social-welfare for our algorithm, while it still scales well for larger problem instances. The results also allow for a deeper empirical analysis of the various aspects of the algorithm. In that context we also propose methods on how to optimize the algorithm for specific tasks.