Ressourcenoptimierung von Workflow Problemen

Inhaltsverzeichnis

1 Einleitung
1.1 Workflow Management
1.2 Motivation
1.3 Beitrag der Arbeit
1.4 Aufbau der Arbeit

2 Workflow Problem Spezifikation
2.1 Grundbegriffe
2.2 Datenfluß
2.3 Partitionierung
2.4 Infrastruktur

3 Constraint Programmierung
3.1 Constraint Programmierung mit Finite Domains (FD)
3.2 Propagierung
3.3 Zerlegung
3.4 Exploration
3.5 Modellierung
3.6 Constraint Programmierung mit Finite Sets (FS)

4 Modellierung
4.1 Grundmodell
4.2 Präzises Modell

5 Propagierung
5.1 Basic Constraints
5.2 Non-basic Constraints
5.3 Benutzerdefinierte Constraints
5.4 Schranken

6 Problemzerlegung und Suche
6.1 Hierarchie
6.2 Workflow Heuristiken
6.3 Optimierung
6.4 Finite Set Heuristiken

7 Implementierung
7.1 Aufbau von Woop
7.2 Skript
7.3 Datenstrukturen

8 Evaluierung
8.1 Grundmodell
8.2 Präzises Modell
8.3 Slack
8.4 Zusammenfassung

9 Zusammenfassung
9.1 Verwandte Arbeiten
9.2 Kernpunkte der Arbeit
9.3 Offene Fragen
9.4 Ausblick

A Benchmark
A.1 Plattform
A.2 Problemstellung: Komplexe, flexible Geschäftsprozesse
A.3 Evaluierung

Zusammenfassung

Aktuelle Workflow Management Systeme sind in der Lage, die Durchlaufzeit einzelner Prozesse schon in der Planungsphase zu optimieren. Sie vernachlässigen jedoch die Optimierung von Organisation und Infrastruktur. Dies gilt insbesondere f ür flexible Prozesse mit kontinuierlicher Versorgung.

Eine Optimierung von Organisation und Infrastruktur wird aufgrund von zunehmender Komplexität notwendig. Dies betrifft vor allem die Wirtschaft, in der Zeit und Kapital eine wesentliche Rolle spielen.

Diese Arbeit stellt das mathematische Modell und die Implementierung von Woop vor. Woop löst Optimierungsprobleme f ür flexible Prozesse mit kontinuierlicher Versorgung unter Anwendung der Constraint Programmierung. Optimale L ösungen werden effizient, exakt und generisch approximiert.

Die Implementierung basiert auf dem System Mozart und der Programmiersprache Oz.

Danksagung

Mein größter Dank gebührt meinen Eltern, die mir das Studium ermöglicht haben, und mich während der gesamten Studienzeit unterst ützen.

Weiterhin danke ich meinen Betreuern Christian Schulte und Tobias M üller, die mir dir Tür zur Constraint Programmierung weit ge öffnet und damit mein Interesse geweckt haben. Außerdem danke ich ihnen f ür die zahlreichen Tipps rund um Mozart, Constraints und Diplomarbeit. Ferner danke ich Prof. Dr. Gert Smolka und dem gesamten Lehrstuhl für das hervorragende Arbeitsumfeld.

Weiterer Dank geht an Daniel Bobbert, Thorsten Brunklaus und Esther Niederberger f ür ihre Ideen und Korrekturen.

Kapitel 1 Einleitung

Diese Arbeit stellt das mathematische Modell und die Implementierung von Woop vor. Woop löst Optimierungsprobleme f ür flexible Prozesse mit kontinuierlicher Versorgung unter Anwendung der Constraint Programmierung. Optimale L ösungen werden effizient, exakt und generisch approximiert.

1.1 Workflow Management

Effiziente Geschäftsprozesse in Unternehmen erfordern informationstechnische Infra- strukturen. Ein Workflow Management System (kurz: WFMS) koordiniert die zu ei- nem Geschäftsprozeß gehörenden Aktivitäten gemäß einer Ablaufspezifikation f ür den vorliegenden Prozeßtyp. Die Bearbeitung von Aktivitäten übernehmen Workflow Teil- nehmer.

Moderne Unternehmen sind darauf angewiesen, daß ein WFMS eine große Zahl (kon- tinuierliche Versorgung) von Geschäftsprozessen verschiedenster Typen (flexible Pro- zesse) verläßlich und ohne sichtliche Verzögerung ausführt. Dabei beschreiben drei essentielle Punkte jeden Prozeß: Prozeßlogik, Organisation und Infrastruktur.

Die Proze ß logik gibt den Ausf ührungszeitpunkt einer Aktivität vor. Dagegen legt die Organisation fest, welche Aktivität von welchem Teilnehmertyp ausgef ührt wird. Pro- zeßlogik und Organisation garantieren die korrekte Arbeitsweise des WFMSs.

Die Infrastruktur beschreibt, wieviele Teilnehmer eines bestimmten Typs notwendig sind. Die Infrastruktur eines WFMS ist maßgebend f ür Invest und Durchsatz.

Aus Sicht der Investoren besteht das wichtigste Planungsproblem des Workflow Ma- nagement darin, f ür eine gegebene Menge von Ablaufspezifikationen und f ür einen Mindestdurchsatz die kostengünstigste Organisation und Infrastruktur zu finden. Hier- bei darf nur auf Teilnehmertypen aus einer gestellten Menge zur ückgegriffen werden.

1.2 Motivation

Für die Planer von WFM-Systemen ist es eine schwierige Aufgabe, eine kosteng ünstige Infrastruktur und Organisation zu finden. Umso m ühsamer gestaltet sich bei komplexen Prozessen die Suche nach der optimalen L ösung.

Neben der Kostenoptimierung fordert die Wirtschaft in der Praxis weitere Konzepte:

Betriebsmodus. Es wird zwischen zwei Modi unterschieden: separat und vermischt. Im separaten Betriebsmodus startet das WFMS ausschließlichProzesse eines bestimmten Typs. Im vermischten Betriebsmodus hingegen werden Prozesse verschiedener Typen im vorgegebenen Verhältnis gestartet.

Gerichteter Datenfluß. Ein Objekt, das nach einer Ablaufspezifikation bearbeitet wird, hat eine feste Sequenz von Teilnehmertypen zu durchlaufen. D.h. der Transport von Objekten wird gesteuert. Dadurch ist eine exakte Bestimmung der effektiven Taktzeit, Organisation und Infrastruktur m öglich.

Attributierte Ressourcen. Teilnehmertypen erlangen durch Eigenschaften (Fähigkeiten, lokale Zeitangaben, Stabilität, Kosten, Werkzeuge etc.) präzisere Züge. Jede Eigenschaft übt Einfluß auf Organisation und Infrastruktur aus, was die Komplexität der Problemstellung steigert. Den größten Anteil an der Komplexität haben die Fähigkeiten. Ein Teilnehmertyp ist nicht notwendigerweise ein Spezialist. Die Fähigkeiten der Teilnehmertypen d ürfen beliebig überlappen.

Zur Beschreibung der genannten Problemstellung und zur Entwicklung eines L ösungsverfahrens bedarf es eines genauen, mathematischen Modells, das als Basis ein erweiterbares Grundmodell hat.

1.3 Beitrag der Arbeit

Diese Arbeit stellt eine neue Klasse von Planungsproblemen vor. Es handelt sich um die Optimierung von Organisation und Infrastruktur flexibler Prozesse mit kontinuierlicher Versorgung.

