Anwendung von Metaheuristiken zur Lösung betrieblicher Planungsprobleme : Potenziale und Grenzen...

1 Einfuhrung

In der betrieblichen Praxis stellt sich eineVielzahl gut strukturierter Problemstellun-gen, bei denen hinsichtlich einer skalarenZielfunktion moglichst gute Handlungs-alternativen zu ermitteln sind. Beispielesind die operative Ressourceneinsatzpla-nung in Fertigungssystemen, die Ablauf-planung von Kommissionierauftragen ineinem Lagersystem, die Steuerung der Be-und Entladung von Containerschiffen oderdie Bestimmung von moglichst guten Allo-kationen im Rahmen von kombinatori-schen Auktionen. In der Praxis kann undmuss man sich hinsichtlich einer pragmati-schen Entscheidungsunterstutzung fur dieMehrzahl solcher Problemstellungen aufeine heuristische (d. h. auf eine naherungs-weise) Losung beschranken. Grunde hier-fur sind einerseits der haufig nicht prakti-kable Rechenaufwand zur Bestimmung ei-ner optimalen Losung aufgrund desVorliegens so genannter NP-schwerer (NP-harter) Probleme [GaJo79; ACGþ99]. An-dererseits sind die im Verlauf der Modellie-rung des Problems getroffenen Verein-fachungen und unsichere Problemdaten zuberucksichtigen, weshalb eine optimale Lo-sung des realen Ursprungsproblems in derRegel ohnehin illusorisch ware. Dem-gegenuber ist die wirtschaftliche Entwick-lung problemadaquater Verfahren ein-schließlich einer implementierungstech-nischen Integration mit entsprechendenAnwendungssystemen (etwa ERP-Syste-men) von großerer praktischer Relevanz.Indessen wurde in der Unternehmensfor-schung genau dieser Aspekt der anwen-dungsorientierten Umsetzung von Lo-

sungsverfahren in der Vergangenheit teil-weise vernachlassigt [Fich94]. In diesemKontext ist der plakativen Formulierung„No systems, no impact“ von Nievergeltzuzustimmen [Niev94], sodass es gebotenerscheint, aufbauend auf theoretischen undalgorithmischen Erkenntnissen zu verschie-denen Problemstellungen und Losungsver-fahren mehr Wert auf die Unterstutzungder Systemimplementierung zu legen.

Zielsetzung dieses Beitrages ist es, die Po-tenziale und Grenzen einer softwaretech-nischen Unterstutzung fur die Anwendungso genannter Metaheuristiken konstruktivzu untersuchen. Solche Verfahren habensich in der Forschung als ein effektives In-strumentarium zur Behandlung vielfaltigs-ter Problemstellungen herausgestellt, aller-dings werden die Verfahren in der Praxisnur sehr vereinzelt eingesetzt. Heutzutagesteht einer praktischen Anwendung vonMetaheuristiken unter anderem die oftmalsaufwandige problemspezifische Adaptionund Implementierung entgegen. Es stelltsich die Frage, wie weit ein solcher Auf-wand mittels softwaretechnischer Metho-den reduziert werden kann – etwa mittelsder Entwicklung einer entsprechendenStandardsoftware oder einer relativ all-gemeingultigen Basisarchitektur und hierineingebetteter wiederverwendbarer Soft-warekomponenten. Gerade im Rahmen derWirtschaftsinformatik stellt die Entwick-lung entsprechender Referenzmodelle hin-sichtlich einer tragfahigen Unterstutzungder Gestaltung von Planungssystemen einezentrale Aufgabe dar. So betont Mertens[Mert98, S. 173] als wesentliche Aufgabeder Wirtschaftsinformatik die anwen-dungsbezogene Umsetzung von Methoden

WIRTSCHAFTSINFORMATIK 45 (2003) 4, S. 395–407

Die Autoren

Andreas FinkStefan Voß

Dr. Andreas Fink,Prof. Dr. Stefan Voß,Institut fur Wirtschaftsinformatik,Universitat Hamburg,Von-Melle-Park 5,20146 Hamburg,Tel. 040 42838-4706bzw. 040 42838-3062,Fax 040 42838-5535,E-Mail: [email protected]. [email protected]

Anwendung von Metaheuristikenzur Losung betrieblicherPlanungsproblemePotenziale und Grenzen einersoftwaretechnischen Unterstutzung

WI – Aufsatz

der Informatik und des Operations Re-search (OR): „Im Verhaltnis zur (Kern-)In-formatik fallt der WI [Wirtschaftsinforma-tik] – ahnlich wie in der Relation zum OR– auch die Aufgabe zu, die oft zu einfachenund fur die Praxis nicht reprasentativenBeispiele (,Toy Examples‘), an denen dieInformatiker die Methoden [. . .] zu erlau-tern pflegen, auf Brauchbarkeit in derWirklichkeit zu prufen. Gegebenenfallsmussen exakte, aber letztlich nicht mit ver-nunftigem Implementierungsaufwand undertraglichen Antwortzeiten realisierbareVerfahren durch pragmatische Heuristikenersetzt werden.“ �hnlich wie von Niever-gelt wird also auch hier der eigentlichenpraktischen Systementwicklung und -an-wendung eine zentrale Rolle zugewiesen.In Quintessenz ergibt sich also das Erfor-dernis einer integrierten Anwendung vonErkenntnissen und Methoden der Soft-waretechnik sowie des Operations Re-search, die insbesondere im Rahmen derWirtschaftsinformatik erfolgen kann. Indiesem Zusammenhang prognostiziert Si-mon [Simo97, S. 14]: „The future of infor-mation systems and, for that matter, the fu-ture of OR, depends heavily on bringingsuch a synthesis about.“

Wir folgen im Wesentlichen dem in Bild 1veranschaulichten Vorgehensmodell. ImRahmen eines allgemein auf eine breite An-wendungsdomane ausgerichteten Entwick-lungsprozesses werden in Analyse-, Ent-wurfs- und Implementierungsaktivitatenwiederverwendbare Artefakte erzeugt (do-main engineering), die zur wiederholtenUnterstutzung der eigentlichen Entwick-

lung spezifischer Anwendungssysteme die-nen (application engineering).

Im folgenden Abschnitt wird die Analyseder betrachteten Anwendungsdomane inknapper Form zusammengefasst. Gemein-samkeiten deuten dabei auf konstante Ele-mente von Softwaresystemen hin, wahrendVariabilitat durch entsprechende Adap-tionsmechanismen abgebildet werdenmuss. Die identifizierten Gemeinsamkeitenund Variationspunkte bilden die Grund-lage fur einen entsprechenden software-technischen Entwurf, den wir in Anwen-dung des generischen Programmierpara-digmas vollziehen. Anschließend werdenverschiedene Aspekte einer praktischenAnwendung anhand einer Fallstudie dis-kutiert, bevor letztendlich wesentlicheSchlussfolgerungen zusammengefasst wer-den und ein kurzer Ausblick erfolgt.

2 Metaheuristiken

Heuristische (Such-)Verfahren ermittelnmit einem praktikablen Rechenaufwandgute, aber nicht notwendigerweise optimaleLosungen (im Sinne von Handlungsalter-nativen). Entsprechende Vorgehensweisensind in der Regel problemspezifisch. Meta-heuristiken sind allgemeine, im Wesentli-chen nicht problemspezifische und damitgenerische Prinzipien und Schemata zurEntwicklung und Steuerung heuristischerVerfahren. In der Literatur subsumiertman hierunter insbesondere Verfahren, dieim Rahmen eines Suchprozesses auf die

sukzessive Ermittlung verbesserter Losun-gen abzielen und hierbei auf dem Grund-ansatz der lokalen Suche und/oder aufdem evolutionaren Prinzip aufbauen.Wahrend bei ersterem Ansatz die schritt-weise Variation einer Losung im Mittel-punkt steht, wird bei evolutionaren (gene-tischen) Verfahren die Generierung neuerLosungskandidaten primar durch eineKombination von Elementen von Losun-gen aus einer Ansammlung von Losungenbetrieben. Fur beide Vorgehensweisen gilt,dass die Grundzuge entsprechender Ver-fahren im Sinne einer generischen Schab-lone allgemein (d. h. unabhangig von ei-nem bestimmten Problemtyp) beschriebenwerden konnen, wahrend die eigentlicheAnwendung einer Metaheuristik eine An-passung bzw. Vervollstandigung hinsicht-lich problemspezifischer Losungsraum-strukturen erfordert.

Eine softwaretechnische Unterstutzungder Entwicklung von Planungssystemensetzt eine substanzielle Analyse der An-wendungsdomane voraus (als Verallgemei-nerung einer auf einen konkreten Einzelfallausgerichteten Systemanalyse). Die hier be-trachtete Anwendungsdomane umfasst so-wohl die betrieblichen Problemstellungen(d. h. das eigentliche fachliche Anwen-dungsgebiet im engeren Sinne) als auch indiesem Zusammenhang zweckmaßige Lo-sungsverfahren. In den folgenden beidenAbschnitten wird ausschnittsweise ein ent-sprechendes Domanenmodell beschrieben.Dies umfasst grundlegende problemspezi-fische Abstraktionen und hierauf aufbau-ende metaheuristische Konzepte. Das Do-manenmodell beinhaltet neben einemDomanenvokabular unter anderem durchMerkmalsdiagramme und algorithmischeSpezifikationen beschriebene metaheuristi-sche Verfahren. Im Mittelpunkt steht dieModellierung von Gemeinsamkeiten undVariabilitat entsprechender Konzepte, diehinsichtlich der zu unterstutzenden Ent-wicklung einer domanenbezogenen Vari-antenvielfalt an Anwendungssystemen (inder Literatur auch als Softwarefamilieoder Softwareproduktlinie bezeichnet[WeLa99]) durch entsprechende Entwurfs-abstraktionen bzw. letztendlich Implemen-tierungsartefakte abgebildet werden mus-sen. Im Rahmen der Analyse werdenprimar funktionale Aspekte betrachtet,wahrend weitere Qualitatsfaktoren wieFlexibilitat sowie Effizienz (der letztend-lichen softwaretechnischen Umsetzung) imWesentlichen im Rahmen der entwurfs-und implementierungstechnischen Abbil-


