Diese Arbeit beschäftigt sich mit neuen Ansätzen zur Lösung des Generalized-Assignment-Problems (GAP). Es werden werden verschiedene Heuristiken wie auch exakte Verfahren zur Lösung des GAP betrachtet.
Unter dem GAP versteht man ein
kombinatorisches Zuordnungsproblem, bei dem n Aufträge von m Arbeitern bearbeitet werden sollen.
Jeder Arbeiter ist durch seine maximale Arbeitszeit beschränkt und für jede Zuordnung eines Arbeiters an einen Auftrag entstehen Kosten.
Das Ziel des GAP ist es, die gesamten Kosten unter Berücksichtigung der gegebenen Schranken zu minimieren.
Studienarbeit
Neue L¨
osungsans¨
atze f¨
ur das
Generalized-Assignment-Problem
von
Christoph Holzbaur
Matr. 959821
19. Juni 2006
Technische Universit¨at Darmstadt
Fachbereich Rechts- und Wirtschaftswissenschaften
Institut f¨
ur Betriebswirtschaftslehre
Fachgebiet Operations Research
Inhaltsverzeichnis
Inhaltsverzeichnis
Inhaltsverzeichnis
IV
Abbildungsverzeichnis
V
Tabellenverzeichnis
VI
Abk¨
urzungsverzeichnis
VII
1 Einleitung
1
1.1 Mathematische Darstellung des Generalized-Assignment-Problems .
2
1.2 Der L¨osungsraum des Generalized-Assignment-Problems . . . . . .
4
2 Heuristiken
5
2.1 Die Heuristik von Martello und Toth . . . . . . . . . . . . . . . . .
5
2.1.1
Darstellung als Maximierungsproblem . . . . . . . . . . . . .
6
2.1.2
Die Heuristik . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.1.3
Ein Beispiel f¨ur die Heuristik von Martello und Toth . . . .
9
2.2 Elliptische Schnitte . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.3 Weitere Heuristiken f¨ur das Generalized-Assignment-Problem . . . .
14
2.3.1
Genetische Algorithmen . . . . . . . . . . . . . . . . . . . .
15
2.3.2
Tabu-Search . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.3.3
Scatter-Search und Path-Relinking . . . . . . . . . . . . . .
18
3 Branch-and-Bound
20
3.1 Branch-and-Bound im Allgemeinen . . . . . . . . . . . . . . . . . .
20
3.2 Der Algorithmus von Martello und Toth . . . . . . . . . . . . . . .
22
3.2.1
Den L¨osungsraum reduzieren . . . . . . . . . . . . . . . . .
22
-II-
Inhaltsverzeichnis
3.2.2
Eine obere Schranke ermitteln . . . . . . . . . . . . . . . . .
24
3.2.3
Die maximale Distanz . . . . . . . . . . . . . . . . . . . . .
25
3.2.4
Die Branching-Strategie . . . . . . . . . . . . . . . . . . . .
27
3.2.5
Ein Beispiel f¨ur den Algorithmus von Martello und Toth . .
28
4 Branch-and-Cut
33
4.1 Das Schnittebenenverfahren . . . . . . . . . . . . . . . . . . . . . .
34
4.2 Die Branching-Strategie des Branch-and-Cut Verfahrens . . . . . .
36
4.3 G¨ultige Schnittebenen konstruieren . . . . . . . . . . . . . . . . . .
36
4.3.1
Gomory-Cuts . . . . . . . . . . . . . . . . . . . . . . . . . .
38
4.3.2
Ein Beispiel f¨ur Gomory-Cuts . . . . . . . . . . . . . . . . .
38
4.3.3
Spezielle Schnittebenen . . . . . . . . . . . . . . . . . . . . .
40
4.3.4
Ein Beispiel f¨ur spezielle Schnittebenen . . . . . . . . . . . .
42
5 Branch-and-Price
45
5.1 Die Dantzig-Wolfe Dekomposition . . . . . . . . . . . . . . . . . . .
46
5.2 Die Set-Partition Zerlegung . . . . . . . . . . . . . . . . . . . . . .
49
5.3 Die Spaltengenerierung von Savelsbergh
. . . . . . . . . . . . . . .
50
5.4 Ein Beispiel f¨ur die Spaltengenerierung . . . . . . . . . . . . . . . .
52
5.5 Die Branching-Strategie . . . . . . . . . . . . . . . . . . . . . . . .
59
6 Branch-and-Cut-and-Price
63
6.1 Schnittebenen f¨ur Branch-and-Cut-and-Price . . . . . . . . . . . . .
64
6.2 Das Stabilisieren der Spaltengenerierung . . . . . . . . . . . . . . .
64
6.2.1
Die Methodik . . . . . . . . . . . . . . . . . . . . . . . . . .
65
6.2.2
Die Anwendung im Algorithmus . . . . . . . . . . . . . . . .
67
6.3 Ein Beispiel f¨ur die stabilisierte Spaltengenerierung . . . . . . . . .
67
6.4 Testergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
7 Glossar
74
7.1 Polytop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
7.2 Set-Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
7.3 Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
7.4 0/1-Knapsackproblem
. . . . . . . . . . . . . . . . . . . . . . . . .
75
7.5 Metaheuristiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
-III-
Inhaltsverzeichnis
7.6 Ejection-Chain . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
7.7 Nachbarschaft . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
7.8 OR-Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
A Ein vollst¨
andiges Beispiel f¨
ur die stabilisierte Spaltengenerierung
78
Literaturverzeichnis
89
-IV-
Abbildungsverzeichnis
Abbildungsverzeichnis
1.1 M¨ogliche Zuordnung von 8 Auftr¨agen zu 3 Arbeiter . . . . . . . . .
1
3.1 Aufteilung, wenn ^j von keinem Arbeiter ¨ubernommen wurde . . . .
27
3.2 Aufteilung, wenn ^j von mehreren Arbeitern ¨ubernommen wurde . .
28
3.3 L¨osungsbaum f¨ur Branch-and-Bound . . . . . . . . . . . . . . . . .
32
4.1 Finden des Optimums mit dem Schnittebenenverfahren . . . . . . .
35
4.2 Ablauf von Branch-and-Cut . . . . . . . . . . . . . . . . . . . . . .
37
5.1 Ablauf von Branch-and-Price . . . . . . . . . . . . . . . . . . . . .
62
6.1 Ablauf von Branch-and-Cut-and-Price . . . . . . . . . . . . . . . .
73
-V-
Tabellenverzeichnis
Tabellenverzeichnis
2.1
¨
Uberf¨uhrung einer L¨osung in eine andere beim Path-Relinking . . .
19
6.1 Auswirkung der Stabilisierung . . . . . . . . . . . . . . . . . . . . .
71
6.2 Auswirkung der Stabilisierung . . . . . . . . . . . . . . . . . . . . .
72
-VI-
Tabellenverzeichnis
Abk¨
urzungsverzeichnis
BCP . . . . . . . . . . . . . . Branch-and-Cut-and-Price
CGA . . . . . . . . . . . . . . Constructive Genetic Algorithm
GA . . . . . . . . . . . . . . . . Genetic Algorithm
GAP . . . . . . . . . . . . . . Generalized-Assignment-Problem
ILP . . . . . . . . . . . . . . . Integer Linear Program
LP . . . . . . . . . . . . . . . . Linear Program
MGAP . . . . . . . . . . . . Multiple-Choice Generalized-Assignment-Problem
MIP . . . . . . . . . . . . . . . Mixed-Integer Program
MP . . . . . . . . . . . . . . . Master Problem
RMP . . . . . . . . . . . . . . Restricted Master Problem
-VII-
KAPITEL 1. EINLEITUNG
1 Einleitung
Diese Arbeit besch¨aftigt sich mit neuen Ans¨atzen zur L¨osung des Generalized-
Assignment-Problems. Unter dem Generalized-Assignment-Problem (GAP) ver-
steht man ein kombinatorisches Zuordnungsproblem, bei welchem n Auftr¨age von
m Arbeitern bearbeitet werden sollen. Abbildung 1.1 zeigt eine m¨ogliche Zuord-
nung von 8 Auftr¨agen zu 3 Arbeitern.
1
Abbildung 1.1: M¨ogliche Zuordnung von 8 Auftr¨agen zu 3 Arbeiter
Beim Generalized-Assignment-Problem ist zu beachten, dass
· jeder Arbeiter durch seine maximale Arbeitszeit beschr¨ankt ist und f¨ur jeden
Auftrag eine bestimmte Menge an Zeiteinheiten (ZE) ben¨otigt
· falls ein Arbeiter einen Auftrag ¨ubernimmt Kosten entstehen, die abh¨angig
von der Kombination ArbeiterAuftrag sind.
1
Das Beispiel, das zu dieser Zuordnung f¨
uhrt wird in Kapitel 3.2.5 behandelt.
-1-
KAPITEL 1. EINLEITUNG
Das Ziel des GAP ist es, die gesamten Kosten unter Ber¨ucksichtigung der gegebenen
Schranken zu minimieren.
In der Praxis findet das Generalized-Assignment-Problem h¨aufig Anwendung. Ab-
gesehen von der Zuordnung von Aufgaben zu Maschinen wird das GAP benutzt
wenn in einem Rechnerverbund mehrere Prozesse bearbeitet werden sollen. Mit Hil-
fe des Generalized-Assignment-Problems werden diese dann an die verschiedenen
Computer verteilt.
In der Literatur tritt das Generalized-Assignment-Problem h¨aufig auch als Ma-
ximierungsproblem auf. Hierbei wird versucht den maximalen Profit bzw. Nut-
zen f¨ur eine Verteilung von Auftr¨agen an Arbeiter unter den gegebenen Gren-
zen zu erreichen. Die Umrechnung des Generalized-Assignment-Problems von der
Minimierungs- in die Maximierungsform wird in Kapitel 2.1.1 behandelt.
Beim Generalized-Assignment-Problem handelt es sich um ein ganzzahliges lineares
Optimierungsproblem. Garey und Johnson [14] haben bewiesen, dass das Generali-
zed-Assignment-Problem NP-schwer ist. Es existiert daher wahrscheinlich kein Al-
gorithmus, der das GAP in polynomialer Zeit l¨osen kann (vgl. [11]). Deshalb wurden
in letzter Zeit einige Anstrengungen unternommen gute Heuristiken zu finden, die
nicht unbedingt das Optimum eines Problems sondern eine gute N¨aherungsl¨osung
in m¨oglichst kurzer Zeit suchen. Einige von ihnen werden in Kapitel 2 beschrieben.
Diese Arbeit besch¨aftigt sich dennoch haupts¨achlich mit exakten L¨osungsverfah-
ren, da diese hervorragende Ergebnisse erzielen. Die zur Zeit effektivsten exakten
L¨osungsverfahren sind Variationen des bekannten Branch-and-Bound Verfahrens
und werden in Kapitel 3 n¨aher beschrieben.
1.1 Mathematische Darstellung des
Generalized-Assignment-Problems
Das Generalized-Assignment-Problem kann als ganzzahliges lineares Programm
(Integer Linear Program, ILP) folgendermaßen mathematisch beschrieben werden.
-2-
KAPITEL 1. EINLEITUNG
Jedem Auftrag j aus der Menge der Auftr¨age J = {1, . . . , n} wird ein Arbeiter i aus
der Menge der Arbeiter I = {1, . . . , m} zugeordnet. Die maximale Arbeitszeit des
Arbeiters i betr¨agt a
i
> 0 Zeiteinheiten. Wenn Arbeiter i den Auftrag j ¨ubernimmt,
ben¨otigt er genau b
ij
> 0 Zeiteinheiten und es entstehen f¨ur diese Zuordnung die
Kosten c
ij
> 0. Ziel ist es die gesamten Kosten F zu minimieren.
Wenn man nun zus¨atzlich z
ij
als eine bin¨are Zuordnugsvariable definiert, f¨ur die
z
ij
=
1 falls Auftrag j dem Arbeiter i zugeordnet wird
0 sonst
i I, j J
gilt, kann man das GAP folgendermaßen beschreiben:
Minimiere F (z) =
i
I jJ
c
ij
z
ij
(1.1)
unter den Nebenbedingungen
j
J
b
ij
z
ij
a
i
i I
(1.2)
i
I
z
ij
= 1
j J
(1.3)
z
ij
{0, 1}
i I, j J.
(1.4)
Die Bedingungen (1.2) werden Kapazit¨atsbeschr¨ankungen (capacity constraints)
genannt und sorgen daf¨ur, dass die maximalen Arbeitszeiten der Arbeiter nicht
¨
uberschritten werden k¨onnen. Die Gleichungen (1.3) bewirken, dass jeder Auftrag
genau ein mal vergeben wird und heißen Zuweisungsbeschr¨ankungen (assignment
constraints). Die Ganzzahligkeitsrestriktionen (1.4) stellen sicher, dass, wenn ein
Auftrag vergeben wird, er auch komplett bearbeitet werden muss.
-3-
KAPITEL 1. EINLEITUNG
1.2 Der L¨
osungsraum des
Generalized-Assignment-Problems
Als L¨osungsraum bezeichnet man in der Mathematik eine L¨osungsmenge, die gleich-
zeitig ein Vektorraum oder ein affiner Raum ist. Der L¨osungsraum K des GAP
besteht aus der Menge aller m¨oglichen Zuordnungen der Auftr¨age auf die Arbeiter,
bei dem jede Zuordnung ein Element aus K darstellt.
Man kann sich vorstellen, dass in einer Urne m Kugeln vorhanden sind, welche f¨ur
die m Arbeiter stehen und dass man bei jedem von n Z¨ugen versucht einen Arbeiter
einer Aufgabe zuzuordnen. Dies entspricht dann n Ziehungen mit m M¨oglichkeiten
mit Zur¨ucklegen und unter Beachtung der Reihenfolge. K enth¨alt demnach |K| =
m
n
Elemente, wobei jedes Element f¨ur eine m¨ogliche Zuordnung aller Auftr¨age zu
den Arbeitern steht.
Der L¨osungsraum des Generalized-Assignment-Problems kann in zwei zueinander
disjunktive Unterr¨aume aufgeteilt werden:
· Die Untermenge F der Elemente, welche die Kapazit¨atsbeschr¨ankungen (1.2)
erf¨ullen (g¨ultige Untermenge) und
· Die Untermenge der restlichen Elemente U (ung¨ultige Untermenge) (vgl. [11]).
-4-
KAPITEL 2. HEURISTIKEN
2 Heuristiken
Da das Generalized-Assignment-Problem NP-schwer ist, ist die optimale L¨osung
in den meisten F¨allen nur sehr aufwendig zu berechnen. In solchen Situationen lie-
fern Heuristiken relativ gute L¨osungen mit vergleichsweise wenig Rechenaufwand.
Das Wort Heuristik leitet sich von dem griechischen Wort heuriskein ab, welches
soviel bedeutet wie
"
finden" oder
"
entdecken". Der Grundgedanke von Heuristi-
ken ist, dass es h¨aufig besser ist eine gute L¨osung mit angemessenem Aufwand
zu berechnen als eine optimale L¨osung mit unangemessenem Aufwand. Heuristi-
ken versuchen nicht ein gegebenes Problem genau zu l¨osen, sondern gehen einen
Kompromiss zwischen der G¨ute der gefundenen L¨osung und dem Rechenaufwand
ein. Heuristiken sind meist f¨ur ein spezielles Problem konzipiert und bedienen sich
der Erkenntnisse ¨uber deren Struktur. Bei Heuristiken ist es jedoch nur beschr¨ankt
m¨oglich eine Aussage ¨uber die Qualit¨at der gefundenen L¨osung zu machen.
In Kapitel 2.1 wird zun¨achst auf ein einfaches heuristisches Er¨offnungsverfahren f¨ur
das GAP von Martello und Toth [33] eingegangen. Kapitel 2.2 beschreibt ein neues
heuristisches Verbesserungsverfahren, das 2004 von Pigatti et al. [40] eingef¨uhrt
wurde. Außerdem werden in Kapitel 2.3 einige neuere ausgew¨ahlte heuristische
Ans¨atze zur L¨osung des Generalized-Assignment-Problems kurz beschrieben und
es werden Literaturhinweise f¨ur die interessantesten Heuristiken gegeben.
2.1 Die Heuristik von Martello und Toth
Martello und Toth [33] entwickelten 1981 einen Algorithmus, welcher eine heu-
ristische L¨osung f¨ur das Generalized-Assignment-Problem liefert. Diese Heuristik
-5-
KAPITEL 2. HEURISTIKEN
ist als Er¨offnungsverfahren gut geeignet und findet als dieses auch in Kapitel 3.2
Anwendung.
Die Heuristik verl¨auft in zwei Schritten. Im ersten Schritt wird iterativ der Auftrag
zugewiesen, der den gr¨oßten Regret f¨ur das Nichtzuweisen hat. Danach wird im
zweiten Schritt versucht, das Ergebnis durch gezieltes Vertauschen von Zuordnun-
gen zu verbessern.
Das Ergebnis der Heuristik wird in Kapitel 3.2 verwendet. Hierf¨ur ist es von Vor-
teil, das Generalized-Assignment-Problem zuerst in ein Maximierungsproblem um-
zuwandeln.
2.1.1 Darstellung als Maximierungsproblem
Martello und Toth [33] definieren den Vektor
t
j
> max
i
I
c
ij
j J
(2.1)
und berechnen die Variable
p
ij
= t
j
- c
ij
i I, j J.
Die Variable p
ij
kann als Profit betrachtet werden, der durch Zuordnung des Auf-
trags j zu den Arbeiter i erwirtschaftet wird. Der Vektor t
j
kann frei gew¨ahlt
werden, da die Bedingung (2.1) daf¨ur sorgt, dass keine negativen Profite entste-
hen. Nun kann das Generalized-Assignment-Problem in ein Maximierungsproblem
umgewandelt werden:
Maximiere W (z) =
i
I jJ
p
ij
z
ij
(2.2)
Bei dieser Umformung bleiben die Kapazit¨atsbeschr¨ankungen (1.2), die Zuwei-
sungsbeschr¨ankungen (1.3) und die Ganzzahligkeitsrestriktionen (1.4) erhalten.
-6-
KAPITEL 2. HEURISTIKEN
2.1.2 Die Heuristik
F¨ur ihre Heuristik definieren Martello und Toth [33] die Gewichtsfunktionen
ij
f¨ur den Nutzen einer Zuweisung des Auftrags j an den Arbeiter i. Die Heuristik
erzielt mit folgenden Gewichtsfunktionen gute Resultate:
ij
=
p
ij
p
ij
b
ij
-b
ij
-b
ij
r
i
(r
i
= noch verf¨ugbare ZE des Arbeiters i).
i I, j J
(2.3)
Im ersten Schritt der Heuristik wird f¨ur jeden Auftrag ein Regret berechnet. Diesen
Wert kann man als Nutzeneinbuße f¨ur das Nichtzuordnen eines Auftrags an einen
Arbeiter in diesem Schritt betrachten. Der Regret f¨ur den Auftrag j berechnet
sich als die Differenz zwischen dem gr¨oßten und dem zweitgr¨oßten Nutzen
ij
der Arbeiter i, deren Kapazit¨at f¨ur das ¨
Ubernehmen des Auftrags j ausreicht.
Daraufhin wird der Auftrag mit dem gr¨oßten Regret dem Arbeiter zugeteilt, der
damit den gr¨oßten Nutzen hat.
Im zweiten Schritt wird versucht eine bessere L¨osung zu finden, indem man unter
Ber¨ucksichtigung der Kapazit¨atsbeschr¨ankungen lokale Vertauschungen vornimmt
(local exchange procedure). Die Idee dahinter ist, dass durch gezielte Vertauschun-
gen (shift procedure) einzelner Auftr¨age j eine bessere L¨osung gefunden werden
kann. Bei der Vertauschung werden nacheinander alle Auftr¨age j betrachtet
2
und
unter Ber¨ucksichtigung der Kapazit¨atsrestriktionen dem Arbeiter i zugewiesen, f¨ur
den der Profit p
ij
am h¨ochsten ist.
3
Die Worst-Case Gesamtkomplexit¨at f¨ur diese
Heuristik ergibt sich als O(n
2
m + nm) = O(n
2
m).
Algorithmus 2.1: Heuristik von Martello und Toth
/ I n i t i a l i s i e r u n g /
F { 1 , . . . , n} ;
f o r
i I do r
i
a
i
;
2
O(n) Operationen
3
O(m) Operationen
-7-
KAPITEL 2. HEURISTIKEN
/ S c h r i t t 1 /
/ F¨uhre den Algorithmus f ¨u r a l l e Auftr¨age durch /
while
F = {} do
f o r
j J do
/ Gibt e s k e i n g r ¨o ß t e s
ij
das d i e s e Bedingung e r f ¨u l l t ,
b r i c h t der Alg o r it hmus ohne E r g e b n i s ab . /
i f
min
i
I
{ b
ij
- r
i
}>0 then
e x i t
e l s e
i
j
= max
i
I
{
ij
| ( b
ij
- r
i
)0}
end
i f
/ Gibt e s k e i n z w e i t g r ¨o ß t e s
ij
wird d
j
a u f g e s e t z t . /
i f
min
i
I-i
{ b
ij
-r i }>0 then
d
j
=
e l s e
/ d
j
i s t d i e D i f f e r e n z zwischen dem g r ¨o ß t e n und dem
z w e i t g r ¨o ß t e n
ij
f ¨u r d i e b e i d e ( b
ij
r
i
) g i l t . d
j
kann man
a l s Nutzeneinbuße f ¨u r das Nichtzuordnen b e t r a c h t e n . /
d
j
=
i
j
- max
i
I-i
{
ij
| ( b
ij
- r
i
)0}
end
i f
end f o r
/ G r ¨oßtes d
j
wird a usg ew¨ahlt und e n t s p r e c h e n d e r Auftrag
wird z u g e o r d n e t . /
d
j
= max
j
J
{ d
j
}
y
j
i
/ Z u g e o r d n e t e r Auf t r a g wird aus der zu unt er suchenden
Menge g e s t r i c h e n und Z e i t r e s s o u r c e n werden a n g e p a s s t /
F F - { j
}
r
i
r
i
- b
i
j
end while
/ S c h r i t t 2 /
/ Optimieren der L¨osung durch h¨oheren P r o f i t /
f o r
j J do
-8-
KAPITEL 2. HEURISTIKEN
p
ij
= max
i
I-{y
j
}
{p
ij
| b
ij
r
i
}
/ Wenn e s f ¨u r e i n e n Auftrag e i n e n A r b e i t e r g i b t , der mehr
P r o f i t e r w i r t s c h a f t e n kann ohne s e i n e Z e i t r e s s o u r c e n zu
¨
u b e r s c h r e i t e n wird ihm d i e s e r Auf t r a g z u g e t e i l t /
i f
p
ij
> p
y
j
j
then
y
j
i
r
y
i
r
y
i
+ b
y
i
i
r
i
r
i
- b
ij
end
i f
end f o r
Wenn man sich ¨uberlegt, dass sich durch den zweiten Schritt die noch offenen
Ressourcen der Arbeiter ver¨andert haben, kann man die Heuristik von Martello und
Toth [33] mit wenig Rechenaufwand noch weiter verbessern, indem man den zweiten
Schritt solange wiederholt, bis keine Verbesserung der L¨osung mehr auftritt.
2.1.3 Ein Beispiel f¨
ur die Heuristik von Martello und Toth
Ausgangspunkt sind 8 Auftr¨age, welche von 3 Arbeitern ¨ubernommen werden sol-
len. Das Generalized-Assignment-Problem sei als Maximierungsproblem (siehe For-
mel 2.2) formuliert.
Die Profite seien
p
ij
=
27 12 12 15 14 23 22 5
14
5
37 16 10 17 39 11
25 16 18
8
17 34
9
12
,
die ben¨otigten Arbeitszeiten seien
b
ij
=
21 13 9 8 9 13 6 13
20
8
18 17
8
12 20
7
5
4
20 30 25 11 20 14
-9-
KAPITEL 2. HEURISTIKEN
und die maximale Arbeitszeit pro Arbeiter sei
a
i
=
2625
34
.
Ferner sei der Nutzen
ij
= -b
ij
:
ij
=
-21 -13 -9 -8 -9 -13 -6 -13
-20
-8
-18 -17
-8
-12 -20
-7
-5
-4
-20 -30 -25 -11 -20 -14
.
F sei die Menge der noch zu betrachtenden Auftr¨age und r
i
f¨ur i I die zur Zeit
noch verf¨ugbare Restkapazit¨at von Arbeiter i.
Initialisierung:
F = {1; . . . ; 8}; r
1
= 26; r
2
= 25; r
3
= 34
Im ersten Schritt wird iterativ der Auftrag j
mit dem gr¨oßten Regret dem Arbeiter
i
mit dem gr¨oßten Nutzen zugeordnet (y
j
= i
). Wenn mehrere Auftr¨age den
gleichen Regret aufweisen wird zwischen diesen Auftr¨agen zuf¨allig entschieden:
d
1
d
2
d
3
d
4
d
5
d
6
d
7
d
8
d
y
F
r
1
r
2
r
3
1. 15
4
9
9
1
1
14
6
d
1
y
1
= 3 {2; 3; 4; 5; 6; 7; 8} 26 25 29
2. -
4
9
9
1
1
14
6
d
7
y
7
= 1
{2; 3; 4; 5; 6; 8}
20 25 29
3. -
4
9
9
1
1
-
6
d
4
y
4
= 1
{2; 3; 5; 6; 8}
12 25 29
4. -
4
9
-
1
1
-
7
d
3
y
3
= 1
{2; 5; 6; 8}
3
25 29
5. -
4
- -
7
1
-
7
d
5
y
5
= 2
{2; 6; 8}
3
17 29
6. -
4
- - -
1
-
7
d
8
y
8
= 2
{2; 6}
3
10 29
7. -
4
- - - - - d
6
y
6
= 3
{2}
3
10 18
8. -
4
- - -
-
- - d
2
y
2
= 3
{}
3
10 14
-10-
KAPITEL 2. HEURISTIKEN
Im zweiten Schritt werden nacheinander alle Auftr¨age betrachtet und wenn man
sich dadurch einen h¨oheren Profit verspricht, so werden sie einem anderen Arbeiter
zugeteilt, dessen Restkapazit¨at noch ausreicht.
j
y
r
1
r
2
r
3
1
-
3
10 14
2
-
3
10 14
3
-
3
10 14
4
-
3
10 14
5
-
3
10 14
6
-
3
10 14
7
-
3
10 14
8 y
8
= 3
3
17
0
Nach Durchf¨uhrung der Heuristik ergibt sich die Zuordnung
y
j
= 3 3 1 1 2 3 1 3
mit den durch Klammern hervorgehobenen Profiten
p
ij
=
27 12 (12) (15) 14 23 (22) 5
14
5
37
16
(10)
17
39
11
(25) (16)
18
8
17
(34)
9
(12)
.
und dem heuristischen Maximalwert
^
W
h
= 25 + 16 + 12 + 15 + 10 + 34 + 22 + 12 = 146.
Wenn man nun den zweiten Schritt wiederholt
j
y
r
1
r
2
r
3
4 y
4
= 2 11
0
0
5 y
5
= 1
2
8
0
-11-
KAPITEL 2. HEURISTIKEN
ergibt sich der neue heuristische Maximalwert
^
W
h
= 25 + 16 + 12 + 16 + 14 + 34 + 22 + 12 = 151.
Eine weitere Wiederholung des zweiten Schrittes ergibt keine Verbesserung des
Maximalwerts. Somit ist das heuristische Maximum mit ^
W
h
= 151 gefunden.
2.2 Elliptische Schnitte
Elliptische Schnitte wurden 2004 von Pigatti et al. [40] eingef¨uhrt und basieren
auf dem k-opt Verfahren und einer Idee von Fischetti und Lodi [13]. K-opt ist ein
Verfahren, bei dem versucht wird, eine bisher erhaltene L¨osung durch Vertauschen
von maximal k Zuordnungen weiter zu verbessern. Da jedoch die Komplexit¨at von
k-opt exponentiell von k abh¨angt, ist es nur f¨ur kleine k geeignet. Fischetti und
Lodi [13] schlugen 2003 ein Verfahren vor, durch das die Anwendung von k-opt
auch f¨ur gr¨oßere k sinnvoll wird.
Angenommen P sei ein 0/1-ILP mit den Variablen z
ij
f¨ur i I und j J und ange-
nommen jede g¨ultige L¨osung von P besitzt genau n Variablen mit dem Wert 1.
4
Sei
z eine heuristisch gefundene L¨osung von P und N
1
(z) die Menge an Variablen aus
z, die den Wert 1 besitzen, dann kann man f¨ur das k-opt Verfahren einen normalen
MIP-L¨oser verwenden. Dies erreicht man durch das Hinzuf¨ugen der Bedingung
i
×jN
1
(z)
z
ij
n - k
(2.4)
zu P . Die auf der linken Seite stehende Summe berechnet die Anzahl an Variablen,
die in z sowie auch in z den Wert 1 besitzen. Durch diese neue Ungleichung wird
also erreicht, dass mindestens n - k Werte aus der Ausgangsl¨osung auch in der
neuen L¨osung vorkommen. Somit wird der MIP-L¨oser auf eine, durch den Wert k
bestimmte, kugelf¨ormige Nachbarschaft
5
um die Ausgangsl¨osung begrenzt.
4
F¨
ur das Generalized-Assignment-Problem sind diese Voraussetzungen g¨ultig.
5
F¨
ur eine Erl¨auterung des Begriffes Nachbarschaft siehe Kapitel 7.7
-12-
KAPITEL 2. HEURISTIKEN
Man kann sich dieses Verfahren folgendermaßen veranschaulichen. Wenn ein exak-
tes Verfahren nicht in der Lage ist eine L¨osung zu finden, kann man durch Hin-
zuf¨ugen von (2.4) das Problem soweit einschr¨anken, dass zumindest in der Nachbar-
schaft einer schon bekannten L¨osung eine neue beste L¨osung gefunden werden kann.
Jede so gefundene bessere L¨osung kann man nat¨urlich als neue Ausgangsl¨osung ver-
wenden, indem man die Ungleichung (2.4) entsprechend anpasst.
Pigatti et al. [40] entwickelten 2004 ein neues exaktes Verfahren f¨ur das GAP, wel-
ches sie Branch-and-Cut-and-Price nannten.
6
Sie versuchten durch Hinzuf¨ugen von
(2.4) ihr Verfahren als heuristisches Verbesserungsverfahren zu verwenden. Sie tes-
teten es an einigen frei verf¨ugbaren Testinstanzen f¨ur das Generalized-Assignment-
Problem [2], um die bisher besten bekannten L¨osungen weiter zu verbessern. Sie
merkten jedoch, dass dies zu keinen merklichen Verbesserungen f¨uhrte. Erst als sie
nicht mehr versuchten, in der kugelf¨ormigen Nachbarschaft um eine heuristische
L¨osung zu suchen, kamen sie auf bessere Ergebnisse. Hierf¨ur schr¨ankten sie das
Problem auf eine elliptische Nachbarschaft um zwei heuristische, jedoch voneinan-
der m¨oglichst unterschiedliche, L¨osungen ein. Das Einschr¨anken des Suchraumes
auf die elliptische Nachbarschaft zwischen den L¨osungen z
1
und z
2
erreichten sie
durch das Hinzuf¨ugen der Ungleichung
i
×jN
1
(z
1
)N
1
(z
2
)
2z
ij
+
i
×j(N
1
(z
1
)N
1
(z
2
))\(N
1
(z
1
)N
1
(z
2
))
z
ij
(z
1
, z
2
) - k
zu P .
Die linke Seite beschreibt hier die Summe an Variablen, die in z wie auch in z
1
und
die in z sowie auch in z
2
den Wert 1 besitzen. Hierbei ist k wie beim k-opt Ver-
fahren der Schlupf, mit dem die Gr¨oße der Nachbarschaft definiert wird. Der Wert
(z
1
, z
2
) entspricht dem Wert, den man f¨ur die linke Seite der Ungleichung erh¨alt,
wenn man dort f¨ur z entweder z
1
oder z
1
einsetzt. Somit ist (z
1
, z
2
) vergleichbar
mit dem Wert n im k-opt Verfahren. Da durch das Hinzuf¨ugen dieser Unglei-
chung die elliptische Nachbarschaft zwischen zwei L¨osungen aus dem L¨osungsraum
"
herausgeschnitten" wurde, nannten Pigatti et al. diese Bedingungen elliptische
Schnitte.
6
Der Branch-and-Cut-and-Price Algorithmus wird in Kapitel 2.3 behandelt.
-13-
Excerpt out of 100 pages
- scroll top
Look inside the ebook
-
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X.