View
113
Download
8
Category
Preview:
Citation preview
Markus Grüne Folie: 1
Doktoranden-Seminar: Simulationen SS2002
Thema: Simulation von Verteilungsmodellen von Workflowmanagement-
Systemen
Markus Grüne
Markus Grüne Folie: 2
Inhalt
AgentenSimulationWorkflowmanagement-Systeme (WFMS)Untersuchungsgegenstände einer simulativen Analyse von WFMSAnwendungsfall: Stochastic Petri Nets zur simulativen Untersuchung von WFMSAusblick
Markus Grüne Folie: 3
AgentenAn agent is an encapsulated computer system that is situated in some environment and that is capable of flexible, autonomous action in that environment in order to meet its design objectives.
Jennings, N. R. (2000): On agent-based software engineering, in: Artificial
Intelligence, Vol. 117, 2000, pp. 277 – 296, Elsevier
Autonomie: Agenten agieren ohne menschliches ZutunSozial: tauschen mit anderen strukturierte Nachrichten aus und kollaborierenReaktiv: antworten auf Änderungen ihrer UmweltProaktiv: verfolgen Ziele
Markus Grüne Folie: 4
Agenten (2)Reaktive Agenten:Eingeschränkte FähigkeitenReasoning = aus Menge situativer Aktionsregeln durch Kombination einer Vielzahl reaktiver Agenten kann proaktives Verhalten erzeugt werden „weak notion of agency“
Deliberative Agenten planen anhand eines symbolischen Modells ihrer Umweltführen - ausgehend von Kontext - zielgerichtete Handlungen durch„strong notion of agenency“
Markus Grüne Folie: 5
Agenten (3)
Opportunistische Agenten finden Anwendung, wenn trotz Vorhandensein eines symbolischen Modells der Umwelt keine wissensbasierte Lsg. des Problems existiert
Kendall, E.A. et al.: Patterns of Intelligent and Mobile Agents, in: Autonomous Agents 98, Minneapolis
Markus Grüne Folie: 6
Agenten (4)
Weitere AspekteMigration eines Agenten (virtuelle, reale)Multi-Agenten-Systeme (MAS)Proxy-Kommunikation zur Kommunikation zwischen unterschiedlichen MAS...
Markus Grüne Folie: 7
Simulation: Definitionsversuch
Simulation means driving a model of a system with suitable inputs and observing the corresponding outputs.Axelrod, R.:Advancing the Art of Simulation in the Social Sciences, in: Complexity, Vol.3, No.2, 1997
Hilfestellung bei Problemen, die nicht mit traditionellen Methoden gelöst werden können, z.B.Konzeption von WFMS, Mikroökonomische Fundierungmakroökonomischer Phänomene (ACE)
Markus Grüne Folie: 8
Simulation: Anwendungsgebiete
Vorhersage von SystemverhaltenSimulation zwecks Beweisführung Beweisführung i.S.v. Eignung zur Demonstration stabiler Systemzustände.Discovery. Im Gegensatz zur Beweisführung werden beim Discovery Eigenschaften des Systems aufgedeckt, die bislang unbekannt waren.
...Axelrod, R.:Advancing the Art of Simulation in the Social Sciences, in: Complexity, Vol.3, No.2, 1997
Markus Grüne Folie: 9
Workflow-Managementsysteme (1)
Bauer, T. et al.: Verteilungsmodelle für Workflow-Management-Systeme – Klassifikation und Simulation, in:Informatik, Forschung und Entwicklung (1999), 14, S. 205
Markus Grüne Folie: 10
Workflow-Managementsysteme (2)Bestandteile von WFMS (stark vereinfacht)WF-Engine selbst kann mehrere WF-Server umfassen und koordinieren
WF-Clients ermöglichen Benutzern die Anzeige auszuführender Aktivitäten in Arbeitslisten
orientiert an WfMC-Definition (nach Gadatsch) mit Änderungen in Yoo, J.-J.; Suh, Y.-H; Lee, D.-I. u.a. (2001): Casting Mobile Agents to Workflow Systems: On Performance and Scalability Issues, in: Mayer, H.C. et al. (Eds.): DEXA 2001, LNCS 2113, pp. 254 – 263, 2001
Markus Grüne Folie: 11
Workflow-Managementsysteme (3)
Zentrales Gestaltungs-Problem bei WFMS:optimale Architektur eines WFMS hängt u.a. ab von:
Anzahl beteiligter OE und deren StrukturNetzwerkkapazität und –strukturräumlicher Verteilung eines Unternehmens, (z.B. Anzahl der beteiligten Filialen)
Markus Grüne Folie: 12
Gestaltungsziele von WFMS (1)
Skalierbarkeit „How well a solution to some problem will
work when the size of the problem increases.” (http://wombat.doc.ic.ac.uk/)
PerformanceAntwortzeit oder Durchsatz/ Throughput, die von den Benutzern eines Systems beobachtet werden
nach Smith, C.U. (1986): The Evolution of Performance Engineering: A Survey, IEEE, 1986
Markus Grüne Folie: 13
Gestaltungsziele von WFMS (2)
LastverteilungLast pro WF-Server, Gesamtlast über alle WF-Server im WFMS und durchschnittliche Belastung der Teilnetze Management-Fragestellungenz.B. Wartezeiten von Kunden, die sich aus der Dauer interner G.-prozesse ergeben Gestaltungsziele = (evtl.) Untersuchungs-gegenstände der simulativen Analyse
Markus Grüne Folie: 14
Simulationsziele
Ziele der
Workflow-Simulation
Überprüfung der Ablauffähigkeit von Workflow-Modellen
Validierung der Realitätstreue von
Workflow-Modellen
Evaluation alternativer
Workflow-Modelle
Gadatsch, A.: Management von Geschäftsprozessen, 2001, S. 183
Markus Grüne Folie: 15
Anwendungsfall: Analyse von WFMS mit Stochastic Petri Nets (SPN)
Frage: Peformance-Steigerung und erhöhte Skalierbarkeit auch durch flexible Architektur eines WFMS erreichbar?Yoo, J.-J.; Suh, Y.-H; Lee, D.-I. u.a. (2001): Casting Mobile Agents to Workflow Systems: On Performance and Scalability Issues, in: Mayer, H.C. et al. (Eds.): DEXA 2001, LNCS 2113, pp. 254 – 263, 2001
Markus Grüne Folie: 16
Rolle von Agenten in WFMS
Agent übernimmt Aktivitäten eines Workflows und meldet Ergebnisse an die Kontrollinstanz des WFMS zurück Agent ist während der Aufgabenausführung unabhängig von der WF-EngineDurch Autonomie und Migrationsfähigkeit von Agenten kann die Zahl der Fernzugriffe im Netzwerk eingeschränkt werden
Markus Grüne Folie: 17
Probleme bei Verwendung von Agenten in WFMS
Bei umfangreichen Workflows evtl. Performance-Probleme, da Agenten bei Wanderung durch das Netz die WF-Definition mit sich tragen müssen. (Code-Size eines Agenten nimmt proportional mit der zugehörigen WF-Instanz zu) Bandbreite sinktKoordination der Agenten durch zentrale Instanz in Form eines Location- und Naming-Servers (LNS), die Agenten die Lokalisierung weiterer Agenten im WFMS ermöglicht. Kontrollinstanz bildet Flaschenhals
Markus Grüne Folie: 18
Suche nach einem geeigneten WFMS
Gesucht:Architektur, die für Vielzahl unterschiedlicher Delegations- / Verteilungsmodelle verwendbar ist 3-Ebenen-ArchitekturDelegationsmodelle, die Flaschenhals-Problematik mindern, die durch Kommunikation mit zentraler Instanz ensteht Proxy-Kommunikation
Markus Grüne Folie: 19
Lösungsansatz nach Yoo et al.
Einführung einer 3-Ebenen-ArchitekturEbene 1: WF-Koordinator, übernimmt Verteilung von Workflows auf unterschiedliche WF-Engines Ebene 2: WF-Engines, bilden Proxy-Agenten, die Workflows aufteiltenEbene 3: Sub-Agenten, die über einzelne Aufgabenträger iterieren.Delegationsmodelle, die für (Teil-) Workflows Agenten instanziierenZiel: Minderung des Flaschenhals-Problems durch hierarchische Gestaltung des Location Managements
Markus Grüne Folie: 20
Beispiele für Delegationsmodelle (1)
Minimum-Modell:Jede Aktivität einer WF-Instanz wird einem Sub-Agenten zugewiesenHoher Kommunikationsaufwand zwischen Proxy-Agenten und Sub-Agenten
Markus Grüne Folie: 21
Mobiler Agent
Task-Peformer-Knoten 1 Task-Performer-Knoten 2 Task-Performer-Knoten 3
Workflow-Engine
(1) migrieren
(2) antworten
(3) migrieren
(4) antworten
(6) antworten
(5) migrieren
Minimum-Modell
Markus Grüne Folie: 22
Mobiler Agent
Task-Peformer-Knoten 1 Task-Performer-Knoten 2 Task-Performer-Knoten 3
Workflow-Engine
(1) migrieren
(2) antworten
(3) migrieren
(4) antworten
(6) antworten
(5) migrieren
Maximum-Modell
Markus Grüne Folie: 23
Beispiele für Delegationsmodelle (2)
Hybrid-Delegationsmodell (min-based max)
geht davon aus, dass ein Workflow durch geschickte, schrittweise Zerlegung in Sub‑Workflows aufgeteilt werden kannAufteilung erfolgt anhand Parallelisierbarkeit der durchzuführenden Teilprozessenebeneinander ausführbare Aktivitäten werden an unterschiedliche Sub-Agenten delegiertAktivitäten, die sequentiell aufeinander folgen werden durch einzelnen Agenten komplett durchgeführt
Markus Grüne Folie: 24
Teilprozess 2
Teilprozess 1
A1 AND
A6
A2 AND AND
A3 A4
A5
AND A7
Beispiele für Delegationsmodelle: Hybrid-Modell
Markus Grüne Folie: 25
Umwandlung der Delegationsmodelle in stochastische Petri-Netze
S. Folie / Handout des Maximum-ModellsBeispiel: Maximum-Modell
WF mit 3 AufgabenAgent, der alle Aufgabenträger „besucht“ und Ergebnisse an WF-Engine zurückmeldet
Markus Grüne Folie: 26
Ergebnisse der Simulation (1)
Kleines WFMS (100 WF-Instanzen)
0
1000
2000
3000
4000
5000
6000
0 2 4 6
Anzahl Zweige
Sim
ula
tio
ns
zeit
(S
ek
.)
min
min-based max
max
Markus Grüne Folie: 27
Ergebnisse der Simulation (2)
Großes WFMS (1000 WF-Instanzen)
02000400060008000
1000012000140001600018000
0 2 4 6
Anzahl Zweige
Sim
ula
tio
ns
zeit
(S
ek
.)
min
min-based max
max
Markus Grüne Folie: 28
Ergebnisse der Simulation (3)
Bei geringer Anzahl von Instanzen schlägt min alle anderen DelegationsmodelleBei großer Anzahl schlägt das Hybrid-Modell die anderen Delegationsmodelle
min ist sensitiver gegenüber der Anzahl der WF-Instanzen als die anderen Delegationsmodelle
Flaschenhals-Problematik eines zentralisierten WFMS
Markus Grüne Folie: 29
Ergebnisse der Simulation (5)
Kleines WFMS (100 WF-Instanzen)
0
1000
2000
3000
4000
5000
6000
0 2 4 6
Zweiglänge
Sim
ula
tio
ns
zeit
(S
ek
.)
min
min-based max
max
Markus Grüne Folie: 30
Ergebnisse der Simulation (6)
Großes WFMS (1000 WF-Instanzen)
0
2000
4000
6000
8000
10000
12000
14000
16000
0 2 4 6
Zweiglänge
Sim
ula
tio
ns
zeit
(S
ek
.)
min
min-based max
max
Markus Grüne Folie: 31
Schlussbetrachtung
VorteileAuswertbarkeit von Stochastischen Petri-Netzen durch Tools möglich (UltraSAN, jetzt Möbius)Berücksichtigung der betrieblichen Ablaufstrukturen zur Wahl eines geeigneten WFMS (bei kleinen Systemen eher min-basierte WFMS, ...)
Markus Grüne Folie: 32
Schlussbetrachtung
NachteileFür jeden neuen WF muss für Simulation ein SPN erstellt werden (aber Wiederverwendung von Teilen aus anderen SPN)SPN eignen sich nur bedingt zur Darstellung der Code-Size von AgentenEntspricht Firing-Rate dem tatsächlichen WFMS-Verhalten?
Markus Grüne Folie: 33
Ausblick
„Adapative“ WFMS, die Delegationsmodelle nach der Analyse der WF-Schemata zuweisenWas bietet P2P bei WFMS ?Unternehmensübergreifende GP-KoordinierungAbwägung Kosten für Aufbau der Simulation vs. Erlöse durch schnellere Abwicklung von GPnSind Netzwerkkapazitäten in Zukunft überhaupt relevant ?
...
Recommended