Domänen-analyse

Domänen-Design

Domänen-implementierung

Domänen-Modell

GenerischeArchitektur

Domänen-wissen

Domain Engineering

Komponenten,Generatoren

Anforderungs-analyse

System-Design

System-implementierung

System-Spezifikation

System-Design

SpezifischeAnforderungen

Application Engineering [1..n]

Spezialisierung Adaptation

SpezifischesAnwendungs-system

Bild 1 Domain engineering und application engineering (in Anlehnung an [Carn02])

396 Andreas Fink, Stefan Voß

dung der Analyseabstraktionen relevantsind.

2.1 ProblemspezifischeAbstraktionen

Es ist von verschiedenen Typen von (Pla-nungs-)Problemen Pmit Probleminstanzenp 2 P auszugehen. Einem Problem P kon-nen ein oder mehrere Losungsraume SPbzw. konkret SP(p) mit Losungen s 2 SP(p)zugeordnet werden. Ist aus dem Kontexteine Eindeutigkeit ersichtlich oder wird einabstrakter Losungsraum zugrunde gelegt,so wird im Weiteren SP(p) auch durch S ab-gekurzt (analoges gilt auch fur die weitereNotation). Wir beschranken uns hier aufdie Betrachtung skalarer Zielfunktionenf : S! R, die jeder Losung einen reellenZielfunktionswert zuordnen. Ausgehendvon Minimierungsproblemen besteht dasZiel darin, eine „moglichst gute“ Losung(d. h. eine Losung mit „moglichst kleinem“Zielfunktionswert) zu ermitteln. Fur einenLosungsraum S konnen eine oder mehrereNachbarschaften (Nachbarschaftsstruktu-ren) NS definiert werden, die fur jede Lo-sung s 2 S eine vollstandig geordnete Men-ge von so genannten NachbarlosungenNS(s) ¼ {n1(s), . . . , n|Ns(s)|(s)} festlegen. Einesolche Nachbarschaft ist in Bild 2 ver-anschaulicht. Zu jeder Nachbarlosungn(s) 2 NS(s) korrespondiert ein Zug (Ope-rator) m(s, n(s)) 2 Nm

S (s), der die Transfor-mation von s zu n(s) reprasentiert. Zugem(s, n(s)) sind durch eine zweckmaßigeZugbewertungsfunktion, die die anschei-nende „Vorteilhaftigkeit“ eines solchen Zu-ges ausdrucken soll, zu beurteilen. ImStandardfall kann dies vermoge der im-plizierten Zielfunktionswertveranderungf(s) � f(n(s)) erfolgen (positive Werte kenn-zeichnen dabei „verbessernde“ Zuge). Hin-sichtlich der Anwendung fortgeschrittenerVerfahren zur systematischen �berwin-dung lokaler Optima sind gegebenenfallsweitere problemspezifische Abstraktionenerforderlich (etwa die Dekomposition vonLosungen und Zugen in so genannte Ele-mentarattribute), auf deren Darstellunghier verzichtet wird (vgl. die ausfuhrliche-ren Darstellungen in [Fink00; FiVo02]).

2.2 Metaheuristische Konzepte

Metaheuristiken sind definitionsgemaß ge-nerisch hinsichtlich problemspezifischer

Konzepte. Ihre Definition ist damit in Ab-hangigkeit von den im vorhergehendenAbschnitt eingefuhrten Abstraktionendurchzufuhren. Außerdem konnen Meta-heuristiken bezuglich interner Mechanis-men variieren. Dementsprechend setzt sicheine konkrete Konfiguration C einer Meta-heuristik H aus einer metaheuristikspezi-fischen Konfiguration CH sowie einer Spe-zifikation CP der im vorhergehendenAbschnitt erorterten problemspezifischenAbstraktionen zusammen. Beispielsweiseumfasst bei einem Verfahren der lokalenSuche CH die Festlegung der Regel zur Ge-nerierung und Auswahl von Nachbarlo-sungen sowie CP die Festlegung von Lo-sungsraum und Nachbarschaftsstruktur.Damit ergibt sich eine entsprechende Ge-nerizitat einer Metaheuristik H, die in Ver-bindung mit einer Konfiguration C eineAbbildung einer Startlosung s auf eine Lo-sung s0 bestimmt: HC : s ! s0. (Fur evolu-tionare Algorithmen ist diese Definitionhinsichtlich der Transformation von Lo-sungspopulationen geeignet zu erweitern;wir beschranken uns in diesem Beitrag hin-gegen auf die Verdeutlichung der Konzepteanhand grundlegender lokaler Suchverfah-ren.)

Eine Analyse metaheuristischer Konzeptehinsichtlich Gemeinsamkeiten fuhrt zu ei-ner Dekomposition in relativ elementareAlgorithmen. Letztendliches Ziel ist dasErzeugen komplexer Verfahren durch eineKomposition abgegrenzter algorithmischer

Bausteine (im Sinne eines „Plug&Play“).Wahrend aus einer theoretischen Sichtwei-se eine umfassende Abbildung von Meta-heuristiken durch eine allgemeine Schab-lone prinzipiell moglich erscheint (vgl.etwa [VaAL98]), wird im Hinblick auf einemodulare und erweiterbare Modellbildungund eine anschließende effiziente Umset-zung hierauf verzichtet. Eine hinreichende�bereinstimmung wesentlicher Verfahrenliegt dagegen im Allgemeinen fur die ver-schiedenen grundlegenden Metaheuristik-klassen vor. Hierzu zahlen die einfache(iterative) lokale Suche, simulated anneal-ing und Varianten, verschiedene Auspra-gungen von tabu search sowie die evolutio-naren Algorithmen – eine weitgehend


Kernpunkte fur das Management

In der betrieblichen Praxis stellt sich eine Vielzahl gut strukturierter Problemstellungen (wieetwa die Optimierung von Fertigungsablaufen oder logistischen Prozessen). Hierfur wurdenin der Forschung verschiedenste Losungsverfahren entwickelt. Die Anwendung solcher Ver-fahren im Rahmen praktischer Entscheidungsunterstutzungssysteme setzt jedoch teilweise ei-ne aufwandige anwendungsspezifische Verfahrensumsetzung voraus.

& Zur Vereinfachung dieser Aufgabe wurden in der Programmiersprache Cþþ verschiede-ne Verfahren (aus der Klasse der so genannten Metaheuristiken) als wiederverwendbareSoftwarekomponenten abgebildet.

& Hiermit wird die praktische Anwendung entsprechender Verfahren deutlich vereinfacht.& Allerdings kann ein gewisser Umsetzungsaufwand unvermeidbar sein, sofern eine best-

mogliche Losungsqualitat angestrebt wird.

Stichworte: Metaheuristiken, Heuristiken, Planungsverfahren, Planungsprobleme, Entschei-dungsunterstutzung, Softwarewiederverwendung, Frameworks, Simulation

μ2

μ3

μ4

μ1=μ(s, n1(s))

n1(s)

n2(s)

n3(s)n4(s)

…

…

n|N(s)|(s)

s

μ|N(s)|

Bild 2 Nachbarschaft einer Losung

Anwendung von Metaheuristiken zur Losung betrieblicher Planungsprobleme 397

koharente Abbildung entsprechender Ge-meinsamkeiten erscheint jeweils moglich.Im hier gegebenen Rahmen werden dieseVerfahren nicht naher beschrieben, sodasswir dementsprechend auf die Literatur ver-weisen; vgl. etwa [AaLe97; Fink00; GlLa97;MiFo00; Voss01]. Wir beschranken uns indiesem Beitrag auf die Veranschaulichungdes verfolgten Ansatzes am Beispiel der ite-rativen lokalen Suche.

Merkmalsdiagramme bieten eine zweck-maßige, bezuglich einer spateren Umset-zung neutrale Form der Definition mog-licher Systemauspragungen innerhalb einerAnwendungsdomane. Als Merkmale wer-den dabei alle hinsichtlich einer Differen-zierung moglicher Systemauspragungensignifikanten Systemeigenschaften auf-gefasst [KCHþ90; SCKþ96; CzEi00]. Dasin Bild 3 dargestellte Merkmalsdiagrammverdeutlicht die wesentlichen Gemeinsam-keiten und Variationspunkte iterativer lo-kaler Suchverfahren uber entsprechendeMerkmale bzw. Untermerkmale. Es wirdunterschieden in obligatorische Merkmale(dargestellt durch einen ausgefullten Kreisan der Verbindungslinie), optionale Merk-male (dargestellt durch einen nicht aus-gefullten Kreis) sowie exklusiv alternativeMerkmale (auch bezeichnet als Dimension,dargestellt durch einen Kreisbogen). ZurKennzeichnung einer unvollstandigenMerkmalsdifferenzierung werden angefug-te Ansatze fur eine Verfeinerung in ent-sprechende Untermerkmale verwendet;dies ist beispielsweise der Fall fur die obli-gatorischen Merkmale des Losungsraums(S) sowie der Nachbarschaft (N), die beieiner konkreten Auspragung einer Meta-heuristik zwingend zu konkretisieren sind.Im Rahmen des generellen Konzepts der

