Produktivität in Geschäftsprozessen erfordert hoch automatisierte und dynamische Mechanismen zur zeitlichen Einteilung von Aktivitäten. Dabei spielt es keine Rolle, ob die zu erledigende Aufgabe der Modellierung eines Herstellungsprozesses von Autos oder der Beschreibung eines elektronischen Services, welches Anfragen an unzählige weitere Web Services weiterleitet, entspricht. Zentrale Fragen, wie "Welche Aktivität ist für diese Aufgabe am besten geeignet?" bestimmen die Zusammenstellung von Workflows vor und während der Laufzeit.<br />Diese Arbeit untersucht ein vereinfachtes Modell eines abstrakten Workflows, welches den Sachverhalt als ganzzahliges 0/1-Programm formuliert. Das Bewertungskriterium von Aktivitäten fußt auf der Zuordnung eines Kosten- und Nutzenwertes. Die Auswahl jener Aktivitäten mit maximalem Gesamtnutzenwert bei Gesamtkosten, die einen vorgegebenen Grenzwert nicht übersteigen, führt zu einem optimalen konkreten Workflow.<br />Eine Heuristik, die auf dem revidierten Simplex-Verfahren basiert, macht sich das Runden der im Allgemeinen nicht ganzzahligen Lösung zu Nutze.<br />Der Algorithmus wurde zusammen mit einem "On-The-Fly-Einlesevorgang" als C Bibliothek implementiert. Weiters steuert für C# Applikationen ein objektorientierter Wrapper den Zugriff auf die Bibliotheksfunktionen.<br />Das Test-Projekt umfasst Zufallstests für die Verifizierung der Funktionalität und ermöglicht darüber hinaus Experimente zur Laufzeitbestimmung.<br />Der Algorithmus löst große Probleminstanzen mit ca. 100000 Variablen auf einem 2.0 GHz Dual-Core Prozessor in 1,3 Sekunden. Dabei übersteigt der relative Fehler jedoch nicht den Reziprokwert der Knotenzahl pro Route.<br />Der konfigurierbare Speicherverbrauch macht die Applikation auch für Geräte mit begrenztem Speicher interessant. Diesen Leistungsmerkmalen zufolge klingt eine Einbindung in ein Workflow Framework äußerst vielversprechend.<br />
de
dc.description.abstract
Productivity at large scale raises the demand for highly automatic and dynamic activity scheduling mechanisms. No matter if the task conforms to modeling the manufacturing process of a car or the offering of an electronic service querying multiple web services on a certain user request. Central questions such as "Which activity fits best for this task?" determine the composition of workflows before and during runtime.<br />This work investigates a simplified abstract workflow model whose mathematical representation corresponds to a binary integer linear program. The evaluation criteria of activities is based on a single benefit and cost value. Selecting those activities with maximum overall benefits and total costs lower than a predefined limit leads to an optimised concrete workflow.<br />A heuristic based on the revised simplex method takes advantage of rounding the non-integral solution. The algorithm together with an on-the-fly read-in procedure was implemented as C library. Furthermore, an OO-Wrapper steers execution for C# applications. The test project comprises random tests for verifying functionality and facilitating runtime experiments.<br />The algorithm solves large problem instances involving about 100000 variables in 1.3 seconds on a 2.0 GHz Dual-Core processor. The relative error is guaranteed not to exceed the reciprocal of the number of nodes per route. Configurable use of memory resources renders the application also attractive for devices with limited storage capabilities.<br />Concerning these performance features, an integration into a workflow framework sounds very promising.<br />
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Zusammenstellung von Workflows
de
dc.subject
Heuristik
de
dc.subject
revidiertes Simplex-Verfahren
de
dc.subject
ganzzahlige lineare Programmierung
de
dc.subject
Aktivität
de
dc.subject
Bewertungskriterien
de
dc.subject
Modell eines abstrakten Workflows
de
dc.subject
optimaler konkreter Workflow
de
dc.subject
Laufzeit
de
dc.subject
Zufallstest
de
dc.subject
composition of workflows
en
dc.subject
heuristic
en
dc.subject
revised simplex method
en
dc.subject
integer linear programming
en
dc.subject
activity
en
dc.subject
evaluation criteria
en
dc.subject
abstract workflow model
en
dc.subject
optimised concrete workflow
en
dc.subject
runtime
en
dc.subject
random test
en
dc.title
A simplex-based heuristic for efficient workflow composition