Ablaufplanungsheuristiken für parallele Maschinen mit reihenfolgeabhängigen Umrüstzeiten

Inhaltsverzeichnis

1 Einleitung 1

2 Ablaufplanungsprobleme für parallele Maschinen mit reihenfolgeabhängigen Um-

r üstzeiten 3

2.1 Motivation 3

2.2 Problembeschreibung 4

2.2.1 Problembeschreibung anhand eines Beispiels 4

2.2.2 Formale Beschreibung des Problems 7

2.3 Diskussion von Vorarbeiten 11

3 Konzept zur Lösung des Problems 15

3.1 Prioritätsbasierte Heuristiken 15

3.2 Anwendung der ATCS-Regel auf das P m s ij Σw j T j -Problem 18

3.3 ACO-Metaheuristik 19

3.3.1 Futtersuche von Ameisen 20

3.3.2 AS 21

3.3.3 ACS 23

3.3.4 AS Rank 25

3.3.5 MMAS 25

3.3.6 ACO 26

3.4 Anwendung der ACO-Metaheuristik auf das P m s ij Σw j T j -Problem 28

3.4.1 Anwendung der ACO-Metaheuristik auf Ablaufplanungspro-

bleme 28

3.4.2 Konstruktion des Graphen für die ACO-Metaheuristik 30

6 Inhaltsverzeichnis

3.4.3 Anwendung der ACO-Metaheuristik auf das P m s ij Σw j T j -

Problem 38

4 Implementierung 45

4.1 Repräsentation von Probleminstanz und Problemlösung 45

4.2 Implementierung der ATCS-Regel 47

4.3 Implementierung der ACO-Metaheuristik 49

5 Leistungsbewertung 51

5.1 Vergleich der Kostenfunktionen für die ATCS-Heuristik 52

5.2 Leistungsbewertung der ACO-Heuristik 53

5.2.1 Testreihe 1: S M axM in f alse, S P os f alse 53

5.2.2 Testreihe 2: S M axM in true, S P os f alse 59

5.2.3 Testreihe 3: S M axM in f alse, S P os true 62

5.2.4 Testreihe 4: Benchmarktest 65

6 Zusammenfassung 69

Literaturverzeichnis 71

B Dateiformate der Testdaten 83

B.1 ATCS - Vergleich der Kostenfunktionen 83

B.2 ACO - Parametertest 84

C Benchmarktest - Verbesserungen 85

1 Einleitung

Diese Arbeit beschäftigt sich mit dem Problem der Verteilung und Festlegung der Reihenfolge von Jobs mit reihenfolgeabhängigen Umrüstzeiten auf parallele, identische Maschinen. Als Leistungsmaß soll die totale gewichtete Verspätung minimiert werden. Das Ziel dieser Arbeit besteht darin, für dieses Ablaufplanungsproblem ein Verfahren auf Basis der Ant-Colony-Optimazation(ACO)-Metaheuristik zu entwickeln. Die ACO-Metaheuristik ist in [Dor99] beschrieben. Ein Verfahren auf Basis der ACO-Metaheuristik für das analoge Einzelmaschinenproblem ist in [Lia07] vorgestellt worden. Das dort vorgestellte Verfahren dient als Ausgangspunkt der vorliegenden Arbeit.

In Kapitel 2 wird zunächst das Problem erläutert. Es werden Beispiele genannt und das Problem formal beschrieben. Weiterhin erfolgt eine Vorstellung von Arbeiten, in denen sich mit der Anwendung der ACO-Metaheuristik auf Ablaufplanungsprobleme bereits beschäftigt wurde.

In Kapitel 3 wird das Konzept zur Anwendung der ACO-Metaheuristik auf das Problem erarbeitet. Zunächst wird die Apparent-Tardiness-Cost-with-Setups(ATCS)-Heuristik als prioritätsbasierte Heuristik vorgestellt. Die ATCS-Heuristik soll als Referenzheuristik dienen. Anschließend wird die ACO-Metaheuristik beschrieben und das Konzept für die Anwendung der ACO-Metaheuristik auf das gegebene Ablaufplanungsproblem vorgestellt.

Nachdem in Kapitel 4 auf die Implementierung des Verfahrens eingegangen wurde, erfolgt in Kapitel 5 eine Leistungsbewertung des Verfahrens.

2 Ablaufplanungsprobleme für parallele

Maschinen mit reihenfolgeabhängigen

Umrüstzeiten

2.1 Motivation

Reihenfolgeabhängige Umrüstzeiten ﬁndet man in der Produktionsdomäne überall dort, wo die notwendige Rüstzeit bzw. Umrüstzeit für die Bearbeitung eines Jobs auf einer Maschine von dem Zustand abhängt, in welchen der zuvor verplante Job die Maschine hinterlassen hat. In [Mön09] ﬁndet man das Beispiel einer Lackiererei für Autokarosserien. Hier wird die Umrüstzeit von der verwendeten Farbe des zu verplanenden und des zuletzt verplanten Jobs bestimmt. Beim Übergang von schwarzer zu weißer Farbe sind umfangreichere Reinigungsarbeiten notwendig. Dadurch entstehen beim Übergang von schwarz zu weiß höhere Umrüstzeiten als beim Übergang von weiß zu schwarz.

Ein weiteres Beispiel wird in [Gra02] beschrieben. Hier wird der Aufbau einer Aluminiumgießerei in Quebec vorgestellt. Schematisch besteht die Gießerei aus zwei Hochöfen für die Schmelze, einem Walzwerk zum Formen von Blechen bestimmter Breite und Dicke und einer Säge zum Zurechtschneiden der Bleche auf die geforderte Länge. Jeder Auftrag enthält Angaben über die gewünschte Legierung, die gewünschte Form der Bleche und die Bestellmenge. Unterscheiden sich die gewünschten Formen der Bleche des zuletzt bearbeiteten und des folgenden Auftrages, ist möglicherweise der Austausch von Walzen des Walzwerkes notwendig. Dadurch können die erforder-

2 Ablaufplanungsprobleme für parallele Maschinen mit reihenfolgeabhängigen

4

Umrüstzeiten

lichen Umrüstzeiten variieren. Große Unterschiede bei den Umrüstzeiten entstehen durch die Reihenfolge der gewünschten Legierungen. In Abhängigkeit der verwendeten Legierung des letzten Jobs muss dem Hochofen lediglich eine bestimmte Menge Erz neu hinzugefügt werden oder die Legierung für den folgenden Job macht die Entleerung und Reinigung der Hochöfen notwendig, wodurch sehr hohe Umrüstzeiten entstehen.

Die in [Gra02] beschriebene Aluminiumgießerei ist auch ein Beispiel für die Verwendung der totalen gewichteten Verspätung als Leistungsmaß bei der Bewertung eines Ablaufplanes. Jedem Auftrag der Gießerei ist ein gewünschter Fertigstellungstermin zugeordnet. Die Kapazität des Werkes ist natürlich begrenzt. Bei hohem Auftragsvolumen sind Verspätungen bei der Fertigstellung der Aufträge nicht zu vermeiden. In diesem Fall ist es sinnvoll, die Aufträge zu priorisieren (etwa nach Wichtigkeit des Kunden) und zu versuchen, die Summe der gewichteten Verspätungen der einzelnen Aufträge zu minimieren.

2.2 Problembeschreibung

2.2.1 Problembeschreibung anhand eines Beispiels

In diesem Abschnitt soll das Ablaufplanungsproblem aus der Aufgabenstellung an-hand eines ﬁktiven Beispiels aus der Logistikdomäne illustriert werden, bevor es dann im nächsten Abschnitt formal beschrieben wird.

Das Beispiel lautet wie folgt:

Ein Logistikunternehmen führt europaweit Transporte durch. Alle Aufträge sind Termingeschäfte. Wird ein Liefertermin überschritten, ist eine Vertragstrafe fällig. Die Höhe der Strafe ist abhängig von der Verspätung multipliziert mit einem Faktor, der pro Auftrag variieren kann. Tabelle

2.2 Problembeschreibung 5

2.1 zeigt die momentane Auftragsliste. Das Unternehmen verfügt über zwei Fahrzeuge. Für beide Fahrzeuge wird eine Durchschnittsgeschwindigkeit von 60 km/h im beladenen und 90 km/h im unbeladenen Zustand angesetzt. Beide Fahrzeuge beﬁnden sich momentan in Berlin.

Die Aufgabe besteht darin, einen Tourenplan für beide Fahrzeuge zu erstellen, bei dem die Summe der zu zahlenden Vertragsstrafen minimal ist.

Bei der folgenden Analyse des Problems werden analoge Begriﬀe der Produktionsdomäne benutzt, um den Bezug des Beispiels zur Aufgabenstellung zu verdeutlichen. Laut Beispiel sind sieben Aufträge gegeben, im Folgenden Jobs genannt. Jeder Job j verfügt über eine Bearbeitungszeit p j . Das ist die Zeit (in Stunden), die für den Transport vom Start zum Ziel des Auftrages benötigt wird. Weiterhin ist jedem Job j eine gewünschte Fertigstellungszeit d j zugeordnet, die dem Liefertermin entspricht. Der im Beispiel genannte auftragsabhängige Faktor wird im Folgenden Gewicht w j des Jobs j genannt. Um nach einem Job i einen Job j durchzuführen, ist eine Leerfahrt vom Zielpunkt des letzten zum Startpunkt des folgenden Jobs notwendig. Die dafür benötigte Zeit s ij wird im Folgenden als Umrüstzeit bezeichnet. s 0j ist die Anfahrtszeit bzw. Anfangsrüstzeit, die benötigt wird, um von Berlin zum Startpunkt des Jobs j zu gelangen. Es ergibt sich die in Tabelle 2.2 gezeigte Proble- minstanz. Die angegebenen Bearbeitungszeiten und Umrüstzeiten wurden mit Hilfe

2 Ablaufplanungsprobleme für parallele Maschinen mit reihenfolgeabhängigen

6

Umrüstzeiten

eines Routenplaners ermittelt.

Tabelle 2.2: Beispiel Probleminstanz

Die Jobs sollen nun auf zwei identische Maschinen (die zur Verfügung stehenden Fahrzeuge) verplant werden. Bei einem Ablaufplan Q ergibt sich für jeden Job j ein Fertigstellungstermin C Q j . Daraus ergibt sich für den Job j die gewichtete Verspätung w j ∗max(0, C Q j −d j ) und damit die totale gewichtet Verspätung des gegebenen Ablaufplanes als Summe der gewichteten Verspätungen aller Jobs. Laut Aufgabe aus dem Beispiel soll nun der Ablaufplan Q opt mit der geringsten totalen gewichteten Verspätung gefunden werden.

Es existieren genau 20160 Möglichkeiten, um sieben Jobs auf zwei Maschinen zu verteilen ¹ . Bei dieser Größenordnung lässt sich der optimale Ablaufplan noch durch Berechnen aller möglichen Ablaufpläne ﬁnden. Das Gantt-Diagramm in Abbildung 2.1 zeigt die optimale Verplanung der Jobs und damit (um wieder zur ursprünglichen Aufgabe zurückzukommen) die optimale Tourenplanung für die beiden zur

1 Ein Ablaufplan mit zwei identischen Maschinen lässt sich durch Hintereinanderschreiben der Jobsequenzen beider Maschinen getrennt durch ein Trennsymbol darstellen. Das heißt, jede Permutation der n Jobs und dem Trennsymbol entspricht einem Ablaufplan. Dabei ist jeder Ablaufplan doppelt aufgeführt, da die Reihenfolge der Maschinen keine Rolle spielt. Die Anzahl unterschiedlicher Ablaufpläne für n Jobs und zwei identischen Maschinen ist also (n + 1)!/2.

2.2 Problembeschreibung 7

Verfügung stehenden Transporter.

Das Beispiel zeigt auch, dass schon bei einer geringen Größe der Probleminstanz die optimale Lösung nicht unbedingt sofort erkennbar sein muss. Beide LKWs stehen zu Beginn in Berlin. Ein Auftrag der Liste ist eine Fahrt von Berlin nach Paris. Die Schlussfolgerung, diesen Auftrag zuerst auszuführen, ist aber falsch. Abbildung 2.1 zeigt, dass bei dem optimalen Ablaufplan der Auftrag Berlin-Paris erst der zweite Auftrag des zweiten LKWs ist.

2.2.2 Formale Beschreibung des Problems

In diesem Abschnitt wird das Problem formal beschrieben. Es werden Bezeichnungen deﬁniert und Eigenschaften des Problems beschrieben, die in der weiteren Arbeit verwendet werden.

Wir beginnen mit der Beschreibung der Probleminstanz. Gegeben sei eine Liste J von n Jobs (synonym Aufträgen): J = (J 1 , ..., J n ). Für einen einzelnen Job J i wird in dieser Arbeit auch einfach j geschrieben, solange die Bezeichnung eindeutig ist. Die Eigenschaften jedes Jobs j sind seine Bearbeitungszeit p j , die gewünschte Fertigstellungszeit d j und ein Gewicht des Jobs w j . Mit dem Gewicht kann die Be-

2 Ablaufplanungsprobleme für parallele Maschinen mit reihenfolgeabhängigen

8

Umrüstzeiten

deutung des Jobs für das Gesamtergebniss variiert werden. Das Gewicht kann z.B. kundenspeziﬁsch festgelegt werden. So können Aufträge wichtiger Kunden einen höheren Rang bei der Lösung des Problems erhalten.

Weiterhin existieren reihenfolgeabhängige Umrüstzeiten. Das bedeutet, wird auf einer Maschine Job j nach einem Job i verplant, ist eine Zeit s ij notwendig, um die Maschine für die Bearbeitung von j umzurüsten. Mit s 0j wird die Rüstzeit für Job j bezeichnet für den Fall, dass j als erster Job auf der Maschine verplant wird. s 0j wird als Anfangsrüstzeit bezeichnet. In der Literatur ﬁndet man auch den Spezialfall: s 0j = 0 für alle j. Dieser Fall soll jedoch in dieser Arbeit nicht gesondert behandelt werden.

Eine Probleminstanz P ist nun deﬁniert durch eine Jobliste J, eine (|J| + 1) × |J|- Matrix S derUmrüstzeiten und einer Anzahl von identischen parallelen Maschinen m:

P ≡ (J, S, m). (2.1)

Eine Probleminstanz besitzt folgende grundlegenden Eigenschaften:

Anzahl der Jobs: n := |J|,

Σ n j=1 p j durchschnittliche Bearbeitungszeit: p := ,

n

Σ n j=1 d j durchschnittliche gewünschte Fertig- d := ,

n

stellungszeit:

kleinste gewünschte Fertigstellungs- d min := min j∈J d j , zeit:

2.2 Problembeschreibung 9

größte gewünschte Fertigstellungszeit: d max := max j∈J d j ,

durchschnittliche Rüstzeit:

ˆ erwartete Zykluszeit: C max := ^(p+s)n ,

m

Enge der Fertigstellungstermine: τ := 1 − d ,

^ˆ Cmax

Spanne der Fertigstellungstermine: R := dmax−d min ,

^ˆ Cmax

Rüstfaktor: η := s .

p

Die Durchschnittswerte, Minimal- und Maximalwerte müssen nicht weiter erklärt werden. Die erwartete Zykluszeit ˆ C max ist eine Schätzung des Zeitpunktes, an dem

alle Jobs der gegebenen Probleminstanz bearbeitet sein werden. Enge und Spanne der Fertigstellungstermine sowie der Rüstfaktor sind weitere wichtige Eigenschaften einer Probleminstanz. Sie bestimmen die Relevanz der gegebenen Bearbeitungszeiten, Fertigstellungstermine und Umrüstzeiten bei der Suche nach einem optimalen Ablaufplan. Je kleiner τ bzw. je größer R, um so höheren Einﬂuss haben die gegebenen gewünschten Fertigstellungstermine. Je größer η um so wichtiger ist die Betrachtung der Umrüstzeiten bei der Suche nach einer optimalen Lösung.

In [Mön09] ist ein Ablaufplan wie folgt deﬁniert:

Unter einem Ablaufplan versteht man für jeden Job die Belegung von einem oder von mehreren Zeitintervallen auf den Maschinen.

Bei Ablaufplänen die hier diskutiert werden, belegt jeder Job genau ein Zeitintervall auf genau einer der m Maschinen. Ein solcher Ablaufplan Q lässt sich formal als eine Liste von m Indexlisten Q = (I 1 ,...,I m ) darstellen. Dabei repräsentiert eine Indexliste I k = (q k (1),...q k (|I k |)) die Jobsequenz auf der Maschine k. Es bezeichnet q k (i) mit (1 ≤ i ≤ |I k |) den Index des i-ten Jobs der Jobsequenz I k .

2 Ablaufplanungsprobleme für parallele Maschinen mit reihenfolgeabhängigen

10

Umrüstzeiten

Der Wert q k (0) ist kein Wert aus der Indexliste I k , da der Index mit 1 beginnt. Aus technischen Gründen (zur Vereinfachung folgender Formeln) deﬁnieren wir jedoch q k (0) = 0, für alle k mit 1 ≤ k ≤ m. Damit bezeichnet s q k ^(0)q k (1) die Anfangsrüstzeit des Jobs q k (1) - das heißt des ersten auf Maschine k verplanten Jobs.

In dieser Arbeit werden Verfahren vorgestellt, die für eine gegebene Probleminstanz (J,S,m) einen Ablaufplan Q erstellen, indem schrittweise jeder Job aus J dem Ablaufplan hinzugefügt wird. Wir bezeichnen bei einem solchen Verfahren mit J d die Menge der Jobs aus J, die bereits in den Ablaufplan aufgenommen wurden und mit J s die Jobs aus J, die noch zu verplanen sind. Eine Jobliste ist vollständig verplant, wenn sich jeder Job aus der Liste in genau einer Indexliste I k beﬁndet. In dem Fall ist J d = J und J s = ∅.