iterativen lokalen Suche ist weiterhin dieanzuwendende Nachbarauswahlregel fest-zulegen (dargestellt als obligatorischesMerkmal NeighborSelection), wobei vier(abschließend definierte) Alternativen zurVerfugung stehen: die jeweilige Auswahldes besten Zuges unter Einschrankung aufverbessernde Zuge, des besten Zuges (gege-benenfalls auch des am wenigsten ver-schlechternden Zuges), des ersten ermittel-ten verbessernden Zuges oder eineszufalligen Zuges.

Das optionale Merkmal Diversification re-prasentiert den Mechanismus zum „Ent-kommen“ aus einem lokalen Optimum.Dieses Merkmal ist optional, da bei einereinfachen Greedy-Strategie (SteepestDescent) die Suche nach Erreichen eineslokalen Optimums beendet wird. Ein all-gemeines Abbruchkriterium ist durch dasSymbol W reprasentiert, ohne dass hier-durch bereits mogliche Kriterien abschlie-ßend bestimmt waren. Schließlich sinddurch das obligatorische Merkmal returnzwei Alternativen fur das Ergebnis desSuchalgorithmus abgebildet. Wahrend inder Regel die beste gefundene Losung ver-langt wird, kann andererseits auch die zu-letzt traversierte Losung angefordert wer-den. Die letztere Option ist etwa dannzweckmaßig, wenn ein Suchverfahren miteiner zufalligen Nachbarauswahl als Diver-sifikationsmechanismus im Rahmen einesubergeordneten Verfahrens eingesetztwird.

Die Semantik von Merkmalen und entspre-chenden Systemen ist aufbauend auf demeigentlichen Merkmalsdiagramm naher zubeschreiben. Dies beinhaltet gegebenenfallsso genannte horizontale Regeln, die die

Menge zulassiger Merkmalskombinationeneinschranken. Die zulassigen Merkmals-kombinationen definieren mogliche Sys-temauspragungen (auch bezeichnet als Ex-tension eines Konzepts). Die naherealgorithmische Spezifikation von Konzep-ten kann unter Verwendung sowohl impe-rativer als auch deklarativer Pseudocode-konstrukte erfolgen. Im Rahmen derAnalyse sollte die Verwendung des Pseudo-codes bewusst frei von den Zwangen einerkonkreten Programmiersprache erfolgen(etwa hinsichtlich einer strengen Typisie-rung), um nicht schon bei der semantischenSpezifikation von Konzepten die eigentli-che Umsetzung zu prajudizieren. In Bild 4ist die iterative lokale Suche algorithmischbeschrieben, wobei bei der Schnittstelle instatisch-strukturelle Parameter („< . . .>“),die das grundsatzliche Verhalten eines Al-gorithmus variieren, sowie einfache dyna-mische Parameter („(. . .)“) im Sinne einer�bergabe (und gegebenenfalls Ruckgabe)von Werten bzw. Objekten unterschiedenwird. Die vier statisch-strukturellen Para-meter ergeben sich aus dem Merkmalsdia-gramm. Die dynamischen Parameter dru-cken unter anderem eine Konkretisierungdes Abbruchkriteriums aus. Die Ausgangs-losung bzw. der Aufrufparameter s wirddurch das Verfahren modifiziert und imSinne eines Referenzparameters implizitzuruckgegeben. Als mogliche Abbruchkri-terien sind eine maximale Rechenzeit(Tmax), eine maximale Iterationsanzahl(Imax), eine maximale Wiederholungsanzahl(Rmax) sowie ein abstrakter Parameter wangegeben. Letzterer reprasentiert ein ex-ternes Abbruchkriterium, wodurch eineasynchrone Terminierung der Suche mog-lich ist (etwa eine Losungsanforderung imRahmen einer Echtzeitplanung). Zweck-maßige Standardvorgaben fur Parametersind durch entsprechende Gleichsetzungenin der Parameterliste kenntlich gemacht.

Die in Bild 4 spezifizierte Grundform deriterativen lokalen Suche basiert auf einerwiederholten Ausfuhrung eines elementa-ren Suchprozesses, der in der Regel in ei-nem lokalen Optimum zum Abschlusskommt (dann existiert kein gultiger Lo-sungskandidat in der Nachbarschaft).Durch den Aufruf eines Diversifikations-verfahrens wird dann ein neuer Ausgangs-punkt fur die nachste Ausfuhrung des ele-mentaren Suchprozesses ermittelt. Zurbeispielhaften Verdeutlichung der Kon-struktion spezifischer Verfahren durch eineKomposition entsprechender Bausteine sindin Bild 5 zunachst zwei konkrete Nach-


Bild 3 Merkmalsdiagramm iterativer lokaler Suchverfahren

IteratedLocalSearch

S N Diversification Ω return

best last

NeighborSelection

best positive best first positive random


barauswahlregeln angegeben (entsprechendder Merkmale best sowie random ausBild 3). Auf dieser Grundlage kann gemaßBild 5 etwa die einfache Greedy-Strategie(SteepestDescent), ein vollstandig zufalls-gesteuertes Suchverfahren RandomWalkund hierauf aufbauend IteratedSteepest-DescentWithPerturbationRestarts einfachdefiniert werden (wobei das Symbol f fureinen nicht relevanten Parameter bzw. eine„leere“ Parameterbelegung steht). Das letz-tere Verfahren reprasentiert die klassischeAuspragung einer iterativen lokalen Suchedergestalt, dass jeweils nach Erreichen ei-nes lokalen Optimums eine bestimmte An-zahl zufalliger Zuge ausgefuhrt wird (uberdie Nutzung von RandomWalk als Aus-pragung der Diversification) und von derdamit erreichten Losung die Suche fort-gefuhrt wird. In diesem Sinne ergibt sich,insbesondere im Zusammenhang mit denhier nicht beschriebenen fortgeschrittenenMetaheuristiken (wie insbesondere simu-lated annealing, tabu search und evolutio-nare Algorithmen) eine Fulle an Kombina-tionsmoglichkeiten. Es stellt sich nun diezentrale Frage, inwieweit derartige Kom-positionsprozesse nicht nur in einer sol-chen abstrakten Darstellungsform sondernauch softwaretechnisch automatisiert um-gesetzt werden konnen.

2.3 „No Free Lunch“-Theorem

In den beiden vorausgegangenen Abschnit-ten wurden Metaheuristiken auf derGrundlage einer scharfen Trennung inproblemspezifische Abstraktionen und ele-mentare metaheuristische Konzepte be-schrieben. Ein auf dieser Grundlage zu ge-staltender softwaretechnischer Entwurfhangt nun entscheidend von dem Ausmaßder zu unterstutzenden Adaption ab. Idea-lerweise besaße man ein allgemeines, nichtproblemspezifisches heuristisches Verfah-ren, das unabhangig von Problemvariatio-nen andere Verfahren hinsichtlich Kriterienwie insbesondere Losungsqualitat und Re-chenzeit dominiert. Ein solches Verfahrenkonnte etwa auf einer allgemeingultigenLosungsreprasentation in der Form klassi-scher mathematischer Optimierungs-modelle operieren (auf der Grundlage einerlinearen oder nicht linearen Zielfunktion,kontinuierlichen und/oder ganzzahligenVariablen sowie einzuhaltenden Gleichun-gen und Ungleichungen). Fur gut struktu-rierte betriebswirtschaftliche Planungspro-bleme kann man entsprechende Modelle in


Bild 4 Pseudocode iterativer lokaler Suchverfahren

BestNeighbor < S, N > ( s ) :

j = argmax{ f (μ(s, nj(s))) | j=1,…,|N(s)|};return nj(s);

RandomNeighbor < S, N > ( s ) :

j = Random( |N(s)| );return nj(s);

SteepestDescent< S, N > ( s, Tmax, Imax, ω ) :

IteratedLocalSearch< S, N, BestPositiveNeighbor, φ >( s, Tmax, Imax, 1, ω, true );

RandomWalk< S, N > ( s, Tmax, Imax, ω, returnBest ) :

IteratedLocalSearch< S, N, RandomNeighbor, φ >( s, Tmax, Imax, 1, ω, returnBest );

IteratedSteepestDescentWithPerturbationRestarts< S, N >( s, Tmax, Imax, Rmax, perturbations, ω ) :

IteratedLocalSearch< S, N, BestPositiveNeighbor,RandomWalk< S, N >( φ, ∞, perturbations, ω, false ) >

( s, Tmax, Imax, Rmax, ω, true );

Bild 5 Konstruktion von SteepestDescent, RandomWalk sowieIteratedSteepestDescentWithPerturbationRestarts

IteratedLocalSearch< S, N, NeighborSelection, Diversification >( s, Tmax=∞, Imax=∞, Rmax=1, ω=false, returnBest=true ) :

Ω : (t ≥ Tmax) or (ω)sbest = s;for r = 1 to Rmax

if r > 1

Diversification( s );i = 0;do

i = i + 1;

s‘ = NeighborSelection< S, N >( s );if s‘ is valid

s = s‘;if f ( s ) < f ( sbest )

sbest = s;

while (s‘ is valid) and (i < Imax);if returnBest

s = sbest;


der Regel relativ leicht formulieren. Esstellt sich somit die Frage, inwieweit ein indiesem Sinne allgemeingultig dominantesheuristisches Verfahren existiert. Bei positi-ver Beantwortung dieser Frage konnte mansich gegebenenfalls auf die Entwicklung,Implementierung und Anwendung einessolchen universellen Verfahrens beschran-ken (ohne eine Differenzierung von Lo-sungsraumen, Nachbarschaftsstrukturenund Rekombinationsoperatoren in Be-tracht ziehen zu mussen).

