15 Pufferoptimierung
15.1 Einf¨uhrung
Wichtige Entscheidungsvariablen:
Puffergr¨oßen
Anzahl Server (Maschinen) pro Station
Bearbeitungszeit pro Station
Kombinationen
Es gilt:
Die Anzahl Puffer beeinflußt die Produktionsrate
Die Verteilung der Puffer beeinflußt die Produktionsrate
Daraus folgen die Fragen:
Wie viele Pufferpl¨atze werden insgesamt ben¨otigt?
Wie sollen die Pufferpl¨atze Pufferpl¨atze auf die Stationen verteilt werden?
15.2 Greedy-Verfahren
Wenn die Puffergr¨oßen einen Einfluß auf die Produktionsrate haben, dann stellen sich
folgende Fragen:
Wie viele P ufferpl¨atze sollen in einem Fließproduktionssystem vorgesehen
werden, damit eine angestrebte Produktionsrate erreicht wird?
Wie sieht die optimale Verteilung der Pufferpl¨atze auf die Statio nen aus?
Ist es optimal, an allen Stationen dieselbe Puffergr¨oß e vorzusehen oder ist es
g¨unstiger, eine ungleichm¨aßige Verteilung der Puffer zu ahlen?
Diese Frage soll anhand eines Beispiels aher betrachtet werden.
Nehmen wir an, die Stationen eines Fließproduktionssystems mit M = 5, b
m
= 10,
CV
m
= 0.3 (identische Stationen) sollen durch Puffer entkoppelt werden. Angenommen,
es steht eine gegebene Gesamtanzahl von N = 12 Pufferpl¨atzen zur Verf¨ugung, die nun
auf die einzelnen Stationen verteilt werden soll. Sollen diese Puffer konzentriert plaziert
oder gleichm¨aßig zwischen allen Station verteilt werden?
73
Die folgende Tabelle zeigt die Entwicklung der Produktionsrate bei unterschiedlichen
Allokationen dieser 12 Pufferpl¨atze auf die vier Pufferbereiche.
Prod.-Rate 1 2 3 4 5
0.09553 3 3 3 3
0.09528 4 3 3 2
0.09428 5 3 3 1
0.09116 6 3 3 0
0.09029 7 3 2 0
0.09554 2 4 4 2
Die gr¨oßte Produktionsrate wird also erreicht, wenn man die Puffer so gleichm¨aßig wie
oglich auf die Pufferbereiche verteilt. Man sollte versuchen, durch die Ano r dnung der
Puffer oglichst gleichstarke Segmente zu schaffen.
Soll ein einzelner Pufferplatz eingef¨ugt werden, dann sollte dieser oglichst in das
Zentrum des Fließproduktionssystems eingef ¨ugt werden. Begr¨undung: Ein Pufferplatz
zerteilt das System in zwei Segmente. Je anger ein Segment ist, d. h. je mehr Statio-
nen hintereinandergeschaltet sind, umso st¨arker onnen sich Blockierungs- und Starving-
effekte kumulieren. Je k¨urzer ein Segment ist, umso geringer sind diese Effekte. Die Pro-
duktionsrate des Gesamtsystems wird aber offensichtlich von dem leistungschw¨achsten
Segment bestimmt.
Im folgenden ist ein Optimierungsprotokoll wiedergegeben, das zeigt, wie f¨ur das obige
Fließproduktionssystem beginnend mit 0 Puffern schrittweise jeweils ein zus¨atzlicher
Puffer an der bestm¨oglichen Position hinzugef¨ugt wurde.
Prod.-Rate 1 2 3 4 5
0.07572 -- 0 0 0 0
+ + + Vergr¨osserung der Puffer + + +
Puffer 3: Anstieg: 0.004694 neue Produktionsrate: 0.08042
Aktuelle Gesamtanzahl der Puffer = 1
0.08042 -- 0 1 0 0
+ + + Vergr¨osserung der Puffer + + +
Puffer 4: Anstieg: 0.004620 neue Produktionsrate: 0.08504
Aktuelle Gesamtanzahl der Puffer = 2
0.08504 -- 0 1 1 0
+ + + Vergr¨osserung der Puffer + + +
Puffer 2: Anstieg: 0.001605 neue Produktionsrate: 0.08664
Aktuelle Gesamtanzahl der Puffer = 3
0.08664 -- 1 1 1 0
+ + + Vergr¨osserung der Puffer + + +
Puffer 5: Anstieg: 0.003032 neue Produktionsrate: 0.08967
Aktuelle Gesamtanzahl der Puffer = 4
0.08967 -- 1 1 1 1
+ + + Vergr¨osserung der Puffer + + +
Puffer 3: Anstieg: 0.001406 neue Produktionsrate: 0.09108
Aktuelle Gesamtanzahl der Puffer = 5
0.09108 -- 1 2 1 1
+ + + Vergr¨osserung der Puffer + + +
Puffer 4: Anstieg: 0.001326 neue Produktionsrate: 0.09240
Aktuelle Gesamtanzahl der Puffer = 6
0.09240 -- 1 2 2 1
+ + + Vergr¨osserung der Puffer + + +
Puffer 3: Anstieg: 0.000510 neue Produktionsrate: 0.09291
Aktuelle Gesamtanzahl der Puffer = 7
0.09291 -- 1 3 2 1
+ + + Vergr¨osserung der Puffer + + +
Puffer 5: Anstieg: 0.000681 neue Produktionsrate: 0.09360
74
Aktuelle Gesamtanzahl der Puffer = 8
0.09360 -- 1 3 2 2
+ + + Vergr¨osserung der Puffer + + +
Puffer 2: Anstieg: 0.000746 neue Produktionsrate: 0.09434
Aktuelle Gesamtanzahl der Puffer = 9
0.09434 -- 2 3 2 2
+ + + Vergr¨osserung der Puffer + + +
Puffer 4: Anstieg: 0.000567 neue Produktionsrate: 0.09491
Aktuelle Gesamtanzahl der Puffer = 10
0.09491 -- 2 3 3 2
+ + + Vergr¨osserung der Puffer + + +
Puffer 3: Anstieg: 0.000300 neue Produktionsrate: 0.09521
Aktuelle Gesamtanzahl der Puffer = 11
0.09521 -- 2 4 3 2
+ + + Vergr¨osserung der Puffer + + +
Puffer 4: Anstieg: 0.000330 neue Produktionsrate: 0.09554
Aktuelle Gesamtanzahl der Puffer = 12
0.09554 -- 2 4 4 2
Man erkennt, daß die marginalen Pro duktionsratenzuw¨achse (Grenznutzen der
Puffer) mit zunehmender Gesamtanzahl von Puffern immer kleiner werden.
Produktionsrate
Veränderter Puffer
.07572
.07773
.07973
.08174
.08374
.08575
.08775
.08976
.09176
.09377
.09577
0 3 4 2 5 3 4 3 5 2 4 3 4 2
Die obigen Aussagen treffen allerdings nur f¨ur Systeme zu, in denen die Statio-
nen in jeder Hinsicht identisch sind. In der Praxis unterscheiden sich die Stationen
aber hinsichtlich der Bearbeitungsgeschwindigkeiten oder der St¨orparameter. In diesen
allen m man die Pufferteilung systemsp ezifisch ermitteln und auf die nachfolgend
behandelten Optimierungsmodelle zur¨uckgreifen.
15.3 Optimierungsmodelle
Literaturhinweis
Tempelmeier (2015), Aufgabe A3.15
In einem Zwei-Stationen-System haben wir nur eine Entscheidungsvariable, und zwar
die Goße des einzigen Puffers. Diese kann man solange ver¨andern, bis die gew¨unschte
Produktionsrate erreicht ist. Denn die Produktionsrate ist eine konkave Funktion der
Puffergr¨oße.
So eindeutig ist die Situation bei mehr als einem Pufferbereich nicht mehr. Dies zeigt
das folgende Bild, in dem ein F PS mit drei Stationen betrachtet wird. Es wurden alle
Kombinationsm¨oglichkeiten von 0 bis 10 Puffern auf die beiden Pufferpl¨atze ausgewertet.
75
3-Stationen-System
Produktionsrate v e rs us Anzahl Puffer
0
1
2
3
4
5
Puffer vor Station 2
1
2
3
4
5
Puffer vor Station 3
0.5
0.6
0.7
0.8
Produktionsrate
Primalproblem
Minimiere B =
N
X
n=1
b
n
u. B. d. R.
X(b
1
, b
2
, . . . , b
N
) X
Ziel
Gesucht: Minimale Gesamtanzahl Pufferpl¨atzen bei g egebener Ziel-Produktionsrate X
Ziel
Dualproblem
Maximiere Z = X(b
1
, b
2
, . . . , b
N
)
u. B. d. R.
N
X
n=1
b
n
= B
Gesucht: Optimale Verteilung einer gegebenen Anzahl von B Pufferpl¨atzen auf die Puffer
76
Primalproblem Dualproblem
Gegeben Gesucht
Primalproblem Produktionsrate Mindestanzahl Puffer
Dualproblem Anzahl Puffer Verteilung der Puffer
Pufferoptimierung
osungsmethoden
Pufferoptimierung
Greedy-Verfahren Meta-Heuristiken Lösung des Primal-Problems
Iterative Approximation der
Produktionsfunktion
Lösung des Dualproblems
Gradientenverfahren
Finde optimale Pufferanzahl
Alle Optimierungsmethoden ben¨otigen zur Evalua tion einer o sungsalternative ein Ver-
fahren zur Leistungsanalyse, z.B. ein Dekompositionsverfahren (siehe oben).
15.4 osung d es Dualproblems
Wenn wir das Dualproblem osen wollen, dann onnen wir von einer gegebenen
Pufferkonfiguration mit N Puffern und den Puffergr¨oßen b
1
, b
2
, . . . , b
N
ausgehen und
versuchen, diese zu verbessern. Allerdings stellt sich die Frage, welche Puffer unter der
Bedingung einer konstanten Gesamtpufferzahl B =
P
N
n=1
b
n
vergr¨oßert und welche
verkleinert werden sollen, damit eine Verbesserung der Produktionsrate erreicht wird.
Ziel ist es ja, die Produktionsrate zu maximieren.
Einen Hinweis darauf, welchen Beitrag ein Puffer zur Erh¨o hung der Produktionsrate
liefert, bietet der Gradient (Vektor der partiellen Ableitungen). Da wir keine geschlosse-
nen, stetig differenzierbaren Funktionen betrachten, sondern nur in der Lage sind, die
Produktionsrate als Funktion der Pufferkonfiguration a n einzelnen Punkten auszuwerten,
kann man versuchen, den Gradienten g, also den Vektor der partiellen Ableitungen, zu
approximieren. Der Gradient gibt dann an, um wieviel die Produktionsrate ansteigt,
wenn man die einzelnen Puffer isoliert betrachtet marg inal vergr¨oßert. Man onnte z. B.
den Puffer n isoliert um einen geringen Betrag vergr ¨oßern und den r esultierenden Anstieg
der Produktionsrate f¨ur die Approximation der partiellen Ableitung der Produktionsrate
bez¨uglich der Variablen b
n
verwenden. Zur Berechnung der jeweiligen Produktionsrate
kann z. B. das obige Dekompositionsverfahren eingesetzt werden.
Bildet man aus allen Elementen des Gr adienten den Mittelwert (alle Einzelwerte sind pos-
itiv), dann kann man ur jeden Puffer die A bweichung der partiellen Ableitung vom
77
gemeinsamen Mittelwert errechnen. Diese Abweichungen onnen positiv oder auch
negativ sein. D. h. die Vergr¨oßerung einiger Puffer uhrt zu einem ¨uberdurchschnittlichen
Produktionsratenanstieg, ahrend die Vergr¨oßerung anderer Puffer nur einen unterdurch-
schnittlichen Anstieg der Produktionsrate bringt. Bei der optimalen Pufferverteilung
werden alle partiellen Abweichungen ann¨ahernd gleich sein.
Multipliziert man diesen projizierten Gradienten p mit einem Faktor α und a ddiert
man den resultierenden Vektor zu dem Vektor der Puffergr¨oßen b, da nn bleibt die
gesamte Pufferzahl konstant. Nur die Verteilung der Gesamtanzahl der Puffer
¨andert sich. Dabei werden die Puffer mit negativen p
n
-Werten um α · p
n
verkleinert.
Je gr¨oßer α ist, umso kleiner wird b
n
. Damit kein Puffer negativ wird, darf α einen
Maximalwert nicht ¨uberschreiten. Dies m b ei der Optimierung jeweils ber¨ucksichtigt
werden. Ist die a ktuelle Puffergr¨oße b
n
, dann darf bei einem gegebenen p
n
-Wert der
Wert von α nicht gr¨o ßer als α
max
=
b
n
p
n
sein. Beispiel: p
4
= 0.00110036; b
4
= 4
α
max
=
b
4
p
4
=
4
0.00110036
= 3635.1629. Anmerkung: Da sowohl die b
n
-Werte als auch die
p
n
-Werte weiter unten im Verlauf der Optimierung ver¨andert werden, ¨andert sich auch
α
max
im Verlauf der O ptimierung.
Das folgende Bild zeigt f¨ur ein Fließproduktionssystem mit 10 Puffern (also 11 Statio-
nen) die projizierten Gradienten f¨ur eine gegebene (nicht-optimale) Pufferverteilung. Zur
Bestimmung der marginalen Produktionsratenver¨anderungen wurde jeder Puffer um 0.1
vergr¨oßert.
Projizierter Gradient
2
3
4
5
6
7
8
9
10
Veränderung der Puffer
Verkleinerung Vergrößerung
Die Produktionsrate verl¨auft wie auf dem folgenden Bild dargestellt (hier wurde ein FPS
mit 3 Stationen betra chtet.)
78
Produktionsrate
versus Pufferverteilung
0.470
0.472
0.474
0.476
0.478
0.480
0.482
0.484
0.486
0.488
Produktio
nsrate
4/4 3/5 2/6 1/7 0/8
Pufferverteilung
(vor Station 2/vor Station 3)
N ist die Anzahl der Puffer. g
n
ist ein Element des Gradienten an der Stelle n. Dann
erhalten wir:
Projizierter Gradient
p
n
= g
n
N
P
n=1
g
n
N
Man kann die optimale (produktionsratenmaximale) Pufferverteilung finden, indem man
die aktuelle Projektion mit einem Faktor α multipliziert und zu der aktuellen Puffer-
konfiguration hinzuaddiert. Allerdings m¨ussen die Abscatzungen des Gradienten u. U.
mehrfach aktualisiert werden, da die Steigung der nichtlinearen Zielfunktion an der
jeweils aktuellen Pufferverteilung sich ¨andert und der zuletzt b erechnete Gradient
nur einen ungenauen Hinweis ¨uber die Steigung der Zielfunktion an den weiter entfernten
Stellen gibt.
Das folgende Bild zeigt f¨ur ein System mit 3 Puffern die Verschiebung der Puffergr¨en
zwischen den einzelnen Puffern.
Ver¨anderung der Pufferverteilung
bei konstanter Gesamtanzahl Puffer (= 10)
79
0
1
2
3
4
5
6
7
8
9
10
0 1000 2000 3000
α
Puffer
Zur weiteren Verdeutlichung der Problemstellung betrachten wir ein Beispiel mit drei
Stationen und zwei Puffern mit insgesamt 8 Pufferpl¨atzen. Das folgende Bild zeigt
die Entwicklung der Produktionsrate, wenn man ausgehend von einer Verteilung 4/ 4
(d. h. 4 Puffer vor Station 2 und 4 Puffer vor Station 3) Pufferpl¨atze von Station 2
zur Station 3 hin verschiebt. F¨ur gr¨oßere bzw. andere Systeme sieht die Entwicklung der
Produktionsrate ¨ahnlich aus. Man kann aber davon ausgehen, daß der Verlauf konkav
ist. Dies wurde zwar nicht allgemein bewiesen, ist aber plausibel. F¨ur alle Punkte auf
der Kurve betr¨agt die Gesamtpufferanzahl 8.
Ver¨anderung der Pufferverteilung
Variation von α
0.470
0.472
0.474
0.476
0.478
0.480
0.482
0.484
0.486
0.488
Produktio
nsrate
4/4 3/5 2/6 1/7 0/8
Pufferverteilung
(vor Station 2/vor Station 3)
l=0 (Start)
l=1
aktuelle
Lösung
Wie findet man nun das Maximum dieser Funktion, ohne eine zeitaufwendige
Vollenumeration aller Pufferkombinationen durchzuf¨uhren? Nimmt man an, daß
die Puffergr¨oßen ganzzahlig sind, dann entspricht die Gesamtanzahl oglicher Puffer-
verteilungen der Kombination von B Elementen (Pufferpl¨atzen) zu N = M 1 Klassen
80
(Pufferbereiche zwischen den M Stationen). Sie ist gegeben durch
(B + 1) · (B + 2) ·. . . · (B + M 2)
(M 2)!
Im Beispiel mit B = 8 und M = 3 sind da s
(8 + 1)
1
= 9
Weiter oben haben wir bereits 5 oglichkeiten auf gez¨ahlt. Hinzu kommen noch die nicht
dargestellten Konfigurationen (8/0), (7/1), (6/2) und ( 5/3), die zu den dargestellten
Kombinationen symmetrisch sind.
Ein Verfahren, das mit den o. g. Gradienten arbeitet, sieht wie folgt aus:
1. Ausgangspunkt ist eine Startl¨osung, d. h. eine gegebene Pufferverteilung
B = (b
1
, b
2
, . . . , b
N
). Eine oglichkeit besteht darin, die Puffer gleichm¨aßig
zu verteilen.
2. Man berechnet den Gradienten g an dieser Stelle. Dabei geht man von
kontinuierlich variierbaren Puffern aus.
3. Man bestimmt dann folgende Projektion des Gradienten:
p
n
= g
n
N
P
n=1
g
n
N
(14)
Einige der p
n
-Werte sind negativ und einige sind posit iv. Multipliziert
man den Vektor p mit einer Konstanten α, und addiert man das Pro-
dukt zu der aktuellen Pufferkonfiguration b, dann entspricht das einer
Umverteilung der Puffer bei konstanter Gesamtanzahl B.
Wir haben es daher nur noch mit einem nichtlinearen Maximierungs-
problem mit einer Entscheidungsvariablen α zu tun.
Wie oben erw¨ahnt, muß allerdings ber¨ucksichtigt werden, da ß durch die
Ver¨onderung der osung kein Puffer negativ wird. Die schrittweise Ver-
lagerung der Puffergr¨oßen als Funktion der Entscheidungsvariablen α
bei konstanter Gesamtanzahl der Puffer ist in den folgenden Bilder dargestellt.
Ver¨anderung der Pufferverteilung
Variation von α
81
0.470
0.472
0.474
0.476
0.478
0.480
0.482
0.484
0.486
0.488
Produktio
nsrate
4/4 3/5 2/6 1/7 0/8
Pufferverteilung
(vor Station 2/vor Station 3)
l=0 (Start)
l=1
aktuelle
Lösung
l=2
nächste
Lösung
Ver¨anderung der Pufferverteilung
Variation von α
0.470
0.472
0.474
0.476
0.478
0.480
0.482
0.484
0.486
0.488
Produktio
nsrate
4/4 3/5 2/6 1/7 0/8
Pufferverteilung
(vor Station 2/vor Station 3)
l=0 (Start)
l=1
l=2
aktuelle
Lösung
l=3
nächste
Lösung
max
Ver¨anderung der Pufferverteilung
Variation von α
82
0.470
0.472
0.474
0.476
0.478
0.480
0.482
0.484
0.486
0.488
Produktionsrate
4/4 3/5 2/6 1/7 0/8
Pufferverteilung
(vor Station 2/vor Station 3)
l=0 (Start)
l=1
l=2
aktuelle
Lösung
l=3
nächste
Lösung
max
Ver¨anderung der Pufferverteilung
Variation von α
0.470
0.472
0.474
0.476
0.478
0.480
0.482
0.484
0.486
0.488
Produktionsrate
4/4 3/5 2/6 1/7 0/8
Pufferverteilung
(vor Station 2/vor Station 3)
l=0 (Start)
l=1
l=2
aktuelle
Lösung
l=3
nächste
Lösung
max
In den Bilder kann man erkennen, daß sich die Obergrenze f¨ur α dynamisch ver¨andert.
Wir betrachten jetzt ein Beispiel, wobei deterministischen Bearbeitungszeiten und Maschi-
nenausf¨alle angenommen werden. Die numerischen Berechnungen der Produktionsraten
der verschiedenen Systemkonfigurationen onnen nicht mit dem obigen Dekompo si-
tionsverfahren nachvollzogen werden, da dort exponentialverteilte Bearbeitungszeiten
und keine Maschinenausf¨alle unterstellt wurden.
Da wir uns j etzt auf das Verfahren zur osung des Dualproblems konzentrieren, gehen
wir einfach davon an, daß wir in der Lage sind, die Produktionsrate f¨ur jede Systemkon-
figuration auszurechnen.
83
Beispiel
Daten
Station m Puffer-
gr¨oße
Bearbei-
tungsrate
Ausfall-
rate
Reparatur-
rate
1 1.000000 0.1 1.000000
2 0 1.000000 0.1 1.000000
3 6 1.000000 0.1 1.000000
4 4 1.000000 0.1 1.000000
Beispiel
Gradient
m Puffer g
m
2 0.0 0.00328809
3 6.0 0.00017786
4 4.0 0.00008243
Summe 0.00354838
Durchschnitt 0.001182793
Der Wert g
1
ergibt sich als X(0.1, 6, 4) X(0, 6, 4). g
2
= X(0, 6.1, 4) X(0, 6, 4), usw.
Beispiel
Berechnung der Projektion des Gradie nten
m g
m
p
m
2 0.00328809 0.00328809 0.001182793 = 0.00 210530
3 0.00017786 0.00017786 0.001182793 = -0 .00100493
4 0.00008243 0.00008243 0.001182793 = -0 .00110036
Man kann nun eines der bekannten Verfahren zur Maximierung einer nichtlinearen
Funktion einer unabh¨angigen Variablen (hier α) einsetzen. Um den Suchbereich
einzugrenzen, kann man ausgehend von einem kleinen Startwert α iterativ solang e
verdoppeln, bis der Funktionswert (d. h. die Produktionsrate) wieder sinkt.
Im vorliegenden Beispiel wird ein Startwert α =
1
0.00210530
= 474.99244 festgelegt und
dieser dann in jeder Iteration verdoppelt. Andere Vorgehensweisen sind oglich.
Beispiel
Neue Pufferverteilung
b
= b
0
+ α
·p
84
Durch die Addition des α
-fachen der Projektion des Gradienten zu den aktuellen Puffern
¨andert sich die Gesamtanzahl der Pufferpl¨atze nicht, da die Summe der Elemente des
Vektors p gleich 0 ist.
Beispiel
Pufferverteilungen (Zwischenergebnisse)
Iteration 1 2 3
α
474.99244 949.98488 1899.96976
m 2 1.00000 2.00000 4.00000
3 5.52266 5.04533 4.09066
4 3.47734 2.95467 1.90934
X 0.8482202 0.8551133 0.8542113
Summe 10 10 10
Nach dem ersten Verfahrensschritt kann man dann die Suche weiter verfeinern. Das
folgende Bild zeigt die Ergebnisse, wenn man α mit dem Verfahren des Goldenen
Schnittes (Golden-Section-Search) festlegt.
Fazit: Man hat das Problem in ein nichtlineares Optimierungsproblem mit einer Vari-
ablen transformiert und kann dann im Prinzip ein beliebiges Suchverfahren einsetzen.
Bei jeder Ver¨anderung der Pufferverteilung muß man dann jeweils die Produktionsrate
bestimmen. Hierzu setzt man Verfahren zur Leistungsanalyse des betrachteten Fließpro-
duktionssystems ein.
Beispiel
Zielfunktionsverlauf
0.81
0.82
0.83
0.84
0.85
0.86
Produktionsrate
0 1000 2000 3000
α
1
2
3
4
5
6
7
8
9
l=1
l=2
l=3
Beispiel
osung n ach Abschluß der Golden-Section-Search
85
m Puffer alt Puffer neu
2 0 2.85400
3 6 4.63768
4 4 2.50832
Summe 10 10
Jetzt haben wir eine neue osung gefunden.
Beispiel
Wie geht es weiter?
Es folgen weitere Iterationen mit folgenden Schritten:
1. Gradienten f¨ur die neue Pufferkonfiguration berechnen und pr¨ufen, ob die q
n
-Werte
ann¨ahernd gleich sind.
Wenn ja, STOP.
Wenn nein:
Projektion berechnen
α variieren und neue Pufferverteilung bestimmen, usw.
Gehe zu Schritt 1.
86