Generierung von Personaleinsatzplänen in Dienstleistungsunternehmen: Reformulierung von Entscheidungsproblemen und deren Lösung


Diplomarbeit, 2010

151 Seiten


Gratis online lesen

Wissenschaftliche Arbeit zur Erlangung des Grades eines
Diplom-Kaufmann
an der Technischen Universität zu München
Generierung von Personaleinsatzplänen in
Dienstleistungsunternehmen: Reformulierung
von Entscheidungsproblemen und deren
Lösung
Studiengang:
TUM-BWL Diplom
Eingereicht von:
Jan Mathias Köhler
Eingereicht am:
München, 01. Februar 2010

Inhaltsverzeichnis
Tabellenverzeichnis
iii
Abbildungsverzeichnis
vi
Abkürzungsverzeichnis
vii
Symbolverzeichnis - Allgemein und MIP
viii
Symbolverzeichnis - DP
xi
1 Einleitung
1
2 Literaturüberblick
6
3 Beschreibung des Schichtplanungsproblems
11
3.1
Begriffe der Schichtplanung
. . . . . . . . . . . . . . . . . . . . 11
3.2
Spaltengenerierungsverfahren zur Lösung der Schichtplanung . . 12
3.3
Nebenbedingungen der Schichtplanung . . . . . . . . . . . . . . 14
4 Formulierung als Kürzeste Wege Problem
15
4.1
Beschreibung des Graphen . . . . . . . . . . . . . . . . . . . . . 15
4.2
Erweiterung um Ressourcenbeschränkungen . . . . . . . . . . . 18
5 Gemischt ganzzahliges Programm
21
5.1
Beschreibung des grundlegenden MIPs . . . . . . . . . . . . . . 21
5.1.1
Notation des MIPs . . . . . . . . . . . . . . . . . . . . . 21
5.1.2
Erläuterung des MIPs . . . . . . . . . . . . . . . . . . . 24
5.1.3
Relaxierung der Ressourcenvariablen . . . . . . . . . . . 27
5.2
Einführung weiterer Nebenbedingungen . . . . . . . . . . . . . . 28
5.2.1
Berücksichtigung eines Dienstes . . . . . . . . . . . . . . 29
5.2.2
Berücksichtigung von Überstunden und Fehlstunden . . . 33
5.2.3
Berücksichtigung einer Mittagspause . . . . . . . . . . . 36
5.2.4
Berücksichtigung eines Zeitfensters . . . . . . . . . . . . 39
5.2.5
Werte des vorherigen Planungshorizonts . . . . . . . . . 40
5.3
Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.4
Komplexität des RCSPs . . . . . . . . . . . . . . . . . . . . . . 43
6 Dynamisches Programm
45
6.1
Einführung in die dynamische Programmierung . . . . . . . . . 45
6.2
Beschreibung des grundlegenden DPs . . . . . . . . . . . . . . . 50
6.2.1
Modellierung des RCSPs als DP . . . . . . . . . . . . . . 51
6.2.2
Induktionsreihenfolge des DPs . . . . . . . . . . . . . . . 52
6.2.3
Darstellung des Algorithmus . . . . . . . . . . . . . . . . 54
i

Inhaltsverzeichnis
6.3
Einführung weiterer Nebenbedingungen . . . . . . . . . . . . . . 65
6.3.1
Berücksichtigung eines Dienstes . . . . . . . . . . . . . . 66
6.3.2
Berücksichtigung von Überstunden und Fehlstunden . . . 72
6.3.3
Berücksichtigung einer Mittagspause . . . . . . . . . . . 74
6.3.4
Berücksichtigung eines Startzeitfensters . . . . . . . . . . 78
6.3.5
Werte des vorherigen Planungshorizonts . . . . . . . . . 79
6.4
Beschleunigung des Algorithmus . . . . . . . . . . . . . . . . . . 80
6.5
Bedingungen für die optimale Lösung . . . . . . . . . . . . . . . 86
7 Zeitliche Analyse der Lösungsverfahren
89
7.1
Parametereinstellung und Beschreibung der Variationen . . . . . 89
7.2
Ergebnisse der Laufzeitanalysen . . . . . . . . . . . . . . . . . . 91
7.2.1
Häufigkeit der Effizienzprüfung . . . . . . . . . . . . . . 92
7.2.2
Variation der ORDER Regel . . . . . . . . . . . . . . . . 93
7.2.3
Praxisbeispiel . . . . . . . . . . . . . . . . . . . . . . . . 95
7.2.4
Praxisbeispiel II . . . . . . . . . . . . . . . . . . . . . . . 97
7.2.5
Variation der Dichte der Deltas . . . . . . . . . . . . . . 98
7.2.6
Auslassung der Nebenbedingungen ,,Mittagspause", ,,Dienst"
bzw. ,,Startzeitfenster" . . . . . . . . . . . . . . . . . . . 100
7.2.7
Variation der Mindestarbeitszeit . . . . . . . . . . . . . . 103
7.2.8
Variation der Höchstarbeitszeit . . . . . . . . . . . . . . 105
7.2.9
Variation des Startzeitfensters . . . . . . . . . . . . . . . 105
7.3
Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . 106
8 Ausblick
108
A Vollständiges Modell des MIPs
xiv
B Vollständiges Modell des DPs
xvii
C Ausführliche Ergebnisse der Laufzeitanalysen
xxiii
C.1 Häufigkeit der Effizienzprüfung . . . . . . . . . . . . . . . . . . xxiii
C.2 Variation der ORDER Regel . . . . . . . . . . . . . . . . . . . . xxiv
C.3 Praxisbeispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv
C.4 Praxisbeispiel II . . . . . . . . . . . . . . . . . . . . . . . . . . . xxvi
C.5 Variation der Dichte der Deltas . . . . . . . . . . . . . . . . . . xxvii
C.6 Auslassung der Nebenbedingungen ,,Mittagspause", ,,Dienst" bzw.
,,Startzeitfenster" . . . . . . . . . . . . . . . . . . . . . . . . . . xxix
C.7 Variation der Mindestarbeitszeit . . . . . . . . . . . . . . . . . . xxxi
C.8 Variation der Höchstarbeitszeit . . . . . . . . . . . . . . . . . . xxxiii
C.9 Variation des Startzeitfensters . . . . . . . . . . . . . . . . . . . xxxv
Literaturverzeichnis
xxxvii
ii

Tabellenverzeichnis
Tab. 1
Zur Wochenarbeitszeit angerechnete und ausbezahlte Stun-
den eines Dienstes. . . . . . . . . . . . . . . . . . . . . . . . . 29
Tab. 2
Allgemeine Parametereinstellungen. . . . . . . . . . . . . . . . 89
Tab. 3
Abweichende Parametereinstellungen bei Variation der Häu-
figkeit der Effizienzprüfung. . . . . . . . . . . . . . . . . . . . 92
Tab. 4
Lösungszeiten bei Variation der Häufigkeit der Effizienzprüfung. 93
Tab. 5
Kennwerte der Labels bei Variation der Häufigkeit der Effizi-
enzprüfung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Tab. 6
Abweichende Parametereinstellungen bei Variation der ORDER
Regel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
Tab. 7
Lösungszeiten bei Variation der ORDER Regel. . . . . . . . . 94
Tab. 8
Kennwerte der Labels bei Variation der ORDER Regel.
. . . 94
Tab. 9
Abweichende Parametereinstellungen im Praxisbeispiel. . . . . 95
Tab. 10
Lösungszeiten des MIPs, DPs und SPs im Praxisbeispiel. . . . 95
Tab. 11
Anzahl an Variablen, Nebenbedingungen und Koeffizienten
ungleich Null im MIP und SP im Praxisbeispiel. . . . . . . . . 96
Tab. 12
Kennwerte der Labels des DPs im Praxisbeispiel. . . . . . . . 97
Tab. 13
Abweichende Parametereinstellungen beim zweiten Praxis-
beispiel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Tab. 14
Lösungszeiten des MIPs, SPs und DPs für das zweite Praxis-
problem.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Tab. 15
Kennwerte der Labels für das DP im zweiten Praxisbeispiel. . 98
Tab. 16
Abweichende Parametereinstellungen bei Variation der Dich-
ten von
dem
und
D
.
. . . . . . . . . . . . . . . . . . . . . . 98
Tab. 17
Lösungszeiten bei Variation der Dichten von
dem
und
D
. . . 99
Tab. 18
Kennwerte der Labels bei Variation der Dichten von
dem
und
D
für zwei Wochen. . . . . . . . . . . . . . . . . . . . . . . . 99
Tab. 19
Kennwerte der Labels bei Variation der Dichten von
dem
und
D
für vier Wochen. . . . . . . . . . . . . . . . . . . . . . . . 100
Tab. 20
Abweichende Parametereinstellungen bei Auslassung der Ne-
benbedingung für die Mittagspause.
. . . . . . . . . . . . . . 101
Tab. 21
Lösungszeiten bei Auslassung der Nebenbedingungen ,,Mit-
tagspause", ,,Dienst" bzw. ,,Startzeitfenster". . . . . . . . . . . 101
Tab. 22
Kennwerte der Labels bei Auslassung der Nebenbedingungen
,,Mittagspause", ,,Dienst" bzw. ,,Startzeitfenster". . . . . . . . 102
Tab. 23
Abweichende Parametereinstellungen bei Variation der Min-
destarbeitszeit. . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Tab. 24
Lösungszeiten bei Variation der Mindestarbeitszeit. . . . . . . 103
Tab. 25
Kennwerte der Labels bei Variation der Mindestarbeitslänge
über zwei Wochen. . . . . . . . . . . . . . . . . . . . . . . . . 104
iii

Tabellenverzeichnis
Tab. 26
Kennwerte der Labels bei Variation der Mindestarbeitslänge
über vier Wochen. . . . . . . . . . . . . . . . . . . . . . . . . 104
Tab. 27
Lösungszeiten bei Variation der Höchstarbeitszeit.
. . . . . . 105
Tab. 28
Lösungszeiten bei Variation des Startzeitfensters. . . . . . . . 105
Tab. C.1
Lösungzeiten bei Variation der Häufigkeit der Effizienzprü-
fung - ausführliche Darstellung. . . . . . . . . . . . . . . . . . xxiii
Tab. C.2
Kennwerte der Labels bei Variation der Häufigkeit der Effizi-
enzprüfung - ausführliche Darstellung. . . . . . . . . . . . . . xxiii
Tab. C.3
Lösungzeiten bei Variation der ORDER Regel - ausführliche
Darstellung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiv
Tab. C.4
Kennwerte der Labels bei Variation der ORDER Regel - aus-
führliche Darstellung. . . . . . . . . . . . . . . . . . . . . . . xxiv
Tab. C.5
Lösungzeiten des MIPs, DPs und SPs im Praxisbeispiel - aus-
führliche Darstellung. . . . . . . . . . . . . . . . . . . . . . . xxv
Tab. C.6
Kennwerte der Labels beim Praxisbeispiel - ausführliche Dar-
stellung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv
Tab. C.7
Anzahl an Variablen, Nebenbedingungen und Koeffizienten
ungleich Null im MIP und SP im zweiten Praxisbeispiel. . . . xxvi
Tab. C.8
Lösungszeiten bei Variation der Dichten von
dem
und
D
-
ausführliche Darstellung. . . . . . . . . . . . . . . . . . . . . . xxvii
Tab. C.9
Kennwerte der Labels bei Variation der Dichten von
dem
und
D
für zwei Wochen - ausführliche Darstellung. . . . . . . . . xxvii
Tab. C.10 Kennwerte der Labels bei Variation der Dichten von
dem
und
D
für vier Wochen - ausführliche Darstelung.
. . . . . . . . xxviii
Tab. C.11 Kennwerte der Labels bei Variation der Dichten von
dem
und
D
für sechs Wochen - ausführliche Darstelung. . . . . . . . . xxviii
Tab. C.12 Lösungszeiten bei Auslassung der Nebenbedingungen ,,Mit-
tagspause", ,,Dienst" bzw. ,,Startzeitfenster" - ausführliche
Darstellung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxix
Tab. C.13 Kennwerte der Labels bei Auslassung der Nebenbedingungen
,,Mittagspause", ,,Dienst" bzw. ,,Startzeitfenster" - ausführli-
che Darstellung. . . . . . . . . . . . . . . . . . . . . . . . . . xxx
Tab. C.14 Lösungszeiten bei Variation der Mindestarbeitszeit - ausführ-
liche Darstellung.
. . . . . . . . . . . . . . . . . . . . . . . . xxxi
Tab. C.15 Kennwerte der Labels bei Variation der Mindestarbeitszeit -
ausführliche Darstellung. . . . . . . . . . . . . . . . . . . . . . xxxii
Tab. C.16 Lösungszeiten bei Variation der Höchstarbeitszeit - ausführ-
liche Darstellung. . . . . . . . . . . . . . . . . . . . . . . . . . xxxiii
Tab. C.17 Kennwerte der Labels bei Variation der Höchstarbeitszeit über
zwei und vier Wochen - ausführliche Darstellung. . . . . . . . xxxiv
iv

Tabellenverzeichnis
Tab. C.18 Lösungszeiten bei Variation des Startzeitfensters - ausführli-
che Darstellung. . . . . . . . . . . . . . . . . . . . . . . . . . xxxv
Tab. C.19 Kennwerte der Labels bei Variation des Startzeitfensters über
zwei und vier Wochen - ausführliche Darstellung. . . . . . . . xxxvi
v

Abbildungsverzeichnis
Abb. 1
Ein Schichtplan über sieben Tage.
. . . . . . . . . . . . . . .
3
Abb. 2
Aufbau des Graphen G. . . . . . . . . . . . . . . . . . . . . . 15
Abb. 3
Arbeit und Pause auf dem Graphen G. . . . . . . . . . . . . . 17
Abb. 4
Graph G mit Ressourcenvariablen, Ressourcenfenstern und
Kantengewichten. . . . . . . . . . . . . . . . . . . . . . . . . . 19
Abb. 5
Graph G mit Binärvariablen von Arbeit und Pause. . . . . . . 22
Abb. 6
Graph G mit Binärvariablen von Arbeit, Pause und Dienst. . 30
Abb. 7
Graph G mit Binärvariablen der Mittagspause. . . . . . . . . 36
Abb. 8
Stufen im dynamischen Programm. . . . . . . . . . . . . . . . 51
Abb. 9
Ausschnitt eines Schichtplans vor dem Verschieben von Ar-
beitsschichten. . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Abb. 10
Ausschnitt eines Schichtplans nach dem Verschieben von Ar-
beitsschichten. . . . . . . . . . . . . . . . . . . . . . . . . . . 87
vi