Durch die beschriebene Darstellungen eines Ablaufplanes Q können nun folgende, grundlegenden Eigenschaften eines Ablaufplanes Q für eine Probleminstanz P deﬁniert werden:

Fertigstellungszeit des Jobs: q k (u): C q k (u) := Σ u i=1 (s q k ^(i−1)q k (i) + p q k (i) ),

Verspätung des Jobs q k (u) auf Ma-:= max(C q k (u) − d q k (u) , 0), T k

q k (u)

schine k:

^|I k ^| totale gewichtete Verspätung des Ab- TW T (Q) := Σ m k=1 (Σ l=1 (w q k (l) T q k (l) )), laufplanes Q:

^|I k ^| Verfügbarkeitszeitpunkt der Jobse- ms(I k ):= Σ i=1 (s q k ^(i−1)q k (i) + p q k (i) ). quenz I k :

Betrachten wir noch einmal den Einﬂuss der Enge der Fertigstellungstermine τ ei- ner Probleminstanz auf die totale gewichtete Verspätung. Laut Deﬁnition von τ

2.3 Diskussion von Vorarbeiten 11

gilt stets τ ≤ 1. Für den Fall τ = 1 gilt d = 0 und somit d j = 0 für alle j ∈ J. In diesem Fall gilt T k q k (u) = max(C q k (u) − d q k (u) , 0) = max(C q k (u) − 0, 0) = C q k (u) . Damit ist die Suche nach der minimalen totalen gewichteten Verspätung identisch mit der Suche nach der minimalen totalen gewichteten Fertigstellungszeit Σw j C j . Je kleiner τ , um so mehr Einﬂuss haben die gewünschten Fertigstellungstermine auf die totale gewichtete Verspätung. Es gilt aber auch, je kleiner τ um so größer ist die Wahrscheinlichkeit, dass ein Ablaufplan Q mit T W T (Q) = 0 existiert.

Wir können nun das gegebene Problem aus der Aufgabenstellung formal wie folgt beschreiben: Sei Q(P ) die Menge aller möglichen zulässigen Ablaufpläne für eine gegebene Probleminstanz P . Gesucht ist ein Ablaufplan Q opt ∈ Q(P ) mit:

T W T (Q opt ) = min Q∈P (Q) (T W T (Q)). (2.2)

In [Gra79] wird die α|β|γ-Notation für Ablaufplanungsprobleme eingeführt. Diese Notation ist eine Standardnotation in der Ablaufplanungsliteratur [Mön09]. In dieser Notation beschreibt α die Maschinenumgebung. Das β-Feld speziﬁziert Restriktionen und Bedingungen, die für Jobs und Maschinen gelten. Das γ-Feld beschreibt das Leistungsmaß und damit das Optimierungsziel. In dieser Notation wird das hier vorgestellte Problem als P m |s ij | w j T j -Problem dargestellt. P m gibt an, dass

es sich um ein Mehrmaschinenproblem handelt, wobei ein Job auf allen Maschinen gleiche Bearbeitungszeiten hat (identische Maschinen).

Das Problem ist NP-schwer, da bereits 1|| w j T j NP-schwer ist (siehe [Pin01]).

2.3 Diskussion von Vorarbeiten

Das P m |s ij | w j T j -Problem ist in [Pin01] beschrieben. In diesem Buch wird die ATCS-Heuristik als möglicher Lösungansatz für das Problem vorgestellt.

2 Ablaufplanungsprobleme für parallele Maschinen mit reihenfolgeabhängigen

12

Umrüstzeiten

Die ACO-Metaheuristik ist eine gemeinsame Beschreibung von Verfahren, die das Verhalten von Ameisen zur Lösung diskreter Optimierungsprobleme adaptieren. Sie wurde 1999 von Dorigo und Di Caro in [Dor99] vorgestellt. Das erste solcher Verfahren ist das 1992 von Dorigo vorgestellte Ant-System (AS) [Dor92]. Wichtige Variationen dieses Verfahrens sind das Ant-Colony-System (ACS) [Dor96] und das Max-Min-Ant-System (MMAS) [Stü00].

In [Bes00], [Mer00], [Hol05] wird die Anwendung der ACO-Metaheuristik auf das Einzelmaschinenproblem 1||Σw j T j vorgestellt. In [Bes00] wird die Verwendung der Modiﬁed-Due-Date(MDD)-, der Earliest-Due-Date(EDD)-, und der Apparent-Urgency(AU)-Regel (siehe [Pin01]) als lokale Heuristik für die Anwendung von ACS untersucht. In [Mer00] wird die Summationsregel eingeführt, die in Abschnitt 3.4 beschrieben ist. Die Summationsregel wird auch in [Mön08] und [Hol05] benutzt. Die verwendete lokale Heuristik ist eine Variation der MDD-Regel. In [Hol05] wird ein neuer ACO-Algorithmus, FACO genannt, vorgestellt. Er unterscheidet sich gegenüber anderen Verfahren vor allem in der Auswahl des nächsten Knotens bei der Konstruktion einer Lösung (vgl. Abschnitt 3.3). Als lokale Heuristik wird die EDD-Regel verwendet.

In [Lia07] wird die Verwendung von ACS für die Lösung des 1||Σw j T j -Problems untersucht. Als lokale Heuristik wird die ATCS-Regel benutzt, die ebenfalls in [Pin01] beschrieben ist. Es wird ein Parameter K eingeführt, mit dem der Wert für die initialen Pheromonwerte (vgl. Abschnitt 3.3) variiert werden kann. Weiterhin wurde experimentell belegt, dass die Interpretation der Pheromonwerte als Job-Position-Zuordnung (vgl. Abschnitt 3.4) bessere Ergebnisse liefert, als die Interpretation als Job-Job-Zuordnung. Das in [Lia07] erarbeitete Verfahren wurde auf die in [Cic03] vorgestellten Testinstanzen angewendet. Dabei konnte für 90 der 120 Testinstanzen bessere Lösungen gefunden werden.

Bei der Anwendung der ACO-Metaheuristik auf Mehrmaschinenprobleme ist das

2.3 Diskussion von Vorarbeiten 13

Problem der Verteilung der Jobs auf die einzelnen Maschinen zu lösen. Hier lassen sich in der Literatur unterschiedliche Ansätze ﬁnden. Das List-Scheduling-Verfahren (vgl. [Mön09]) wird für das P m ||Σw j T j -Problem in [Rag09] und für das R m ||Σw j T j -Problem in [Mön08] verwendet. Eine Erweiterung gegenüber dem List-Scheduling-Verfahren besteht darin, dass mit einer bestimmten Wahrscheinlichkeit nicht die Maschine mit aktuell kleinster Zykluszeit, sondern eine zufällig bestimmte Maschine gewählt wird. Eine weitere wichtige Erweiterung aus [Mön08] ist die Einführung vom maschinenabhängigen Pheromonwerten (siehe Abschnitt 3.4). In [Zho07] erfolgt die Maschinenauswahl durch Pheromonwerte. Das bedeutet, es existieren zwei Pheromontypen. Es gibt Pheromone für die Auswahl einer Maschine und für die Auswahl des nächsten Jobs. Das Prinzip, in jedem Schritt eine Maschine und für diese Maschine einen Job zu bestimmen, wird jedoch beibehalten. In diesem Punkt unterscheidet das in [Arn08] vorgestellte Verfahren. Hier erfolgt zunächst in einem ersten Schritt die Zuweisung aller Jobs zu den Maschinen und in einem zweiten Schritt die Bestimmung der Reihenfolge der Jobs pro Maschine. Für beide Schritte werden Pheromone verwendet. In [Zho07] und [Arn08] wird, wie in [Mön08] das R m ||Σw j T j -Problem behandelt.

Es wurde keine Arbeit gefunden, die die Anwendung der ACO-Metaheuristik auf das P m |s ij | w j T j -Problem zum Gegenstand hat.

3 Konzept zur Lösung des Problems

Das hier besprochene P m |s ij |Σw j T j -Problem ist, wie die meisten Ablaufplanungsprobleme, NP-schwer. Das bedeutet, falls P ⊂ N P ¹ , existiert kein Algorithmus, der das Problem in polynomialer Zeit löst. Aus diesem Grund werden Heuristiken gesucht, die in adäquater Zeit eine möglichst gute Lösung für eine gegebene Probleminstanz liefern sollen. Kapitel 3.1 stellt eine Klasse von Heuristiken - die prioritätsbasierten Heuristiken vor, die für Ablaufplanungsprobleme verwendet wird. Es wird gezeigt, wie die ATCS-Heuristik als Beispiel für eine prioritätsbasierte Heuristik, auf das P m |s ij |Σw j T j -Problem angewendet werden kann.

In Abschnitt 3.3 wird die ACO-Metaheuristik als Optimierungsverfahren vorgestellt, welches das Verhalten von Ameisenkolonien adaptiert. Anschließend wird in Abschnitt 3.4 ein Verfahren erarbeitet, das die ACO-Metaheuristik auf das P m |s ij |Σw j T j -Problem anwendet.

3.1 Prioritätsbasierte Heuristiken

Die Grundidee bei prioritätsbasierten Heuristiken besteht darin, für jeden Job an-hand einer Prioritätsregel einen Index zu berechnen und den Job mit dem höchsten Index als nächsten Job zu verplanen. Man unterscheidet zwischen statischen und dynamischen Prioritätsregeln. Statische Prioritätsregeln sind zeitunabhängig. Ein Beispiel für eine statische Prioritätsregel ist die folgende Weighted-Shortest-

1 Das ist aber noch nicht bewiesen.

16 3 Konzept zur Lösung des Problems

Processing-Time(WSPT)-Regel:

Die WSPT-Regel ﬁndet die optimale Lösung für das 1||w j C j -Problem, wie in [Pin01] bewiesen wird. Eine weitere zeitunabhängige Prioritätsregel ist die Shortest-Setup-Time(SST)-Regel:

Hier wird der Index in Abhängigkeit des zuvor verplanten Jobs bestimmt. Die SST-Regel wird zur Lösung des 1|s ij |C max -Problems angewendet.

Bei dynamischen Prioritätsregeln ist der Index zeitabhängig. Das bedeutet, dass der Index nach jeder Verplanung eines Jobs neu berechnet werden muss. Ein Beispiel für eine dynamische Prioritätsregel ist die Minimum-Slack(MS)-Regel:

M S j (t) = max(d j − p j − t). (3.3)

Dabei ist t der aktuelle Verfügbarkeitszeitpunkt der Maschine, auf die Job j verplant werden soll. Die MS-Regel wird für das 1||L max -Problem verwendet [Pin01]. Dabei ist das Leistungsmaß L max die maximale Terminabweichung aller Jobs (L max = max j∈J (C j − d j )).

3.1 Prioritätsbasierte Heuristiken 17

Für komplexere Optimierungsziele können Prioritätsregeln zu zusammengesetzten Prioritätsregeln kombiniert werden. Ein Beispiel für eine solche zusammengesetzte Prioritätsregel ist die Apparent-Tardiness-Cost-with-Setups(ATCS)-Regel. Bei der ATCS-Regel wird der Prioritätsindex mit folgender Formel berechnet:

Die ATCS-Regel wird als Heuristik für das 1|s ij |Σw j T j -Problem verwendet. Sie ist eine Kombination der WSPT-, MS- und der SST-Regel. Dabei bezeichnet t den Verfügbarkeitszeitpunkt der Maschine. Die Faktoren k 1 und k 2 dienen zur Wichtung der einzelnen Bestandteile der Formel. In [Pin01] wird vorgeschlagen, diese Parameter mit Hilfe der Enge der Fertigstellungstermine τ , der Spanne der Fertigstellungstermine R und dem Rüstfaktor η der gegebenen Probleminstanz wie folgt zu bestimmen:

Eine andere Möglichkeit zur Bestimmung günstiger Werte für die Faktoren k 1 und k 2 ist die Durchführung einer Gitterpunktanalyse. Dabei werden die Parameter innerhalb eines Intervalls variiert und diejenige Parameterkombination gewählt, die zum besten Ergebnis für die gegebene Probleminstanz führt. In [Mön08] wird diese Methode angewendet.

18 3 Konzept zur Lösung des Problems

3.2 Anwendung der ATCS-Regel auf das

P m |s ij |Σw j T j -Problem

Bei der Anwendung der ATCS-Regel auf ein Mehrmaschinenproblem kommt die Aufgabe hinzu, die Maschine für den nächsten zu verplanenden Job zu bestimmen. In [Mön09] wird der List-Scheduling-Algorithmus vorgestellt. Dieser Algorithmus wählt diejenige Maschine k mit dem kleinsten Verfügbarkeitszeitpunkt ms(k) aus und bestimmt für diese Maschine den nächsten Job mit Hilfe des Prioritätsindexes - in unserem Fall der ATCS-Regel.

Der in Abbildung 3.1 dargestellte Algorithmus verallgemeinert diesen Ansatz, indem zur Auswahl der nächsten Maschine nicht der Verfügbarkeitszeitpunkt, sondern eine allgemeine Kostenfunktion cost(k,j k ) verwendet wird. Für jede Maschine k wird durch die ATCS-Regel der potentiell nächste zu verplanende Job j k bestimmt. Anschließend wird durch die Kostenfunktion ermittelt, auf welcher Maschine der für diese Maschine ermittelte Job j k verplant wird.

Folgende Kostenfunktionen werden getestet:

cost 1 (k,j k ) = ms(I k ),

cost 2 (k,j k ) = ms(I k × j k ) = ms(I k ) + s last(I k )j k + p j k ,

cost 3 (k,j k ) = w j k T k j k = max(0, w j k ∗ (ms(I k × j k ) − d j k )),



 cost 4 (k,j k ) = 

Dabei bedeutet ms(I k ) der Verfügbarkeitszeitpunkt der Jobsequenz I k (vgl. Abschnitt 2.2.2). Mit I k × j k wird die um den Job j k erweiterte Jobsequenz I k bezeichnet.

Die erste Kostenfunktion implementiert den in [Mön09] vorgestellten List-Scheduling- Algorithmus. Bei der Kostenfunktion cost 2 wird, als Erweiterung von cost 1 , noch die

0.1: S 1..m // Jobsequenzen der Maschinen 1..m (S i = ∅)

0.2: Setze J s ← J // Menge der noch zu verplanenden Jobs

1: while(J s = ∅)

1.1: foreach k (1 ≤ k ≤ m)

1.1.1: bestimme j k ∈ J s mit I j k (S k ) = max j∈J s (I j (S k ))

1.2: bestimme m next mit cost(m next , j mnext ) = min 0 (cost(k, j k )) 1.3: S mnext ← S mnext × j mnext 1.4: J s ← J s \ j mnext

2: return S 1..m

Rüstzeit und Bearbeitungszeit des als nächstes zu verplanenden Jobs berücksichtigt. Die Idee von cost 3 besteht darin, denjenigen Job mit der geringsten gewichteten Verspätung zu verplanen. cost 4 ist schließlich eine Kombination von cost 2 und cost 3 .

3.3 ACO-Metaheuristik

Ameisen führen, wie weiter unten gezeigt wird, bei der Futtersuche eine Wegoptimierung durch. Die erste Adaption des Verhaltens von Ameisen zur Lösung von Optimierungsproblemen ist das sogenannte Ant System (AS), das in [Dor92] vorgestellt wird. In der Literatur ﬁnden sich mehrere Variationen bzw. Erweiterungen von AS. In [Dor99] wird schließlich die ACO-Metaheuristik vorgestellt. Die ACO-Metaheuristik ist zum Einen eine Konsolidierung aller bis dahin beschriebenen

20 3 Konzept zur Lösung des Problems

Ameisenverfahren, zum Anderen eine Vorlage für Verfahren, die später vorgestellt wurden.

In diesem Abschnitt wird zunächst das Verhalten von Ameisenkolonien bei der Futtersuche erläutert und anschließend gezeigt, wie dieses Verhalten in verschiedenen Heuristiken adaptiert wurde. Am Ende des Abschnittes wird die ACO-Metaheuristik beschrieben.

3.3.1 Futtersuche von Ameisen

Hat ein Ameisenvolk eine Futterquelle gefunden, dann ist zu beobachten, dass nach einer gewissen Zeit alle Ameisen den selben Weg vom Nest zur Futterquelle benutzen. Man kann weiter feststellen, dass dieser Weg hinsichtlich der Länge minimal ist, bzw. dem Minimum sehr nahe kommt. Es scheint also, dass Ameisen Wege von ihrem Nest zu einer Futterquelle optimieren können. Diese Beobachtung ist durch ein Experiment von Goss et al [Gos89] veriﬁziert worden. Das Experiment bestand darin, Ameisen zwei Wege unterschiedlicher Länge zu einer Futterquelle zu ermöglichen. Es wurde festgestellt, dass alle Ameisen nach einer bestimmten Einschwingphase stets den kürzeren Weg zur Futterquelle wählten.

Die Frage ist nun, welches Prinzip den Ameisen diese Wegoptimierung ermöglicht. Man weiß, dass Ameisen auf ihrem Weg Pheromone (d.h. Duftstoﬀe) verteilen. Bei der Entscheidung, wie eine Ameise bei ihrer Futtersuche ihren Weg fortsetzt, werden von der Ameise alle vorhandenen Pheromonspuren in der Umgebung berücksichtigt. Die Ameise wählt mit größerer Wahrscheinlichkeit einen Weg, der durch eine höhere Pheromonkonzentration markiert ist. Indem sie diesen Weg wählt, erhöht sie selbst die Pheromonkonzentration dieses Weges weiter. Die Menge der Pheromonspuren, welche die Ameisen hinterlegen, bildet eine globale Struktur an Information. Ameisen kommunizieren indirekt über diese globale Struktur miteinander. Diese indirekte Kommunikation bezeichnet man als Stigmergenz.

