Extrait
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-
Fin de l'extrait de 100 pages
- Citation du texte
- Christoph Holzbaur (Auteur), 2006, Neue Lösungsansätze für das Generalized-Assignment-Problem, Munich, GRIN Verlag, https://www.grin.com/document/186357
Textes similaires
Devenir un auteur
✕
Extrait de
100
pages
Commentaires