Trotz eines breiten Anwendungsspektrums wird das Planungsproblem erstmals in die- ser Arbeit mathematisch abstrahiert und als ein Workflow Problem modelliert. Dabei wird zunächst ein Grundmodell vorgestellt, das sukzessiv um präzise Informationen (lokale Zeit, Werkzeuge, vermischte Betriebsart) erweitert wird. Das mathematische Grundmodell erlaubt genauere, formale Untersuchungen des Problems.

Als Lösungstechnik wird die Constraint Programmierung gewählt. Sie erlaubt eine di- rekte Umsetzung des mathematischen Modells. Die Umsetzung beinhaltet sowohl aus dem Modell hervorgegangene Constraints als auch spezielle, auf das Problem zuge- schnittene Heuristiken. Die Implementierung trägt den Namen Woop (Workflow Opti- mizer) ¹⁶ und basiert auf dem System Mozart²³ und der Sprache Oz³¹.

Woop ist in der Lage, korrekte und exakte L ösungen generisch aus partiellen Informationen zu berechnen. Das Verfahren ist effizient, skalierbar und approximiert schnell optimale Lösungen.

Darüber hinaus enthält Woop interaktive Komponenten, die den Anwender dabei unterstützen, Einfluß auf die Lösungsverfahren auszuüben. Durch benutzerdefinierte Modellierungsanweisungen werden dem System partielle Informationen über den Lö- sungsraum mitgeteilt. Ferner kann der Anwender verschiedene Heuristiken erstellen und testen.

1.4 Aufbau der Arbeit

Das nachfolgende Kapitel 2 stellt das vorliegende Optimierungsproblem flexibler Ge- schäftsprozesse mit kontinuierlicher Versorgung vor. Kapitel 3 gibt eine Übersicht zur Programmierung mit Constraints. Es bildet die Grundlage f ür die nachfolgenden Ka- pitel. Anschließend wird in Kapitel 4 ein mathematisches Modell f ür das Problem ein- geführt. In Kapitel 5 werden Eigenschaften des Problems und des Modells untersucht, um gegebenfalls weitere Einschränkungen des Suchraums zu erfassen. Das Thema Suche und Heuristik wird detailiert in Kapitel 6 behandelt. Die Kernpunkte der Im- plementierung von Woop werden in Kapitel 7 behandelt. In Kapitel 8 werden die vorgestellten Aspekte evaluiert. Das letzte Kapitel faßt die Ergebnisse zusammen. Ab- schließend werden offene Fragen und der Ausblick diskutiert.

Kapitel 2 Workflow Problem Spezifikation

Der Begriff Workflow wird von der Workflow Management Coalition (WfMC)³³ als teilweise oder vollständige Automatisierung eines Geschäftsprozesses definiert, während der Dokumente, Informationen oder Aufgaben von einem Teilnehmer (einer Ressource) zum anderen gereicht werden, um sie nach einer Menge von prozeduralen Regeln zu bearbeiten.

In diesem Kapitel wird das zu untersuchende Problem vorgestellt. Es handelt sich um ein Optimierungsproblem f ür einen Workflow, der aus flexiblen Geschäftprozessen mit kontinuierlicher Versorgung besteht. Die hier benutzten Begriffe sind an die standar- disierten Definitionen der WfMC angelehnt und werden teilweise erweitert.

Dieses Kapitel beginnt zunächst mit der Erklärung der Grundbegriffe von Geschäfts- prozessen. Insbesondere wird das Workflow Problem mit kontinuierlicher Versorgung von klassischen Schedulingproblemen abgegrenzt. Anschließend wird erkl ärt, wie ei- ne Menge von Prozessen im Datenfluß eingesetzt wird, und wie jeder Ablaufplan eines Prozesses zu lesen ist. In jedem der folgenden Abschnitte werden Teile des Lösungsweges skizziert.

2.1 Grundbegriffe

Ein Geschäftsproze ß (Business Process) beschreibt die in einer realen Welt miteinander vernetzen Teilprozesse bzw. Aktivitäten, die gemeinsam eine übergeordnete Aufgabe lösen. Beispiele hierf ür sind Reklamation oder Bestellannahme in einem Call Center. Ein Bestellvorgang besteht aus mehreren aufeinander folgenden Arbeitsschritten, die von Personen, Maschinen oder Software ausgef ührt werden.

Die Abbildung eines Geschäftsprozesses in eine f ür ein Workflow Management Sy- stem verständliche Darstellung wird als Proze ß definition (Process Definition) bezeich- net. Diese Modellierung beinhaltet alle stattfindenden Aktivitäten, einen Zeitplan be- züglich der Aktivitäten, sowie alle Ressourcen, die diese Aktivitäten ausführen. Die Prozeßdefinition wird an ein Workflowsystem übergeben, welches mit dieser Informa- tion Instanzen der Prozeßdefinition ausf ühren kann. Eine Prozeßdefinition, die aus- schließlich auf Computern eingesetzt wird, heißt Workflowdefinition und ihre Instanz einfach Workflow.

Jeder Geschäftsprozeß besteht aus drei orthogonal aufgebauten Ebenen. Leymann und Roller legen die Ebenen in¹⁹ wie folgt fest:

1. Prozeßlogik Welche Aktivität soll zu welchem Zeitpunkt ausgef ührt werden?
2. Organisation Wer führt welche Aktivität aus?
3. Infrastruktur Welche Ressourcen sind in welcher Anzahl notwendig?

Diese Arbeit widmet sich der Aufgabe, Prozeßdefinitionen aus partiellen Informatio- nen gemäß der formulierten Ziele und Kriterien zu bestimmen. Zu den wichtigsten Eingangsinformationen geh ören relative Ablaufvorgaben sowie Ressourcentypen.

Unter einem Ablauf versteht man eine relative Reihenfolge von Aktivitäten. Im Ge- gensatz zu einem Zeitplan, in dem der Ausf ührungszeitpunkt jeder Aktivität bekannt ist, legt der relative Ablauf zeitliche Rahmenbedingungen fest, die durch Relationen zwischen Aktivitäten ausgedrückt werden. Im folgenden wird von einem Ablauf ge- sprochen, wenn die relative Reihenfolge von Aktivitäten gemeint ist, und es wird von einem Zeitplan gesprochen, wenn die exakten Ausführungszeiten gemeint sind.

Den Zeitpunkt und die Art der Prozeßausf ührung bestimmt der Modus. Er legt fest, wieviele verschiedene Prozeßdefinitionen gleichzeitig instanziiert werden dürfen. Ablauf und Modus bilden zusammen den Datenflu ß.

Beispiel 2.1.1. In einem Call Center f ür Druckaufträge wird eine Bestellung per Te- lefon von einem Operator entgegengenommen. Anschließend wird sie an die Druck- abteilung weitergeleitet, wo ein Drucker den Ausdruck übernimmt. Zuletzt stellt der Lieferbote die Ware zu. Die Aufgabe besteht darin, die kostengünstigste Prozeßdefini- tion zu bestimmen.

In diesem Beispiel werden drei Ressourcen angegeben: Operator, Kopierer und Lieferbote. Der Lieferbote ist ein Mensch, der Drucker eine Maschine und der Operator kann entweder ein Mensch oder eine mit Sprachtechnologie ausgestattet Software sein. Die nachfolgende Tabelle hält die Ressourcen mitsamt ihren Kosten fest.

Abbildung in dieser Leseprobe nicht enthalten

Die Ressourcen f ür Start und Ende verursachen keine Kosten. Sie simulieren Ressour- cen, die eine Start- und eine Endaktivität ausführen und dienen lediglich als Orientie- rungspunkte. Diese Ressourcen werden auch Sonderressourcen genannt. Desweiteren erkennt man, daß die Auswahl zwischen einem Menschen und einem Programm als Operator gegeben ist. Hierbei ist das Programm g ünstiger, da es keine monatlichen Gehaltskosten verursacht. Allerdings sollte der Mensch zumindest aufgrund der Viel- falt seiner Fähigkeiten den Vorzug erhalten. Die endg ültige Wahl wird entsprechend der geforderten Aktivitäten getroffen.