3.3 ACO-Metaheuristik 21

Das Ergebnis des Experiments von Goss et al. [Gos89] kann nun wie folgt begründet werden: Zu Beginn sind keine Pheromone verteilt. Die Ameisen wählen beide Wege mit gleicher Wahrscheinlichkeit. Damit steigt die Pheromonintensität auch auf beiden Wegen gleich. Die Ameisen, die den kürzeren Weg gewählt haben, erreichen die Futterquelle aber zuerst. Als Rückweg zum Nest benutzen sie den selben Weg, da dieser bereits durch Pheromone markiert ist. Erreichen nun die ersten Ameisen, die den kürzeren Weg zum Futter gewählt haben, wieder das Nest, so ist die Pheromonspur dieses kürzeren Weges plötzlich höher als die Pheromonspur des längeren Weges. Dadurch wählen mehr Ameisen diesen kürzeren Weg und verstärken die Pheromonspur des kürzeren Weges immer weiter. Es entsteht ein autokatalytischer Prozess, an dessen Ende alle Ameisen den kürzeren Weg zum Futter wählen.

3.3.2 AS

Als erste Adaption des beschriebenen Verhaltens von Ameisen gilt das von Dorigo in [Dor92] eingeführte Ant System (AS). AS ist eine Heuristik, mit der in gewichteten Graphen kürzeste Wegen gefunden werden können.

Gegeben sei ein schlichter Graph G = (V,E) mit einer Kantenwichtung d ij . Gesucht ist ein kürzester Weg der bestimmte Bedingungen erfüllt. Im Fall des Traveling-Salesman-Problems (TSP) sind Hamiltonkreise gesucht.

Die Grundidee von AS ist, „Ameisen“ nach kürzesten Wegen suchen zu lassen. In jeder Iteration werden m „Ameisen“ erzeugt. Jede „Ameise“ ist ein Prozess, der mit einem leeren Weg beginnt und diesem Weg in jedem Schritt einen neuen Knoten hinzufügt. Am Ende ist ein Weg konstruiert, der einer Lösung des gegebenen Problems entspricht. Ist k eine „Ameise“ und i der zuletzt dem Weg von k hinzugefügte Knoten, dann bezeichnet N k (i) die Menge der Knoten, die als nächstes dem Weg hinzugefügt werden können. Weiterhin ist jeder Kante (ij) ∈ E ein Pheromonwert τ ij und eine lokale Heuristik η ij zugeordnet. Die Pheromonwerte repräsentieren ei- ne globale Struktur, die Informationen über bereits gefundene Lösungen anderer

22 3 Konzept zur Lösung des Problems

Ameisen abbildet. Diese Struktur wird von jeder Ameise aktualisiert. Die lokale Heuristik repräsentiert Informationen über die Probleminstanz, die für die Wegkonstruktion relevant sind. Im Falle von TSP entspricht η ij einfach der reziproken Kantenwichtung η ij = 1/d ij . Ist nun i der zuletzt hinzugefügte Knoten der Ameise k, so wird ein Knoten j ∈ N k (i) mit folgender Wahrscheinlichkeit p k ij dem Weg als nächster Knoten hinzugefügt:

Dabei sind α und β Parameter, die den Einﬂuss der Pheromonwerte und der lokalen Heuristik auf die Konstruktion des Weges wichten. Ist α = 0, so wird aus dem Algorithmus ein einfaches Greedy-Verfahren.

Ein weiterer Aspekt des Verfahrens ist die Pheromonänderung, d.h. die Anpassung der τ ij durch die „Ameisen“. Die Anpassung der τ ij geschieht durch die Formel:

τ ij ← ρτ ij + ∆τ ij . (3.7)

Dabei ist ρ ein Flüchtigkeitskoeﬃzient, der die Verdunstung der Pheromonwerte simuliert. Es gilt 0 ≤ ρ ≤ 1. ∆τ ij wird bestimmt durch:

∆τ ij = Σ m (3.8) k=1 ∆τ k ij ,

wobei ∆τ k ij den Pheromonwert darstellt, den die k-te Ameise auf der Kante (ij) hinterlassen hat. Insbesondere ist ∆τ k ij = 0, falls die Kante (ij) von der k-ten Amei-

se gar nicht besucht wurde. Für den Fall, dass (ij) Teil des durch die k-te Ameise gefundenen Lösungsweges ist, werden drei Modelle zur Bestimmung von ∆τ k ij unter-

3.3 ACO-Metaheuristik 23

schieden. Im Ant-Density-Modell wird ∆τ k ij = Q gesetzt, wobei Q eine Konstante

ist, welche die Pheromongrundmenge einer Ameise repräsentiert. Im Ant-Quantity-Modell ﬂießt die Kantenwichtung in die Berechnung der Pheromonmenge mit ein: ij = Q/d ij . Kürzere Kanten erhalten also eine höhere Pheromonmenge. Im Ant- ∆τ k

Cycle-Modell wird die Länge L k des durch die k-te „Ameise“ gefundenen Lösung in die Berechnung von ∆τ k ij mit herangezogen: ∆τ k ij = Q/L k . Weiterhin unterscheiden sich die drei genannten Modelle im Zeitpunkt, wann die Pheromonänderung erfolgt. Bei Ant-Density- und Ant-Quantity-Modellen erfolgt der Pheromonänderung nachdem eine „Ameise“ einen Weg konstruiert hat. Bei Ant-Cycle erfolgt der Pheromonupdate am Ende jeder Iteration. Ant-Cycle hat sich als die deutlich beste der drei Möglichkeiten herausgestellt. Das kann damit begründet werden, dass bei diesem Modell die Güte der gefundenen Lösung in die Pheromonänderung mit einﬂießt. In Abbildung 3.2 ist AS mit dem Ant-Cycle-Modell abgebildet.

1: InitializePheromonsAndParameters()

2: while terminationCriterionNotSatisﬁed

2.1: for k = 1 to maxAntCount 2.1.1: ConstructSolution() 2.2: UpdatePheromons()

3: return bestSolutionFound

3.3.3 ACS

ACS (Ant-Colony-System) ist eine Erweiterung von AS, die in [Dor96] beschrieben wird. ACS unterscheidet sich von AS in folgenden drei Punkten:

24 3 Konzept zur Lösung des Problems

1. Wegkonstruktion: Bei der Wegkonstruktion erfolgt die Auswahl des nächsten Knotens j durch die Formel:

Dabei ist S ein mit Hilfe der Formel (3.6) zufällig gewählter Knoten, q < 1 ein Wahrscheinlichkeitswert und q 0 ≤ 1 ein Parameter. Die „Ameise“ wählt mit einer Wahrscheinlichkeit q 0 den Knoten, der zur Zeit die beste Bewertung hat. Mit einer Wahrscheinlichkeit von 1 − q 0 wird durch Formel (3.6) die „Umgebung erkundet“.

2. Pheromonänderung: Der Pheromonänderung erfolgt, wie bei Ant-Cycle, am Ende der Iteration. Allerdings wird nur die beste Lösung zur Änderung der Pheromonwerte berücksichtigt wird. Dabei kann entweder die global beste Lösung oder die beste Lösung der aktuellen Iteration verwendet werden.

3. lokale Verdunstung: Nachdem eine „Ameise“ eine weitere Kante (ij) ausgewählt hat, wird der Pheromonwert τ ij dieser Kante mit Hilfe folgender Formel reduziert:

τ ij ← (1 − θ)τ ij + θτ 0 . (3.10)

Dabei ist τ 0 der initiale Pheromonwert und 0 ≤ θ ≤ 1 ein Parameter, der die Stärke der Verdunstung bestimmt. Durch die lokale Verdunstung wird die Wahrscheinlichkeit verringert, dass die Kante von einer folgenden „Ameise“ der selben Iteration ebenfalls verwendet wird. Dadurch wird der Suchraum der Iteration erweitert.

3.3 ACO-Metaheuristik 25

3.3.4 AS Rank

Die AS Rank -Heuristik wird in [Bul97] beschrieben. Bei dieser Heuristik werden die „Ameisen“ einer Iteration bezüglich der Güte der gefundenen Lösung sortiert. Nur die besten n „Ameisen“ jeder Iteration tragen zur Pheromonänderung bei. Der Einﬂuss jeder „Ameise“ ist dabei gewichtet nach ihrem Rang in der aufgestellten „Bestenliste“.

3.3.5 MMAS

Das Max-Min-Ant-System (MMAS) ist eine weitere Erweiterung des AS. Diese Erweiterung wird in [Stü00] vorgestellt. Ähnlich wie bei ACS wird nur die global beste Lösung zur Pheromonänderung berücksichtigt. Die wesentliche Neuerung vom MMAS gegenüber AS ist die Einführung von Minimal- und Maximalwerten τ min und τ max für die Pheromone. Es gilt stets 0 < τ min ≤ τ ij ≤ τ max . τ min und τ max werden vor jeder Iteration durch folgende Formeln neu berechnet:

Dabei ist ρ der Flüchtigkeitskoeﬃzient aus Formel (3.7), L best der Zielfunktionswert der besten gefundenen Lösung, avg die durchschnittliche Größe der Nachbarschaftsmenge N k (siehe Abschnitt 3.3.2) und p best die geschätzte Wahrscheinlichkeit, dass das Optimum gefunden wird.

Durch die Beschränkung der Pheromonwerte auf ein Intervall wird der autokata-

26 3 Konzept zur Lösung des Problems

lytische Prozess gedämpft. Das Ziel besteht darin, eine zu schnelle Konvergenz in Richtung eines lokalen Optimums zu vermeiden. Eine weitere Idee ist die Initialisierung der Pheromonwerte auf τ max . Dadurch wird die Erkundung zu Beginn des Verfahrens erhöht.

In [Stü00] wird außerdem die PTS-Regel (pheromon trail smoothing) eingeführt. Die Pheromone werden durch Anwendung folgender Formel „geglättet“:

τ ij ← τ ij + δ(τ max − τ ij ). (3.13)

Dabei ist 0 ≤ δ ≤ 1 ein Glättungsfaktor, der die Pheromonwerte proportional zu ihrer Diﬀerenz zum maximalen Pheromonwert τ max erhöht. Dadurch wird die Wahrscheinlichkeit der Auswahl von Wegen mit geringeren Pheromonwerten erhöht und der Suchraum erweitert. Man beachte, dass δ = 0 die Glättung völlig ausschaltet, während δ = 1 alle Pheromonwerte auf τ max reinitialisiert. In [Stü00] wird für δ der Wert δ = 0.5 vorgeschlagen.

Erfahrungen mit MMAS zeigen, dass dieses Verfahren in der Regel zu besseren Lösungen führt, dafür jedoch wesentlich länger benötigt als andere hier beschriebene Verfahren.

3.3.6 ACO

Die ACO-Metaheuristik wird in [Dor99] vorgestellt. Sie kann als gemeinsame Beschreibung der Verfahren verstanden werden, die das Prinzip der Ameisen der indirekten Kommunikation adaptieren, um kürzeste Wege in gewichteten Graphen zu ﬁnden. Die hier vorgestellten Verfahren AS, ACS, MMAS und AS Rank können als Ausprägungen der ACO-Metaheuristik betrachtet werden.

Das Prinzip der ACO-Metaheuristik besteht darin, dass „Ameisen“ im gegebenen

3.3 ACO-Metaheuristik 27

Graphen Lösungswege konstruieren, die die gegebenen Bedingungen erfüllen. Bei der Konstruktion der Wege beginnt eine „Ameise“ mit einem leeren Weg und fügt in jedem Schritt dem Weg einen weitere Knoten hinzu. Beim Hinzufügen eines Knotens ist die „Ameise“ in der Lage, alle potentiell möglichen Knoten N (i) zu bestimmen, wobei i den Knoten bezeichnet, auf dem sich die „Ameise“ gerade beﬁndet. Aus dieser Knotenmenge wird mit Hilfe der Formel (3.9) der nächste Knoten für den Lösungsweg ermittelt. Bei der Wegkonstruktion benutzt die „Ameise“ eine problemspeziﬁsche lokale Heuristik η und Informationen eines Pheromonfeldes τ . Das Pheromonfeld ist eine globale Datenstruktur, welche den Status der Lösungssuche des Verfahrens repräsentiert. „Ameisen“ kommunizieren ausschließlich indirekt über das Pheromonfeld miteinander. Das Pheromonfeld wird von den „Ameisen“ aktualisiert. Die ACO-Metaheuristik unterscheidet zwischen drei Möglichkeiten der Aktualisierung: Jede „Ameise“ kann die Pheromonwerte nach dem Hinzufügen eines Knotens (online step-by-step pheromon update) und nach Beendigung der Wegkonstruktion (online delayed pheromon update) aktualisieren. Als dritte Option ist eine Aktualisierung der Pheromone am Ende einer Iteration möglich (oﬄine pheromon update). So können nach einer Iteration etwa die beste gefundene Lösung das Pheromonfeld und amit den Status des Verfahrens weiter beinﬂussen. Damit die ACO-Metaheuristik auf ein Problem anwendbar ist, muss sich dieses Problem als Suche nach kürzesten Wegen, die gegebene Bedingungen erfüllen, beschreiben lassen. Außerdem muss eine „Ameise“ stets in der Lage sein, einen Weg zu konstruieren, der die gestellten Bedingungen erfüllt. Das heißt, bei der Wegkonstruktion einer „Ameise“ darf die Menge der möglichen Folgeknoten N (i) nicht leer sein, solange die Wegkonstruktion nicht beendet ist und der konstruierte Weg keine Lösung für das gegebene Problem darstellt.

28 3 Konzept zur Lösung des Problems

3.4 Anwendung der ACO-Metaheuristik auf das

P m |s ij |Σw j T j -Problem

In diesem Abschnitt wird beschrieben, wie sich die ACO-Metaheuristik auf das P m |s ij |Σw j T j -Problem anwenden lässt. Als erstes werden Ideen vorgestellt, die sich für die Anwendung der ACO-Metaheuristik auf Ablaufplanungsprobleme in der Literatur ﬁnden lassen. Die Anwendung der ACO-Metaheuristik auf Ablaufplanungsprobleme erfordert eine Beschreibung des Problems als Suche nach kürzesten Wegen in einem gewichteten Graphen. Es werden Konstruktionen für solche Graphen für Einzelmaschinenprobleme vorgestellt und Konstruktionen für Mehrmaschinenproblem erarbeitet. Anschließend erfolgt die Vorstellung des Konzeptes zur Anwendung der ACO-Metaheuristik auf das P m |s ij |Σw j T j -Problem.

3.4.1 Anwendung der ACO-Metaheuristik auf Ablaufplanungsprobleme

Zur Anwendung der ACO-Metaheuristik auf Ablaufplanungsprobleme ﬁnden sich in der Literatur folgende Ideen:

Interpretation der Pheromonwerte: Der Pheromonwert τ ij bestimmt die Pheromonmenge für das Verplanen von Job j auf Position i. Diese Interpretation des Pheromonfeldes hat sich für Ablaufplanungsprobleme bewährt, bei denen die Fertigstellungszeit eine Rolle spielt. Der Grund dafür ist, dass bei solchen Problemen die Position der Verplanung eines Jobs einen wesentlichen Einﬂuss auf die Güte einer Lösung hat. Das wird mit dieser Interpretation des Pheromonfeldes berücksichtigt. Diese Interpretation der Pheromonwerte kann auch für Mehrmaschinenprobleme angewendet werden. In diesem Fall wird mit Hilfe der der ACO-Metaheuristik eine Jobsequenz erstellt und die Jobs dann anhand dieser Sequenz und durch Anwendung des List-Scheduling-Verfahrens (vgl. [Mön09]) auf die Maschinen verteilt. Dagegen wird in [Mön08] wird vorgeschlagen, maschinenabhängige Pheromonwerte τ ijk zu benutzen. Dabei bestimmt τ ijk die Pheromonmenge für das Verplanen von Job j an Position i auf Maschine k. In [Mön08] wurden maschinenabhängige Pheromonwerte

3.4 Anwendung der ACO-Metaheuristik auf das P m |s ij |Σw j T j -Problem 29

für heterogen Maschinen eingeführt. Die Idee lässt sich natürlich auch auf Probleme mit identischen Maschinen anwenden.

Summationsregel: In [Mer00] wird eine Summationsregel für Pheromonwerte eingeführt. Es wird vorgeschlagen, die Formeln (3.6) und (3.9) durch folgende Formeln zu ersetzen:

Die Idee dahinter ist, dass ein hoher Pheromonwert für einen Job j an einer Position i auch Einﬂuss auf die Verplanung des Jobs auf alle nachfolgenden Positionen haben soll. Wurde der Job nicht an Position i verplant, so erhöht die Summationsregel die Wahrscheinlichkeit, dass er möglichst bald hinter i verplant wird. Ein hoher Pheromonwert an Position i beeinﬂusst also auch die Entscheidungen für die darauﬀolgenden Positionen.

Auswahl der nächsten Maschine: Bei Mehrmaschinenproblemen muss in jedem Schritt diejenige Maschine bestimmt werden, für die der nächste zu verplanende Job ausgewählt wird. In [Mön08] und [Rag09] wird vorgeschlagen, jeweils die Maschine mit der geringsten Fertigstellungszeit auszuwählen. In [Mön08] wird außerdem vorgeschlagen, mit einer bestimmten Wahrscheinlichkeit von dieser Regel abzuweichen und eine beliebige Maschine zu selektieren.

30 3 Konzept zur Lösung des Problems

3.4.2 Konstruktion des Graphen für die ACO-Metaheuristik

