36,99 €
Mehr erfahren.
- Herausgeber: GRIN Verlag
- Sprache: Deutsch
Diplomarbeit aus dem Jahr 2002 im Fachbereich Informatik - Angewandte Informatik, Note: 1.0, Universität des Saarlandes, Sprache: Deutsch, Abstract: AktuelleWorkflow 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.
Das E-Book können Sie in Legimi-Apps oder einer beliebigen App lesen, die das folgende Format unterstützen:
Veröffentlichungsjahr: 2008
Ähnliche
Page 1
Ressourcenoptimierung von
Page 2
Zusammenfassung
Aktuelle Workflow Management Systeme sind in der Lage, die Durchlaufzeit einzelner Prozesse schon in der Planungsphase zu optimieren. Sie vernachl¨ assigen jedoch die Optimierung von Organisation und Infrastruktur. Dies gilt insbesondere f ¨ ur flexible
Prozesse mit kontinuierlicher Versorgung.
Eine Optimierung von Organisation und Infrastruktur wird aufgrund von zunehmender Komplexit¨ at 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 vonWoopvor.Woopl¨ ost Optimierungsprobleme f¨ ur flexible Prozesse mit kontinuierlicher Versorgung unter Anwendung der Constraint Programmierung. Optimale L ¨ osungen werden
effizient, exakt und generisch approximiert.
Die Implementierung basiert auf dem System Mozart und der Programmiersprache Oz.
Page 3
Danksagung
Mein gr¨ oßter Dank geb¨ uhrt meinen Eltern, die mir das Studium erm¨ oglicht haben, und mich w¨ ahrend der gesamten Studienzeit unterst ¨ utzen.
Weiterhin danke ich meinen Betreuern Christian Schulte und Tobias M ¨ uller, die mir dir
T¨ ur zur Constraint Programmierung weit ge ¨ offnet und damit mein Interesse geweckt
haben. Außerdem danke ich ihnen f¨ ur die zahlreichen Tipps rund um Mozart, Constraints und Diplomarbeit. Ferner danke ich Prof. Dr. Gert Smolka und dem gesamten Lehrstuhl f¨ ur das hervorragende Arbeitsumfeld.
Weiterer Dank geht an Daniel Bobbert, Thorsten Brunklaus und Esther Niederberger f¨ ur ihre Ideen und Korrekturen.
Page 8
INHALTSVERZEICHNIS8
5 Propagierung 59
5.1 Basic Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.2 Non-basic Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.3 Benutzerdefinierte Constraints . . . . . . . . . . . . . . . . . . . . . 62 5.4 Schranken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6 Problemzerlegung und Suche 69
6.1 Hierarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6.2 Workflow Heuristiken . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6.3 Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 6.4 Finite Set Heuristiken . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7 Implementierung 79
7.1 Aufbau von Woop . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7.2 Skript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 7.3 Datenstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8 Evaluierung 87
8.1 Grundmodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 8.2 Pr¨ azises Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 8.3 Slack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 8.4 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
9 Zusammenfassung 95
9.1 Verwandte Arbeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 9.2 Kernpunkte der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . 96 9.3 Offene Fragen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 9.4 Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Page 10
Page 11
Kapitel 1
Einleitung
Diese Arbeit stellt das mathematische Modell und die Implementierung vonWoopvor.Woopl¨ ost Optimierungsprobleme f¨ ur flexible Prozesse mit kontinuierlicher Versorgung unter Anwendung der Constraint Programmierung. Optimale L ¨ osungen werden
effizient, exakt und generisch approximiert.
1.1 Workflow Management
Effiziente Gesch¨ aftsprozesse in Unternehmen erfordern informationstechnische Infrastrukturen. Ein Workflow Management System (kurz: WFMS) koordiniert die zu einem Gesch¨ aftsprozeß geh¨ orenden Aktivit¨ aten gem¨ aß einer Ablaufspezifikation f¨ ur den vorliegenden Prozeßtyp. Die Bearbeitung von Aktivit¨ aten ¨ ubernehmen Workflow Teilnehmer.
Moderne Unternehmen sind darauf angewiesen, daß ein WFMS eine große Zahl (kon-tinuierlicheVersorgung)von Gesch¨ aftsprozessen verschiedenster Typen (flexibleProzesse)verl¨ aßlich und ohne sichtliche Verz¨ ogerung ausf¨ uhrt. Dabei beschreiben drei essentielle Punkte jeden Prozeß: Prozeßlogik, Organisation und Infrastruktur. DieProzeßlogikgibt den Ausf¨ uhrungszeitpunkt einer Aktivit¨ at vor. Dagegen legt dieOrganisationfest, welche Aktivit¨ at von welchem Teilnehmertyp ausgef¨ uhrt wird. Prozeßlogik und Organisation garantieren die korrekte Arbeitsweise des WFMSs. DieInfrastrukturbeschreibt, wieviele Teilnehmer eines bestimmten Typs notwendig sind. Die Infrastruktur eines WFMS ist maßgebend f ¨ ur Invest und Durchsatz.
Aus Sicht der Investoren besteht das wichtigste Planungsproblem des Workflow Management darin, f¨ ur eine gegebene Menge von Ablaufspezifikationen und f ¨ ur einen
Mindestdurchsatz die kosteng¨ unstigste Organisation und Infrastruktur zu finden. Hierbei darf nur auf Teilnehmertypen aus einer gestellten Menge zur ¨ uckgegriffen werden.
Page 12
KAPITEL 1. EINLEITUNG12
1.2 Motivation
F¨ ur die Planer von WFM-Systemen ist es eine schwierige Aufgabe, eine kosteng ¨ unstige Infrastruktur und Organisation zu finden. Umso m ¨ uhsamer gestaltet sich bei komplexen Prozessen die Suche nach der optimalen L ¨ osung.
Neben der Kostenoptimierung fordert die Wirtschaft in der Praxis weitere Konzepte:Betriebsmodus.Es wird zwischen zwei Modi unterschieden: separat und vermischt. ImseparatenBetriebsmodus startet das WFMS ausschließlich Prozesse eines bestimmten Typs. ImvermischtenBetriebsmodus hingegen werden Prozesse verschiedener Typen im vorgegebenen Verh¨ altnis gestartet.
Gerichteter Datenfluß.Ein Objekt, das nach einer Ablaufspezifikation bearbeitet wird, hat eine feste Sequenz von Teilnehmertypen zu durchlaufen. D.h. der Trans-port von Objekten wird gesteuert. Dadurch ist eine exakte Bestimmung der effektiven Taktzeit, Organisation und Infrastruktur m ¨ oglich.
Attributierte Ressourcen.Teilnehmertypen erlangen durch Eigenschaften (F¨ ahigkeiten, lokale Zeitangaben, Stabilit¨ at, Kosten, Werkzeuge etc.) pr¨ azisere Z¨ uge. Je-
de Eigenschaft ¨ ubt Einfluß auf Organisation und Infrastruktur aus, was die Komplexit¨ at der Problemstellung steigert. Den gr ¨ die F¨ ahigkeiten. Ein Teilnehmertyp ist nicht notwendigerweise ein Spezialist. Die F¨ ahigkeiten der Teilnehmertypen d¨ urfen beliebig ¨ uberlappen.
Zur Beschreibung der genannten Problemstellung und zur Entwicklung eines L ¨ osungsverfahrens 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 dieser Arbeit mathematisch abstrahiert und als ein Workflow Problem modelliert. Dabei wird zun¨ achst ein Grundmodell vorgestellt, das sukzessiv um pr¨ azise Informationen (lokale Zeit, Werkzeuge, vermischte Betriebsart) erweitert wird. Das mathematische Grundmodell erlaubt genauere, formale Untersuchungen des Problems. Als L¨ osungstechnik wird die Constraint Programmierung gew¨ ahlt. Sie erlaubt eine direkte Umsetzung des mathematischen Modells. Die Umsetzung beinhaltet sowohl aus dem Modell hervorgegangene Constraints als auch spezielle, auf das Problem zugeschnittene Heuristiken. Die Implementierung tr¨ agt den NamenWoop (Workflow Opti- mizer)[16] und basiert auf dem System Mozart [23] und der Sprache Oz [31].
Page 13
1.4. AUFBAU DER ARBEIT13
Woopist in der Lage, korrekte und exakte L¨ osungen generisch aus partiellen Informationen zu berechnen. Das Verfahren ist effizient, skalierbar und approximiert schnell optimale L¨ osungen.
Dar¨ uber hinaus enth¨ altWoopinteraktive Komponenten, die den Anwender dabei unterst¨ utzen, Einfluß auf die L¨ osungsverfahren auszu¨ uben. Durch benutzerdefinierte Modellierungsanweisungen werden dem System partielle Informationen ¨ uber den L¨ osungsraum mitgeteilt. Ferner kann der Anwender verschiedene Heuristiken erstellen und testen.
1.4 Aufbau der Arbeit
Das nachfolgende Kapitel 2 stellt das vorliegende Optimierungsproblem flexibler Gesch¨ aftsprozesse mit kontinuierlicher Versorgung vor. Kapitel 3 gibt eine ¨ Ubersicht zur
Programmierung mit Constraints. Es bildet die Grundlage f ¨ ur die nachfolgenden Kapitel. Anschließend wird in Kapitel 4 ein mathematisches Modell f ¨ gef¨ uhrt. In Kapitel 5 werden Eigenschaften des Problems und des Modells untersucht, um gegebenfalls weitere Einschr¨ ankungen des Suchraums zu erfassen. Das Thema Suche und Heuristik wird detailiert in Kapitel 6 behandelt. Die Kernpunkte der Implementierung vonWoopwerden 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.
Page 14
Page 15
Kapitel 2
Workflow Problem Spezifikation
Der BegriffWorkflowwird von der Workflow Management Coalition (WfMC) [33] als teilweise oder vollst¨ andige Automatisierung eines Gesch¨ aftsprozesses definiert, w¨ ahrend 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¨ ur einen Workflow, der aus flexiblen Gesch¨ aftprozessen mit kontinuierlicher Versorgung besteht. Die hier benutzten Begriffe sind an die standardisierten Definitionen der WfMC angelehnt und werden teilweise erweitert. Dieses Kapitel beginnt zun¨ achst mit der Erkl¨ arung der Grundbegriffe von Gesch¨ aftsprozessen. Insbesondere wird das Workflow Problem mit kontinuierlicher Versorgung von klassischen Schedulingproblemen abgegrenzt. Anschließend wird erkl¨ art, wie eine 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¨ osungsweges skizziert.
2.1 Grundbegriffe
EinGesch¨ aftsprozeß (Business Process)beschreibt die in einer realen Welt miteinander vernetzen Teilprozesse bzw. Aktivit¨ aten, die gemeinsam eine ¨ ubergeordnete Auf-
gabe l¨ osen. Beispiele hierf¨ ur sind Reklamation oder Bestellannahme in einem Call Center. Ein Bestellvorgang besteht aus mehreren aufeinander folgenden Arbeitsschritten, die von Personen, Maschinen oder Software ausgef ¨ uhrt werden.
Die Abbildung eines Gesch¨ aftsprozesses in eine f¨ ur ein Workflow Management System verst¨ andliche Darstellung wird alsProzeßdefinition (Process Definition)bezeichnet. Diese Modellierung beinhaltet alle stattfindenden Aktivit¨ aten, einen Zeitplan be- z¨ uglich der Aktivit¨ aten, sowie alle Ressourcen, die diese Aktivit¨ aten ausf¨ uhren. Die
Page 16
KAPITEL 2. WORKFLOW PROBLEM SPEZIFIKATION16
Prozeßdefinition wird an ein Workflowsystem ¨
tion Instanzen der Prozeßdefinition ausf ¨ uhren kann. Eine Prozeßdefinition, die ausschließlich auf Computern eingesetzt wird, heißtWorkflowdefinitionund ihre Instanz einfachWorkflow.
Jeder Gesch¨ aftsprozeß besteht aus drei orthogonal aufgebauten Ebenen. Leymann und Roller legen die Ebenen in [19] wie folgt fest:
1.Prozeßlogik
Welche Aktivit¨ at soll zu welchem Zeitpunkt ausgef¨ uhrt werden?
2.OrganisationWer f¨ uhrt welche Aktivit¨ at aus?
3.Infrastruktur
Welche Ressourcen sind in welcher Anzahl notwendig?
Diese Arbeit widmet sich der Aufgabe, Prozeßdefinitionen aus partiellen Informationen gem¨ aß der formulierten Ziele und Kriterien zu bestimmen. Zu den wichtigsten Eingangsinformationen geh¨ oren relative Ablaufvorgaben sowie Ressourcentypen. Unter einem Ablauf versteht man eine relative Reihenfolge von Aktivit¨ aten. Im Gegensatz zu einem Zeitplan, in dem der Ausf ¨ uhrungszeitpunkt jeder Aktivit¨ at bekannt
ist, legt der relative Ablauf zeitliche Rahmenbedingungen fest, die durch Relationen zwischen Aktivit¨ aten ausgedr¨ uckt werden. Im folgenden wird von einemAblaufgesprochen, wenn die relative Reihenfolge von Aktivit¨ aten gemeint ist, und es wird von einemZeitplangesprochen, wenn die exakten Ausf ¨ uhrungszeiten gemeint sind.
Den Zeitpunkt und die Art der Prozeßausf ¨ uhrung bestimmt derModus.Er legt fest,
wieviele verschiedene Prozeßdefinitionen gleichzeitig instanziiert werden d ¨ lauf und Modus bilden zusammen denDatenfluß.
Beispiel 2.1.1.In einem Call Center f¨ ur Druckauftr¨ age wird eine Bestellung per Telefon von einem Operator entgegengenommen. Anschließend wird sie an die Druckabteilung weitergeleitet, wo ein Drucker den Ausdruck ¨ ubernimmt. Zuletzt stellt der
Lieferbote die Ware zu. Die Aufgabe besteht darin, die kosteng ¨ unstigste Prozeßdefinition 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¨ alt die Ressourcen mitsamt ihren Kosten fest.
Page 17
2.1. GRUNDBEGRIFFE17
Die Ressourcen f¨ ur Start und Ende verursachen keine Kosten. Sie simulieren Ressourcen, die eine Start- und eine Endaktivit¨ at ausf¨ uhren und dienen lediglich als Orientierungspunkte. Diese Ressourcen werden auchSonderressourcengenannt. Desweiteren erkennt man, daß die Auswahl zwischen einem Menschen und einem Programm als Operator gegeben ist. Hierbei ist das Programm g ¨ unstiger, da es keine monatlichen
Gehaltskosten verursacht. Allerdings sollte der Mensch zumindest aufgrund der Vielfalt seiner F¨ ahigkeiten den Vorzug erhalten. Die endg ¨ ultige Wahl wird entsprechend der geforderten Aktivit¨ aten getroffen.
Die Aktivit¨ aten im Beispiel unterliegen einer typischen, relativen Reihenfolge. Die nachfolgende Tabelle listet alle geforderten Aktivit¨ aten mitsamt ihrer Kodierung (SpalteA)auf. In der Prozeßdefinition werden ¨ ublicherweise ganze Zahlen als Namen
f¨ ur Aktivit¨ aten verwendet. Zu jeder Aktivit¨ at wird zus¨ atzlich angegeben, welche Aktivit¨ aten zuvor ausgef¨ uhrt werden m¨ ussen, und welche Ressource (SpalteT)diese ausf¨ uhren kann.