Abkürzungsverzeichnis
Abkürzungsverzeichnis
B&B
Branch & Bound
B&P
Branch & Price
CG
Spaltengenerierungsverfahren (engl.: column generation)
DL
Anzahl an dominierten Labels im dynamischen Programm
DP
Dynamische Programmierung bzw. Programm
EL
Anzahl an erstellten Labels im dynamischen Programm
IP
Ganzzahlige Programmierung bzw. Programm (engl.: integer
programming)
LP
Lineare Programmierung bzw. lineares Programm
LV
Anzahl an notwendigen paarweisen Vergleichen der Labels
im dynamischen Programm, um in einer Iteration die Labels
auf Dominanz zu untersuchen
M
Mittelwert (engl.: mean)
MIP
Gemischt ganzzahlige Programmierung bzw. Programm
(engl.: mixed integer programming)
MP
Masterproblem des Spaltengenerierungsverfahrens
NB
Nebenbedingung(en)
RCSP
Kürzeste Wege Problem mit Ressourcenbeschränkung (engl.:
resource constrained shortest path problem)
SD
Standardabweicheung (engl.: standard deviation
SP
Subproblem des Spaltengenerierungsverfahrens bzw. konkre-
tes Subproblem aus Brunner et al. (2010)
SPP
Kürzeste Wege Problem (engl.: shortest path problem)
VC
Variationskoeffizient (engl.: coefficient of variation)
vii

Symbolverzeichnis - Allgemein und MIP
Symbolverzeichnis - Allgemein und MIP
A
Index für Arbeit
A
Menge der Kanten des Graphen G
c
over
Kosten für eine Überstunde o
w
c
Reduzierte Kosten einer Spalte des Masterproblems
c
paid
Kosten für eine ausbezahlte Überstunde h
w
c
sched
Gesamtkosten, die aus einem Schichtplan resultieren
D
Index für den Dienst
D
Menge der Tage im Planungshorizont
d
Index für einen Tag
Vektor der Dualvariablen mit = (
dem
ab
,
D
ab
)
dem
ab
Wert
der
Dualvariable
der
Arbeitsnachfrage-
Nebenbedingung I aus dem Masterproblem in Periode
(a, b) mit (a, b) A
D
ab
Wert
der
Dualvariablen
der
Dienstnachfrage-
Nebenbedingung II aus dem Masterproblem in Periode
(a, b) mit (a, b) A
E
A
Zeitpunkt, zu dem die reguläre Arbeit A spätestens endet
E
WE
Letzter Tag des Wochenendes
f
1
(j)
Gibt die Stundenanzahl des im Knoten j V
D
w
beginnenden
Dienstes D an, welche zur regulären Wochenarbeitszeit R
WA
addiert wird
f
2
(j)
Funktion, welche jeder Nummer eines Knotens j V eine
Knotennummer des ersten Tages zuweißt, mit f
2
(j) : V
j mod K
d
,
für j mod K
d
= 0
K
d
,
für j mod K
d
= 0
h
w
Anzahl an ausbezahlten Überstunden in der Woche w W
i
Index eines obenliegenden Knotens mit i
V
i
-
Beide Vorgängerknoten des Knotens i
i
-
Vorgängerknoten des Knotens i aus den oberen Knoten V
i
-
Vorgängerknoten des Knotens i aus den unteren Knoten V
j
Index eines untenliegenden Knotens mit j V
K
d
Anzahl an Knoten pro Tag
K
w
Anzahl an Knoten pro Woche, mit K
w
= (
|V| - 2)\|W|
(·)
Verhältnis der Lösungszeit zur Anzahl an erstellten (EL)
oder dominierten Labels (DL) bzw. an notwendigen paar-
weisen Vergleichen (LV) zur Bestimmung der Dominanz in
[
s
10
6
]
M
Positive, genügend große Zahl mit M N
N
D
Maximale Anzahl an Diensten pro Woche
viii

Symbolverzeichnis - Allgemein und MIP
o
w
Anzahl an Überstunden in der Woche w W
0
P
Index für Pause
q
Index des Knotens im Graphen mit der kleinsten Nummer
q
j,j
+
Binärvariable, mit 1, wenn der Arzt nach einer Mittagspause
in der Periode (j, j
+
) mit j V die erste Periode arbeitet, 0
sonst
q
j
-
,j
Binärvariable, mit 1, wenn der Arzt in der Periode (j
-
, j)
mit j V eine Mittagspause absolviert, 0 sonst
r
Index für Ressourcen, mit r T
R
A
w
Anzahl an Arbeitsstunden, welche in Woche w nicht zur Ver-
fügung stehen
R
D
Ressourcenverbrauch des Dienstes
()
Dichte der
dem
bzw.
D
, welche das Verhältnis von der An-
zahl an
dem
> 0 bzw.
D
> 0 pro 24 Stunden ausdrückt
R
r
Höchstdauer der Ressource r T
R
P
Anzahl an Stunden, welche vor Beginn des Planungshori-
zonts bereits pausiert wurden
R
r
(a) Höhe der Ressource r T im Knoten a V
R
r
Mindestdauer der Ressource r T
t
Index des Knotens im Graphen mit der höchsten Nummer
S
A
Zeitpunkt, zu dem die reguläre Arbeit A frühestens beginnt
S
D
Zeitpunkt, zu dem der Dienst D beginnt
S
WE
Tag, zu dem das Wochenende beginnt
T
Menge der Ressourcen, mit
T = {A, WA, P, D}
T
late
Höchstdauer an Arbeit vor Aufnahme einer Mittagspause
T
post
Mindestdauer an Arbeit nach Beendigung einer Mittagspau-
se
T
pre
Mindestdauer an Arbeit vor Aufnahme einer Mittagspause
T
win
Maximale Länge zwischen frühestem und spätestem Arbeits-
beginn pro Woche
u
w
Anzahl an ,,Fehlstunden" in der Woche w W
v
Vertragliche Wochenarbeitszeit
V
Menge aller Knoten des Graphen G
V
Menge der obenliegenden Knoten, mit
V = {i|i mod 2 = 1 :
i V} V
V
Menge der untenliegenden Knoten, mit
V = {j|j mod 2 =
0 : j V} V
V
D
w
Teilmenge der untenliegenden Knoten bei denen der Dienst
D in Woche w startet, mit V
D
w
=
{j|j mod K
d
= 2(S
D
+ 1) :
j V
} V, wobei die Woche w von Montag bis Sonntag
geht
ix

Symbolverzeichnis - Allgemein und MIP
^
V
D
w
Teilmenge der untenliegenden Knoten bei denen der Dienst
D in Woche w startet zur Berechnung von v, wobei die Wo-
che w von Sonntag bis Samstag geht
V
e
w
Teilmenge des letzten untenliegenden Knotens der Woche w,
mit
V
e
w
=
{j|j = w · K
w
+ 1 : j V w W} V
V
s
w
Teilmenge der obenliegenden Knoten bei dem seit Be-
ginn der Woche w eine Periode vergangen ist, mit
V
s
w
=
{i|i mod K
w
= 3 : i V} V
V
w,d
Teilmenge der untenliegenden Knoten von einem Tag d in
der Woche w, mit V
w,d
=
{j|(w - 1)K
w
+ 2 + (d - 1)K
d
j
(w - 1)K
w
+ dK
d
: j V, w W, d D} V
V
non
Menge
der
Knoten,
bei
denen
die
Variable
{x
i
-
i
, x
i
-
i
, x
ii
+
, q
i
-
i
, q
ii
+
, y
i
-
i
, y
ii
+
} Null gesetzt werden kann
W
Menge der Wochen im Planungshorizont,
W {1, 2, ...}
W
0
Menge der Wochen im Planungshorizont einschließlich der
Vorwoche, mit
W
0
=
W {0}
WA
Index für die Wochenarbeit
w
Index für eine Woche
x
j
-
j
Binärvariable, mit 1, wenn der Arzt in Periode (j
-
, j) pau-
siert, 0 sonst
x
i
-
i
Binärvariable, mit 1, wenn der Arzt in Periode (i
-
, i) arbei-
tet, 0 sonst
y
i
-
i
Binärvariable, mit 1, wenn der Arzt in der Periode (i
-
, i) mit
i
V einen Dienst absolviert, 0 sonst
y
j
-
j
Binärvariable, mit 1, wenn der Arzt in der Periode (j
-
o
, j)
mit j V die erste Periode nach einem Dienst pausiert, 0
sonst
x

Symbolverzeichnis - DP
Symbolverzeichnis - DP
a
j
Entscheidung, um vom Zustand x
j
in den Zustand x
j+1
zu
gelangen, mit a
j
{l, p, d, b}
A
j
(x
j
)
Menge der möglichen Entscheidungen auf Stufe j in Abhän-
gigkeit des Zustandes x
j
a
Optimale Folge von Entscheidungen
b
Index für eine Mittagspause bei der Entscheidung a
j
d
Index für einen Dienst bei der Entscheidung a
j
dem
j
Wert
der
Dualvariable
der
Arbeitsnachfrage-
Nebenbedingung I aus dem Masterproblem zwischen
Stufe j und j + 1
D
j
Wert
der
Dualvariablen
der
Dienstnachfrage-
Nebenbedingung II aus dem Masterproblem zwischen
Stufe j und j + 1
(d
so
)
k
j
Komponente des Labels L
k
j
, welche den Wert 1 annimmt,
wenn ein Dienst am Sonntag stattfindet und 0 sonst
(e)
k
j
Komponente des Labels L
k
j
, welche den Beginn der frühesten
Arbeitsschicht in einer Woche angibt
(l)
k
j
Komponente des Labels L
k
j
, welche den Beginn der spätesten
Arbeitsschicht in einer Woche angibt
EF F (X
j
)
Methode des Algorithmus im dynamischen Programm, wel-
che die Zustände x
j
X
j
auf Effizienz überprüft
e
win
Zeitpunkt des Endes eines Startzeitfensters
~
f
1
(j)
Gibt die Stundenanzahl des auf Stufe j beginnenden Diens-
tes D an, welche zur regulären Wochenarbeitszeit R
WA
ad-
diert wird
f
3
e
win
Funktion, welche für alle e
win
> 24 den Endzeitpunkt e
win
zurück auf einen 24-Stundentag berechnet mit f
3
e
win
=
0, für e
win
24
e
win
mod 24, für e
win
> 24
Zeitspanne, in welcher eine Arbeit möglich ist, wobei =
24/7 angibt, dass es möglich ist, rund um die Uhr zu arbeiten
I
{A}
(x)
Indikatorfunktion (auch charakteristische Funktion genannt)
mit x X, wobei X eine beliebige Menge ist, und A X,
mit I
{A}
(x) = 1, falls x A und I
{A}
(x) = 0 sonst
j
Index für eine Stufe
j
so
D
Index für eine Stufe, auf welcher an einem Sonntag der Dienst
beginnt
K
j
Menge der Indizes aller Zustände x
k
j
auf der Stufe j mit k
K
j
xi

Symbolverzeichnis - DP
L
k
j
Das
k-te
Label
eines
Zustandes
x
j
auf
der
Stufe
j, wobei das Label durch die Komponenten L
k
j
=
R
W A
, R
A
, R
D
, R
P
, obj, s
mo
, n
D
, d
so
, mp, e, l
k
j
charakte-
risiert ist
l
Index für eine Arbeit bei der Entscheidung a
j
(mp)
k
j
Komponente des Labels L
k
j
, mit (mp)
j
=
-1, wenn bisher
keine Mittagspause absolviert wurde und (mp)
j
= ~j, wenn
in Stufe ~j mit ~j < j eine Mittagspause gehalten wurde
n
D
k
j
Komponente des Labels L
k
j
, welche die bisherige Anzahl an
Diensten in der Woche angibt mit n
D
{0, ...N
D
}
(obj)
k
j
Komponente des Labels L
k
j
, welche den Zielfunktionswert auf
der Stufe j angibt
Operator zwischen zwei Argumenten, welcher die UND-
Verknüpfung angibt
Operator zwischen zwei Argumenten, welcher die ODER-
Verknüpfung angibt
ORDER(X
j
)
Methode des Algorithmus im dynamischen Programm, wel-
che die Zustände x
j
X
j
nach der definierten Reihenfolge
der Abarbeitung sortiert
P()
Potenzmenge einer beliebigen Menge , wobei in dieser Ar-
beit
/ P() definiert sei
p
Index für eine Pause bei der Entscheidung a
j
Tage in der Woche, an denen eine Arbeit möglich ist
r(x
j
,a
j
)
Ertragsfunktion
r
init
Wert der Zielfunktion auf der Stufe j = 0
R
P
min,V W
Minimaler Wert der Pausenressource R
P
von allen Endzu-
ständen einer Vorwoche
(R
r
)
k
j
Komponente des Labels L
k
j
, welche den Ressourcenverbrauch
der Ressource r T angibt
S
Bezeichnung für einen Schichtplan, welcher das Label L
k
j
ent-
hält
(s
mo
)
k
j
Komponente des Labels L
k
j
, welche angibt, um wie viel Uhr
die erste Schicht der Woche begonnen wurde
s
win
Zeitpunkt des Beginns eines Startzeitfensters
t(x
j
,a
j
)
Transformationsfunktion im dynamischen Programm, wobei
t
(x
j
, ) mit {l, p, d, b} bezeichnet, dass die Entscheidung
a
j
= in der Transformationsfunktion verwendet wird
V (x
j
)
Wertfunktion
X
j
Menge aller Zustände auf der Stufe j
x
j
Zustand auf der Stufe j
xii

Symbolverzeichnis - DP
x
init
Initialisierungszustand, mit welchem die dynamische Pro-
grammierung begonnen wird. Ist dieser Zustand nicht in je-
der Woche gleich, so wird das Symbol x
init,w
benutzt, um
den Initialisierungszustand der Woche w zu kennzeichnen
x
Optimale Folge von Zuständen
xiii

1 Einleitung
1 Einleitung
Der wachsende Kostendruck im Dienstleistungssektor und insbesondere im Ge-
sundheitswesen macht es notwendig vorhandene Ressourcen möglichst effizient
einzusetzen (Thungjaroenkul et al. 2007). Der größte Anteil der Ausgaben in
diesen Sektoren wird für Personal verwendet. Eine Reduzierung dieser Kosten
scheitert oft an der Variabilität des Bedarfs und der gleichzeitigen Notwen-
digkeit fester Schichtpläne. Überdies sind Präferenzen der Arbeitnehmer und
gesetzliche Vorgaben zu berücksichtigen.
Der aktuelle Bericht ,,Pflege-Thermometer" des deutschen Instituts für an-
gewandte Pflegeforschung (dip) zeigt, dass der Abbau von Pflegekräften in
Krankenhäusern bei gleichzeitigem Aufbau an ärztlichem Personal fortgesetzt
wird. (Isfort und Weidner 2007, S.5):
,,Sowohl bei den Stellen für pflegerische Hilfskräfte (Krankenpflegehelfer/-
innen) als auch für das examinierte Pflegepersonal (Krankenpflegekräf-
te) wurden in erheblichem Umfang Reduzierungen vorgenommen. Es
wurden 48.000 Vollzeitäquivalente (-13,5%) für Krankenpflegekräfte in
den bettenführenden Bereichen im Zeitraum von zehn Jahren abgebaut.
Dabei hat sich die Fallzahl der stationär behandelten Patienten erhöht
und die Verweildauer der Patienten ist gesunken. Es erfolgte im glei-
chen Zeitraum ein Aufbau des ärztlichen Personals in erheblichem Um-
fang (+19,5%). Die Belastungszahl des Pflegedienstes nach Fällen stieg
in zehn Jahren von 48 Patienten auf 59, was einem Plus von 23% ent-
spricht!"
Weitere Informationen, die bestätigen, dass dieser Trend im Jahr 2008 fort-
gesetzt wurde, sind im Bericht des Statistischen Bundesamtes ,,Grunddaten
der Krankenhäuser" (Statistisches Bundesamt 2009) zu finden.
Oben beschriebene Entwicklungen verstärken die Notwendigkeit eine effizi-
ente Schichtplanung für das im Krankenhaus eingesetzte Personal zu entwi-
ckeln. Der Großteil der aktuellen Forschung bezieht sich auf die Planung des
Pflegepersonals (nurse scheduling). Eine Übersicht über bisherige Veröffentli-
chungen hierzu gibt Cheang et al. (2003) und Burke et al. (2004). Bisherige
entwickelte Methoden, welche für einen kurzen bzw. mittleren Planungshori-
zont bei Pflegepersonal eingesetzt werden können, wurden bereits mit einigem
Erfolg umgesetzt (Bard und Purnomo 2005, Kellogg und Walczak 2007).
Das Problem der Schichtplanung von Ärzten wird bisher jedoch weniger
behandelt. Ein Grund ist die erhöhte Komplexität im Vergleich zur Planung
von Pflegepersonal. Flexible Arbeitsverträge, welche vom Krankenhaus, Bun-
desland, Ausbildungsstand und Status des Arztes abhängen, erschweren eine
Generalisierung erheblich.
In Brunner et al. (2009) wurde ein neuer Ansatz gewählt, um dieses Pro-
blem anzugehen. Der gewählte Ansatz erlaubt eine flexible Generierung von
1

1 Einleitung
Schichtplänen, wobei eine große Anzahl an Parametern frei gewählt werden
kann.
Das beschriebene Problem wurde als lineares Programm (LP) modelliert
und anhand von Daten aus der Praxis für 16 Anästhesisten des Klinikums
rechts der Isar in München getestet. Für große Instanzen wurde aufgrund der
großen Variablen- und Nebenbedingungsanzahl keine Lösung in vertretbarer
Zeit gefunden.
Daher wurde in einem nächsten Schritt ein Branch & Price (B&P) Ver-
fahren
1
benutzt (Brunner et al. 2010), wobei im Subproblem des Spalten-
generierungsverfahrens (engl.: column generation bzw. CG) die Schichtpläne
der einzelnen Ärzte erzeugt werden. Das Subproblem (SP) wird dort als ein
gemischt ganzzahliges Programm (engl.: mixed integer program bzw. MIP)
modelliert. Für komplexere Probleminstanzen ist die Lösung als MIP jedoch
ineffizient bzgl. der Lösungszeit.
Ziel dieser Arbeit ist es daher, das Subproblem der Schichtplanerzeugung
geeignet zu reformulieren und effizient zu lösen, um die bisherige Lösungszeit
zu verbessern.
Folgende Parameter sind bei der Generierung eines Schichtplans zu berück-
sichtigen. Ein Arzt kann für eine reguläre Arbeit eingeteilt werden, welche eine
Mindest- und Höchstdauer besitzt. Des Weiteren gibt es die Möglichkeit eines
Bereitschaftsdienstes, welcher im Folgenden als ,,Dienst" bezeichnet wird. Hier-
bei ist der Arzt 24 Stunden im Klinikum anwesend, um für unvorhergesehene
Nachfrage, z.B. Notfälle, eingesetzt zu werden. Es gibt eine maximale Anzahl
an Diensten pro Woche, welche ein Arzt übernehmen kann. Ein Teil dieser Ar-
beitszeit wird der regulären Wochenarbeitszeit angerechnet. Nach einer Arbeit
bzw. einem Dienst muss eine Mindestpausenlänge eingehalten werden. Weite-
re Restriktionen sind die Berücksichtigung einer maximalen Wochenarbeitszeit
und einer Mittagspause. Da die Arbeit eines Arztes zu einem beliebigen Zeit-
punkt in einer Woche beginnen kann, wird zudem gefordert, dass sich die
verschiedenen Arbeitsstartzeitpunkte einer Woche innerhalb eines definierten
Zeitfensters befinden. Hiervon ist der Beginn des Dienstes ausgenommen.
Abbildung 1 zeigt als Beispiel einen Ausschnitt eines Schichtplans über sie-
ben Tage. Jeder Tag ist in 24 Perioden eingeteilt, wobei Periode Null um 0 Uhr
beginnt und um 1 Uhr endet. Die hellgrau bzw. dunkelgrau hinterlegte Zahl 1
steht hierbei für Arbeit bzw. Dienst, die Zahl 0 repräsentiert eine Pause (Mit-
tagspause oder Pause zwischen zwei Schichten). Die Arbeit für diesen Arzt
beginnt beispielsweise am ersten und fünften Tag um 7 Uhr. An diesen Tagen
wird auch eine Mittagspause eingeplant, die durch die Null im Block der hell-
grau hinterlegten Einsen erkennbar ist. Diese findet jeweils von 12 bis 13 Uhr
1
Eine Übersicht zu der Branch & Price Literatur gibt Barnhart et al. (1998). Eine Einfüh-
rung in B&P kann in Grünert und Irnich (2005a, Kapitel 3) gefunden werden.
2

1 Einleitung
Periode
Tag 1
Tag 2
Tag 3
Tag 4
Tag 5
Tag 6
Tag 7
0
0
0
1
0
0
0
1
1
0
0
1
0
0
0
1
2
0
0
1
0
0
0
1
3
0
0
1
0
0
0
1
4
0
0
1
0
0
0
1
5
0
0
1
0
0
0
1
6
0
0
1
0
0
0
1
7
1
0
1
0
1
0
1
8
1
1
0
1
1
1
0
9
1
1
0
1
1
1
0
10
1
1
0
1
1
1
0
11
1
1
0
0
1
1
0
12
0
1
0
1
0
1
0
13
1
1
0
1
1
1
0
14
1
1
0
1
1
1
0
15
1
1
0
1
1
1
0
16
1
1
0
1
1
1
0
17
1
1
0
1
1
1
0
18
1
1
0
0
1
1
0
19
0
1
0
0
1
1
0
20
0
1
0
0
0
1
0
21
0
1
0
0
0
1
0
22
0
1
0
0
0
1
0
23
0
1
0
0
0
1
0
Abb. 1: Ein Schichtplan über sieben Tage.
statt. Am zweiten und sechsten Tag hat der Arzt einen Dienst, welcher um
8 Uhr beginnt und 24 Stunden dauert.
Es ist auch erkennbar, dass nach einer Arbeit oder einem Dienst eine Min-
destpausenlänge von zwölf Stunden eingehalten wird.
Bei der Erstellung eines Schichtplans für einen einzelnen Arzt ist der pe-
riodenabhängige Nutzen der Arbeit über den gesamten Planungshorizont zu
optimieren. Der Nutzen einer Periode ist hierbei der nichtnegative Wert der
Dualvariablen für diese Periode. Der gesamte Nutzen ergibt sich aus den re-
duzierten Kosten einer Spalte. Es sei daran erinnert, dass die Schichtplange-
nerierung die Erzeugung einer Spalte im Subproblem darstellt und diese bei
einem B&P so lange fortgesetzt wird, bis der Nutzen einer Spalte nichtnega-
tiv ist. Um die reduzierten Kosten einer Spalte zu berechnen, wird hierbei die
Summe der Dualvariablen von einem positiven Wert, welcher die Kosten für
Überstunden berücksichtigt, subtrahiert.
In der Reformulierung wird das Subproblem in dieser Arbeit als ein Netz-
werk modelliert und als Kürzeste Wege Problem mit Ressourcenbeschränkung
(engl.: resource constrained shortest path problem oder RCSP) dargestellt. Als
Lösungsverfahren werden sowohl ein MIP als auch die dynamische Program-
mierung (DP) gewählt.
Im folgenden Kapitel 2 wird eine Übersicht über die Literatur gegeben. Hier-
bei wird auf bisherige Forschungsarbeiten im Zusammenhang der Schichtpla-
nung (scheduling) eingegangen und insbesondere jene dargestellt, welche im
Lösungsverfahren ein Netzwerk bzw. ein RCSP wählen. Überdies werden Ar-
beiten erwähnt, welche die dynamische Programmierung als Lösung verwen-
den. Es wird deutlich, dass oftmals ein scheduling Problem als B&P gelöst
wird, wobei das Subproblem meist als Netzwerkflussproblem modelliert und
mit einem DP gelöst wird. Fast immer sind starke Einschränkungen bzgl. der
Flexibilität bei der Erzeugung des Schichtplans vorhanden.
3

1 Einleitung
In Kapitel 3 wird die Problemstellung detailliert erläutert. Hierbei wird
auf den Zusammenhang zum Spaltengenerierungsverfahren aus Brunner et al.
(2010) eingegangen. Zudem werden die Nebenbedingungen mit den entspre-
chenden Parametern eingeführt.
In Kapitel 4 wird der Graph beschrieben, welcher für die Modellierung des
RCSPs verwendet wird. Zuerst wird der Graph mit Kantengewichten beschrie-
ben und der Zusammenhang zur Schichtplanung dargestellt. In Kapitel 4.2 wer-
den den Knoten Ressourcen zugeordnet, um die einzelnen Nebenbedingungen
abbilden zu können.
Kapitel 5 beschreibt das gemischt ganzzahlige Modell. In Kapitel 5.1 werden
nur die Nebenbedingungen an Mindest- und Höchstarbeitszeit und die Min-
destpausendauer berücksichtigt. Das Grundmodell des MIP wird eingeführt
und die Notation erläutert. Zudem wird auf mögliche Variablenrelaxationen
eingegangen. Darauf aufbauend wird das Modell in Kapitel 5.2 erweitert, um
den Dienst, die Überstunden und Fehlstunden, die Mittagspause, das Startzeit-
fenster der Arbeit und mögliche Werte aus dem vorherigen Planungshorizont
zu berücksichtigen. Um die Lösungsdauer des Algorithmus in Abhängigkeit
der möglichen Arbeitszeit zu verbessern, wird eine Eingrenzung der Variablen
durchgeführt, welche in Kapitel 5.3 dargestellt ist. Als letztes Teilkapitel wird
die Komplexität des RCSPs erläutert. Es ist ein schwach NP-vollständiges Pro-
blem und kann, wenn als dynamisches Programm (DP) formuliert, in pseudo-
polynomialer Zeit gelöst werden.
Da das Kürzeste Wege Problem mit Ressourcenbeschränkung als MIP kei-
ne verbesserte Lösungszeit hervorbrachte, wurde in Kapitel 6 das RCSP als
dynamisches Programm modelliert. Nach einer Einführung in die dynamische
Programmierung wird ab Kapitel 6.2 erläutert, wie das DP modelliert wird,
um das RCSP abbilden zu können. In einem nächsten Schritt wird der für das
dynamische Programm verwendete Algorithmus beschrieben.
Laufzeitanalysen der beiden Lösungsverfahren werden in Kapitel 7 darge-
stellt. Hierbei wird deutlich, dass die Lösung des RCSP als MIP im Durch-
schnitt langsamer als die ursprüngliche Formulierung aus Brunner et al. (2010)
ist. Die deutliche Beschleunigung des Lösungsprozesses, vor allem für komplexe
Instanzen, durch die Formulierung als DP wird ersichtlich. Zusätzlich werden
für das Modell der dynamischen Programmierung Analysen anhand verschie-
dener Parametereinstellungen vorgenommen.
Im letzten Kapitel werden die Resultate zusammengefasst und ein Ausblick
für weiterführende Untersuchungen gegeben.
Das ,,Symbolverzeichnis - DP" beinhaltet die in Kapitel 6 eingeführten Sym-
bole, welche ausschließlich für die Beschreibung des dynamischen Programms
verwendet werden. Alle weiteren Symbole, welche in den anderen Kapiteln erst-
mals erwähnt werden, finden sich im ,,Symbolverzeichnis - Allgemein und MIP".
4

1 Einleitung
Da die Modellierung des DPs auf Erkenntnissen vorheriger Kapitel aufbaut,
sind Symbole, welche in Kapitel 6 benutzt werden, auch im zweitgenannten
Symbolverzeichnis zu finden.
5

2 Literaturüberblick
2 Literaturüberblick
Der Überblick über bisher veröffentlichte Literatur ist in drei Teilen gegliedert.
Zuerst wird ein Überblick über Probleme der Schichtplanung im Allgemeinen
gegeben. Danach folgen Abschnitte über Artikel, in welchen das Schichtpla-
nungsproblem als Kürzeste Wege Problem (engl.: shortest path problem oder
SPP) gelöst wird. Zuletzt werden Veröffentlichungen dargestellt, in welchen die
dynamische Programmierung eingesetzt wird. Meist wird die DP als Lösungs-
verfahren eines Branch & Price verwendet. In den letzten beiden Teilen werden
die Artikel anhand der Problembeschreibung (i), der Nebenbedingungen und
Zielfunktion (ii), dem Lösungsverfahren (iii) und sonstiger Aspekte (iv) kurz
charakterisiert.
Schichtplanung im Allgemeinen
Ernst et al. (2004a, 2004b) gibt einen Überblick über die bisherigen Forschun-
gen in der Schichtplanung (scheduling und rostering) wobei in Ernst et al.
(2004a) eine kommentierte Übersicht von 700 Veröffentlichungen zusammen-
gestellt ist. Die am meisten eingesetzte Lösungsmethode ist die ganzzahlige
Programmierung (ohne spezielle Lösungsalgorithmen) und Heuristiken, wel-
che zusammen etwa ein Drittel aller betrachteten Veröffentlichungen ausma-
chen. Weitere wichtige Methoden (in der Reihenfolge der Verwendung) sind
set partitioning- und set covering-Verfahren, welche auch zu den ganzzahligen
linearen Programmen zählen, jedoch eine spezielle Struktur aufweisen, und das
Spaltengenerierungsverfahren.
2
Etwa die Hälfte aller Artikel beschäftigt sich
mit Schichtplanungen im öffentlichen Transport, von Pflegekräften oder vom
Personal bei Luftfahrtgesellschaften.
Übersichtsartikel zur Schichtplanung bei Krankenschwestern wurden von
Cheang et al. (2003) und Burke et al. (2004) veröffentlicht. Einen Überblick
über die aktuellen Forschungsergebnisse bei der Crewplanung (crew rostering)
bei Luftfahrtgesellschaften gibt Kohl und Karisch (2004). Eine sehr ausführ-
liche Übersicht mit einigen Kurzbeschreibungen von Artikeln, welche den Be-
reich von Call Center behandeln, gibt Mandelbaum (2006). Diese Arbeit ent-
hält auch Verweise zur Schichtplanung bei Call Centern.
2
Eine Darstellung der Lösungsmethode des Spaltengenerierungsverfahrens bei ganzzahligen
Programmen und eine Übersicht über Artikel gibt Wilhelm (2001).
6

2 Literaturüberblick
Schichtplanung mit einem Kürzeste Wege Problem
Eine ausführliche Grundlage über die allgemeine Formulierung eines, wie in
dieser Arbeit vorliegenden, RCSPs wird in Zhu (2005) gegeben. Insbesondere
enthält die Arbeit einen ausführlichen Überblick von Artikeln über das RCSP,
welches mit einem B&P, CG oder DP gelöst wird.
In den meisten Artikeln, welche sich mit Schichtplanung beschäftigen, wird
ein SPP als Lösung eines Subproblems innerhalb eines Spaltengenerierungs-
verfahrens verwendet.
Desrochers und Soumis (1989) beschreiben ein crew scheduling Problem an-
hand der Einplanung von Busfahrern im öffentlichen Transport. Es werden
den Busfahrern feststehende Arbeitspakete, z.B. gewisse Busrouten, zugeteilt.
(ii): Hierbei werden folgende Nebenbedingungen berücksichtigt: eine maxima-
le Anzahl an Arbeitspaketen pro Fahrer, eine einzuhaltende Pause zwischen
zwei Arbeitspaketen, eine Höchstarbeitszeit pro Tag und eine maximale An-
wesenheitsdauer jedes Fahrers pro Tag, auf welcher seine tatsächliche Arbeit
verteilt sein darf. (iii): Das Problem wird mithilfe eines CGs gelöst, wobei das
Subproblem ein RCSP ist. Obige Nebenbedingungen werden als Ressourcen
eingeführt. Ein Knoten stellt im Netzwerk ein Arbeitspaketbeginn bzw. -ende
dar und eine Kante ist dementsprechend Arbeitszeit bzw. Pausenzeit. Das Sub-
problem wird mit einem DP gelöst. (iv): Der beschriebene Algorithmus wurde
bereits an zwei Praxisproblemen getestet.
Bei Eveborn und Rönnqvist (2004) wird ein Schichtplan für Arbeiter be-
trachtet. (ii): Die Flexibilität des Schichtplans ist ähnlich hoch wie in dieser
Arbeit. Der Schichtplan ist gestaltbar bezüglich Wochenarbeitszeit, täglicher
Arbeitszeit und Anzahl an Arbeitstagen bzw. freien Tagen in Folge. Die Zeit-
perioden, in welchen gearbeitet werden kann, und Präferenzen bzgl. gewisser
Schichten können ebenso wie Engpässe in der Deckung der Nachfrage berück-
sichtigt werden. (iii): Die Erzeugung der Schichtpläne wird als set partitioning
Problem dargestellt, welches mit einem B&P gelöst wird. Das Subproblem, die
neuen Spalten in jedem Knoten des B&P zu finden, wird als verschachteltes
Kürzeste Wege Problem zweier SPP modelliert. Das innere SPP erzeugt zu-
lässige Teilschichten, welche im äußeren SPP zu einem Schichtplan kombiniert
werden, wobei die reduzierten Kosten minimiert werden. Das äußere SPP wird
anhand eines DPs gelöst. Es wird nicht näher auf die Modellierung der beiden
Kürzeste Wege Probleme bzw. auf die Formulierung des DPs eingegangen. (iv):
Der Algorithmus wird in der Praxis unter dem Namen SCHEDULER ange-
wandt, wobei in den beschriebenen Fällen aufgrund von Zeitbeschränkungen
bei der Lösungsfindung nicht optimale Lösungen akzeptiert wurden.
Cezik et al. (2001) beschreibt die Erstellung eines Schichtplans über eine
Woche in einem Call Center mit deterministischer Nachfrage. Die Schichtpla-
nung weist eine hohe Flexibilität auf. (ii): Die Variabilität in der Planung
7

2 Literaturüberblick
liegt darin, dass die Startzeit der täglichen Schichten flexibel ist, jedoch in
einer Woche innerhalb eines Zeitfensters liegen muss. Es müssen überdies zwei
Tage pro Woche arbeitsfrei sein, von denen einer am Wochenende liegt. Die
Gesamtlänge einer Tagesschicht, die Einhaltung einer Mittagspause und die
Verrechnung von Überstunden werden zudem berücksichtigt. Das Ziel ist die
Minimierung der Arbeitskosten und der nicht gedeckten Nachfrage. (iii): Aus-
gehend von einem shift scheduling Problem, welches zulässige Tagesschichten
erstellt, werden die Kombinationen dieser Schichten anhand eines Netzwerks
überprüft. Knoten repräsentieren eine Tagesschicht bzw. einen freien Tag und
die Größe des Flusses auf den Kanten stellt dar, wie viele Arbeiter eine konkrete
Kombination dieser Tagesschichten wählt. Das Problem wird als ganzzahliges
Programm (engl.: integer programming bzw. IP) gelöst. (iv): Zeitanalysen mit
Daten aus einem Call Center werden präsentiert, wobei in vertretbarer Zeit
fast-optimale Lösungen gefunden werden können.
Jaumard et al. (1998) löst die Schichtplanung für Pflegekräfte in einem Kran-
kenhaus. Es werden sieben verschiedene feste Schichttypen über drei Tageszei-
ten (Tag, Abend, Nacht) berücksichtigt. (ii): Als Nebenbedingungen werden die
maximale Arbeitszeit, die Einhaltung einer Anzahl an arbeitsfreien Wochen-
enden und die Einplanung von Urlaub berücksichtigt. Überdies ist der Wechsel
zwischen Schichttypen und die Anzahl der in Folge geleisteten Schichten eines
bestimmten Typs beschränkt. Zudem wird das Verhältnis von Schichttypen
innerhalb des persönlichen Arbeitsplans berücksichtigt. (iii): Es wird ein B&P
verwendet, wobei das Subproblem als RCSP formuliert wird. Im Subproblem
werden für die einzelnen Pflegekräfte Arbeitspläne erzeugt. Zur Lösung des
RCSPs wird ein pseudo-polynomialer Algorithmus über zwei Phasen angege-
ben, welcher ausführlich in Jaumard et al. (1996) erläutert wird.
In Mason und Smith (1998) wird eine allgemein Schichtplanung über meh-
rere Wochen mit festen Schichttypen dargestellt. (ii): Ziel ist die Maximierung
der Qualität eines Schichtplans, wobei diese durch die Verteilung der Tage mit
Arbeit und der freien Tage, der Präferenzen für bestimmte Schichttypen und
dem Übergang zwischen zwei Schichttypen (z.B. von Spät- zu Frühschicht)
bestimmt ist. (iii): Das Problem wird mithilfe eines CGs gelöst. Hierbei sorgt
das als IP formulierte Masterproblem (MP) für die Deckung der Nachfrage.
Im Subproblem, welches als Netzwerkfluss Problem dargestellt ist, wird an-
hand des Netzwerks die beste Kombination verschiedener Tagesschichten zu
einer Schicht über n Tage festgestellt. (iv): Das Netzwerk ist ähnlich wie in
Jaumard et al. 1998 aufgebaut, enthält aber keine Ressourcenrestriktionen auf
den Kanten. Eine Zeitanalyse wird anhand einer Schichtplanung für Kranken-
schwestern gegeben.
8

2 Literaturüberblick
Schichtplanung mit dynamischer Programmierung
Ernst et al. (2004a) zählt 17 Veröffentlichungen, welche die dynamische Pro-
grammierung als Lösungsprinzip für ein scheduling oder rostering Problem
verwenden. In den meisten dieser wird DP zur Lösung des Subproblems eines
CGs verwendet, wobei das Subproblem als Kürzeste Wege Problem mit oder
ohne Ressourcenbeschränkung modelliert wird.
In Yunes et al. (2000) wird ein Crew Scheduling Problem anhand des Bei-
spiels von Busfahrern einer brasilianischen Metropole gelöst. (ii): Eine Menge
an Bustouren muss einer Menge an bestehenden Fahrern zugeteilt werden,
wobei die Kosten für den Einsatz der Fahrer minimiert wird. Hierbei muss ei-
ne maximale Arbeitszeit pro Tag und eine minimale Pausenzeit zwischen den
Schichten berücksichtigt werden. Überdies muss jeder Fahrer seinen Arbeitstag
am selben Busdepot beenden, an dem er die erste Tour begonnen hat. (iii):
Das Problem ist als hybrides Modell aus ganzzahliger Programmierung und
constraint programming modelliert und wird mit einem B&P gelöst. Das Sub-
problem, welches die Dienstblöcke erstellt, wird ähnlich wie in Desrochers und
Soumis (1989) als RCSP modelliert und mit einem DP gelöst. (iv): Es wer-
den jedoch keine detaillierten Informationen über die Modellierung des RCSPs
gegeben. Die beschriebene Methode löst Probleme für große Instanzen mit
150 Busrouten und 12 Millionen zulässigen Diensten.
In Beliën und Demeulemeester (2006) werden für ein belgisches Krankenhaus
die Einplanung von auszubildenden Ärzten beschrieben. Den Ärzten muss ein
Jahresplan zugeteilt werden, welcher die Stationen festlegt, auf denen sie in
Abhängigkeit ihrer gewählten Spezialisierung assistieren. (ii): Hierbei liegen
feste Arbeitszeiten vor. Folgende Nebenbedingungen werden berücksichtigt:
1) Bestimmte Stationen müssen von jedem Arzt durchlaufen werden, wobei
eine Mindest- und Höchstdauer für jede Station vorgeschrieben ist. 2) Die
Zeit in einer Station kann zeitlich nicht unterbrochen werden. 3) Präferen-
zen von Ärzten bzgl. ihrer zeitlichen Verfügbarkeit werden als soft-constraint
berücksichtigt. (iii): Das Problem wird mit einem B&P gelöst, wobei beim
Subproblem nicht wie üblich Spalten für die einzelnen Ärzte generiert werden,
sondern Spalten für die zu erfüllenden Aufgaben. Hierbei ist das Subproblem
als RCSP modelliert und wird als DP gelöst. Jede Stufe stellt eine Zeitperiode
dar, wobei ein Zustand durch die Kosten für die Einplanung der Ärzte definiert
wird. (iv): Der Algorithmus kann erweitert werden, um die n besten Spalten
zu generieren.
Eine gemeinsame Betrachtung der Schichtplanung von Krankenschwestern
und dem Erstellen des Operationsplans für Chirurgen wird in Beliën und
Demeulemeester (2008) aufgezeigt. (ii): Bei der Schichtplanung werden drei
Schichttypen eingeplant, wobei die Anzahl an Tagen mit Pause bzw. Arbeit
in Folge beschränkt ist. Zudem ist die gesamte wöchentliche Arbeitszeit, die
9

2 Literaturüberblick
Anzahl an Schichten in Folge, die Arbeit am Wochenende und der Übergang
zwischen verschiedenen Schichttypen restringiert. (iii): Das Problem ist als IP
formuliert und als B&P gelöst. Das Subproblem zur Generierung der einzel-
nen Schichtpläne ist ein Kürzteste Wege Problem und wird als DP gelöst.
Die Erstellung des Operationsplans erfolgt auch mithilfe eines B&Ps, wobei
das Subproblem als ein MIP dargestellt ist. Der Operationsplan bestimmt den
Bedarf an Krankenschwestern. Die gemeinsame Betrachtung erfolgt durch ein
lineares Programm, in welchem die Schichtpläne von Krankenschwestern und
die Arbeitszeit der Chirurgen kombiniert werden.
Die in dieser Arbeit behandelte Problemstellung ist eine Reformulierung
des Subproblems vom Spaltengenerierungsverfahren, welches in Brunner et al.
(2010) beschrieben wird. Dort wird die Schichtplanung von Ärzten behan-
delt. Die Besonderheit liegt in der großen Flexibilität des Ansatzes, der va-
riable Startzeiten, Arbeitsdauern, Überstunden und einen Bereitschaftsdienst
berücksichtigen kann, wobei die maximale Arbeitszeit eines Tages und einer
Woche eingehalten werden und eine tägliche Mittagspause und Mindestpau-
senlänge zwischen zwei Schichten zu berücksichtigen sind. Das beschriebene
Subproblem, welches als MIP gelöst wird, liefert nur für einfache Problemin-
stanzen eine Lösung in vertretbarer Zeit. Daher ist eine Reformulierung des
SPs notwendig.
Der Literaturüberblick zeigt, dass oftmals bei Schichtplanungsproblemen,
welche mit einem B&P gelöst werden, das Subproblem als Kürzeste Wege Pro-
blem reformuliert und auch mit einem DP gelöst wird. Bisher wurde jedoch
kein Ansatz veröffentlicht, welcher durch die Gestaltung der Nebenbedingun-
gen eine hohe Flexibilität bei der Erstellung des Schichtplans aufweist und bei
welchem die Schichten implizit modelliert werden, wie es in dieser Arbeit der
Fall ist.
10