Die vorgestellte Interpretation der Pheromonwerte wirft die Frage auf, wie aus einem Ablaufplanungsproblem der Graph zur Anwendung der ACO-Metaheuristik konstruiert werden kann. In [Bau99] werden zwei Möglichkeiten für die Konstruktion eines Graphen für Ablaufplanungsprobleme mit Einzelmaschinen gezeigt. Wir beginnen mit der Vorstellungen dieser Konstruktionen und entwickeln anschließend zwei unterschiedliche Konstruktionen für Mehrmaschinenprobleme.

Gegeben sei eine Jobmenge J mit |J| = n. Ein Graph G = (V,E) wird wie folgt konstruiert: Die Knotenmenge V wird der Potenzmenge ℘(J) gleichgesetzt: V = ℘(J). Damit repräsentiert jeder Knoten v ∈ V eine Teilmenge der Jobs (v ⊆ J). Zwischen zwei Knoten u,v ∈ V mit u = v existiert genau dann eine Kante uv, wenn gilt v = u ∪ {j} mit j ∈ J. Das bedeutet, eine Kante von u nach v existiert genau dann, wenn v durch Hinzufügen eines weiteren Jobs zu u entsteht. Die Knoten lassen sich in n + 1 Schichten anordnen V = V 0 ∪ V 1 ∪ . . . ∪ V n , wobei die Schicht V i alle Kno- ten v ∈ V mit |v| = i enthält. Jede Schicht V i enthält genau Knoten. Jeder n

i

dieser Knoten besitzt n − i ausgehende Kanten. Damit enthält der Graph genau (n−i) = 2 n · n Kanten. Abbildung 3.3 zeigt den Graphen für den Fall |J| = 3. n Σ n

i=0 i 2

Jeder Knoten v ∈ V repräsentiert den Zustand, dass die Jobs v ⊆ J bereits verplant wurden. V 0 enthält genau einen Knoten v ∅ , der den Zustand darstellt, dass noch kein Job verplant wurde. V n enthält ebenfalls nur einen Knoten v J der die Verplanung aller Jobs symbolisiert. Jeder Weg von v ∅ nach v J stellt einen gültigen Ablaufplan dar. So repräsentiert der in Abbildung 3.3 eingezeichnete Weg den Ablaufplan (3,1,2). Damit erfüllt der Graph die Bedingungen, um als Eingabe für die ACO-Metaheuristik zu dienen. Die „Ameisen“ starten mit der Wegkonstruktion in v ∅ und sind stets in der Lage, einen Weg nach v J und damit einen gültigen Ablaufplan zu konstruieren. Ein Problem ist jedoch das exponentielle Wachstum der Anzahl der Kanten gegenüber der Jobanzahl. Der Verplanen der Jobs j an Position i wird nicht durch eine Kante, sondern durch Kanten repräsentiert. Jede dieser n−1

i−1

Kanten uv symbolisiert das Verplanen des Jobs j an Position i unter der Bedingung,

3.4 Anwendung der ACO-Metaheuristik auf das P m |s ij |Σw j T j -Problem 31

dass vorher die Jobs u verplant wurden. Bei der oben angegebenen Interpretation der Pheromonwerte τ ij entspricht die Aktualisierung eines Pheromonwertes der Aktualisierung der Pheromonwerte aller Kanten uv mit v ∈ V i und v \ u = {j}.

Abbildung 3.3: Graph für Einzelmaschinenproblem - 1. Möglichkeit

Bei der zweiten in [Bau99] vorgestellten Konstruktion wird ein Graph G = (V,E) mit V = V 1 ∪ . . . ∪ V n erstellt. Jede Teilmenge V i ⊆ V enthält n + 1 Knoten V i = {v i1 , . . . , v in }∪{p i }. Die Kantenmenge E setzt sich zusammen aus E = E 1 ∪E ² mit E 1 = {p i v ij : 1 ≤ i,j ≤ n} und E 2 = {v ij p i+1 : 1 ≤ i < n, 1 ≤ j ≤ n}. Der so konstruierte Graph besteht aus n(n + 1) Knoten und 2n(n − 1) Kanten. Jeder Ablaufplan kann als ein Weg von p 1 zu einem Knoten v nj ∈ V n beschrieben werden. Die Wahl einer Kante p i v ij ∈ E 1 entspricht der Verplanung von Job j an Position i. Abbildung 3.4 zeigt den Graph für |J| = 3. Der markierte Weg beschreibt wiederum den Ablaufplan (3,1,2).

32 3 Konzept zur Lösung des Problems

Nicht jeder Weg von p 1 zu einem Knoten v nj ∈ V n stellt einen gültigen Ablaufplan dar. Allerdings ist es einer „Ameise“ jederzeit möglich, für einen Knoten p i die Menge aller möglichen Kanten N pi ⊆ {p i v ij : 1 ≤ j ≤ n} zu bestimmen, indem sie bei der Wegkonstruktion die bereits verplanten Jobs lokal speichert. Dabei ist |N pi | = n − i + 1 für alle 1 ≤ i ≤ n. Der „Ameise“ ist es also stets möglich, einen gültigen Ablaufplan zu konstruieren. Der konstruierte Graph erfüllt somit die Voraussetzungen, um als Eingabe für die ACO-Metaheuristik verwendet werden zu können. In den Knoten v ij mit 1 ≤ i < n, 1 ≤ j ≤ n muss die „Ameise“ keine Entscheidung treﬀen, da von diesen Knoten jeweils nur eine Kante aus der Menge E 2 ausgeht, der zum Knoten p i+1 führt.

Abbildung 3.4: Graph für Einzelmaschinenproblem - 2. Möglichkeit

3.4 Anwendung der ACO-Metaheuristik auf das P m |s ij |Σw j T j -Problem 33

Die zweite vorgestellte Konstruktion führt zu einem Graphen mit wesentlich weniger Knoten und Kanten. Bei der Interpretation des Pheromonwertes τ ij als „Pheromonmenge für das Verplanen von Job j auf Position i“ wird jedes τ ij durch genau eine Kante (p i v ij ) repräsentiert, anstatt durch Kanten. Die zweite Konstruktion n−1

i−1

ist somit einfacher und stringenter als die erste. Bei der ersten Konstruktion repräsentieren die Pheromonwerte das Verplanen eines Jobs j an Position i unter der Bedingung, dass vorher die Menge u ⊆ J mit |u| = i − 1 verplant wurde. Diese Repräsentation ist technisch nicht realisierbar, da Anzahl der zu verwaltenden Pheromonwerte mit der Anzahl der Jobs exponentiell wächst. Wird die Anzahl der zu verwaltenden Pheromonwerte eingeschränkt, indem man die Werte aller Kanten, die das Verplanen eines Jobs j an Position i repräsentieren gleichsetzt, führt dies letztendlich wieder zur zweiten Konstruktion, die diesen Sachverhalt aber einfacher darstellt.

Eine einfache Erweiterung der zweiten Konstruktion auf ein Mehrmaschinenproblem mit m Maschinen wird in Abbildung 3.5 gezeigt. Die Idee ist, dass jeder Knoten v ij aus dem Einzelmaschinenfall durch m Knoten v ijk mit 1 ≤ i,j ≤ n, 1 ≤ k ≤ m ersetzt wird. Entsprechend wird in E 1 jede Kante p i v ij durch m Kanten p i v ijk ersetzt. Die Auswahl einer Kante p i v ijk bei der Wegkonstruktion repräsentiert die Selektion des Jobs j an i-ter Stelle ¹ und Verplanung des Jobs auf Maschine k. Der in Abbildung 3.5 markierte Weg repräsentiert also die Verplanung der Jobs in folgender Reihenfolge: Job 3 auf Maschine 1, Job 1 auf Maschine 2 und Job 2 auf Maschine 1. Der erstellte Ablaufplan lautet also (m 1 = (3,1),m 2 = (2)).

Bei einem so konstruierten Graph, triﬀt eine „Ameise“ bei der Auswahl der nächsten Kante die Entscheidung für den nächsten Job und gleichzeitig für die Maschine, auf die dieser Job verplant werden soll. In [Mön08] und [Rag09] wird die nächste Maschine anhand der geringsten Fertigstellungszeit ms(k) bestimmt und anschließend

1 Man beachte, dass die Auswahl eines Jobs zur Verplanung an i-ter Stelle, anders als Einzelmaschinenproblemen, i.d.R. nicht der Position des Jobs auf der selektierten Maschine entspricht. Dieses Problem wird weiter unten noch behandelt.

Abbildung 3.5: Graph für Mehrmaschinenproblem - 1. Möglichkeit

mit Hilfe einer prioritätsbasierten Heuristik η job der nächste Job für diese Maschine ermittelt. Diese Vorgehensweise kann wie folgt als lokale Heuristik η ACO interpre- tiert und verwendet werden:

3.4 Anwendung der ACO-Metaheuristik auf das P m |s ij |Σw j T j -Problem 35

Die soeben betrachtete Konstruktion eines Graphen für ein Mehrmaschinenproblem stellt eine plausible Erweiterung der oben beschriebenen Konstruktion für das Einzelmaschinenproblem dar. Doch wie bereits angedeutet, entspricht die Auswahl einer Kante p i v ijk bei der Wegkonstruktion einer „Ameise“ nicht der Verplanung von Job j auf Maschine k an Position i, sondern der Selektion des Jobs j an i-ter Stelle. So wird in der in Abbildung 3.5 gezeigten Wegkonstruktion Job 1 an dritter Stelle ausgewählt und auf Position 2 der Maschine 1 verplant. Für die Interpretation des Index i als Position des Jobs auf Maschine k ist eine andere Konstruktion notwendig.

Gegeben sei wieder eine Jobmenge J und eine Maschinenanzahl m. Wir konstruieren einen Graph G = (V,E) = ({s} ∪ V 1 ∪ V 2 ∪ . . . ∪ V n , E 1 ∪ E 2 ∪ E 3 ) wie folgt: Jede Menge V i mit (1 ≤ i ≤ n) enthält m Knoten {p ik : 1 ≤ k ≤ m} und n · m Knoten {v ijk : 1 ≤ j ≤ n, 1 ≤ k ≤ m}. Jeder Knoten p ik repräsentiert die Position i auf Maschine k. Jeder Knoten v ijk repräsentiert die Verplanung von Job j auf Position i auf Maschine k. Die Kantenmenge E 1 enthält alle Kanten von s zu einem p-Knoten: E 1 = {sp ik : 1 ≤ i ≤ n, 1 ≤ k ≤ m}. Damit hat s n · m ausgehende Kanten. Die Menge E 2 enthält Kanten von p-Knoten zu v-Knoten: E 2 = {p ik v ijk : 1 ≤ i,j ≤ n, 1 ≤ k ≤ m}. Jeder p-Knoten hat somit n ausgehende Kanten. Jeder v-Knoten hat genau eine ausgehende Kante, die zu s führt. Diese Menge von Kanten ist in E 3 enthalten: E 3 = {v ijk s : 1 ≤ i,j ≤ n, 1 ≤ k ≤ m}. Abbildung 3.6 zeigt den Graph für n = 3. Dabei sind , aus Gründen einer besseren Übersichtlichkeit, aus der Menge E 3 nur zwei Kanten abgebildet. Der „Aussenring“ enthält alle v-Knoten. Man denke sich von jedem dieser Knoten eine Kante zum Knoten s.

Eine „Ameise“ beginnt die Wegkonstruktion am Knoten s, den die „Ameise“ bei der Konstruktion insgesamt n mal besuchen wird. Im Knoten s bestimmt die „Ameise“

Abbildung 3.6: Graph für Mehrmaschinenproblem - 2. Möglichkeit

die Maschine k für die Verplanung des nächsten Jobs. Da die „Ameise“ die von ihr bereits verplanten Jobs speichert, kann sie die Position i auf Maschine k für den nächsten zu verplanenden Job bestimmen. Anhand dieser Entscheidung, fügt die Ameise die Kante sp ik ∈ E 1 dem Weg hinzu und beﬁndet sich nun auf dem Kno- ten p ik . Dort triﬀt sie, im Sinne der ACO-Metaheuristik, auf Basis der gegebenen

3.4 Anwendung der ACO-Metaheuristik auf das P m |s ij |Σw j T j -Problem 37

lokalen Heuristik und Pheromonwerten eine Entscheidung für den nächsten Job j, der auf Maschine k auf Position i verplant werden soll. Sie wählt aufgrund der Entscheidung die Kante p ik v ijk ∈ E 2 aus und beﬁndet sich nun auf dem Knoten v ijk . Von dort kehrt sie über die einzige ausgehende Kante v ijk s zum Knoten s zurück. Die Konstruktion ist beendet, wenn die „Ameise“ n Jobs verplant hat. Der Weg enthält dann exakt 3n − 1 Kanten, die zwischen den Mengen E 1 , E 2 und E 3 alternieren. Der in Abbildung 3.6 markierte Weg repräsentiert wieder die Verplanung (in dieser Reihenfolge) von Job 3 auf Maschine 1, Job 1 auf Maschine 2 und Job 2 auf Maschine 1. Die Kanten des Weges sind durchnummeriert.

Der Graph enthält, wie auch der Graph aus der zuvor vorgestellten Konstruktion m · n ² Kanten, denen ein Pheromonwert τ ijk zugeordnet ist. Die höchste Position eines verplanten Jobs auf einer Maschine ist aber bei Verteilung der Jobs auf die Maschinen kleiner als n. Bei gleichmäßiger Verteilung der Jobs auf die Maschinen sind pro Maschine n/m Jobs verplant. Bei moderater Streuung der Bearbeitungszeiten und Umrüstzeiten wird die höchste Position kaum größer als n/m sein. Das bedeutet, dass die Wahrscheinlichkeit, dass eine Kante sp ik mit i > n/m von einer „Ameise“ selektiert wird, mit steigendem i sehr stark abnimmt. Die Anzahl der Pheromonwerte, die eine „Ameise“ tatsächlich zur Konstruktion eines Weges betrachtet ist deshalb wesentlich geringer als m · n ² . Bei gleichmäßiger Verteilung der Jobs auf die Maschinen ist sie: m·n ² /m = n ² . Das bedeutet, es werden weniger Pheromonwerte für die Wegkonstruktion genutzt als beim vorher vorgestellten Graphen.

Es wurden zwei Möglichkeiten vorgestellt, für ein gegebenes Ablaufplanungsproblem mit parallelen Maschinen einen Graphen zu konstruieren, der als Eingabe für die ACO-Metaheuristik verwendet werden kann. Beide Konstruktionen unterscheiden sich in der Interpretation des i-Indexes der Pheromonwerte τ ijk . Die erste Konstruktion ist eine einfache und naheliegende Erweiterung der Konstruktion, die in [Bau99] für Einzelmaschinenprobleme gezeigt wird. Hier wird i als Position des Jobs j in der Auswahlliste interpretiert. Bei der zweiten vorgestellten Konstruktion repräsentiert i die Position des Jobs auf Maschine k. Beide Interpretationen sind plausibel und

38 3 Konzept zur Lösung des Problems

führen zu gültigen Problembeschreibungen für die ACO-Metaheuristik. Es werden daher beide Konstruktionen, d.h. beide Interpretationen der Pheromonwerte, getestet und gegenübergestellt.

Bei Verwendung maschinenunabhängiger Pheromonwerte wird in beiden vorgestellten Konstruktionen m = 1 gesetzt. Im Fall m = 1 hat die „Ameise“ im Knoten s keinen Entscheidungsspielraum. Beﬁndet sich die „Ameise“ das i-te mal im Knoten s, wurden bis dahin i − 1 Jobs verplant. Die „Ameise“ muss dann den Weg zum Knoten p i1 fortsetzen, um den nächsten Job auf Position i zu verplanen. Da die Ameise im Knoten s keine Entscheidungen mehr triﬀt, kann dieser Knoten auch übergangen werden. Die „Ameise“ kann ihren Weg von einem Knoten v ij1 ∈ V i direkt zum Knoten p (i+1)1 fortsetzen. D.h. wir ersetzen E 3 durch 3 = {v ij1 p (i+1)1 : 1 ≤ i < n, 1 ≤ j ≤ n}. Der daraus resultierende Graph ent- E

spricht dem Graph aus der ersten Konstruktion. Das bedeutet, im Fall m = 1 fallen beide Konstruktionen zusammen.

3.4.3 Anwendung der ACO-Metaheuristik auf das

P m |s ij |Σw j T j -Problem

Die Abbildungen 3.7 und 3.8 zeigen das Konzept für die Anwendung der ACO-Metaheuristik auf das P m |s ij |Σw j T j -Problem. Die einzelnen Schritte des Verfahrens werden im Folgenden erläutert.

Das Konzept soll ermöglichen, die vorgestellten Interpretationen der Pheromonwerte miteinander zu vergleichen. So wird ein boolescher Parameter S τ k eingeführt, welcher bestimmt, ob maschinenabhängige Pheromonwerte (vgl. [Mön08]) verwendet werden sollen oder nicht. Ein weiterer boolescher Parameter S P os bestimmt die Interpretation des i-Index der Pheromonwerte τ ijk . Bei S P os = f alse wird der Index im Sinne von [Mön08] interpretiert (Position des Jobs auf Maschine k). Damit wird der zweite im letzten Abschnitt vorgestellte Graph benutzt. Bei S P os = true wird die Interpretation des Indexes laut der ersten vorgestellten Konstruktion benutzt.

3.4 Anwendung der ACO-Metaheuristik auf das P m |s ij |Σw j T j -Problem 39

Die Verwendung der in [Mer00] vorgestellten Summationsregel soll einstellbar sein, um deren Einﬂuss auf die Güte des Verfahrens testen zu können. Es wird deshalb ein weiterer boolescher Parameter S Σ deﬁniert, der die Verwendung der Summationsregel (S Σ = true) bestimmt.

