12 Das dynamische einstufige Mehr-Produkt-Losgr¨oßenproblem
Modellvarianten
• Mikroperioden-Modelle (Losgr¨oßen- und Reihenfolgen)
• Makroperioden-Modelle (Losgr¨oßen)
12.1 Modellformulierungen
Modell CLSP – ein Makroperioden-Modell
Minimiere Z =
K
X
k=1
T
X
t=1
s
k
·γ
kt
+ h
k
·y
kt
+ p
kt
· q
kt
u. B. d. R.
y
k,t−1
+ q
kt
− y
kt
= d
kt
k = 1, 2, ..., K; t = 1, 2, ..., T
q
kt
− M ·γ
kt
≤ 0 k = 1, 2, ..., K; t = 1, 2, ..., T
CLSP II
K
X
k=1
tb
jk
· q
kt
+ tr
jk
·γ
kt
≤ b
jt
j = 1, 2, ..., J; t = 1, 2, ..., T
K
X
k=1
tb
jk
· q
kt
≤ b
jt
j = 1, 2, ..., J; t = 1, 2, ..., T
K
X
k=1
tb
k
· q
kt
≤ b
t
t = 1, 2, ..., T
Standardformulierung des CLSP
• LP-Relaxation bringt sehr schlechte untere Schranken
• Daher Reformulierungen auf der Basis des K¨urzeste-Wege-Problems und des klassischen unkapaz-
itierten Standortproblems
• Erweiterungsm¨oglichkeiten
38
Standortformulierung des CLSP: Modell CLSP
SPL
Minimiere Z =
K
X
k=1
T
X
t=1
s
k
· γ
kt
+
K
X
k=1
T
X
t=1
T
X
τ =t
h
ktτ
· δ
ktτ
u. B. d. R.
τ
X
t=1
δ
ktτ
= 1 k = 1, 2, . . . , K; τ = 1, 2, . . . , T
δ
ktτ
≤ γ
kt
k = 1, 2, . . . , K; t = 1, 2, . . . , T ; τ = t, t + 1, . . . , T ; d
kτ
> 0
X
k∈K
j
"
T
X
τ =t
tb
k
·d
kτ
· δ
ktτ
+ tr
k
·γ
kt
#
≤ b
jt
j = 1, 2, . . . , J;
t = 1, 2, . . . , T
δ
kτ t
≥ 0 k = 1, 2, . . . , K; τ = 1, 2, . . . , T ; t = τ, τ + 1, . . . , T
γ
kτ
∈ {0, 1} k = 1, 2, . . . , K; τ = 1, 2, . . . , T
Set-Partitioning-Modell
Minimiere Z =
K
X
k=1
X
i∈P
k
c
i
·γ
i
u. B. d. R.
K
X
k=1
X
i∈P
k
κ
ij t
·γ
i
≤ b
jt
j = 1, 2, . . . , J; t = 1, 2, . . . , T
X
i∈P
k
γ
i
= 1 k = 1, 2, . . . , K
12.2 Das ABC-Verfahren von Maes
Vorw¨artseinplanung – Zul¨assigkeit
39
3
2
1
3
2
1
aktuelle Periode
3
2
1
CF
τ
j
bereits eingeplante
Produktionsperioden
j
Periode
Kapazität
Produkt 1
Produkt 2
Produkt 3
CN
τ
j
CB
j
CV
τ
b
j
τ
Prinzipielle Vorgehensweise
Umformung einer Tabelle mit Bedarfsme ngen
d
kt
1 2 3 4 5 6 7 8 9 10
1 x x x – x – – x – x
2 – x x – x x – x x x
3 x – x – x – x x x –
4 x x x – – – x x x –
in eine Tabelle von Produktionsmengen
d
kt
1 2 3 4 5 6 7 8 9 10
1 X – – – – – – – – X
2 – – – – X – – – – X
3 – – – – – – – X – –
4 – X – – – – – – – –
Entscheidungen
• Reihenfolge der Produkte (A)
• Kostenkriterium (B)
• Richtung (C)
Vorzuziehe n de Produktionsmeng en
CF
T
= 0
CF
t
= max
n
0,
K
X
k=1
tb
k
· d
k,t+1
− b
t+1
+ CF
t+1
o
40
Beispiel
k \ t 1 2 3 4 5 6
1 110 49 0 82 40 65
2 48 75 15 10 15 70
b
t
160 160 160 160 120 120
Iteration τ = 1, I
nicht fixiert
k \ t 1 2 3 4 5 6
1 110 49 0 82 40 65
2 48 75 15 10 15 70
W
t
158 124 15 92 55 135
I
t
2 36 145 68 65 -15
CF
t
0 0 0 0 15 0
Iteration τ = 1, II
nicht fixiert
k \ t 1 2 3 4 5 6
1 110 49 0 82 40 65
2 48 75 15 10 15 70
I
t
2 36 145 68 65 -15
Iteration τ = 1, III
nicht fixiert
k \ t 1 2 3 4 5 6
1 110 49 0 82 40 65
2 48 75 15 10 15 70
I
t
2 36 145 68 65 -15
Iteration τ = 1, Aktueller Produktionsplan
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 75 15 10 15 70
41
Iteration τ = 2, I
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 75 15 10 15 70
I
t
2 36 145 68 65 -15
CF
t
0 0 0 0 15 0
Iteration τ = 2, II
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 75 15 10 15 70
I
t
2 36 145 68 65 -15
CF
t
0 0 0 0 15 0
Iteration τ = 2, III
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 75 15 10 15 70
I
t
2 36 145 68 65 -15
CF
t
0 0 0 0 15 0
Iteration τ = 2, IV
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 75 15 10 15 70
I
t
2 36 145 68 65 -15
CF
t
0 0 0 0 15 0
c
P er
222
50
c
P er
223
32.5
Iteration τ = 2, V
42
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 90 0 10 15 70
I
t
2 21 160 68 65 -15
CF
t
0 0 0 0 15 0
Iteration τ = 2, VI
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 90 0 10 15 70
I
t
2 21 160 68 65 -15
CF
t
0 0 0 0 15 0
c
P er
223
32.5
c
P er
224
28.33
Iteration τ = 2, VII
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 100 0 0 15 70
I
t
2 11 160 78 65 -15
CF
t
0 0 0 0 15 0
Iteration τ = 2, Aktueller Produktionsplan
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 100 0 0 15 70
I
t
2 11 160 78 65 -15
CF
t
0 0 0 0 15 0
Iteration τ = 3, Aktueller Produktionsplan
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 100 0 0 15 70
I
t
2 11 160 78 65 -15
CF
t
0 0 0 0 15 0
43
Iteration τ = 4, I
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 100 0 0 15 70
I
t
2 11 160 78 65 -15
CF
t
0 0 0 0 15 0
Iteration τ = 4, II
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 100 0 0 15 70
I
t
2 11 160 78 65 -15
CF
t
0 0 0 0 15 0
c
P er
144
100
c
P er
145
130
Iteration τ = 5, I
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 100 0 0 15 70
I
t
2 11 160 78 65 -15
CF
t
0 0 0 0 15 0
Iteration τ = 5, II
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 100 0 0 15 70
I
t
2 11 160 78 65 -15
CF
t
0 0 0 0 15 0
c
P er
155
100
c
P er
156
180
Iteration τ = 5, III
44
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 100 0 0 15 70
I
t
2 11 160 78 65 -15
CF
t
0 0 0 0 15 0
Iteration τ = 5, IV
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 100 0 0 15 70
I
t
2 11 160 78 65 -15
CF
t
0 0 0 0 15 0
Iteration τ = 5, V
fixiert nicht fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 100 0 0 30 55
I
t
2 11 160 78 50 0
CF
t
0 0 0 0 0 0
Iteration τ = 6, I
fixiert
nicht
fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 100 0 0 30 55
I
t
2 11 160 78 50 0
CF
t
0 0 0 0 0 0
Iteration τ = 6, L¨osung
fixiert
t 1 2 3 4 5 6
q
1t
110 49 0 82 40 65
q
2t
48 100 0 0 30 55
45