Teil XIV
Losgr¨oßen- und
Ressourceneinsatzplanung
35 Kapazit¨atsorientiertes PPS-System
KPPS
Bau-
stellen-
produktion
Werk-statt-
produktion
Zentren-
produktion
Fließ-
produktion
JIT-
Produktion
...
Vernetzte Produktionssegmente
Kapazitätsorientiertes PPS-System
Segment-spezifische
Feinplanung und
-steuerung
Aggregierte Gesamtplanung
Kapazitiertes
Hauptproduktions-
programm
Detaillierte Losgrößen-
und Ressourcenein-
satzplanung
191
Teil XV
Operative Planung bei
Werkstattproduktion
Achtung
Zur dynamischen Losgr¨oßenplanung bei Werkstattproduktion (Makroperiodenmodelle,
”big bucket”-Modelle) siehe Vorlesung SCMP III.
36 Durchlauft erminimierung
Literaturhinweis
Tempelmeier (20 15), Teil B, Abschnitt 3
Losgr¨oßenplanung Terminplanung
A1
A2
A3
A4
A5
A6
A7
B1
A3 B2
A2
A1
C1
Kapazitäts-
orientierte
Losgrößen-
planung
Ressourcen-
einsatzplanung
Wochen
Tage/Stunden
Eilaufträge
Aufträge für B- und C-Produkte
M2
M1
Sp¨atestzul¨assige Einplanung
192
A1
5
A2
7
A3
11
B1
8
B2
7
P
8
Wunschterminspätestzulässiger Starttermin
"Heute" = frühestmöglicher Starttermin
Einzelteil B
Einzelteil A
Endprodukt
Fr¨uhestm¨ogliche Einplanung
A1
5
A2
7
A3
11
B1
8
B2
7
P
8
Pufferzeit
(bei spätestzulässigem
Start von A und P)
Wunschterminspätestzulässiger Starttermin
"Heute" = frühestmöglicher Starttermin
Einzelteil B
Einzelteil A
Endprodukt
Auftragsnetz
P
BA
A1: Drehen
A2: Bohren
A3: Qualitätskontrolle
B1: Fräsen
B2: Bohren
P: Montage
A1
5
A2
7
A3
11
B1
8
B2
7
P
8
193
36.1 Symbole
Symbole
d
j
Dauer des Arbeitsgangs j
d
jn
zeitlicher Mindestabstand zwischen dem Ende des Arbeitsgangs j
und dem Beginn des Arbeitsgangs n, z. B. zur Ber¨ucksichtigung von
Transportzeiten
FAZ
j
fr¨uhestm¨oglicher Anfan gszeitpunkt des Arbeitsgangs j
FEZ
j
fr¨uhestm¨oglicher En dzeitpunkt des Arbeitsgangs j
N
j
Indexmenge der direkten Nachfolger des Arbeitsgangs j
SAZ
j
sp¨atestzul¨assiger Anfangszeitpunkt des Arbeitsgangs j
SEZ
j
sp¨atestzul¨assiger Endzeitpunkt des Arbeitsgangs j
V
j
Indexmenge der direkten Vorg¨anger des Arbeitsgangs j
36.2 Vorw¨artsrechung
Vorw¨artsrechnung
FAZ
0
= 0
FEZ
j
= FAZ
j
+ d
j
FAZ
j
= max
v∈V
j
FEZ
v
+ d
vj
AG j
Vorgänger
Vorgänger
Nachfolger
FAZ j
194
36.3 R¨uckw¨artsrechnung
R¨uckw¨artsrechnung
SEZ
J
= FEZ
J
SAZ
j
= SEZ
j
d
j
SEZ
j
= min
n∈N
j
SAZ
n
d
jn
AG j
Nachfolger
SEZ j
NachfolgerVorgänger
Pufferzeiten
GP
j
= SAZ
j
FAZ
j
= SEZ
j
FEZ
j
36.4 Beispiel
Beispiel
195
Arbeitsgang j Dauer FAZ
j
FEZ
j
SAZ
j
SEZ
j
GP
j
A1 5 0 5 0 5 0
A2 7 5 12 5 12 0
A3 11 12 23 12 23 0
B1 8 0 8 8 16 8
B2 7 8 15 16 23 8
P 8 23 31 23 31 0
Beispiel ¨uberlappte Produktion (d
A3,P
= 2)
Arbeitsgang j Dauer FAZ
j
FEZ
j
SAZ
j
SEZ
j
GP
j
A1 5 0 5 0 5 0
A2 7 5 12 5 12 0
A3 11 12 23 12 23 0
B1 8 0 8 6 14 6
B2 7 8 15 14 21 6
P 8 21 29 21 29 0
Termine fr¨uhestm¨oglich/sp¨atestzul¨assig
5 10 15 20 25
Zeit
B1
B2
A1
A2
A3
P
-----
B1
B2
A1
A2
A3
P
Vorgang
B1
B2
A1
A2
A3
P
oben - frühestmöglich, unten - spätestzulässig
B1
B2
A1
A2
A3
P
Kapazit¨atsbelastung
196
A1
5
A2
7
A3
11
B1
8
B2
7
P
8
Einzelteil B
Einzelteil A
Endprodukt
A3
B2
Zeit
verfügbare Kapazität
A3 und B2 werden von derselben Ressource durchgeführt
Anpassung der Kapazit¨aten
Zeitliche Anpassung
Intensit¨atsm¨aßige Anpassung
Quantitative Anpassung
37 Kapazit¨atsorientierte Terminplanung (RCPSP)
37.1 Einf¨uhrung
Gemeinsamer Netzplan f¨ur zwei Auftr¨age
Auftrag B
B1
B2
7
6
B3
5
Auftrag A
Q
A1
A2
S
3
9
A3
4
Literaturhinweis
Tempelmeier (20 15), Teil B, Abschnitt 3
197
37.2 Beispiel
Ergebnisse der Zeitplanung
Arbeitsgang j Dauer FAZ
j
FEZ
j
SAZ
j
SEZ
j
GP
j
Q 0 0 0 0 0 0
A1 3 0 3 6 9 6
A2 9 0 9 0 9 0
A3 4 9 13 9 13 0
B1 7 0 7 1 8 1
B2 6 0 6 2 8 2
B3 5 7 12 8 13 1
S 0 13 13 13 13 0
Netzplan mit Ergebnissen
der Durchlaufterminierung
Q
0
0
0
0
0
A1
0
3
6
9
3
A2
0
9
0
9
9
A3
9
13
9
13
4
B1
0
7
1
8
7
B2
0
6
2
8
6
B3
7
12
8
13
5
S
13
13
13
13
0
0
0
0
0
0
0
0
0
0
0
Legende:
FAZ
j
SAZ
j
FEZ
j
SEZ
j
Dauer
Gantt-Chart bei unbeschr¨ankten Kapazit¨aten aller Ressourcen
Belastung der Ressource 2
198
Begrenzte Kapazit¨at der Ressource 2 (AG 2 und 6)
Einplanung nach LOZ- Regel
Begrenzte Kapazit¨at der Ressource 2 (AG 2 und 6)
Einplanung nach KOZ-Regel
Begrenzte Kapazit¨aten: Ressource 1 (AG 2 und 6)
Ressource 2 (alle anderen AG)
199
37.3 Modellformulierung
Modell RCPSP
Zielfunktion
Minimiere Z =
SEZ
J
P
t=FEZ
J
t · x
Jt
Fertigstellungstermin des
Auftragsnetzes (Zykluszeit)
Literaturhinweis
Tempelmeier (20 15), Teil B, Aufgabe B3.3
G¨unther and Tempelmeier (2016), Abschnitt 11.1.4
Modell RCPSP
Nebenbedingungen
u. B. d. R.
SEZ
j
P
t=FEZ
j
x
jt
= 1 j = 1, 2, ..., J
SEZ
h
P
t=FEZ
h
t · x
ht
SEZ
j
P
t=FEZ
j
(t d
j
)·x
jt
j = 1, 2, ..., J; h V
j
J
P
j=1
k
jr
·
t+d
j
1
P
q=t
x
jq
K
r
r = 1, 2, ..., R; t = 1, 2, ..., T
200
Erl¨auterung der Reihenfolgebedingung
t
h
t
j
d
j
t
h
=
SEZ
h
P
t=FEZ
h
t · x
ht
t
j
=
SEZ
j
P
t=FEZ
j
t · x
jt
Fertigstellungsperiode und Kapazit¨atsbelastung
t
3 4 5 6 7 8 9
x
jq
q = t, t + 1, ..., t + d
j
1
Optimale osung bei ver¨andertem Liefertermin
und Ressourcenkonkurrenz der Arbeitsg¨ange A1, B2 und B3
S
B 3
B 2
B 1
A3
A2
A1
Q
1
1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1
1
1
1
1
1
Periode
37.4 Heuristische osungsverfahren
Literaturhinweis
201
Tempelmeier (20 15), Teil B, Aufgabe B3.4
Kapazit¨atsbelastungsausgleich
Belastung
Periode
A
B
C
Kapazität
Ressourcen
37.4.1 Priorit¨atsregelverfahren
Heuristisches osungsverfahren
Initialisierung
Mengen An ( begonnen) = {}
Mengen Cn (fertig) = {}
D n (einplanbar) = {}
F
r
= K
r
(r = 1, 2, ..., R) ( Freie Kapazit¨at)
t := 0
Schritt 1: Einplanung aller zum Zeitpunkt t einplanbaren AG
a) Ermittle die aktuell einplanbaren Vor g¨ange unter Beachtung der Projektstruk-
tur und der Kapazit¨aten der Ressourcen. Falls die Menge Dn leer ist, gehe zu
Schritt 2.
b) Lege Priorit¨atswerte der einplanbaren AG fest
c) Auswahl des achsten AG j gem¨ Priorit¨aten
d) Einplanung des AG j: Starttermin(j) = t Endtermin(j) = t + d(j) Restka-
pazit¨at der Ressource r: F
r
= F
r
k
jr
Menge der begonnenen AG: An An+j
Gehe zu Schritt 1a
Schritt 2: achster Einplanungszeitpunkt
a) Falls An und Cn alle Auftr¨age enthalten, Stop.
202
b) Falls An = {}, Stop, keine zul¨assige osung.
c) Bestimme den Termin t, an dem der achste AG aus der Menge An fertig
wird. Entferne alle AG mit Fertigstellungstermin t aus der Menge An, f¨uge
sie in die Menge Cn ein und erh¨ohe die Restkapazit¨at der jeweils betroffenen
Ressource um die freigebenen Kapazit¨atseinheiten. Gehe zu Schritt 1a
37.5 Beispiel
Das folgende Beispiel mit einer R essource wurde mit dem Produktions-Management-
Trainer erzeugt.
Beispieldaten
Vorgang j Dauer d
j
Ressource r k
jr
r K
r
AG-1 0 1 1 1 1
AG-2 3 1 1
AG-3 9 1 1
AG-4 4 1 1
AG-5 7 1 1
AG-6 6 1 1
AG-7 5 1 1
AG-8 0 1 1
Netzplan
203
Ergebnis der Durchlaufterminierung
Vorgang FAZ(i) FEZ(i) SAZ(i) SEZ(i) GP(i)
AG-1 0 0 0 0
AG-2 0 3 6 9 6
AG-3 0 9 0 9 0
AG-4 9 13 9 13 0
AG-5 0 7 1 8 1
AG-6 0 6 2 8 2
AG-7 7 12 8 13 1
AG-8 13 13 13 13 0
Ergebnis der Durchlaufterminierung
Ablauf der Berechnungen: Sortierkriterium: K¨urzeste Operationszeit
Schritt 1: Periode t = 0
Vorgang AG-1 wird in Menge Dn eingef¨ugt
Aktuelle Mengen f¨ur t = 0
Menge An =
Menge Cn =
Menge Dn = {AG-1}
204
Einplanung von Vorgang AG-1 auf Ressource 1
Start 0 Ende 0
Vorgang AG-1 in Menge An einf¨ugen
Schritt 1: Periode t = 0
Aktuelle Mengen f¨ur t = 0
Menge An = {AG-1}
Menge Cn =
Menge Dn =
205
Schritt 2:
Vorgang AG-1 Ende 0
Vorgang AG-1 in Menge Cn einf¨ugen
Schritt 1: Periode t = 0
Vorgang AG-2 wird in Menge Dn eingef¨ugt
Vorgang AG-3 wird in Menge Dn eingef¨ugt
Vorgang AG-5 wird in Menge Dn eingef¨ugt
Vorgang AG-6 wird in Menge Dn eingef¨ugt
Aktuelle Mengen f¨ur t = 0
Menge An =
Menge Cn = {AG-1}
Menge Dn = {AG-2,AG-3,AG-5,AG- 6}
Einplanung von Vorgang AG-2 auf Ressource 1
Start 0 Ende 3
Vorgang AG-2 in Menge An einf¨ugen
Schritt 1: Periode t = 0
Aktuelle Mengen f¨ur t = 0
Menge An = {AG-2}
Menge Cn = {AG-1}
Menge Dn =
206
Schritt 2:
Vorgang AG-2 Ende 3
Vorgang AG-2 in Menge Cn einf¨ugen
Schritt 1: Periode t = 3
Vorgang AG-3 wird in Menge Dn eingef¨ugt
Vorgang AG-5 wird in Menge Dn eingef¨ugt
Vorgang AG-6 wird in Menge Dn eingef¨ugt
Aktuelle Mengen f¨ur t = 3
Menge An =
Menge Cn = {AG-1,AG-2}
Menge Dn = {AG-3,AG-5,AG-6}
207
Einplanung von Vorgang AG-6 auf Ressource 1
Start 3 Ende 9
Vorgang AG-6 in Menge An einf¨ugen
Schritt 1: Periode t = 3
Aktuelle Mengen f¨ur t = 3
Menge An = {AG-6}
Menge Cn = {AG-1,AG-2}
Menge Dn =
Schritt 2:
Vorgang AG-6 Ende 9
Vorgang AG-6 in Menge Cn einf¨ugen
Schritt 1: Periode t = 9
Vorgang AG-3 wird in Menge Dn eingef¨ugt
Vorgang AG-5 wird in Menge Dn eingef¨ugt
Aktuelle Mengen f¨ur t = 9
Menge An =
Menge Cn = {AG-1,AG-2,AG-6}
Menge Dn = {AG-3,AG-5}
208
Einplanung von Vorgang AG-5 auf Ressource 1
Start 9 Ende 16
Vorgang AG-5 in Menge An einf¨ugen
Schritt 1: Periode t = 9
Aktuelle Mengen f¨ur t = 9
Menge An = {AG-5}
Menge Cn = {AG-1,AG-2,AG-6}
Menge Dn =
209
Schritt 2:
Vorgang AG-5 Ende 16
Vorgang AG-5 in Menge Cn einf¨ugen
Schritt 1: Periode t = 16
Vorgang AG-3 wird in Menge Dn eingef¨ugt
Vorgang AG-7 wird in Menge Dn eingef¨ugt
Aktuelle Mengen f¨ur t = 16
Menge An =
Menge Cn = {AG-1,AG-2,AG-6,AG-5}
Menge Dn = {AG-3,AG-7}
Einplanung von Vorgang AG-7 auf Ressource 1
Start 16 Ende 21
Vorgang AG-7 in Menge An einf¨ugen
Schritt 1: Periode t = 16
Aktuelle Mengen f¨ur t = 16
Menge An = {AG-7}
Menge Cn = {AG-1,AG-2,AG-6,AG-5}
Menge Dn =
210
Schritt 2:
Vorgang AG-7 Ende 21
Vorgang AG-7 in Menge Cn einf¨ugen
Schritt 1: Periode t = 21
Vorgang AG-3 wird in Menge Dn eingef¨ugt
Aktuelle Mengen f¨ur t = 21
Menge An =
Menge Cn = {AG-1,AG-2,AG-6,AG-5,AG-7}
Menge Dn = {AG-3}
211
Einplanung von Vorgang AG-3 auf Ressource 1
Start 21 Ende 30
Vorgang AG-3 in Menge An einf¨ugen
Schritt 1: Periode t = 21
Aktuelle Mengen f¨ur t = 21
Menge An = {AG-3}
Menge Cn = {AG-1,AG-2,AG-6,AG-5,AG-7}
Menge Dn =
Schritt 2:
Vorgang AG-3 Ende 30
Vorgang AG-3 in Menge Cn einf¨ugen
Schritt 1: Periode t = 30
Vorgang AG-4 wird in Menge Dn eingef¨ugt
Aktuelle Mengen f¨ur t = 30
Menge An =
Menge Cn = {AG-1,AG-2,AG-6,AG-5,AG-7,AG-3}
Menge Dn = {AG-4}
212
Einplanung von Vorgang AG-4 auf Ressource 1
Start 30 Ende 34
Vorgang AG-4 in Menge An einf¨ugen
Schritt 1: Periode t = 30
Aktuelle Mengen f¨ur t = 30
Menge An = {AG-4}
Menge Cn = {AG-1,AG-2,AG-6,AG-5,AG-7,AG-3}
Menge Dn =
213
Schritt 2:
Vorgang AG-4 Ende 34
Vorgang AG-4 in Menge Cn einf¨ugen
Schritt 1: Periode t = 34
Vorgang AG-8 wird in Menge Dn eingef¨ugt
Aktuelle Mengen f¨ur t = 34
Menge An =
Menge Cn = {AG-1,AG-2,AG-6,AG-5,AG-7,AG-3,AG-4}
Menge Dn = {AG-8}
Einplanung von Vorgang AG-8 auf Ressource 1
Start 34 Ende 34
Vorgang AG-8 in Menge An einf¨ugen
Schritt 1: Periode t = 34
Aktuelle Mengen f¨ur t = 34
Menge An = {AG-8}
Menge Cn = {AG-1,AG-2,AG-6,AG-5,AG-7,AG-3,AG-4}
Menge Dn =
Da die Menge Dn leer ist, wird das Verfahren beendet.
Start Ende
AG-1 0 0
AG-2 0 3
AG-3 21 30
AG-4 30 34
AG-5 9 16
AG-6 3 9
AG-7 16 21
AG-8 34 34
214
osung
Kapazit¨at=1
Erh¨oht man die Kapazit¨at, dann verk¨urzt sich die Zykluszeit. Dies zeigt das folg ende
Bild.
osung
Kapazit¨at=2
215