3 Beschreibung des Schichtplanungsproblems
3 Beschreibung des Schichtplanungsproblems
In diesem Kapitel wird das Schichtplanungsproblem eingeführt. Zuerst werden
häufig vorkommende Begriffe erklärt. Anschließend wird in Kapitel 3.2 der
Zusammenhang der Schichtplanung zum Spaltengenerierungsverfahren
3
aus
Brunner et al. (2010) dargestellt. Im letzten Abschnitt werden die Neben-
bedingungen erläutert.
3.1 Begriffe der Schichtplanung
In dieser Arbeit werden insbesondere folgende Begriffe verwendet. Um Unklar-
heiten zu vermeiden, werden diese nun definiert.
Arbeit
Die reguläre Tätigkeit eines Arztes, welche eine Mindest-
und Höchstdauer an kontinuierlicher Arbeit besitzt. Des
Weiteren gibt es eine Höchstarbeitsdauer pro Woche.
Dienst
Ein Dienst ist die Abkürzung für den Bereitschaftsdienst.
Hierbei ist der Arzt 24 Stunden im Klinikum anwesend,
um unvorhergesehen auftretende Nachfrage zu decken. Ein
Teil des Dienstes wird in Abhängigkeit des Wochentages
zu der regulären Wochenarbeitszeit gezählt (näheres hierzu
in Kapitel 5.2.1). Die maximale Anzahl an Diensten eines
Arztes pro Woche ist restringiert.
Schicht
Eine Schicht eines Arztes umfasst die Zeit, in welcher ein
Arzt in der Arbeit oder im Dienst tätig ist.
Schichtplan
Ein Schichtplan stellt über einen begrenzten Zeithorizont
die Abfolge von Arbeit, Dienst und Pause für einen Arzt
dar.
Mittagspause
Während einer Arbeit muss ein Arzt eine Mittagspause ver-
bringen. Eine gewisse Dauer an Arbeitszeit vor bzw. nach
einer Mittagspause muss eingehalten werden.
Pause
Nach einer Schicht muss ein Arzt eine gewisse Zeit pausie-
ren, in welcher keine neue Schicht begonnen werden darf.
3
Für eine allgemeine Darstellung des Spaltengenerierungsverfahrens und mögliche Anwen-
dungen sei auf Desaulniers et al. (2005) verwiesen.
11

3 Beschreibung des Schichtplanungsproblems
3.2 Spaltengenerierungsverfahren zur Lösung der
Schichtplanung
Ein Schichtplan über sieben Tage mit 24 Perioden pro Tag, welcher in Ab-
bildung 1 in Kapitel 1 als Matrix mit 7
· 24 = 168 Einträge veranschaulicht
wird, kann ebenso als eine Spalte mit 168 Zeilen dargestellt werden. Hierbei
entsprechen die ersten 24 Zeilen dem ersten Tag des Schichtplans, die Zeilen
25­48 dem zweiten Tag usw.
Die Generierung eines zulässigen Schichtplans als Spalte entspricht dem
Subproblem aus dem Spaltengenerierungsverfahren, welches in Brunner et al.
(2010) beschrieben wird. Dort wird das CG im Rahmen eines Branch&Price
verwendet. Das Subproblem wird dort als ein MIP modelliert und gelöst. Ziel
dieser Arbeit ist es, dieses SP als ein Netzwerkflussproblem zu reformulieren,
und anschließend geeignet zu lösen, um die Lösungszeit zu verbessern.
Bei dem ursprünglichen CG werden für 16 Anästhesisten des Klinikums
rechts der Isar Schichtpläne gesucht, die den Bedarf an Ärzten decken und die
entstehenden Kosten optimieren. Im Masterproblem werden hierbei die Kos-
ten minimiert, welche durch Zuteilung von Ärzten auf die Schichtpläne ent-
stehen. Hierbei würde durch die Generierung aller möglichen Schichtpläne am
Anfang zu viele Kombinationsmöglichkeiten berücksichtigt werden müssen, so-
dass die Schichtpläne nacheinander im SP erzeugt werden. Im Lösungsprozess
wird das MP im ersten Schritt mit selbst erstellten Schichtplänen initialisiert
und relaxiert gelöst. Hierbei wird die Ganzzahligkeitsbedingung der Anzahl an
eingeteilten Ärzten auf reelle Zahlen gelockert. Die Werte der Dualvariablen
aus dem relaxierten MP werden dann benützt, um das SP zu lösen und mit
Hilfe der reduzierten Kosten die Güte eines dort erzeugten Schichtplans zu
bewerten.
Im MP gibt es drei Nebenbedingungen (NB), denen die in Klammern ange-
gebenen Dualvariablen zugeordnet werden. Diese sind:
NB I (
dem
ab
)
stellt ein ausreichendes Angebot an Ärzten zu jeder Peri-
ode (a, b) sicher, um die deterministische, periodenabhängi-
ge Nachfrage an Ärzten in regulärer Arbeit zu decken.
NB II (
D
ab
)
stellt wie NB I ein ausreichendes Angebot an Ärzten, welche
im Dienst benötigt werden, zu jeder Periode (a, b) sicher.
NB III (
conv
)
sorgt dafür, dass über alle Schichtpläne nicht mehr Ärzte
mit Qualifikation j als verfügbar eingeteilt werden. Sollten
in einer Periode zu wenig Ärzte zur Verfügung stehen, um
die Nachfrage zu decken, so können im MP externe Ärzte
eingeplant werden. Diese verursachen höhere Kosten.
12

3 Beschreibung des Schichtplanungsproblems
Abweichend von der Notation in Brunner et al. (2010) wird eine Periode
nicht mit t sondern mit (a, b) notiert.
Ziel des MPs ist es, die Kosten zu minimieren. Die zu minimierenden Kos-
ten, die mit den in Klammer angegebenen Kostenparameter bewertet werden,
bestehen aus den anfallenden Überstunden o
w
(c
over
) in einer Woche w und
den ausbezahlten Überstunden h
w
(c
paid
). Eine Überstunde der Woche w wird
ausbezahlt, wenn diese nicht durch Fehlstunden in der darauf folgenden Woche
w + 1 ausgeglichen werden kann. Für die Kosten eines Schichtplans c
sched
gilt:
c
sched
=
wW
(c
paid
h
w
+ c
over
o
w
)
Zudem sind die Kosten von externen Ärzten zu berücksichtigen, welche benö-
tigt werden, falls die Nachfrage nicht durch anwesende Ärzte gedeckt werden
kann. Würden externe Ärzte für die Deckung der Nachfrage nach regulärer
Arbeit bzw. Dienst benötigt werden, so würde dies durch den Wert der ent-
sprechenden nichtnegativen Dualvariable
dem
ab
bzw.
D
ab
gezeigt werden. Die
Dualvariable
dem
ab
ist in Perioden (a, b), in welchen im Masterproblem keine
Nachfrage nach Ärzten herrscht, Null, d. h. beispielsweise von 21 bis 7 Uhr.
D
ab
ist so modelliert, dass diese jeweils nur für die erste Periode in welcher ein
Dienst begonnen wird (also beispielsweise von 8 bis 9 Uhr) ungleich Null sein
kann. Für alle anderen Perioden nimmt diese den Wert Null an.
Daher geht diese Information über die Werte der Dualvariablen in das SP
ein und muss dort nicht explizit behandelt werden. Fixkosten, wie monatliche
Gehälter, werden nicht berücksichtigt, da die Anzahl der eingestellten Ärzte
fest ist und die entstehenden Fixkosten daher nicht minimiert werden können.
Die Güte eines im SP erzeugten Schichtplanes wird mit Hilfe der reduzierten
Kosten c einer Spalte des MPs festgestellt. Hierbei ist
c = c
sched
-
(a,b)A
(
dem
ab
· x
ab
)
-
(a,b)A
D
ab
· y
ab
-
conv
wobei x
ab
bzw. y
ab
eine Binärvariable ist, welche Eins ist, falls in der Peri-
ode (a,b) gearbeitet bzw. ein Dienst ausgeführt wird.
Für jede Iteration beim CG werden neue Werte der Dualvariablen vom MP
verwendet, um die reduzierten Kosten zu berechnen. Können für entsprechen-
de Werte der Dualvariablen
dem
ab
,
D
ab
und
conv
nur noch positive Werte für c
(Zielfunktion des Subproblems) erreicht werden, so können keine weitere Spal-
ten erzeugt werden, die den Zielfunktionswert des MPs verbessern würden und
die optimale Lösung des MPs ist gefunden.
Die Zielfunktion wird in den folgenden Kapiteln wegen den zusätzlich er-
läuterten Nebenbedingungen ergänzt. Allgemein ist in der Zielfunktion der
Parameter
conv
nicht berücksichtigt. Der Wert dieser Dualvariable stellt im
13

3 Beschreibung des Schichtplanungsproblems
Subproblem nur eine nichtnegative Konstante dar, welche in der Zielfunkti-
on unabhängig vom erzeugten Schichtplan subtrahiert wird. Es gilt für die
reduzierten Kosten
c Folgendes.
c
conv
0
In der vorliegenden Arbeit wird
conv
= 0 angenommen und somit kann dieser
Parameter weggelassen werden, ohne dass dies Einfluss auf die Lösung hätte.
3.3 Nebenbedingungen der Schichtplanung
Das Subproblem enthält Nebenbedingungen, welche für einen zulässigen Schicht-
plan erfüllt sein müssen. Die Modellierung der folgenden Nebenbedingungen
als MIP erfolgt in Kapitel 5.
· Jede Arbeitsschicht hat eine Mindest- und Höchstarbeitsdauer R
A
bzw.
R
A
, wobei eine Pause nicht zur Arbeitszeit gerechnet wird.
· Jeder Arzt besitzt eine maximale Wochenarbeitszeit R
WA
. Die Wochen-
arbeitszeit ergibt sich aus den gearbeiteten Schichten und der nicht aus-
bezahlten Arbeitszeit bei den Diensten. Eine Mindestwochenarbeitszeit
wird nicht modelliert. Diese ist im Tarifvertrag festgesetzt, jedoch wer-
den fehlende Stunden bis zur Mindestwochenarbeitszeit für Forschung
eingesetzt und brauchen deswegen nicht berücksichtigt werden.
· Nach einer Arbeitsschicht oder einem Dienst muss eine Pause einer defi-
nierten Mindestlänge R
P
eingehalten werden.
· Jeder Arzt hat eine vereinbarte Vertragsarbeitszeit v pro Woche w. Diese
kann durch Überstunden o
w
bis zur maximalen Wochenarbeitszeit R
WA
überschritten werden.
· Überstunden o
w
in einer Woche w werden ausbezahlt, falls sie durch
,,Fehlstunden" u
w+1
in der darauf folgenden Woche w + 1 nicht kompen-
siert werden können.
· In jeder Arbeitsschicht muss eine Mittagspause stattfinden, welche nach
mindestens T
pre
bzw. höchstens T
late
Arbeitsperioden stattfindet. Nach
der Mittagspause muss noch eine Mindestdauer T
post
gearbeitet werden.
· Die einzelnen Arbeitsschichten können zu beliebigen Zeitpunkten in ei-
ner Woche starten, wobei der Unterschied zwischen dem frühesten und
spätesten Startzeitpunkt in einer Woche auf T
win
begrenzt ist.
· Pro Woche kann ein Arzt für maximal N
D
Dienste eingeteilt werden.
14

4 Formulierung als Kürzeste Wege Problem
4 Formulierung als Kürzeste Wege Problem
Das Subproblem wird im Folgenden als Kürzeste Wege Problem mit Res-
sourcenbeschränkung im Rahmen eines Netzwerks modelliert. Jaumard et al.
(1998) beschreiben in ihrer Arbeit einen Ansatz, welcher die Planung der
Schichten von Krankenschwestern anhand eines RCSPs als Netzwerkfluss op-
timiert. Die Arbeit behandelt jedoch die verschiedenen möglichen Schichten
und ihre möglichen Kombinationen explizit.
In einem ersten Schritt wird der Graph für das Kürzeste Wege Problem ein-
geführt.
4
Dieser wird im zweiten Teilkapitel um die Ressourcenbeschränkungen
ergänzt.
4.1 Beschreibung des Graphen
Im Folgenden wird der Aufbau des Graphen beschrieben und die entsprechende
Notation eingeführt. Eine Darstellung für den Graphen zeigt Abbildung 2.
q
i
j
t
i - 2
i + 2
j - 2
j + 2
...
...
...
...
q+1
t-1
Abb. 2: Aufbau des Graphen G.
Graph
Sei G = (V, A) ein gerichteter, azyklischer Graph mit n = |V| topolo-
gisch sortierten Knoten v
1
, ...v
n
und m = |A| Kanten.
5
Eine gerichtete Kante
(im Weiteren nur als Kante bezeichnet) von v
a
nach v
b
wird im Folgenden als
(a, b) A, mit a, b V bezeichnet. Es gilt hierbei, dass 1
a < b
n ist, d. h.
dass alle Pfeile in Richtung Senke gerichtet sind. Es seien v
1
= q und v
2
= q +1
das Quellknotenpaar
6
und v
n-1
= t - 1 und v
n
= t das Senkenknotenpaar. Die
Knotenmenge
V wird in zwei disjunkte Mengen unterteilt, den oberen Knoten
V und den unteren Knoten V, wobei V V = V, V V = {} und |V| = |V| gilt.
Knoten i, j und a, b
Im Weiteren werden in dieser Arbeit, wenn nicht anders
gekennzeichnet, stets angenommen, dass i V und j V sind. Des Weiteren
seien a,b zwei beliebige Knoten mit a, b V.
4
Graphen, Netzwerke und Kürzeste Wege Probleme werden ausführlich in Ahuja et al.
(1993) und Jungnickel (1994) dargestellt.
5
Die Notation
|A| beschreibt die Mächtigkeit der Menge A.
6
Der erste Quellknoten q wird in der Nummerierung im Folgenden mit
q = 1 festgesetzt.
15

4 Formulierung als Kürzeste Wege Problem
Knotenpaar
Ein Knotenpaar [i,j] besteht aus einem obenliegenden Knoten
i V und einem untenliegenden Knoten j V, wobei es nicht möglich ist, von
einem dieser Knoten über Kanten zum anderen zu gelangen.
Vorgänger und Nachfolger
Jeder Knoten a V \ {q, q + 1, t - 1, t} besitzt
genau zwei direkte Vorgänger- und zwei direkte Nachfolgerknoten. Die zwei
Vorgänger- bzw. Nachfolgerknoten von a werden durch die Vorgängerrelation
a
-
bzw. Nachfolgerrelation a
+
bestimmt. Hierbei gibt a
-
V bzw. a
+
V den Vorgänger- bzw. Nachfolgerknoten von a aus den unteren Knoten an.
Entsprechend ist a
-
V bzw. a
+
V der Vorgänger- bzw. Nachfolgerknoten
von a aus den oberen Knoten. Die Knoten sind topologisch sortiert und so
nummeriert, dass im Knotenpaar [i,j] die Zahl des unteren Knotens j=i+1 ist.
Aus den oben genannten ergeben sich mit einem Knotenpaar [i,j] folgende
Beziehungen der Knoten zueinander, welche für das Verständnis der späteren
Formulierung als MIP (siehe Kapitel 5.1) notwendig sind:
· i - 2 = i
-
= j
-
· j = (j - 2)
+
= (i - 2)
+
· j - 2 = i
-
= j
-
· i + 2 = i
+
= j
+
· i = (j - 2)
+
= (i - 2)
+
· j + 2 = i
+
= j
+
Zeitpunkt und Periode
Jeder Knoten repräsentiert einen Zeitpunkt, wobei
dieser derselbe für ein Knotenpaar ist. Eine Kante (a, b) A stellt eine Peri-
ode (a, b) zwischen den Zeitpunkten a und b dar.
Arbeit und Pause
Ist bei einer Kante (a, b) der Endknoten b
V, so reprä-
sentiert diese Kante eine Arbeitsperiode. Ist der Endknoten b V, so stellt
diese Kante eine Pausenperiode dar.
In Abbildung 2 sind die Kanten (i - 2, i) bzw. (j - 2, i) entsprechend eine
Arbeitsperiode und die Kanten (i - 2, j) bzw. (j - 2, j) eine Pausenperiode.
Wird beispielsweise als Periodendauer eine Stunde gewählt, so stellen die
Knoten i - 2 und j - 2 jeweils den Zeitpunkt 9 Uhr dar und die Perioden
(
i - 2, i) bzw. (j - 2, i) repräsentieren die Zeit zwischen 9 und 10 Uhr, in
welcher gearbeitet wird.
Der Unterschied innerhalb der beiden Kanten ist folgender: Die Kanten
(i­2, i), welche mit einem oberen Knoten beginnen und enden, stellen eine
Fortsetzung einer Arbeitsperiode dar, d. h. in der Periode, welche zum Zeit-
punkt i - 2 endet, wurde bereits gearbeitet. Eine Kante mit untenliegendem
Anfangs- und obenliegenden Endknoten (j - 2, i) stellt einen Übergang von
Pause zu Arbeit dar, d. h. bis zum Zeitpunkt j - 2 wurde pausiert und an-
schließend wurde die Arbeit aufgenommen. Analog gilt für die Kanten, welche
16

4 Formulierung als Kürzeste Wege Problem
in einem unteren Knoten enden, dass (j - 2, j) mit j - 2, j V die Fort-
setzung einer Pause darstellen, wohingegen (i - 2, j) mit i - 2 V, j V
die erste Pausenperiode nach einer Arbeit ist. In Kapitel 5.1.1 werden diesen
Kanten binären Entscheidungsvariablen zugeordnet. Das nachfolgende Beispiel
und Abbildung 3 verdeutlichen den oben beschriebenen Zusammenhang.
Pfad
Ein Pfad ~
P = (e
1
, ...e
n
) ist eine Sequenz von Kanten, beginnend bei
Kante e
1
bis Kante e
n
. Diese kann auch als Sequenz der durchschrittenen
Knoten P = (v
1
, v
2
, ..., v
k-1
, v
k
, ..., v
n
, v
n+1
) dargestellt werden, wobei v
k
ein
direkter Nachfolger von v
k-1
und v
1
=
{q q + 1} und v
n+1
=
{t - 1
t} sind.
7
Ein Pfad repräsentiert einen Schichtplan. Kanten (i
-
, i) stellen eine
Arbeitsperiode im Schichtplan dar und Kanten (j
-
, j) eine Pausenperiode.
1
3
5
7
9
11
2
4
6
8
10
12
Abb. 3: Arbeit und Pause auf dem Graphen G.
Beispiel
In Abbildung 3 ist als Veranschaulichung ein Graph über 5 Perioden
dargestellt, mit q = 1 und t = 12. Eine durchgezogene Kante bedeutet, dass
diese Kante auf dem Pfad benutzt wird, wohingegen eine gestrichelte Kante
unbenutzt bleibt. Der gezeichnete Pfad gibt eine Schicht an, in welcher der
Arzt in der ersten Periode pausiert (die untere Kante (2
, 4) wird auf dem Pfad
benutzt). Danach fängt er in der zweiten Periode an zu arbeiten. Dies wird
durch Kante (4, 5) dargestellt. Er setzt seine Arbeit in der dritten Periode
mit Kante (5, 7) fort und hat die erste Pause in der vierten Periode. Kante
(7, 10) stellt diesen Übergang der Arbeit auf den oberen Knoten zur Pause auf
den unteren Knoten dar. In der letzten Periode (10, 12) pausiert der Arzt eine
weitere Periode. Zu beachten sind auch die unterschiedliche Interpretationen
einer der vier verschiedenartig laufenden Kanten im Schichtplan. Bei Kante
(2, 4) bzw. (10, 12) wird eine Pause fortgesetzt. Kante (5, 7) repräsentiert die
Fortsetzung einer Arbeit bzw. eines Dienstes. Die erste Periode einer Pause
kennzeichnet Kante (7, 10) und Kante (4, 5) stellt die erste Arbeitsperiode
dar.
7
Es gilt für die Anzahl der durchschrittenen Knoten vom Quellknotenpaar zum Senkekno-
tenpaar, dass
|P | =
1
2
(
|V| - 2) =
1
4
|A|.
17

4 Formulierung als Kürzeste Wege Problem
Kantengewichte
Um den Aufbau des Netzwerkes zu vervollständigen, wer-
den den Kanten des Graphen G Gewichte zugeordnet, sodass der bisherige
Graph G = (V, A) zu G = (V, A, ) erweitert wird. Hierbei entspricht ei-
nem Vektor der nichtnegativen Dualvariablenwerte = (
dem
ab
,
D
ab
) aus dem
Master Problem des Spaltengenerierungsverfahrens von Brunner et al. (2010).
Die Dualvariablenwerte hängen von der Periode (a, b) ab. Mit Hilfe dieser kön-
nen die reduzierten Kosten des neuen Schichtplans berechnet werden. Es gilt
R
+
0
× R
+
0
.
Die Kantengewichte sind für Pausenperioden stets Null. In Perioden, in
denen gearbeitet werden kann, ist
dem
ab
0. Der Wert der Dualvariable für
den Dienst ist stets Null, bis auf die Periode, in welcher der Dienst gestartet
werden kann. In dieser Periode ist
D
ab
0.
4.2 Erweiterung um Ressourcenbeschränkungen
Der bisherige Graph G = (V, A, ) wird in diesem Kapitel erweitert. Es werden
Ressourcen hinzugefügt, um die Abbildung der verschiedenen Nebenbedingun-
gen eines Schichtplans zu ermöglichen. Eine ausführliche Grundlage über die
generelle Formulierung eines RCSPs wird in Zhu (2005) und Grünert und Ir-
nich (2005b) gegeben.
Ressourcen
Es werden vier verschiedene Ressourcenvariablen eingeführt, wel-
che für Arbeit A, Wochenarbeit WA, Pause P und Dienst D stehen. Diese
Ressourcenvariablen R
r
(a) mit r T = {A, WA, P, D} werden jedem Kno-
ten a V zugeordnet.
8
Sie sind ganzzahlig und zählen den Verbrauch an der
Ressource r bis zum Zeitpunkt a, d. h. die Dauer, welche bis zum Zeitpunkt a
beispielsweise gearbeitet oder pausiert wurde.
Wenn die Variable R
P
(26) = 7 ist, bedeutet dies, dass im Knoten 26, d. h.
nach Ablauf von zwölf Perioden, sieben Perioden pausiert wurden. Es ist zu
beachten, dass die Ressourcen ,,zurücksetzbare" Ressourcen sind, d. h. sie kön-
nen in bestimmten Situationen auf einen Anfangswert zurückgesetzt werden,
z.B. werden die Ressource P , A und D am Ende der ersten Periode einer Pau-
se, Arbeit oder Dienstes auf den Wert Eins gesetzt. Die Ressource WA wird
am Anfang der Woche auf den Wert Null gesetzt.
Ressourcenfenster
Ein Ressourcenfenster [R
r
, R
r
]
a
wird auf jedem Kno-
ten a festgesetzt, welches den Bereich festsetzt, in dem sich die Ressource r im
Knoten a befinden muss. Dieses kann für jeden Knoten individuell definiert
werden. Für die Modellierung ist es ausreichend zwischen Knoten aus
V bzw.
V zu unterscheiden. Hierbei sind, da es keine Mindestwochenarbeitszeit und
8
Da
R
WA
(
a) für a V stets Null ist, könnte R
WA
(
a) nur für a V definiert werden. Aus
Gründen der einheitlichen Nomenklatur wird darauf jedoch verzichtet.
18

4 Formulierung als Kürzeste Wege Problem
Höchstpausendauer gibt, R
WA
= 0 bzw. R
P
=
und können daher aus der
Problemformulierung weggelassen werden.
Mit Hilfe der Ressourcenfenster und der Ressourcenvariablen können die
Mindest- und Höchstdauern von Arbeit, Wochenarbeit, Pause und Dienst mo-
delliert werden.
Ressourcenverbrauch
Es könnte ein Ressourcenverbrauch u
ab
mit (a, b) A
definiert werden. Dieser wäre auf jeder Kante (a, b) für alle Ressourcen aus
T jeweils Eins, da jede Kante eine einstündige Periode darstellt und der Ver-
brauch an Arbeit, Dienst bzw. Pause pro Periode somit genau Eins ist.
Da in Kapitel 5 einer Kante (a, b) binäre Entscheidungsvariablen zugeord-
net werden, welche Eins sind, wenn diese Kante durchschritten wird, kann der
Ressourcenverbrauch weggelassen werden. Wird eine Kante (a, b) durchschrit-
ten, so ist die entsprechende Binärvariable Eins und kann für die Bestimmung
des Ressourcenverbrauchs benutzt werden.
Die Erweiterung des Modells zu einer feineren Zeitunterteilung der Perioden
ist möglich, indem die Ressourcenfenster entsprechend erhöht werden. Bei-
spielsweise müsste bei einer halbstündigen Periodeneinteilung die maximale
Wochenarbeitszeit von 48 auf 96 Einheiten verdoppelt werden.
q
i
j
t
i - 2
i + 2
j - 2
j + 2
(i-2)i
...
...
...
...
q+1
t-1
(j-2)i
[R
r
, R
r
]
i+2
R
r
(i)
R
r
(j)
[R
r
, R
r
]
j+2
Abb. 4: Graph
G
mit
Ressourcenvariablen,
Ressourcenfenstern
und
Kantengewichten.
Zulässiger Pfad
Ziel im RCSP ist es, einen zulässigen ,,kürzesten" Pfad von
einem Quellknoten zu einem Senkeknoten zu finden. Würde man die Gewichte
als Entfernung zwischen zwei Knoten interpretieren, würde man eigentlich den
längsten Pfad von der Quelle zur Senke suchen, da die Gewichte
ab
einer
Periode (a, b) nichtnegativ sind. Jedoch wird in der Zielfunktion
c
sched
-
(a,b)A
(
dem
ab
· x
ab
)
-
(a,b)A
D
ab
· y
ab
-
conv
19

4 Formulierung als Kürzeste Wege Problem
(vlg. Kapitel 3 bzw. 5) über die negativen
ab
summiert, wodurch sich ein
,,kürzester" Pfad ergibt. Der gefundene Pfad entspricht einem Schichtplan für
das Subproblem.
Abbildung 4 zeigt den Graphen G mit den Ressourcenfenstern, Ressour-
cenvariablen und Kantengewichten. Um den Graphen übersichtlich zu halten,
sind die Ressourcenfenster bzw. Ressourcenvariablen nur für jeweils zwei Kno-
ten gezeigt, obwohl diese auf jedem Knoten definiert sind. Die Kantengewichte
sind nur für diejenigen Kanten eingezeichnet, an denen diese ungleich Null
sein können (wobei
D
(i-2)i
nach Definition stets Null ist). Dies sind die Kanten,
welche eine Arbeits- bzw. Dienstperiode darstellen.
20

5 Gemischt ganzzahliges Programm
5 Gemischt ganzzahliges Programm
Aufbauend auf der Modellierung als RCSP über den Graphen G = (V, A, )
wird im folgenden Abschnitt das Problem, einen zulässigen ,,kürzesten" Pfad
von der Quelle zur Senke zu finden, als gemischt ganzzahliges Programm formu-
liert. Zuerst wird das Grundmodell des MIPs beschrieben. Dieses berücksich-
tigt Mindest- und Höchstdauern an Arbeit, Wochenarbeit und Pause. In Ab-
schnitt 5.2 wird dieses Modell erweitert. Nebenbedingungen für den Dienst, die
Überstunden, die Mittagspause und das Zeitfenster der verschiedenen Start-
zeitpunkte werden ergänzt. Das vollständige Modell des MIPs mit allen Ne-
benbedingungen ist in Anhang A aufgeführt.
Für eine Beschreibung anderer Lösungsverfahren sei auf Zhu (2005) und
Ziegelmann (2001) verwiesen. Das Buch von Williams (1999) stellt ein gutes
Nachschlagewerk dar, um IPs und MIPs zu modellieren.
5.1 Beschreibung des grundlegenden MIPs
In diesem Kapitel wird das grundlegende MIP beschrieben. Zuerst wird die
Notation und das gemischt ganzzahlige Programm dargestellt. Im nächsten
Abschnitt werden die Nebenbedingungen erläutert. Als letztes wird begründet,
warum die Ressourcenvariablen relaxiert werden können.
5.1.1 Notation des MIPs
Um festzustellen, welche Kante auf dem Graphen benutzt wurde, wird für
Arbeit und Pause die binären Entscheidungsvariablen x
i
-
i
bzw. x
j
-
j
mit i
V
und j V definiert. Sei
x
i
-
i
=
1, wenn der Arzt in der Periode (i
-
, i) mit i V arbeitet
0, sonst
und
x
j
-
j
=
1, wenn der Arzt in der Periode (j
-
, j) mit j V pausiert
0, sonst
Die beiden Variablen x
i
-
i
bzw. x
j
-
j
unterscheiden sich darin, auf welchen Kan-
ten sie verlaufen. Da x
i
-
i
auf Kanten mit einem oberen Endknoten liegt, gibt
diese Variable an, ob in einer Periode gearbeitet wird. Die Variable x
j
-
j
ist
entsprechend auf einer Kante mit unterem Endknoten und gibt eine Pausen-
periode an.
Den Graphen mit den Binärvariablen zeigt Abbildung 5. Aus Gründen der
Übersichtlichkeit sind die in Abbildung 4 angegebenen Ressourcenvariablen,
21

