WI – AUFSATZ

Robuste multikriterielle Dienstkompositionin InformationssystemenDienstkompositionen werden dazu verwendet, Geschäftsprozesse in unterschiedlichenAnwendungsdomänen zu implementieren. Die Quality-of-Service (QoS)-basierte Auswahlvon Diensten beinhaltet multiple, typischerweise zu einander in Konflikt stehende,möglicherweise unsichere QoS-Attribute. Der Artikel stellt einen heuristischenmultikriteriellen Dienstauswahlansatz vor, der dazu dient, eine Pareto-Front alternativerDienstselektionen mit vertretbarem Rechenaufwand zu ermitteln. Die erhaltenenDienstselektionen sind robust bezüglich einer eingeschränkten Ausführungsdauer, wennunsichere Antwortzeiten berücksichtigt werden. Der vorgeschlagene Lösungsansatz basiertauf einem Nondominated Sorting Genetic Algorithm (NSGA-II)-Ansatz, derproblemspezifische Eigenschaften ausnutzt. Die Anwendbarkeit des vorgeschlagenenLösungsansatzes wird durch eine Simulationsstudie gezeigt.

DOI 10.1007/s11576-014-0416-4

Die Autoren

Dipl.-Inf. René RamacherProf. Dr. Lars Mönch (�)Lehrgebiet UnternehmensweiteSoftwaresystemeFakultät für Mathematikund InformatikFernuniversität in HagenUniversitätsstraße 158097 HagenDeutschlandLars.Moench@fernuni-hagen.de

Eingegangen: 2013-07-13Angenommen: 2014-02-05Angenommen nach zwei Überarbei-tungen durch die Herausgeber desSchwerpunktthemas.Online publiziert: 2014-04-17

This article is also available in Eng-lish via http://www.springerlink.comand http://www.bise-journal.org: Ra-macher R, Mönch L (2014) RobustMulti-criteria Service Compositionin Information Systems. Bus Inf SystEng. doi: 10.1007/s12599-014-0325-5.

© Springer Fachmedien Wiesbaden2014

1 Einleitung

Service-orientierte Architekturen (SOA)stellen ein sich rasch entwickelndes Ar-chitekturparadigma dar, das zur Imple-mentierung betrieblicher Anwendungs-systeme verwendet wird (Papazoglouet al. 2008; Aier et al. 2011). Ge-schäftsprozesse werden auf Basis vonSoftwarediensten implementiert, auf diein einer SOA unter Verwendung vonStandardschnittstellen zugegriffen wer-den kann. Diese Dienste werden in-nerhalb eines Unternehmens zur Ver-fügung gestellt oder können von ex-ternen Dienstanbietern bezogen werden.Die Auswahl der zu komponierendenDienste wird durch funktionale Anforde-rungen und durch QoS-Anforderungenbestimmt. In Anbetracht eines wachsen-den Marktes für Dienste und alternati-ve Dienstimplementierungen besteht dieHerausforderung für eine QoS-basierteDienstauwahl darin, zu komponieren-de Dienste derart zu identifizieren, dassQoS-Anforderungen erfüllt werden undQoS-Attribute optimiert werden (Bich-ler und Lin 2006). Wir erwarten zukünf-tige Anwendungen von QoS-basiertenDienstauswahlalgorithmen für Entschei-dungsunterstützungssysteme in Domä-nen wie Wertschöpfungsnetzwerken, d.h.für die Orchestrierung eines Netzwerksvon Produktions- und Logistikaktivitä-ten, Supply Chain Management oder fürden kombinierten Verkehr im Rahmendes Physischen Internets.

Die QoS-basierte Dienstauswahl stelltein multikriterielles Optimierungspro-blem dar, das, wie von Yu und Lin (2004)gezeigt, NP-schwer ist. Unter ökonomi-schen Gesichtspunkten besteht das Zieleiner QoS-basierten Dienstauswahl dar-in, die Kosten der Dienstkomposition zuminimieren.

Eder et al. (1999) folgend, wird einegroße Kundenzufriedenheit durch einehohe Verfügbarkeit der Geschäftspro-zesse und der Einhaltung von zeitli-chen Bedingungen während der Ausfüh-rung erreicht. Die Ausführungszeit ei-ner Dienstkomposition wird wesentlichdurch die Antwortzeiten der Dienste be-stimmt, die typischerweise unsicher sind.Der Dienst-Rekonfigurationsansatz vonRamacher und Mönch (2013) wird da-zu verwendet, die Verletzung der ein-geschränkten Ausführungsdauer in ei-ner unsicheren Umgebung zu vermeiden.Das häufige Ersetzen von Diensten alsFolge einer Dienst-Rekonfiguration ist ineiner Umgebung, in der eine Implemen-tierung von Diensten oder entsprechen-de Verträge mit Anbietern nicht oder nurmit großem Aufwand geändert werdenkönnen, nicht wünschenswert. Ein wei-terer Nachteil von existierenden Dienst-auswahlverfahren ist darin zu sehen,dass die Optimierung multipler QoS-Attribute bisher weitestgehend vernach-lässigt wurde. Die QoS-Attribute werdentypischerweise in einer integrierten Ziel-funktion zusammengefasst, die auf einereinfachen Addition der gewichteten QoS-Attribute basiert. Wir sprechen an die-

WIRTSCHAFTSINFORMATIK 3|2014 159

WI – AUFSATZ

ser Stelle von Simple Additive Weighting(SAW). Dieser Ansatz hat aber den Nach-teil, dass diese Art der Integration voraus-setzt, dass ein Kompromiss zwischen denQoS-Attributen bereits vor der Optimie-rung bekannt sein muss, obwohl Infor-mationen über verschiedene alternativeLösungen nicht vorliegen.

Dieser Artikel schlägt ein multikri-terielles QoS-basiertes Dienstauswahlm-odell vor, das die Unsicherheit derAntwortzeiten berücksichtigt. Bertsimasund Sim (2004) folgend, wird eine Lö-sung, d.h. eine Dienstauswahl, robust ge-nannt, wenn sie mit einer bestimmtenWahrscheinlichkeit zulässig bleibt, ob-wohl sich die Problemparameter inner-halb eines bestimmten Bereichs ändern.Bezogen auf die Dienstauswahl bedeu-tet das, dass eine zuverlässige Ausfüh-rung einer Dienstkomposition bezüglicheiner eingeschränkten Ausführungsdauerunter Berücksichtigung von unsicherenAntwortzeiten ermöglicht wird. DieserTyp von Robustheit wird in Anlehnungan Scholl (2001) Zulässigkeitsrobustheitgenannt. Robuste Ansätze werden bis-her überwiegend in der relevanten Li-teratur vernachlässigt. Unter Benutzungder Prinzipien der multikriteriellen Opti-mierung versucht der Lösungsansatz eineMenge alternativer Lösungen zu ermit-teln, die zum einen die Kosten minimie-ren, andererseits aber die Verfügbarkeitmaximieren.

Der vorgeschlagene Lösungsansatzkombiniert die NSGA-II-Metaheuristikmit Heuristiken, welche die spezifischeStruktur des Dienstauswahlproblemsausnutzen. Die Heuristiken von Ra-macher und Mönch (2012) werden inder vorliegenden Arbeit erweitert, da-mit sie für komplexe Prozessmodelleund unsichere Antwortzeiten geeignetsind. Numerische Experimente zeigen,dass qualitativ hochwertige Dienstkom-positionen innerhalb weniger Minu-ten Rechnenzeit unter Verwendung derHeuristiken ermittelt werden können,während der Rechenaufwand für mit-telgroße Dienstkompositionen bereitseinige Stunden beträgt, wenn exakteVerfahren verwendet werden.

Der Artikel ist wie folgt aufge-baut. Das Dienstauswahlproblem wirdin Abschn. 2.1 formuliert. Mögli-che Anwendungsdomänen für eineQoS-basierte Dienstauswahl werdenin Abschn. 2.2 vorgestellt. Vorarbei-ten werden in Abschn. 2.3 diskutiert.Abschnitt 3.1 dient dazu, den auf Me-taheuristiken basierenden Ansatz für

Abb. 1 Prozessmodell einer Dienstkomposition

das betrachtete multikriterielle Dienst-auswahlproblem zu beschreiben. InAbschn. 3.2 werden problemspezifischeHeuristiken und ihre Verwendung in derMetaheuristik diskutiert, während ein ex-akter Ansatz in Abschn. 3.3 beschriebenwird. Das Design der numerischen Ex-perimente wird in Abschn. 4 vorgestellt.Außerdem werden dort auch die erzieltenErgebnisse diskutiert. In Abschn. 5 wer-den wesentliche Ergebnisse des Artikelszusammengefasst und ein Ausblick aufweitere Forschungsarbeiten gegeben.

2 Multikriterielle Dienstauswahl

2.1 Dienstkompositionsmodelle

Dienste sind wohldefinierte, eigenständi-ge Module, die Anwendungsfunktionali-tät anbieten. Auf einen Dienst kann unterVerwendung öffentlicher Schnittstellenzugegriffen werden, die durch standar-disierte Schnittstellenbeschreibungsspra-chen beschrieben sind. Ein Task stellt ei-ne abstrakte Funktionalität dar, die durcheinen Dienst zur Verfügung gestellt wer-den kann. Die Dienstklasse Si beinhal-tet die Dienste, welche die funktiona-len Anforderungen erfüllen, um Task tiauszuführen.

Wenn existierende Dienste zusammen-gefügt werden, um eine spezifische Funk-tionalität anzubieten, wird die daraus re-sultierende Komponente als Dienstkom-position bezeichnet. Eine Dienstkompo-sition kann unter Verwendung eines Pro-zessmodells beschrieben werden, das ausTasks besteht. Die Ausführungslogik ei-nes Prozessmodells ist durch die sequen-tielle Ausführung von Tasks, beding-ten Verzweigungen und Parallelisierun-gen gegeben. Die Bedingungen einer Ver-zweigung werden während der Ausfüh-rung einer Dienstkomposition ausgewer-tet. Darauf basierend wird ein konkreterZweig ausgewählt. Es wird angenommen,

dass die Verzweigungswahrscheinlichkei-ten bekannt sind oder geeignete Schätz-werte dafür verfügbar sind. Die Zwei-ge einer Parallelisierung werden paral-lel ausgeführt. Die parallelisierten Zwei-ge werden nur dann wieder zusammen-geführt, wenn die Ausführung jedes ein-zelnen Zweiges beendet ist. Ein Prozess-modell, das aus sieben Tasks, zwei be-dingten Verzweigungen sowie einer Par-allelisierung besteht, ist in Abb. 1 dar-gestellt. Es wird angemerkt, dass Diensteaus sieben Dienstklassen verwendet wer-den, um die erforderliche Funktionalitätzur Ausführung der Tasks ti, i = 1, . . . ,7in Abb. 1 zur Verfügung zu stellen.