Ein vierter boolescher Parameter S M axM in bestimmt, ob die Pheromonwerte im Sinne von MMAS mit Hilfe der Formeln (3.11) und (3.12) begrenzt werden sollen. Damit wird der Test des vorgestellten MMAS-Verfahrens ermöglicht. Eine Begrenzung der Pheromonwerte nach unten ﬁndet auch bei S M axM in = f alse statt, dann jedoch durch die einfachere Formel: τ ≥ τ 0 /5. Diese Begrenzung der Pheromonwerte nach unten wird in [Lia07] vorgeschlagen.

1: initialize()

2: Schedule GB ← Schedule Init

3: while (!exitCondition())

3.1 Schedule IB ← Schedule Init 3.2 for i=1 to antCount 3.2.1 Schedule ← Ant_ConstructSolution() 3.2.2 processLocalOptimization(Schedule) 3.2.3 Schedule IB ← best(Schedule IB , Schedule) 3.3 Schedule GB ← best(Schedule GB , Schedule IB ) 3.4 processOf f lineP heromoneU pdate(Schedule IB/GB )

4: return Schedule GB

1: Schedule S ← ∅

2: while(J s = ∅)

2.1: nextM achine ← determineN extM achine(S) 2.2: nextJob ← determineN extJob(S, nextM achine) 2.3: scheduleN extJob(S, nextM achine, nextJob) 2.4: processOnlineP heromonU pdate(nextM achine, nextJob, jobP os)

3: return S

Relative Gütefunktion: Zur Initialisierung und Aktualisierung der Pheromonwerte wird normalerweise die Güte der gefundenen Lösung benutzt. Im hier besprochenen Problem wird die Güte L(S) eines gefundenen Ablaufplanes S mit L(S) = T W T (S) berechnet werden. Die totale gewichtete Verspätung eines Ablaufplanes ist aber sehr stark von der Enge der Fertigstellungszeiten der gegebenen Probleminstanz abhängig. Für die Testinstanzen, die in Kapitel 5 vorgestellt werden, unterscheiden sich die Werte der ermittelten Ablaufpläne mitunter um den Faktor 10 ⁶ . Dadurch unterscheiden sich die Pheromonwerte je nach gegebener Probleminstanz erheblich, wodurch die Verwendung einzelner Parameter für die unterschiedlichen Probleminstanzen nicht mehr vergleichbar ist. Der Vorschlag ist deshalb, zur Initialisierung und Aktualisierung der Pheromonwerte nicht die absolute Güte der gefunden Lösung zu benutzen, sondern die relative Verbesserung der gefunden Lösung S bezüglich der Anfangslösung S init :

3.4 Anwendung der ACO-Metaheuristik auf das P m |s ij |Σw j T j -Problem 41

Es folgt die Beschreibung der einzelnen Schritte des Verfahrens. Bei der Beschreibung der Schritte werden weitere Parameter genannt, mit denen sich das Verhalten des Verfahrens beeinﬂussen lässt. Die einzelnen Parameter werden in Tabelle 3.1 noch einmal aufgelistet.

initialize (ACO 1): Eine erste Lösung Schedule Init wird mit Hilfe der ATCS-Heuristik konstruiert. Die Parameter k 1 und k 2 der ATCS-Regel werden durch eine Gitterpunktanalyse bestimmt. Dabei wird für beide Parameter das Intervall [0.5,6.5] in 13 Schritten getestet. Die ermittelten k 1 und k 2 werden gespeichert und auch zur Bestimmung der lokalen Heuristik η (siehe determineN extJob) verwendet.

Der ermittelte Ablaufplan wird noch optimiert (siehe processLocalOptimzation). Gilt nach der Optimierung T W T (S init ) = 0 wird das Verfahren abgebrochen und die gefundene, optimale Lösung ausgegeben. Andernfalls erfolgt die Initialisierung des Pheromonfeldes.

Im Fall S M axM in = f alse wird der initiale Pheromonwert τ 0 durch folgende Formel bestimmt:

wobei K ein Parameter ist, der in [Lia07] eingeführt wurde. Durch Anwendung von Formel (3.17) vereinfacht sich jedoch die Berechnung der initialen Pheromonwerte auf:

τ 0 = K. (3.19)

Im Fall S M axM in = true erfolgt die Berechnung von τ min und τ max und das Setzen der initialen Pheromonwerte auf τ max (vgl. Abschnitt 3.3.5).

42 3 Konzept zur Lösung des Problems

exitCondition (ACO 3): Das Verfahren wird beendet, wenn eines der drei Kriterien erfüllt ist:

• es wurde ein Ablaufplan S gefunden mit T W T (S) = 0,

• es wurden insgesamt I max Iterationen durchgeführt,

• die letzten I woi Iterationen haben keine Verbesserung ergeben.

Dabei sind I max und I woi Parameter des Verfahrens.

antCount (ACO 3.2): Die Anzahl der Ameisen pro Iteration wird mit folgender Formel bestimmt:

Die Formel stellt das geometrische Mittel aus der Anzahl der Jobs n und der Anzahl der Jobs pro Maschine n/m dar. Dadurch ist die Anzahl der Ameisen abhängig von der Größe der Probleminstanz, welche durch die Anzahl der Jobs und Anzahl der Maschinen bestimmt ist. Durch den Parameter antF actor kann dann die Anzahl der Ameisen, unabhängig von der Größe der Probleminstanz, skaliert werden.

processLocalOptimization (ACO 3.2.2): Als lokale Optimierung wird die in [Mön08] und [Meh98] beschriebene Dekompositionsheuristik verwendet. Für eine Jobsequenz einer Maschine werden die ersten λ Jobs permutiert. Von der besten gefundenen Sequenz werden die ersten α Jobs ﬁxiert und das Verfahren auf die nächsten λ Jobs angewendet. Das Verfahren wird solange wiederholt, bis keine Verbesserung der Lösungsgüte mehr erreicht wird. Bei der Implementierung des Ver- fahrens wurde λ = 5 und α = 2 gesetzt.

3.4 Anwendung der ACO-Metaheuristik auf das P m |s ij |Σw j T j -Problem 43

processOﬄinePheromoneUpdate (ACO 3.4): Die Pheromone werden mit Hilfe der Formel (3.7) aktualisiert. Es trägt nur die „Ameise“ mit der besten Lösung zur Aktualisierung der Pheromonwerte bei. Dabei bestimmt der Parameter λ, mit welcher Wahrscheinlichkeit die global beste Lösung bzw. die beste Lösung der aktuellen Iteration (1 − λ) verwendet wird.

determineNextMachine (Ant 2.1): Mit einer Wahrscheinlichkeit von ζ wird diejenige Maschine mit dem aktuell geringsten Verfügbarkeitszeitpunkt gewählt. Mit einer Wahrscheinlichkeit von 1 − ζ wird eine beliebige Maschine selektiert.

determineNextJob (Ant 2.2): Je nach Wert des Schalters S Σ wird mit Hilfe der Formeln (3.6) und (3.9) bzw. den Formeln (3.14) und (3.15) aus der Menge J S der nächste zu verplanende Job für die zuvor selektierte Maschine ermittelt. Als lokale Heuristik wird die ATCS-Regel verwendet. Dabei werden für die Parameter k 1 und k 2 der ATCS-Regel die gleichen Werte verwendet, die bei der Initialisierung durch die Gitterpunktanalyse gefunden wurden.

scheduleNextJob (Ant 2.3): Der ermittelte Job wird der Jobsequenz der selektierten Maschine hinzugefügt.

processOnlinePheromonUpdate (Ant 2.4): In diesem Schritt erfolgt die lokale Verdunstung der Pheromonwerte nach Formel (3.10). Dabei ist θ ein einstellbarer Parameter des Verfahrens.

44 3 Konzept zur Lösung des Problems

4 Implementierung

Die in Kapitel 3 vorgestellten Verfahren wurden in C++ implementiert. In diesem Kapitel soll die Implementierung erläutert werden. Es erfolgt die Beschreibung der erstellten Klassen und Programme.

4.1 Repräsentation von Probleminstanz und Problemlösung

Abbildung 4.1 zeigt die Klassen ProblemInstance, InstanceGenerator und Schedule. Die Klasse ProblemInstance repräsentiert eine Probleminstanz, wie sie in Kapitel 2 eingeführt wurde. Eine Instanz der Klasse ProblemInstance wird durch Angabe der Jobanzahl und Anzahl der Maschinen initialisiert. Es stehen Methoden zum Setzen und Auslesen von Bearbeitungszeiten, Fertigstellungszeiten, Gewichten und Rüstzeiten der Jobs zur Verfügung. Die Klasse InstanceGenerator stellt zwei Methoden mit dem Namen createInstance und unterschiedlichen Signaturen zur Verfügung, um Instanzen der Klasse InstanceGenerator zu erzeugen. Die erste Methode liest Testdaten aus einer Datei ein. Die zweite Methode generiert eine neue Instanz aus den in Tabelle 4.1 genannten Parametern. Diese Methode wurde auch verwendet, um die Testinstanzen nach dem Testschema zu erzeugen, welches in Kapitel 5 vorgestellt wird.

Die Klasse Schedule repräsentiert einen Ablaufplan für eine gegeben Probleminstanz und somit das Ergebnis der hier vorgestellten Verfahren. Die Klasse verwaltet für jede Maschine eine Liste, welche die auf dieser Maschine verplanten Jobs enthält und eine Liste aller noch nicht verplanten Jobs J s (vgl. Kapitel 2). Die Metho- de schedule(machine, job) wird verwendet, um einen noch nicht verplanten Job auf

eine der Maschinen zu verplanen. Mit allen weiteren in Abbildung 4.1 gezeigten Methoden lassen sich Eigenschaften des Ablaufplanes bestimmen. Insbesondere liefert getTotalWeightedTardiness() die totale gewichtete Verspätung T W T des Ablaufpla- nes und damit das Optimierungsziel.

4.2 Implementierung der ATCS-Regel 47

Tabelle 4.1: InstanceGenerator::createInstance() - Parameter

4.2 Implementierung der ATCS-Regel

Die Klasse ATCS implementiert die in Abschnitt 3.1 vorgestellte ATCS-Regel. Mit der Methode calculateATCSIndex() kann der ATCS-Index nach Formel (3.4) für einen gegebenen Job auf einer Maschine bestimmt werden. Diese Methode wird auch von der Methode createSchedule(ProblemInstance, k1, k2) verwendet, die den in Abbildung 3.1 gezeigten Algorithmus implementiert. Der Methode werden neben der Probleminstanz die beiden Parameter k 1 und k 2 aus Formel (3.4) übergeben, die für die Bestimmung des ATCS-Indexes benutzt werden sollen. Dagegen werden bei der Methode createSchedule(ProblemInstance, minK, maxK, count, k1, k2) die Parameter k 1 und k 2 durch eine Gitterpunktananlyse bestimmt. Beide Parameter werden im Intervall [minK, maxK] in count Schritten variiert. Die beste Kombination der Parameter wird zurückgeliefert.

Die vier in Abschnitt 3.2 vorgestellten Kostenfunktionen wurden in den Klassen ATCS1, ATCS2, ATCS3 und ATCS4 implementiert und durch Anwendung des „Strategy“-Entwurfsmusters (siehe [Gam95]) an die Klasse ATCS gebunden.

Zum Test der Implementierung wurde das Programm ATCSTest erstellt. Dem Programm wird der Dateiname einer Testinstanz und die gewünschte Maschinenanzahl übergeben. Das Programm ruft dann für jede der vier implementierten Kostenfunktionen die in Listing 4.1 gezeigte Funktion auf. Als Ergebnis liefert ATCSTest für jede der vier Kostenfunktionen die totale gewichtete Verspätung des ermittelten Ablaufplanes sowie die durch die Gitterpunktanalyse gefundenen Parameter k1 und k2, mit denen der Ablaufplan ermittelt wurde.

4.3 Implementierung der ACO-Metaheuristik 49

4.3 Implementierung der ACO-Metaheuristik

Abbildung 4.3 zeigt die Klassen ACO und Ant, mit denen das in Abschnitt 3.4 vorgestellte Verfahren implementiert ist. Die dort in den Abbildungen 3.7 und 3.8 gezeigten Algorithmen sind in den Methoden ACO::createSchedule() und Ant::build() umgesetzt.

50 4 Implementierung

Weitere Methoden der beiden Klassen implementieren die in Abschnitt 3.4 diskutierten Einzelschritte der Algorithmen. Die in Tabelle 3.1 aufgelisteten Parameter des Verfahrens werden durch Variablen der Klasse ACO implementiert. Die Klasse verfügt über entsprechende Methoden zum Setzen und Auslesen dieser Parameter.

Zum Testen des Verfahrens wurde das Programm ACOTest erstellt. Das Programm erwartet als Eingabe Dateinamen einer Probleminstanz, die Anzahl der Maschinen sowie Werte für alle in Tabelle 3.1 gelisteten Parameter. Als Ergebnis liefert das Programm die totale gewichtete Verspätung des initialen Ablaufplans S init und der durch das Verfahren gefundenen Lösung S best , die Anzahl der benötigten Iterationen sowie die benötigte Zeit in Sekunden. Listing 4.2 zeigt den Aufruf und die Ausgabe des Programms.

5 Leistungsbewertung

In diesem Kapitel werden die Ergebnisse der Tests der in Kapitel 3 erläuterten Verfahren vorgestellt. Für den Test der Verfahren wurden 1680 Probleminstanzen anhand des in Tabelle 5.1 gezeigten Testschemas erstellt. Das Testschema variiert die Probleminstanzen in der Enge der Fertigstellungstermine τ , der Spanne der Fertigstellungstermine R, dem Rüstfaktor η und der Anzahl der Maschinen. Die Idee für den Aufbau das Testschemas ist aus [Mön08] entnommen.

52 5 Leistungsbewertung

In Abschnitt 5.1 werden die in Abschnitt 3.2 beschriebenen vier Kostenfunktionen für die ATCS-Heuristik miteinander verglichen. In Abschnitt 5.2 erfolgt die Leistungsbewertung des in Abschnitt 3.4 vorgestellten Konzeptes zur Anwendung der ACO-Heuristik auf das 1|s ij |Σw j T j -Problem.

5.1 Vergleich der Kostenfunktionen für die ATCS-Heuristik

Die vier in Abschnitt 3.2 beschriebenen Kostenfunktionen für die Anwendung der ATCS-Heuristik auf das P m |s ij |Σw j T j -Problem wurden auf die generierten Testinstanzen angewendet. Jede Zeile der Tabelle 5.2 zeigt den Vergleich von je zwei der vier vorgestellten Kostenfunktionen miteinander. Dabei zeigt Spalte 2, mit wie viel Prozent der die erste Kostenfunktion (a) eine bessere Lösung als die zweite fand. Spalte 2 zeigt mit wie viel Prozent die zweite Kostenfunktion (b) besser war und Spalte 3 zeigt schließlich den prozentualen Anteil der Testinstanzen, bei denen beide verglichenen Kostenfunktionen das selbe Ergebnis erzielten.

Die Tabelle zeigt, dass mit Anwendung der Kostenfunktion cost 2 häuﬁger bessere Ergebnisse erzielt wurden als mit den anderen drei Kostenfunktionen.

5.2 Leistungsbewertung der ACO-Heuristik 53

5.2 Leistungsbewertung der ACO-Heuristik

Es folgt die Auﬂistung der Ergebnisse der Tests des in Kapitel 3 vorgestellten Verfahrens. Insgesamt wurden vier Testreihen durchgeführt. Bei der ersten Testreihe war das Ziel, sinnvolle Werte für alle Parameter für die Anwendung von ACS (S M axM in = f alse) zu bestimmen und dabei den Einﬂuss der Summationsregel (S Σ ) und maschinenabhängiger Pheromonwerte (S τ k ) auf das Ergebnis zu ermitteln. Bei der zweiten Testreihe wurde, ausgehend von den gefundenen Parameterkombinationen des ersten Tests, das Verhalten des Verfahrens im Fall S M axM in =true, d.h. bei Verwendung von MMAS untersucht. Bei der ersten und zweiten Testreihe wurde S P os = f alse gesetzt. Bei der dritten Testreihe wurde nun mit S P os = true die zweite in Kapitel 3 vorgestellte Interpretation der Pheromonwerte getestet. Bei der vierten Testreihe wurde schließlich das Verfahren auf die in [Cic03] vorgestellten Testinstanzen angewendet.

Bei allen Tests wurden, falls nicht explizit anders angegeben, folgende Parameterwerte benutzt: I max = 1000, I woi = 100, α = 1, β = 0.5.

5.2.1 Testreihe 1: S M axM in = f alse, S P os = f alse

Das Ziel der ersten Testreihe war, den Einﬂuss der Summationsregel und machinenabhängiger Pheromonwerte auf das Ergebnis des Verfahrens zu ermitteln. Außerdem sollten sinnvolle Parameterkombinationen, insbesondere für die Parameter K, antF actor, θ, ρ, ζ und λ bestimmt werden.

Für die Suche nach günstigen Parameterkombinationen wurden 27 Testinstanzen aus dem Testschema (vgl. Tabelle 5.3) ausgewählt.

Es wurden zwei Parametertests durchgeführt. Die Ergebnisse der beiden Tests sind in den Tabellen 5.4 und 5.5 dargestellt. Beide Tabellen zeigen in den ersten beiden Spalten den Wert des variierten Parameters. Die folgenden Spalten zeigen die durch- schnittliche Verbesserung, die durchschnittliche Anzahl der benötigten Iterationen

und die durchschnittliche benötigte Zeit für die gegebene Parametervariation. Die Wahl der Parameterkombinationen für den zweiten Test erfolgte auf Grundlage der Ergebnisse des ersten Tests.

Tabelle 5.4: Parametertest 1: λ = 1, S M axM in = f alse, S P os = f alse

Tabelle 5.5: Parametertest 2: ζ = 0.9, S M axM in = f alse, S P os = f alse

