A simplex-based heuristic for efficient workflow composition

Abstract

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 />

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 />