Die Menge aller Tasks wird mit T be-zeichnet. Die Bezeichnung ti → tk wirdverwendet, wenn ti ein Vorgängertaskvon tk ist. Die Menge T ⊆ T bestehtaus Tasks, die keine Vorgänger haben,während T ⊆ T die Menge von Tasksdarstellt, die keine Nachfolger besitzen.Yu et al. (2007) folgend, wird die Aus-führungsstruktur einer Dienstkompositi-on durch Ausführungspfade P und Aus-führungsrouten R beschrieben. Ein Aus-führungspfad p ∈ P ist ein Pfad vonti ∈ T nach tk ∈ T, der genau einenZweig im Falle einer bedingten Ver-zweigung sowie genau einen Zweig imFalle einer Parallelisierung enthält. Ei-ne Ausführungsroute r ∈ R ist ein Un-termodell eines Prozessmodells, das ge-nau einen Zweig im Falle einer beding-ten Verzweigung, aber alle Zweige für ei-ne Parallelisierung enthält. Die Ausfüh-rungswahrscheinlichkeit ν(r) von r ∈ Rwird als Produkt der Verzweigungswahr-scheinlichkeiten der Zweige berechnet,die in r enthalten sind. Die Bezeichnungti ∈ T[r] und ti ∈ T[p] wird verwen-det, wenn Task ti Bestandteil einer Aus-führungsroute r oder eine Ausführungs-pfades p ist. Die Ausführungspfade P ={p1,p2,p3} und die AusführungsroutenR = {r1, r2} der Dienstkomposition ausAbb. 1 sind in Abb. 2 dargestellt.

160 WIRTSCHAFTSINFORMATIK 3|2014

WI – AUFSATZ

Abb. 2 Ausführungsrouten und -pfade eines Prozessmodells

Die Menge aller Dienste wird mit S =⋃ti∈T Si bezeichnet. Eine Dienstbindung

bestimmt einen Dienst sij ∈ Si, der da-zu verwendet wird, Task ti auszufüh-ren. Folglich kann eine Dienstbindung alsAbbildung

b : T → S, ti �→ sij ∈ Si (1)

aufgefasst werden. Im weiteren Verlaufdes Artikels wird der Dienst b(ti), der anti gebunden ist, mit bi bezeichnet. DieMenge aller Dienstbindungen ist danngegeben durch B := {b|b : T → S, ti �→bi ∈ Si}.

Die Kosten, die mit einem Aufruf vons ∈ S verbunden sind, werden mit c(s) ∈IR+ bezeichnet. Die Verfügbarkeit vons ∈ S ist durch a(s) ∈ [0,1] gegeben. Dietatsächliche Antwortzeit von s ist r(s) ∈IR+, wobei r(s) erst dann bekannt ist,nachdem die Ausführung von s abge-schlossen ist. Aus diesem Grund wird einSchätzwert r(s) ∈ IR+ für die Antwortzeitbetrachtet. Ein sinnvoller Wert für r(s)kann auf historischen Daten basierendangegeben werden, die, wie von Qianget al. (2012) vorgeschlagen, durch Moni-toringsysteme zur Verfügung gestellt wer-den. Eine empirische Verteilung der Ant-wortzeiten sij ∈ Si ist durch K ∈ IN+Klassen gegeben. Der linke Endpunkt der

k-ten Klasse wird durch rk−1ij bezeich-

net, während der rechte Endpunkt durchrk

ij gegeben ist. Die minimale Antwort-

zeit ist r0ij. Die maximale Antwortzeit ist

durch rKij gegeben. Die übrigen k−1 Wer-

te rkij werden äquidistant zwischen r0

ij und

rKij gewählt. Die Größe hk

ij stellt die An-

zahl der Dienstaufrufe dar, die für sij mit

rk−1ij ≤ r(sij) < rk

ij beobachtet wurden.

Yu et al. (2007) folgend, werden die er-warteten Kosten c(b), die Verfügbarkeita(b) sowie die Ausführungszeit e(b) einerDienstkomposition wie folgt berechnet:

c(b) =∑

r∈R

ν(r) ·∑

ti∈T[r]c(bi), (2)

a(b) = minr∈R

∏

ti∈T[r]a(bi), (3)

e(b) = maxp∈P

ep(b). (4)

In (4) bezeichnet dabei ep(b) die Aus-führungsdauer von Ausführungspfad p ∈P. Da die Tasks eines Ausführungspfa-des sequentiell ausgeführt werden, kanndie Ausführungszeit wie folgt berechnetwerden:

ep(b) =∑

ti∈T[p]r(bi). (5)

Die Ausführungsdauer einer Dienstkom-position darf e nicht überschreiten. Wenndie Ausführungszeitrestriktion verletztist, ist die Ausführung der Dienstkom-position fehlgeschlagen. Da unsichereAntwortzeiten betrachtet werden, stelltdie Ausfallsicherheit ψ(b) die Wahr-scheinlichkeit dar, dass die Ausführungs-

dauerrestriktion eingehalten wird, wenndie Dienstkomposition entsprechend derBindung b ausgeführt wird. Die minima-le Zuverlässigkeit, die durch die Dienst-bindung b zu erreichen ist, beträgt ψmin.D.h., b ist nur dann zulässig, wennψ(b) ≥ ψmin gilt.

Das Ziel einer Dienstauswahl bestehtdarin, einen Kompromiss zwischen denin Konflikt stehenden Zielen der Kos-tenminimierung und der Maximierungder Verfügbarkeit zu erreichen. Das zulösende Problem wird wegen der eng-lischen Bezeichnung Multi-criteria Sto-chastic Service Selection im weiteren Ver-lauf des Artikels mit MCSS abgekürzt.Das MCSS-Problem kann mit Stan-dardlösungsverfahren behandelt werden,wenn die Ziele durch

I(b) = a(b) + w · c(b) (6)

zu einer integrierten Zielfunktion zusam-mengefasst werden. Die Größe w stelltin (6) einen Gewichtungsparameter dar,der dazu verwendet wird, die Bedeutungder Kostenminimierungszielsetzung ge-genüber der Zielsetzung der Maximie-rung der Verfügbarkeit auszubalancieren.Die Wahl von w hängt vom Größenver-hältnis der Kosten und der Verfügbar-keit sowie von den Präferenzen des Ent-scheiders ab. Eine Integration der beidenZiele, wie in (6) durchgeführt, wird alsA-priori-Ansatz bezeichnet, weil w vorder Optimierung ohne Kenntnisse übermögliche Alternativen festzulegen ist.

Ein multikriterieller Dienstauswahlan-satz vermeidet eine Festlegung des Wertesvon w vor der Optimierung. Die Maxi-mierung der Verfügbarkeit und die Mi-nimierung der Kosten stehen in Kon-flikt zueinander. Daraus folgt, dass jedeDienstbindung einen Kompromiss zwi-schen den beiden Zielen darstellt. Somitexistiert typischerweise keine einzelneLösung, die gleichzeitig optimal für beideZiele ist. Eine zulässige Dienstbindung bwird als nicht-dominiert bezeichnet, wenkeine andere zulässige Dienstbindung b′existiert mit c(b′) ≤ c(b) und a(b′) ≥a(b) und in mindestens einer der beidenUngleichungen keine Gleichheit gilt. DieMenge aller nicht-dominierten Lösungenwird als Pareto-Front bezeichnet.

2.2 Potentielle Anwendungsbeispiele

In diesem Abschnitt diskutieren wir po-tentielle Anwendungen der Techniken,die wir in diesem Artikel vorschlagen,weil uns praktische Anwendungen von

WIRTSCHAFTSINFORMATIK 3|2014 161

WI – AUFSATZ

Abb. 3 Angebot alternativer Dienste zur Implementierung eines Geschäftsprozesses

QoS-basierten Dienstauswahlverfahrennicht bekannt sind. Webservices werdendazu verwendet, Geschäftsprozesse zuautomatisieren. Die QoS-basierte Dienst-auswahl wird typischerweise im Kontextder Komposition von Webservices be-trachtet, um komplexe Anwendungs-funktionalität zu implementieren. Diedynamische Anpassung von Dienstkom-positionen auf Basis von Webserviceswird beispielsweise durch die eFlow-Umgebung unterstützt, die von Casatiet al. (2000) vorgeschlagen wurde. Eswird aber in diesem Abschnitt gezeigtwerden, dass Ansätze der QoS-basiertenDienstauswahl leicht so erweitert wer-den können, dass eine Anwendungin allgemeinen Orchestrierungs- undBereitstellungsszenarien möglich ist.

Viswanadham und Kameshwaran(2009) betrachten die Orchestrierungeines Netzwerkes von Aktivitäten inWertschöpfungsketten. Es wird ein Or-chestrator angenommen, der keine eige-nen Kapazitäten besitzt, aber auf einengroßen Pool von Dienstanbietern zugrei-fen kann, die unterschiedliche Aktivitä-ten in der Wertschöpfungskette durch-führen können. Viswanadham und Ka-meshwaran (2009) berichten, dass dasin Hong Kong ansässige Handelsunter-nehmen Li & Fung mit Tausenden vonDienstanbietern zusammenarbeitet. Die-se Anbieter werden sehr kurzfristig ent-sprechend der Aktivitäten ausgewählt,

die zur Erfüllung eines Auftrages not-wendig sind. Die Auswahl wird durchbestimmte, miteinander in Konflikt ste-hende Attribute beeinflusst, wie zumBeispiel die Produktionskapazitäten derDienstanbieter, die Durchlaufzeiten so-wie die Produktionskosten. Obwohl einegemischt-ganzzahlige Optimierungsfor-mulierung (Mixed Integer Programming(MIP)) basierend auf einem SAW-Ansatzvorgestellt wird, erscheint eine heuristi-sche multikriterielle Entscheidungsme-thode zur Lösung des Orchestrierungs-problems vorteilhaft, um effizient mög-liche alternative Implementierungen derWertschöpfungskette zu erhalten.

Eine andere Anwendung der QoS-basierten Dienstauswahl ist in Rechen-zentren anzutreffen, wenn Dienste zurVerfügung gestellt werden. Die Diens-te, aus denen sich ein Geschäftsprozesszusammensetzt, sind in unterschiedli-chen Softwarekomponenten wie zumBeispiel Enterprise-Resource-Planning(ERP)-Systemen, Standard-IT-Diensten,z.B. Verzeichnisdienste, oder als Indivi-dualsoftware bereitgestellte Webservicesimplementiert (siehe Abb. 3). Die exis-tierenden Softwarekomponenten kön-nen auf internen Servern oder in einerCloud-Umgebung, die als Infrastructure-As-A-Service (IAAS) verwendet wird,bereitgestellt werden. Ein Beispiel füreine IAAS ist die von Amazon angebo-tene Elastic Computing Cloud (EC2).