Die Aktivitäten im Beispiel unterliegen einer typischen, relativen Reihenfolge. Die nachfolgende Tabelle listet alle geforderten Aktivitäten mitsamt ihrer Kodierung (Spal- te A) auf. In der Prozeßdefinition werden üblicherweise ganze Zahlen als Namen f ür Aktivitäten verwendet. Zu jeder Aktivität wird zusätzlich angegeben, welche Ak- tivitäten zuvor ausgef ührt werden müssen, und welche Ressource (Spalte T) diese ausführen kann.

Abbildung in dieser Leseprobe nicht enthalten

Analog zu der Start- und Endressource liegt die Start- und Endaktivität vor. Die Star- taktivität hat keinen Vorgänger. Sowohl ein Mensch als auch ein Programm kann in der Rolle des Operators Lieferboten anfordern und Druckbestellungen entgegennehmen. Aber nur ein menschlicher Operator ist in der Lage ein passendes, fantasievolles Co- ver zu entwerfen. Daraus ist zu schließen, daß mindestens ein menschlicher Operator in der Prozeßdefinition vorkommen muß, da alle aufgef ührten Aktivitäten ausgeführt werden müssen. Ob die Prozeßdefinition nur menschliche oder beide Operatortypen enthält, hängt davon ab, welches Ziel und welche Vorgaben gesetzt wurden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Ablauf: Bestellannahme einer Druckware

Zur Veranschaulichung eines Ablaufs werden Flu ß diagramme oder allgemeiner ausge- drückt, gerichtete, azyklische und zusammenhängende Graphen benutzt. Die Knoten eines Graphen entsprechen Aktivitäten, während Kanten als Vorrangsrelationen inter- pretiert werden. Eine Kante von nach bedeutet, daß Aktivität unbedingt vor Ak- tivität ausgeführt werden soll. Jeder Graph enthält genau eine Startaktivität (Knoten ohne Vorgänger) und genau eine Endaktivität (Knoten ohne Nachfolger). Zum Beispiel zeigt Abbildung 2.1 einen Graphen der den relativen Aktivitätenfluß der Bestellannah- me aus Beispiel 2.1.1 darstellt.

Das Beispiel ist einfach gehalten. Die Fähigkeiten der Ressourcen überlappen sich kaum. Damit ist es leicht, eine konkrete Organisation anzugeben. Bei gr ößeren Prozes- sen und flexibleren Ressourcen sind die Überlappungen wesentlich gr ößer. Dort fällt die Ermittlung einer guten Organisation schwieriger aus. Es ergeben sich vielf ältige Kombinationsmöglichkeiten, deren Berechnung ohne Computerunterst ützung unmög- lich ist.

Eine Proze ß instanz (Process Instance) ist eine zustandsbehaftete, konkrete Ausf üh- rung einer Prozeßdefinition. Der Zustand wechselt nach jeder Beendigung einer Ak- tivität, und gibt Auskunft über das Voranschreiten der Instanz. Innerhalb einer Pro- zeßinstanz wird ein Objekt (Object) von Ressource zu Ressource gereicht und durch Aktivitäten verändert. Der aktuelle Zustand der Instanz ist am Objekt nachvollzieh- bar. Das Objekt entspricht dem Produkt eines Geschäftsprozesses, beispielsweise der Lieferung einer Druckware.

2.1.1 Kontinuierliche Versorgung

Bekannte Schedulingprobleme wie zum Br ückenbau [5, 10] oder JobShop [2, 11, 17, 5, 10] suchen nach Lösungen, die insbesondere die Prozeßlogik optimieren. Hierbei ist lediglich die Durchlaufzeit eines einzelnen Objektes relevant. Die Durchlaufzeit ist die Zeit, die die Bearbeitung eines vollständigen Prozesses in Anspruch nimmt. Es wird demnach versucht, eine passende Organisation anzugeben, die eine optimale Prozeßlogik erf üllt. Problematisch wird es, wenn die Organisation und die Infrastruk- tur kontinuierlich mit neuen Objekten versorgt werden. Dann ist die Frage nach dem Durchsatz von Objekten viel interessanter, d.h. wieviele Objekte k önnen pro Zeitraum einen kompletten Prozeß durchlaufen?

Die kontinuierliche Versorgung kann nur so schnell wie die langsamste Ressource sein (bottleneck Problematik). Eine Ressource ist nicht unbedingt im Sinne der Geschwin- digkeit langsam. Vielmehr muß darauf geachtet werden, ob sie langandauernde Ak- tivitäten besitzt, und ob die Organisation der Ressource übermäßig viele Aktivitäten zugewiesen hat. Übertragen auf das Beispiel 2.1.1 heißt dies, daß die Auslieferung ei- ner Drucksache wesentlich mehr Zeit in Anspruch nimmt als beispielsweise der Druck selbst. Es wird also die Bearbeitungszeit eines Teilnehmers f ür eine Menge von Akti- vitäten betrachtet. Setzt man die Bearbeitungszeit ins Verhältnis zur Anzahl der Teil- nehmer, so ergibt dies die effektive Taktzeit. Sie ist das k ürzeste Zeitintervall zwischen zwei Prozeßinstanzen.

Angenommen, es liegt eine Prozeßdefinition vor, in der eine Ressource die maximale Taktzeit von 500 Minuten aufweist. Dann wird alle 500 Minuten ein neuer Prozeß instanziiert. Steht der Auftraggeber unter Zeitdruck und will alle 300 Minuten einen Prozeß starten, dann w ürde spätestens an der Ressource ein Stau entstehen, der fortwährend wachsen würde. Folgerichtig muß die Taktzeit für vermindert werden. Hierzu stehen zwei M öglichkeiten zur Verf ügung:

Umverteilung von Aktivit äten. Falls möglich, sollten Aktivitäten auf andere Res- sourcen umverteilt werden. In diesem Fall ist eine Überlappung von Aktivitäten verschiedener Ressourcen sehr hilfreich. Weniger beschäftigte Ressourcen fül- len nun ihre Wartezeiten mit den Aktivitäten überladener Ressourcen.

Aufstocken von Ressourcen. Ist eine Umverteilung nicht m öglich, oder f ührt sie zu keinem besseren Ergebnis, muß eine weitere Ressource desselben Typs wie hinzugefügt werden. Damit entlastet die Ressource . Die Taktzeit würde sich für auf 250 Minuten halbieren.

Ziel ist eine Ausbalancierung aller Taktzeiten. Das Ergebnis der Ausbalancierung ist eine veränderte Infrastruktur. Durch die Hinzunahme einer weiteren Ressource wird der Infrastruktur ein weiterer Aspekt hinzugefügt: die Erhöhung der Kosten. Die Ko- sten sind die wichtigsten Faktoren in der Wirtschaft und müssen so gering wie möglich gehalten werden. Sowohl die Infrastruktur als auch die Kosten sind Punkte, die von ty- pischen Schedulingproblemen nicht bedacht werden. Im Gegensatz dazu entwerfen die Schedulingalgorithmen einen exakten Zeitplan f ür die Problemstellung. Die hier vorgestellte Klasse von Problemen begn ügt sich mit einem relativen Ablauf. Es ist unwesentlich, in welcher Reihenfolge eine Ressource ihre Aktivitäten ausführt. Die Taktzeiten und die Kosten sind davon v öllig unabhängig, womit eine Festlegung auf einen Zeitplan wegfällt.