5 Gemischt ganzzahliges Programm
Ressourcenfenster und Kantengewichte nicht noch einmal dargestellt. Man er-
kennt, dass die Kanten mit den Binärvariablen x
(j-2)i
bzw. x
(i-2)i
eine Arbeits-
periode und die Kanten mit x
j(j+2)
bzw. x
i(j+2)
eine Pausenperiode darstellen.
q
i
j
t
i - 2
i + 2
j - 2
j + 2
x
(i-2)i
x
j(j+2)
...
...
...
...
q+1
t-1
x
i(j+2)
x
(j-2)i
Abb. 5: Graph G mit Binärvariablen von Arbeit und Pause.
Von den vier binären Entscheidungsvariablen einer Periode (z.B. x
(i-2)i
,
x
(j-2)i
x
(i-2)j
und x
(j-2)j
) nimmt genau eine den Wert Eins an. Aus der Kom-
bination der Binärvariablen kann somit ein Schichtplan erstellt werden. Ab-
bildung 1 in Kapitel 1 zeigt einen Ausschnitt eines solchen Plans über sieben
Tage (wobei in dem Plan auch ein Dienst berücksichtigt ist).
Um das Grundmodel als MIP zu lösen, wird folgende Notation verwendet.
Diese beinhaltet teilweise Notationen, welche erst in der Erweiterung benötigt
werden. Um Wiederholungen zu vermeiden, werden diese bereits an geeigneter
Stelle in diesem Kapitel erwähnt.
Indizes und Mengen
A
Index für Arbeit
WA
Index für Wochenarbeit
P
Index für Pause
D
Index für Dienst
W
Menge der Wochen im Planungshorizont,
W {1, 2, ...}
T
Menge der Tage in einer Woche
V
Menge aller Knoten
V
Menge der obenliegenden Knoten,
mit
V = {i|i mod 2 = 1 : i V} V
V
Menge der untenliegenden Knoten,
mit
V = {j|j mod 2 = 0 : j V} V
V
s
w
Teilmenge der obenliegenden Knoten bei dem seit Beginn der Woche
w eine Periode vergangen ist, mit
V
s
w
=
{i|i mod K
w
= 3 : i V} V
T
Menge der Ressourcen, mit
T = {A, WA, P, D}
i
Index eines obenliegenden Knotens, mit i
V
j
Index eines untenliegenden Knotens, mit j V
w
Index für Wochen
22

5 Gemischt ganzzahliges Programm
r Index für Ressourcen, mit r A
q Index des Knotens mit der kleinsten Nummer, mit q = 1
t
Index des Knoten mit der höchsten Nummer, mit t = |V|
Parameter
K
w
Anzahl an Knoten pro Woche, mit K
w
= (
|V| - 2)\|W|
R
r
Höchstdauer der Ressource r T
R
r
Mindestdauer der Ressource r T
dem
ab
Wert der Dualvariable der Nebenbedingung I aus dem Masterproblem,
mit (a, b) A
M
Positive, genügend große Zahl
9
Binäre Entscheidungsvariablen
x
i
-
i
1, wenn der Arzt in Periode (i
-
, i) arbeitet, 0 sonst
x
j
-
j
1, wenn der Arzt in Periode (j
-
, j) pausiert, 0 sonst
Ganzzahlige Entscheidungsvariablen
R
r
(a) Höhe der Ressource r T im Knoten a V
Subproblem
Minimiere
iV
(
-
dem
i
-
i
x
i
-
i
)
(1)
unter den Bedingungen, dass
NB: Flusserhaltung
r(q)
+
x
qr
+
s(q+1)
+
x
(q+1)s
= 1
(2)
pa
-
x
pa
-
sa+
x
as
= 0
a V \ {q, q + 1, t - 1, t} (3)
r(t-1)
-
x
r(t-1)
+
st
-
x
st
= 1
(4)
NB: Ressourcenverbrauch
R
A
(i)
R
A
(i
-
) + x
i
-
i
i V
(5)
R
A
(i)
R
A
(i
-
) + x
i
-
i
- M · x
i
-
i
i V
(6)
R
A
(i)
M(1 - x
i
-
i
) + 1
i V
(7)
R
A
(i)
x
i
-
i
i V
(8)
9
Für M muss gelten:
M
max
{R
A
- 1, R
D
- 1, R
P
,
1
2
· K - T
win
, T
pre
- 1, T
post
+ 1
- R
A
, R
A
- T
late
+ 1
}.
Einige dieser Parameter werden später in Kapitel 5.2 eingeführt.
23

5 Gemischt ganzzahliges Programm
R
A
(j) = R
A
(j
-
) + M(1 - x
j
-
j
)
j V
(9)
R
WA
(i) = x
i
-
i
+ x
i
-
i
i V
s
w
(10)
R
WA
(i) = R
WA
(i
-
) + x
i
-
i
+ x
i
-
i
i V \ V
s
w
(11)
R
P
(j)
R
P
(j
-
) + x
j
-
j
j V
(12)
R
P
(j)
M(1 - x
j
-
j
) + 1
j V
(13)
R
P
(i)
M(1 - x
i
-
i
) + R
P
(i
-
)
i V
(14)
NB: Ressourcenfenster
R
A
(j)
R
A
j V
(15)
R
r
(i)
R
r
i V, r {A,WA}
(16)
R
P
(i)
R
P
i V
(17)
Variablendefinition
x
a
-
a
{0, 1}
a V
(18)
R
r
(a) N
0
r {A,WA,P} , a V
(19)
5.1.2 Erläuterung des MIPs
Im Folgenden werden die Zielfunktion und Bedingungen (2)­(19) näher erläu-
tert.
Zielfunktion (1)
Die Zielfunktion minimiert die negative Summe aus den
Kantengewichten
dem
i
-
i
der Kanten, welche auf dem gewählten Pfad von der
Quelle zur Senke liegen. Es könnte statt der Minimierung über die negative
Summe auch ein Maximierungsproblem über die positive Summe formuliert
werden. Diese Formulierung würde jedoch von dem ursprünglichen Ziel ab-
weichen, die reduzierten Kosten einer neuen Spalte für ein Masterproblem zu
minimieren. Die vollständige Zielfunktion, welche die reduzierten Kosten einer
Spalte darstellt, ergibt sich nach Erweiterung des Modells und ist in Kapitel
5.2.3 beschrieben.
NB für Flusserhaltung (2)­(4)
Der erste Block (2)­(4) formuliert die Fluss-
bedingungen für die Quellknoten q und q+1, die Senkeknoten t - 1 und t und
jeden dazwischen liegenden Knoten. Aus Bedingung (2) geht hervor, dass in
die Quellknoten q und q+1 eine Mengeneinheit eingespeist wird. Dies bedeu-
tet, dass genau eine der binären Variablen den Wert Eins annimmt. Analog
legt Bedingung (4) fest, dass in den Senkeknoten t - 1 und t eine Mengen-
einheit abgegeben wird. Die Bedingung (3) stellt sicher, dass die Summe aller
in den Knoten a V \ {q, q + 1, t - 1, t} einfließenden Variablen die Summe
aller ausfließenden Variablen ist. Da aus der Quelle genau eine Variable den
24

5 Gemischt ganzzahliges Programm
Wert Eins annimmt, verursacht diese Bedingung, dass pro Periode genau eine
binäre Variable auf den Kanten ungleich Null ist.
NB für Ressourcenverbrauch (5)­(14)
Der Nebenbedingungsblock (5)­(14)
weist den Ressourcenvariablen R
r
(a) mit a V ihre Werte zu. Die Bedingun-
gen (5)­(9) bestimmen hierbei die Werte der Variable R
A
(a) der Ressource
Arbeit:
· Wird zu arbeiten begonnen, d. h. ist x
i
-
i
= 1, so wird durch (7) und (8)
der Wert von R
A
(i) auf 1 gesetzt.
· Wird auf einer Kante (i
-
, i) die Arbeit fortgesetzt, d. h. x
i
-
i
= 1 und
x
i
-
i
= 1, so wird durch (5) und (6) der Wert der Ressource R
A
(i) auf dem
Endknoten der Kante um Eins höher als R
A
(i
-
) auf dem Startknoten der
Kante gesetzt.
· Wird pausiert, so berechnet Bedingung (9) den Wert von R
A
(j) für die
unteren Knoten j V. Es gilt: x
j
-
j
= 1
R
A
(j) = R
A
(j
-
). Dies ist
notwendig, um mit Bedingung (15) überprüfen zu können, ob der Arzt
die Mindestarbeitszeit R
A
absolviert hat, bevor er nach dem Zeitpunkt
j
-
in die Pause geht.
Bedingungen (12)­(14) bestimmen den Wert der Ressource Pause. Es ist
zu beachten, dass keine
-Nebenbedingungen, wie für Ressource A notwen-
dig sind, da keine Maximalpausenlänge vorhanden ist. Als Folge wurden die
Nebenbedingungen so formuliert, dass die Pausenlänge R
P
(a) nach einer Pau-
senperiode um Eins erhöht werden kann, aber nicht muss:
· Am Ende einer Arbeit, d. h. x
j
-
j
= 1, kann R
P
(j) durch die Bedin-
gung (13) auf den Wert Eins gesetzt werden.
· Wird in einer Periode (j
-
, j) die Pause fortgesetzt (x
j
-
j
= 1), so kann
nach (12) die Ressource R
P
(j) am Ende der Periode um maximal Eins
höher als R
P
(j
-
) am Anfang der Periode sein.
· Wird nach einer Pause eine Arbeit begonnen (x
i
-
i
= 1), so wird die
bisherige Pausenlänge bei einem Knoten i
V durch (14) bestimmt.
Dies ist notwendig, um mit der Bedingung (17) überprüfen zu können,
ob der Arzt die Mindestpausenlänge R
P
eingehalten hat und eine neue
Arbeit beginnen kann.
Der Wert der Ressource Wochenarbeit R
WA
(i) wird durch die Bedingun-
gen (10) und (11) berechnet. Es handelt sich bei allen Bedingungen um Glei-
chungen, da die Ressource R
WA
kontinuierlich in der Woche nach oben gezählt
wird und zu einem bestimmten Zeitpunkt (Ende der ersten Periode einer Wo-
che) zurückgesetzt wird:
25

5 Gemischt ganzzahliges Programm
· In Bedingung (10) wird die Ressource R
WA
(i) am Wochenbeginn auf den
Wert 0 oder 1 zurückgesetzt. Der Wochenbeginn wird durch die Kno-
tenmenge
V
s
w
beschrieben und beinhaltet nicht die Anfangsknoten der
nullten sondern der ersten Periode.
10
Somit wird die Ressource R
WA
(i)
auf Eins gesetzt, falls in der nullten Periode bereits gearbeitet wurde,
d. h. die Variable x
i
-
i
= 1 ist.
· Die Wochenarbeitszeit für jeden oberen Knoten i, ausgenommen den
Knoten aus
V
s
w
wird durch Bedingung (11) berechnet. Falls gearbeitet
wird, erhöht sich die Wochenarbeitszeit um Eins.
NB für Ressourcenfenster (15)­(17)
Dieser Block dient zur Einhaltung
der Mindest- und Höchstressourcendauer. Die Ressourcen A und P haben eine
Mindestdauer, welche durch Bedingungen (15) bzw. (17) eingehalten wird.
Bedingung (16) setzt die Höchstdauer für Ressourcen A und WA fest.
Durch Bedingungen (15) und (16) wird das Ressourcenfenster von Arbeit
folgendermaßen eingehalten. Befindet man sich auf den oberen Kanten, d. h. es
wird gerade gearbeitet, so kann man erst einen unteren Knoten betreten, falls
man die erforderliche Mindestarbeitszeit R
A
absolviert hat. Hierzu wird, falls
eine Pause aufgenommen wird (also x
j
-
j
= 1 ist), durch Bedingung (9) der
Wert der Variable R
A
(j
-
) an die Variable R
A
(j) übergeben. Es muss nach (15)
gelten, dass die Ressource R
A
(j)
R
A
ist.
Gilt R
A
(j) < R
A
so kann x
j
-
j
aus Bedingung (9) nicht Eins werden, d. h.
die Mindestarbeitszeit ist noch nicht erfüllt, um in die Pause zu gehen. Für die
Höchstdauer der Arbeit gilt, dass man sich höchstens so lange auf den oberen
Kanten aufhalten kann, solange R
A
(i)
R
A
erfüllt ist.
Bedingung (16) für die Wochenarbeit überprüft für alle oberen Knoten, ob
noch eine weitere Periode gearbeitet werden kann oder bereits die maximale
Wochenarbeitszeit
11
R
WA
erreicht worden ist. Diese Bedingung ist analog der
Bedingung für die Einhaltung der Höchstarbeitsdauer der Ressource A.
Die Einhaltung der Pause erfolgt folgendermaßen. Die Mindestpausendauer
wird durch die Bedingung (17) auf den oberen Knoten überprüft. Es kann nur
eine Arbeit aufgenommen werden, wenn die Mindestpausendauer R
P
bereits
geruht wurde. Wird eine Arbeit aufgenommen (x
i
-
i
= 1), so überträgt Bedin-
gung (14) den Wert der Ressource ,,Pause" R
P
(i
-
) des unteren Knoten i
-
auf
die Variable R
P
(i) des oberen Knoten i. Durch Bedingung (17) kann so über-
10
Es ist nicht möglich,
R
WA
(
i) = 0 für die Wochenanfangsknoten (Montag 0 Uhr) zu setzen,
da diese gleichzeitig die Wochenendknoten der Vorwoche (Sonntag 24 Uhr) sind. Somit
würde der Wert von
R
A
(
j) in Bedingung (30) für den letzten Tag der Woche w stets
Null ergeben. Die Einführung von
V
s
w
ist wichtig für die Berechnung von Überstunden
und Fehlstunden, welche in Kapitel 5.2.2 besprochen werden.
11
Es sei daran erinnert, dass
R
WA
die vertragliche Wochenarbeitszeit
v plus die möglichen
Überstunden ist. Die Überstunden werden in Kapitel 5.2.2 eingeführt.
26

5 Gemischt ganzzahliges Programm
prüft werden, ob die Mindestpausendauer eingehalten wurde und eine Arbeit
aufgenommen werden kann.
Variablendefinition (18)­(19)
Die Definition der Variablen ist in (18)­(19)
beschrieben. Hierbei kann die Ganzzahligkeit bei den Ressourcenvariablen R
r
(a)
in Bedingung (19) relaxiert werden. Dies wird im folgenden Abschnitt erklärt.
5.1.3 Relaxierung der Ressourcenvariablen
Die Ganzzahligkeit bei den Ressourcenvariablen R
r
(a) wird durch Nebenbedin-
gungen (5)­(17) erzwungen und kann daher relaxiert werden. Im Folgenden
wird dies für die einzelnen Ressourcenvariablen R
r
(a) mit r {A, WA, P }
erläutert.
Ganzzahligkeit von
R
A
(a)
Die Ganzzahligkeit von R
A
(a) ergibt sich aus
den Bedingungen (5)­(8) und (16).
· Ist x
i
-
i
= 1, so ergibt sich durch (5) und (6) der Wert von R
A
(i) aus
der Addition von R
A
(i
-
) und der Binärvariablen x
i
-
i
. Ist also R
A
(i
-
)
ganzzahlig, so gilt dies auch für R
A
(i). Der Wert R
A
(i
-
) ist ganzzahlig,
da der Wert der Variable R
A
(i) im ersten oberen Knoten q, nämlich
R
A
(q) = 0 ist. Es wird stets R
A
(q) = 0 gelten, da sonst die Beschränkung
auf das ganzzahlige R
A
durch Bedingung (16) nicht komplett ausgenutzt
werden kann.
· Ist x
i
-
i
= 1, so wird durch (7) und (8) erzwungen, dass R
A
(i) = 1 ist.
· Ausgehend von diesem Wert, ergeben sich nach (5) und (6) die weiteren
Werte für R
A
(i) aus der Addition des Wertes der Ressource R
A
(i
-
) und
der Binärvariablen x
i
-
i
. Der Wert R
A
(i
-
) ist entweder Eins, falls dies
durch (7) und (8) erzwungen wurde, oder er ergibt sich aus Addition des
Wertes Eins und einer endlichen Anzahl an binären Variablen.
· Ist x
j
-
j
= 1, so ist der Wert R
A
(j) für den unteren Knoten j gleich dem
ganzzahligen Wert R
A
(j
-
) des oberen Knotens j
-
.
Ganzzahligkeit von
R
WA
(a)
Die Ganzzahligkeit von R
WA
ergibt sich ähnlich
wie für R
A
.
· Für i V
s
w
ergibt sich R
WA
(i) nach (10) aus Addition von binären Va-
riablen.
· Für i V \ V
s
w
errechnet sich R
WA
(i) nach (11) aus der Addition von
binären Variablen und des Wertes der Ressource vom oberen Vorgänger-
knoten R
WA
(i
-
). Dieser Wert ist - analog zur obigen Begründung bei der
27

5 Gemischt ganzzahliges Programm
Ressource A - entweder Eins oder ergibt sich aus Addition von Eins mit
einer endlichen Anzahl an Binärvariablen.
Ganzzahligkeit von
R
P
(a)
Bei der Ganzzahligkeit von R
P
ist zu berücksich-
tigen, dass es nur eine Minimalpausendauer R
P
gibt. Um die Zielfunktion zu
minimieren, ist es günstig, nach einer Schicht so früh wie möglich die nächs-
te zu beginnen. Dies ist der Fall, da die
dem
ab
bzw.
D
ab
nur ungleich Null sein
können und daher zur Minimierung der Zielfunktion beitragen können, falls in
der Periode (a, b) eine Schicht ausgeführt wird. Daher ist das Lösungsverfah-
ren bestrebt, die Werte für R
P
(a) so groß wie möglich zu wählen, wodurch es
ausreichend ist, nur
­Bedingungen aufzustellen.
· Beginnt der Arzt eine Pause in der Periode (x
j
-
j
= 1), so ist nach Be-
dingung (13) der größtmögliche Wert für R
P
(j) Eins.
· Vom ganzzahligen Wert Eins ergeben sich die weiteren Werte von R
P
(j)
für die unteren Knoten j V aus Bedingung (12), indem die binäre
Variable x
j
-
j
addiert wird.
· Beginnt der Arzt nach einer Pause eine Arbeit (x
i
-
i
= 1), so ist der
größte Wert für R
P
(i) gleich R
P
(i
-
). Um Bedingung (17) so früh wie
möglich erfüllen zu können, muss der Wert R
P
(i) ganzzahlig sein, da die
Ressourcenschranke R
P
auch ganzzahlig ist.
5.2 Einführung weiterer Nebenbedingungen
Die Lösung des Grundmodells (1)­(19) erzeugt einen Schichtplan, welcher die
tägliche Mindest- und Höchstarbeitszeit, die Mindestpausenlänge und die wö-
chentliche Höchstarbeitszeit berücksichtigt. Um die Qualität des Schichtplans
zu erhöhen und alle Nebenbedingungen aus dem ursprünglichen Subproblem
aus Brunner et al. (2010) zu berücksichtigen, wird das Modell um mehrere
Faktoren erweitert. Zuerst wird in Kapitel 5.2.1 der Einbezug eines Dienstes
erläutert, dann wird in Kapitel 5.2.2 gezeigt, wie Überstunden im MIP berück-
sichtigt werden können. Kapitel 5.2.3 erweitert das bisherige Modell um eine
Mittagspause und Kapitel 5.2.4 behandelt die Einschränkung der unterschied-
lichen Startzeitpunkte in einer Woche.
Am Anfang jedes dieser Kapitel wird eine Problembeschreibung gegeben.
Darauf folgend werden notwendige Ergänzungen der Notation und der Ne-
benbedingungen im Vergleich zum Grundmodell eingeführt. In einem dritten
Abschnitt werden jeweils die neuen bzw. modifizierten Nebenbedingungen er-
läutert.
28

5 Gemischt ganzzahliges Programm
5.2.1 Berücksichtigung eines Dienstes
Problembeschreibung
Der Bereitschaftsdienst bzw. Dienst wird eingeführt,
damit in den Stunden, in denen kein planmäßiger OP-Betrieb herrscht (in
der Nacht bzw. am Wochenende) die Nachfrage an Ärzten gedeckt ist. Im
betrachteten Fall des Klinikums rechts der Isar beginnt von Montag bis Freitag
ab 16 Uhr ein 16-Stunden Dienst. Vor Antreten des Dienstes muss der Arzt
noch eine 8 Stunden Schicht arbeiten, sodass im Gesamten sein Arbeitstag um
8 Uhr beginnt und 24 Stunden später endet. Am Samstag und Sonntag gibt
es keine geplanten Operationen, sodass der Dienst von 8 Uhr startet und bis
8 Uhr des nächsten Tages geht.
Beide Dienstarten, sowohl die kombinierte Dienstart an Wochentagen, als
auch der ,,reine" Dienst am Wochenende können als ein 24 Stunden Dienst
dargestellt werden. Im Folgenden wird daher die Modellierung des Dienstes so
vereinfacht, dass dieser stets 24 Stunden dauert.
Neben der Dienstlänge ist die Bedingung einzuhalten, dass der Arzt nach
einem Dienst die Mindestpausenlänge von R
P
pausieren muss. Die maximale
Anzahl an Diensten pro Woche ist auf N
D
Dienste
12
beschränkt.
Die Dienste beginnen in der gewählten Modellierung jeweils um 8 Uhr. Die
Menge aller untenliegenden Knoten bei denen der Dienst D in Woche w startet
(welche also 8 Uhr repräsentieren) wird mit
V
D
w
bezeichnet.
Ein Teil der Dienstzeit wird in Abhängigkeit des Tages zu der Wochenar-
beitszeit hinzugezählt. Hierbei gilt für den am Sonntag beginnenden Dienst,
dass die 8 Stunden, welche in die nächste Woche ragen, als Arbeitszeit dieser
nächsten Woche zählen. Tabelle 1 zeigt, wie viele Stunden bei welchem Dienst
ausbezahlt bzw. zu der Wochenarbeitszeit angerechnet werden.
Wochentag
Angerechnete Stunden
Ausbezahlte Stunden
Montag - Donnerstag
16
8
Freitag
8
16
Samstag
0
24
Sonntag
8
13
16
Tab. 1: Zur Wochenarbeitszeit angerechnete und ausbezahlte Stunden eines
Dienstes.
12
wobei
N
D
4 für den Fall, dass
R
P
> 0. Da der Dienst stets zur selben Uhrzeit beginnt,
muss bei
R
P
> 0 zwischen zwei Diensten ein Tag ohne Dienst sein.
13
Diese 8 Stunden werden als reguläre Arbeitszeit für die folgende Woche berücksichtigt.
29

5 Gemischt ganzzahliges Programm
Notation
Um den Dienst auf dem Graphen zu berücksichtigen, wird eine
neue Variable eingeführt. Diese ist
y
i
-
i
=
1, wenn der Arzt in der Periode (i
-
, i) mit i
V einen Dienst hat
0, sonst
und
y
j
-
j
=
1, wenn der Arzt in der Periode (j
-
, j) mit j V die erste Periode
nach einem Dienst pausiert
0, sonst
Als Binärvariable, welche die Fortsetzung einer Pause angibt (also im Graphen
auf einer unteren Kante j
-
j läuft) kann die Variable x
j
-
j
auch für den Dienst
verwendet werden. Es wird keine neue Variable y
j
-
j
benötigt. Die bisher einge-
führten Binärvariablen zeigt Abbildung 6. Allen Kanten bis auf (j, j + 2) sind
durch die Einführung des Dienstes nun zwei Binärvariablen zugeordnet.
q
i
j
t
i - 2
i + 2
j - 2
j + 2
x
(i-2)i
y
(i-2)i
x
j(j+2)
...
...
...
...
q+1
t-1
x
i(j+2)
y
i(j+2)
x
(j-2)i
y
(j-2)i
Abb. 6: Graph G mit Binärvariablen von Arbeit, Pause und Dienst.
Die bisherige Notation wird folgendermaßen erweitert, um den Dienst zu
modellieren:
Indizes, Mengen und Parameter
K
d
Anzahl an Knoten pro Tag
D
ab
Wert der Dualvariablen der Nebenbedingung II aus dem
Masterproblem, mit (a, b) A
V
D
w
Teilmenge der untenliegenden Knoten bei denen der Dienst D in
Woche w startet, mit V
D
w
=
{j|j mod K
d
= 2(S
D
+ 1) : j V} V
N
D
Maximale Anzahl an Diensten pro Woche
R
D
Höchstdauer des Dienstes
R
D
Mindestdauer des Dienstes
Variablen
R
D
(a) Höhe der Ressource D im Knoten a V
30

5 Gemischt ganzzahliges Programm
Es werden zusätzlich folgende Nebenbedingungen eingefügt bzw. modifiziert.
R
D
(i)
R
D
(i
-
) + y
i
-
i
+ y
i
-
i
i V
(20)
R
D
(i)
R
D
(i
-
) + y
i
-
i
+ y
i
-
i
- M(1 - y
i
-
i
)
i V
(21)
R
D
(i)
M(1 - y
i
-
i
) + 1
i V
(22)
R
D
(i)
y
i
-
i
i V
(23)
R
D
(j) = R
D
(j
-
) + M(1 - y
j
-
j
)
j V
(24)
R
r
(j)
R
r
j V, r {A,D}
(15b)
R
r
(i)
R
r
i V, r {A,WA,D} (16b)
R
D
(a) N
0
a V
(25)
y
i
-
i
, y
ii
+
{0, 1}
i V
(26)
Erläuterung
Der Nebenbedingungsblock (20)­(26) bestimmt die Werte der
Variable R
D
(a) der Ressource ,,Dienst". Diese sind ähnlich den Bedingun-
gen (5)­(9) der Ressource ,,Arbeit" definiert:
· Wird ein Dienst in Periode (i
-
, i) begonnen, so wird durch (22) und (23)
der Wert von R
D
(i) auf Eins gesetzt.
· Wird in der Periode (i
-
, i) der Dienst fortgesetzt, so erhöhen (20) und (21)
den Wert der Ressource R
D
(i) um Eins im Vergleich zum Wert R
D
(i
-
).
· Wird nach einem Dienst pausiert, so überträgt Bedingung (24) den Wert
der Ressource R
D
(j
-
) auf die Ressource R
D
(j). Mit Bedingung (15b)
kann nun überprüft werden, ob die Mindestdienstlänge R
D
eingehalten
wurde.
· Bedingung (16b) überprüft, ob die Höchstdienstlänge nicht überschritten
wurde, d. h. es muss R
D
(i)
R
D
gelten.
· Um die feste Dauer (24 Stunden) des Dienstes zu modellieren, wird die
Mindestdauer gleich der Höchstdauer R
D
= R
D
gesetzt.
· Die Bedingungen (25) bzw. (26) setzten den Definitionsbereich der Va-
riablen y bzw. R
D
fest.
Da nun neben der Variable x
j
-
j
auch die Variable y
j
-
j
die erste Periode
einer Pause angibt, müssen Bedingungen (13) und (14) modifiziert werden.
Dies ist notwendig, da dieselbe Ressource R
D
(a) die Pausenlänge sowohl nach
einer Arbeit, als auch nach einem Dienst misst. Es muss jeweils die Variable
y
j
-
j
in den Nebenbedingungen ergänzt werden, sodass
R
P
(j)
M(1 - x
j
-
j
- y
j
-
j
) + 1
j V
(13b)
R
P
(i)
M(1 - x
i
-
i
- y
i
-
i
) + R
P
(i
-
)
i V
(14b)
31