Bei den Parametertests wurde ein großer Einﬂuss des Parameters antF actor festgestellt. Mit antF actor = 1, d.h. mit mehr Ameisen pro Iteration wurden bessere Ergebnisse erzielt, allerdings dafür auch mehr Zeit benötigt. Bei allen anderen Parametern ist die Abhängigkeit der benötigten Zeit gegenüber dem verwendeten Wert des Parameters weit weniger ausgeprägt. Die Bestimmung der besten Parameterkonﬁgurationen erfolgte deshalb in Abhängigkeit des Parameters antF actor.

Zur Bestimmung günstiger Parameterkombinationen wurden die ermittelten Ablaufpläne für die Testinstanzen aus den beiden Parametertests nach den Parametern S Σ , S τ k , K, θ, ρ, ζ und λ gruppiert und nach der erzielten durchschnittlichen Verbesserung sortiert. Die Tabellen 5.6 und 5.7 zeigen für antF actor = 0.5 bzw. antF actor = 1 die jeweils besten fünf Ergebnisse für die vier Variationen der Parameter S Σ und S τ k . Die erste Spalte „Rang“ zeigt die Position der Parameterkombination in der sortierten Liste.

Beide Tabellen zeigen, dass mit S τ k = f alse wesentlich schlechtere Ergebnisse er-

56 5 Leistungsbewertung

zielt wurden als mit S τ k = true. Für antF actor = 0.5 (Tabelle 5.6) liegt die beste Parameterkombination für S τ k = f alse an Position 58, für antF actor = 1 (Tabelle 5.7) an Position 61. In beiden Fällen ist die durchschnittliche Verbesserung gegenüber der besten Parameterkombination deutlich schlechter.

Beide Tabellen zeigen auch, dass durch Anwendung der Summationsregel (S Σ = true) bessere Ergebisse erzielt wurden als ohne Anwendung der Summationsregel. Allerdings ist der Einﬂuss gegenüber der Verwendung maschinenabhängiger Pheromonwerte kleiner. So liegt die beste Parameterkombination mit S Σ = f alse für antF actor = 0.5 auf Position 6 und für antF actor = 1 auf Position 4.

Tabelle 5.6: beste Parameterkombinationen aus Test 1 und 2: antF actor = 0.5

5.2 Leistungsbewertung der ACO-Heuristik 57

Tabelle 5.7: beste Parameterkombinationen aus Test 1 und 2: antF actor = 1.0

Für die Anwendung auf das Testschema wurden die beiden besten Parameterkombinationen für antF actor = 0.5 und S Σ ∈ {f alse, true} aus Tabelle 5.6 ausgewählt. Maschinenunabhängige Pheromonwerte (S τ k = f alse) wurden auf Grund der Ergebnisse aus den Tabellen 5.6 und 5.7 nicht weiter untersucht. In Tabelle 5.8 sind die Ergebnisse der Anwendung der beiden Parameterkombinationen auf das Testschema dargestellt. Die Tabelle zeigt die erreichte durchschnittliche Verbesserung und die durchschnittliche benötigte Zeit für beide getesteten Parameterkombinationen in Abhängigkeit der Eigenschaften m, (τ, R) und η der Probleminstanzen.

58 5 Leistungsbewertung

S Σ f alse S Σ true

Parameter Wert Verbesserung Zeit Verbesserung Zeit

2 23.81 90 24.83 84

m

3 20.21 55 20.96 60

4 18.63 40 18.91 46

τ , R 0.30, 0.25 45.90 59 46.28 61

0.30, 0.50 72.05 49 73.64 55

0.30, 0.75 86.74 38 86.57 32

0.30, 1.00 23.90 30 23.57 30

0.20, 0.25 25.94 86 25.32 77

0.40, 0.50 58.64 62 60.90 66

0.40, 0.75 80.76 39 81.72 42

0.40, 1.00 28.99 42 7.88 43

0.50, 0.25 13.42 69 14.71 75

0.50, 0.50 32.70 75 34.61 76

0.50, 0.75 53.38 63 55.80 61

0.50, 1.00 24.68 52 5.74 64

0.60, 0.25 6.86 72 8.18 82

0.60, 0.50 11.73 70 12.83 75

0.60, 0.75 14.69 68 16.51 74

0.60, 1.00 10.04 71 0.68 64

0.70, 0.25 2.63 62 3.41 61

0.70, 0.50 3.95 64 4.52 63

0.70, 0.75 4.74 60 5.49 70

0.70, 1.00 4.30 68 5.08 69

0.80, 0.25 1.48 67 1.53 62

0.80, 0.50 1.83 63 2.07 62

0.80, 0.75 2.16 64 2.17 63

0.80, 1.00 1.81 66 2.15 65

0.90, 0.25 0.95 61 1.18 64

0.90, 0.50 0.83 63 1.17 66

0.90, 0.75 1.12 62 1.25 68

0.90, 1.00 0.97 67 1.23 67

0.25 14.43 73 14.76 74

η

0.50 19.52 62 19.69 64

0.75 24.10 59 25.15 58

1.00 25.84 53 27.05 56

Tabelle 5.8: Anwendung auf Testschema: antF actor 0.5, K 0.1, θ 0.1, ρ

0.3, ζ 0 9, λ 0 9, S τ k true, S M axM in f alse, S P os f alse

5.2 Leistungsbewertung der ACO-Heuristik 59

Die günstige Auswirkung der Summationsregel auf das Verfahren wurde durch den Test bestätigt. Die Tabelle zeigt weiterhin eine Abhängigkeit der erreichten durchschnittlichen Verbesserung von der Anzahl der Maschinen m, der Spanne der Fertigstellungstermine τ sowie dem Rüstfaktor R. Ein möglicher Grund für die Abnahme der durchschnittlichen Verbesserung bei Erhöhung von m ist die Wahl der Methode für die lokalen Optimierung des Verfahrens. Bei der verwendeten lokalen Optimierung (vgl. Abschnitt 3.4) werden die einzelnen Jobsequenzen auf den Maschinen optimiert, nicht aber die Verteilung der Jobs auf die Maschinen. Ungünstige Zuordnungen der Jobs auf die Maschinen werden durch die gewählte lokale Optimierung nicht verbessert. Ein Grund für die deutlich geringere durchschnittliche Verbesserung bei steigendem τ bzw. die höhere durchschnittliche Verbesserung bei steigendem η könnte die Abhängigkeit der Eﬀektivität der verwendeten Referenzheuristik ¹ von den genannten Eigenschaften einer Probleminstanz sein. In [Mön08] wird auf die Abhängigkeit der Eﬀektivität der ATC-Regel von der Spanne der Fertigstellungstermine hingewiesen. Es wird die schlechtere Eﬀektivität der ATC-Regel bei kleinen τ begründet. Die dort angeführten Argumente sind auch für die ATCS-Regel gültig.

5.2.2 Testreihe 2: S M axM in = true, S P os = f alse

Das Ziel der zweiten Testreihe war, mit S M axM in = true, q 0 = 0 und θ = 0 die Anwendung von MMAS zu testen. Mit ρ = 0.3, ζ = 0.9, λ = 1, S Σ = true und S τ k = true wurden Parameterwerte gewählt, die in der ersten Testreihe als günstig ermittelt und für die Anwendung des Verfahrens gegen das Testschema verwendet wurden. Der Parameter K wird bei S M axM in = true nicht benutzt, da in diesem Fall die Pheromone durch den Wert τ max initialisiert werden (vgl. Abschnitt 3.3.5).

Zunächst wurden mit einem Parametertest günstige Werte für die Parameter β, p best und δ gesucht. Tabelle 5.9 zeigt das Ergebnis des Tests. Der Aufbau der Tabelle ist analog zu den Tabellen der Parametertests aus Abschnitt 5.2.1. Insgesamt ergab

1 der ATCS-Heuristik

60 5 Leistungsbewertung

der Parametertest wesentlich schlechtere Ergebnisse als die ersten beiden Parametertests mit S M M AS = f alse der ersten Testreihe. Der Wert I woi = 100 scheint für MMAS zu klein gewählt zu sein.

Tabelle 5.9: Parametertest 3: q 0 = 0, θ = 0, ρ = 0.3, ζ = 0.9, λ = 1, S Σ = true, S τ k = true, S M axM in = true, S P os = f alse

Für die Anwendung auf das Testschema wurden die besten Werte des Parametertests gewählt. Der Parameter I woi wurde zwischen 100 und 300 variiert. Tabelle 5.10 zeigt die die Ergebnisse der Anwendung auf das Testschema.

Die Ergebnisse aus Tabelle 5.10 bestätigen die schon in der ersten Testreihe festgestellte Abhängigkeit der erzielten durchschnittlichen Verbesserung gegenüber den Eigenschaften der Probleminstanzen m, τ und η. Die Erhöhung des Paremeters I woi auf 300 hat die Leistung des Verfahrens verbessert. Allerdings wurden auch mit diesem Parameterwert die durchschnittlichen Verbesserungen aus der ersten Testreihe nicht erreicht.

5.2 Leistungsbewertung der ACO-Heuristik 61

I woi 100 I woi 300

Parameter Wert Verbesserung Zeit Verbesserung Zeit

2 15.85 40 17.66 118

m

3 12.63 26 14.75 74

4 10.64 20 12.25 56

τ , R 0.30, 0.25 32.63 35 44.89 98

0.30, 0.50 58.52 30 61.95 69

0.30, 0.75 76.54 17 79.75 51

0.30, 1.00 22.09 23 23.54 68

0.20, 0.25 18.48 47 23.94 117

0.40, 0.50 35.22 35 42.46 105

0.40, 0.75 55.59 21 59.33 64

0.40, 1.00 17.73 30 17.19 91

0.50, 0.25 9.70 45 13.72 119

0.50, 0.50 17.06 38 22.89 110

0.50, 0.75 16.44 24 17.09 71

0.50, 1.00 7.80 26 7.73 77

0.60, 0.25 5.06 38 6.22 103

0.60, 0.50 4.68 28 6.60 87

0.60, 0.75 3.40 23 3.89 68

0.60, 1.00 2.51 24 2.49 68

0.70, 0.25 1.63 31 2.34 93

0.70, 0.50 1.90 33 2.16 82

0.70, 0.75 1.67 23 1.82 69

0.70, 1.00 1.33 22 1.36 68

0.80, 0.25 0.82 31 1.16 92

0.80, 0.50 0.73 28 0.99 82

0.80, 0.75 0.71 23 0.81 66

0.80, 1.00 0.52 21 0.59 67

0.90, 0.25 0.65 35 0.84 96

0.90, 0.50 0.43 27 0.55 81

0.90, 0.75 0.31 23 0.36 70

0.90, 1.00 0.30 21 0.35 63

0.25 9.19 36 10.45 101

η

0.50 11.99 29 13.20 83

0.75 15.26 25 17.60 74

1.00 15.92 25 18.55 71

Tabelle 5.10: Anwendung auf Testschema: antF actor 1, θ 0, ρ 0.3, ζ

0.9, λ 1, q 0 0, S Σ true, S τ k true, S M axM in true, S P os f alse, p best

0.05, δ 0, β 1

62 5 Leistungsbewertung

5.2.3 Testreihe 3: S M axM in = f alse, S P os = true

Bei der ersten beiden Testreihen wurde mit S P os = f alse die Interpretation des i-Indexes der Pheromonwerte als Position des Jobs auf der ausgewählten Maschine betrachtet. Das Ziel der dritten Testreihe war es, mit S P os = true die zweite vorgestellte Interpretation des i-Indexes als Position des Jobs in der Auswahlliste zu untersuchen. Wiederum wurden zunächst günstige Kombinationen der Parameterwerte durch zwei Parametertests (vgl. Tabellen 5.12 und 5.13) gesucht. Aus Zeitmangel wurde jedoch für diese für diese Parametertests die Anzahl der verwendeten Testinstanzen weiter eingeschränkt (siehe Tabelle 5.11). In Abschnitt 3.4.2 wurden die Graphen beschrieben, die den beiden Interpretationen des i-Indexes der Pheromonwerte bei der Anwendung der ACO-Metaheuristik zugrunde liegen. Dabei wurde festgestellt, dass für S P os = f alse weniger Pheromonwerte (bzw. Kanten) zur Lösungskonstruktion verwendet werden, als für den Fall S P os = true. Aufgrund dessen wurde bei den Parametertests für S P os = true höhere Werte für den Parameter antF actor getestet.

Für die Anwendung auf das Testschema wurden die besten gefundenen Werte für die einzelnen Parameter aus den Parametertests gewählt. Der Parameter antF actor wurde in den Werten {2,5,10} variiert. Tabelle 5.14 zeigt das Ergebnis der Anwen- dung des Verfahrens auf das Testschema.

Tabelle 5.12: Parametertest 4: S Σ = true, S τ k = true, S M axM in = f alse, S P os = true

Tabelle 5.13: Parametertest 5: λ = 1, S Σ = true, S τ k = true, S M axM in = f alse, S P os = true

64 5 Leistungsbewertung

antF actor 2 antF actor 5 antF actor 10

Parameter Wert Verb. Zeit Verb. Zeit Verb. Zeit

2 23.28 74 24.25 196 24.81 376

m

3 20.37 49 21.62 125 22.62 250

4 18.40 37 19.88 96 20.79 195

τ , R 0.30, 0.25 45.99 49 49.70 139 51.43 271

0.30, 0.50 67.30 41 69.38 112 71.49 249

0.30, 0.75 85.26 25 85.83 65 86.31 122

0.30, 1.00 24.78 32 25.76 78 25.63 153

0.20, 0.25 21.85 62 26.42 169 28.81 352

0.40, 0.50 51.38 54 54.28 141 56.61 284

0.40, 0.75 76.85 36 78.34 101 79.34 200

0.40, 1.00 29.61 47 29.91 115 30.11 220

0.50, 0.25 14.26 65 16.19 172 17.53 330

0.50, 0.50 27.91 68 30.97 176 33.71 371

0.50, 0.75 49.87 70 51.52 163 53.62 303

0.50, 1.00 26.43 66 27.32 177 28.13 329

0.60, 0.25 8.58 64 9.96 185 10.76 327

0.60, 0.50 13.89 67 15.30 169 16.16 344

0.60, 0.75 16.04 67 17.40 159 18.23 302

0.60, 1.00 10.60 60 11.23 150 11.83 290

0.70, 0.25 4.77 60 5.68 171 6.05 293

0.70, 0.50 6.01 60 6.80 150 7.44 317

0.70, 0.75 6.21 59 7.02 142 7.34 307

0.70, 1.00 5.25 52 6.03 141 6.29 286

0.80, 0.25 2.32 48 2.89 124 3.08 248

0.80, 0.50 2.77 51 3.05 121 3.32 242

0.80, 0.75 2.95 49 3.15 129 3.39 238

0.80, 1.00 2.31 50 2.64 122 2.80 255

0.90, 0.25 1.54 42 1.84 120 1.95 226

0.90, 0.50 1.88 48 2.13 119 2.27 233

0.90, 0.75 1.86 48 1.96 119 2.15 252

0.90, 1.00 1.79 50 2.07 123 2.18 250

0.25 13.16 56 13.94 148 14.47 288

η

0.50 18.49 53 19.73 138 20.59 284

0.75 24.49 52 26.01 135 26.92 262

1.00 27.05 54 28.47 134 29.48 258

Tabelle 5.14: Anwendung auf Testschema: K 20, θ 0.4, ρ 0.01, ζ 0.8, λ

1, S Σ true, S τ k true, S M axM in f alse, S P os true

5.2 Leistungsbewertung der ACO-Heuristik 65

Tabelle 5.14 zeigt, dass mit antF actor = 2 und S P os=true ähnliche Ergebnisse erzielt wurden, wie mit antF actor = 0.5 und S P os = f alse (vgl. Tabelle 5.8). Mit antF actor = 5 und antF actor = 10 wurde die durchschnittliche Verbesserung weiter gesteigert. Allerdings erhöhte sich auch die durchschnittlich benötige Zeit deutlich.

5.2.4 Testreihe 4: Benchmarktest

In [Cic03] werden Ergebnisse für 120 Testinstanzen für das Einzelmaschinenproblem 1|s ij |Σw j T j vorgestellt. In [Lia07] wurden durch Verwendung der ACO-Metaheuristik für viele dieser Testinstanzen Verbesserungen erreicht. Das in dieser Arbeit vorgestellte Verfahren soll nun ebenfalls gegen die Instanzen getestet werden.

Bei dem Einzelmaschinenproblem sind beide hier vorgestellten Interpretationen der Pheromonwerte identisch. Der Parameter S P os ist somit nicht relevant ¹ . Da die Parametertests für S P os = f alse umfangreicher waren, wurden die für diesen Fall gefundenen besten Parameterwerte für den Benchmarktest benutzt. Folgende Variationen der Parameterwerte wurden getestet:

ACO 1 : antF actor = 0.5, S Σ = f alse,

ACO 2 : antF actor = 0.5, S Σ = true, ACO 3 : antF actor = 1.0, S Σ = f alse, ACO 4 : antF actor = 1.0, S Σ = true.

Die Werte für die weiteren Parameter sind (vgl. Tabelle 5.8) K = 0.1, θ = 0.1, ρ = 0.3, λ = 0.9, S M axM in = f alse und S P os = f alse.

Für 46 der 120 Testinstanzen wurden mit mindestens einer der vier Variationen Verbesserungen gegenüber den Ergebnissen aus [Cic03] und [Lia07] erzielt. Die Verbesserungen sind in den Tabellen 5.15 und 5.16 aufgelistet. In diesen beiden Tabellen

1 Ebenso der Parameter ζ und S τ k .

66 5 Leistungsbewertung