Ohne auf die exakte Ermittlung der Infrastruktur zum oben genannten Beispiel 2.1.1 einzugehen, die in Kapitel 4 näher erläutert wird, soll dennoch eine geeignete L ösung angeben werden. Abbildung 2.2 gibt eine vollständige Organisation und Infrastruktur an. Demnach werden drei Operatoren ben ötigt sowie zwei Drucker und f ünf Lieferbo- ten.

2.1.2 Aktivit äten

Eine Aktivität (Activity, Job) ist ein logischer, atomarer Schritt innerhalb einer Pro- zeßdefinition. Jede Aktivität wird in einer Prozeßinstanz von einer Ressource genau einmal ausgeführt. Ziel ist es, eine gute Organisation anzugeben, die zu g ünstigen Ko- sten und zu einer minimalen, effektiven Taktzeit f ührt. Beide Größen werden durch die Bearbeitungszeit einer Aktivität sowie die Werkzeuge einer Aktivität beeinflußt.

Die Zeit, die die Ausf ührung einer Aktivität in Anspruch nimmt, wird Bearbeitungszeit (Processing Time) genannt. Die Summe aller Bearbeitungszeiten in einem Block ist ein wesentlicher Bestandteil der Blockbearbeitungszeit, welche großen Einfluß auf die Anzahl von Teilnehmern hat (siehe Abschnitt 2.4). Hierbei wird zwischen globaler und

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Organisation und Infrastruktur: Bestellannahme einer Druckware

lokaler Bearbeitungszeit unterschieden, wobei vor der Planung eine Zeitart festzulegen ist.

Globale Bearbeitungszeit. Jede Aktivität wird, gleich von welcher Ressource, im- mer in der gleichen Zeit bearbeitet. Man betrachte hierzu erneut das Beispiel

2.1.1. Demnach würde die Aktivität Lieferboten anfordern von beiden Operatoren Software und Mensch die gleiche Zeit in Anspruch nehmen.

Lokale Bearbeitungszeit. Diese Angabe ist ressourcenspezifisch. Je nachdem wel- che Ressource eingesetzt wird, ändert sich die Bearbeitungszeit. Diese Angabe ist der Realität näher, da eine Software automatisch ein Signal absetzen kann, wohingegen der Mensch lange Telefonierzeiten braucht. Der Nachteil der ge- wonnenen Präzision ist die Unbestimmtheit der Bearbeitungszeit. Obwohl der relative Zeitpunkt der Aktivität möglicherweise einfach zu bestimmen ist, muß der Ressourcentyp nicht unbedingt bekannt sein. Demnach kann nur ein Be- reich der Bearbeitungszeit angegeben werden: der zwischen der k ürzesten und längsten Dauer.

Hat eine Ressource zwei Aktivitäten zu bearbeiten, ben ötigt auch der Wechsel von der einen Aktivität zur anderen eine Zeitspanne, U ¨ bergangszeit (Transition Time) genannt. Die Übergangszeit wird als eine Konstante angenommen. Dies reduziert die Komple- xität, da nicht zwischen allen möglichen Aktivitätspaaren unterschieden wird. In der

Regel sind die Abweichungen von der durchschnittlichen Übergangszeit zu gering, um signifikant zu sein. Auch die Summe der Übergangszeiten in einem Block ist ein Teil der Blockbearbeitungszeit.

Eine Erweiterung von Aktivitäten ist die Angabe der zu benutzenden Werkzeuge (Ac- tivity Tools). Eine Aktivität wird von einer Ressource nur dann ausgeführt, wenn ihr Werkzeugmagazin die Werkzeuge, die f ür die Aktivität benötigt werden, bereitstellt. Werkzeuge sind demnach eine weitere Definition f ür Aktivitäten und steigern damit die Komplexität des Problems. Da die Aktivitäten atomar sind, bleiben die Werkzeug- anwendungen ebenfalls atomar. Die Anwendungsreihenfolge der Werkzeuge ist nicht relevant. Weitere Informationen zu Werkzeugen werden im nächsten Abschnitt vorge- stellt.

Aktivitäten können zu einer Aktivitätengruppe (Activity Block) bezogen auf bestimmte Eigenschaften, wie zum Beispiel die Zugeh örigkeit zu einem gemeinsamen Ressour- centyp, zusammengefaßt werden. Aus dem oben genannten Beispiel 2.1.1 gehen die Gruppen , , , und hervor. Diese Gruppen wer- den auch Blöcke genannt.

2.1.3 Teilnehmer

Die WfMC verwendet f ür eine Ressource das Synonym Workflow Teilnehmer (Workflow Participent). Im folgenden werden beide Begriffe gleichwertig benutzt. Workflow Teilnehmer können sowohl menschliche, maschinelle als auch softwaretechnische (Intelligente Agenten) Ressourcen sein. Jeder Teilnehmer hat einen bestimmten Typ, der durch eine Reihe von Eigenschaften bestimmt wird. Hierzu zählen insbesondere Einsatzfähigkeiten, Kosten und Stabilität.

Unter Einsatzfähigkeiten versteht man die prinzipiell m öglichen Aktivitäten, die ein Teilnehmertyp anbietet. In der Realität wird oftmals nur eine Teilmenge dieser Ak- tivitäten eingesetzt. Die Wahl eines geeigneten Teilnehmertypen hängt von einer zu- grundeliegenden Menge von Aktivitäten ab. Es kann nur der Typ zum Einsatz kommen, der alle Aktivitäten dieser Menge durch seine Einsatzfähigkeiten abdeckt.

Zur Ausführung von Aktivitäten werden Werkzeuge ben ötigt. Dabei darf eine Aktivität auch mehrere Werkzeuge verlangen. Zwei Aktivitäten und dürfen auf gemeinsame Werkzeuge zugreifen, wenn beide ein gleiches Werkzeug verwenden. Damit existiert eine Ü berlappung vonWerkzeugen.

Jeder Teilnehmertyp hat ein beschränktes Werkzeugmagazin. Dies hat zur Folge, daß ein kleines Magazin nur wenige Werkzeuge aufnehmen kann, und somit nur eine klei- ne Auswahl der Fähigkeiten zur Verf ügung stellt. Damit ist die Auswahl von Akti- vitäten wichtig. Da alle Aktivitäten ein gemeinsames Werkzeugmagazin teilen, ist ei- ne hohe Überlappung wünschenswert, weil mehr Platz f ür weitere Werkzeuge und Aktivitäten vorhanden wäre. Ein Werkzeugmagazin kann man mit einem Schreibtisch vergleichen, auf dem begrenzt Platz ist, so daß nur wenige Utensilien darauf gela- gert werden, und nur die eingesetzt werden, die f ür die Aufgaben notwendig sind. Ein Werkzeug auf dem Schreibtisch kann der Computer sein. Er wird sowohl f ür die

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Zeitablauf

Aktivität Aufnahme von Kundendaten als auch f ür die Aktivität interne E- Mail Benachrichtigung verwendet. Durch gemeinsame Nutzung des Compu- ters wird der Fall ausgeschlossen, daß für jede Aktivität ein eigener Computer ange- schafft wird.

Eine Instanz einer Aktivität heißt aus Sicht des Teilnehmers, der sie ausf ührt, Arbeit (Work Item). Ein Teilnehmer kann nur eine Arbeit gleichzeitig verrichten. Stehen meh- rere Arbeiten an, so müssen diese an eine Warteliste (Worklist) angehängt werden.