5 Gemischt ganzzahliges Programm
gilt.
Die hinzugefügten Binärvariablen müssen auch in den Flussbedingungen in-
tegriert werden. Die Änderung der Bedingungen (2) für die Quelle bzw. (4) für
die Senke wird in Kapitel 5.2.3 nach Erläuterung der Mittagspause erklärt, da
durch die Mittagspause die Bedingungen (2) und (4) weiter modifiziert werden
müssen.
Bedingung (3) wird durch Berücksichtigung des Dienstes folgendermaßen
geändert.
pa
-
x
pa
+ y
pa
-
sa+
x
as
+ y
as
= 0
a V \ {q, q + 1, t - 1, t}
(3b)
Zu beachten bei (3b) ist, dass die Variable y
a
-
a
und y
aa
+
, jeweils für a V
nicht existieren, da die Fortsetzung einer Pause bereits durch die Variable x
aa
+
mit a V abgedeckt wird.
Die Modifikation von (3) hätte zur Folge, dass die folgenden Bedingun-
gen (27)­(28) zum Modell hinzugefügt werden müssten, da es möglich wäre,
dass ein Dienst bzw. Arbeit mit der Variablen für Arbeit bzw. Dienst fortge-
setzt wird.
y
pi
+ x
is
1
i V, p i
-
, s i
+
(27)
x
pi
+ y
is
1
i V, p i
-
, s i
+
(28)
Die Bedingungen (27) und (28) stellen sicher, dass eine begonnene Arbeit nur
durch die entsprechenden x-Variablen fortgesetzt und beendet werden kann.
Dies gilt auch für einen Dienst, welcher durch y-Variablen gekennzeichnet ist.
Es ist nicht möglich, dass ein begonnener Dienst durch x-Variablen fortgesetzt
wird.
Alternativ zur Flusserhaltungsbedingung (3b) und den Bedingungen (27)
und (28) wäre es möglich, (3b) getrennt nach oberen bzw. unteren Knoten
und Arbeit bzw. Dienst zu betrachten. Dies hätte den Vorteil, dass Bedingun-
gen (27) und (28) nicht mehr notwendig wären. Die Anzahl an erforderlichen
Restriktionen würde gleich bleiben. Folgende Bedingungen würden an Stelle
von (3b) benötigt werden:
pi
-
x
pi
-
si+
x
is
= 0
a V \ {q, t - 1}
(3.1)
pi
-
y
pi
-
si+
y
is
= 0
a V \ {q, t - 1}
(3.2)
(
pj
-
x
pj
+ y
j
-
j
)
- (
sj+
y
js
+ y
jj
+
) = 0
a V \ {q - 1, t}
(3.3)
Die Bedingungen (3.1) und (3.2) sorgen dafür, dass für eine begonnene Arbeit
die Variablen x
i
-
i
bzw. x
ii
+
und für einen begonnenen Dienst stets die Varia-
32

5 Gemischt ganzzahliges Programm
blen y
i
-
i
bzw. y
ii
+
verwendet werden. Der Fall, dass in einer Periode (i
-
, i) ein
Dienst begonnen wird und in der nächsten Periode dieser mit der Variable x
ii
+
fortgesetzt wird bzw. der umgekehrte Fall sind somit ausgeschlossen. Somit
sind mit Formulierung (3.1)­(3.3) die Bedingungen (27) und (28) überflüssig.
Die maximale Anzahl an Diensten N
D
, welche einem Arzt pro Woche w
zugeteilt werden können, wird durch Bedingung (29) sichergestellt.
jV
D
w
y
jj
+
N
D
w W
(29)
Die Summe über alle Perioden in einer Woche, in denen ein Dienst gestartet
wird, also y
jj
+
= 1, darf höchstens der Anzahl an erlaubten Diensten N
D
entsprechen.
Wird ein Dienst begonnen, so wird auch das Kantengewicht
D
i
-
i
in der Mi-
nimierung der Zielfunktion berücksichtigt. Die Zielfunktion ändert sich zu
Minimiere
-
iV
(
dem
i
-
i
· x
i
-
i
+
D
i
-
i
· y
i
-
i
)
(1b)
Zu berücksichtigen ist, dass der Parameter
D
i
-
i
lediglich in der ersten Peri-
ode eines Dienstes ungleich Null sein kann. Daher werden nur diese Werte
berücksichtigt, da alle anderen Werte Null sind.
5.2.2 Berücksichtigung von Überstunden und Fehlstunden
Problembeschreibung
Ein Arzt besitzt die vertraglich vereinbarte Wochen-
arbeitszeit v. Abweichend von dieser Arbeitszeit kann er maximal insgesamt
R
WA
Stunden pro Woche arbeiten. Der größte Wert der Variable o
w
N
0
, wel-
che die Überstunden zählt, ist somit R
WA
-v. Fehlstunden, die in einer Woche
auftreten, betreffen den Fall, dass weniger als v Stunden gearbeitet werden.
Fehlstunden werden mit der Variablen u
w
N
0
gemessen. Neben den Über-
stunden gibt es ausbezahlte Überstunden h
w
N
0
. Es wird laut Tarifvertrag
eine Überstunde der Woche w ausbezahlt, wenn diese nicht durch Fehlstunden
in der darauf folgenden Woche w + 1 ausgeglichen werden kann.
Um die Abweichung von der Wochenarbeitszeit v bewerten zu können, muss
neben der reinen Arbeitszeit auch die Zeit berücksichtigt werden, welche von
den Diensten teilweise auf die Wochenarbeitszeit angerechnet wird. Tabelle 1
bietet einen Überblick über entsprechende Zeiten. Um diese Information im
MIP zu berücksichtigen, wird eine Funktion f
1
(j) eingeführt. Diese gibt die
Stundenanzahl vom im Knoten j V
D
w
beginnenden Dienst D an, welche zur
regulären Wochenarbeitszeit R
WA
addiert wird.
Die Arbeitszeit eines Dienstes am Sonntag wird auf den Montag der fol-
genden Woche angerechnet. Um dies zu berücksichtigen, wird eine Knoten-
menge ^
V
D
w
eingeführt. Diese Teilmenge der untenliegenden Knoten bei denen
33

5 Gemischt ganzzahliges Programm
der Dienst D in Woche w startet, enthält die Knoten des Dienstbeginns vom
Sonntag der Vorwoche bis Samstag der aktuellen Woche. Dies bedeutet, dass
alle Dienste, welche zu der Wochenarbeitszeit einer Woche w beitragen, in der
Menge berücksichtigt sind. In ^
V
D
w
sind für w = 1 nur sechs Knoten enthalten,
da es keinen Sonntag der Woche 0 gibt.
14
Notation
Insgesamt wird durch die Modellierung von Überstunden und Fehl-
stunden die Notation folgendermaßen erweitert.
Mengen, Parameter und Funktionen
W
0
Menge der Wochen im Planungshorizont einschließlich der Vorwoche,
mit
W
0
=
W {0}
^
V
D
w
Teilmenge der untenliegenden Knoten bei denen der Dienst D
in Woche w startet zur Berechnung von v
V
e
w
Teilmenge des letzten untenliegenden Knotens der Woche w,
mit
V
e
w
=
{j|j = w · K
w
+ 1 : j V w W} V
u
v
Vertragsarbeitszeit pro Woche
c
paid
Kosten für eine ausbezahlte Überstunde h
w
c
over
Kosten für eine Überstunde o
w
f
1
(j) Gibt die Stundenanzahl des im Knoten j V
D
w
beginnenden
Dienstes D an, welche zur regulären Wochenarbeitszeit R
WA
addiert wird
Variablen
o
w
Anzahl an Überstunden in Woche w W
0
u
w
Anzahl an ,,Fehlstunden" in Woche w W
h
w
Anzahl an ausbezahlten Überstunden in Woche w W
Folgende Bedingungen ergänzen das bisherige Modell, um die Werte von o
w
,
u
w
und h
w
bestimmen zu können.
v =
jV
e
w
R
W A
(j) +
j^
V
D
w
f
1
(j) · y
jj
+
- o
w
+ u
w
w W
(30)
h
w
o
w-1
- u
w
w W
(31)
o
w
{0, 1, ..., R
WA
- v}
w W
(32)
u
w
{0, 1, ..., v}
w W
0
(33)
h
w
{0, 1, ..., R
WA
- v}
w W
(34)
14
Für Initialisierungen, bei welcher Werte von Woche 0 eingeplant werden, siehe Kapitel
5.2.5
34

5 Gemischt ganzzahliges Programm
Erläuterung
In (30) wird zur Bestimmung von o
w
, u
w
und h
w
die Summe aus
der bis Ende der Woche regulär gearbeiteten Zeit R
W A
(j) und der aus Diensten
anrechenbaren Arbeitszeit f
1
(j) gebildet. Übersteigt diese Summe den Wert v
der Vertragsarbeitszeit, so erhöht sich der Wert o
w
der Überstunden. Ist die
Summe kleiner als v, so erhöht sich u
w
.
Die ausbezahlten Überstunden h
w
werden mit Nebenbedingung (31) berech-
net, wobei nur diejenigen Überstunden aus o
w-1
der Woche w - 1 angerechnet
werden, welche durch Fehlstunden in der darauf folgenden Woche w nicht aus-
geglichen werden können.
Die anfallenden Kosten durch Überstunden werden auch in der Zielfunktion
berücksichtigt. Die Kostenparameter sind c
over
für Überstunden und c
paid
für
ausbezahlte Überstunden. Gilt c
over
> c
paid
, so können in einer Woche w nicht
sowohl o
w
> 0 als auch u
w
> 0 sein, da über beide Variablen in der Zielfunktion
minimiert wird.
15
Für die modifizierte Zielfunktion gilt
Minimiere
wW
(c
paid
h
w
+ c
over
o
w
)
-
i
V
(
dem
i
-
i
x
i
-
i
+
D
i
-
i
y
i
-
i
)
(1c)
Die Bedingung (1c) stellt die Zielfunktion dar, falls keine Mittagspause be-
rücksichtigt wird. Durch die Einführung einer Mittagspause ist eine weitere
Änderung notwendig.
Die Variablen o
w
, u
w
und h
w
sind nach oben beschränkt, positiv und ganz-
zahlig. Die Bedingungen (32)­(34) geben die entsprechenden Beschränkungen
an. Die Ganzzahligkeit dieser Variablen kann auf
R
+
0
relaxiert werden. Durch
die Bedingung (30) wird o
w
und u
w
zur Ganzzahligkeit gezwungen, da alle
anderen Variablen bzw. Parameter dieser Bedingung aus
N
0
sind. Die Variable
h
w
wird durch die Bedingung (31) und durch die Zielfunktion zur Ganzzah-
ligkeit gezwungen. Den kleinsten Wert, welchen h
w
im Minimierungsproblem
annehmen kann, ist genau die Differenz der ganzzahligen Variablen o
w-1
und
u
w
. Somit muss h
w
ganzzahlig sein.
15
Als Beispiel zur Illustration sei bei einem dreiwöchigen Schichtplan mit vertraglicher Wo-
chenarbeitszeit von 42 Stunden die Wochenarbeitszeiten 48, 42 und 36 Stunden. Würden
nun durch die Variablen
o
w
> 0 und u
w
> 0 in der ersten und zweiten Woche 6 Über-
stunden und in der zweiten und dritten Woche 6 Fehlstunden veranschlagt werden, so
würde die Einplanung der Fehlstunden in der zweiten Woche für Überstunden in der
ersten Woche aufkommen, d. h.
h
2
wäre Null. Da tatsächlich keine Fehlstunden gemacht
wurden, müssten auch 6 Überstunden in der zweiten Woche eingeplant werden. Diese
würden nicht die ausbezahlten Überstunden
h
3
erhöhen, da in der dritten Woche tat-
sächlich 6 Fehlstunden gemacht werden. Die gleichzeitige Einplanung von Überstunden
und Fehlstunden in der zweiten Woche hätte somit den Effekt
h
w
zu minimieren, jedoch
nur durch ,,künstliche" Überstunden. Wird daher
c
over
> c
paid
gesetzt, so ist dieser Effekt
nicht günstig, da sowohl die Überstunden
o
w
als auch die ausbezahlten Überstunden
h
w
in der Zielfunktion minimiert werden und anhand der Kostenparameter die Minimierung
von
o
w
günstiger für die Zielfunktion ausfällt.
35

5 Gemischt ganzzahliges Programm
5.2.3 Berücksichtigung einer Mittagspause
Problembeschreibung
An jedem Tag, an dem gearbeitet wird, ist im Schicht-
plan eine Mittagspause über eine Periode berücksichtigt. Für einen Dienst wird
keine Mittagspause bestimmt. Vor einer Mittagspause muss der Arzt mindes-
tens T
pre
Stunden und höchstens T
late
Stunden gearbeitet haben. Nach der
Mittagspause muss er noch T
post
Stunden arbeiten. Für die Berücksichtigung
der Mittagspause wird eine weitere Binärvariable q
ab
benötigt, welche nur für
die beiden Kanten (j
-
, j) und (j, j
+
) definiert ist. Sei
q
j
-
,j
=
1, wenn der Arzt in der Periode (j
-
, j) mit j V eine
Mittagspause hat
0, sonst
und
q
j,j
+
=
1, wenn der Arzt nach einer Mittagspause in der Periode (j, j
+
)
mit j V die erste Periode arbeitet
0, sonst
Abbildung 7 zeigt eine Mittagspause auf dem Graphen G. Auf den durchge-
zogenen Kanten sind die angegebenen Binärvariablen Eins. Die Mittagspause
erfolgt in Periode (i-2,j), sodass die Variable q
(i-2)j
= 1 ist.
16
Die erste Periode
nach der Mittagspause, in der gearbeitet wird, ist (j, i + 2). Dies wird durch
die Variable q
j(i+2)
, welche den Wert Eins annimmt, verdeutlicht.
i
j
i - 4
i - 2
i + 2
i + 4
j - 4
j - 2
j + 2
j + 4
x
(i-4)(i-2)
x
(i+2)(i+4)
q
(i-2)j
q
j(i+2)
...
...
...
...
Abb. 7: Graph G mit Binärvariablen der Mittagspause.
16
Die Kante (
i - 2, j) ist identisch mit der Kante (j
-
, j).
36

5 Gemischt ganzzahliges Programm
Notation
Zur Berücksichtigung der Mittagspause wird das Modell um fol-
gende Notation ergänzt.
Mengen und Parameter
T
pre
Mindestdauer an Arbeit vor Aufnahme einer Mittagspause
T
late
Höchstdauer an Arbeit vor Aufnahme einer Mittagspause
T
post
Mindestdauer an Arbeit nach Beendigung einer Mittagspause
V
w,d
Teilmenge der untenliegenden Knoten von einem Tag d in
der Woche w, mit V
w,d
=
{j|(w - 1)K
w
+ 2 + (d - 1)K
d
j
(w - 1)K
w
+ dK
d
: j V, w W, d D} V
Für die Einhaltung der Mittagspause werden folgende Bedingungen im Mo-
dell ergänzt.
q
j
-
j
R
A
(j
-
)
- (T
pre
- 1) + M(1 - q
j
-
j
)
j V
(35)
q
j
-
j
R
A
(j
-
)
- (T
late
- 1) - M(1 - q
j
-
j
)
j V
(36)
q
jj
+
(T
post
+ 1)
- [R
A
(j + 2 · T
post
- 1) - R
A
(j
-
)]
- M(1 - q
jj
+
)
j V
(37)
q
jj
+
- q
j
-
j
= 0
j V
(38)
jV
w,d
(x
jj
+
- q
j
-
j
) = 0
w W, d D (39)
q
i
-
i
, q
ii
+
{0, 1}
i V
(40)
Erläuterung
Im Folgenden werden die Bedingungen (35)­(40) näher erläu-
tert.
· Die Bedingung (35) legt fest, dass der Beginn einer Mittagspause erfolgen
kann, nachdem mindestens
T
pre
Perioden gearbeitet wurde. Wird die
Mittagspause zum Zeitpunkt j
-
begonnen, also q
j
-
j
= 1, so kann (35)
zu R
A
(j
-
)
T
pre
umgeformt werden.
· Es dürfen höchstens T
late
Perioden bis zu einer Mittagspause gearbeitet
worden sein. Ist q
j
-
j
= 1, so folgt aus (36), dass R
A
(i)
T
late
sein muss.
· Nach einer Mittagspause müssen noch mindestens T
post
Perioden gear-
beitet werden. Dies wird durch die Bedingung (37) sichergestellt. Hierbei
wurde im Knoten
j
-
die Mittagspause begonnen, sodass die vor Aufnah-
me der Mittagspause geleistete Arbeit R
A
(j
-
) beträgt. Die Arbeit R
A
im oberen Knoten (j + 2 · T
post
- 1), welcher T
post
Perioden nach En-
de der Mittagspause ist, muss abzüglich der Arbeit R
A
(j
-
) mindestens
T
post
betragen. Anders formuliert muss für q
jj
+
= 1 gelten, dass R
A
(j +
2
· T
post
- 1) - R
A
(j
-
)
T
post
ist.
37

5 Gemischt ganzzahliges Programm
· Die Bedingung (38) erzwingt, dass die Mittagspause genau eine Periode
dauert und danach die Variable q
jj
+
für die erste Arbeitsstunde nach der
Pause verwendet wird.
17
· Bedingung (39) fordert, dass pro Tag genau eine Mittagspause erfolgt,
falls gearbeitet wird.
· Bedingung (40) definiert die Variable q als Binärvariable.
Durch das Einführen einer Mittagspause mit der Variablen q
jj
+
, welche eben-
so wie x
ii
+
anzeigt, ob eine Arbeit fortgesetzt wurde, müssen die folgenden
Nebenbedingungen modifiziert werden, in denen die Variable x
ii
+
enthalten ist
(welche aus Gründen der Notation in den Nebenbedingungen als x
i
-
i
geschrie-
ben wird). Es wird jeweils die Variable q
i
-
i
hinzugefügt.
R
A
(i)
R
A
(i
-
) + x
i
-
i
+ q
i
-
i
i V
(5b)
R
A
(i)
R
A
(i
-
) + x
i
-
i
+ q
i
-
i
- M · x
i
-
i
i V
(6b)
R
WA
(i) = R
WA
(i
-
) + x
i
-
i
+ x
i
-
i
+ q
i
-
i
i V \ V
s
w
(11b)
Durch die Bedingungen (5b), (6b) und (11b) werden die Ressourcen R
A
(i)
bzw. R
WA
(i) nun auch um Eins erhöht, wenn die Arbeit mit der Variablen q
i
-
i
nach einer Mittagspause fortgesetzt wird.
Die Flussbedingungen müssen auch angepasst werden. Die folgenden Bedin-
gungen beinhalten auch die Änderungen, welche sich durch Einführung des
Dienstes ergaben, bisher jedoch nicht vermerkt wurden.
rq
+
(x
qr
+ y
qr
) +
s(q+1)
+
(x
(q+1)s
) + y
(q+1)(q+1)
+
= 1
(2b)
pa
-
(x
pa
+ y
pa
+ q
pa
)
-
sa+
(x
as
+ y
as
+ q
as
) = 0
a V \ {q, q + 1, t - 1, t} (3c)
r(t-1)
-
(x
r(t-1)
+ y
r(t-1)
) +
st
-
x
st
+ y
t
-
t
= 1
(4b)
Da eine Schicht nicht mit einer Mittagspause beginnen kann bzw. eine
Schicht nicht mit einer Mittagspause enden kann, enthalten Bedingungen (2b)
und (4b) nicht die Binärvariable q
ab
der Mittagspause.
Bedingung (2b) besagt, dass von allen Binärvariablen, die aus den Quellen
entspringen, nur eine den Wert Eins annehmen kann. Von allen Variablen, wel-
che in die Senkeknoten münden, kann durch Bedingung (4b) ebenso nur eine
17
Es ist wichtig, dass für die erste Arbeitsperiode nach einer Mittagspause eine andere
Variable als
x
jj
+
bzw.
y
jj
+
verwendet wird, da diese spezifische Bedeutungen besitzen
und anderen Nebenbedingungen zugeordnet sind.
38

5 Gemischt ganzzahliges Programm
Binärvariable ungleich Null sein. Die Bedingung (3c) bestimmt die Flusserhal-
tung für alle Knoten, außer den Quellknoten und Senkeknoten.
Die Zielfunktion muss ebenso um q
i
-
i
erweitert werden und es ergibt sich
die neue Zielfunktion:
Minimiere
wW
(c
paid
h
w
+ c
over
o
w
)
-
iV
(
dem
i
-
i
(x
i
-
i
+ q
i
-
i
) +
D
i
-
i
· y
i
-
i
) (1d)
5.2.4 Berücksichtigung eines Zeitfensters
Problembeschreibung
Der Startzeitpunkt der Arbeit ist beliebig, liegt je-
doch zwischen dem frühesten Zeitpunkt S
A
, an welchem die Nachfrage nach
Ärzten beginnt und dem spätesten Zeitpunkt E
A
, an dem die Nachfrage endet.
Damit im Schichtplan einer Woche für einen Arzt die Zeiten des Arbeitsbe-
ginns nicht zu sehr auseinander weichen, werden diese auf maximal T
win
Stun-
den begrenzet. Hierzu wird der späteste Arbeitszeitbeginn in der Woche w
bestimmt und der Variablen l
w
zugewiesen. Diese Variable wird mit jedem
weiteren Startzeitpunkt der Woche w verglichen. Die Differenz darf höchstens
T
win
betragen.
Notation
Zur Bestimmung des frühesten Startzeitpunktes pro Woche wird
die Notation wie folgt ergänzt.
Mengen, Parameter und Funktionen
S
A
Zeitpunkt, zu dem die reguläre Arbeit A frühestens beginnt
E
A
Zeitpunkt, zu dem die reguläre Arbeit A spätestens endet
T
win
Maximale Länge zwischen frühestem und spätestem Arbeitsbeginn
pro Woche
f
2
(j) Funktion, welche jeder Nummer eines Knotens j V eine
Knotennummer des ersten Tages zuweißt, mit
f
2
(j) : V
j mod K
d
,
für j mod K
d
= 0
K
d
,
für j mod K
d
= 0
Die folgenden Nebenbedingungen bestimmen den spätesten Startzeitpunkt und
sorgen für die Einhaltung des Zeitfensters T
win
.
l
w
1
2
jV
w,d
f
2
(j) x
jj
+
- 2
w W, d D
(41)
l
w
-
1
2
jV
w,d
f
2
(j) x
jj
+
- 2
T
win
+ M(1 -
jV
w,d
x
jj
+
)
w W, d D
(42)
39

5 Gemischt ganzzahliges Programm
l
w
{S
A
, · · · , E
A
- R
A
}
w W
(43)
Erläuterung
Die Nebenbedingungen (41) und (42) begrenzen die Dauer zwi-
schen den verschiedenen Startzeiten der Arbeit in einer Woche w auf T
win
.
Hierbei berechnet Bedingung (41) den spätesten Schichtbeginn in der Wo-
che w. Beginnt eine Schicht im Knoten j, so ergibt das Produkt aus f
2
(j) und
x
jj
+
den Startknoten dieser Schicht bezogen auf den ersten Tag. Von dieser
Zahl müssen 2 abgezogen werden und das Ergebnis halbiert werden, um den
Startzeitpunkt als Uhrzeit zu erhalten. Erfolgt beispielsweise der Start einer
Schicht am dritten Tag der ersten Woche um 9 Uhr, also im Knoten j = 116, so
ergibt f
2
(116) = 20. Davon 2 subtrahiert und das Ergebnis halbiert resultiert
in der Startzeit (20
- 2)/2 = 9 Uhr. Nach (41) nimmt dabei l
w
den größten
aller Schichtbeginne einer Woche w an.
Wird am Tag d der Woche w gearbeitet, also gilt
jV
w,d
x
jj
+
= 1, so
folgt aus Bedingung (42), dass die Differenz zwischen dem spätesten Schicht-
beginn l
w
einer Woche und dem Schichtbeginn des Tages d höchstens T
win
sein
darf.
Relaxation von
l
w
Die Ganzzahligkeit von l
w
kann auf
R
+
0
relaxiert werden.
In Bedingung (41) setzt sich die rechte Seite der Gleichung aus Multiplikation
und Subtraktion ganzzahliger Werte zusammen, muss also einen ganzzahligen
Wert ergeben. Somit ist l
w
größer gleich einem ganzzahligen Wert.
In Bedingung (42) ist die rechte Seite ganzzahlig, falls
jV
w,d
x
jj
+
= 1,
also an einem Tag d gearbeitet wird. Auf der linken Seite wird von l
w
et-
was Ganzzahliges abgezogen. Es wird nun überprüft, ob l
w
abzüglich etwas
Ganzzahligem kleiner oder gleich dem ganzzahligen Zeitfenster ist. Ein ma-
ximales Zeitfenster ist nur möglich, falls l
w
den kleinstmöglichen Wert aus
Bedingung (41) annimmt, welcher ganzzahlig ist.
5.2.5 Werte des vorherigen Planungshorizonts
Der Schichtplan wird über einen vorher bestimmten Planungshorizont erstellt.
Dieser ist in sich abgeschlossen und nimmt keine Informationen von vorherigen
Schichtplänen auf. Um dies zu ändern, kann die Information etwaiger Über-
stunden aus der Vorwoche des aktuellen Planungshorizonts, also Woche 0,
durch Einführen eines Parameters o
0
festgesetzt werden.
Wird am Sonntag der Woche 0 gearbeitet, so kann mit einem Parameter
R
P
indirekt das Ende der Arbeit in den aktuellen Planungshorizont überge-
ben werden. R
P
gibt an, wie viele Stunden vor Beginn des Planungshorizonts
(Montag 0 Uhr) bereits pausiert wurden. Hierdurch ergibt sich der frühest
mögliche Starttermin am ersten Tag des Schichtplans. Vor Aufnahme einer
Arbeit müssen mindestens R
P
Stunden Pause sein.
40

5 Gemischt ganzzahliges Programm
Die Zuweisung
R
P
(q + 1) = R
P
(44)
übergibt die bisherige Pausendauer an die Ressourcenvariable des unteren
Quellknotens q+1. Falls die Arbeit zu jedem Zeitpunkt am ersten Tag des
Planungshorizonts beginnen kann, so muss der Wert R
P
= R
P
gesetzt werden.
Wird beispielsweise am Sonntag bis 21 Uhr gearbeitet, so werden bis Mon-
tag 0 Uhr drei Stunden pausiert, also wird der Wert von R
P
= 3 gesetzt.
Wird bis 8 Uhr am ersten Montag noch ein Dienst vom Sonntag der Vorwoche
ausgeführt, so wird dies durch die Einstellung R
P
=
-8 berücksichtigt.
Falls in einer Woche nicht die maximale Wochenarbeitszeit R
WA
zur Verfü-
gung steht, wird dies durch den Parameter R
A
w
mit w W berücksichtigt, wel-
cher angibt, wie viele Arbeitsstunden in Woche w nicht zur Verfügung stehen.
Eine Anwendung wäre denkbar, falls beispielsweise am Sonntag der Vorwoche
ein Dienst begonnen wurde. Die acht Stunden, welche der Arbeitszeit in der
ersten Woche des Planungshorizonts übergeben werden, könnten durch R
A
w
ab-
gebildet werden. Hierfür muss die Bedingung (30) abgeändert werden, indem
zu der bisherigen Wochenarbeitszeit der Wert von R
A
w
dazugezählt wird:
v =
jV
e
w
R
WA
(j) +
j^
V
D
w
f
1
(j) · y
jj
+
+ R
A
w
- o
w
+ u
w
w W
(30b)
5.3 Preprocessing
Die Anzahl der Variablen und Nebenbedingungen des ganzen Modells inklu-
sive aller Erweiterungen entspricht O(|V|). Die davon benötigte Anzahl der
Variablen zur Berechnung der optimalen Lösung ist ein Teil, da eine Vielzahl
an Binärvariablen nicht benötigt werden und ihnen daher der Wert Null zu-
gewiesen werden kann. Berücksichtigt man den Zeitrahmen, in dem ein Arzt
eine Arbeit ausführen kann bzw. einen Dienst beginnen kann, die Mindestar-
beitszeit und die Parameter T
pre
bzw. T
post
, so können Variablen, welche in
bestimmten Knoten starten, auf den Wert Null gesetzt werden. Dies bedeutet,
dass über die entsprechende Kante der Fluss nicht laufen kann.
Zur Beschreibung des Preprocessing sind folgende neue Parameter notwen-
dig. S
D
beschreibt den Zeitpunkt, zu welchem der Dienst beginnt. Dieser ist
identisch mit dem Zeitpunkt des Dienstendes, da ein Dienst 24 Stunden dauert.
S
WE
und E
WE
beschreiben den ersten bzw. letzten Tag eines Wochenendes.
Beispielsweise wähle man den Zeitrahmen, in dem gearbeitet werden kann,
von 7 bis 21 Uhr, d. h. S
A
= 7 und E
A
= 21. Außerhalb dieses Zeitrahmens
kann die Variable x
i
-
i
, ohne einen Einfluss auf die optimale Lösung zu neh-
men, auf Null gesetzt werden. Zusätzlich kann in der Periode von 7 bis 8 Uhr
sinnvollerweise nur x
i
-
i
= 1 sein, falls gearbeitet wird.
41