kennzeichnet die Spalte „Pos“ die Nummer der entsprechenden Probleminstanz aus den Benchmarktest, für die eine Verbesserung erzielt wurde. Die Spalte „Benchmark“ zeigt für die gegebene Probleminstanz die Ergebnisse aus [Cic03], die Spalte „ACO Lia07 “ die Ergebnisse aus [Lia07] und Spalte „AT CS“ die Ergebnisse der initialen Lösung die durch die ATCS-Heuristik bestimmt wurde. Die vier Spalten ACO 1−4 zeigen die Ergebnisse der vier oben beschriebenen Parametervariationen. Die Ergebnisse, die Verbesserungen gegenüber der in [Cic03] und [Lia07] erreichten Lösungen darstellen sind fett gedruckt. Die dazugehörigen Ablaufpläne sind im Anhang aufgelistet.

Interessant ist auch die Verteilung der gefundenen Verbesserungen auf die vier getesteten Parameterkombinationen. So wurden mit ACO 2 und ACO 4 jeweils achtzehn bessere Lösungen gefunden. Mit ACO 3 wurde nur in neun Fällen und mit ACO ¹ nur in zwei Fällen die Ergebnisse aus [Cic03] und [Lia07] übertroﬀen. Das bestätigt noch einmal der Vorteil der Verwendung der Summationsregel (S Σ = true).

Tabelle 5.15: Benchmark Vergleich - Verbesserungen (Teil 1)

5.2 Leistungsbewertung der ACO-Heuristik 67

Pos Benchmark ACO Lia07 AT CS ACO 1 ACO 2 ACO 3 ACO 4

58 55522 52752 64416 55895 55365 52140

48593

60 73328 72600 93083 80658 74918 80529

72534

61 79884 80343 85619 79533 79467 79141

78798

62 47860 46466 58220 46612 46034 45015

44781

63 78822 78081 83609 76512 76098 77079

75850

64 96378 95113 110578 98051 95640 95640

95111

65 134881 132078 143374 129885 130730 133129 130022

66 64054 63278 77284 61505 64834 60868

59998

67 34899 32315 45177 33648 30663 30567

30031

68 26404 26366 34633 23737 23956 25145

23693

70 81200 81356 86893 82256 79010 78637

78404

72 56934 54849 81588 52299 51737 49066

47842

73 36465 34082 51870 35347 30797 34470

29234

75 30980 27248 47920 29294 35269 26251

24372

77 40558 37257 58921 36675 39207 45009

34281

78 25105 24795 39961 23330 26925 28319

21755

79 125824 122051 140887 120783 120462 130161 127541

80 31844 26470 54533 31535 26192 25944

22654

82 413488 413181 420252 416521 415273 412998 413862

86 365783 365199 370195 366475 367555 363985 365008

87 403016 401535 412161 407700 401416 407408 403187

89 416916 412359 420845 417368 411434 416936 415451

101 355822 355372 362081 360238 355131 356651 356930

102 496131 495980 497759 495583 495146 496410 494378

104 362008 360756 364629 360788 360788 360614 359485

105 456364 454890 462073 456051 453282 455965 450806

108 468111 466063 475931 467680 464658 466646 466939

110 421282 421060 425926 419282 418984 420249 419596

113 263200 262367 268791 263158 261789 262025 265229

120 399700 398590 410253 407654 398518 406300 405110

Tabelle 5 16: Benchmark Vergleich - Verbesserungen (Teil 2)

6 Zusammenfassung

Das Ziel dieser Arbeit war, die ACO-Metaheuristik auf das Ablaufplanungsproblem P m |s ij |Σw j T j anzuwenden. In [Lia07] wird die Anwendung der ACO-Metaheuristik auf das analoge Einzelmaschinenproblem beschrieben. Dieser Artikel war Ausgangspunkt dieser Arbeit.

In [Lia07] wird für die Pheromonwerte die Position-Maschine-Interpretation benutzt. Diese Interpretation wurde auch in dieser Arbeit verwendet. Dabei wurde gezeigt, dass bei Mehrmaschinenproblemen zwei verschiedene Interpretationen der Position existieren. Das erstellte Verfahren unterstützt beide Interpretationen.

Die Anwendung der ACO-Metaheuristik erfordert die Beschreibung des Problems als Suche von kürzesten Wegen in einem gewichteten Graphen. In [Bau99] werden Konstruktionen eines Graphen für Einzelmaschinenprobleme vorgestellt. Auf Basis dieser Arbeit wurden Konstruktionen für das Mehrmaschinenproblem erarbeitet.

Bei dem Konzept für das Verfahren wurden Ideen aus der Literatur, wie die Summationsregel, berücksichtigt. Im Vergleich zu anderen in der Literatur vorgestellten Verfahren wurden die durch die Ameisen gefundenen Lösungen nicht über ihre absolute Güte, sondern über ihre relative Güte gegenüber der initialen Lösung bewertet.

Die Leistungsbewertung des Verfahrens hat gezeigt, dass durch die Anwendung der ACO-Metaheuristik zum Teil deutlich bessere Lösungen gefunden werden können als mit der ATCS-Heuristik, die als Referenz diente. Es wurde festgestellt, dass die Verwendung maschinenabhängiger Pheromonwerte und der Summationsregel die Leistung deutlich steigert. Die Auswertungen der Tests zeigen aber auch, dass

70 6 Zusammenfassung

die erzielten Verbesserungen mit Anzahl der Maschinen abnehmen. Eine Ursache dafür kann sein, dass die verwendete lokale Optimierung die Reihenfolge der Jobs auf den Maschinen, jedoch nicht die Verteilung der Jobs zwischen den Maschinen optimiert.´Diese Tatsache könnte ein Ansatzpunkt für weitere Verbesserungen des Verfahrens sein.

Zum Schluss wurde das Verfahren gegen die in [Cic03] vorgestellten Benchmarktests angewendet. Es wurden zum Teil bessere Ergebnisse gefunden als in [Cic03] und [Lia07]. Damit ist gezeigt, dass das in dieser Arbeit vorgestellte Verfahren mit modernen Verfahren zur Lösung von Ablaufplanungsproblemen vergleichbar ist.

Literaturverzeichnis

[Arn08] Arnaout, Jean-Paul; Musa, Rami und Rabadi, Ghaith: Ant Colony Optimization Algorithm to Parallel Machine Scheduling Problem with Setups. 4th IEEE Conference on Automization Science and Engineering Key Bridge Marriott, Washington DC, USA (2008)

[Bau99] Bauer, Andreas; Bullnheimer, Bernd; Hartl, Richard F. und Strauß, Christine: Applying Ant Colony Optimization to solve the Single Machine Total Tardiness Problem (1999), URL http://epub.wu-wien.ac.at/dyn/virlib/wp/eng/mediate/ epub-wu-01_1dd.pdf?ID=epub-wu-01_1dd

[Bes00] den Besten, Matthijs; Stützle, Thomas und Dorigo, Marco: Ant Colony Optimization for the Total Weighted Tardiness Problem (2000):S. 611-620

[Bul97] Bullnheimer, Bernd; Hartl, Richard F. und Strauß, Christine: A New Rank Based Version of the Ant System - A Computational Study. Central European Journal for Operations Research and Economics (1997), Bd. 7:S. 25-38

[Cic03] Cicirello, Vincent A.: Weighted Tardiness Scheduling with Sequence-Dependent Setups: A Benchmark Library, Techn. Ber., Intelligent Coordination and Logistics Laboratory The Robotics Institute Carnegie Mellon University Pittsburgh, Pennsylvania 15213 (2003)

[Dor92] Dorigo, Marco: Optimization, Learning and Natural Algorithms, Disser- tation, Politecnico di Milano (1992)

72 Literaturverzeichnis

[Dor96] Dorigo, Marco und Gambardella, Luca Maria: Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation (1996), Bd. 1:S. 53-66

[Dor99] Dorigo, Marco und Caro, Gianni Di: The Ant Colony Optimization Meta-Heuristic (1999)

[Gam95] Gamma, Erich; Helm, Richard; Johnson, Ralph und Vlis- John: Addison-Wesley Professional Design Patterns, sides,

(1995), URL http://www.amazon.ca/exec/obidos/redirect?tag=

citeulike09-20\&ampandpath=ASIN/0201633612

[Gos89] Goss, S.; Aron, S.; Deneubourg, J. und Pasteels, J.: Self-organized shortcuts in the Argentine ant. Naturwissenschaften (1989), Bd. 76(12):S. 579-581, URL http://dx.doi.org/10.1007/BF00462870

[Gra79] Graham, R. L; Lawler, E. L.; Lenstra, J. K. und Rinnooy, A. H. G.: Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of discrete Mathematics (1979), Bd. 5:S. 287-326

[Gra02] Gravel, Marc; Price, Wilson L. und Gagne, Caroline: Scheduling continuous casting of aluminum using a multiple objective ant colony optimization metaheuristic. European Journal of Operational Research (2002), Bd. 143(1):S. 218-229, URL http://ideas.repec.org/a/eee/ejores/

v143y2002i1p218-229.html

[Hol05] Holthaus, O. und Rajendran, C.: A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weightd tardiness of jobs. Journal of the Operational Research Society (2005), Bd. 56:S. 947-953

[Hor00] Horng, Shwu-Min; Fowler, John W. und Cochran, Jeﬀery K.: A genetic algorithm approach to manage ion implantation processes in wafer fabrication. IJMTM (2000), Bd. 1(2/3):S. 156-172, URL http://dblp.

uni-trier.de/db/journals/ijmtm/ijmtm1.html#HorngFC00

Literaturverzeichnis 73

[Lia07] Liao, Ching-Jong und Juan, Hsiao-Chien: An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups. Computers & Operations Research (2007), Bd. 34:S. 1899-1909

[Meh98] Mehta, V.S. und Uzsoy, R.: Minimizing total tardiness on a batch processing machine with incompatible job families. IIE Transactions (1998), Bd. 30:S. 165-178

[Mer00] Merkle, Daniel und Middendorf, Martin: An Ant Algorithm with a New Pheromone Evaluation Rule for Total Tardiness Problems, Dissertation, London, UK (2000)

[Mön08] Mönch, Lars: Heuristics to Minimize Total Weighted Tardiness of Jobs on Unrelated Parallel Machines. 4th IEEE Conference on Automation Science and Engineering, Key Bridge Marriott, Washington DC, USA (2008)

[Mön09] Mönch, Lars: Entscheidungsmethoden in unternehmensweiten Softwaresystemen, Fernkurs FernUniversität Hagen (2009)

[Pfu08] Pfund, Michele; Fowler, John W.; Gadkari, Amit und Chen, Yan: Scheduling jobs on parallel machines with setup times and ready times. Comput. Ind. Eng. (2008), Bd. 54(4):S. 764-782

[Pin01] Pinedo, Michael: Scheduling:Theory, Algorithms, and Systems, 978-0130281388, Prentice Hall (2001)

[Rag09] Raghavan, N.R.Srinivasa und M.Venkataramana: Parallel processor scheduling for minimizing total weighted tardiness using ant colony optimization. The International Journal of Advanced Manufacturing Technology (2009), Bd. 41:S. 986-996

[Stü00] Stützle, Thomas und Hoos, Holger: Max-Min Ant System. Future Generation Computer Systems (2000), Bd. 16:S. 889-914

[Zho07] Zhou, Hong; Li, Zhengdao und Wu, Xuejing: Scheduling Unrelated Par- allel Machine to Minimize Total Weighted Tardiness Using Ant Colony

74 Literaturverzeichnis

Optimization , in: Automation and Logistics, IEEE International Confe-

rence , 132-136

Abbildungsverzeichnis

2.1 Gantt-Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.1 Algorithmus ATCS . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Algorithmus AS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 Graph für Einzelmaschinenproblem - 1. Möglichkeit . . . . . . . . . 31 3.4 Graph für Einzelmaschinenproblem - 2. Möglichkeit . . . . . . . . . 32 3.5 Graph für Mehrmaschinenproblem - 1. Möglichkeit . . . . . . . . . 34 3.6 Graph für Mehrmaschinenproblem - 2. Möglichkeit . . . . . . . . . 36 3.7 Algorithmus ACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.8 Algorithmus Ant_ConstructSolution . . . . . . . . . . . . . . . . . 40

4.1 UML: ProblemInstance, Schedule . . . . . . . . . . . . . . . . . . . 46 4.2 UML: ATCS-Heuristik . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3 UML: ACO-Heuristik . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Tabellenverzeichnis

2.1 Auftragsliste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Beispiel Probleminstanz . . . . . . . . . . . . . . . . . . . . . . . . 6

3.1 Parameter des ACO-Verfahrens . . . . . . . . . . . . . . . . . . . . 44

4.1 InstanceGenerator::createInstance() - Parameter . . . . . . . . . . . 47

5.1 Testschema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.2 Vergleich - ATCS Kostenfunktionen . . . . . . . . . . . . . . . . . . 52 5.3 Testinstanzen für Parametertest 1, 2 und 3 . . . . . . . . . . . . . . 54 5.4 Parametertest 1: λ = 1, S M axM in = f alse, S P os = f alse . . . . . . . 54 5.5 Parametertest 2: ζ = 0.9, S M axM in = f alse, S P os = f alse . . . . . . 55 5.6 beste Parameterkombinationen aus Test 1 und 2: antF actor = 0.5 . 56 5.7 beste Parameterkombinationen aus Test 1 und 2: antF actor = 1.0 . 57 5.8 Anwendung auf Testschema: antF actor = 0.5, K = 0.1, θ = 0.1, ρ = 0.3, ζ = 0.9, λ = 0.9, S τ k = true, S M axM in = f alse, S P os = f alse . . . 58 5.9 Parametertest 3: q 0 = 0, θ = 0, ρ = 0.3, ζ = 0.9, λ = 1, S Σ = true, S τ k = true, S M axM in = true, S P os = f alse . . . . . . . . . . . . 60 5.10 Anwendung auf Testschema: antF actor = 1, θ = 0, ρ = 0.3, ζ = 0.9, λ = 1, q 0 = 0, S Σ = true, S τ k = true, S M axM in = true, S P os = f alse, p best = 0.05, δ = 0, β = 1 . . . . . . . . . . . . . . . . . . . . . 61 5.11 Testinstanzen für Parametertest 4 und 5 . . . . . . . . . . . . . . . 62 5.12 Parametertest 4: S Σ = true, S τ k = true, S M axM in = f alse, S P os = true 63 5.13 Parametertest 5: λ = 1, S Σ = true, S τ k = true, S M axM in = f alse, S P os = true . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

78 Tabellenverzeichnis

5.14 Anwendung auf Testschema: K 20, θ 0.4, ρ 0.01, ζ 0.8, λ

1, S Σ true, S τ k true, S M axM in f alse, S P os true 64

5.15 Benchmark Vergleich - Verbesserungen (Teil 1) 66

5.16 Benchmark Vergleich - Verbesserungen (Teil 2) 67

B.1 Dateiformat - atcs dat 83

B 2 Dateiformat - aco dat 84

B Dateiformate der Testdaten

B.1 ATCS - Vergleich der Kostenfunktionen

84 B Dateiformate der Testdaten

B.2 ACO - Parametertest

Tabelle B.2: Dateiformat - aco*.dat

C Benchmarktest - Verbesserungen

Abschnitt beschreibt die Anwendung des in dieser Arbeit diskutierten Verfahrens auf die in [Cic03] vorgestellten Probleminstanzen. Dabei wurden für 46 der 120 Probleminstanzen Ablaufpläne gefunden, die die Ergebnisse aus [Cic03] und [Lia07] verbessern (vgl. Tabellen 5.15, 5.16). Es folgt die Auﬂistung dieser Ablaufpläne.

Für jeden Ablaufplan ist jeweils in der ersten Zeile der Name der entsprechenden Probleminstanz (vgl. [Cic03]), die verwendeten Werte für die Parameter antF actor und S Σ , die totale gewichtete Verspätung T W T und die benötigte Zeit für das Ermitteln des Ablaufplanes dargestellt. Der Ablaufplan wird darauf folgend in einer 4 × 15-Matrix dargestellt. Dabei repräsentiert der Wert der i-ten Zeile und j-ten Spalte die Jobnummer an Position 15(i − 1) + j des Ablaufplanes (1 ≤ i ≤ 4,1≤ j ≤ 15).

wt_sds_9: antF actor = 1, S Σ = true, T W T = 7331, Zeit = 642 16 1 47 25 3 13 5 56 14 45 57 15 42 17 50 2 12 8 58 11 7 20 34 59 52 26 23 51 48 10 54 41 33 21 6 40 28 9 29 36 53 38 43 49 39 46 4 24 32 18 22 37 44 31 55 30 60 19 27 35

wt_sds_24: antF actor = 0.5, S Σ = true, T W T = 1407, Zeit = 161 59 11 58 38 43 6 3 22 39 29 4 36 27 17 2 15 37 60 46 13 23 44 54 33 53 9 14 55 5 56 26 24 49 45 35 31 10 42 32 19 40 20 51 18 34 7 16 12 57 48 52 30 41 21 50 47 1 28 8 25

86 C Benchmarktest - Verbesserungen

wt_sds_27: antF actor = 1, S Σ = true, T W T = 69, Zeit = 597 33 7 23 12 8 32 52 44 54 16 38 59 24 43 53 40 35 46 20 60 22 9 37 45 39 42 21 4 17 18 30 2 57 50 6 31 55 41 27 19 14 5 51 15 34 29 26 48 1 49 58 36 56 10 28 47 25 11 3 13

wt_sds_28: antF actor = 0.5, S Σ = true, T W T = 0, Zeit = 32 12 49 11 46 27 31 1 35 26 17 3 53 47 23 14 24 18 33 54 52 37 36 19 10 25 51 40 32 41 45 30 38 6 39 57 4 55 16 44 9 59 28 15 7 13 20 48 50 2 43 22 21 8 5 42 34 58 56 29 60

wt_sds_28: antF actor = 1, S Σ = f alse, T W T = 0, Zeit = 114 12 28 23 31 1 3 53 47 11 46 27 33 49 54 17 36 19 10 25 16 24 32 37 14 26 40 52 44 9 41 51 45 30 50 35 59 57 6 39 18 48 22 8 13 20 4 55 38 15 7 21 2 43 5 42 34 58 56 29 60