Die Annahme eines Objektes zur Bearbeitung kostet Zeit, R ü stzeit (Setup Time) ge- nannt. Neben der Rüstzeit fallen f ür jede Aktivität Bearbeitungszeiten an (lokal/global). Den Zeitablauf eines Objektes während der Bearbeitung durch einen Teilnehmer zeigt Abbildung 2.3. Die Bearbeitungszeit eines Objektes in einem Block heißt Blockbear- beitungszeit (abgek ürzt bbz). Die Rüstzeit setzt sich aus den beiden Zeiten und zusammen, die während der Annahme und der Abgabe eines Objektes anfallen. Nach der Annahme werden alle dem Teilnehmer zugewiesenen Aktivitäten am Objekt aus- geführt, ohne dabei das Objekt zwischenzeitlich abzugeben. Die Dauer des Wechsels von einer Aktivität auf die nächste ist schließlich die Übergangszeit.

Ein Teilnehmer kann unter Belastung ausfallen. Dadurch treten zwei Probleme auf.

Stillstand. Gibt es keine Ersatzteilnehmer, kann es zu einem Workflow Stillstand kommen.

Stau. Können andere Teilnehmer die Arbeiten eines ausgefallenen Teilnehmers nicht in der geforderten Zeit ausführen, kommt es zu einem Stau. Dies führt zu einer erhöhten Durchlaufzeit (bzw. effektiven Taktzeit).

Beide Probleme werden durch den Einsatz zusätzlicher Teilnehmer gel öst. Die Wahr- scheinlichkeit von Ausfällen wird durch eine prozentuale Stabilitätsangabe eines Teil- nehmertyps ausgedr ückt. Zuverlässige Teilnehmertypen haben eine hohe Stabilität, na- he bei 100 %. Unzuverlässige Teilnehmertypen haben dagegen eine Stabilität nahe bei

0 %. Die Stabilitätsangabe wird direkt zur Berechnung der notwendigen Teilnehmerzahl benutzt. Für weitere Informationen wird auf Abschnitt 4.1.4 verwiesen.

Eine andere Art des Ausfalls ist der Ausfall eines Werkzeugs. Hier gilt eine ähnliche Argumentation wie beim Ausfall eines Teilnehmers. Ein Werkzeugersatz wird Schwe- sterwerkzeug genannt. Die Anzahl der Schwesterwerkzeuge ist vorgegeben. Dies hat extremen Einfluß auf das Werkzeugmagazin. Angenommen, es existiert ein Teilneh- mer mit einem Werkzeugmagazin von 30 Plätzen und es gilt, daß jedes Werkzeug im Magazin ein Schwesterwerkzeug hat. Dann sind nur noch 15 Plätze für verschiedene Werkzeuge frei. Wird die Zahl der Schwesterwerkzeuge auf zwei erh öht, so kommen nur noch 10 verschiedene Werkzeuge in Frage.

Auch die Teilnehmer k önnen zu einer gemeinsamen Gruppe eines gemeinsamen Typs (Worklflow Participant Block) zusammengefaßt werden. Sie bilden gewissermaßen einen großen Teilnehmer und besitzen eine gemeinsame Warteliste. Liegt noch Arbeit vor und ist ein Teilnehmer bereit, akzeptiert er die Arbeit. Durch solche Gruppenbil- dungen werden Taktzeit und Ausfallrisiko, welches sonst einen kompletten Workflow blockieren kann, verringert. Die Abbildung 2.10 auf Seite 28 zeigt eine andere Darstel- lung der Infrastruktur zum oben genannten Beispiel 2.1.1. Nach wie vor besteht es aus f ünf Blöcken. Der erste und der letzte Block sind Sonderbl öcke, die den Start- bzw. Endteilnehmer darstellen, und kommen daher jeweils einmal vor. Dagegen besteht der zweite Block aus drei, der dritte aus zwei und der vierte aus f ünf Teilnehmern.

Die Aufgabe besteht darin, eine passende Infrastruktur zu finden. Zu jedem Block soll jeweils der beste Teilnehmertyp in ausreichender Anzahl ermittelt werden. F ür vertie- fende Modell- und Lösungsbetrachtungen soll auf das Kapitel 4 verwiesen werden.

2.2 Datenfluß

In diesem Abschnitt werden zwei Eigenschaften des Datenflusses betrachtet: Ablauf und Modus. Der Ablauf gibt die relative Ausf ührungsreihenfolge von Aktivitäten vor, d.h. wie ein Prozeß durchlaufen wird. Dagegen bestimmt der Modus, wie eine Men- ge von Prozeßdefinitionen zu behandeln ist. So wird zunächst auf die grafische Re- präsentation eines Ablaufs eingegangen, und dann erklärt, welche Ablaufstrategien es gibt. Anschließend werden zwei Modi vorgestellt, die in dieser Anwendung zum Ein- satz kommen.

2.2.1 Ablauf

Die Darstellung von Abläufen ermöglichen gerichtete, azyklische und zusammenhän- gende Graphen. Alle im Graphen vorkommenden Knoten repräsentieren Aktivitäten. Eine Kante ist eine Vorrangsrelation zwischen zwei Aktivitäten, wobei die Quelle der Kante die Vorgängeraktivität und das Ziel die Nachfolgeraktivität ist. Für eine Kan- te von nach schreiben wir . Jeder Ablauf enthält genau eine Startakti- vität (Knoten ohne Vorgänger) und genau eine Endaktivität (Knoten ohne Nachfolger).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.5: OR Split / OR Join

In diesem Zusammenhang heißt dieser Graph auch Vorranggraph. Ein typischer Vor- ranggraph wurde bereits vorgestellt (siehe Abbildung 2.1 auf Seite 17). Dieser Graph enthält eine Kante von Knoten 12 zu Knoten 14, wobei 12 die Vorgängeraktivität und 14 die Nachfolgeraktivität ist. Diese Kante bedeutet, daß die Aktivität 12 unbedingt vor 14 in der zeitlichen Abfolge bearbeitet werden soll. Aktivitätenpaare, die in keiner Relation zueinander stehen, sind zeitlich unabhängig. Ein Beispiel f ür diesen Fall sind die Knoten 11 und 12, die auf keinem gemeinsamen Pfad liegen.

Die WfMC schlägt zwei Ausführungsstrategien vor: Parallel Routing und Sequential Routing. Parallel Routing erlaubt die gleichzeitige Bearbeitung mehrerer Aktivit äten an einem Objekt. Im Gegensatz dazu fordert Sequential Routing die sequentielle An- wendung von Aktivitäten. Ein Prozeß kann beide Strategien beinhalten. Beispielswei- se besteht die Reklamation zunächst aus sequentiellen Schritten, wie Aufnahme von Kundendaten und der Beschreibung des Produkts. Die Anfragen über den Verbleib des Produkts werden anschließend parallel auf mehrere Lager verteilt.

In der Darstellung des Parallel Routing werden AND-Splits und AND-Joins (Abbil- dung 2.4) verwendet. Ein AND-Split verzweigt in mehrere nebenläufige Teilprozesse und kommt am AND-Join wieder zusammen. Dazwischen laufen beliebige Teilpro- zesse ab.

Desweiteren existieren für Parallel ebenso wie für Sequential Routing Entscheidungs- möglichkeiten (Kontrollfluß), dargestellt durch OR-Splits und OR-Joins (Abbildung 2.5). Je nachdem welcher Fall beim OR-Split eintritt, werden die entsprechenden Aktivitäten in einem Teilprozess ausgeführt. Dies beinhaltet, daß die Aktivitäten, die zu den konträren Teilprozessen geh ören, überhaupt nicht bearbeitet werden. Mehrere Teilprozesse münden wieder in einen OR-Join.

Das Workflow Problem enthält sehr einfache Abläufe, die von einem strikten sequentiellen Routing ausgehen. Damit entfallen AND-Splits und AND-Joins. Zu jedem Zeitpunkt wird ein Objekt maximal von einer Aktivität bearbeitet.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.6: Ablauf: Reklamation einer Druckware