5 Gemischt ganzzahliges Programm
Zusätzlich sei ein arbeitsfreies Wochenende von Samstag bis Sonntag durch
die Parameter S
WE
= 6 und E
WE
= 7 definiert. Ist das Wochenende arbeitsfrei,
so kann keine Arbeit und Mittagspause erfolgen. Daher können die Variablen
x
i
-
i
, x
i
-
i
, x
ii
+
, q
i
-
i
, q
ii
+
am Wochenende Null gesetzt werden, d. h. es kann nur
pausiert werden.
Um die Mengen der Knoten zu berücksichtigen, bei denen die Variable
{x
i
-
i
, x
i
-
i
, x
ii
+
, q
i
-
i
, q
ii
+
, y
i
-
i
, y
ii
+
} Null gesetzt werden kann, wird die Men-
ge
V
non
eingeführt. Hierbei sei i stets aus den oberen Knoten V und p
i
:=
1
2
(i mod K
d
)
- 1 . Dabei gibt p
i
einen Zeitpunkt zwischen 0 und 23 Uhr an,
welcher durch den Knoten i dargestellt wird.
Beispielsweise handelt es sich bei i = 133 um den oberen Knoten des dritten
Tages von 18 Uhr. Dieser wird durch (133 mod 48
-1 = 18) zu 18 Uhr berech-
net. Zur Erinnerung sei erwähnt, dass der erste obere Knoten im Netzwerk,
welcher 0 Uhr repräsentiert, die Nummer 1 trägt.
Die Mengen der Knoten am Wochenende und die Knoten, zu denen die
Variablen x
i
-
i
, x
i
-
i
, x
ii
+
, q
i
-
i
, q
ii
+
, y
i
-
i
und y
ii
+
den Wert Null annehmen, sind:
V
non
WE
= i | S
WE
- 1 · K
d
i mod K
w
< E
WE
· K
d
: i V
V
non
x
i-i
= i | p
i
S
A
+ 1
p
i
> E
A
: i V
V
non
x
i-i
= i | p
i
S
A
p
i
E
A
- R
A
+ 1 : i V
V
non
x
ii+
= i | p
i
S
A
+ R
A
+ 1
p
i
> E
A
: i V
V
non
q
ii+
= i | p
i
< S
A
+ T
pre
p
i
> E
A
- T
post
: i V
V
non
q
i-i
= i | p
i
S
A
+ T
pre
+ 1
p
i
> E
A
- T
post
+ 1 : i V
V
non
y
ii+
= i | p
i
< S
D
p
i
> S
D
+ 1 : i V
V
non
y
i-i
=
V \ V
D
w
Im Folgenden werden die einzelnen Mengen kurz erläutert. Bei der Interpreta-
tion ist zu beachten, ob i ein Anfangs- oder Endknoten der Kante darstellt.
V
non
WE
Diese Knotenmenge definiert alle Knoten eines Wochenendes. Ist das
Wochenende arbeitsfrei, so können die Variablen x
i
-
i
, x
i
-
i
, x
ii
+
, q
i
-
i
, q
ii
+
auch bei den Knoten dieser Menge Null gesetzt werden.
V
non
x
i-i
Eine fortgesetzte Arbeitsperiode kann nicht früher als eine Periode nach
Arbeitsbeginn S
A
oder später als das Arbeitsende E
A
existieren.
V
non
x
i-i
Eine Arbeit kann nicht vor Arbeitsbeginn S
A
beginnen. Auch ist ein
Beginn nach der Periode, in welcher begonnen werden müsste, um noch
die Mindestarbeitszeit R
A
und eine Mittagspause zu absolvieren, nicht
möglich.
42

5 Gemischt ganzzahliges Programm
V
non
x
ii+
Die erste Pausenperiode nach einer Arbeit kann frühestens nach Ab-
solvierung der Mindestarbeitszeit und einer Mittagspause stattfinden.
Zudem kann sie nicht später als das Arbeitsende E
A
erfolgen.
V
non
q
ii+
Die Mittagspause kann nicht vor Absolvierung von T
pre
Arbeitstunden
nach Arbeitsbeginn S
A
erfolgen. Zudem müssen bis zum Arbeitsende E
A
noch mindestens T
post
Arbeitsperioden vorhanden sein.
V
non
q
i-i
Die erste Arbeitsperiode nach einer Mittagspause kann frühestens nach
dem Arbeitsbeginn und T
pre
Arbeitstunden und einer Mittagspause er-
folgen. Nach dieser ersten Arbeitsperiode müssen bis zum Arbeitsende
E
A
noch mindestens T
post
Arbeitsperioden vorhanden sein.
V
non
y
ii+
Die erste Pausenperiode nach einem Dienst kann nur zur selben Zeit
beginnen, wie auch der Dienst selber, da der Dienst einen ganzen Tag
dauert.
V
non
y
i-i
Ein Dienst kann nur in den spezifizierten Knoten
V
D
w
beginnen.
Die Auswirkung dieser Einschränkung der Variablen auf die Lösungszeit ist
deutlich. Kapitel 7 enthält Zeitanalysen, welche diesen Sachverhalt verdeutli-
chen. Die Beschleunigung der Rechenzeit wird weniger durch die Anzahl an
Knoten in den Mengen
V
non
verursacht. Am Wichtigsten ist, welche Knoten
in diesen Mengen enthalten sind.
Besonders die implizite Festlegung, dass eine Arbeitsschicht nur innerhalb
eines Tages liegen kann, d. h. spätestens bis 24 Uhr beendet sein muss, be-
schleunigt die Lösungsdauer. Das Problem des Festsetzens der optimalen Ar-
beitsschichten wird hierdurch in Tagesprobleme zerlegt, welche durch die Ein-
haltung der Pausen zwischen den Tagen, der maximalen Wochenarbeitszeit
und des Zeitfensters für den Arbeitsbeginn innerhalb einer Woche zusammen-
hängen.
5.4 Komplexität des RCSPs
Bei der vorliegenden Formulierung als MIP entspricht die Anzahl an Nebenbe-
dingungen und Variablen O(|V |). Das MIP wird mit dem Simplex Verfahren
mithilfe eines Branch & Bound (B&B) gelöst. Allgemein gilt, dass Kürzes-
te Wege Probleme mit nicht negativen Kanten in polynomialer Zeit gelöst
werden können. Dies wird u. a. in Ahuja et al. (1993, Kapitel 4) gezeigt.
Fügt man eine Ressourcenbeschränkung
18
hinzu, so ist das RCSP ein NP-
vollständiges Problem. Es wird in Garey und Johnson (1979) als Problem
ND30 mit ,,shortest weight-constrained path" (S. 214) bezeichnet. Es ist eine
18
genauer ein Kantengewicht, wobei ein zulässiger Pfad von Quelle zur Senke nur ein ma-
ximales kumuliertes Gesamtgewicht haben darf
43

5 Gemischt ganzzahliges Programm
Transformation des NP-vollständigen Problems SP12 ,,PARTITION", welches
in pseudo-polynomialer Zeit durch ein dynamisches Programm gelöst werden
kann (S. 223). Somit ist das vorliegende Problem ein schwach NP-vollständiges
Problem. Ein formeller Beweis hierzu kann in Ziegelmann (2001) gefunden wer-
den.
44

6 Dynamisches Programm
6 Dynamisches Programm
Dieses Kapitel behandelt die Lösung des Schichtplanungsproblems als dyna-
misches Programm. Zuerst erfolgt in Kapitel 6.1 eine Einführung in die DP. In
Kapitel 6.2 wird das grundlegende Modell erläutert, wobei die Modellierung des
RCSPs als DP beschrieben und der Lösungsalgorithmus erläutert wird. Darauf
aufbauend werden in Kapitel 6.3 weitere Nebenbedingungen sukzessive in das
Modell eingebaut und die dafür notwendigen Veränderungen des Modells dar-
gelegt. Das vollständige DP befindet sich nochmals in Anhang B. Kapitel 6.4
behandelt eine Möglichkeit, die Lösungsdauer des Algorithmus zu beschleuni-
gen, welche sonst aufgrund der Berücksichtigung des Startzeitfensters deutlich
an Effizienz verliert. Abschließend wird in Kapitel 6.5 darauf eingegangen,
wann die Lösung als DP eine optimale Lösung darstellt. Das Schichtplanungs-
problem wird in Wochenprobleme zerlegt, wobei dies in bestimmten Situatio-
nen zu optimalen Lösungen führt. Die in diesen Kapitel verwendeten Opera-
toren ,,
" und ,," bezeichnen eine Verknüpfung zwischen zwei Argumenten.
Hierbei ist ,,
" die UND-Verknüpfung und ,," die ODER-Verknüpfung.
6.1 Einführung in die dynamische Programmierung
Der Begriff ,,Dynamische Programmierung" wurde erstmals in (Bellman 1952)
eingeführt. Der Hauptverdienst von Bellman war es die verschiedenen Problem-
stellungen aufzuzeigen, für welche die dynamische Programmierung angewandt
werden kann.
Diese ist keine eigenständige Lösungsmethode, sondern ein Optimierungs-
prinzip. Eine kurze Einführung kann in Hans (2001) und Beliën (2006) gefun-
den werden. Auch Bradley et al. (1977) hat ein eigenes Kapitel, in welchem die
Grundlagen ausführlich erklärt und mit Beispielen verdeutlicht werden. Eine
ausführliche Sammlung an verschiedenen Problemstellungen, die illustrieren,
in welchen Fällen die DP angewandt werden kann, sind in Bellman und Dreyfus
(1962), Bellman (1959) und Dreyfus und Law (1977) dargestellt.
Im Folgenden werden die wichtigsten Charakteristika eines Dynamischen
Programms für das in dieser Arbeit behandelte Problem angegeben und erläu-
tert.
Stufen
Gegeben ist ein diskretes System über n+1 Stufen (engl.: stages),
wobei jede Stufe mit einer Ziffer j N
0
=
{0, 1, ..., n} bezeichnet wird. Ist
j R so handelt es sich um ein stetiges System. Dies ist beispielsweise der
Fall, wenn die kontinuierliche Zeit zur Kennzeichnung von Stufen benützt wird.
Bei der dynamischen Programmierung wird ein Problem, welches sich über
mehrere Perioden oder Stufen erstreckt, in Teilprobleme zerlegt, welche einzeln
lösbar sind. Jedes Teilproblem ist vom selben Problemtyp wie das vollständige
45

6 Dynamisches Programm
Problem und wird daher mit derselben Methode gelöst (z.B. Simplexverfah-
ren). Die Lösung des Teilproblems einer Stufe fließt als Information in das
Teilproblem der ,,nächsten" Stufe ein, bis die letzte Stufe erreicht ist.
Induktionsreihenfolge
Zu beachten ist, dass es zwei mögliche Reihenfolgen
gibt, die Teilprobleme zu lösen. Dadurch wird deutlich, dass der Ausdruck
,,nächste Stufe" sich nicht auf einen zeitlichen Ablauf bezieht. Betrachtet man
das Problem ausgehend von der ,,zeitlich" letzten zu treffenden Entscheidung
und löst es rückwärts, so wird dieses Verfahren als backward dynamic pro-
gramming oder auch Dynamische Programmierung mit Rückwärts-Induktion
bezeichnet. Im Falle der Erzeugung des Schichtplans über eine Woche mit ein-
stündigen Perioden würde man beispielsweise Sonntag 24 Uhr als erste Stufe
wählen (j = 168) und die nächste zu lösende Stufe wäre Sonntag 23 Uhr
(j = 167).
Bei der DP mit Vorwärts-Induktion (forward dynamic programming) ist das
erste zu lösende Teilproblem die ,,zeitlich" erste zu treffende Entscheidung und
die Lösung der Teilprobleme erfolgt vorwärts laufend. Beim Schichtplan würde
man beispielsweise bei Montag 0 Uhr
19
beginnen (j = 0) und als nächste zu
lösende Stufe Montag 1 Uhr (j = 1) wählen.
Beide Induktionsverfahren führen, falls sie angewandt werden können, zu
der identischen optimalen Lösung. Die Interpretation der Teillösungen auf den
einzelnen Stufen ist unterschiedlich. Dies wird in Kapitel 6.2.2 am Beispiel der
Schichtplanung erläutert.
Zustand
Auf jeder Stufe j können verschiedene Zustände angenommen wer-
den, welche mit der Zustandsvariablen x
j
X
j
abgebildet werden. X
j
stellt
hierbei die Menge aller Zustände auf der Stufe j dar. Möchte man einen spezifi-
schen Zustand der Stufe j kennzeichnen, so wird im späteren Teil die Notation
x
k
j
mit k K
j
verwendet. Die Menge K
j
beinhaltet hierbei die Indizes aller
Zustände auf der Stufe j.
Je nach Problemstellung ist die Charakterisierung eines Zustands unter-
schiedlich. Ein Zustand wird durch verschiedene Komponenten charakterisiert.
Ein Zustand könnte beispielsweise in einem Kürzeste Wege Problem durch die
bereits zurückgelegte Wegstrecke und dem bisherigen Benzinverbrauch defi-
niert sein.
Entscheidung
Eine mögliche Entscheidung a
j
A(x
j
) wird getroffen, um
vom Zustand x
j
in den Zustand x
j+1
zu gelangen. Die Menge A(x
j
) enthält
demnach alle Entscheidungen, welche in Abhängigkeit des Zustandes x
j
mög-
lich sind.
19
Montag 0 Uhr ist gleich Sonntag 24 Uhr.
46

6 Dynamisches Programm
Ausgehend von einem Zustand können demnach bestimmte Entscheidungen
getroffen werden, wodurch der jetzige Zustand in einen neuen Zustand auf
der nächsten Stufe transformiert wird. Zu beachten ist, dass die Menge der
möglichen Entscheidungen A(x
j
) vom aktuellen Zustand abhängen. Beispiels-
weise könnte die Aktion ,,Fahre weiter" in einem Wegenetz nicht möglich sein,
wenn bereits der ganze Benzinvorrat - welcher den Zustand charakterisiert -
verbraucht worden ist.
Transformationsfunktion
Der Übergang zwischen zwei Zuständen wird über
die Transformationsfunktion t(x
j
, a
j
) abgebildet. Es gilt x
j+1
= t(x
j
, a
j
).
Durch die Transformationsfunktion werden die Komponenten, welche einen
Zustand beschreiben, aktualisiert. Beispielsweise wird durch die Funktion t(x
j
, a
j
)
der neue Zustand x
j+1
dadurch festgelegt, dass die zurückgelegte Wegstrecke
um 10 km steigt und der Benzinverbrauch sich um 3 Liter erhöht. Es könnte
hierbei a
j
=
{Fahre weiter} sein. Durch den aktuellen Zustand x
j
und der
Aktion a
j
wird also vorgegeben, dass im Zustand x
j+1
nun 10 km mehr zu-
rückgelegt und 3 Liter mehr Benzin als im Zustand x
j
verbraucht worden sind.
Ertragsfunktion
Anfallende Kosten bzw. Erträge beim Übergang zwischen
zwei Zuständen werden mit der Ertragsfunktion r(x
j
, a
j
) mit r : X
j
× A
j
R
ermittelt.
Meist ist bei der DP das Ziel, die kumulierten Erträge über alle Stufen zu
optimieren. Ein Beispiel für kumulierte Erträge könnte der summierte Wert
der Gegenstände sein, welche in einem Knapsack-Problem eingeplant werden
können. Hierbei stellt die Einplanung eines Gegenstandes j eine Stufe dar.
20
Optimalitätsprinzip
Nach dem Optimalitätsprinzip setzt sich bei Problemen,
welche mit der dynamischen Programmierung gelöst werden können, jede op-
timale Lösung aus optimalen Teillösungen zusammen.
Richard Bellman (Bellman 1959) drückte dies wie folgt aus. ,,An optimal
policy has the property that whatever the initial state and initial decisions are,
the remaining decisions must constitute an optimal policy with regard to the
state resulting from the first decision." (S. 83)
Das oben genannte Optimalitätsprinzip wurde ursprünglich für ein DP mit
Rückwärts-Induktion formuliert. In Bhavnani und Chen (1966)
21
wird dieses
Prinzip für ein DP mit Vorwärts-Induktion angepasst.
,,An optimal policy has the property that whatever the ensuing state and
decisions are, the preceding decisions must constitute an optimal policy with
regard to the state existing before the last decision."
20
Für eine ausführliche Darstellung zur Modellierung und Lösung von Knapsack Problemen
mit der dynamischen Programmierung siehe Kellerer et al. (2004).
21
zitiert nach Seinfeld und Lapidus (1968, S. 475).
47

6 Dynamisches Programm
Damit das Optimalitätsprinzip angewendet werden kann, müssen beim Pro-
blem, welches mit dynamischer Programmierung gelöst werden soll, zwei Be-
dingungen erfüllt sein. Diese werden u. a. in Cooper und Cooper (1981, Kapi-
tel 3) diskutiert:
1. Trennbarkeit der Zielfunktion
2. Markov-Eigenschaft der Zustände
Die erste Eigenschaft bedeutet, dass der Wert der Zielfunktion in dem Sinne
trennbar ist, dass die Änderung des Zielfunktionswertes auf einer Stufe j nur
von der Entscheidung a
j
und dem Zustand x
j
abhängt.
Die Markov-Eigenschaft bedeutet, dass nach einer Entscheidung a
j
auf der
Stufe j der hieraus resultierende Zustand x
j+1
nur von x
j
und a
j
abhängt.
Die beiden Bedingungen werden in Kapitel 6.2.1 am konkreten Beispiel der
Schichtplanung erläutert.
Um einen Zusammenhang zwischen den einzelnen Stufen herstellen zu kön-
nen, wird eine Rekursionsgleichung verwendet, welche eine Verbindung zwi-
schen den kumulierten Erträgen bis zu einer Stufe mit den Erträgen der nächs-
ten Stufen herstellt.
Rekursionsgleichung
Mathematisch ausgedrückt ergibt das Optimalitätsprin-
zip eine Rekursionsgleichung. Diese gibt im Fall der Vorwärts-Induktion für ein
Minimierungsproblem die rekursive Folge von Wertfunktionen V (x
j
) an. Hier-
bei wird die Wertfunktion V (x
j
) für die Vorwärts-Induktion in Worten wie
folgt definiert:
V (x
j
) := Optimaler Wert von allen bisherig getroffenen Entscheidungen
unter der Voraussetzung, dass man sich im Zustand x
j
befindet und
bereits j Stufen absolviert hat.
Die Wertfunktion ist somit durch
V (x
j+1
) = min
a
j
A(x
j
)
{r(x
j
, a
j
) + V (x
j
)
}
(45)
unter den Nebenbedingungen
V (x
0
) = r
init
a
j
A(x
j
)
x
j+1
= t(a
j
, x
j
)
gegeben. Wenn deutlicher ausgedrückt werden soll, dass die Wertfunktion -
wie im Bellmanschen Optimalitätsprinzip postuliert - nur von den Zuständen
x
j
und Entscheidungen a
j
abhängt, lässt sich die Gleichung zu
V (t(a
j
, x
j
)) = min
a
j
A(x
j
)
{r(x
j
, a
j
) + V (x
j
)
}
(46)
48

6 Dynamisches Programm
unter den Nebenbedingungen
V (x
0
) = r
init
a
j
A(x
j
)
x
j+1
= t(a
j
, x
j
)
umformen. Der Parameter r
init
gibt den Wert der Zielfunktion auf der Stufe
j = 0 an und ist in den meisten Fällen Null.
Die Gleichung für V (x
j
) stellt eine Funktionalgleichung
22
dar und ist daher
auch unter diesem Namen bekannt.
Politik
Eine Politik stellt eine Folge a = (a
0
, ..., a
n-1
) von Entscheidungsva-
riablen dar. Die dazugehörige Zustandsfolge mit x
0
= x
init
, x
j+1
= t
j
(x
j
, a
j
)
mit j = 0, ..., n - 1 wird durch x = (x
0
, ..., x
n
) dargestellt. Hierbei gibt x
init
den Ausgangszustand an, mit welchem das DP begonnen wird.
Optimale Politik
Sei n die letzte Stufe eines Optimierungsproblems und sei
j
n. Sei weiterhin bei der Vorwärts-Induktion DP (x
j
) als das dynamische
Optimierungsproblem definiert, welches mit x
j
in der Stufe j endet. Sei zu-
sätzlich a
eine optimale Politik für DP (x
n
) und x
die dazugehörige optimale
Folge von Entscheidungen, d. h. a
und x
geben die optimale Politik und die
optimale Folge von Entscheidungen für das gesamte Optimierungsproblem von
Stufe 0 bis n an.
Nach dem Optimalitätsprinzip ist somit eine Teilfolge a
0
, ..., a
j-1
eine opti-
male Politik für DP (x
j
) und x
0
, ..., x
j
ist deren Folge von Zuständen.
23
Eine
optimale Politik ist die Folge von Entscheidungen, welche die Wertfunktion
optimiert.
Einteilung von Modellen der dynamischen Programmierung
Folgende Un-
terscheidungen können im Allgemeinen bei Modellen der dynamischen Pro-
grammierung getroffen werden:
· Je nach Modellierung der Stufen (stetig oder diskret) werden die Modelle
in kontinuierliche bzw. diskrete dynamische Programmierung unterteilt.
22
Eine Funktionalgleichung ist eine Gleichung, in welcher eine Funktion als implizite Funk-
tion ausgedrückt wird. Dies bedeutet, dass die abhängige Variablen (hier:
V (x
j
)) nicht
explizit durch die unabhängige Variable
x
j
ausgedrückt wird. Wie auch hier der Fall,
wird der Wert einer Funktionalgleichung an einer bestimmten Stelle oftmals in Abhän-
gigkeit ihres Wertes an einer anderen Stelle beschrieben, z.B.
V (x
j
) =
c + V (x
j-1
) mit
c R. Rekursionsgleichungen sind hierbei eine Klasse der Funktionalgleichungen.
23
Das Optimalitätsprinzip für Rückwärts-Induktion wäre unter der Definition, dass ein dy-
namisches Optimierungsproblem, welches mit
x
j
in der Stufe
j gestartet wird, als DP (x
j
)
bezeichnet. Für eine optimale Lösung gibt es nach dem Bellmanschen Optimalitätsprinzip
eine Politik
a
, welche für das
DP (x
0
) eine optimale Folge von Entscheidungen darstellt.
Die dazugehörige Folge von Zuständen wird durch
x
ausgedrückt. Somit ist a
k
, ..., a
n-1
eine optimale Politik für
DP (x
k
) und
x
k
, ..., x
n
deren Folge von Zuständen.
49

6 Dynamisches Programm
· Ist das Resultat der Entscheidungen r
j
(x
j
, a
j
) mit Unsicherheit verbun-
den, so spricht man von stochastischer DP und es werden die erwarteten
statt der sicher eintretenden Erträge optimiert. Im vorliegenden Fall wird
durch eine Entscheidung die Zielfunktion um einen festen vorher bekann-
ten Wert verändert und man spricht von deterministischer DP.
Diese Arbeit behandelt den Fall eines diskreten deterministischen DPs. Für
eine Behandlung von stetigen DPs sei auf Bertsekas (2005) verwiesen. Stochas-
tische DPs werden von Sennott (1999) dargestellt.
6.2 Beschreibung des grundlegenden DPs
Im vorliegenden Fall der Erzeugung eines Schichtplans wird eine Vorwärts-
Induktion gewählt. Unabhängig von der Induktionsart erhält man als Ergebnis
den optimalen Schichtplan. Es sei daran erinnert, dass ein optimaler Schicht-
plan hierbei derjenige ist, durch dessen Anwendung die kleinsten reduzierten
Kosten entstehen.
Das allgemeine dynamische Programm sieht bei Minimierung der reduzierten
Kosten C wie folgt aus.
Minimiere C =
n-1
j=0
r(x
j
, a
j
)
unter den Nebenbedingungen
x
j+1
= t
j
(x
j
, a
j
)
x
0
= x
init
x
j
X
j
a
j
A(x
j
)
Zuerst wird in Kapitel 6.2.1 die dynamische Programmierung auf das ver-
einfachte Modell angewandt. Das vereinfachte Modell des dynamischen Pro-
gramms beschränkt sich auf dieselben Nebenbedingungen wie das grundle-
gende MIP in Kapitel 5.1. Es berücksichtigt die Mindest- und Höchstdauern
der Arbeit pro Tag, die Mindestpausendauer zwischen zwei Schichten und die
Höchstarbeitsdauer pro Woche.
Danach wird in Kapitel 6.2.2 auf die Induktionsreihenfolge eingegangen und
erklärt, welche kurzfristigen Modifikationen am Schichtplan mit welcher In-
duktionsreihenfolge möglich sind. Anschließend wird in Kapitel 6.2.3 der Al-
gorithmus für das vereinfachte Modell eingeführt und es wird erläutert, welche
Schritte zur Bestimmung eines optimalen Schichtplans notwendig sind.
In Kapitel 6.3 wird der Algorithmus um den Dienst, die Überstunden und
Fehlstunden, die Mittagspause und das Startzeitfenster ergänzt. Darauf wird in
Kapitel 6.4 eine weitere Modifikation des Algorithmus erläutert. Hierbei wird
50

6 Dynamisches Programm
das Startzeitfenster anders modelliert und die Zeit, in welcher keine Nachfrage
nach Ärzten besteht, wird im Algorithmus berücksichtigt, was beides zu einer
Beschleunigung der Lösungsdauer führt. Das vollständige Modell des DPs,
welches alle Nebenbedingungen berücksichtigt, ist im Anhang B enthalten.
6.2.1 Modellierung des RCSPs als DP
In diesem Kapitel wird erläutert, wie ein dynamisches Programm als Lösungs-
methode für das in Kapitel 4 formulierte RCSP modelliert werden kann. Hier-
bei wird darauf eingegangen, wie eine Stufe, ein Zustand, eine Entscheidung
bzw. eine Politik dargestellt wird und warum das Optimalitätsprinzip für das
beschriebene Problem gilt. Für die allgemeine Modellierung eines dynamischen
Programms für ein RCSP sei sowohl auf Hartel und Glaser (1996) als auch auf
Righini und Salani (2008) verwiesen.
Eine Stufe j entspricht einem Knotenpaar des RCSPs, also einem Zeitpunkt.
Im Folgenden wird um die Notation einfach zu halten, davon ausgegangen, dass
die Schichtplanung stundenweise durchgeführt wird. Für einen Planungshori-
zont über eine Woche und stündlicher Unterteilung gibt es demnach 7
· 24 +
1 = 169 Stufen von 0,..., 168. Hierbei ist die Anzahl ungerade, da man noch
eine letzte Stufe benötigt, um das Ende der letzten Periode n = 168 zu kenn-
zeichnen. Die Nummer j einer Stufe gibt die j-te Stunde seit Wochenbeginn
an.
Abbildung 8 zeigt die Zusammenfassung eines Knotenpaares [a,a+1] bzw.
[a+2,a+3] zu der Stufe j bzw. j + 1, wobei a und a + 2 aus den oberen Knoten
sind.
Die Notation der Kantengewichte
j
zwischen den Stufen j und j + 1 weicht
von der bisherigen Notation ab. Bisher galt für die Kantengewichte einer Pause,
dass
a,a+3
=
a+1,a+3
= 0 ist. Für die Gewichte einer Arbeitsperiode galt
a,a+2
=
a+1,a+2
. Es gilt nun, dass
j
=
a,a+2
=
a+1,a+2
. Überdies werden
a,a+3
bzw.
a+1,a+3
, da diese stets Null sind, nicht mehr berücksichtigt.
a
a + 2
a + 1
a + 3
...
...
...
...
j
j
j+1
Abb. 8: Stufen im dynamischen Programm.
Jeder Stufe werden Zustände zugewiesen. Jeder Zustand x
j
auf der Stu-
fe j ergibt sich aus einem Pfad vom Quellknotenpaar zum Knotenpaar j. Die
51