Ein allgemein anwendbares heuristischesSuchverfahren, das ausschließlich Informa-tionen zu Zielfunktionswerten von Losun-gen verwendet (Blackbox-Ansatz), wirdauch als blind search bezeichnet [Culb98].Diesbezuglich kann man zeigen, dass –leicht vereinfacht ausgedruckt – kein sol-ches Verfahren besser als eine zufalligeEnumeration von Losungen (randomsearch) sein kann, falls die Ergebnisse uberalle moglichen Zielfunktionen gemitteltwerden. Das heißt, es gibt kein universelluberlegenes, allgemein anwendbares Ver-fahren, weshalb dieses Resultat auch als„No Free Lunch“-Theorem bezeichnetwird [WoMc97; Culb98; RaSu95]. (Diesetheoretische Aussage ist prinzipiell sowohlfur evolutionare Verfahren als auch furVerfahren auf dem Grundsatz der lokalenSuche anwendbar.) Der Herleitung des Re-sultats liegt die Annahme einer uniformenVerteilung von Zielfunktionen zugrunde.Damit sind Regularitaten der Problem-struktur bzw. der Zielfunktion, die beipraktischen Problemen typischerweise vor-handenen sind, nicht abgebildet. Allerdingskann man zeigen, dass die Relevanz des„No Free Lunch“-Theorems im Allgemei-nen auch dann gegeben ist, wenn das Ver-fahren nicht an solche Regularitaten ange-passt ist [WoMc97]. Damit erfordert eineSteigerung der durch ein heuristisches Ver-fahren erzielbaren Losungsgute im All-gemeinen eine Verfahrensanpassung unterVerwendung problemspezifischen Wis-sens. In der Literatur zu heuristischenSuchverfahren ist die Vorteilhaftigkeitproblemspezifischer Anpassungen in viel-faltigen experimentellen Untersuchungenbelegt worden.

Demgemaß ist festzustellen, dass es keinuniverselles Verfahren geben kann, welchesandere Verfahren generell dominiert. Inder Anwendung ist damit jeweils ein situa-tiver Kompromiss zwischen der Verfah-rensgute sowie dem Ausmaß der Verfah-rensanpassung und dem entsprechenden

Implementierungsaufwand einzugehen.Als Schlussfolgerung hinsichtlich einersoftwaretechnischen Unterstutzung derAnwendung von Metaheuristiken ist damitzu konstatieren: Es ist zwar auch einemoglichst einfach verwendbare Standard-funktionalitat bereit zu stellen, andererseitssind aber weitreichende problem- und ver-fahrensspezifische Adapationsmechanis-men zu gewahrleisten. In der praktischenAnwendung verursacht eine solche Adap-tion einen gewissen Aufwand und setzt ei-ne gewisse Verfahrens- und Implementie-rungsexpertise voraus, was entsprechendeGrenzen fur eine einfache praktische An-wendung nach sich ziehen kann.

3 SoftwaretechnischerEntwurf undImplementierung

Im vorausgehenden Abschnitt wurde diebetrachtete Anwendungsdomane aus-schnittsweise beschrieben und hinsichtlichGemeinsamkeiten und Variabilitat ana-lysiert. Auf Basis des entwickelten Mo-dells sowie der Erklarung des Zwangeszur Gewahrleistung weitreichender Adap-tierbarkeit stellt sich nun die Aufgabe derGestaltung eines softwaretechnischen Un-terstutzungspotenzials fur die Entwicklungentsprechender Anwendungssysteme. Auf-grund der Vielfalt betrieblicher Planungs-probleme sowie der im vorausgegangenenAbschnitt 2.3 erorterten Randbedingungenkann das zu schaffende Unterstutzungs-potenzial nicht durch ein Optimierungs-system mit monolithischer Struktur bereit-gestellt werden. Stattdessen zielen wir aufwiederverwendbare (Software-)Kompo-nenten mit wohl definierten Schnittstellenab, die flexibel an spezifische Anforderun-gen angepasst werden konnen. (Wir kon-nen in diesem Rahmen nicht in ausreichen-dem Maße auf softwaretechnische Ansatzeim Wiederverwendungskontext sowie diebreite Diskussion zum Begriff der (Soft-ware-)Komponente eingehen und verwei-sen stattdessen etwa auf [CzEi00; Meye97;Szyp03]. Dies gilt auch fur die Diskussionzur Spezifikation von Fachkomponenten[Turo02].) Das Charakteristikum der Wie-derverwendbarkeit von Komponenten be-zieht sich auf das Vorliegen von Adap-tionsmechanismen hinsichtlich gewisserzum Zeitpunkt der Komponentenentwick-lung nicht abschließend festlegbarer An-forderungen. Dabei kann eine Wiederver-

wendung in der Regel nicht nur aufindividuellen Komponenten basieren, son-dern es muss in einem gewissen Maße aucheine Wiederverwendung von Architektur-elementen stattfinden. Unter Software-architektur versteht man den inneren Auf-bau eines Softwaresystems hinsichtlich derinvolvierten Systemelemente und ihrer Be-ziehungen, einschließlich der hierbei zumEinsatz kommenden Mechanismen sowieder dabei zugrunde gelegten Entwurfsprin-zipien, die durch entsprechende Restriktio-nen (hinsichtlich Funktionalitat, Effizienz,Wiederverwendung, Technologie usw.) be-einflusst sind.

Unser Ziel ist damit die Entwicklung einesAnwendungsframeworks [FaSJ99; Pree97],das fur die hier zugrunde gelegte Anwen-dungsdomane wiederverwendbare Soft-warekomponenten bereitstellt, die in einezweckmaßige Architektur einzubetten sind.Frameworks unterscheiden sich von Klas-senbibliotheken im Zusammenhang mit derVorgabe einer Architektur insbesondere da-durch, dass der Kontrollfluss zwischen an-wendungsspezifischem Code und Frame-workcode in der Regel bidirektional ist.Damit geht die mittels eines Frameworksabbildbare bzw. wiederverwendbare Funk-tionalitat uber die Moglichkeiten einerKlassenbibliothek hinaus. Frameworks sindvon Entwurfsmustern [GHVJ96] insbeson-dere dadurch abzugrenzen, dass ein Frame-work eine (zu vervollstandigende) Imple-mentierung, d. h. Software, ist, wahrend einEntwurfsmuster Wissen uber die Losungbestimmter Problemstellungen darstellt.Die Unvollstandigkeit eines Frameworksbezieht sich im Wesentlichen auf die in derDomanenanalyse identifizierten anwen-dungsspezifischen Variationspunkte (auchals hot spots bezeichnet [Pree97]).

Hinsichtlich der Entwicklung einer trag-fahigen Frameworkarchitektur ist die Mo-dularisierung in uber Schnittstellen wohldefinierte Komponenten als ein grundsatz-liches Mittel zur Bewaltigung von Kom-plexitat zu betrachten, wobei die interneRealisierung von Komponenten gemaßdem Prinzip des Information Hiding ver-borgen sein sollte [Parn72a; Parn72b]. Eineentsprechende Kapselung von Komponen-ten kann im Sinne objektorientierter Ent-wurfsprinzipien mittels Klassen bzw. Ob-jekttypen erfolgen. Das heißt etwa, dassdie in Abschnitt 2.1 identifizierten Abs-traktionen Problemstellung P, Losungs-raum S und Nachbarschaft N durch Ob-jekttypen mit geeigneten Schnittstellenspe-



zifikationen abgebildet werden. KonkreteAuspragungen derartiger Objekttypen er-geben sich durch die problemspezifischeImplementierung bzw. Spezialisierung derim Allgemeinen nur hinsichtlich Ihres ex-ternen Verhaltens beschriebenen Verfah-ren.

Das Kernproblem der hier betrachteten An-wendungsdomane ist das Zusammenwirkenvon metaheuristischen Verfahren mit prob-lemspezifischen Abstraktionen. Allerdingsist die softwaretechnische Wiederverwen-dung von algorithmischen Konzepten unterprimarer Anwendung objektorientierterTechniken problematisch [Weih97]. Dage-gen bietet das so genannte generische Pro-grammierparadigma [MuSt94] einen trag-fahigen Losungsansatz hinsichtlich derCharakteristika des hier vorliegenden Zu-sammenspiels verschiedener Konzeptebzw. der sich hieraus ergebenden Variabili-tatsanforderungen. Das generische Pro-grammierparadigma basiert auf einer Zerle-gung dergestalt, dass abstrakte (generische)Algorithmen (in diesem Fall Metaheuristi-ken) auf typisierten Strukturen (in diesemFall Losungsraum- und Nachbarschafts-strukturen) operieren. Ein generischer Al-gorithmus ergibt sich dabei konkret uberden generischen Code sowie schnittstellen-bezogene Anforderungen an die Typ-parameter (etwa die Existenz einerMethodezur Zielfunktionswertberechnung in einerLosungskomponente), auf denen der gene-rische Algorithmus operiert (vgl. Bild 4).Eine in diesem Sinne generische Software-komponente zeigt damit eine multiple Po-lymorphie hinsichtlich der verwendetenTypparameter.

In Bild 6 ist der auf dem generischen Pro-grammierparadigma basierende Architek-turentwurf beispielhaft als ein UML-Klas-sendiagramm veranschaulicht. Die KlasseIteratedLocalSearch ist entsprechend derin Bild 3 und Bild 4 modellierten Varia-tionspunkte generisch gemaß der vier Typ-parameter S, N, NeighborSelection undDiversification. Hinsichtlich einer koha-renten Darstellung sind diese Typparame-ter durch einen Konfigurationstyp C zu-sammengefasst, der damit die Adaptions-schnittstelle (adaptation interface) derKomponente definiert. Eine konkrete An-passung einer solchen generischen Klasseerfolgt durch eine zweistufige Konfigurati-onshierarchie (vgl. Abschnitt 2.2). In derersten Stufe wird die metaheuristikspezi-fische Konfiguration CH durch eine Bin-dung der entsprechenden metaheuristik-