Darüber hinaus wird verlangt, daß jede Aktivität im Ablauf irgendwann ausgef ührt wird. Dies schließt OR-Splits und OR-Joins ebenfalls aus. Allerdings k önnen die- se simuliert werden, indem f ür jede mögliche Alternative eines OR-Splits ein eige- ner Ablauf angelegt wird. Die Menge der daraus entstandenen Abläufe geht in den Lösungsprozeß ein. Wie dieser Vorgang abläuft, wird im nächsten Abschnitt erklärt.

2.2.2 Modus

Der Problemstellung liegt eine Menge von Abläufen vor. Eine Lösung, insbesondere eine Infrastruktur, muß die Relationen aller Abläufe erfüllen. Auf die reale Welt übertragen heißt dies beispielsweise, daß in einem Call Center eine Bestellung und eine Reklamation von denselben Teilnehmern durchgef ührt werden kann.

Für die Bearbeitung mehrerer Prozeßdefinitionen stehen zwei Modi zur Verf ügung: der separate und der vermischte Datenfluß.

Im separaten Datenflu ß darf zu jedem Zeitpunkt maximal eine Prozeßdefinition aktiv vertreten sein, d.h. eine Menge von Teilnehmern nimmt entweder nur Bestellungen oder nur Reklamationen entgegen. Der Graph eines separaten Datenflusses bzw. Ab- laufs entsteht aus der Vereinigung der Knoten und Kanten aller Ablaufgraphen der Problemstellung.

Angenommen, Beispiel 2.1.1 wird durch einen weiteren Ablauf, wie in Abbildung 2.6 dargestellt, ergänzt. Die Interpretation des neuen Ablaufs soll hier nicht von Belang sein. Es soll sich um eine allgemeine Form der Reklamation von Druckwaren handeln. So erhält man aus beiden Abläufen einen Graphen f ür den separaten Datenfluß, indem die Vereinigung wie beschrieben gebildet wird. Abbildung 2.7 zeigt das Resultat.

Dagegen ist im vermischten Datenflu ß die gleichzeitige Bearbeitung mehrerer Pro- zeßdefinitionen erlaubt. Der Workflow enthält Objekte aller Prozeßdefinitionen, deren

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.7: Beispiel Druckware: separater Datenfluß

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.8: Beispiel Druckware: vermischter Datenfluß

Zahl einem vorgegebenen Verhältnis entspricht.

Um einen Graphen für den vermischten Datenfluß zu erhalten, muß man in zwei Schritten vorgehen. Erst werden alle Aktivitätsnamen so umbenannt, daß zwei Abläufe nie gemeinsame Aktivitätsnamen besitzen. Start- und Endaktivität bleiben hierbei un- verändert. Semantisch gesehen ändert die Umbenennung nichts, da Aktivitäten über Werkzeuge definiert werden. Nach der Umbenennung wird wieder eine Vereinigung aller Abläufe gebildet.

Abbildung 2.8 zeigt einen Graphen f ür den vermischten Datenfluß zum oben genann- ten Beispiel der Druckware. Anhand der Graphen für den separaten und vermischten Datenfluß kann die Notwendigkeit der Umbenennung demonstriert werden. Beim se- paraten Datenfluß wird immer nur nach einer Prozeßdefinition gearbeitet. Es ist zu je- dem Zeitpunkt klar, welche Aktivitäten erlaubt und welche verboten sind. Das Work- flow System muß zwischen Prozeßdefinitionen umschalten, wenn es neue Aufgaben zu erfüllen hat. Beim vermischten Datenfluß sind mehrere Prozeßdefinitionen gleich- zeitig aktiv. Bildet man beispielsweise die Vereinigung aller Abläufe ohne vorherige Umbenennungen, besteht die Gefahr, daß zusätzliche, ungewollte Kanten entstehen. Am Beispiel der Bestellung sieht man, daß die Aktivitäten 12 und 13 voneinander unabhängig sind. Durch die Vereinigung wird jedoch eine Kante aus der Reklamation hinzugef ügt, die die Freiheit der Platzierung von Aktivitäten einschränkt.

2.3 Partitionierung

Ein Mittel zur Bestimmung der Organisation ist die Partitionierung. Die Partitionie- rung ist ein Vorgang, bei dem die Aktivitäten eines separaten bzw. vermischten Da- tenflusses in paarweise disjunkte Mengen aufgeteilt werden. Bei diesen Mengen spricht man auch von Blöcken. Zu jeder Aktivitätsmenge eines Blocks geh ört eine Infrastruktur, die aus Teilnehmern gleichen Typs bestehen. Jeder Teilnehmer des Blocks führt nach Erhalt eines Objektes nur die Aktivitäten des Blocks aus. Neben der Organisation ist ein gerichteter Datenfluß (Abschnitt 2.3.1) ein weiteres Ziel der Partitionierung. Dieser zentrale Vorgang hat gr ößten Einfluß auf Prozeßlogik, Organi- sation und Infrastruktur.

Die Prozeßlogik wird durch die Abläufe der Problemstellung bestimmt. Jede Kante eines Ablaufs gibt die relative Ausführungsreihenfolge vor. Mit Hilfe der Kanten wird bestimmt, welche Aktivität welcher Menge zugewiesen werden soll, und f ührt damit eine Ordnung auf den Mengen ein. Es gilt die Regel: ist eine Kante, die besagt, daß Aktivität vor ausgeführt werden soll, so liegen die Aktivitäten entweder in einer gemeinsamen Menge , oder Aktivität liegt in einer Menge und Aktivität liegt in einer Menge mit Die Partitionierung wird anhand eines gefärbten Graphen veranschaulicht. Aktivitäten, die in einer gemeinsamen Menge liegen, sind einheitlich gefärbt. Die Abbildung 2.9 zeigt einen gefärbten Graphen f ür den separaten Datenfluß des Beispiels 2.1.1 (siehe Seite 16). Der Graph wurde in f ünf Mengen partitioniert. Die Aktivitäten 0 und 100 bilden trotz gleicher Färbung zwei Mengen, um deren Sonderrolle für Start und Ende zu demonstrieren. Die Menge besteht aus den Aktivitäten 11, 12, 15; die Menge aus 14 und 16; und schließlich die Menge aus 13, 17, 18 und 19.

Es muß beachtet werden, daß die hier vorgestellte Zuordnung der Aktivitäten ebenfalls relativen Charakter hat. Das heißt, daß eine Aktivität nicht notwendigerweise auf eine Menge festgelegt werden kann. Es ist wahrscheinlicher, daß eine Aktivität mehreren Mengen zugewiesen werden kann. Dies hat zur Folge, daß alle M öglichkeiten der Par- titionierung überprüft werden müssen, indem dem System sukzessive weitere partielle Informationen gegeben werden. Dieser Vorgang heißt Suche und wird im Kapitel 6 detailliert vorgestellt.

Auch mit einer teilweisen Partitionierung kann eine geeignete Organisation angegeben werden. Für jede Menge muß untersucht werden, welcher Teilnehmer die geforder- ten Aktivitäten prinzipiell zur Verfügung stellt. Sind mehrere Möglichkeiten gegeben, so wählt man den günstigsten Teilnehmertyp. Auch die eingesetzten Teilnehmerty- pen können im Graph dargestellt werden. Die Färbung der Knoten zeigt nicht nur die Angehörigkeit zu einer gemeinsamen Aktivitätenmenge sondern auch zu einem ge- meinsamen Teilnehmertyp an.

Sind die Mengen und ihre Teilnehmertypen bekannt, ist es m öglich, eine Aussage

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.9: Beispiel Druckauftrag: Partitionierung separater Datenfluß

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.10: Anordnung Teilnehmerbl öcke