Wir nehmen an, dass QoS-Schätzwertevorhanden sind, die beispielsweise imRahmen von sorgfältig geplanten Expe-rimenten zur Leistungsbewertung einesSystems, wie von Jamoussi et al. (2010)beschrieben, erhoben werden können.Ein Bereitstellungsplan ist für jede Soft-warekomponente zu ermitteln, so dassdie QoS-Anforderungen erfüllt und dieQoS-Attribute optimiert werden. EinBeispielprozess, der aus vier Tasks be-steht, ist in Abb. 3 dargestellt. Die Taskswerden durch Standardsoftware wie demLightweight Directory Access Protocol(LDAP), ERP-Systeme sowie Webser-vices, die auf Servern innerhalb des Un-ternehmens betrieben werden oder inForm von IAAS von außerhalb bezogenwerden können, ausgeführt. Die Kosteneines Bereitstellungsplans bestehen ausden Mietkosten für IAAS und den Be-triebskosten der internen Server. Zusätz-lich zu diesen Kosten können die Ausfüh-rungsdauer eines Geschäftsprozesses undder Durchsatz als Zielsetzungen betrach-tet werden, die zueinander in Konfliktstehen.

Das letzte Beispiel beschäftigt sich mitzukünftigen Logistikkonzepten. Im Rah-men des Physischen Internets werdenphysische Objekte in sogenannten π-Containern innerhalb einer mehrglied-rigen Transportkette, d.h. durch kom-binierten Verkehr, transportiert (Mon-treuil 2011). Die einzelnen Segmente

162 WIRTSCHAFTSINFORMATIK 3|2014

WI – AUFSATZ

der Transportkette sind durch π-Hubsverbunden, die ein effizientes Verladenbzw. Umladen von π-Containers er-möglichen. Ein Nachfrager von Trans-portleistungen hat entsprechende Trans-portdienstleister auszuwählen, die sei-ne Transportgüter von Segment zu Seg-ment transportiert, um das Transportzielzu erreichen. Die Dienste, die von denTransportdienstleistern angeboten wer-den, unterscheiden sich bezüglich derTransportzeit, Transportkosten und an-deren Maßen für die Qualität der Trans-portdienstleistung. Die entsprechendenDienste bilden eine Dienstklasse für je-des Segment. Wenn man den Transportin einem bestimmten Segment als Taskauffasst, erlaubt die QoS-basierte Dienst-auswahl diejenigen Transportdienstleis-tungsanbieter zu identifizieren, die QoS-Ziele wie die Minimierung der Trans-portkosten bei gleichzeitiger Einhaltungvon Zeitrestriktionen für die gesamteTransportzeit erfüllen.

2.3 Relevante Vorarbeiten

Ein Dienstauswahlmodell für die Kom-position von sequentiell ausgeführtenTasks, das zusätzlich zur Optimierungvon QoS-Attributen auch Nebenbedin-gungen für QoS-Attribute berücksich-tigt, wird von Yu und Lin (2004)vorgeschlagen. Ein SAW-Ansatz wirdverwendet, um die zu optimierendenQoS-Attribute in einer integrierten Ziel-funktion zu kombinieren. Das Dienst-auswahlproblem wird als kombinato-risches Optimierungsproblem und alsgraphbasiertes Problem formuliert. DasOptimierungsproblem ist ein Spezial-fall des NP-schweren Multiple-Choice-Knapsack-Problems (MCKP). Verschie-dene exakte Ansätze werden jeweils fürdie kombinatorische und die graphba-sierte Formulierung in Bezug auf den je-weiligen Rechenaufwand untersucht. DerAlgorithmus von Pisinger (1995) ist denübrigen untersuchten Ansätzen in (Yuund Lin 2004) bezüglich des Rechenauf-wands überlegen.

Aggregationsfunktionen werden ver-wendet, um die Werte von QoS-Attributen einer Dienstkomposition zuermitteln, die bedingte Verzweigungenund Parallelisierungen umfasst. Jaegeret al. (2004) und Cardoso et al. (2004)schlagen verschiedene Aggregationsmus-ter vor, die zur Festlegung entsprechen-der Aggregationsfunktionen verwendetwerden können. Aggregationsfunktio-nen zur Ermittlung von Kosten, zur

Berechnung der Verfügbarkeit und zurAggregation der Gesamtausführungs-dauer der Dienstkomposition werdenzur Verfügung gestellt. Yu et al. (2007)schlagen ein QoS-basiertes Dienstaus-wahlmodell vor, das auf den von Jae-ger et al. (2004) vorgeschlagenen QoS-Aggregationsfunktionen basiert. MultipleQoS-Attribute, die zu optimieren sind,werden in einer integrierten Zielfunktionbehandelt, die das SAW-Prinzip verwen-det. Verschiedene exakte Lösungsansätzewerden untersucht.

Der Rechenaufwand, der zur Ermitt-lung optimaler Dienstbindungen erfor-derlich ist, steigt exponentiell mit der An-zahl der Tasks. Aus diesem Grund istman daran interessiert, effiziente Heuris-tiken zu entwickeln, um mit dem erhöh-ten Rechenaufwand umgehen zu können,der in Folge großer Dienstkompositionenentsteht. QoS-basierte Dienstauswahlan-sätze, die auf genetischen Algorithmen(GAs) basieren, wurden von Jaeger undMühl (2007) und Canfora et al. (2005b)unabhängig voneinander vorgeschlagen.Es wurde gezeigt, dass eine Dienstbin-dung, die zulässig bezüglich gegebenerQoS-Restriktionen ist, effizient ermitteltwerden kann. Die Optimierung der QoS-Attribute ist dabei aber verbesserungsfä-hig.

Die Unsicherheit von QoS-Attributenbleibt in den bisher diskutierten Model-len weitestgehend unberücksichtigt. Can-fora et al. (2005a) betrachten unsiche-re QoS-Werte und deren Einfluss aufQoS-Anforderungen. Sie zielen daraufab, die Tasks eines Prozessmodells, d.h.die Bestandteile eines Workflows, die beider Bearbeitung einer Dienstkompositi-on noch nicht ausgeführt wurden, zu be-stimmen. Für die identifizierten Bestand-teile wird eine erneute Dienstauswahl an-gestoßen, wenn sich die aus der Unsi-cherheit ergebende Abweichung der rea-lisierten QoS-Werte von Referenzwerteneinen bestimmten Schwellenwert über-schreiten. Dieser Ansatz wurde von Ra-macher und Mönch (2013) auf die Situa-tion ausgedehnt, dass unsichere Antwort-zeiten und eine global eingeschränkteAusführungszeit berücksichtigt werden.

Die vorgenannten Dienstauswahl-modelle behandeln lediglich die Opti-mierung eines einzelnen Ziels. Falls meh-rere QoS-Attribute zu berücksichtigensind, wird eine integrierte Zielfunktion,die auf SAW basiert, verwendet. Die Be-stimmung der Gewichte für die Integrati-on ist aber schwierig, insbesondere dann,

wenn zusätzliche Informationen, bei-spielsweise bezüglich der Lage alternati-ver Lösungen, fehlen. Infolgedessen sindDienstauswahlmodelle, die auf den Prin-zipien der multikriteriellen Optimierungbasieren, wünschenswert.

Liu et al. (2005) betrachten einenNSGA-II-Ansatz für eine multikriteriel-le Dienstauwahl. Allerdings werden we-der eine geeignete Problemrepräsentati-on angegeben noch numerische Experi-mente mit dem NSGA-II-Ansatz durch-geführt. Ein weiterer Ansatz, der einenGA verwendet, um ein Dienstauswahl-problem im multikriteriellen Sinne zulösen, wurde von Wada et al. (2011)vorgeschlagen. Nicht-dominierte Dienst-bindungen werden für die Ziele Kosten-minimierung und Durchsatzmaximie-rung gesucht. Ein konventioneller GAwird problemspezifisch angepasst, um ei-ne Menge nicht-dominierter Dienstbin-dungen zu ermitteln. Eine Fitnessfunk-tion, ähnlich zu der in NSGA-II, be-wertet ein Chromosom in Bezug darauf,wie stark es andere Chromosomen do-miniert und bezüglich seiner Entfernungzu anderen Lösungen in der Populati-on, um dadurch die Bestimmung nicht-dominierter Lösungen zu unterstützen.

Ein multikriterieller Ansatz, der aufganzzahliger Optimierung (Integer Pro-gramming (IP)) basiert, wird von Wieseet al. (2008) vorgeschlagen. Das Dienst-auswahlmodell berücksichtigt unsiche-re Antwortzeiten und unsichere Kosten.Das Ziel der Dienstauswahl besteht dar-in, das Risikomaß Average Value at Riskder Kosten sowie die Gesamtdauer derDienstkomposition zu minimieren, wo-bei das Erreichen einer Mindestverfüg-barkeit der Dienstkomposition als Ne-benbedingung betrachtet wird. Die Zie-le werden unabhängig voneinander opti-miert, um nicht-dominierte Lösungen zuerhalten.

Mit Ausnahme von Wiese et al. (2008)berücksichtigen multikriterielle Dienst-auswahlansätze keine unsicheren QoS-Attribute. Unter Berücksichtigung vonunsicheren Antwortzeiten versucht diein diesem Artikel vorgeschlagene Dienst-auswahl, eine robuste Dienstbindung zuidentifizieren, die eine zuverlässige Aus-führung der Dienstkomposition ermög-licht. Obwohl andere QoS-Attribute be-trachtet werden, wird ein ähnliches Zielvon Wiese et al. (2008) verfolgt. In (Wie-se et al. 2008) wird ein IP-Ansatz ge-wählt, der allerdings nicht in der Lageist, mit großen Dienstkompositionen inangemessener Rechenzeit umzugehen, da

WIRTSCHAFTSINFORMATIK 3|2014 163

WI – AUFSATZ

das Problem NP-schwer ist. Aus diesemGrund besteht das Ziel des vorliegendenArtikels darin, einen heuristischen Lö-sungsansatz vorzuschlagen, der in der La-ge ist, sogar für große Dienstkomposi-tionen eine Pareto-Front mit angemes-senem Zeitaufwand zu ermittelt. Das indieser Arbeit vorgeschlagene Verfahrenist der erste uns bekannte Ansatz, derproblemspezifische Heuristiken für dasDienstkompositionsproblem verwendet,um die Effizienz der zugrundeliegendenMetaheuristik zu verbessern.

