Interdependences among planning problems : a multi-agent-based coordination approach

Gegenstand dieser Arbeit sind Interdependenzen von Planungsproblemen in einer Lieferkette im Kontext eines tiefbaulogistischen Szenarios im Erdbau. In dem Baustellenszenario stehen im Rahmen der Ablaufplanung von Aktivitäten das Resource-Constrained Project Scheduling Problem (RCPSP) und im Rahmen der räumlichen Aktivitätenverteilung das asymmetrische Traveling Salesman Problem (ATSP) in einer Interdependenz. Die Koordination zur Auflösung der durch Interdependenzen mehrerer Planungsprobleme verursachten Auswirkungen stellt das Kernproblem dar. Da die einzelnen Planungsverfahren die Optimalität der Planung des jeweiligen anderen Planungsproblems nicht berücksichtigen, entstehen potentiell im Bezug auf das Gesamtsystem und dessen Zielfunktion vom Optimum erheblich abweichende Lösungen, obwohl die isolierten Lösungen der Teilprobleme möglicherweise optimal sind. Das Koordinationsproblem wird durch die asymmetrische Informationsverteilung über die gesamte Lieferkette hinweg erschwert. Aus Perspektive der Lieferkette hat dies zur Folge, dass die Leistungserbringer als teilweise autonom handelnde Entscheidungsträger über alle Stufen eng miteinander verzahnt werden müssen. In diesem Kontext, der vertraglichen Beziehung zwischen den Leistungserbringern mit möglicherweise unterschiedlichen Interessen, wird das Koordinationsproblem um den Abstimmungsaufwand zwischen den potentiell autonomen Leistungserbringern erweitert. Diese dezentrale Entscheidungssituation muss somit bei der Koordination zur Planung beachtet werden. Softwareagenten bieten dabei einen geeigneten Ansatz autonome, verteilte, dezentrale, logistische Systeme zu repräsentieren. Speziell der Bereich der agentenbasierten dezentralen Koordination zur dezentralen Planung dezentraler Pläne bietet dieser Arbeit eine Perspektive, einen Lösungsansatz für das Koordinationsproblem zu entwickeln. Konkret wird für die Planungs- und Koordinationsaufgaben der agentenbasierte Koordinationsansatz des Generalized Partial Global Planning (GPGP) angewendet, in dem sowohl der Prozess der Planung als auch das Ergebnis verteilt sind. Auf Basis dieses Verfahrens wird ein Koordinationsansatz entlang des Interaction Protocol Engineering-Vorgehensmodell entwickelt. Das Ergebnis stellt ein Koordinationsprotokoll dar. Die Evaluation erfolgt mit Hilfe der Evaluationsmethode Simulation im Rahmen einer Multiagentensimulation. Als Simulationsmodell dient eine reduzierte Version des diese Arbeit motivierenden tiefbaulogistischen Szenarios. Ziel der Simulation ist es zu zeigen, dass das in dieser Arbeit vorgestellte Multiagentensystem und das für die Planung interdependenter Planungsprobleme entwickelte Koordinationsprotokoll (1) sich zur Optimierung bzgl. der interdependenten Planungsprobleme eignet und (2) ein korrektes Systemverhalten aufzeigt.In this thesis, interdependencies of planning problems in a supply chain in the context of a civil engineering logistic scenario are analysed. In this construction site scenario there are - within the scheduling of activities - the resource-constrained project scheduling problem (RCPSP) and - within the spatial distribution of activities - the asymmetric traveling salesman problem (ATSP) in an interdependence. The required coordination in order to resolve the impact caused by interdependencies of several planning is address as the core problem in this work. Since the individual planning processes do not consider the optimality of the planning of the respective other planning problem, there arise potentially in terms of the overall system and its objective function from the optimum material deviated solutions, although the isolated solutions of partial problems are optimally possibly. The coordination problem is exacerbated by the asymmetric distribution of information through the supply chain. From the perspective of the supply chain, this has the consequence that the service providers must be closely integrated as autonomous actors throughout all levels of the supply chain. In this context of the contractual relationship between the service providers with potentially different interests the coordination problem is extended to the coordination effort between the potentially autonomous providers. This decentralized decision situation must therefore be considered in the coordination of planning. Thereby software agents provide a suitable approach to represent autonomous, distributed, decentralized logistics systems. Especially the field of agent-based decentralized coordination for decentralized planning of decentralized plans offers this work a perspective to develop an approach for the coordination problem. Specifically, the agent-based coordination approach of the generalized partial global planning (GPGP) is used for the planning and coordination tasks, in which both the process of planning as well as the result of planning is distributed. Based on this method, a coordination approach along the interaction protocol engineering process model is developed. The result represents a coordination protocol. The evaluation is performed using the method of simulation as part of a multi-agent simulation. The simulation model is a reduced version of the construction site scenario. The aim of the simulation is to show that the presented multi-agent system and developed coordination protocol (1) are suitable for the optimization of the interdependent planning problems and (2) showing a sound system behaviour