über die Infrastruktur zu geben. Aus der Summe der Bearbeitungszeiten der Akti- vitäten wird die Blockbearbeitungszeit pro Block gebildet, die ein wesentliches Maß f ür die Anzahl der notwendigen Teilnehmer im jeweiligen Block ist. Eine passende Infrastruktur bezüglich des separaten Datenflusses zum oben genannten Beispiel (Ab- bildung 2.7) zeigt Abbildung 2.10. Man erkennt eine Einteilung des Graphen in f ünf Blöcke. Jeder Block ist einheitlich gefärbt und entspricht einem Teilnehmertyp. Die Färbung der Infrastruktur reflektiert die Färbung des Ablaufgraphen. Die Aktivitäten 11, 12 und 15 der Menge werden vom Teilnehmertyp , der dreifach vorkommt, ausgeführt. Zufällig handelt es sich hier um die gleiche Infrastruktur wie f ür die Be- stellannahme. Dies ist ein Indiz daf ür, daß zwischen Bestellung und Reklamation nur geringe Unterschiede vorliegen.

2.3.1 Gerichteter Datenfluß

Die Partitionierung ist das Instrument, das einen gerichteten Datenfluß gewährleistet. Durch sie kann eine geeignete Teilnehmerordnung (Abbildung 2.10) angeben werden. Diese Ordnung ist so zu interpretieren, daß kein Objekt, welches von einem beliebigen Teilnehmer aktuell bearbeitet wird, im nächsten Arbeitsschritt an einen Vorgängerteilnehmer von weitergereicht wird. Der nächste Arbeitsschritt kann somit nur von selbst oder von einem Nachfolger ausgef ührt werden.

Der gerichtete Datenfluß gibt eine bessere Abschätzung der effektiven Taktzeit an, da sich alle Objekte nur in eine Richtung bewegen. Gäbe es diese Ordnung nicht, wäre es ungewiß, wieviel Zeit ein Objekt außerhalb seiner Ressourcen (Transport, Wartestel- lung) verbringt.

2.3.2 Sonderaktivit äten

Sonderaktivitäten, wie Start und Ende (0 und 100), k önnen simuliert werden, indem ihre Bearbeitungszeiten und die Kosten ihrer speziellen Teilnehmertypen auf Null ge- setzt werden. Somit spielen sie in der Ermittlung der Gesamtkosten keine Rolle. Wei- tere Sonderaktivitäten können überall in Ablaufsplänen platziert werden. Sie bieten

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.11: Mehr Übersicht durch Sonderaktivitäten

Einsatzmöglichkeiten als Sammelknoten f ür Graphen, die f ür eine bessere Überschau- barkeit sorgen. Insbesondere eignen sie sich zur Vereinfachung von Graphen (siehe Abbildung 2.11).

2.4 Infrastruktur

Die Infrastruktur macht den Hauptanteil des Gesamtinvests aus. Der Gesamtinvest be- steht aus den Kosten pro Block. Zu jedem Block wird ein Teilnehmertyp in bestimmter Anzahl ermittelt. Der Teilnehmertyp hängt hauptsächlich von der Partitionierung ab. Die Anzahl der Teilnehmer pro Block ist von mehreren Variablen abhängig. Hierzu zählen die Gr ößen maximale Taktzeit, Blockbearbeitungszeit, Stabilität des Teilneh- mers und Verlust.

Maximale Taktzeit. Durch die kontinuierliche Versorgung wird die Taktzeit vermin- dert. Eine weitere Verminderung der Taktzeit erfordert mehr Teilnehmer. Je klei- ner die vorgegebene, maximale Taktzeit, umso h öher fällt der Invest aus.

Blockbearbeitungszeit. Die Blockbearbeitungszeit besteht hauptsächlich aus den Be- arbeitungszeiten der Aktivitäten in diesem Block. Eine größere Blockbearbei- tungszeit bedingt eine h öhere Taktzeit des Blocks, was wiederum zu einer Auf- stockung der Teilnehmer f ührt. Abbildung 2.12 zeigt die Veränderung der Teil- nehmerzahl in Abhängigkeit der Blockbearbeitungszeit.

Stabilität. Je stabiler der Teilnehmertyp, desto weniger Ausfälle können langfristig vorkommen. Weniger Ausfälle bedeuten weniger Ersatzteilnehmer.

Verlust. Der Verlust deckt alle übriggebliebenen Fehlerquellen. Je geringer der Ver- lust, umso weniger Teilnehmer sind notwendig, um ein Objekt in der beabsich- tigten maximalen Taktzeit zu bearbeiten.

Man sieht, daß die Zusammenhänge in vielfacher Abhängigkeit zueinander stehen. Während die maximale Taktzeit und der Verlust bekannte Gr ößen sind, wird die Block- bearbeitungszeit und die Stabilität erst zur Laufzeit ermittelt. Beide Größen hängen von der Partitionierung ab. Sie gibt vor, welche Bearbeitungszeiten bzw. Aktivit äten in einem Block vorliegen. Erst danach k önnen Teilnehmer und ihre Anzahl ermittelt wer- den. Die Abbildung 2.13 zeigt die Vernetzung der Informationen an. Eine gerichtete Kante sagt aus, daß die Quelle ein Parameter f ür das Ziel ist. So hängt beispielswei- se die Blockbearbeitungszeit von der vorliegenden Partitionierung ab. Eine Ausnah- me bildet die Beziehung zwischen den Teilnehmertypen und der Partitionierung. Hier

30 KAPITEL 2. WORKFLOW PROBLEM SPEZIFIKATION

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.12: Anzahl Teilnehmer steigt mit der Blockbearbeitungszeit an.

besteht eine gegenseitige Beeinflussung. Die einzigen Konstanten sind der maximale Takt und der eingerechnete Verlust. Alle anderen Angaben sind Variablen, die zur Berechnung des Gesamtinvest beitragen. Die Änderung einer Variable kann zu einer Veränderung einer anderen f ühren. Wird beispielsweise die Anzahl der Teilnehmer in einem Block festgelegt, so hat dies Auswirkungen auf die Blockbearbeitungszeit und dementsprechend auch auf die Partitionierung.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.13: Parameter f ür die Investberechnung

Kapitel 3 Constraint Programmierung

Dieses Kapitel stellt Constraint Programmierung (kurz: CP) vor. Es bildet das Fun- dament für die nachfolgenden Kapitel. Constraint Programmierung eignet sich ins- besondere zur Lösung von kombinatorischen Problemen. Darunter fallen klassische Probleme, wie beispielsweise Puzzle, Ressourcenplanung, oder Zuschnittsprobleme [11, 30].

Constraints sind prädikatenlogische Formeln, die Relationen zwischen Variablen ausdrücken. Ziel ist, durch Constraints eine Belegung f ür die in den Constraints auftretenden Variablen zu finden. Die Belegung muß mit den Constraints konsistent sein. Solange keine Belegung f ür eine Variable bekannt ist, wird mit partiellen Wertinformationen der Variable operiert.

Constraints können verschiedene Domänen haben. Zu den bekanntesten geh ören ganze Zahlen³², reelle Zahlen²⁴, Mengen¹² oder Bäume⁹. Diese Arbeit befaßt sich zum einen mit Constraint Programmierung auf endlichen Teilmengen der ganzen Zahlen (Finite Domain) [20, 29, 30] und zum anderen mit der Domäne der endlichen, ganzzahligen Mengen (Finite Set) [20, 21].

3.1 Constraint Programmierung mit Finite Domains (FD)