3 Rahmenwerk für diemultikriterielle Dienstauswahl

3.1 NSGA-II-basierter Lösungsansatz

3.1.1 Funktionsweise von NSGA-II

Der NSGA-II-Ansatz wurde von Debet al. (2002) vorgeschlagen und stellt ei-ne etablierte Metaheuristik zur Appro-ximation der wahren Pareto-Front fürkombinatorische Optimierungsproblemedar. Wie in Talbi et al. (2012) disku-tiert, sind aber prinzipiell auch ande-re Metaheurisiken für die Lösung die-ser Problemstellung geeignet. Die NSGA-II-Metaheuristik basiert auf Selektion,Crossover und Mutation zur Ermittlungneuer Populationen von Chromosomen.Der Selektionsmechanismus des NSGA-II-Ansatzes unterstützt die Bestimmungvon Pareto-optimalen Lösungen. Als Teildes Selektionsmechanismus verbessertein Crowding-Operator die Diversifizie-rung von Lösungen auf der Pareto-Front,um eine möglichst gute Abdeckung derwahren Pareto-Front zu gewährleisten.Um den NSGA-II-Ansatz auf das MCSS-Problem anwenden zu können, sind ei-ne Problemkodierung und eine geeigneteBewertungsmethode festzulegen.

3.1.2 Lösungsrepräsentation undgenetische Operatoren

Das MCSS-Problem gestattet in natürli-chen Art und Weise die nachfolgend be-schriebene Kodierung von Lösungen. Ei-ne Dienstbindung für eine Dienstkompo-sition mit n Tasks wird durch ein Chro-mosom mit n Genen dargestellt. Das i-teGen bestimmt den Dienst sij ∈ Si, deran Task ti gebunden ist. Das i-te Gennimmt einen Wert aus der Allelmenge{1, . . . , |Si|} an.

Nachkommen eines Chromosom wer-den durch einen Uniform-Crossover-Operator bestimmt. Der Nachkomme o1

wird von zwei Eltern c1 und c2, diedurch eine Wettkampfselektion identifi-ziert werden, abgeleitet. Für jedes Genvon o1 wird ein Elternchromosom ausder Menge {c1, c2} mit Wahrscheinlich-keit ps ausgewählt. Der Wert des Gens desausgewählten Elternchromosoms wirdals Wert des Gens für den Nachkommenübernommen.

Der Mutation-Operator verändert diedurch ein Chromosom kodierte Dienst-bindung zufällig, um eine vorzeitige Kon-vergenz des Algorithmus zu verhindern.Der Mutation-Operator wählt zufallsba-siert die Gene eines Chromosoms aus,die im Rahmen der Mutation betrach-tet werden. Ein Gen wird mit der Wahr-scheinlichkeit pg vom Mutationsoperatorausgewählt. Der Wert eines ausgewähltenGens wird auf einen zufällig bestimmtenWert der korrespondierenden Allelmen-ge gesetzt. Die Chromosomen der initia-len Population werden dadurch ermit-telt, dass die Werte der Gene ebenfallszufällig aus deren korrespondierenderAllelmenge ausgewählt werden.

3.1.3 Bewertung von Chromosomen

Die Fitness eines Chromosoms c, das dieDienstbindung bc kodiert, wird durch dieWerte ocos t(c) und oavail(c) dargestellt.Die erwarteten Kosten c(bc) und die er-wartete Verfügbarkeit a(bc) werden ge-mäß der Beziehungen (2) und (3) be-rechnet. Zusätzlich ist die Zuverlässigkeitψ(bc) zu bestimmen, um zu ermitteln, obeine Dienstbindung zulässig im Hinblickauf die geforderte Mindestzuverlässigkeitist.

Die Zuverlässigkeit ψ(bc) wird durcheine Monte-Carlo-Simulation (MCS) be-rechnet. Die Unsicherheit der Antwort-zeiten wird dazu durch eine endlicheMenge Ω von Szenarien berücksichtigt.Ein Szenario ω ∈ Ω repräsentiert dieAntwortzeit rω(s) ∈ IR+ für jeden Diensts ∈ S, die als Stichprobe aus der Ver-teilung der Antwortzeit von s ermitteltwird. Die Ausführungsdauer der Dienst-komposition bei Vorliegen der Dienst-bindung bc im Szenario ω ist e(bc,ω).Der Wert e(bc,ω) wird entsprechend derBeziehungen (4) und (5) berechnet, wo-bei r(s) = rω(s) verwendet wird. DieZuverlässigkeit ψ(bc) wird abgeschätztdurch:

ψMCS(bc) =∑

ω∈Ω κ(ω)

|Ω| , (7)

wobei κ(ω) den Wert 1 annimmt, wenne(bc,ω) ≤ e gilt und 0 sonst.

Ein Chromosom c ist unzulässig, fallsψMCS(bc) < ψmin gilt. Ein gebräuchli-cher Mechanismus zum Umgang mit un-zulässigen Lösungen besteht in der Ver-wendung von Straftermen. Der StraftermP(c) für ein Chromosom c ist definiertals:

P(c) = max{ψmin − ψMCS(bc),0

}. (8)

Deb (2000) folgend, wird die Fitness desChromosoms c berechnet durch:

