Ziel dieser Diplomarbeit ist die Konzeption und Implementierung eines universell einsetzbaren Multiagentensystems für unterschiedliche Anwendungsgebiete. Bei diesen Systemen erfolgt das Lösen von Aufgaben durch das Zusammenwirken der spezialisierten Handlungsweisen autonom agierender, intelligenter Agenten. Die dabei entstehenden Koordinations-, Kooperations- und Organisationsprobleme werden durch die Methoden des Rollenmodells und der verteilten künstlichen Intelligenz bewältigt. Zur Evaluierung des entwickelten Systems erfolgen Berechnungen von kombinatorischen sequenzabhängigen Schedulingproblemen. Dazu werden mehrere Optimierungsalgorithmen auf der Basis von Agenten erstellt.
Das in dieser Arbeit entworfene Multiagentensystem erfüllt mit seinen Fähigkeiten die aktuellen Anforderungen für flexibles verteiltes Rechnen. Die Untersuchung zeigt, dass agentenbasierte Softwarearchitekturen viele Vorteile gegenüber dem objekt- und komponentenbasierten Ansatz bieten. Die Agententechnologie ermöglicht eine übersichtliche Systementwicklung und führt unter anderem zu einer besseren Beherrschung der Systemkomplexität. Durch das intelligente Verhalten der Agenten lassen sich die komplexen Schedulingprobleme effizient lösen.
Inhaltsverzeichnis
1 Einleitung
2 Grundlagen
2.1 Definition Agent
2.2 Arten von Softwareagenten nach Russel und Norvig
2.3 Eigenschaften einer Agentenumgebung
2.4 Multiagentensystem
2.5 Emergenz im Multiagentensystem
2.6 Rollenmodell
2.7 Referenzmodell für Agentenplattformen
2.8 Betrachtung agentenbasierter Systeme und aktueller Einsatzgebiete
2.8.1 Electronic Commerce
2.8.2 Information Retrieval
2.8.3 Weitere Einsatzgebiete
2.9 Schedulingproblem
3 Konzeption eines Multiagentensystems
3.1 Anforderungen
3.2 Agentenrollen
3.2.1 Server Agent
3.2.2 Task Contractor Agent
3.2.3 Controller Agent
3.2.4 Collector Agent
3.2.5 Splitter Agent
3.2.6 Answer Agent
3.2.7 Jabber Agent
3.2.8 Client Agent
3.2.9 Load Balance Agent
3.2.10 Worker Agent
3.3 Architektur
3.4 Kommunikation der Agenten
3.4.1 Nachrichtenpaket
3.4.2 Scheduling Task Paket
3.4.3 Control Task Paket
3.5 Lastverteilung
3.6 Ausfallsicherheit und Fehlertoleranz
3.7 Funktionsweise des Systems
3.8 Skalierbarkeit
3.9 Betrachtung des entstandenen Systems
4 Implementierung
4.1 Java Agent Development Framework
4.1.1 Verhaltensmuster von Agenten
4.1.2 Interaktion zwischen Agenten
4.1.3 Gruppenunterstützungsmodell
4.1.4 Informationssicherheit
4.1.5 Ausfallsicherheit
4.2 Scheduling Framework
4.2.1 Näherungsverfahren der Simulation
4.2.2 Funktionsweise des Frameworks
4.2.3 Algorithmen und Zielkriterien
4.3 Implementierung von Lagoon
4.3.1 Start des Systems
4.3.2 Agentenrollen
4.3.3 Nachrichtenpakete und Kommunikation der Agenten
4.4 Grafische Benutzeroberfläche
5 Schedulingalgorithmen
5.1 Einteilung der Algorithmen
5.2 Sequenzierungsalgorithmen
5.2.1 Random Down Swing
5.2.2 Random Walk Recipe Variation
5.2.3 Simplex Methode
5.2.4 Partikel Schwarm Optimierung
5.3 Partitionierungsalgorithmus
5.3.1 Central Complex
5.3.2 Weitere Optimierungsalgorithmen
6 Simulation und Ergebnisse
6.1 Testfälle und Simulationsumgebung
6.2 Simulation 1: Parallele Maschinen
6.3 Simulation 2: Simplex Methode
6.4 Simulation 3: Lateness
6.5 Simulationsergebnis
7 Zusammenfassung und Ausblick
A Grundlagen
A.1 Agentenarchitekturen
A.2 Kommunikationsparameter
B Konzeption eines Multiagentensystems
B.1 Beispielstruktur eines Systems mit Lagoon
B.2 Sequenzdiagramm des Beispiels für die Funktionsweise
C Implementierung
C.1 Weitere Frameworks für Agentensysteme
C.2 Klassenhierarchie der Behaviours
C.3 Kommunikationsaktivitäten
D Simplex Methode am Beispiel
E Simulation
E.1 Betriebsumgebungen
E.2 Testfälle
E.3 Simulation: Simplex Methode
Zielsetzung und thematische Schwerpunkte
Ziel dieser Arbeit ist die Konzeption und Implementierung eines flexiblen, plattformunabhängigen Multiagentensystems (MAS) zur effizienten Lösung komplexer, reihenfolgeabhängiger Schedulingprobleme, wie sie beispielsweise in der Halbleiterfertigung bei Cluster Tools auftreten.
- Entwicklung einer agentenbasierten Softwarearchitektur auf Basis des JADE-Frameworks.
- Implementierung dezentraler Lastausgleichs- und Koordinationsmechanismen mittels Rollenmodell.
- Integration verschiedener heuristischer und deterministischer Optimierungsalgorithmen zur Scheduling-Optimierung.
- Evaluierung des Systems durch Simulation verschiedener Testfälle und Vergleich der Algorithmus-Leistung.
- Schaffung einer skalierbaren und ausfallsicheren Umgebung für verteiltes Rechnen.
Auszug aus dem Buch
2.9 Schedulingproblem
Zur Evaluierung des MAS wird das Lösen von komplexen Schedulingproblemen betrachtet. Beim Scheduling werden einer begrenzten Anzahl von Ressourcen Jobs in einer bestimmten Reihenfolge zugewiesen. Die Ressourcen sind bei der betrachteten Problemstellung Maschinen mit mehreren Bearbeitungseinheiten zur parallelen Verarbeitung, die so genannten Bediener. Die Jobs werden als Sequenz in einer Warteschlange vor diesen angeordnet und entsprechend eines Ablaufplans der Reihe nach abgearbeitet.
Der in dieser Arbeit betrachtete spezielle Sachverhalt besteht im Lösen von kombinatorischen sequenzabhängigen Schedulingproblemen für mehrere Maschinen. Kombinatorisch umfasst dabei die möglichen Anordnungen der Jobs in der Warteschlange. Bei Sequenzabhängigkeit ist die zeitliche Reihenfolge der nicht unterbrechbaren Jobs ausschlaggebend für die Qualität der Lösung.
Diese komplexen Schedulingprobleme mit reihenfolgeabhängigen Prozesszeiten treten in der Halbleiterfertigung auf. Für eine effiziente Herstellung von Mikrochips ist ein bestmöglicher Ablaufplan erforderlich, um die Produktionszeit zu verkürzen und die damit verbundenen Kosten zu senken. Diese Aufgabenstellung gehören zur Klasse der NP-vollständigen Probleme, für die bisher keine praktikablen klassischen Verfahren zur Lösungsfindung existieren.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die Agententechnologie und Multiagentensysteme ein und definiert das Ziel der Arbeit, ein System zur Lösung komplexer Schedulingprobleme zu entwickeln.
2 Grundlagen: Das Kapitel behandelt theoretische Grundlagen zu Agenten, Multiagentensystemen, Emergenz, Rollenmodellen sowie Schedulingproblemen in der Halbleiterfertigung.
3 Konzeption eines Multiagentensystems: Hier wird das Konzept des MAS "Lagoon" vorgestellt, inklusive der Anforderungsanalyse, der verschiedenen Agentenrollen, Architektur und Lastverteilungsstrategien.
4 Implementierung: Dieses Kapitel beschreibt die technische Umsetzung des Systems in Java unter Verwendung des JADE-Frameworks und des Scheduling Frameworks Sage.
5 Schedulingalgorithmen: Es werden verschiedene Optimierungsalgorithmen, darunter Random Down Swing, Simplex Methode und Partikel Schwarm Optimierung, zur Lösung der Schedulingprobleme erläutert.
6 Simulation und Ergebnisse: Dieses Kapitel vergleicht die Leistung der entwickelten Algorithmen anhand verschiedener Simulationstests und analysiert deren Effizienz und Skalierbarkeit.
7 Zusammenfassung und Ausblick: Die Arbeit schließt mit einer Rekapitulation der Ergebnisse sowie einem Ausblick auf zukünftige Erweiterungsmöglichkeiten und Forschungsfelder ab.
Schlüsselwörter
Multiagentensystem, MAS, JADE, Scheduling, Schedulingproblem, Agenten, Rollenmodell, Halbleiterfertigung, Optimierungsalgorithmen, Lastverteilung, verteilte Systeme, Simulation, Cluster Tool, Künstliche Intelligenz, Grid Computing.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Es geht um die Entwicklung eines universell einsetzbaren Multiagentensystems (MAS), das spezifisch für die Lösung komplexer, reihenfolgeabhängiger Schedulingprobleme konzipiert wurde.
Was sind die zentralen Themenfelder der Arbeit?
Zentrale Themen sind die agentenorientierte Softwareentwicklung, die Modellierung von Multiagentensystemen nach dem Rollenmodell sowie die Optimierung von Ablaufplänen in der Halbleiterindustrie.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Ziel ist die Konzeption und Implementierung einer plattformunabhängigen, flexiblen Softwarearchitektur, welche die Bearbeitung von Scheduling-Aufgaben durch die Kooperation autonomer Agenten effizient und skalierbar gestaltet.
Welche wissenschaftlichen Methoden werden verwendet?
Die Arbeit nutzt Methoden der verteilten künstlichen Intelligenz, diverse Heuristiken und Optimierungsalgorithmen (wie Simplex oder PSO) sowie Simulationen zur Evaluierung der Systemleistung.
Was wird im Hauptteil der Arbeit behandelt?
Im Hauptteil werden das Konzept des "Lagoon"-Systems, die Implementierung unter Nutzung des JADE-Frameworks sowie die detaillierte Analyse und Vergleich verschiedener Scheduling-Algorithmen beschrieben.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die wichtigsten Begriffe sind Multiagentensystem, Scheduling, JADE, Agentenrollen, Rollenmodell, Lastverteilung, Optimierung und Cluster Tools.
Was ist der Vorteil des Rollenmodells in diesem Kontext?
Das Rollenmodell bietet eine hohe Flexibilität und Allgemeingültigkeit, da keine zentrale Steuereinheit erforderlich ist und Aufgaben dynamisch an Agenten mit passenden Fähigkeiten vergeben werden können.
Wie unterscheidet sich das Push-Verfahren vom Pull-Verfahren bei der Lastverteilung?
Beim Pull-Verfahren suchen unterlastete Agenten aktiv nach Aufträgen, während beim Push-Verfahren überlastete Agenten aktiv nach Partnern suchen, um überschüssige Aufgaben abzugeben, was den Nachrichtendienst entlastet.
- Arbeit zitieren
- Peter Hillmann (Autor:in), 2011, Entwicklung eines Multiagentensystems auf Basis des Frameworks Jade zur Lösung komplexer Schedulingprobleme, München, GRIN Verlag, https://www.grin.com/document/366790