spezifischen Variationspunkte vorgenom-men, was in diesem Fall zu dem VerfahrenSteepestDescent fuhrt. In der folgendenStufe erfolgt die Spezifikation CP derproblemspezifischen Variationspunkte. Indem Beispiel wird hierzu auf Komponen-ten zuruckgegriffen (VCS_S sowieAS_S_N_Shift), die in Abschnitt 4.2 an ei-nem beispielhaften praktischen Anwen-dungsfall erlautert werden.

Die Implementierung eines solchen Ent-wurfs setzt die Verwendung einer geeig-neten Programmiersprache voraus. Cþþbietet mit dem Template-Konstrukt eineneffektiven Mechanismus, Klassen mit Typ-parametern zu versehen, was eine direkteprogrammiersprachliche Umsetzung des inBild 6 dargestellten Entwurfs ermoglicht;die konkrete Cþþ-Implementierung istausschnittsweise in Bild 7 dargestellt. (Vgl.weiterfuhrend zu den Potenzialen desTemplate-Mechanismus [CzEi00].)

Ein wesentlicher Vorteil des verfolgtenEntwurfs- und Implementierungsansatzesist die naturliche Reprasentation der in derDomanenanalyse identifizierten Varia-tionspunkte in dem Entwurf sowie in derImplementierung, was eine pragnante de-klarative Form der Spezifikation ge-wunschter Anwendungssysteme ermog-licht. Dabei kann man im Wesentlichenvon einer so genannten Blackbox-Wieder-verwendung sprechen, da eine Komposi-tion von Komponenten unter Bezugnahmeauf Schnittstellenspezifikationen erfolgt,ohne dass eine programmiersprachlicheAnpassung von Metaheuristikkomponen-ten erforderlich ware. Der entsprechendeAbstraktionsgrad geht dabei nicht zulastenvon Laufzeiteffizienz, da der Cþþ-Com-piler die Festlegung der Typparameter zur�bersetzungszeit auswertet und damithocheffizienten Code generieren kann. Indem gegebenen Kontext fuhrt damit dieAnwendung des generischen Programmier-paradigmas zu einer generativen Erzeu-


IteratedLocalSearch

C

<<bind>>( C::NeighborSelection = BestPositiveNeighbor,C::Diversification = 0 )

SteepestDescentC

<<bind>>( C::S = VCS_S, C::N = AS_S_N_Shift )

myHeuristic

S, N,NeighborSelection,Diversification

Bild 6 Adaption der generischen Klasse IteratedLocalSearch

template <class C> struct CSteepestDescent{typedef BestPositiveNeighbor<C> NeighborSelection;/* .. */

};

struct Cp{typedef VCS_S S;typedef AS_S_N_Shift N;

};

myHeuristic = new IteratedLocalSearch< CSteepestDescent<Cp> >;

myHeuristic->search( initialSolution );

Bild 7 Umsetzung des Entwurfs aus Bild 6 in Cþþ


gung des Zielsystems, weshalb man hiervon einer kombiniert generativ-komposi-torischen Wiederverwendung sprechenkann (vgl. auch die Beschreibung eines ex-plizit auf das Framework ausgerichtetenGenerators in Abschnitt 4.1). (Selbstredendkann die Frage nach effektiven Methodenzur Generierung maßgeschneiderter Kom-ponenten im Allgemeinen noch keineswegsals hinreichend beantwortet betrachtetwerden [Szyp03; CzEi00].)

Der beschriebene Entwurf bezieht sich aufden Kernaspekt des hier zugrunde geleg-ten Problems, indem die Anwendung vonMetaheuristiken originar vermoge einerWiederverwendung entsprechender Meta-heuristiksoftwarekomponenten unterstutztwird. Andererseits verbleibt im Rahmeneiner praktischen Anwendung noch dieUmsetzung problemspezifischer Struktu-ren (insbesondere durch Losungsraum-und Nachbarschaftskomponenten). DieseAufgabe stellt sich, da wir hier entgegeneinigen anderen Ansatzen (vgl. etwa[Dorn00] sowie die Detailplanungsverfah-ren in SAP APO, die sich primar auf Sche-duling-Problemstellungen in Fertigungs-systemen beziehen) auf eine vollstandigeGenerizitat der Metaheuristiksoftware-komponenten hinsichtlich beliebiger An-wendungsprobleme abzielen. Fur neuartigeProblemstellungen sind gegebenenfalls spe-zifische Losungsraumstrukturen bzw. ent-sprechende Komponenten neu zu ent-wickeln, weshalb deutliche Grenzen fur dieWiederverwendung von problemspezi-fischem Implementierungscode bestehen.Nichtsdestotrotz besitzen vielfaltige prak-tische Problemstellungen gewisse Gemein-samkeiten hinsichtlich zweckmaßiger Lo-sungsraumstrukturen. Damit erscheint esangebracht, solche gemeinsamen Elementezu faktorisieren und mittels klassischer ob-jektorientierter Vererbungshierarchien ab-zubilden, um hiermit optional mittels ob-jektorientierter Spezialisierung eine mog-lichst einfache Anwendbarkeit – im Sinneeines minimalen Implementierungsauf-wands – des Frameworks zu ermoglichen.Auch wenn solche Formen der Implemen-tierungsvererbung als ein problematischerMechanismus zu betrachten sind [BrSi02;Szyp03], haben verschiedene Fallstudiengezeigt, dass eine entsprechende Optionhilfreich sein kann, um mit sehr geringemAufwand Anwendungsprototypen erstel-len zu konnen.

Der diskutierte Losungsansatz wurde alsein Anwendungsframework unter der Be-

zeichnung HotFrame (Heuristic Optimi-zation Framework) in Cþþ umgesetzt.Hinsichtlich einer ausfuhrlichen Darstel-lung der Architektur von HotFrame undausgewahlter Anwendungsfallstudien seiauf [Fink00; FiVo02] verwiesen; weiteredomanenunabhangige Metaheuristikframe-works werden in [VoWo02] beschrieben.HotFrame beinhaltet eine Vielzahl anMetaheuristiken wie insbesondere

& iterative lokale Suchverfahren mit ver-schiedenen Nachbarauswahlregeln undbeliebigen Diversifikationsmechanis-men,

& simulated annealing und Varianten (wieetwa threshold accepting) mit verschie-denen Akzeptanzkriterien, Abkuh-lungsschemata und Wiederaufheizoptio-nen,

& tabu search mit drei prinzipiellen Tabu-isierungskriterien (statisch, strikt, reak-tiv) und beliebigen Diversifikations-mechanismen,

& evolutionare Algorithmen mit verschie-denen Selektions-, Rekombinations-,Mutations- und Generationsentwick-lungsmechanismen,

& sowie erweiterte Konzepte wie etwaKandidatenlisten, variable Nachbar-schaften sowie die Pilotverfahren.

Außerdem werden vordefinierte Losungs-raumkomponenten (und entsprechendeNachbarschaften) fur Problemstellungen,deren Losungen sich zweckmaßig als bina-re Vektoren, Permutationen oder (gegebe-nenfalls geordnete) Zuordnungen von Ob-jekten zu Ressourcen ausdrucken lassen,zur Verfugung gestellt. Mittels solcherproblemspezifischer Standardkomponen-ten lassen sich bereits etwa eine Vielzahlvon kombinierten Reihenfolge- und Zu-ordnungsproblemen im Bereich der Fer-tigungsplanung abbilden.

4 Anwendung

4.1 Inkrementeller Anwendungs-prozess

Ein vollstandiges Ausnutzen der durch dasentwickelte Framework gebotenen Poten-ziale setzt ein gewisses Verstandnis derFrameworkarchitektur voraus, was als einwesentliches Problem des Frameworkkon-zepts im Allgemeinen anzusehen ist[BMMþ99]. Damit erscheint eine Gestal-tung einer inkrementellen und moglichst

einfachen Form der Anwendung des Fra-meworks zweckmaßig (im Sinne einesadoption path), in deren Rahmen eine suk-zessive Anpassung an spezielle Anforde-rungen erfolgen kann. Im Weiteren wirdeine solche inkrementelle Anwendung desFrameworks fur den Fall beschrieben, dassdie Problemstellung eine Verwendung derim Framework enthaltenen problemspezi-fischen Standardkomponenten erlaubt[FiVW99]. Ein idealtypischer Prozess derinkrementellen Anwendung des Frame-works im Kontext lokaler Suchverfahrenkann in vier Schritte untergliedert wer-den:

1. Losungsbewertung: Nach der Auswahleiner geeigneten Losungsraumkom-ponente ist von dieser eine Klasse abzu-leiten, innerhalb derer im Wesentlichenlediglich die Methode zur Berechnungder Zielfunktion zu implementieren ist.Daruber hinaus ist eine entsprechendeProblemklasse zu definieren, uber diekonkrete Probleminstanzen reprasen-tiert werden (gegebenenfalls durch eineSchnittstelle zu entsprechenden Daten-bank- bzw. Anwendungssystemen). Alleweiteren problemspezifischen Kom-ponenten sowie die Metaheuristikkom-ponenten werden unverandert uber-nommen. Nach diesem ersten Schrittsind bereits alle funktionalen Vorausset-zungen fur eine umfassende Anwend-barkeit von Metaheuristiken erfullt (unddamit existiert ein funktionsfahiger Pro-totyp), wahrend die folgenden Schritteauf Effizienz- und Effektivitatssteige-rungen ausgerichtet sind.

2. Effiziente Nachbarschaftsbewertung:In der Regel existiert nach Schritt 1 einbetrachtliches Potenzial fur eine Lauf-zeitbeschleunigung mittels einer effi-zienteren Gestaltung der Nachbar-schaftsbewertung durch eine adaptiveDurchfuhrung der Zielfunktionswert-berechnung bzw. der Bewertung vonZugen (gegebenenfalls losgelost von derimplizierten Zielfunktionswertveran-derung). Der entsprechende Implemen-tierungsaufwand bezieht sich im We-sentlichen auf die Redefinition lediglicheiner Methode.

