Markus GrüneFolie: 1 Doktoranden-Seminar: Simulationen SS2002 Thema: Simulation von Verteilungsmodellen von Workflowmanagement-Systemen Markus Grüne

Markus Grüne Folie: 1

Doktoranden-Seminar: Simulationen SS2002

Thema: Simulation von Verteilungsmodellen von Workflowmanagement-

Systemen

Markus Grüne


Inhalt

AgentenSimulationWorkflowmanagement-Systeme (WFMS)Untersuchungsgegenstände einer simulativen Analyse von WFMSAnwendungsfall: Stochastic Petri Nets zur simulativen Untersuchung von WFMSAusblick


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


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“


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


Agenten (4)

Weitere AspekteMigration eines Agenten (virtuelle, reale)Multi-Agenten-Systeme (MAS)Proxy-Kommunikation zur Kommunikation zwischen unterschiedlichen MAS...


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)


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


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


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


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)


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


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


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


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


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


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


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


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


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


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


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


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


Teilprozess 2

Teilprozess 1

A1 AND

A6

A2 AND AND

A3 A4

A5

AND A7

Beispiele für Delegationsmodelle: Hybrid-Modell


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


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



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



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



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



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


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, ...)


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?


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 ?

...

Documents

Markus GrüneFolie: 1 Doktoranden-Seminar: Simulationen SS2002 Thema: Simulation von Verteilungsmodellen von Workflowmanagement-Systemen Markus Grüne