6 Dynamisches Programm
Zustände sind im Grundmodell durch den Ressourcenverbrauch an Wochen-
arbeit, Arbeit und Pause und durch den Zielfunktionswert beschrieben. Der
Zielfunktionswert ist die negative Summe der Kantengewichte der Kanten, auf
denen im Pfad bis zur Stufe j gearbeitet wurde.
Die möglichen Entscheidungen a
j
A
j
(x
j
) =
P{l, p}
24
sind im Grund-
modell durch Arbeit l (engl. labour
25
) und Pause p gegeben.
Die Politik ist ein erzeugter Schichtplan. In Abbildung 1 auf Seite 3 wird
beispielsweise die Entscheidung a
j
= l durch die Zahl Eins und die Entschei-
dung a
j
= p durch die Zahl Null repräsentiert.
Das Optimalitätsprinzip kann angewandt werden, da die Trennbarkeit
der Zielfunktion (Voraussetzung 1) und die Markov-Eigenschaft der Zustände
(Voraussetzung 2) vorliegen. Dies kann aus folgenden Gründen angenommen
werden.
Die Trennbarkeit der Zielfunktion (1) bedeutet, dass der Effekt auf die Ziel-
funktion auf einer Stufe j nur vom Zustand x
j
und von der Entscheidung a
j
abhängt. Die Zielfunktion (Bedingung 1, Kapitel 5.1.1) wird in der DP als
j{0,...n-1}
(
-
dem
j
· I
{l}
(a
j
)) geschrieben.
26
Ob in der Zielfunktion ein weite-
res
-
dem
j
addiert wird, hängt nur von der Entscheidung a
j
ab. Diese hängt
wiederum lediglich von x
j
ab, da a
j
A
j
(x
j
) ist.
Voraussetzung (2) besagt, dass ein Zustand x
j
nur von dem vorherigen Zu-
stand x
j-1
und der Entscheidung a
j-1
, welche zu diesem Zustand geführt hat,
abhängt. Diese Bedingung ist erfüllt, da x
j
= t(x
j-1
, a
j-1
) und die Transfor-
mationsfunktion t von keinen weiteren Variablen abhängt.
Die Transformationsfunktion und die Rekursionsgleichung für die Schicht-
planung werden in Kapitel 6.2.3 definiert.
6.2.2 Induktionsreihenfolge des DPs
Die Schichtplanung wird mit Vorwärts-Induktion gelöst. Eine Betrachtung mit
Rückwärts-Induktion wäre auch möglich. Beide Verfahren führen auf den opti-
malen Schichtplan, unterscheiden sich jedoch in den Ergebnissen, welche man
auf den einzelnen Stufen erhält. Dies und die Verwendbarkeit der einzelnen
Informationen in der Praxis in Abhängigkeit der Induktionsreihenfolge werden
im Folgenden verdeutlicht.
Rückwärts-Induktion
Ausgehend von einem beliebigen Zustand x
j
lässt sich
der Schichtplan erstellen, welcher zum Ende der Woche den Zielfunktionswert
optimiert, unter der Voraussetzung, dass dieser Teilschichtplan beim Zustand
24
P stellt das Zeichen für die Potenzmenge dar. Abweichend von der gebräuchlichen Defi-
nition, ist in dieser Arbeit die leere Menge nicht Bestandteil der Potenzmenge.
25
Aufgrund der bereits assoziierten Indizes
w für die Woche und a für die Entscheidung a
j
wurde der Index
l für die Arbeit gewählt.
26
I
{l}
(
a
j
) ist das Symbol der Indikatorfunktion, welche im Symbolverzeichnis definiert wird.
52

6 Dynamisches Programm
x
j
startet (x
j
- x
(j)
n
). Hierbei ist x
(j)
n
der beste Endzustand, welcher vom
Zustand x
j
aus zu erreichen ist.
Vorwärts-Induktion
Das dynamische Programm enthält auf jeder Stufe Tei-
linformationen. Bei der Vorwärts-Induktion kann man anhand dieser rekon-
struieren, wie der beste Schichtplan von Wochenbeginn zu einem bestimmten
gewählten Zustand einer konkreten Stufe j ist. Beispielsweise sei der gewünsch-
te Zustand x
j
dadurch gekennzeichnet, dass der Arzt 16 Stunden gearbeitet
hat
R
A
j
= 16 , bereits die Mindestpausenlänge nach seiner letzten Schicht
absolviert hat
R
P
j
R
P
und einen Zielfunktionswert von höchstens -1250
(obj)
j
-1250 haben soll. Aus der Lösung des DPs lassen sich anhand der
gespeicherten Informationen diejenigen Schichtpläne erstellen, bei welchen es
möglich ist in Stufe j einen solchen Zustand x
j
zu erreichen. Es lassen sich
demnach alle Schichtpläne vom Anfangszustand x
init
bis zum vorgegebenen
Zustand x
j
rekonstruieren (x
init
- x
j
).
Bedeutung in der Praxis
Die Anwendung der Rückwärts- bzw. Vorwärts-
Induktion könnte in der Praxis folgendermaßen genützt werden. Man kann
beispielsweise daran interessiert sein, wie ein Schichtplan innerhalb der laufen-
den Woche modifiziert werden sollte, falls es notwendig wird, dass der Arzt von
dem optimalen Schichtplan a
abweicht, also einen Zustand x
j
annimmt, wel-
cher nicht in x
enthalten ist. Dies kann anhand der Informationen aus dem DP
mit Rückwärts-Induktion berechnet werden. Man betrachtet hierzu die Stufe j
und wählt ausgehend vom Zustand x
j
die weiteren Zustände x
j+1
, ..., x
n
bis
zur letzten Stufe n der Woche.
Können Ärzte bei der Planung ihrer Schichtpläne Wünsche äußern, so eignet
sich die Vorwärts-Induktion. Angenommen, ein Arzt möchte ab Freitag Urlaub
nehmen und bis dahin seine vertragliche Wochenarbeitszeit von 42 Stunden ab-
solviert haben. Anhand dieses Zielzustandes
R
A
j
= 42 kann mit den In-
formationen aus dem DP mit Vorwärts-Induktion derjenige Schichtplan erstellt
werden, welcher unter Berücksichtigung der Präferenzen des Arztes optimal ist.
In der vorliegenden Arbeit ist ein dynamisches Programm mit Vorwärts-
Induktion gewählt worden, um Präferenzen von Ärzten berücksichtigen zu
können. Mit der Methode der Vorwärts-Induktion kann auch der optimale
Restschichtplan einer Woche nach Modifikation des geplanten Schichtplans er-
zeugt werden. Hierzu setzt man als Anfangszustand x
0
= x
j
und löst das DP
über die restlichen Tage erneut. Die Berücksichtigung von Präferenzen ist über
die Rückwärts-Induktion jedoch nicht immer möglich. Es ist denkbar, dass der
gewählte Präferenzzustand im Laufe des DPs mit Rückwärts-Induktion nicht
erstellt wird, da dieser Zustand nicht zur Konstruktion des optimalen Schicht-
plans notwendig ist.
53

6 Dynamisches Programm
6.2.3 Darstellung des Algorithmus
Der gewählte Algorithmus, um das dynamische Programm zu lösen, ist ein
Label Setting Algorithmus. Er beruht auf den Ausführungen von Righini und
Salani (2008), Desrochers und Soumis (1988) und Desrosiers et al. (1995). Um
einen Zusammenhang von Label Setting Algorithmus, Dijkstra Algorithmus
und der dynamischen Programmierung zu erhalten, sei auf Sniedovich (2006)
verwiesen.
Jeder Zustand auf einer Stufe wird durch ein Label repräsentiert. Dieses
beinhaltet den Ressourcenverbrauch der verschiedenen Ressourcen
27
, den Ziel-
funktionswert und weitere Komponenten, welche notwendig sind, um die ent-
sprechenden Nebenbedingungen abzubilden. Diese Komponenten werden in
den folgenden Kapiteln eingeführt. Die optimale Lösung wird durch das Label
mit dem geringsten Zielfunktionswert auf der letzten Stufe dargestellt. Aus-
gehend von diesem Label lassen sich alle optimalen Vorgängerzustände und
Vorgängerentscheidungen rekursiv berechnen.
Der Algorithmus erweitert alle Zustände und geht dabei in aufsteigender
Reihenfolge von der ersten bis zur letzten Stufe. Dies wird solange fortgesetzt,
bis durch die Transformationsfunktion von allen Zuständen mit allen dort mög-
lichen Entscheidungen die Folgezustände gebildet wurden.
Die Effektivität des Algorithmus beruht auf der Anzahl an erzeugten Zu-
ständen. Von jedem Zustand entspricht die maximal mögliche Anzahl an neu-
en Zuständen der Anzahl an möglichen Entscheidungen, d. h. die Anzahl an
Zuständen nimmt exponential zu. Um die Anzahl möglichst gering zu halten,
werden nur effiziente Zustände fortgesetzt.
Ein Zustand ist effizient, falls dieser von keinem anderen dominiert wird.
Wird ein Zustand dominiert, so bezeichnet dies, dass ein Zustand im Ver-
gleich zu einem anderen Zustand anhand gewisser Kriterien ,,schlechter" ist.
28
Regeln bzw. die Kriterien für die Dominanz zwischen zwei Zuständen werden
in diesem Kapitel eingeführt und in den folgenden Kapiteln an die Erweiterun-
gen angepasst. Ein nicht-effizienter bzw. dominierter Zustand kann nicht mehr
das Optimum auf der letzten Stufe erreichen und kann somit gelöscht werden.
Nachdem durch die Transformationsfunktion ein neuer Zustand auf der Stufe j
erzeugt wurde, werden alle Zustände x
j
X
j
anhand von Dominanzregeln auf
ihre Effizienz überprüft. Dieser Vorgang wird als EF F (X
j
) abgekürzt. Wird
ein Zustand durch die Transformationsfunktion benutzt, um einen neuen Zu-
stand zu erzeugen, so wird das Label des ,,alten" Zustands dauerhaft, d. h.,
27
Die Ressourcen sind ,,zurücksetzbare" Ressourcen, welche durch
t(x
j
, a
j
) in Abhängigkeit
von
x
j
und
a
j
auf einen Wert Null bzw. Eins zurückgesetzt werden können. Es sei hierzu
auf die Ausführungen in Kapitel 4.2 verwiesen.
28
Beispielsweise ist ein Zustand ,,schlechter", wenn er im Vergleich zu einem anderen Zustand
auf derselben Stufe einen höheren Zielfunktionswert und einen höheren Verbrauch an der
Ressource ,,Wochenarbeit" besitzt.
54

6 Dynamisches Programm
es kann nicht mehr dominiert werden. Im Folgenden wird auch der Begriff
,,Effizienzprüfung" für die Anwendung von EF F (X
j
) verwendet.
Die Reihenfolge der Bearbeitung der Stufen und die Reihenfolge der Bear-
beitung der Labels einer Stufe kann variiert werden. Stufen werden in dieser
Arbeit in aufsteigender Reihenfolge bearbeitet. Sind alle Zustände einer Stu-
fe durch die Transformationsfunktion behandelt worden, so wird die nächste
Stufe betrachtet. Die Abarbeitung der einzelnen Labels innerhalb einer Stufe
kann verschiedene Reihenfolgen haben, je nach Sortierung der Menge X
j
. Die
Sortierung wird durch ORDER(X
j
) dargestellt. Die zeitliche Effizienz ver-
schiedener Sortierungen wird in Kapitel 7.2.2 diskutiert. Mögliche Reihenfol-
gen sind aufsteigende oder absteigende Labelnummern,
29
die Sortierung nach
Zielfunktionswert oder die Sortierung nach Wochenarbeitszeit.
Im Algorithmus wird die Erstellung eines Schichtplans in Wochenprobleme
zerlegt, indem Schichtpläne für einzelne Wochen w W gebildet und die-
se dann kombiniert werden. Dieses Vorgehen ist notwendig aufgrund der Be-
rücksichtigung des maximalen Startzeitfensters T
win
innerhalb einer Woche.
Dieses kann für jede Woche unterschiedlich sein. Hierdurch können weniger
Labels aufgrund von Dominanzen gelöscht werden, wodurch eine große Anzahl
an Labels generiert werden müsste. Hierdurch verliert der Algorithmus seine
Effizienz. Eine ausführliche Erklärung wird in Kapitel 6.3.4 gegeben. In Kapi-
tel 6.5 wird erläutert unter welchen Bedingungen dieses Vorgehen dennoch zur
optimalen Lösung führt.
Das Vorgehen zur Erzeugung des optimalen Schichtplans ist zweigeteilt. Zu-
erst werden alle Labels von der ersten bis zur letzten Stufe über alle Wochen
erzeugt. Danach wird vom letzten Label ausgehend rekursiv die optimale Folge
von Zuständen und die optimale Politik bestimmt.
Der Ablauf des Algorithmus der ersten Stufe wird im Folgenden in Algorith-
mus 1 dargestellt.
Es werden die Wochen des Schichtplans in aufsteigender Reihenfolge durch-
laufen (1) und am Anfang für die Stufe Null der Zustand x
0
initialisiert (2)
und der Menge der Zustände X
0
zugewiesen (3). Um die Notation zu verein-
fachen, wurde bei den Zuständen bzw. Entscheidungen und deren Mengen auf
den Index der Woche verzichtet.
30
Für alle restlichen Stufen j = 1, ...n (4)
wird zuerst die Menge der Zustände (Labels) nach der gewünschten Reihen-
folge sortiert (5), bevor alle Zustände daraus nach der sortierten Reihenfolge
abgearbeitet werden (6). Zu jedem Zustand werden zudem die entsprechenden
möglichen Entscheidungen bestimmt (6) und der neue Zustand x
j
der nächsten
29
Aufsteigende Labelnummern, d. h., das erste entnommene Label hat den kleinsten Index,
entspricht dem First In First Out (FIFO) Verfahren. Das Label, welches zuerst für die
Stufe
j erzeugt wurde, wird wieder als erstes verwendet um in die Transformationsfunk-
tion
t(x
j
, a
j
) =
x
j+1
einzufließen. Analog entspricht die Entnahme nach absteigender
Labelnummer dem Last In First Out (LIFO) Verfahren.
30
Sonst müsste es beispielsweise
x
w,j-1
bzw.
a
w,j-1
lauten.
55

6 Dynamisches Programm
Algorithmus 1 Erzeugung aller nicht-dominierten Labels
1:
for w = 1 to |W| do
2:
x
0
x
init
3:
X
0
=
{x
0
}
4:
for j = 1 to n do
5:
ORDER(X
j-1
)
6:
for all x
j-1
X
j-1
, a
j-1
A
j-1
(x
j-1
) do
7:
x
j
t (x
j-1
, a
j-1
)
(I,II,III,IV)
8:
X
j
= X
j
{x
j
}
9:
EFF(X
j
)
(V)
10:
end for
11:
end for
12:
end for
Stufe wird mit der Transformationsfunktion berechnet (7). Dieser wird darauf
zu der Menge der Zustände X
j
hinzugefügt (8). In der Menge X
j
werden nun
alle Zustände auf ihre Effizienz hin überprüft (9), d. h. dominierte Zustände
werden gelöscht. Die Schritte (5) bis (9) werden bis Erreichen der vorletzten
Stufe n-1 wiederholt, aus welcher sich die Zustände der letzten Stufe ergeben.
Die römischen Ziffern beschreiben die einzelnen Bestandteile, welche für die
Realisation des Algorithmus notwendig sind. Um den Übergang von einem zum
nächsten Zustand mithilfe der Transformationsfunktion zu beschreiben (Zei-
le 7), ist es notwendig, die Ertragsfunktion (I) und den Aufbau eines Labels (II)
zu kennen. Die Ertragsfunktion beschreibt die Aktualisierung der Zielfunktion
von einem zum nächsten Zustand. Des Weiteren müssen sowohl die mögli-
chen Entscheidungen a
j-1
A
j-1
(x
j-1
) beschrieben werden (III) als auch die
Transformationsfunktion (IV) an sich. Diese beschreibt, wie die Komponenten
eines Labels geändert werden, um das Label auf der nächsten Stufe zu bil-
den. Als letztes wird die Effizienz der Labels (V) anhand von Dominanzregeln
bestimmt.
Der Ablauf des Algorithmus 2 zur Bestimmung der optimalen Zustandsfolge
und der optimalen Politik ist Folgender.
Algorithmus 2 Bestimmung der optimalen Politik
1:
x
w
1
, ..., x
w
|W|
arg min
k
i
K
i
iW
|W|
i
(obj)
k
i
w
i
s. t. NB
(A)
2:
for i = |W| to 1 do
3:
x
n
x
w
i
4:
for j = 1 to n do
5:
x
n-j
, a
n-j
x
n-j
, a
n-j
|
V (x
n-j+1
)
=
{r(x
n-j
, a
n-j
) + V (x
n-j
)
} x
n-j
X
n-j
, a
n-j
A
n-j
(B)
6:
end for
7:
end for
Zuerst werden die Zustände der letzten Stufe x
w
i
aller Wochen i W be-
stimmt, welche in Kombination die Zielfunktion minimieren (1). Hierbei bildet
56

6 Dynamisches Programm
x
w
1
, ..., x
w
|W|
ein Tupel dieser Zustände. Für jede Woche i gibt es also genau
einen optimalen Zustand x
w
i
. Um herauszufinden, welche Labelnummer k
i
die-
ser Zustand trägt, muss die Summe aus den Zielfunktionswerten (obj)
k
i
w
i
für alle
verschiedenen Kombinationen von k
i
K
i
und i W gebildet werden. Das
Tupel k
1
, ..., k
|W|
, welches die Summe der einzelnen Zielfunktionswerte (obj)
k
i
w
i
minimiert, beschreibt die Labelnummern. Es müssen hierbei Nebenbedingun-
gen bei der Kombination der einzelnen Endzustände berücksichtigt werden.
Dieser Schritt des Algorithmus wird als Teil A bezeichnet und die Nebenbe-
dingungen werden in den späteren Kapiteln erklärt.
Als nächster Schritt wird für jede Woche (2) der beste Endzustand als x
n
bezeichnet (3). Ausgehend von diesem optimalen Zustand wird mithilfe der
Rekursionsgleichung der vorhergehende optimale Zustand x
n-j
und die opti-
male Entscheidung a
n-j
in (5) ermittelt. Dies wird durch die for-Schleife in (4)
solange fortgesetzt, bis a
0
und x
0
ermittelt wurden. Dieser Schritt des Algo-
rithmus wird im Folgenden als Teil B bezeichnet.
Um die beiden Algorithmen implementieren zu können, werden in den nächs-
ten Kapiteln die Details der Implementierung erläutert. Die Beschreibung der
einzelnen Punkte ist hierbei folgendermaßen aufgebaut.
I. Bildung der Ertragsfunktion
II. Definition des Labels, welches einem Zustand zugeordnet wird
III. Mögliche Entscheidungen a
j
in Abhängigkeit des Zustands x
j
IV. Beschreibung der Transformationsfunktion t (x
j
, a
j
)
V. Dominanzregeln, um Zustände, die nicht zum Optimum führen können,
zu löschen
VI. Bestimmung der optimalen Politik aus den berechneten Labels unter Be-
rücksichtigung der Zerlegung in Wochenproblemen (Teil A und B)
Ertragsfunktion
Die Ertragsfunktion hängt in der konkreten Problemstel-
lung nur von a
j
ab, welches aber wieder von x
j
abhängig ist, da a
j
A
j
(x
j
)
ist. Falls in der Periode (j, j + 1) gearbeitet wird, gibt die Ertragsfunktion das
negativ genommene
dem
j
zurück.
r(x
j
, a
j
) =
-
dem
j
· I
{l}
(a
j
) =
-
dem
j
, für a
j
= l
0
, für a
j
= l
(47)
57

6 Dynamisches Programm
Label
Jedem Zustand auf der Stufe j wird ein Label L
k
j
zugeordnet mit k
K
j
. Somit ist das Label L
k
j
das k-te Label auf der Stufe j. Im Grundmodell
wird ein Zustand durch die bis zur Stufe j verbrauchten Ressourcen an Wo-
chenarbeitszeit R
WA
, Arbeit R
A
und Pause R
P
sowie dem Zielfunktionswert
obj beschrieben. Zudem wird die Komponente s
mo
benötigt. Diese gibt an,
um wie viel Uhr die erste Schicht in der Woche begonnen wurde. Die Einfüh-
rung ist aufgrund der Zerlegung des Planungshorizonts in einwöchige Probleme
notwendig.
Ein Label besitzt daher die Form (R
W A
, R
A
, R
P
, obj, s
mo
)
k
j
. Um einzelne
Komponenten des Labels L
k
j
zu benennen, wird die Notation (R
A
)
k
j
verwen-
det, um beispielsweise den aktuellen Ressourcenverbrauch an Arbeit des k-ten
Zustands auf der Stufe j zu beschreiben.
Der Initialisierungszustand x
init
, welcher durch das Label L
1
0
ausgedrückt
wird, ist L
1
0
= (0, 0, R
P
, 0)
1
0
.
Im Folgenden wird L
k
j
auch im Sinne des Zustandes x
k
j
verwendet, welcher
durch dieses Label ausgedrückt wird.
Entscheidungen
Ausgehend von einem x
j
wird überprüft, welche Entschei-
dungen a
j
zulässig sind, d. h. es wird die Menge A
j
(x
j
) bestimmt, welche alle
möglichen Entscheidungen ausgehend vom Zustand x
j
X
j
enthält. Hierbei
ist eine mögliche Entscheidung a
j
in Abhängigkeit des Zustands x
j
·
a
j
= l für alle j mit x
j
X
j
, wenn
R
WA
j
< R
WA
- max 0; R
A
- R
A
j
(48.1)
R
A
j
< R
A
(48.2)
R
P
j
R
P
(48.3)
gilt, d. h., der Arbeitszustand x
j
ist folgendermaßen charakterisiert: Von x
j
aus kann die Mindestarbeitsdauer ohne Überschreitung von R
WA
beendet wer-
den (48.1), die Höchstarbeitsdauer wurde noch nicht erreicht (48.2) und die
Mindestpausendauer wurde absolviert (48.3).
Eine weitere Entscheidung a
j
ist
·
a
j
= p für alle j mit x
j
X
j
, wenn
R
WA
j
= R
WA
R
A
j
= R
A
(49.1)
R
A
j
R
A
(49.2)
R
P
j
< R
P
(49.3)
R
P
j
R
P
R
A
j
= 0
(49.4)
58

6 Dynamisches Programm
gilt, d. h. im Pausenzustand x
j
gilt eine der folgenden Bedingungen: Die ma-
ximale Wochenarbeitszeit bzw. Höchstarbeitsdauer wurde erreicht (49.1), die
Mindestarbeitsdauer am Tag wurde erreicht (49.2), die Mindestpausendauer
wurde noch nicht erreicht (49.3) oder die Mindestpausendauer wurde erreicht
und es wurde noch nicht begonnen zu arbeiten (49.4).
Aus obigen Beschreibungen wird deutlich, dass von bestimmten Zuständen
aus auch beide Aktionen
{Arbeit, P ause} durchgeführt werden können. Dies
trifft zu für alle x
j
X
j
: R
WA
j
< R
WA
R
A
j
R
A
R
P
j
R
P
.
Transformationsfunktion
Durch die Transformationsfunktion t(x
j
, a
j
) wird
ein neuer Zustand x
j+1
erzeugt, welcher durch das Label L
j+1
ausgedrückt
wird. Bei der Beschreibung der Transformationsfunktion wird, um die Notation
einfach zu halten, ein Label nur durch seine Stufe beschrieben und nicht durch
die Nummerierung k des Labels.
Die Transformationsfunktion t(x
j
, a
j
) hängt von der Entscheidung a
j
ab. Es
wird daher zur Darstellung t(x
j
, a
j
) nach der Entscheidung aufgeteilt. Hierbei
gibt t
l
(x
j
, l) die Transformationsfunktion für eine Arbeit a
j
= l und t
p
(x
j
, p)
die Transformationsfunktion für eine Pause a
j
= p an. Je nach Entscheidung
a
j
werden andere Komponenten eines Zustandes aktualisiert.
Das neue Label L
j+1
wird gebildet, indem das Vorgängerlabel L
j
dupliziert
wird. Dies wird im Folgenden als L
j+1
L
j
dargestellt. Danach werden ent-
sprechende Komponenten bei L
j+1
aktualisiert. Im Folgenden werden nur die
Komponenten beschrieben, welche sich von L
j
auf L
j+1
ändern. Es gilt:
t
l
x
j
, l :
R
WA
j+1
= R
WA
j
+ 1
R
A
j+1
= R
A
j
+ 1
(obj)
j+1
= (obj)
j
-
dem
j
(s
mo
)
j
= 0
(s
mo
)
j+1
= j
(50.1)
(50.2)
(50.3)
(50.4)
t
p
x
j
, p :
R
A
j+1
= 0
R
P
j+1
= min
R
P
j
· I
{p}
(a
j-1
) + 1; R
P
(51.1)
(51.2)
Anschaulich wird durch die Entscheidung für Arbeit zwischen der Stufe j und
j + 1 der Ressourcenverbrauch von Wochenarbeitszeit R
WA
(50.1) und Ar-
beitszeit R
A
(50.2) um Eins erhöht und der Zielfunktionswert (50.3) um
dem
j
erniedrigt. Der Wert von R
P
bleibt gleich und wird deswegen in keiner Glei-
chung explizit erwähnt. Wurde bisher der erste Schichtstart in der Woche noch
nicht festgelegt, so wird dieser auf j gesetzt (50.4). Der Pfeil drückt hierbei
eine Kausalität aus. Falls die Bedingung auf der linken Seite zutrifft, so folgt
die rechte Seite. Trifft die Bedingung nicht zu, so verändert sich nichts an der
Komponente (s
mo
) und es gilt (s
mo
)
j
= (s
mo
)
j+1
.
59

6 Dynamisches Programm
Bei einer Pause bleibt der Wert der Komponenten R
WA
, obj und s
mo
gleich.
Falls durch a
j
die erste Pausenperiode gegeben ist, also in Periode j - 1 kei-
ne Pause gehalten wurde, wird
R
P
j
durch die Indikatorfunktion
31
zuerst
auf Null gesetzt, bevor es um Eins erhöht wird (51.2). Ist es nicht die erste
Pausenperiode, so wird der Ressourcenverbrauch von R
P
um Eins bis zum ma-
ximalen Wert von R
P
erhöht. Die Beschränkung auf R
P
wurde gewählt, um
im späteren Abschnitt bei den Dominanzregeln möglichst wenig Unterschei-
dungen treffen zu müssen. Ein Zustand, welcher mehr als R
P
Pausenperioden
hat, unterscheidet sich von seiner ,,Güte" nicht von einem Zustand mit genau
R
P
Pausenperioden.
Es ist notwendig, R
A
j+1
= 0 zu setzen (51.1), um einen Arbeitszustand
von einem Pausenzustand unterscheiden zu können. In einem Pausenzustand
gilt R
A
j
= 0, in einem Arbeitszustand R
A
j
> 0.
Dominanzregeln
Die Effizienz des Algorithmus beruht auf der Anzahl an
erzeugten Zuständen. Um nur die notwendigen Zustände zu speichern, werden
unnötige Zustände, die in ihrer Fortsetzung nicht mehr zum Optimum führen
können, gelöscht. Hierfür sind Dominanzbeziehungen zwischen Zuständen not-
wendig. Diese werden bei der Überprüfung der Effizienz EF F (X
j
) angewandt.
Es werden zuerst allgemeine Dominanzregeln dargestellt, bevor diese, als
mathematische Bedingungen formuliert, auf das Schichtplanungsproblem an-
gewandt werden. Dominiert L
k
j
den Zustand L
k
j
, so wird dies durch L
k
j
L
k
j
ausgedrückt. Der Zustand L
k
j
braucht nicht mehr fortgesetzt und kann somit
gelöscht werden. Seien S und S die Schichtpläne, welche L
k
j
bzw. L
k
j
enthalten.
Für eine Dominanz L
k
j
L
k
j
muss allgemein Folgendes gelten:
· Setzt man den Schichtplan S fort, so müssen mindestens genauso viele
dem
(bzw. in der späteren Erweiterung auch die
D
) in die Zielfunkti-
on einbezogen werden können wie von L
k
j
aus. Sei es, weil sie nur von
L
k
j
aus erreichbar sind oder weil L
k
j
mehr Ressourcen an Arbeit bzw.
Wochenarbeit besitzt, um diese einzubeziehen.
· Der Zielfunktionswert von L
k
j
muss mindestens dem von L
k
j
entsprechen.
· Der erste Schichtbeginn in der gesamten Woche ist bei S später oder
gleich spät wie bei S .
Obige Punkte werden bei den Erklärungen der einzelnen Dominanzregeln
anhand mathematischer Bedingungen erläutert.
Für die Anwendung von Dominanzregeln werden im Grundmodell zwei Grup-
pen von Labels untereinander verglichen. Gruppe (I) mit Labels, welche den
31
Die Indikatorfunktion wird zur Vereinfachung der Darstellung verwendet. Die explizite
Modellierung der Indikatorfunktion ist in Kapitel 6.2.3 erläutert.
60