3. Problemspezifische Anpassung: Ent-sprechend der Diskussion in Abschnitt2.3 profitieren heuristische Verfahrenhaufig von einer Integration problem-spezifischen Wissens (etwa durch dieGestaltung spezieller Nachbarschafts-strukturen). Ein solcher Schritt erfor-dert im Gegensatz zu den Schritten 1



und 2 allerdings haufig eine erweiterteImplementierungsexpertise.

4. Erweiterung von Metaheuristiken:Wahrend in den vorhergehenden Schrit-ten problemspezifische Anpassungen imMittelpunkt stehen, besteht letztendlichauch die Moglichkeit fur eine Anpas-sung bzw. Erweiterung der Metaheuris-tikkomponenten bzw. entsprechenderBausteine.

Dieser inkrementelle Anwendungspfadsetzt voraus, dass die zur Verfugung stehen-den Frameworkkomponenten sowohl ein-fach verwendbare Standardfunktionalitatbeinhalten als auch weitreichende Adap-tionsmechanismen bieten. Hinsichtlich deszuerst genannten Aspektes sind die Meta-heuristikkomponenten von HotFrame so-weit wie moglich autoadaptiv dahingehendgestaltet, dass im Rahmen der Anwendungkeine manuelle Kalibrierung von Verfah-rensparametern erforderlich ist (etwa durchVorgabe einer problemunabhangigen Stan-dardparametrisierung wie in einer speziel-len Auspragung von simulated annealinggemaß [JAMS89] oder reactive tabu searchgemaß [Batt96]).

Trotz des beschrieben inkrementellen An-wendungspfades setzt bereits Schritt 1 einnicht unerhebliches Wissen voraus. So stel-len sich bei einer geplanten Anwendungvon HotFrame zunachst elementare Fra-gen dahingehend, welche Metaheuristik-komponenten uberhaupt existieren, wiediese konfiguriert werden konnen, welcheQuellcodedateien hierzu einbezogen wer-den mussen usw. Um hierbei den Anwen-der soweit wie moglich zu unterstutzen,wurde ein Softwaregenerator prototypischentwickelt, der auf Basis einer deklarativenKonfiguration (noch zu vervollstandigen-den) Anwendungscode generativ erzeugt[Bisk00; FiVo01]. Die Benutzeroberflachedes Generators ist in Bild 8 veranschau-licht. Der Generator basiert auf einerSpezifikation der Frameworkarchitekturhinsichtlich enthaltener Metaheuristikkom-ponenten und ihrer Parameter, problem-spezifischer Komponenten und ihrer Ab-hangigkeiten sowie einer Assoziation vonKomponenten mit Quellcodeschablonenund Ersetzungsregeln bezuglich der spezi-fischen Konfiguration. Der Generator bie-tet dem Benutzer eine intuitive Form derFrameworkadaption uber die Auswahl undKonfiguration der Metaheuristik ein-schließlich der Wahl problemspezifischerStandardkomponenten.

4.2 Fallstudie Containerterminal

HotFrame wurde anhand einer Vielzahlvon Problemstellungen experimentell eva-luiert. Zu den Anwendungen zahlen unteranderem die Sequenzierung von Produk-tionsmustern, Flow-Shop-Problemstellun-gen, Fließbandabstimmungsprobleme, dieMaschinenbelegungsplanung auf identi-schen parallelen Maschinen, Investitions-auswahlprobleme, das Steiner-Problem inGraphen, die Konstruktion von Kom-munikationsnetzwerken in Ringtopologie,das Lastausgleichsproblem in Kommuni-kationsringen, die Ablaufplanung vonKommissionierauftragen in einem Lager-system, die Steuerung der Be- und Ent-ladung von Containerschiffen sowie dieBestimmung von moglichst guten Alloka-tionen im Rahmen von kombinatorischenAuktionen. Vergleiche mit Resultaten ausder Literatur, die in der Regel auf der Ent-wicklung und Anwendung spezialisierterLosungsansatze basieren, belegen ein-drucklich die Konkurrenzfahigkeit des ver-folgten allgemeinen Ansatzes (vgl. etwa[FiVo99; Fink00; FiSV00; FiVo03]). Wirgehen hierauf in diesem Beitrag nicht naherein, sondern beschreiben im Folgenden ei-ne praktische Anwendungsfallstudie, uman diesem Beispiel die Potenziale undGrenzen einer softwaretechnischen Unter-

stutzung fur die Anwendung von Meta-heuristiken zur Losung betrieblicher Pla-nungsprobleme zu verdeutlichen.

Zur Veranschaulichung der Anwendungvon HotFrame fur eine praktische Pro-blemstellung beziehen wir uns auf Ablaufeauf einem Containerterminal (in diesemFall im Hamburger Hafen, vgl. [BRSV00]).Das Layout eines Ausschnitts einer solchenAnlage ist in Bild 9 dargestellt. Auf demTerminal werden Container zwischenContainerschiffen und dem Lagerbereich(bzw. letztendlich Lkws und Guterbahnen)umgeschlagen. Am Schiff kommen hierbeihorizontal zur Kaimauer bewegliche Ver-ladebrucken zum Einsatz, die den Trans-port aus dem Schiff auf einen Pufferlager-platz unter der Verladebrucke undumgekehrt bewerkstelligen. Der Transportvon Containern zwischen solchen Puffer-lagerplatzen an den Verladebrucken undContainerstellplatzen in dem Lagerbereicherfolgt etwa mittels so genannter Portal-hubfahrzeuge (auch bezeichnet als van car-rier oder straddle carrier). Die wesentlicheAufgabenstellung besteht in der Disposi-tion des wasserseitigen Umschlagprozesseszwischen Schiff und Lagerbereich. Hierbeisind uber zweckmaßige Steuerungsstrate-gien Transportauftrage an die Portalhub-fahrzeuge geordnet zuzuordnen.


Bild 8 Generator


Die Losung dieser Planungsaufgabe mittelsMetaheuristiken setzt zunachst eine Mo-dellbildung voraus, die uber einen Abs-traktionsprozess den Kern des Disposi-tionsproblems herausbildet. Hinsichtlicheiner Anwendung lokaler Suchverfahrenbedeutet dies im Wesentlichen die Fest-legung der Menge der zu betrachtendenHandlungsalternativen durch einen Lo-sungsraum einschließlich einer konkretenZielfunktion. Grundsatzliches Ziel ist indiesem Fall die Minimierung der durch dieDauer der Be- und Entladung bestimmtenSchiffsliegezeiten durch eine zulassige Zu-ordnung der Be- und Entladeauftrage andie Portalhubfahrzeuge. Dieses Entschei-dungsproblem kann folgendermaßen aufdie in Abschnitt 2.1 entwickelten Modell-elemente abgebildet werden:

& Die Daten einer Probleminstanz ergebensich als die Menge der das betrachteteSchiff betreffenden Be- und Entladeauf-trage mit jeweiligen Start- und Ziel-punkten.

& Der Losungsraum ist bestimmt durchdie geordnete Zuordnung aller Trans-portauftrage an Portalhubfahrzeuge.Unter Annahme deterministischer Ab-laufe kann auf dieser Basis die Dauer derSchiffsabfertigung und damit der Ziel-funktionswert berechnet werden.

& Eine einfache Nachbarschaftsstrukturergibt sich durch eine Definition vonZugen im Sinne einer beliebigen Veran-

derung der Zuordnung eines Transport-auftrages.

Die Anwendung von HotFrame ist aufdieser Grundlage relativ einfach, da eineallgemeine Losungsraumstruktur als Stan-dardkomponente zur Verfugung steht, diedie geordnete Zuordnung von Objekten zuRessourcen abbildet (AS_S als Abkurzungfur assignment & sequencing solution). Wei-terhin ist eine entsprechende Nachbar-schaftsstruktur als Standardkomponentevordefiniert (AS_S_N_Shift als Abkurzungfur assignment & sequencing solutionneighborhood shift); vgl. Bild 6 und Bild 7.Als Implementierungsaufgaben verbleibendie Ableitung einer speziellen Losungs-raumklasse (VCS_S als Abkurzung fur vancarrier scheduling solution) und die Defini-tion der virtuellen Methode zur Zielfunk-tionswertberechnung. Das heißt, nach derImplementierung weniger Codezeilen sindalle prinzipiellen Voraussetzungen zur An-wendung vielfaltiger Metaheuristiken er-fullt. Hiermit konnten fur reale Anwen-dungsprobleme Produktivitatssteigerungenvon bis zu 9% erzielt werden (im Ver-gleich zu den bislang eingesetzten Priori-tatsregelverfahren). Dieses Anwendungs-beispiel verdeutlicht das grundsatzlichePotenzial fur eine softwaretechnische Un-terstutzung der Anwendung von Metaheu-ristiken zur Losung betrieblicher Pla-nungsprobleme. Die wesentlichen Grenzeneiner solchen Unterstutzung ergeben sich

dann, wenn bei komplexeren Problemstel-lungen gegebenenfalls die Definition undUmsetzung spezieller Losungsraum- undNachbarschaftsstrukturen erforderlich ist,was notwendigerweise einen gewissen Auf-wand zur Implementierung problemspezi-fischer Komponenten nach sich zieht. Ausdiesem Grund erscheint das Idealbild einerautomatisierten Anwendbarkeit von Meta-heuristiken auf vollkommen neue Prob-lemstellungen nicht generell einlosbar –There is no free lunch.