In diesem Abschnitt wird die Programmierung mit Finite Domain Constraints vorge- stellt. Zunächst werden neue Begriffe eingeführt, mit denen wichtige Mechanismen erklärt werden. Zu diesen geh ören: Propagierung, Zerlegung und Exploration.

Finite Domain, Constraint. Ein endlicher Bereich (finite domain) ist eine endliche Teilmenge der ganzen Zahlen. Ein Constraint ist eine prädikatenlogische Formel. Typische Constraints in Finite Domain Problemen zeigen folgende Beispiele:

Abbildung in dieser Leseprobe nicht enthalten

Domain Constraint. Ein Bereichsconstraint (domain constraint) wird ge- schrieben, wobei ein endlicher Bereich ist. Ein Bereichsconstraint ist äquivalent zu Basic Constraint. Ein Basic Constraint gibt vor, welche Werte eine Variable einnehmen kann. Hierzu geh ören folgende drei Formen:

wobei Variablen, eine Konstante und ein endlicher Bereich ist. Anwendungsbeispiele hierfür sind in (3.1).

Non-basic Constraint. Ein Non-basic Constraint dr ückt eine Relation zwischen Va- riablen aus. Beispiele sind in (3.2) und in (3.3) wobei letzterer ein symbolischer Cons- traint ist.

Finite Domain Problem. Ein Finite Domain Problem ist eine endliche Menge quantorenfreier Constraints, so daß zu jeder in den Constraints vorkommenden Variable einen endlichen Bereich enthält. Eine Variablenbelegung ist eine Funktion, die von einer Variable auf eine ganze Zahl abbildet.

Lösung. Eine Lösung ist eine Variablenbelegung, die jeden Constraint in erf üllt. Betrachtet man nur die Variablen in , so hat ein Finite Domain Problem höchstens endlich viele Lösungen.

3.2 Propagierung

Constraint Propagierung ist eine Inferenzregel f ür Finite Domain Probleme, die die endlichen Bereiche von Variablen einschränkt, d.h. sie schließt inkonsistente Werte aus den endlichen Bereichen aus.

Propagierer. Ein Propagierer ist eine Implementierung eines Non-basic Constraint. Dabei kann es zu einem Non-basic Constraint auch mehrere Propagierer geben, die sich durch ihre Implementierung unterscheiden. Seine Aufgabe besteht darin, inkonsistente Werte aus den Bereichen seiner Variablen auszuschließen.

Space. Constraint Propagierung findet in einem Umfeld statt, das Space genannt wird. Ein Space besteht aus einem Constraintspeicher und einer Reihe von Propagierern, die mit dem Constraintspeicher verbunden sind (siehe Abbildung 3.1). Der Constraintspei- cher enthält eine Konjunktion von Basic Constraints. Ein an den Constraintspeicher angehängter Propagierer überwacht seine Variablen, die sich im Constraintspeicher befinden. Wird eine dieser Variablen verändert, so versucht der Propagierer den Cons- traintspeicher zu aktualisieren.

Kommunikation. Propagierer kommunizieren miteinander über gemeinsame Variablen. Beispielsweise kommunizieren die Propagierer der Constraints

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Space

über die gemeinsam genutzten Variablen und . Eine dichte Verkettung der Constraints führt zu einer starken Propagierung.

Constraintspeicher aktualisieren. Ein Propagierer eines Non-basic Constraint be-

rechnet einen Basic Constraint . Damit wird der Constraintspeicher auf

aktualisiert, falls durch impliziert wird, und falls neue und konsistente

Informationen liefert.

Determinierung. Ein Constraintspeicher determiniert eine Variable , falls er den Wert von kennt, d.h. falls es eine Zahl gibt, so daß der Speicher den Constraint

impliziert.

Inkonsistenz. Ein Propagierer ist inkonsistent, wenn keine Variablenbelegung exi- stiert, die sowohl den Constraintspeicher als auch den durch den Propagierer imple- mentierten Basic Constraint erfüllt. Man spricht von einem Fehlschlag (failure).

Subsumtion. Ein Propagierer wird subsumiert, wenn jede Variablenbelegung sowohl den Constraintspeicher als auch den vom Propagierer implementierten Basic Cons- traint erfüllt. In diesem Fall wird der Propagierer gelöscht. Ein Beispiel für diesen Fall ist:

Abbildung in dieser Leseprobe nicht enthalten

Inkonsistenz und Subsumtion wird spätestens beim Festlegen der Variablenwerte des Propagierers entdeckt.

Stabilität. Ein Propagierer ist stabil, wenn er entweder einen Fehlschlag erzeugt, oder wenn er keine neue Information dem Constraintspeicher hinzuf ügen kann.

Spacezustände. Ein Space schlägt fehl, falls einer seiner Propagierer fehlschlägt. Ein Space ist stabil, wenn alle seine Propagierer stabil sind, und ein Space ist gelöst, wenn er nicht fehlschlägt und keine Propagierer übrig sind.

Lösung eines Space. Eine Variablenbelegung wird eine L ösung eines Space genannt, wenn sie alle Constraints im Speicher und alle durch die Propagierer implementierten Constraints erfüllt.

3.2.1 Unvollst ändigkeit

Constraint Propagierung ist unvollständig. Es kann vorkommen, daß ein Space ei- ne eindeutige Lösung hat, die aber durch Constraint Propagierung nicht gefunden wird. Auf der anderen Seite kann es vorkommen, daß Constraint Propagierung einen unlösbaren Space nicht erkennt, weil sie zu keinem Fehlschlag f ührt. Das folgende Beispiel verdeutlich dies. Es besteht aus drei Propagierern f ür die Constraints und dem Constraintspeicher Dieser Space hat keine L ösung. Dennoch kann kein Propagierer eine Inkonsistenz feststellen, oder dem Speicher neue Informationen hinzuf ügen. Aus diesem Grund wird eine Zerlegung notwendig.

3.3 Zerlegung

Liegt ein Space zwar in einem stabilen, aber weder in einem gel östen noch in ei- nem fehlgeschlagenen Zustand vor, so haben alle Propagierer einen Fixpunkt erreicht. Um fortzufahren wird eine Zerlegung von notwendig. Hierzu wird ein Constraint gewählt, mit dem in zwei neue Space Strukturen zerlegt wird. Dem ersten wird ein Propagierer f ür den Constraint hinzugef ügt, so daß nun gel öst werden soll. Dem zweiten Space wird ein Propagierer f ür hinzugefügt. Der Space wird in diesem Zusammenhang auch Wahlpunkt (choice point) genannt.

Vollständigkeit. Die Kombination von Propagierung und Zerlegung ist eine vollstän- dige Lösungsmethode f ür Finite Domain Probleme. Ist ein Problem gegeben, so enthält ein Space zunächst nur Basic Constraints und angehängte Propagierer. Nach dem Start der Propagierer erreichen diese nach endlicher Zeit einen stabilen Zustand. Haben sie eine Lösung oder einen Fehlschlag produziert, endet die Berechnung. Andernfalls wird eine Zerlegung gemacht. Die Wahl einer guten Zerlegung bestimmt die Heuristik .

3.3.1 Heuristik

Eine Heuristik ist eine Regel, die vorgibt, wie ein Zerlegungsconstraint beschaffen sein muß, um schnell zu einer (guten) L ösung zu kommen. Die Wahl der Zerlegungscons- traints bestimmt somit Gr öße und Gestalt des Suchbaums. Eine erste schnelle L ösung sollte möglichst wenige Knoten benötigen. Desweiteren sollte die beste Lösung einen möglichst kleinen Suchbaum aufbauen. Beides ist durch eine geeignete Wahl von Zer- legungsconstraints zu erzielen. Die Heuristik wird besser, je mehr Wissen über die Problemstellung bekannt ist.

[...]