Zusammenfassung

Das Verhalten eines Petrinetzes kann gegeben sein durch die Menge seiner Schalt- oder Schrittfolgen, durch Erreichbarkeitsgraphen, aber auch durch halbgeordenete Ereignismengen, die oft als beschriftete azyklische Graphen dargestellt werden. Die zuletzt genannte Semantik erlaubt die explizite Darstellung von kausaler Unabhängigkeit; zwei Ereignisse finden unabhängig statt, wenn sie im Graphen nicht geordnet sind. Während derartige halbgeordnete Semantiken in der Theorie seit langer Zeit betrachtetet werden, finden sie erst in jüngerer Zeit in Anwendungen Beachtung, insbesondere in den Bereichen Geschäftsprozessmodellierung, Webdienste und Eingebettete Systeme, meist in Form verschiedener Varianten von Sequenzdiagrammen.

 

Die traditionelle Vorgehensweise beim modellbasierten Systementwurf - Konstruktion eines Modells und anschließende explizite oder implizite Betrachtung seines Verhaltens - wird vielfach abgelöst durch eine umgekehrte Vorgehensweise: Das Verhalten wird zunächst formalisiert und modelliert, und das Systemmodell wird daraus anschließend automatisch synthetisiert. Während für Petrinetze entsprechende Syntheseverfahren für Schrittfolgen und Erreichbarkeitsgraphen bekannt waren und in der Praxis eingesetzt wurden, fehlten Verfahren für die Synthese von Petrinetzen aus halbgeordneten Verhaltensbeschreibungen. Die Entwicklung derartiger Verfahren, ihre Implementierung und deren exemplarische Anwendung im Bereich der Geschäftsprozessmodellierung war Gegenstand dieses Vorhabens.

 

Das Projekt wurde in 2 Phasen bearbeitet. Die erste Projektphase von 2007 bis 2010 wurde von der DFG noch einmal um den gleichen Zeitraum verlängert. Die von der DFG bewilligte Förderung betrug für beide Phasen jeweils 2 Jahre, welche sich aber durch zwischenzeitliche Verzögerungen in der Bearbeitung jeweils auf 3 Jahre streckte. Das Projekt wurde zuerst an der katholischen Universität Eichstätt bearbeitet und wechselte dann Mitte der ersten Projektphase an die Universität Augsburg.

Es wurden die folgenden Ergebnisse erzielt:

 

  • S/T-Netze: Das Syntheseproblem für S/T-Netze aus halbordnungsbasierten Verhaltensbeschreibungen wurde umfassend gelöst, und zwar sowohl bzgl. Term-basierten als auch Graphen-basierten Darstellungen des halbgeordneten Verhaltens. Insbesondere wurden dabei auch verschiedene endliche Term- und Graphen-basierte Darstellungen unendlicher Abläufe und unendlicher Mengen von Abläufen betrachtet, die für die meisten Anwendungen ausreichend ausdrucksmächtig sind. Allerdings ist das Synthesproblem auf theoretischer Ebene noch insoweit nicht endgültig gelöst, als noch keine endliche Darstellung von beliebigem halbordnungsbasiertem Verhalten von Petrinetzen gefunden wurde.
  • Syntaktisch erweiterte Petrinetz-Modelle: S/T-Netze abstrahieren in verschiedener Weise zu stark von Aspekten, die in realen Anwendungen von hoher Relevanz sind, und haben eine in der Praxis nicht ausreichende Ausdrucksmächtigkeit. Dazu gehören u.a. die Berücksichtigung von Einschränkungen der Nebenläufigkeit durch knappe Ressourcen und durch Lesezugriffe. Solche Aspekte können in Petrinetzen durch verschiedenartige syntaktische Ergänzungen, welche i.d.R. Einfluss auf das Verhaltensmodell haben, berücksichtigt werden. Im Projekt konnten die Ergebnisse für S/T-Netze vollständig auf Petrinetze mit syntaktischer Erweiterung um Inhibitorkanten, Lesekanten und Kapazitätsbeschränkungen verallgemeinert werden (eine Erweiterung um Inhibitorkanten verleiht Petrinetzen die Ausdrucksmächtigkeit von Turingmaschinen). Außerdem untersuchten wir die Anwendbarkeit unserer Syntheseverfahren auf abstrakte algebraische Petrinetz-Definitionen, welche viele verschiedene konkrete Instantiierungen erlauben.
  • Varianten des klassischen Synthese-Problems: Das ursprünglich betrachtete klassische Synthese-Problem stellte sich in praktischen Anwendungen oft wegen spezifischer zusätzlicher Anforderungen und Randbedingungen als nicht direkt anwendbar heraus. Im Projekt entwickelten wir deshalb einen umfassenden Überblick über nützliche Varianten der klassischen Problemstellung mit zugehörigen Lösungsmethoden in verschiedenen realistischen Anwendungsszenarien, basierend auf den zuvor erzielten Ergebnissen für das klassische Problem.
  • Halbordnungsbasierte Verhaltensbeschreibungen von Petrinetzen: Als Basis für die von uns entwickelten Synthese-Algorithmen entwickelten wir eine neue einheitliche mathematische Beschreibung für die verschiedenen existierenden Verhaltensmodelle von Petrinetzen. Damit können unsere Resultate auch auf jedes andere Verhaltensmodell von Petrinetzen übertragen werden. Es stellte sich heraus, dass sich aus dieser neuen einheitlichen Beschreibung effizientere Ausführbarkeitstest und Entfaltungsalgorithmen entwickeln ließen. Diese effizienteren Algorithmen wiederum lassen sich gewinnbringend in Teilverfahren der Synthese einsetzen.
  • Synthese-Methoden: Es ergab sich bei Untersuchungen zu effizienteren Synthesealgorithmen, dass es mehrere verschiedene grundlegende Methoden gibt, aus Sprachen ein Petrinetz zu synthetisieren, wobei die optimale Wahl einer Methode im konkreten Fall vom Anwendungskontext abhängt. Kombiniert mit der einheitlichen mathematischen Beschreibung des Verhaltens von Petrinetzen konnten wir alle bisher entwickelten Synthesemethoden als Spezialfälle der von uns entwickelten Verfahren identifizieren.
  • Implementierung: Die entwickelten Syntheseverfahren für S/T-Netze wurden prototypisch in den zwei Tools VIPTool (Eichstätt) und SynopsTool (Augsburg) implementiert und mit Hilfe von aus der Literatur bekannten Fallstudien sowie mit Fallstudien aus den im Projekt betrachteten Anwendungsbereichen evaluiert.
  • Anwendung: Es wurden Vorgehensmodelle für den Werkzeug-unterstützten Modellentwurf im Bereich der Geschäftsprozessmodellierung entwickelt. Hierbei wurden zwei verschiedene Ansätze zur Entwicklung von Geschäftsprozessmodellen betrachtet, nämlich einmal basierend auf Mengen von ad-hoc spezifizierter Beispielsabläufe und einmal basierend auf von Informationssystemen generierten sog. Ereignis-Logs. Gegen Ende der Projektlaufzeit ergab sich mit der Konstruktion sog. Petrinetz-Tranduktoren aus experimentellen Dialog-Daten ein weiteres Anwendungsfeld für Synthesemethoden, welches aber nicht mehr im Projekt ausgearbeitet werden konnte.

Suche