An dem Beispiel des Containerterminalslasst sich ein verkomplizierendes Merkmalmancher betrieblicher Planungs- undSteuerungsprobleme verdeutlichen. In derPraxis mussen haufig auf der Grundlagenur partiell vorliegender Informationenbzw. einer sich kontinuierlich verandern-den Datenlage Entscheidungen getroffenwerden (gegebenenfalls unter Echtzeitan-forderungen). Eine solche Onlinecharakte-ristik liegt in der Regel auch bei der Steue-rung der Portalhubfahrzeuge vor, da ausverschiedenen betrieblichen Grunden Ent-ladesequenzen jeweils nur mit einem einge-schrankten Vorausschaubereich bekanntsind und gegebenenfalls �nderungen un-terworfen sind. Analoge Situationen sindin der Praxis allgegenwartig – beispielswei-se bei der Ressourceneinsatzsteuerung imRahmen der Fertigungsplanung (etwa auf-grund von Machinenausfallen) oder bei derDisposition von Fordergeraten in einemHochregallagersystem (etwa aufgrund neuerdringlicher Kommissionierauftrage). Derfur eine bestimmte Datengrundlage er-zeugte Plan kann jeweils eventuell nur un-vollstandig umgesetzt werden. Stattdessenergibt sich dann ein rollierender Planungs-ablauf. Es stellt sich die Frage, wie sich einesolche Onlinecharakteristik (gegebenenfallsverbunden mit Echtzeitanforderungen) aufdie Anwendung von Metaheuristiken bzw.die entsprechende softwaretechnische Um-setzung auswirkt. Im Rahmen von Hot-Frame kommt in diesem Zusammenhangdas externe Abbruchkriterium zum Tragen(vgl. Abschnitt 2.2). Die Implementierungmetaheuristischer Verfahren beinhaltet je-weils eine �berprufung dieses Abbruch-kriteriums durch einen externen Metho-denaufruf nach jeder Iteration (in Cþþtechnisch umgesetzt durch ein frei kon-figurierbares Funktionsobjekt). In diesemZusammenhang werden auch jeweils dieaktuelle sowie die beste bisher ermittelteLosung extern zur Verfugung gestellt. Diesermoglicht einerseits die Suche nach ver-besserten Losungen bis zu dem Zeitpunkt,



an dem eine Entscheidung tatsachlich an-steht (das heißt, sobald etwa ein Portalhub-fahrzeug einen Transportauftrag abge-schlossen hat und damit wieder fur einenFolgeauftrag zur Verfugung steht). Ande-rerseits kann der Suchprozess bei einer ver-anderten Datenlage gestoppt und nachAnpassung der Datenstrukturen fort-gesetzt werden. Eine Anwendung entspre-chender Konzepte bei der Disposition vonFordergeraten in einem Hochregallager-system ist beispielsweise in [Gute02] doku-mentiert.

5 Fazit

In dem Beitrag wurden die Potenziale undGrenzen einer softwaretechnischen Unter-stutzung fur die Anwendung von Meta-heuristiken zur Losung betrieblicher Pla-nungsprobleme aufgezeigt. Die bisher imVergleich zur uberaus umfangreichen For-schungsliteratur nur sehr vereinzelte An-wendung moderner heuristischer Verfah-ren in der betrieblichen Praxis verdeutlichtdie Relevanz des betrachteten Unter-suchungsgegenstands. Ein entsprechenderTechnologietransfer setzt die integrativeErweiterung und Anwendung von Er-kenntnissen und Techniken aus dem Op-erations Research und der Softwaretechnikvoraus. Dieser Aufgabe hat sich insbeson-dere die Wirtschaftsinformatik zu stellen,um zu einer pragmatischen Umsetzungquantitativer Verfahren im Rahmen einerpraktischen Entwicklung von Planungssys-temen beizutragen. In dem Beitrag wurdeunter Bezug auf das generische Program-mierparadigma eine Frameworkarchitekturbeschrieben, die eine kombiniert generativ-kompositorische Wiederverwendung vonMetaheuristikkomponenten fur die Ent-wicklung spezifischer Planungssysteme er-moglicht. Entsprechende Komponentenbilden einen „Werkzeugkasten“, der denState-of-the-Art in der umfangreichen For-schung zu Metaheuristiken abbilden soll.Der Losungsansatz zeichnet sich dadurchaus, dass eine klare Trennung zwischenmetaheuristischen Verfahrenskonzeptenund problemspezifischen Abstraktionenerreicht wurde, weshalb das Frameworkfur beliebige Planungsprobleme, die prin-zipiell metaheuristischen Verfahren zu-ganglich sind, eingesetzt werden kann.Gleichwohl konnte uber experimentelleUntersuchungen und praktische Anwen-dungsfallstudien die Effektivitat des An-

satzes im Vergleich zu spezialisierten Ver-fahren belegt werden.

Die in diesem Beitrag betrachtete Anwen-dungsdomane ist durch Losungsverfahrencharakterisiert, die in einem relativ hohenMaße problemspezifisch sind. Eine Soft-warewiederverwendung setzt damit weit-reichende strukturelle Adaptionsmechanis-men voraus; außerdem sind grundsatzlicheLaufzeiteffizienzanforderungen zu beruck-sichtigen. Diese Zwange fuhrten zu einemLosungsansatz, der auf einer generativenErzeugung maßgeschneiderter Komponen-ten mittels einer parametrischen Adaptionzur �bersetzungszeit basiert (mit demhiermit verbundenen Erfordernis einer ge-wissen programmiersprachlichen Exper-tise). Eine schlichte Verwendung direktausfuhrbarer („binarer“) Softwarekom-ponenten [Szyp03], die in der Regel nur ei-ne relativ einfache dynamische Parametri-sierung und Komposition erlauben,erscheint aufgrund der beschriebenen An-forderungen hingegen nicht moglich.

Als Ausblick sei auf eine Tendenz im Zu-sammenhang mit der Entwicklung undUntersuchung betrieblicher Planungs- undSteuerungssysteme hingewiesen, die erwei-terte Anforderungen an eine softwaretech-nische Unterstutzung der Anwendung me-

taheuristischer Verfahren mit sich bringt.Zur Abbildung der Komplexitat betrachte-ter Systeme werden in Kombination mitOptimierungsverfahren immer haufiger Si-mulationsmodelle eingesetzt, die verschie-denen Zwecken dienen konnen:

& Einerseits konnen mittels SimulationPlane experimentell bewertet werden,was insbesondere dann zweckmaßig ist,wenn aufgrund von signifikanten sto-chastischen Einflussen dies allein mittelsanalytischer Methoden nicht moglichist. Herkommlicherweise erfolgt eineExperimentsteuerung durch einenmenschlichen Planer. Von diesem veran-dert festgelegte Systemkonfigurationenwerden jeweils simulativ bewertet. Al-lerdings kann die Experimentsteuerungauch als ein heuristischer Suchprozessaufgefasst und damit gegebenenfallsdurch die Anwendung von Metaheuris-tiken automatisiert werden (im Sinne ei-ner der Simulation ubergeordneten Op-timierung). Das heißt, Metaheuristikenkonnen zur systematischen Variation si-mulativ zu bewertender Systemkonfigu-rationen genutzt werden. Fur den be-trachteten Anwendungsfall konnte diesbeispielsweise die Bruckenpositionie-rung oder die Anzahl einzusetzenderPortalhubfahrzeuge betreffen.


Simulationssystem bzw. -modell

Solver in der Funktion„untergeordnete Optimierung“

Solver in der Funktion „übergeordnete Optimierung“

Zielfunktion,ggf. multi-kriteriell

Echtzeitcharakteristik

Optimierungsmethode

Optimie-rungsme-thode

Lösungsraum /Nachbarschaft

Kopplungsschnittstelle

Kopplungsschnittstelle

Lösungsraum /Nachbarschaft

Zielfunktion

Bild 10 Schematische Darstellung des Zusammenspiels zwischen Optimierung undSimulation


& Andererseits sind Elemente der Steue-rungslogik des Systems und damit desSimulationsmodells selbst gezielt zu ge-stalten und profitieren damit von derLosung entsprechender Teilproblemedurch die Anwendung von Metaheuris-tiken (im Sinn einer untergeordnetenOptimierung). Das oben diskutierte An-wendungsbeispiel der Onlinesteuerungder Portalhubfahrzeuge entspricht die-ser Rolle.

Eine angemessene Unterstutzung dieserbeiden Aufgaben ließe sich vor allem durcheine weitgehende Automatisierung einesZusammenspiels von Optimierung und Si-mulation erreichen. Dies bedingt auf soft-waretechnischer Ebene eine tragfahige undflexible Kopplung von Optimierungs- undSimulationskomponenten entsprechendder in Bild 10 schematisch skizzierten In-teraktion. In diesem Aufgabenbereich of-fenbart sich ein erheblicher Forschungs-und Entwicklungsbedarf, um mittelfristigstandardisierte softwaretechnische Archi-tekturen und Komponenten zu schaffen,die die effektive und effiziente Kopplungvon Optimierung und Simulation im prak-tischen Einsatz unterstutzen und hierbeieinerseits effektive Verfahren beinhaltensowie andererseits die in einem praktischenEinsatz unverzichtbare Einfachheit der an-wendungsfallbezogenen Adaption gewahr-leisten.

Literatur

[AaLe97] Aarts, E. H. L.; Lenstra, J. K. (Hrsg.):Local Search in Combinatorial Optimization.Wiley, Chichester 1997.

[ACGþ99]Ausiello, G.; Crescenzi, P.; Gambosi, G.;Kann, V.; Marchetti-Spaccamela, A., Protasi, M.:Complexity and Approximation: CombinatorialOptimization Problems and Their Approxim-ability Properties. Springer, Berlin Heidelberg1999.

[Batt96] Battiti, R.: Reactive search: Toward self-tuning heuristics. In: Rayward-Smith, V. J.; Os-man, I. H.; Reeves, C. R.; Smith, G. D. (Hrsg.):Modern Heuristic Search Methods. Wiley, Chi-chester 1996, S. 61–83.