6 Dynamisches Programm
Zustand ,,Pause" durch
R
A
k
j
= 0 und Gruppe (II) mit Labels, welche den
Zustand ,,Arbeit" durch R
A
k
j
> 0 beschreiben. Seien L
k
j
und L
k
j
zwei un-
terschiedliche Labels. L
k
j
dominiert L
k
j
wenn im Grundmodell folgende Bezie-
hungen gegeben sind:
I Für R
A
k
j
= 0 und R
A
k
j
= 0 muss gelten:
R
WA k
j
R
WA k
j
(52.1)
R
P k
j
R
P k
j
(52.2)
(obj)
k
j
(obj)
k
j
(52.3)
(s
mo
)
k
j
(s
mo
)
k
j
(s
mo
)
k
j
= R
P
(52.4)
II Für
R
A
k
j
> 0 und R
A
k
j
> 0 muss gelten:
R
WA k
j
R
WA k
j
(53.1)
R
A k
j
R
A
R
A k
j
R
A
R
A k
j
= R
A k
j
(53.2)
R
A k
j
R
A k
j
(53.3)
(obj)
k
j
(obj)
k
j
(53.4)
(s
mo
)
k
j
(s
mo
)
k
j
(s
mo
)
k
j
R
P
(53.5)
Erläuterung der Dominanzregeln: In beiden Fällen I und II muss durch (52.1)
bzw. (53.1) der dominierende Zustand weniger oder gleich viel Wochenarbeits-
zeit besitzen. Überdies wird durch (52.3) bzw. (53.4) festgelegt, dass der domi-
nierende Zustand einen geringeren oder gleich großen Zielfunktionswert besitzt.
Durch (52.4) bzw. (53.5) wird vorgegeben, dass beim Schichtplan des domi-
nierenden Zustands
L
k
j
die erste Schicht der Woche später beginnt als beim
dominierten Zustand L
k
j
. Es ist auch möglich, dass bei L
k
j
die Mindestpausen-
länge R
P
absolviert wurde, bevor die erste Schicht begonnen wurde.
Bedingungen (52.4) und (53.5) sind notwendig, da der Schichtplan über dem
gesamten Planungshorizont aus der Kombination von einzelnen Wochenplänen
zusammengesetzt wird. In einem Schichtplan könnte eine Arbeit in den letzten
Perioden des Sonntags beendet werden, wodurch ein Schichtbeginn der nächs-
ten Woche aufgrund der Mindestpausenlänge erst verspätet möglich ist. Da bei
der Erstellung der Labels unklar ist, welche Wochenschichtpläne zu einem op-
timalen Schichtplan über den gesamten Planungshorizont kombiniert werden,
sind Labels dominierend, welche einen späteren ersten Schichtbeginn in der
Woche haben, da diese mit mehr Schichtplänen aus der Vorwoche kombiniert
werden können.
61

6 Dynamisches Programm
Wenn beide Labels eine Pausenperiode darstellen (Fall I), so gilt L
k
j
L
k
j
,
wenn der Zustand L
k
j
zusätzlich eine längere Pause absolviert hat (52.2).
Für den Fall II, dass beide Labels eine Arbeitsperiode darstellen, müssen
folgende Bedingungen zusätzlich gegeben sein. Bedingung (53.2) stellt sicher,
dass von beiden Zuständen ein Pausenzustand zur gleichen Zeit erreicht werden
könnte. Dies ist aus folgendem Grund notwendig: Es ist eine Situation denkbar,
in welcher beispielsweise
R
WA k
j
R
WA k
j
, R
A k
j
= R
A k
j
- 1 < R
A
und (obj)
k
j
< (obj)
k
j
gilt. Auf den ersten Blick scheint L
k
j
besser als L
k
j
zu sein. Der Zustand L
k
j
kann jedoch im Gesamten einen in Bezug auf den Zielfunktionswert schlech-
teren Endzustand ergeben. Seien hierfür S und S die Schichtpläne (Politiken),
welche L
k
j
bzw. L
k
j
enthalten. Bei S kann ausgehend von L
k
j
eine Periode eher
in die Pause gegangen werden als bei S. Sei die Stufe des frühesten Pausen-
zustands bei S mit ~j bezeichnet. Nach Absolvierung der Mindestpausendau-
er bei S kann somit ein
dem
(~j) dem Zielfunktionswert hinzugefügt werden,
welches für den Schichtplan S nicht erreichbar wäre, da im Schichtplan S in
der Stufe ~j noch die letzte Periode der Mindestpausenlänge absolviert werden
muss.
Bedingung (53.3) besagt, dass der dominierende Zustand höchstens soviel
an der Ressource R
A
verbraucht hat, wie der dominierte Zustand.
Bestimmung der optimalen Politik
Nach Berechnung aller Labels für jede
einzelne Woche, kann aus den nicht-dominierten Labels die optimale Politik
a
und die Folge der optimalen Zustände x
bestimmt werden.
Das Vorgehen hierfür gliedert sich, wie im Algorithmus 2 dargestellt, in
zwei Teilschritte A und B. In A wird aus den Endzuständen der einzelnen
Wochen w die Kombination der besten Endzustände ermittelt, wobei von jeder
Woche genau ein Endzustand berücksichtigt werden muss und der Übergang
zwischen zwei Wochen entsprechende Nebenbedingungen einhalten muss.
Für jede Woche wird darauf im Teilschritt B mithilfe der Rekursionsglei-
chung
V (t(x
j
, a
j
)) = min
aA(x
j
)
{-
dem
j
· I
{l}
(a
j
) + V (x
j
)
}
anhand des in A ermittelten Zustands x
n
die restlichen Entscheidungen a
n-j
und Zustände x
n-j
mit j = 1, ..., n ermittelt. Es wird hierbei rekursiv vor-
gegangen, um alle vorhergehenden Zustände und Entscheidungen mithilfe der
Rekursionsgleichung zu berechnen.
62

6 Dynamisches Programm
Zu A) Bezeichne w
i
die letzte Stufe einer Woche i W.
32
Die Endzustände
einer Woche werden als L
k
i
w
i
mit k
i
K
w
i
bezeichnet. Um die entsprechen-
den Endzustände zu finden, welche den Zielfunktionswert über den gesamten
Planungshorizont minimieren, ist folgendes Minimierungsproblem zu lösen.
arg min
k
i
K
wi
iW iW
(obj)
k
i
w
i
(54)
unter der Nebenbedingung
R
P k
i
w
i
+ (s
mo
)
w
i+1
R
P
i = 1, ..., |W| - 1
(55.1)
Dieses Minimierungsproblem lässt sich als Kombinationsproblem lösen. Bei ei-
nem Planungshorizont von beispielsweise drei Wochen wird aus allen Endzu-
ständen L
k
i
w
i
mit i {1, 2, 3} alle Kombinationen L
k
1
w
1
, L
k
2
w
2
, L
k
3
w
3
bestimmt.
Sind beispielsweise die Anzahl der Labels auf der letzten Stufe der Wochen
durch
|K
w
1
| = 30, |K
w
2
| = 23 und |K
w
3
| = 25 gegeben, so müssen insgesamt
30
· 23 · 25 = 17250 Kombinationen berechnet werden.
Die Kombination mit dem kleinsten Zielfunktionswert wird als Optimum
festgelegt, wodurch die drei Zustände x
w
i
mit i = 1, 2, 3 bekannt sind.
Um Nebenbedingung (55.1) im Kombinationsproblem zu berücksichtigen,
wird ein Strafterm eingeführt, z.B. M
0, welcher zum Zielfunktionswert ad-
diert wird, um zu verhindern, dass die entsprechende Kombination den kleins-
ten Zielfunktionswert bilden kann.
Zu B) Ausgehend von den x
w
i
werden nun rekursiv für jede Woche separat
die restlichen Zustände und Entscheidungen iterativ bestimmt. Da jede Woche
einzeln betrachtet wird, ist der Zustand x
w
i
im Folgenden als x
n
bezeichnet.
Es werden nun die folgenden beiden Schritte für j = 1, ..., n wiederholt.
1. Aus x
n-j+1
wird zuerst a
n-j
für j = 1, ..., n ermittelt. Es gilt
R
A
n-j+1
> 0 a
n-j
= l
j = 1, ..., n
(56.1)
R
A
n-j+1
= 0
a
n-j
= p
j = 1, ..., n
(56.2)
Ist im bekannten Zustand x
n-j+1
der Ressourcenverbrauch an Arbeit
R
A
größer als Null, so ist dies nur möglich, wenn auf der vorherigen
Stufe n - j die Entscheidung {Arbeit} getroffen wurde (56.1). Ist der
Ressourcenverbrauch gleich Null, so muss eine Pause eingelegt worden
sein (56.2).
32
Bei Perioden über eine Stunde und sieben Tage in einer Woche sind beispielsweise
w
1
=
24
· 7 = 168, w
2
= 24
· 24 = 336 etc.
63

6 Dynamisches Programm
2. Aus V (x
n-j+1
) = (obj)
n-j+1
und a
n-j
wird anschließend iterativ das
gesuchte x
n-j
X
n-j
mit der Rekursionsgleichung ermittelt. Es gilt:
V x
n-j+1
= r x
n-j
, a
n-j
+ V x
n-j
j = 1, ..., n
Es wird also iterativ derjenige Zustand x
k
n-j
mit k K
n-j
gesucht, für
welchen bei a
n-j
= l
R
A k
n-j
+ 1 = (R
A
)
n-j+1
j = 1, ..., n
(57.1)
(obj)
k
n-j
-
dem
n-j
= (obj)
n-j+1
j = 1, ..., n
(57.2)
gilt und bei a
n-j
= p Folgendes:
R
P k
n-j
+ 1 = R
P
n-j+1
(58.1)
R
P k
n-j
= R
P
R
P
n-j+1
= 1
(58.2)
R
P k
n-j
= R
P
R
P
n-j+1
= R
P
R
A
n-j+1
= 0
j = 1, ..., n
(58.3)
(obj)
k
n-j
= (obj)
n-j+1
j = 1, ..., n
(58.4)
Wurde auf der Stufe n - j als optimale Entscheidung getroffen, eine weitere
Periode zu arbeiten, so muss nach (57.1) der Ressourcenverbrauch R
A
k
n-j
aus dem unbekannten Zustand x
k
n-j
um Eins erhöht werden, um auf den be-
kannten Ressourcenverbrauch R
A
n-j+1
zu kommen. Der unbekannte Ziel-
funktionswert (obj)
k
n-j
muss nach (57.2) abzüglich von
dem
n-j
dem bekannten
Wert (obj)
n-j+1
entsprechen.
Wurde entschieden zu pausieren a
n-j
= p , so muss nach (58.1) der Res-
sourcenverbrauch R
P
k
n-j
um Eins erhöht werden, um den bekannten Res-
sourcenverbrauch
R
P
n-j+1
zu erhalten. Ist der Wert R
P
n-j+1
alternativ
gleich Eins, so muss nach (58.2) die Stufe n-j +1 das Ende der ersten Pausen-
periode sein und die Stufe n-j das Ende einer Arbeitsperiode. Im Zustand der
Arbeit gilt aufgrund der Transformationsfunktion stets R
P
k
n-j
= R
P
, sodass
der gesuchte Zustand in (58.2) diese Bedingung erfüllen muss. Wurde bereits
die Mindestpausenlänge R
P
erreicht, so wird nach der Transformationsfunk-
tion (51.2) die Ressource R
P
nicht mehr erhöht. Deshalb ist nach (58.3) der
Ressourcenverbrauch von R
P
im unbekannten Zustand x
k
n-j
und im bekann-
ten Zustand x
n-j+1
gleich R
P
und R
A
n-j+1
= 0. Letztgenannter Term ist
notwendig, um die Zustände x
k
n-j
und x
n-j+1
als Pausenzustände zu identifi-
zieren.
64

6 Dynamisches Programm
Der Zielfunktionswert muss nach (58.4) auf beiden Stufen n-j und n-j +1
gleich sein.
Es ist nicht möglich, dass die obigen Bedingungen für mehrere Zustände
x
k
n-j
zutreffen, da in diesem Fall anhand der Dominanzregeln schwächere oder
identische Zustände gelöscht werden, sodass nur ein Zustand mit den entspre-
chenden Charakteristika übrig bleibt.
Schritt 1 und 2 wird für das nächste j fortgesetzt, solange bis man (x
0
, a
0
) der
jeweiligen Woche erhält. Wurde dies bei allen Wochen fortgesetzt, so kann aus
allen ermittelten a
j
der Schichtplan des gesamten Planungshorizonts erstellt
werden.
Darstellung der Indikatorfunktionen
Die in diesem bzw. nächsten Kapitel
erwähnten Indikatorfunktionen I
{p}
(a
j-1
) bzw. I
{l}
(a
j-1
), welche bei der Be-
stimmung der möglichen Entscheidung a
j
A
j
(x
j
) verwendet werden, sind
mit Binärvariablen vergleichbar. Da im Zustand j die Entscheidung a
j-1
un-
bekannt ist, können die Werte für I
{p}
(a
j-1
) bzw. I
{l}
(a
j-1
) nicht direkt be-
stimmt werden. Daher müssen diese durch den Ressourcenverbrauch an Arbeit
bestimmt werden. Es gilt Folgendes.
I
{p}
(a
j-1
) =
1, wenn bis Stufe j mindestens eine Periode pausiert wurde,
d. h. wenn R
A
j
= 0
33
0, sonst
bzw.
I
{l}
(a
j-1
)
=
1, wenn bis Stufe j mindestens eine Periode gearbeitet wurde,
d. h. wenn R
A
j
> 0
0, sonst
Die Schreibweise mit Indikatorfunktionen ist somit eine abkürzende Schreib-
weise, um in den einzelnen Formeln auf die Bedingungen ,,Wenn R
A
j
= 0,
dann..." bzw. ,,Wenn R
A
j
> 0, dann..." verzichten zu können.
6.3 Einführung weiterer Nebenbedingungen
In diesem Kapitel wird das dynamische Programm ergänzt, um weitere Neben-
bedingungen in der Schichtplanung einplanen zu können. Es werden die Verän-
derungen erklärt, welche für die Berücksichtigung des Dienstes, der Überstun-
den, der Mittagspause und des Startzeitfensters notwendig sind. Jedes dieser
Kapitel ist folgendermaßen unterteilt. Es wird - falls zutreffend - darauf ein-
gegangen, wie sich die Ertragsfunktion ändert und welche Entscheidungen in
Abhängigkeit des Zustands möglich sind. Des Weiteren wird erklärt, wie die
33
und nach Berücksichtigung des Dienstes zusätzlich
R
D
j
= 0
65

6 Dynamisches Programm
Zustände charakterisiert sind (d. h. welche Komponenten in einem Label ent-
halten sind), wie die Zustände durch die Transformationsfunktion aktualisiert
werden, wie die Dominanzregeln abgeändert werden und wie die optimale Po-
litik bestimmt wird. Die Problembeschreibungen der einzelnen Erweiterungen,
sind in den Kapiteln 5.2.1­5.2.4 ausführlich erläutert. Das vollständige DP
wird nochmals im Anhang B dargestellt.
6.3.1 Berücksichtigung eines Dienstes
Neben der Einplanung der Arbeit wird nun ein Bereitschaftsdienst berück-
sichtigt, welcher eine feste Länge besitzt und jeden Tag zum selben Zeitpunkt
beginnt. Es dürfen pro Woche einem Arzt höchstens N
D
Dienste zugeteilt
werden. Die Arbeitszeit der Dienste wird anteilig auf die Wochenarbeitszeit
angerechnet. In Kapitel 5.2.1 werden die Nebenbedingungen dargestellt.
Durch die Einführung eines Dienstes ist eine weitere Entscheidung möglich.
Sei a
j
= d, wenn auf der Stufe j entschieden wird, einen Dienst in der Periode
(j, j + 1) zu machen.
Ertragsfunktion
Die Ertragsfunktion ändert sich zu
r(x
j
, a
j
) =
-
dem
j
· I
{l}
(a
j
)
-
D
j
· I
{d}
(a
j
) =
-
dem
j
, für a
j
= l
-
D
j
, für a
j
= d
0
, für a
j
/
{l, d}
(47b)
Es werden nun zusätzlich zu den Werten der Dualvariablen
dem
die Werte
der Dualvariablen
D
in der Ertragsfunktion berücksichtigt, wenn ein Dienst
absolviert wird.
Label
Das Label R
WA
, R
A
, R
D
, R
P
, obj, s
mo
, n
D
, d
so
k
j
mit den drei zusätzli-
chen Komponenten R
D
, n
D
und d
so
charakterisiert nun einen Zustand. Hierbei
gibt R
D
den Ressourcenverbrauch des Dienstes
34
und n
D
{0, ...N
D
} die bis-
herige Anzahl an Diensten der Woche an. Die Komponente d
so
beschreibt, ob
ein Dienst am Sonntag stattfindet und ist 1, wenn dies der Fall ist und 0 sonst.
Der Initialisierungszustand x
init
wird durch L
1
0
= (0, 0, 0, R
P
, 0, 0, 0, 0)
1
0
aus-
gedrückt. Ausgehend von diesem Label wird jede Woche separat berechnet.
Entscheidungen
Die möglichen Entscheidungen a
j
in Abhängigkeit des Zu-
stands x
j
sind nun a
j
P{l, d, p}. Dies bedeutet a
j
kann jede Kombination
aus Arbeit, Dienst und Pause annehmen.
34
Der Ressourcenverbrauch entspricht den absolvierten Stunden eines Dienstes.
66

6 Dynamisches Programm
Im Einzelnen müssen folgende Ergänzungen bei den einzelnen Entscheidun-
gen gemacht werden.
·
a
j
= l für alle j mit x
j
X
j
, wenn zusätzlich
R
D
j
= 0
(48.4)
gilt, d. h., es kann nur gearbeitet werden, wenn gerade kein Dienst absolviert
wird.
·
a
j
= p für alle j mit x
j
X
j
, wenn abweichend
R
WA
j
= R
WA
R
A
j
= R
A
R
D
j
= R
D
(49.1b)
R
A
j
R
A
R
D
j
R
D
(49.2b)
R
P
j
= R
P
R
A
j
= 0
R
D
j
= 0
(49.4b)
gilt, d. h. es kann auch pausiert werden, wenn die Höchstdauer (49.1b) oder
Mindestdauer (49.2b) für einen Dienst erreicht worden ist. Alternativ kann
die Mindestpausendauer erreicht worden sein (49.4b), wobei es sich um einen
Pausenzustand handeln muss (Ressourcenverbrauch an Arbeit und Dienst ist
Null). Es sei daran erinnert, dass in der Problemformulierung R
D
= R
D
gilt.
·
a
j
= d für alle j mit x
j
X
j
, wenn
R
WA
j
R
WA
- ~
f
1
(j)
(59.1)
R
P
j
= R
P
(59.2)
j mod 24 = S
D
R
D
> 0
(59.3)
n
D
+ I
{S
D
}
(j mod 24)
N
D
(59.4)
gilt, d. h. der begonnene Dienst kann ohne Überschreitung von
R
WA
beendet
werden (59.1). Hierbei gibt ~
f
1
(j) die Stundenanzahl des auf der Stufe j begin-
nenden Dienstes an, welcher zur regulären Wochenarbeitszeit addiert wird.
35
Zusätzlich muss die Mindestpausenlänge erfüllt sein (59.2). Ein Dienst kann
absolviert werden, wenn entweder die Stufe j den Zeitpunkt S
D
darstellt, in
welcher ein Dienst starten kann oder bereits ein Dienst gestartet wurde (59.3).
Durch (59.4) wird sichergestellt, dass ein Dienst nur begonnen wird, wenn die
Anzahl N
D
an erlaubten Diensten dadurch nicht überschritten wird.
Transformationsfunktion
Da eine neue Entscheidung eingeführt wurde, wird
nun t
d
(x
j
, d) für a
j
= d als Transformationsfunktion definiert. Im Folgenden
werden notwendige Änderungen bzw. Ergänzungen bei den bisherigen Funk-
35
~
f
1
(
j) entspricht f
1
(
j), wobei ~
f
1
(
j) für eine Stufe j und f
1
(
j) für einen Knoten j definiert
ist.
67

6 Dynamisches Programm
tionen beschrieben. Es gilt L
j+1
L
j
und die Komponenten, welche sich
zusätzlich zum Grundmodell von L
j
auf L
j+1
ändern, sind:
t
p
(x
j
, p) :
R
A
j+1
= 0
R
D
j+1
= 0
(51.1b)
t
d
x
j
, d :
R
WA
j+1
= R
WA
j
+ I
{S
D
}
(j mod 24) · ~
f
1
(j)
R
D
j+1
= R
D
j
+ 1
(obj)
j+1
= (obj)
j
-
D
j
(s
mo
)
j
= 0
(s
mo
)
j+1
= j
n
D
j+1
= n
D
j
+ I
{S
D
}
(j mod 24)
j · I
{S
D
}
(j mod 24) ·
1
24
= 7
(d
so
)
j+1
= 1
(60.1)
(60.2)
(60.3)
(60.4)
(60.5)
(60.6)
Wird eine Pause eingelegt, so wird durch (51.1b) zusätzlich R
D
j+1
= 0
gesetzt. Somit wird ein Pausenzustand durch R
A
j
= 0 und R
D
j
= 0, ein
Arbeitszustand durch R
A
j
> 0 und ein Dienstzustand durch R
D
j
> 0
gekennzeichnet. Weitere Änderungen sind für die Transformationsfunktion bei
einer Pause nicht notwendig.
Wird die Entscheidung für einen Dienst getroffen, so wird durch (60.1) die
Wochenarbeitszeit um ~
f
1
(j) erhöht, wenn der Dienst in j gestartet wurde
I
{S
D
}
(j mod 24) = 1 . Dies bedeutet, die Addition der zusätzlichen Wochen-
arbeitszeit eines Dienstes zum bisherigen R
WA
erfolgt in der ersten Periode
eines Dienstes.
Die Ressourcenvariable R
D
erhöht sich um Eins (60.2) und der Zielfunkti-
onswert wird um
D
j
verringert (60.3). Da
D
j
nur für die Anfangsperiode eines
Dienstes ungleich Null sein kann, wird ähnlich der Wochenarbeitszeit in der
ersten Periode des Dienstes auch die Verringerung der Zielfunktion berücksich-
tigt.
Wurde bisher noch keine Schicht in der Woche begonnen (s
mo
)
j
= 0 , so
wird durch (60.4) der früheste Startzeitpunkt der ersten Schicht in der Woche
auf j gesetzt.
Die Anzahl der bisher gehaltenen Dienste erhöht sich in der ersten Dienst-
periode durch (60.5) um Eins.
Aufgrund der Zerlegung in einzelne Wochenprobleme ist es notwendig zu wis-
sen, ob am Sonntag ein Dienst gehalten wird, welcher am Montag der nächsten
Woche beendet wird. Dies wird durch (60.6) berücksichtigt. Der Sonntag einer
Woche besitzt die 24 Stufen j = 144, ..., 167. Wird ein Dienst am Sonntag
gestartet, so ergibt
j · I
{S
D
}
(j mod 24) ·
1
24
= 7 und (d
so
)
j+1
wird auf Eins
gesetzt. Würden Dienste um 0 Uhr jedes Tages gestartet werden, so wäre für
j = 144 die Berechnung 144
·
1
24
= 6. Für diesen speziellen Fall würde ein
68

6 Dynamisches Programm
Dienst am Sonntag, welcher 24 Stunden dauert, auch am Sonntag beendet sein,
wodurch die Komponente (s
mo
)
j
nicht aktualisiert werden müsste.
Dominanzregeln
Es werden nun drei Arten von Zuständen unterschieden.
(I): Ein Pausenzustand mit (R
A
)
k
j
= (R
D
)
k
j
= 0, (II): ein Arbeitszustand mit
(R
A
)
k
j
> 0 und (III): ein Dienstzustand mit (R
D
)
k
j
> 0.
Folgende Gleichungen müssen ergänzt werden, um festzustellen, ob L
k
j
L
k
j
gilt.
I Für
R
A
k
j
= R
D
k
j
= 0 und R
A
k
j
= R
D
k
j
= 0 muss gelten:
(s
mo
)
k
j
< S
D
+ R
P
(s
mo
)
k
j
S
D
+ R
P
(52.5)
n
D k
j
n
D k
j
(52.6)
II Für
R
A
k
j
> 0 und R
A
k
j
> 0 muss gelten:
(s
mo
)
k
j
< S
D
+ R
P
(s
mo
)
k
j
S
D
+ R
P
(53.6)
n
D k
j
n
D k
j
(53.7)
III Für
R
A
k
j
> 0 R
D
k
j
> 0 und R
D
k
j
> 0 muss gelten:
R
WA k
j
R
WA k
j
(61.1)
(obj)
k
j
(obj)
k
j
(61.2)
(s
mo
)
k
j
(s
mo
)
k
j
(s
mo
)
k
j
R
P
(61.3)
(s
mo
)
k
j
< S
D
+ R
P
(s
mo
)
k
j
S
D
+ R
P
(61.4)
n
D k
j
n
D k
j
(61.5)
Der Pausenzustand I wird nun durch einen Zustand gekennzeichnet, bei wel-
chem der Ressourcenverbrauch von R
A
und R
D
Null ist. Der dominierende
und der dominierte Zustand sind durch einen solchen Ressourcenverbrauch
gekennzeichnet.
Im Fall III ist der dominierte Zustand x
k
j
ausschließlich ein Dienstzustand.
Die dominierenden Zustände können Zustände der Arbeit oder des Dienstes
sein. Hierdurch wird verhindert, dass ein Dienstzustand einen Arbeitszustand
dominieren kann. Grund hierfür ist, dass von einem Dienstzustand in Stufe j
aus nicht alle
dem
j+i
mit i N
0
erreicht werden können, wie von einem Arbeits-
zustand aus, was der Grundregel der Dominanz widerspricht.
Für alle drei Fälle gilt nun nach Bedingungen (52.6), (53.7) und (61.5) zu-
sätzlich, dass im dominierenden Zustand höchstens gleich viele Dienste wie im
schwachen Zustand absolviert wurden.
Bei den Bedingungen (52.5), (53.6) und (61.4) zeigt S
D
+ R
P
den Zeitpunkt
69

6 Dynamisches Programm
an, ab welchem bei Absolvierung eines Dienstes am Sonntag der vorherigen
Woche, eine Schicht aufgenommen werden könnte. Dies ist der Zeitpunkt des
Schichtendes plus der Mindestpausendauer. Dieser Zeitpunkt wird im Folgen-
den als j
mo
bezeichnet. Der Schichtplan, welcher bis zu einem dominierten
Zustand L
k
j
führt, muss eine Schicht enthalten, welche früher als j
mo
beginnt.
Alternativ ist es möglich, dass beim Schichtplan des dominierenden Zustands
L
k
j
die erste Schicht in einer späteren Periode als j
mo
anfängt.
Grund für diese Bedingung ist die Kombination von einzelnen Wochenplänen
zu einem Schichtplan über den gesamten Planungshorizont. Ein Schichtplan,
welcher ermöglicht, dass in der Vorwoche am Sonntag ein Dienst eingeplant
werden kann, ist u. U. wertvoll, da das
D
vom Sonntag einen sehr großen
Wert annehmen könnte. Deshalb kann ein Zustand eines solchen Schichtplans
nur von einem Zustand dominiert werden, welcher im Hinblick auf die Er-
möglichung eines Dienstes am Sonntag der Vorwoche mindestens genauso gut
ist.
Die Erklärung von Bedingungen (61.1), (61.2) und (61.3) ist identisch zu
der Erklärung von (52.1), (52.3) und (52.4).
Bestimmung der optimalen Politik
Durch die Einführung eines Dienstes
sind sowohl bei der Bestimmung der besten Endzustände (Teilschritt A) als
auch bei der Ermittlung der übrigen Entscheidungen und Zustände (Teil-
schritt B) Nebenbedingungen zu ergänzen.
Zu A) Bei der Kombination der unterschiedlichen Wochen muss nun der
Dienst am Sonntag, welcher am Montag der nächsten Woche endet, beachtet
werden. Folgende Ergänzungen bei den Nebenbedingungen des Minimierungs-
problems sind notwendig. Hierbei drückt der Parameter ~
f
1
(j
so
D
) di