wt_sds_28: antF actor = 1, S Σ = true, T W T = 0, Zeit = 59 12 49 54 47 46 27 31 1 23 14 26 17 3 37 53 19 33 44 40 52 24 11 32 41 55 10 25 51 45 30 16 36 22 6 35 59 28 9 4 56 50 2 43 39 18 48 8 13 20 38 15 7 21 57 5 42 34 58 29 60

wt_sds_30: antF actor = 1, S Σ = true, T W T = 360, Zeit = 293 26 52 20 10 40 30 6 33 42 1 14 28 38 12 15 32 16 8 50 59 19 55 2 3 56 41 46 58 48 31 4 24 53 36 60 5 35 18 21 29 39 9 7 45 25 37 54 23 34 49 44 27 47 22 11 51 57 17 43 13

wt_sds_37: antF actor = 1, S Σ = true, T W T = 1911, Zeit = 814 27 34 14 51 37 52 26 21 58 42 56 1 32 10 23 3 60 48 45 47 36 17 2 41 46 31 57 50 24 12 39 5 22 8 33 25 7 35 15 9 43 59 18 20 40 16 4 44 28 11 54 38 6 19 29 30 49 13 53 55

wt_sds_42: antF actor = 1, S Σ = true, T W T = 60495, Zeit = 323 7 1 2 10 39 4 8 32 9 16 43 24 58 44 60 50 37 17 28 12 18 23 29 21 34 14 22 51 36 6 48 49 30 15 46 41 59 45 31 11 19 47 5 33 3 40 52 38 53 56 25 57 42 13 26 35 54 55 27 20

wt_sds_44: antF actor = 1, S Σ = f alse, T W T = 36515, Zeit = 888 60 50 43 49 21 14 44 5 6 32 56 58 48 10 57 59 55 25 20 12 41 1 3 37 7 38 28 53 22 15 34 40 35 8 52 18 33 11 29 31 36 46 19 47 54 13 9 26 16 42 30 39 17 27 23 45 24 4 51 2

wt_sds_45: antF actor = 1, S Σ = f alse, T W T = 60151, Zeit = 643 18 22 12 16 10 44 60 35 54 57 36 2 47 42 43 48 56 58 55 40 6 8 11 25 1 49 59 46 28 17 38 5 23 30 19 27 37 32 29 41 52 3 51 21 50 24 4 53 9 7 34 13 15 14 20 45 31 39 26 33

wt_sds_46: antF actor = 1, S Σ = true, T W T = 37251, Zeit = 219 49 19 20 7 25 4 37 5 22 60 16 9 41 30 50 59 3 2 58 40 13 18 52 28 29 48 35 23 43 46 17 1 15 51 33 6 53 11 54 8 12 39 26 45 24 21 56 34 32 42 55 14 36 38 57 31 27 10 44 47

88 C Benchmarktest - Verbesserungen

wt_sds_48: antF actor = 1, S Σ = true, T W T = 68650, Zeit = 325 30 44 31 60 49 3 46 37 22 11 51 59 9 6 27 17 8 54 28 39 58 16 2 1 38 48 33 57 18 10 19 12 45 35 47 41 55 56 4 24 52 7 26 5 53 25 15 23 13 20 29 43 40 36 34 42 21 50 32 14

wt_sds_49: antF actor = 0.5, S Σ = true, T W T = 80418, Zeit = 276 39 50 30 6 46 48 20 49 42 14 59 55 35 16 25 24 56 10 40 23 29 15 41 58 12 33 36 7 44 3 53 31 28 57 45 37 27 8 9 17 18 5 1 32 54 43 4 47 51 26 34 13 38 19 11 22 60 21 52 2

wt_sds_50: antF actor = 0.5, S Σ = f alse, T W T = 35124, Zeit = 200 7 58 9 15 34 54 37 46 31 45 49 56 23 36 38 10 17 2 39 22 32 14 51 12 26 44 6 1 4 43 47 50 25 60 27 5 30 52 11 19 59 18 20 16 24 13 55 48 57 40 35 42 41 33 29 28 21 53 3 8

wt_sds_52: antF actor = 0.5, S Σ = true, T W T = 104696, Zeit = 148 43 30 60 47 57 15 59 28 5 55 51 14 53 25 41 16 39 26 21 29 58 44 4 8 3 35 18 1 31 7 9 11 17 22 49 37 20 38 27 12 50 33 56 2 36 23 24 46 45 6 32 54 48 40 13 34 42 19 52 10

wt_sds_53: antF actor = 1, S Σ = f alse, T W T = 95246, Zeit = 1206 54 33 37 51 21 44 9 14 48 36 20 42 30 41 57 6 25 38 35 15 55 46 29 43 59 23 52 47 4 17 40 58 49 56 8 10 60 2 34 7 11 16 19 26 31 1 3 50 45 39 24 32 18 53 27 28 13 5 22 12

wt_sds_56: antF actor = 1, S Σ = f alse, T W T = 81609, Zeit = 782 1 4 21 54 45 28 60 48 38 39 20 12 10 5 29 7 22 33 17 57 6 26 49 51 40 25 27 14 55 32 58 37 52 8 19 36 15 30 24 56 2 16 43 53 44 23 31 41 34 3 13 18 11 47 42 46 35 59 9 50

wt_sds_58: antF actor = 0.5, S Σ = true, T W T = 48593, Zeit = 250 22 53 16 43 31 49 60 5 11 55 20 32 2 36 48 6 56 24 46 33 21 1 44 18 4 7 29 39 54 3 30 28 14 9 40 26 23 37 27 41 59 15 42 10 13 50 52 38 47 45 35 19 8 57 25 17 12 51 58 34

wt_sds_60: antF actor = 1, S Σ = true, T W T = 72534, Zeit = 634 43 38 40 50 56 27 2 53 32 17 60 21 18 1 44 45 19 12 41 49 31 23 9 36 59 37 48 15 22 10 7 51 57 58 11 20 47 34 24 35 3 28 26 52 4 33 6 29 25 55 42 14 13 46 30 8 5 16 39 54

wt_sds_61: antF actor = 1, S Σ = true, T W T = 78798, Zeit = 640 27 49 45 58 42 54 55 44 28 35 47 21 3 26 8 46 43 33 41 11 31 18 24 10 57 60 4 40 7 2 51 39 59 16 32 50 20 17 23 29 56 6 22 37 34 38 13 12 9 30 19 52 15 48 1 5 36 25 53 14

wt_sds_62: antF actor = 0.5, S Σ = true, T W T = 44781, Zeit = 224 47 24 31 7 39 43 17 50 45 38 53 25 37 19 10 33 51 4 36 23 22 55 15 26 2 59 5 28 27 40 48 54 30 56 13 3 16 6 20 58 1 46 32 52 35 44 57 12 42 29 41 49 8 21 14 18 34 60 11 9

90 C Benchmarktest - Verbesserungen

wt_sds_63: antF actor = 1, S Σ = f alse, T W T = 75850, Zeit = 616 54 7 58 50 32 3 45 49 35 53 8 43 33 41 60 29 57 56 14 19 39 48 4 44 24 6 10 42 25 59 52 5 12 27 34 37 23 9 16 2 15 31 28 26 40 38 18 22 55 1 11 30 13 46 51 36 47 21 17 20

wt_sds_64: antF actor = 1, S Σ = f alse, T W T = 95111, Zeit = 784 44 22 47 30 24 46 25 39 9 11 36 6 5 49 48 40 37 16 20 56 57 45 4 59 26 58 8 32 1 23 28 53 42 13 51 41 19 60 43 15 17 14 54 31 38 50 12 34 52 7 55 18 10 27 35 33 29 21 3 2

wt_sds_65: antF actor = 0.5, S Σ = f alse, T W T = 129885, Zeit = 455 17 27 29 18 53 9 11 4 2 59 24 19 1 21 35 39 32 47 42 20 51 33 50 58 26 28 25 48 52 8 30 46 6 5 3 40 31 37 34 16 22 49 14 41 55 10 43 54 44 36 15 12 45 13 7 38 60 57 23 56

wt_sds_66: antF actor = 1, S Σ = true, T W T = 59998, Zeit = 687 7 54 21 44 24 60 15 10 6 17 51 31 46 22 37 20 32 18 49 26 45 4 29 2 1 36 53 41 33 14 25 56 50 39 12 34 47 38 11 19 35 3 55 52 40 42 9 43 30 58 57 23 16 13 8 27 28 59 5 48

wt_sds_67: antF actor = 1, S Σ = true, T W T = 30031, Zeit = 497 12 36 58 16 19 44 20 2 30 34 37 51 7 15 53 1 11 33 59 14 56 45 47 50 26 54 42 55 17 13 6 41 4 40 60 21 39 57 27 52 31 28 49 23 10 5 48 32 38 24 22 29 18 25 8 43 35 9 3 46

wt_sds_68: antF actor = 0.5, S Σ = true, T W T = 23693, Zeit = 188 11 38 30 45 19 40 2 53 60 10 33 12 49 28 47 25 1 16 55 59 34 37 54 58 41 14 56 43 9 57 26 6 5 23 29 27 46 50 24 22 35 3 18 20 52 21 32 15 51 8 42 13 36 7 39 17 31 44 4 48

wt_sds_70: antF actor = 1, S Σ = true, T W T = 78404, Zeit = 650 22 8 46 1 30 58 21 36 19 39 45 44 50 29 27 7 43 16 6 17 59 34 32 41 55 9 40 52 49 15 53 11 23 51 42 35 14 10 33 5 37 26 54 57 20 4 2 13 28 12 38 48 18 60 3 31 47 56 24 25

wt_sds_72: antF actor = 0.5, S Σ = true, T W T = 47842, Zeit = 141 57 44 5 23 4 58 31 11 8 30 20 60 49 15 52 18 59 1 25 39 34 29 28 36 56 3 42 40 46 43 17 33 21 7 27 47 12 53 26 55 32 41 10 50 19 54 48 2 14 45 37 16 9 13 35 24 6 22 51 38

wt_sds_73: antF actor = 1, S Σ = true, T W T = 29234, Zeit = 573 22 12 52 46 20 19 23 47 35 21 44 56 60 8 53 34 10 42 37 45 4 31 24 26 27 29 59 28 30 5 38 17 11 13 15 7 1 50 39 48 51 6 49 2 43 58 32 16 36 40 14 41 3 25 9 55 33 54 57 18

wt_sds_75: antF actor = 0.5, S Σ = true, T W T = 24372, Zeit = 146 37 41 32 59 20 34 23 45 52 18 17 6 22 9 50 53 4 1 27 21 8 60 44 11 54 29 28 57 42 24 2 43 30 15 7 31 36 49 38 13 25 39 56 3 51 55 16 10 40 5 33 35 58 48 47 19 12 26 46 14

92 C Benchmarktest - Verbesserungen

wt_sds_77: antF actor = 1, S Σ = true, T W T = 34281, Zeit = 565 31 47 28 41 4 2 5 60 16 57 24 9 45 21 25 13 42 49 35 18 55 15 46 50 3 14 1 36 6 12 8 30 22 38 56 26 11 39 58 10 29 33 19 20 54 37 52 34 32 40 7 23 48 27 51 17 53 44 59 43

wt_sds_78: antF actor = 1, S Σ = true, T W T = 21755, Zeit = 467 48 52 2 25 41 43 39 28 15 59 40 37 27 8 44 57 10 3 42 53 14 58 51 17 1 7 5 50 9 46 31 18 16 38 11 20 4 56 24 23 13 6 12 49 30 32 47 35 34 54 26 36 33 22 19 29 55 21 60 45

wt_sds_79: antF actor = 0.5, S Σ = true, T W T = 120462, Zeit = 128 38 5 36 55 47 58 7 43 21 50 13 54 35 16 11 51 19 8 17 49 42 60 37 40 44 15 12 46 9 20 18 14 22 39 10 4 32 6 52 31 41 48 34 57 53 24 3 23 33 1 2 59 45 27 25 29 30 28 26 56

wt_sds_80: antF actor = 0.5, S Σ = true, T W T = 22654, Zeit = 320 18 46 40 43 54 39 51 25 3 27 2 13 38 10 55 20 16 44 47 6 37 30 42 11 60 33 23 24 50 19 5 45 57 35 15 59 41 29 4 26 9 8 34 32 48 49 56 17 7 1 12 21 28 14 58 52 31 22 53 36

wt_sds_82: antF actor = 1, S Σ = f alse, T W T = 412998, Zeit = 463 18 59 35 17 31 33 48 37 49 7 53 54 14 21 15 56 29 39 44 19 58 50 16 5 1 45 27 34 10 43 60 20 3 26 41 24 42 11 40 52 32 22 36 30 8 23 57 13 55 9 38 46 6 47 51 25 28 4 12 2

wt_sds_86: antF actor = 1, S Σ = f alse, T W T = 363985, Zeit = 686 3 38 47 7 5 49 9 43 17 37 25 33 30 21 41 16 1 31 19 52 18 34 2 39 15 6 10 44 12 4 40 58 59 29 11 13 24 53 26 42 57 27 45 55 14 56 60 23 35 36 20 22 48 32 50 28 54 46 51 8

wt_sds_87: antF actor = 0.5, S Σ = true, T W T = 401416, Zeit = 192 24 8 7 54 22 28 43 42 12 37 27 56 25 20 60 46 36 35 53 48 15 6 21 30 11 4 31 40 57 41 44 10 39 29 9 50 49 34 13 45 16 26 38 19 18 3 1 51 32 52 59 14 17 47 33 55 5 23 58 2

wt_sds_89: antF actor = 0.5, S Σ = true, T W T = 411434, Zeit = 228 44 39 47 25 7 60 48 36 51 24 54 27 17 15 22 40 37 23 6 3 34 14 50 11 45 42 26 30 18 16 4 8 55 10 43 58 59 49 52 31 53 13 46 21 56 5 41 2 38 33 20 29 35 28 12 9 1 32 57 19

wt_sds_101: antF actor = 0.5, S Σ = true, T W T = 355131, Zeit = 281 35 33 14 23 55 26 9 28 53 42 25 44 16 32 59 52 31 4 58 45 56 29 3 49 2 60 48 7 40 51 21 12 24 39 6 11 27 43 54 13 10 18 22 36 8 15 19 34 17 57 5 38 1 30 46 37 47 41 20 50

wt_sds_102: antF actor = 1, S Σ = true, T W T = 494378, Zeit = 326 9 15 39 49 27 60 42 4 38 36 46 14 56 47 32 12 54 45 21 19 41 16 11 30 7 50 26 25 51 57 34 53 23 13 20 1 55 22 6 35 29 43 52 24 5 10 3 8 2 33 28 59 31 17 37 18 58 48 44 40

94 C Benchmarktest - Verbesserungen

wt_sds_104: antF actor = 1, S Σ = true, T W T = 359485, Zeit = 383 38 49 32 33 51 36 53 57 5 39 4 40 28 43 8 22 50 42 10 26 35 41 17 14 1 58 44 27 16 52 21 18 2 47 30 29 55 46 13 15 9 60 24 59 7 23 19 48 11 34 37 54 45 56 25 6 31 20 3 12

wt_sds_105: antF actor = 1, S Σ = true, T W T = 450806, Zeit = 474 58 18 19 26 15 6 23 42 55 50 43 46 39 8 38 60 20 25 7 31 44 10 17 36 12 32 48 14 30 54 33 5 41 13 11 47 16 49 3 24 52 9 21 56 29 34 40 57 35 53 28 51 22 45 59 1 27 4 37 2

wt_sds_108: antF actor = 0.5, S Σ = true, T W T = 464658, Zeit = 270 47 41 54 44 30 51 26 60 20 57 40 6 9 59 22 19 28 46 14 13 36 42 18 58 52 49 25 17 3 2 31 45 11 8 48 43 32 1 12 55 24 4 53 10 27 56 34 16 23 50 5 33 39 21 35 7 37 29 38 15

wt_sds_110: antF actor = 0.5, S Σ = true, T W T = 418984, Zeit = 140 15 45 40 25 54 7 47 55 49 36 20 17 33 44 48 22 50 23 16 31 46 39 4 14 28 41 42 43 27 57 24 1 56 5 52 32 58 19 6 30 13 35 12 53 8 3 9 34 11 51 18 38 2 29 60 10 21 59 37 26

wt_sds_113: antF actor = 0.5, S Σ = true, T W T = 261789, Zeit = 172 46 47 16 39 29 60 42 5 35 51 54 36 9 32 10 7 19 21 8 52 24 4 3 44 45 53 30 33 28 2 17 40 55 13 57 38 50 48 31 27 49 23 6 25 15 22 20 41 12 1 11 59 14 26 37 58 34 18 56 43

wt_sds_120: antF actor = 0.5, S Σ = true, T W T = 398518, Zeit = 249 18 13 52 22 28 31 27 20 45 19 25 15 35 14 39 24 34 49 55 60 44 9 53 33 3 16 56 42 23 50 41 36 1 6 7 30 10 11 38 51 21 26 29 5 2 48 43 37 12 54 40 4 59 8 32 57 17 46 47 58

Kompletter Text

Beschreibung

Ähnliche Arbeiten

Kommentare

Kommentieren

Neuigkeiten

So funktioniert's

Ähnliche Arbeiten

Facebook

Neuigkeiten

Bücher zum Thema

Autor

Kompletter Text

Beschreibung

Ähnliche Arbeiten

Kommentare

Kommentieren

Neuigkeiten

So funktioniert's

Ähnliche Arbeiten

Facebook

Neuigkeiten

Bücher zum Thema

Registrieren oder einloggen

Neu hier?

Einloggen

Die Alternative

Passwort vergessen?

Neues Passwort anfordern