[Bisk00] Biskup, U.: Entwicklung einer Konfigura-tionsanwendung basierend auf den Anforderun-gen von HotFrame: Grafische Benutzeroberfla-che, Software-Generator, Konfigurationsspra-che. Diplomarbeit, Technische UniversitatBraunschweig 2000.

[BMMþ99] Bosch, J.; Molin, P.; Mattsson, M.;Bengtsson, P.; Fayad, M. E.: Framework prob-lems and experiences. In: Fayad, M. E.; Schmidt,D. C.; Johnson, R. E. (Hrsg.): Building Applica-tion Frameworks: Object-Oriented Foundationsof Framework Design. Wiley, Chichester 1999,S. 55–82.

[BRSV00] Bose, J.; Reiners, T.; Steenken, D.; Voß, S.:Vehicle dispatching at seaport container terminalsusing evolutionary algorithms. In: Sprague, R. H.(Hrsg.): Proceedings of the 33rd Annual HawaiiInternational Conference on System Sciences,IEEE, Piscataway (2000), DTM-IT, S. 1–10.

[BrSi02] Broy, M.; Siedersleben, J.: Objektorien-tierte Programmierung und Softwareentwick-lung: Eine kritische Einschatzung. In: Informa-tik-Spektrum 25 (2002), S. 3–11.

[Carn02] Carnegie Mellon Software EngineeringInstitute: Domain Engineering.http://www.sei.cmu.edu/domain-engineering/domain_eng.html. Abruf am 2002-12-02.

[Culb98] Culberson, J. C.: On the futility of blindsearch: An algorithmic view of “no free lunch”.In: Evolutionary Computation 6 (1998),S. 109–127.

[CzEi00] Czarnecki, K.; Eisenecker, U. W.: Gen-erative Programming: Methods, Tools, and Ap-plications. Addison-Wesley, Reading 2000.

[Dorn00] Dorn, J.: Planung von betrieblichen Ab-laufen durch Standardsoftware – eine Wider-spruch? In: Wirtschaftsinformatik 42 (2000), S.201–209.

[FaSJ99] Fayad, M. E.; Schmidt, D. C.; Johnson, R. E.(Hrsg.): Building Application Frameworks: Ob-ject-Oriented Foundations of Framework Design.Wiley, Chichester 1999.

[Fich94] Fichefet, J.: From operational research to-wards decision science aid: A quest for the philo-sophers’ stone? In: Cahiers du CERO 36 (1994),S. 113–142.

[Fink00] Fink, A.: Software-Wiederverwendungbei der Losung von Planungsproblemen mittelsMeta-Heuristiken. Shaker, Aachen 2000.

[FiSV00] Fink, A; Schneidereit, G.; Voß, S.: Solvinggeneral ring network design problems by meta-heuristics. In: Laguna, M.; Gonzalez Velarde,J. L. (Hrsg.): Computing Tools for Modeling,Optimization and Simulation (Interfaces inComputer Science and Operations Research),Kluwer, Boston 2000, S. 91–113.

[FiVW99] Fink, A.; Voß, S.; Woodruff, D. L.: Anadoption path for intelligent heuristic searchcomponentware. In: Rolland, E.; Umanath, N. S.(Hrsg.): Proceedings of the 4th INFORMS Con-ference on Information Systems and Technology.INFORMS, Linthicum 1999, S. 153–168.

[FiVo99] Fink, A.; Voß, S.: Applications of modernheuristic search methods to pattern sequencingproblems. Computers & Operations Research26 (1999), S. 17–34.

[FiVo01] Fink, A.; Voß, S.: Reusable metaheuristicsoftware components and their application viasoftware generators. In: De Sousa, J. P. (Hrsg.):Proceedings of the 4th Metaheuristics Interna-tional Conference, Porto 2001, S. 637–642.

[FiVo02] Fink, A.; Voß, S.: HotFrame: A heuristicoptimization framework. In: Voß, S.; Woodruff,D. L. (Hrsg.): Optimization Software Class Li-braries. Kluwer, Boston 2002, S. 81–154.

[FiVo03] Fink, A.; Voß, S.: Solving the continuousflow-shop scheduling problem by metaheuris-tics. European Journal of Operational Research.Im Druck (2003).

[GHJV96] Gamma, E.; Helm, R.; Johnson, R.;Vlissides, J.: Entwurfsmuster: Elemente wieder-verwendbarer objektorientierter Software. Ad-dison-Wesley, Bonn 1996.

[GaJo79] Garey, M. R.; Johnson, D. S.: Compu-ters and Intractability: A Guide to the Theory

of NP-Completeness. Freeman, New York1979.

[GlLa97] Glover, F.; Laguna, M.: Tabu Search.Kluwer, Boston 1997.

[Gute02] Gutenschwager, K.: Online-Dispositions-probleme in der Lagerlogistik: Modellierung –Losungsansatze – praktische Umsetzung. Physi-ca, Heidelberg 2002.

[JAMS89] Johnson, D. S.; Aragon, C. R.; McGeoch,L. A.; Schevon, C.: Optimization by simulatedannealing: An experimental evaluation; part i,graph partitioning. Operations Research 37(1989), S. 865–892.

[KCHþ90] Kang, K.; Cohen, S.; Hess, J.; Novak,W.; Peterson, S.: Feature-oriented domain analy-sis (FODA) feasibility study. ArbeitsberichtCMU/SEI-90-TR-21, Carnegie Mellon SoftwareEngineering Institute, Carnegie Mellon Univer-sity 1990.

[Mert98] Mertens, P.: Geschichte und ausgewahlteGegenwartsprobleme der Wirtschaftsinformatik.In: Wirtschaftswissenschaftliches Studium (WiSt)27 (1998), S. 170–175.

[Meye97] Meyer, B.: Object-Oriented SoftwareConstruction. 2. Aufl., Prentice Hall, Engle-wood-Cliffs 1997.

[MiFo00] Michalewicz, Z.; Fogel, D. B.: How toSolve It: Modern Heuristics. Springer, BerlinHeidelberg 2000.

[MuSt94] Musser, D. R.; Stepanov, A. A.: Algo-rithm-oriented generic libraries. Software –Practice and Experience 24 (1994), S. 623–642.

[Niev94] Nievergelt, J.: Complexity, algorithms,programs, systems: The shifting focus. In: Jour-nal of Symbolic Computation 17 (1994), S. 297–310.

[Parn72a] Parnas, D. L.: A technique for softwaremodule specification with examples. In: Com-munications of the ACM 15 (1972), S. 330–336.

[Parn72b] Parnas, D. L.: On the criteria to be usedin decomposing systems into modules. In: Com-munications of the ACM 15 (1972), S. 1053–1058.

[Pree97] Pree, W.: Komponentenbasierte Software-entwicklung mit Frameworks. dbpunkt, Heidel-berg 1997.

[RaSu95] Radcliffe, N. J.; Surry, P. D.: Fundamentallimitations on search algorithms: Evolutionarycomputing in perspective. In: Van Leeuwen, J.(Hrsg.): Computer Science Today: Recent Trendsand Developments, Lecture Notes in ComputerScience 1000. Springer, Berlin Heidelberg 1995,S. 275–291.

[Simo97] Simon, H. A.: The future of informationsystems. In: Ramesh, R.; Rao, H. R. (Hrsg.): In-terface between Information Systems and Op-erations Research, Part I – Models of Systems.Annals of Operations Research 71, Baltzer, Am-sterdam 1997, S. 3–14.

[SCKþ96] Simos, M.; Creps, D.; Klinger, C.; Le-vine, L.; Allemang, D.: Organization domainmodeling (ODM) guidebook, version 2.0. Soft-ware Technology for Adaptable, Reliable Sys-tems (STARS), Arbeitsbericht STARS-VC-A025/001/00, 1996.

[Szyp03] Szyperski, C. (mit Gruntz, D.; Murer, S.):Component Software: Beyond Object-OrientedProgramming. 2. Aufl., Addison-Wesley, Read-ing 2003.

[Turo02] Turowksi, K. (Hrsg.): VereinheitlichteSpezifikation von Fachkomponenten. Memoran-dum des Arbeitskreises 5.10.3 (Komponenten-



orientierte betriebliche Anwendungssysteme)der Gesellschaft fur Informatik, Februar 2002.

[VaAL98] Vaessens, R. J. M.; Aarts, E. H. L.; Len-stra, J. K.: A local search template. Computers &Operations Research 25 (1998), S. 969–979.

[Voss01] Voß, S.: Meta-heuristics: The state of theart. In: Nareyek, A. (Hrsg.): Local Search forPlanning and Scheduling, Lecture Notes in Arti-ficial Intelligence 2148. Springer, Berlin Heidel-berg 2001, S. 1–23.

[VoWo02] Voß, S.; Woodruff, D. L. (Hrsg.): Opti-mization Software Class Libraries. Kluwer, Bos-ton 2002.

[Weih97] Weihe, K.: Reuse of algorithms: Still achallenge to object-oriented programming. In:ACM SIGPLAN Notices 32 (1997) 10, S. 34–48.

[WeLa99] Weiss, D. J.; Lai, C. T. R.: Software Pro-duct-Line Engineering: A Family-Based Soft-ware Development Process. Addison-Wesley,Reading 1999.

[WoMc97] Wolpert, D. H.; Macready, W. G.: Nofree lunch theorems for optimization. IEEETransactions on Evolutionary Computation 1(1997), S. 67–82.



Date post:	25-Aug-2016
Category:	Documents
Upload:	stefan
View:	214 times
Download:	1 times

Anwendung von Metaheuristiken zur Lösung betrieblicher Planungsprobleme : Potenziale und Grenzen...

Documents