ocos t(c) ={

c(bc), falls c zulässig ist,

cmax + P(c), sonst,

(9)

oavail(c) ={

a(bc), falls c zulässig ist,

amin − P(c), sonst.

(10)

In (9) und (10) entsprechen die Wertecmax und amin den höchsten Kosten bzw.der geringsten Verfügbarkeit innerhalbder aktuellen Population.

Die Konkretisierung des NSGA-IIdurch die beschriebene Kodierung undden Bewertungsmechanismus wird alsMCS-GA bezeichnet.

3.2 Heuristische Erweiterungen

Eine Dienstbindung, die durch ein Chro-mosom kodiert wird, kann durch denAustausch von Diensten, die an einen be-stimmten Task gebunden sind, verbessertwerden. Die Auswahl geeigneter Dienstewird durch zwei Heuristiken unterstützt,die Eigenschaften des MCSS-Problemsausnutzen. Wie in Ramacher und Mönch(2012) vorgeschlagen, können die Heu-ristiken in die Metaheuristik eingebettetwerden.

3.2.1 Heuristiken für MCSS

Die Heuristiken beziehen sich auf diedeterministische Version des MCSS-Problems. Aus diesem Grund wird dieunsichere Antwortzeit eines Dienstess ∈ S durch einen geeigneten Schätz-wert rH(s) ∈ IR+ ersetzt. Dieser Wertbasiert wie folgt auf dem Erwartungswertund der mit einem Risikofaktor η ≥ 0multiplizierten Standardabweichung:

rH(s) = E[R] + η√

Var[R], (11)

wobei R eine Zufallsvariable für die Ant-wortzeiten von s ist. Der Risikofaktor

164 WIRTSCHAFTSINFORMATIK 3|2014

WI – AUFSATZ

wird während des Optimierungsprozes-ses geeignet verändert, um die Zulässig-keit des stochastischen Problems sicher-zustellen. Eine Dienstbindung b ist zu-lässig bezüglich der Antwortzeiten, wenne(b) ≤ e gilt, andernfalls ist b unzuläs-sig. Diese beiden Fälle unterscheidend,werden zwei Heuristiken vorgeschlagen:• Repair-Heuristik: Eine unzulässi-

ge Dienstbindung wird so ange-passt, dass die Ausführungsdauer derDienstkomposition verringert wird.

• Improve-Heuristik: Eine zulässigeDienstbindung wird derart verändert,dass die Zielfunktionswerte verbes-sert werden, ohne dabei die maxi-mal mögliche Ausführungsdauer zuüberschreiten.

Die beiden Heuristiken ersetzen einenDienst bi, der an einen Task ti gebun-den ist, durch einen passenden Dienstsij ∈ Si. Diese Ersetzung wird durch eineRebinding-Funktion RB ausgeführt, diewie folgt definiert ist:

RB : B × T × S → B, (b, ti, sij) �→ b′,

(12)

wobei

b′(tk) :={

bk, falls tk ∈ T\{ti},sij, sonst

(13)

gilt.Die Eignung eines Dienstes sij ist ein

Maß, das zur Ermittlung von Dienstenherangezogen werden kann, um Dienstbi zu ersetzen. Die Betrachtung der Eig-nung eines Elements ist typisch für Op-timierungsansätze für das MCKP. Bei-spielsweise schlägt Pisinger (1995) vor,die Wahrscheinlichkeit dafür, dass einElement Bestandteil einer optimalen Lö-sung ist, durch den Quotienten aus sei-nem Nutzen und seinem Gewicht abzu-schätzen. Für die Dienstauswahl wird dieEignung eines Dienstes in Abhängigkeitvon zwei Gewichtungsfaktoren wcos t(b)und wavail(b) wie folgt berechnet:

μb(sij) = [wcos t(b)

(c(sij) − c(bi)

)

+ wavail(b)(a(bi) − a(sij)

)]

× [rH(bi) − rH(sij)

]−1. (14)

Die Größe μb(sij) schätzt dabei ab, inwelchem Ausmaß die Kosten und dieVerfügbarkeit des Dienstes pro Zeitein-heit verändert wird, wenn Dienst sij da-zu verwendet wird, Task ti anstelle von biauszuführen.

Die Menge Di der dominierendenDienste für Task ti ist durch

Di = {sij ∈ Si|c(sij) ≤ c(bi), a(sij) ≥ a(bi),

rH(sij) ≤ rH(bi)}

(15)

gegeben. Jeder Dienst sij ∈ Di kann da-zu verwendet werden, bi zu ersetzen,ohne die Ausführungsdauer der Dienst-komposition zu erhöhen oder die Werteder zu optimierenden QoS-Attribute zuverschlechtern.

3.2.2 Repair-Heuristik

Das Ziel der Repair-Heuristik bestehtdarin, einen Dienst bi durch einen Dienstsij ∈ Si zu ersetzen, der eine geringereAntwortzeit besitzt, um so die Gesamt-ausführungsdauer der Dienstkompositi-on zu verringern. Die einzelnen Taskstragen unterschiedlich zu einer Verrin-gerung der Ausführungsdauer bei. DieEignung eines Tasks wird durch einTaskgewicht R

b (ti) berechnet, das für dieRepair-Heuristik wie folgt definiert ist:

Rb (ti)

=∑

{p∈P|ti∈T[p]} max{eb(p) − e,0}∑

p∈P max{eb(p) − e,0} .

(16)

Das Taskgewicht Rb (ti) ist wohldefiniert,

wenn wenigstens ein Ausführungspfaddie Ausführungsdauerrestriktion über-schreitet. Die Größe R

b (ti) ist 0, wennti nur zu Ausführungspfaden gehört,die nicht die maximal mögliche Ausfüh-rungsdauer verletzen. In dieser Situati-on kann Task ti nicht dazu beitragen,die Ausführungsdauer zu verringern. DerWert R

b (ti) wird größer, wenn ti zu min-destens einem Ausführungspfad gehört,der die Ausführungsdauerrestriktion ver-letzt.

Die Repair-Heuristik besteht aus zweiPhasen. In der ersten Phase werden nurDienste aus Di betrachtet. Für jeden Taskti wird der Dienst sij ∈ Di mit der nied-rigsten Antwortzeit aus Di ausgewähltund zur Ersetzung von bi verwendet, wo-bei im Falle mehrere Dienste mit nied-rigster Antwortzeit einer zufällig gewähltwird. Wenn die so erhaltene Dienstbin-dung immer noch unzulässig ist, fährtdie Heuristik mit einer zweiten Phasefort. Die Repair-Heuristik betrachtet inder zweiten Phase den kombinierten In-dex μR

b (sij) = μb(sij)/Rb (ti), um die Eig-

nung von Dienst sij zu berechnen. Der

Wert von μRb (sij) ist positiv und klein für

diejenigen sij, deren Kosten im Vergleichzu bi nur geringfügig größer sind, derenVerfügbarkeit nur geringfügig geringer istund bei denen Task ti stark zur Verringe-rung der Gesamtausführungsdauer bei-trägt. Die zweite Phase wird durch diefolgende Schrittfolge implementiert:• Schritt 1: Bestimme alle Ausführungs-

pfade, welche die Ausführungszeitre-striktion verletzten, d.h. Pb = {p ∈P|eb(p) > e}. Beende die Heuristik,falls Pb = ∅ gilt. In diesem Fall ist dieDienstbindung zulässig.

• Schritt 2: Ermittle diejenigen Diens-te, welche die Ausführungsdauer derDienstkomposition verringern, d.h.

SRb = {

sij|rH(sij) < rH(bi), ti ∈ T[Pb]}.

(17)

Beende die Heuristik, wenn SRb = ∅

gilt. In diesem Fall existiert keine zu-lässige Lösung.

• Schritt 3: Wähle zufällig einen Dienstsij ∈ SR

b mit dem niedrigsten Wert

von μRb (sij) aus und leite daraus b′ =

RB(b, ti, sij) ab.• Schritt 4: Setze b = b′ und fahre mit

Schritt 1 fort.Wir bemerken, dass die Berechnung derGröße μR

b (sij) in Schritt 3 für alle sij ∈SR

b möglich ist, da rH(sij) = rH(bi) si-

chergestellt ist und Rb (ti) > 0 gilt, weil

nur Tasks betrachtet werden, die zu ei-nem Ausführungspfad gehören, der dieAusführungsdauerrestriktion verletzt.

3.2.3 Improve-Heuristik

Diese Heuristik zielt darauf ab, die Kos-ten und die Verfügbarkeit für eine zu-lässige Dienstbindung zu verbessern. DieImprove-Heuristik besteht wiederum auszwei Phasen. In einer ersten Phase wirdder Dienst sij ∈ Di mit dem niedrigstenWert für wcos t(b)c(sij) − wavail(b)a(sij)

ausgewählt und an ti gebunden, umdie Zielfunktionswerte zu verbessern.Die Gesamtausführungsdauer kann sichnicht durch die Auswahl eines Dienstesaus Di vergrößern. Deshalb bleiben dieDienstbindungen nach der ersten Phasezulässig.

In der zweiten Phase wird die po-sitive Differenz (Schlupf) zwischen derAusführungsdauer eines Ausführungs-pfades und der Ausführungsdauerre-striktion ausgenutzt, um die Zielfunk-tionswerte weiter zu verbessern. Ana-log zur Repair-Heuristik wird die Eig-nung eines Tasks, zu einer Verbesserung

WIRTSCHAFTSINFORMATIK 3|2014 165

WI – AUFSATZ

der Zielfunktionswerte beizutragen ohnedie Ausführungsdauerrestriktion zu ver-letzen, betrachtet. Das Gewicht von Taskti mit Bezug auf den Schlupf der Ausfüh-rungspfade, zu denen er gehört, wird wiefolgt berechnet:

Ib(ti)

= min{p∈P|ti∈T[p]} max{e − eb(p),0}∑

p∈P max{e − eb(p),0} .

(18)

Die Größe Ib(ti) nimmt einen großen

Wert für Task ti an, wenn dieser nurzu Ausführungspfaden mit einen großenSchlupf gehört. Das Taskgewicht ist 0für einen Task, der zu wenigstens einemAusführungspfad gehört, dessen Ausfüh-rungszeit größer gleich e ist. Das Taskge-wicht wird gemeinsam mit μb im kom-binierten Index μI

b(sij) = μb(sij) · Ib(ti)

berücksichtigt. Der Wert von μIb(sij) ist

umso größer, je stärker durch sij pro Zeit-einheit die Kosten reduziert und die Ver-fügbarkeit erhöht werden, bezogen aufdie Verzögerung der Dienstkomposition,die durch sij verursacht wird.

Die Improve-Heuristik besteht aus dernachfolgenden Schrittfolge. Die MengeCS ⊆ S stellt die Menge der Dienste dar,die nicht mehr von der Heuristik berück-sichtigt werden. Als Initialwert wird CS =∅ verwendet.• Schritt 1: Ermittle die Menge aller

Dienste, die zu einer Verbesserung vonKosten und Verfügbarkeit führen, d.h.

SIb = {

sij|c(sij) < c(bi),

a(sij) > a(bi), sij ∈ S\CS}. (19)

Beende die Heuristik, falls SIb = ∅ gilt.

• Schritt 2: Wähle zufällig den Dienstsij ∈ SI

b mit dem größten Wert für

μIb(sij) aus und leite daraus die Bin-

dung b′ = RB(b, ti, sij) ab.• Schritt 3: Falls e(b′) ≤ e gilt, setze b =

b′ und fahre mit Schritt 1 fort. Fügeansonsten sij zu CS hinzu und gehe zuSchritt 1.Es wird angemerkt, dass für jeden

Dienst sij ∈ SIb aufgrund der ersten Phase

der Heuristik die Ungleichung rH(sij) >

rH(bi) gültig ist. Daraus folgt, dass derkombinierte Index μI

b(sij) für alle sij ∈ SIb

wohldefiniert ist.

3.2.4 Hybridisierung von MCS-GA

Die Repair- und die Improve-Heuristikwerden innerhalb von MCS-GA verwen-

det, um die Dienstbindungen zu verbes-sern, die durch die Chromosomen re-präsentiert werden. Im Rahmen der In-tegration sind die Gewichtungsparame-ter wcos t(b) und wavail(b) festzulegen,der Risikofaktor η anzupassen sowie dieChromosomen auszuwählen, auf welchedie Heuristiken anzuwenden sind.

Eine Anwendung der Heuristiken aufjedes Chromosom ist nicht sinnvoll, dadie Heuristiken ein Greedy-Verfahrenanwenden. Unterschiedliche Lösungenkönnen so auf eine einzelne Lösung abge-bildet werden. Dadurch wird die Diversi-tät der Population verringert. Das Chro-mosom, auf das die Heuristiken ange-wandt werden, wird unter Verwendungeiner Auswahlwahrscheinlichkeit ausge-wählt. Diese Wahrscheinlichkeit hängtvon einem Temperaturparameter Θ ∈[0,1] und einer Charakterisierung ξ(Pi)

der Population ab. Die Größe Θ wirddurch Θ = 1 initialisiert. Sie wird nachjeder Generation linear verringert, sodass am Ende des Algorithmus Θ = 0erreicht wird. Zur Charakterisierung vonPopulation Pi wird der Anteil zulässigerDienstbindungen herangezogen, d.h., wirbetrachten:

ξ(Pi) = |{bc|c ∈ Pi,ψMCS(bc) ≥ ψmin}||Pi| .

(20)

Die Größen PR und PI geben an,wie wahrscheinlich die Anwendung derRepair- bzw. der Improve-Heuristik ist.Diese Größen werden wie folgt gewählt:

PR = (1 − ξ(Pi)

)Θ, (21)

PI = ξ(Pi)Θ. (22)

Zwei Zufallszahlen rR, rI ∈ [0,1] werdenunabhängig voneinander gewählt, nach-dem ein Chromosom c erzeugt wurde.Die Heuristik h wird auf c angewandt,falls rh ≤ Ph für h = R oder h = I gilt.Wenn viele Lösungen unzulässig sind, istdie Wahrscheinlichkeit PR groß. In die-ser Situation wird die Repair-Heuristikhäufig angewandt. Als Ergebnis werdenzulässige Lösungen in der Populationetabliert.

Andererseits wird im Falle vieler zu-lässiger Lösungen die WahrscheinlichkeitPI erhöht. Die positiven Schlupfwertekönnen in dieser Situation ausgenutztwerden, um die Zielfunktionswerte zuverbessern.

Der Wert des Risikofaktors η, zu Be-ginn des Verfahrens als 0 gewählt, wird

angepasst, indem die Zulässigkeit der vonden Heuristiken ermittelten Lösungenberücksichtigt wird. Jedes Mal wenn ei-ne der Heuristiken angewandt wird, wirddie Zulässigkeit von c evaluiert, indemder Strafterm P(c), definiert durch (10),ausgewertet wird. Anschließend wird η

durch η = η + P(c) · Θ aktualisiert. DieAnpassung berücksichtigt die Zulässig-keit des MCSS-Problems, denn der Risi-kofaktor wächst in dem Maße wie die Un-zulässigkeit, die durch P(c) repräsentiertwird. Die Abhängigkeit vom Temperatur-parameter stellt sicher, dass die Schritt-weite der Anpassung gegen Verfahrensen-de kleiner wird, um eine Konvergenz vonη zu ermöglichen.

Die Gewichte wcos t(b) und wavail(b)werden, Deb und Goel (2001) folgend, inAbhängigkeit von der aktuellen Dienst-bindung b wie folgt gewählt:

wcos t(b) = (cmax − c(b))

(cmax − cmin)2, (23)

wavail(b) = (a(b) − amin)

(amax − amin)2. (24)

Die Werte cmax und cmin stellen die ma-ximalen und minimalen Kosten einerDienstbindung in der aktuellen Pareto-Front dar. In analoger Weise sind amaxund amin die maximale und die minima-le Verfügbarkeit. Wir nehmen an, dasscmax = cmin und amax = amin gilt. Fallsdas nicht der Fall ist, werden die Ge-wichte auf den Wert 1 gesetzt. Die Wahlder Gewichte zwingt die Heuristiken da-zu, das Ziel zu begünstigen, das näheran seinem individuellen Optimum ist.Die hybride Variante von MCS-GA wirdMCS-GA-H genannt.

3.3 Exakter Lösungsansatz

Die ε-Constraint-Methode gestattet ei-ne unabhängige Optimierung von mehr-fachen Zielen, um eine Pareto-Front zuerhalten (vergleiche Ehrgott 2010 fürDetails). Anstelle die unterschiedlichenZiele in eine Zielfunktion zu integrie-ren, wird ein einzelnes Ziel in einembestimmten Schritt optimiert, währenddie übrigen Ziele in Nebenbedingungenumgewandelt werden. Ein ε-Constraint-Problem mit K Zielen fk, k = 1, . . . ,K ,die zu minimieren sind, kann wie folgtangegeben werden:

min fk (25)

unter den Nebenbedingungen

fj ≤ εj, j = 1, . . . ,K, j = k. (26)

166 WIRTSCHAFTSINFORMATIK 3|2014

WI – AUFSATZ

Die ε-Constraint-Formulierung desMCSS-Problems wird in (27)–(30) an-gegeben. Die Größen Ecos t,Eavail ∈ {0,1}und εcos t, εavail ∈ IR sind Parameterdes Modells. Die Wahl Ecos t = 1 undEavail = 0 führt zu einer Kostenminimie-rung, wobei die minimale Verfügbarkeitεavail als Nebenbedingung für die Verfüg-barkeit verwendet wird. Durch die um-gekehrte Wahl Ecos t = 0 und Eavail = 1wird durch das Modell eine Maximie-rung der Verfügbarkeit angestrebt, wobeidie Kosten durch die Nebenbedingungεcos t eingeschränkt sind. Wir erhalten:

minb∈B

Ecos t c(b) − Eavaila(b) (27)

unter den Nebenbedingungen:

(1 − Ecos t)c(b) ≤ εcos t, (28)

a(b) ≥ (1 − Eavail)εavail, (29)

P(e(b) ≤ e

) ≥ ψmin. (30)

Die Ungleichungen (28) und (29) sinddie ε-Nebenbedingungen. Die Zuverläs-sigkeitsnebenbedingung ist durch (30) alsChance-Constraint formuliert. Die Be-rechnung von a(b) kann durch eine lo-garithmische Transformation linearisiertwerden. Die Wahrscheinlichkeit P(e(b) ≤e) kann näherungsweise durch einenszenario-basierten Ansatz ermittelt wer-den, bei dem die Antwortzeiten, die zurBerechnung von e(b) erforderlich sind,wie von Wiese et al. (2008) vorgeschla-gen, durch eine Stichprobe aus den Ver-teilungsfunktionen der Antwortzeiten er-hoben werden. Daraus folgt insgesamt,dass das Modell (27)–(30) als lineares IPimplementiert werden kann.

Das Modell (27)–(30) wird iterativ ge-löst, um eine Menge Pareto-optimalerDienstbindungen zu erhalten. Die ersteIteration startet mit Ecos t = 0, Eavail = 1,εavail = 0 und εcos t = M, wobei M dieSumme der Kosten aller Dienste in S ist.Als Lösung erhält man eine Dienstbin-dung mit der Verfügbarkeit acur , wobeidie Kosten durch M eingeschränkt sind.Danach wird das IP ein zweites Mal ge-löst, wobei Ecos t = 1, Eavail = 0, εavail =acur und εcos t = M verwendet werden.Dieses Vorgehen führt zu einer Pareto-optimalen Dienstbindung mit Verfügbar-keit acur und Kosten ccur . Die nächsteIteration startet mit Ecos t = 0,Eavail =1, εavail = 0 und εcos t = ccur − δ, wobeiδ ein Wert ist, der kleiner als die Kosten-differenz zwischen zwei beliebigen Diens-ten in S ist. Dieses Vorgehen wird wieder-holt, bis das IP für die Parameter εavail

Tab. 1 Versuchsdesign

Faktor Design Level Anzahl

Prozessmodelltyp (CTyp) SMALL Small, medium 2

LARGE Large 1

Anzahl der Dienste (m) SMALL 4, 6, 8 3

LARGE 10, 20, 30 3

Mindestzuverlässigkeit (ψmin) SMALL 0,94 1

LARGE 0,92, 0,94, 0,96, 0,98 4

Unsicherheit der Antwortzeiten (mr) SMALL 0,25 1

LARGE 0,15, 0,25, 0,35 3

Einschränkung der Ausführungsdauer (me) SMALL 0,20 1

LARGE 0,10, 0,15, 0,20, 0,25, 0,30 5

und εcos t keine zulässige Lösung mehrbesitzt. Die verwendeten Probleminstan-zen für die ε-Constraint-Methode stel-len sicher, dass keine zwei Dienste mitidentischen Kosten existieren. Aus die-sem Grund gilt stets δ > 0. Allerdingskann in praktischen Situationen δ = 0auftreten. In diesem Fall ist dann dieε-Constraint-Methode nicht anwendbar.

4 Numerische Experimente

Die Leistungsfähigkeit von MCS-GA undMCS-GA-H wird im Hinblick auf die er-reichte Lösungsqualität und den Rechen-aufwand im Vergleich zur ε-Constraint-Methode ermittelt. Zufällig erzeugte Pro-bleminstanzen werden verwendet. Ob-wohl die Probleminstanzen synthetischsind, werden sie einer Versuchsplanungfolgend generiert, die einen großen Be-reich von Faktoren abdeckt.

4.1 Versuchsplanung

Tabelle 1 zeigt die Faktoren, die zur Ge-nerierung der Probleminstanzen verwen-det werden. Es werden zwei Versuchsdesi-gns, die als SMALL und LARGE bezeich-net werden, unterschieden. Der FaktorCTyp bestimmt das Prozessmodell deruntersuchten Dienstkomposition. Das inAbb. 1 gezeigte Prozessmodell wird da-bei als medium bezeichnet. Das Prozess-modell vom Typ small bzw. large erhältman durch Entfernen bzw. Hinzufügenvon Tasks zum Prozessmodell vom Typmedium. Das Prozessmodell vom Typsmall besteht aus fünf Tasks, während dasProzessmodell vom Typ large 25 Tasksumfasst. Insgesamt werden 186 Faktor-kombinationen betrachtet, wobei für je-de Faktorkombination drei unabhängigeProbleminstanzen generiert werden.

In einer Probleminstanz werden fürjede Dienstklasse m Dienste generiert.Die Kosten und die Verfügbarkeit einesDienstes sij ∈ Si werden durch c(sij) =100(1.5 − r1) und a(sij) = 0.9 + 0.1r2festgelegt, wobei r1, r2 Realisierungen dergleichverteilten Zufallsvariablen R1,R2 ∼U[0,1] sind.

Die Antwortzeit von sij wird durch ei-ne empirische Verteilung mit K = 10Klassen repräsentiert. Die minimale undmaximale Antwortzeit von sij ∈ Si istdurch r0

ij = 100(1 − mr)√

r1r2 bzw. rKij =

100(1+mr)√

r1r2 gegeben. Die Beobach-tungshäufigkeit jeder Klasse wird durchhk

ij = 100rk festgelegt, wobei für jedes

k = 1, . . . ,K der Wert rk eine Realisie-rung der Zufallsvariablen Rk ∼ U[0,1]ist. Die eingeschränkte Antwortzeit istdurch e = (1 − me)r + mer gegeben. Mitr und r werden die minimale und diemaximale Ausführungsdauer der Dienst-komposition unter Berücksichtigung dergenerierten Antwortzeiten bezeichnet.

4.2 Ergebnisse

Die ε-Constraint-Methode wird unterVerwendung des Optimierungswerk-zeugs LPSolve 5.5 implementiert. MCS-GA und MCS-GA-H sind in der Pro-grammiersprache C++ unter Verwen-dung der NSGA-II-Implementierungder MOMHLib-Klassenbibliothek im-plementiert. Die Experimente wurdenauf einem PC mit Intel Pentium IV CPUmit 3.6 GHz und 4 GB RAM durchge-führt. Die Pareto-Front, die von einemAnsatz A ∈ {MCS-GA,MCS-GA-H, ε}ermittelt wird, wird als yA bezeichnet.Die Verfahren MCS-GA und MCS-GA-Hwerden für jede Probleminstanz fünf Malunabhängig voneinander ausgeführt. DieBewertung einer Pareto-Front yA erfolgt

WIRTSCHAFTSINFORMATIK 3|2014 167

WI – AUFSATZ

Tab. 2 Numerische Ergebnisse für das SMALL-Design

Faktor m error dist ONVG Iε Zeit (s)

MCS-GA MCS-GA-H MCS-GA MCS-GA-H MCS-GA MCS-GA-H MCS-GA MCS-GA-H

Small 4 0,000 0,000 0,000 0,000 6,660 6,660 1,000 1,000 1

6 0,000 0,000 0,000 0,000 4,870 4,870 1,000 1,000 4

8 0,018 0,012 0,051 0,029 15,030 15,710 1,001 1,001 25

Medium 4 0,000 0,000 0,000 0,000 10,330 10,330 1,000 1,000 1265

6 0,134 0,072 0,914 0,121 75,930 73,040 1,014 1,005 3688

8 0,279 0,174 7,603 1,517 122,730 81,530 1,207 1,137 35362

im Vergleich zu einer Referenzmengeytrue, die durch Vereinigung der nicht-dominierten Lösungen aller ermitteltenPareto-Fronten für eine Probleminstanzabgeleitet wird. Zur Bewertung von yAwerden die folgenden Maße verwendet:

ONVG(yA) = |yA|, (31)

ONTVG(yA) = ∣∣{

b | b ∈ yA ∩ ytrue}∣∣,

(32)

Iε(yA) = maxb∈ytrue

minb′∈yA

max

{c(b′)c(b)

,a(b)

a(b′)

}

,

(33)

error(yA) = ONTVG(yA)/ONVG(yA),

(34)

dist(yA) = 1

ONVG(yA)

∑

b∈yA

minb′∈ytrue

d(b,b′),

(35)

wobei

d2(b,b′)

= (c(b) − c(b′))2

(cmax(ytrue) − cmin(ytrue))2

+ (a(b) − a(b′))2

(amax(ytrue) − amin(ytrue))2(36)

gilt. ONVG misst die tatsächliche Größeder Pareto-Front yA, während ONTVGder Anzahl nicht-dominierter Lösungeninnerhalb von yA entspricht. Das error-Maß bewertet das Verhältnis von domi-nierten Lösungen und Pareto-optimalenLösungen innerhalb von yA. Das mul-tiplikative ε-Maß Iε ermittelt den Fak-tor, um den die Front yA unter Berück-sichtigung aller zu optimierenden Zieleschlechter ist als die Front ytrue (Zitzleret al. 2003). Der Wert d(b,b′) gibt die Di-stanz zweier Lösungen b und b′ an. Die-se Distanz wird von dist zur Berechnungder durchschnittlichen Distanz zwischenyA und ytrue verwendet.

Die Parametrisierung von MCS-GAund MCS-GA-H wurde auf Basis vonVorversuchen vorgenommen. Die Popu-lationsgröße {50, 75, 100, 150} und dieMutationswahrscheinlichkeit {0,1, 0,2,0,3} wurden in diesen Experimenten un-tersucht. Dabei wurde eine Populations-größe von 100 und eine Mutationswahr-scheinlichkeit von 0,1 als im Durch-schnitt leistungsfähigste Konfigurationfür die Mehrheit der untersuchten Fak-torkombinationen ermittelt. Zusätzlichwurden Pilotexperimente zur Ermittlungvon geeigneten Werten für die Aus-wahlwahrscheinlichkeit ps des Uniform-Crossover-Operators und der Auswahl-wahrscheinlichkeit pg für den Mutations-operator durchgeführt. Basierend auf denPilotexperimenten wird für ps und pg je-weils der Wert 0,5 verwendet, d.h., esfindet ein Münzwurf statt, bei dem dieMünze fair ist. Die Anzahl der Szena-rien zur Schätzung von ψMCS(b) wur-den ebenfalls im Rahmen von Pilotexpe-rimenten festgelegt. Es hat sich herausge-stellt, dass bereits bei 100 Szenarien derFehler |ψMCS(b)−ψ(b)| kleiner als 0,002ist.

Die Probleminstanzen des SMALL-Designs werden durch MCS-GA, MCS-GA-H und durch die ε-Constraint-Methode gelöst. Die Rechenzeit vonMCS-GA und MCS-GA-H wird auf 600Sekunden begrenzt. Die ermittelten Er-gebnisse sind in Tab. 2 dargestellt. EineZeile gibt die durchschnittlichen Wertean, die für die Probleminstanzen ermit-telt wurden, die der in der Faktor-Spalteangegebenen Charakteristik entsprechen.

Die Probleminstanzen des LARGE-Designs werden aufgrund des stark an-wachsenden Rechenaufwandes der ε-Constraint-Methode nur durch MCS-GAund MCS-GA-H gelöst. Die dabei er-mittelten Ergebnisse sind in Tab. 3 inder gleichen Weise wie in Tab. 2 dar-gestellt. Die Rechenzeiten von MCS-GA

und MCS-GA-H sind im LARGE-Designebenfalls auf 600 Sekunden begrenzt.

4.3 Diskussion der Ergebnisse

Die für das SMALL-Design ermitteltenErgebnisse zeigen, dass für m = 4 undm = 6 sowohl MCS-GA als auch MCS-GA-H in der Lage ist, die wahre Pareto-Front zu identifizieren. Die Werte für er-ror, Iε und dist erhöhen sich leicht, wennder Suchraum durch die Betrachtung ei-ner größeren Anzahl von Diensten proTask vergrößert wird. Allerdings zeigendie Ergebnisse, dass für alle untersuch-ten Faktorkombinationen die von MCS-GA und MCS-GA-H bestimmten Pareto-Fronten sehr nah an der wahren Pareto-Front liegen, die durch die ε-Constraint-Methode ermittelt wird. Dabei erzieltMCS-GA-H im Vergleich zu MCS-GA inallen Fällen bessere Werte für das error-und dist-Maß.

Der Vorteil von MCS-GA-H gegenüberMCS-GA nimmt mit einem größer wer-denden Suchraum zu. Wie die Ergebnissedes LARGE-Designs zeigen, erzielt MCS-GA-H in fast allen untersuchten Fak-torkombinationen bessere Ergebnisse alsMCS-GA. Der durch MCS-GA-H erziel-te Vorteil ist insbesondere in Situationengroß, in denen eine schwere Einschrän-kung der Ausführungsdauer vorliegt. Fürdie Experimente mit me = 0,1 ist MCS-GA-H nicht mehr in der Lage, zulässigeLösungen zu finden.

Die Werte für error und Iε erhöhensich für MCS-GA, wenn m größer wird,wodurch deutlich wird, dass die Qualitätder Approximation von ytrue mit zuneh-mender Größe des Suchraums abnimmt.Die Unsicherheit der Antwortzeiten, diedurch den Wert von mr bestimmt wird,beeinflusst die erzielten Ergebnisse nurgeringfügig.

Die Ergebnisse zeigen, dass die in die-sem Artikel beschriebenen Algorithmen

168 WIRTSCHAFTSINFORMATIK 3|2014

WI – AUFSATZ

Tab. 3 Numerische Ergebnisse für das LARGE-Design

Faktor error dist ONVG Iε

MCS-GA MCS-GA-H MCS-GA MCS-GA-H MCS-GA MCS-GA-H MCS-GA MCS-GA-H

m 10 0,635 0,593 1,141 0,561 162,670 156,150 1,127 1,007

20 0,651 0,589 2,176 0,325 163,780 165,920 1,183 1,007

30 0,611 0,601 3,212 0,354 157,120 172,180 1,206 1,005

ψmin 0,92 0,636 0,596 1,354 0,402 161,290 166,270 1,170 1,005

0,94 0,627 0,591 2,749 0,428 172,810 181,330 1,173 1,006

0,96 0,641 0,594 1,699 0,407 158,150 156,440 1,167 1,006

0,98 0,625 0,597 2,692 0,405 152,520 154,960 1,166 1,006

mr 0,15 0,637 0,595 1,876 0,242 169,390 175,880 1,172 1,006

0,25 0,644 0,582 1,899 0,423 139,920 135,930 1,169 1,006

0,35 0,613 0,607 2,728 0,645 174,270 182,450 1,164 1,006

me 0,10 – 0,541 – 0,059 0,000 17,680 – 1,007

0,15 0,670 0,555 9,893 0,088 24,020 61,900 1,158 1,007

0,20 0,672 0,582 4,238 0,335 125,740 138,770 1,170 1,007

0,25 0,632 0,628 1,036 0,560 262,700 256,210 1,171 1,005

0,30 0,598 0,617 0,319 0,705 393,500 349,200 1,168 1,005

Abb. 4 Pareto-Front für eine einzelne Probleminstanz

zur Bestimmung einer geeigneten Appro-ximation einer wahren Pareto-Front ge-eignet sind, wobei der Rechenaufwandim Vergleich zu einem exakten Lösungs-verfahren deutlich gesenkt wird. Ledig-lich in einer Situation mit einer schwerenEinschränkung der Ausführungsdauer istMCS-GA nicht in der Lage, zulässige Lö-sungen zu finden. In einer solchen Si-tuation sind die Erweiterungen in MCS-GA-H erforderlich, um eine Pareto-Frontmit zulässigen Lösungen zu identifizie-ren. In fast allen anderen Fällen konntegezeigt werden, dass die Leistungsfähig-keit des MCS-GA durch die Anwendungder Heuristiken in MCS-GA-H verbessertwird.

Die in Abb. 4 gezeigten Pareto-Frontenverdeutlichen den Wert der robusten

Dienstauswahl. Die Pareto-Fronten wur-den für eine Dienstkomposition mit ei-nem Prozessmodell vom Typ mediumdurch MCS-GA-H und MCS-GA be-stimmt, wobei sich MCS-GA auf dieBetrachtung von Erwartungswerten derAntwortzeiten beschränkt (MCS-GA-E).Die von MCS-GA-H gefundene Pareto-Front liegt sehr nah an der von MCS-GA-E ermittelten Pareto-Front. Dadurchwird gezeigt, dass die Einbußen im Hin-blick auf die zu optimierenden Ziele, dieaus der Sicherstellung einer robusten Lö-sung resultieren, gering sind. Die durchSimulation von 100000 Anfragen ermit-telte Zuverlässigkeit der von MCS-GA-Eidentifizierten Lösungen zeigt allerdings,dass in der von MCS-GA-E bestimmtenPareto-Front keine Lösung der Anforde-

rung an eine Mindestzuverlässigkeit vonψmin = 0,98 genügt, während diese Min-destzuverlässigkeit von mehr als 98 %der Lösungen in der von MCS-GA-Hbestimmten Pareto-Front erfüllt wird.

Für eine weitergehende Untersuchungwurden je fünf Probleminstanzen für je-den Prozessmodelltyp durch MCS-GA-H und MCS-GA-E gelöst und der Anteilder Lösung in den Pareto-Fronten ermit-telt, die eine Mindestzuverlässigkeit vonψmin = 0,98 erfüllen. In den von MCS-GA-E ermittelten Pareto-Fronten erfüllenim Durchschnitt nur 10 %, 4 % und 1 %der Lösungen die Mindestzuverlässigkeitfür Prozessmodelle vom Typ small, medi-um und large, während für MCS-GA-Hdie korrespondierenden Werte auf 98 %,95 % und 93 % ansteigen.

5 Zusammenfassungund Ausblick auf zukünftigeForschungsarbeiten

Eine QoS-basierte Dienstauswahl be-rücksichtigt mehrere, typischerweise inKonflikt stehende und gegebenenfalls un-sichere QoS-Attribute. Die Implementie-rung einer Dienstkomposition unter Ver-wendung von existierenden Diensten er-fordert einen Kompromiss zwischen denin Konflikt stehenden QoS-Attributen.

WIRTSCHAFTSINFORMATIK 3|2014 169

WI – AUFSATZ

Zusammenfassung / AbstractRené Ramacher, Lars Mönch

Robuste multikriterielle Dienstkomposition in Informationssystemen

Dienstkompositionen werden dazu verwendet, Geschäftsprozesse in einer Vielzahlvon Anwendungsdomänen zu implementieren. Die Quality-of-Service (QoS)-basierteAuswahl von Diensten berücksichtigt mehrere, typischerweise konfliktäre und mög-licherweise unsichere QoS-Attribute. Ein multikriterieller Lösungsansatz ist wün-schenswert, um eine Menge alternativer Dienstselektionen zu ermitteln. Außerdemist festzustellen, dass die Unsicherheit von QoS-Attributen in existierenden Ansätzenvernachlässigt wird. Daraus folgt, dass es erforderlich ist, Dienst-Rekonfigurationenzu betrachten, um eine Verletzung von QoS-Restriktionen zu vermeiden. Das inder Arbeit untersuchte Problem ist NP-schwer. Der Artikel stellt einen heuristischenmultikriteriellen Dienstauswahlansatz vor, der dazu entworfen wurde, eine Pareto-Front alternativer Dienstselektionen mit vertretbarem Rechenaufwand zu ermitteln.Die erhaltenen Dienstselektionen sind robust bezüglich einer eingeschränkten Aus-führungsdauer, wenn unsichere Antwortzeiten berücksichtigt werden. Der vorge-schlagene Lösungsansatz basiert auf einem Nondominated Sorting Genetic Algo-rithm (NSGA-II)-Ansatz, der problemspezifische Eigenschaften ausnutzt. Die Anwend-barkeit des vorgeschlagenen Lösungsansatzes wird durch eine Simulationsstudiegezeigt.

Schlüsselwörter: Dienstkomposition, QoS-basierte Dienstauwahl, Genetische Al-gorithmen, Unsichere QoS

Robust Multi-criteria Service Composition in Information Systems

Service compositions are used to implement business processes in a variety of appli-cation domains. A quality of service (QoS)-aware selection of the service to be com-posed involves multiple, usually conflicting and possibly uncertain QoS attributes.A multi-criteria solution approach is desired to generate a set of alternative serviceselections. In addition, the uncertainty of QoS-attributes is neglected in existing solu-tion approaches. Hence, the need for service reconfigurations is imposed to avoid theviolation of QoS restrictions. The researched problem is NP-hard. This article presentsa heuristic multi-criteria service selection approach that is designed to determine aPareto frontier of alternative service selections in a reasonable amount of time. Tak-ing into account the uncertainty of response times, the obtained service selectionsare robust with respect to the constrained execution time. The proposed solutionapproach is based on the Non-dominated Sorting Genetic Algorithm (NSGA)-II ex-tended by heuristics that exploit problem specific characteristics of the QoS-awareservice selection. The applicability of the solution approach is demonstrated by asimulation study.

Keywords: Service composition, QoS-aware service selection, Genetic algorithm,Uncertain QoS

Die Darstellung der Menge von mög-lichen alternativen Implementierungenunterstützt einen Entscheidungsfinderbei der Bestimmung eines solchen Kom-promisses. In diesem Artikel wird einmultikriterielles Dienstauswahlproblemmit unsicheren Antwortzeiten betrach-tet. Der vorgeschlagene Dienstauswahl-ansatz adressiert die Identifizierung ei-ner robusten Dienstauswahl, die in ei-ner Ausführungsumgebung mit unsiche-ren Antwortzeiten die Einhaltung einereingeschränkten Ausführungsdauer beieiner geforderten Mindestzuverlässigkeitgewährleistet. Es wird ein auf der NSGA-II-Metaheuristik basierender Lösungsan-satz zur Bestimmung von Pareto-Frontenvorgeschlagen, um dem multikriteriellenCharakter des Dienstauswahlproblemsgerecht zu werden. Der Lösungsansatzwird durch problemspezifische Heuristi-ken erweitert, die bestimmte Eigenschaf-ten des Dienstauswahlproblems ausnut-zen. Die durchgeführten numerischenExperimente zeigen, dass die Lösungs-ansätze zur Anwendung in einem ope-rativen Umfeld geeignet sind, da einegute Approximation der wahren Pareto-Front in wenigen Minuten ermittelt wer-den kann. Zusätzlich zeigen die erhal-tenen Ergebnisse, dass die Berücksichti-gung der Unsicherheit der Antwortzei-ten im Lösungsverfahren zu einer deut-lichen Verbesserung der Zuverlässigkeiteiner Dienstauswahl führt. Diese Eigen-schaft des vorgeschlagenen Ansatzes istinsbesondere auch unter Management-gesichtspunkten bedeutsam. Wir gehendavon aus, dass dadurch Anwendungenin Wertschöpfungsnetzwerken, im Sup-ply Chain Management oder in mehr-gliedrigen Transportketten mit kombi-niertem Verkehr möglich sind. Außer-dem erwarten wir, dass die Kombina-tion von verbesserter Datenverfügbar-keit und Fortschritt in den Algorith-men zu einer neuen Klasse von Ent-scheidungsunterstützungssystemen füh-ren wird.

Obwohl das vorgeschlagene Dienst-auswahlmodell auf eine robuste Dienst-auswahl abzielt, die unsichere QoS-Attribute berücksichtigt, ist in zukünf-tigen Arbeiten der Ansatz auf die Be-trachtung von ausgefallenen oder nicht-verfügbaren Diensten auszuweiten. Umeine zulässige Ausführung in einer vola-tilen Umgebung im Falle von ausgefalle-nen Diensten zu gewährleisten, sind An-passungen an der Dienstauswahl erfor-derlich.

170 WIRTSCHAFTSINFORMATIK 3|2014

WI – AUFSATZ

Literatur

Aier S, Bucher T, Winter R (2011) Kriti-sche Erfolgsfaktoren für die Gestaltung ser-viceorientierter Informationssysteme: Ab-leitung und empirische Evaluation einesKausalmodells. WIRTSCHAFTSINFORMATIK53(2):75–87

Bertsimas D, Sim M (2004) The price of robust-ness. Operations Research 52(1):35–53

Bichler M, Lin KJ (2006) Service-oriented com-puting. IEEE Computer 39(3):99–101

Canfora G, Di Penta M, Esposito R, VillaniML (2005a) QoS-aware replanning of com-posite web services. In: Proc of the IEEEinternational conference on web services,Orlando, S 121–129

Canfora G, Di Penta M, Esposito R, Villani ML(2005b) An approach for QoS-aware servicecomposition based on genetic algorithms.In: Proc of the international conferenceon genetic and evolutionary computation,Washington, S 1069–1075

Cardoso J, Sheth AP, Miller JA, Arnold J,Kochut K (2004) Quality of service for work-flows and web service processes. Journalon Web Semantics 1(3):281–308

Casati F, Ilnicki S, Jin L, Krishnamoorthy V,Shan M-C (2000) Adaptive and dynamicservice composition in eFlow. In: Proc ofthe 12th international conference on ad-vanced information systems engineering,Stockholm, S 13–31

Deb K (2000) An efficient constraint han-dling method for genetic algorithms. Com-puter Methods in Applied Mechanics andEngineering 186(2):311–338

Deb K, Goel T (2001) A hybrid multi-objectiveevolutionary approach to engineeringshape design. In: Proc of the first in-ternational conference on evolutionarymulti-criterion optimization, Zürich,S 385–399

Deb K, Pratap A, Agarwal S, Meyarivan T(2002) A fast and elitist genetic algorithm:NSGA-II. IEEE Transactions on EvolutionaryComputation 6(2):182–197

Eder J, Panagos E, Pozewaunig H, RabinovichM (1999) Time management in workflow

systems. In: Proc of the 3rd interna-tional conference on information systems,Poznan, S 265–280

Ehrgott M (2010) Multicriteria optimization, 2Aufl. Springer, Berlin

Jaeger MC, Rojec-Goldmann G, Mühl G (2004)QoS aggregation for web service composi-tion using workflow patterns. In: Proc ofthe 8th international enterprise distributedobject computing conference, Monterey,S 149–159

Jaeger M, Mühl G (2007) QoS-based selec-tion of services: the implementation of agenetic algorithm. In: Proc of the KiVSworkshop 2007: service-oriented archi-tectures und service oriented computing,Bern, S 359–370

Jamoussi Y, Driss M, Jèzèquel J-M, BenGhèzala HH (2010) QoS assurance forservice-based applications using discrete-event simulation. International Journal ofComputer Sciences 7(6):1–11

Liu S, Liu Y, Jing N, Tang G, Yu T (2005) A dy-namic web service selection strategy withQoS global optimization based on multi-objective genetic algorithm. In: Proc of the4th international conference on grid andcooperative computing, Beijing, S 84–89

Montreuil B (2011) Toward a physical Inter-net: meeting the global logistics sustain-ability grand challenge. Logistics Research3:71–87

Papazoglou MP, Traverso P, Dustar S, Ley-mann F (2008) Service-oriented comput-ing: a research roadmap. InternationalJournal of Cooperative Information Sys-tems 17(2):223–255

Pisinger D (1995) A minimal algorithm forthe multiple-choice knapsack problem. Eu-ropean Journal of Operational Research83(2):94–410

Qiang H, Jun H, Yun Y, Schneider JG, Hai J,Versteeg S (2012) Probabilistic critical pathidentification for cost-effective monitoringof service-based systems. In: Proc of the9th international conference on servicescomputing, Hawaii, S 178–185

Ramacher R, Mönch L (2012) Heuristiken zurmultikriteriellen Komposition von Diensten

in dienstbasierten Informationssystemen.In: Proc of the Multikonferenz Wirtschafts-informatik 2012, Braunschweig, S 1171–1182

Ramacher R, Mönch L (2013) Reliable ser-vice reconfiguration for time-critical ser-vice compositions. In: Proc of the 10thinternational conference on services com-puting, Santa Clara, S 184–191

Scholl A (2001) Robuste Planung und Opti-mierung. Grundlagen, Konzepte und Me-thoden, Experimentelle Untersuchungen.Physica-Verlag, Heidelberg

Talbi E-G, Basseur M, Nebro AJ, Alba E (2012)Multi-objective optimization using meta-heuristics: non-standard algorithms. In-ternational Transactions in Operational Re-search 19:283–305

Viswanadham N, Kameshwaran S (2009) Or-chestrating a network of activities in thevalue chain. In: Proc of the 5th annualIEEE conference on automation scienceand engineering, Bangalore, S 501–506

Wada H, Suzuki J, Yamano Y, Oba K (2011)E3: multi-objective genetic algorithms forSLA-aware service deployment optimiza-tion problem. IEEE Transactions on ServicesComputing 99(12):1155–1156

Wiese W, Hochreiter R, Kuhn D (2008) Astochastic programming approach for QoS-aware service composition. In: Proc of 8thIEEE international symposium on clustercomputing and the grid, Lyon, S 226–233

Yu T, Lin K-J (2004) Service selection algo-rithms for web services with end-to-endQoS constraints. In: Proc of the IEEEinternational conference on e-commercetechnology, San Diego, S 129–136

Yu T, Zhang Y, Lin K-J (2007) Efficient algo-rithms for Web services selection with end-to-end QoS constraints. ACM Transactionson the Web 1(1):6

Zitzler E, Thiele L, Laumanns M, Fonseca CM,da Fonseca VG (2003) Performance assess-ment of multiobjective optimizers: an anal-ysis and review. IEEE Transactions onEvolutionary Computation 7(1):117–132

WIRTSCHAFTSINFORMATIK 3|2014 171