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 Stunden eines Dienstes. . . . . . . . . . . . . . . . . . . . . . . . . 29 Tab. 2 Allgemeine Parametereinstellungen. . . . . . . . . . . . . . . . 89 Tab. 3 Abweichende Parametereinstellungen bei Variation der Häufigkeit 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 Effizienzprü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

Tab. 11 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 Praxisbeispiel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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

Tab. 17

Tab. 18

δ D für zwei Wochen. . . . . . . . . . . . . . . . . . . . . . . . 99 Kennwerte der Labels bei Variation der Dichten von δ dem und Tab. 19

δ D für vier Wochen. . . . . . . . . . . . . . . . . . . . . . . . 100 Tab. 20 Abweichende Parametereinstellungen bei Auslassung der Nebenbedingung für die Mittagspause. . . . . . . . . . . . . . . 101 Tab. 21 Lösungszeiten bei Auslassung der Nebenbedingungen „Mittagspause“, „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 Mindestarbeitszeit. . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Tab. 24 Lösungszeiten bei Variation der Mindestarbeitszeit. . . . . . . 103 Tab. 25 Kennwerte der Labels bei Variation der Mindestarbeitslänge

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 Effizienzprü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ührlicheDarstellung. . . . . . . . . . . . . . . . . . . . . . . xxiv Tab. C.5 Lösungzeiten des MIPs, DPs und SPs im Praxisbeispiel - aus- führlicheDarstellung. . . . . . . . . . . . . . . . . . . . . . . xxv Tab. C.6 Kennwerte der Labels beim Praxisbeispiel - ausführliche Darstellung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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-

Tab. C.13 Kennwerte der Labels bei Auslassung der Nebenbedingungen

Tab. C.14 Lösungszeiten bei Variation der Mindestarbeitszeit - ausführ- licheDarstellung. . . . . . . . . . . . . . . . . . . . . . . . . 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- licheDarstellung. . . . . . . . . . . . . . . . . . . . . . . . . . xxxiii Tab. C.17 Kennwerte der Labels bei Variation der Höchstarbeitszeit über

Tabellenverzeichnis

Tab. C.18 Lösungszeiten bei Variation des Startzeitfensters - ausführli- cheDarstellung. . . . . . . . . . . . . . . . . . . . . . . . . . xxxv Tab. C.19 Kennwerte der Labels bei Variation des Startzeitfensters über

Abbildungsverzeichnis   

Abb.  1 Ein Schichtplan über sieben Tage.  

Abb.  2 Aufbau des Graphen G.  

Abb.  3 Arbeit und Pause auf dem Graphen G.  

Abb.  4 Graph G mit Ressourcenvariablen, Ressourcenfenstern und  

Kantengewichten.   

Abb.  5 Graph G mit Binärvariablen von Arbeit und Pause.  

Abb.  6 Graph G mit Binärvariablen von Arbeit, Pause und Dienst.  

Abb.  7 Graph G mit Binärvariablen der Mittagspause.  

Abb.  8 Stufen im dynamischen Programm.  

Abb.  9 Ausschnitt eines Schichtplans vor dem Verschieben von Ar-  

beitsschichten.   

Abb.  10 Ausschnitt eines Schichtplans nach dem Verschieben von Ar-  

beitsschichten.   

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

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. konkretes 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 c over

c sched Gesamtkosten, die aus einem Schichtplan resultieren D Index für den Dienst D Menge der Tage im Planungshorizont

d

δ δ dem Wert der Dualvariable der Arbeitsnachfrage- ab

δ D Wert der Dualvariablen der Dienstnachfrage- ab

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

f 2 (j) Funktion, welche jeder Nummer eines Knotens j ∈ V eine

h w

Index eines obenliegenden Knotens mit i ∈ V i

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 Index eines untenliegenden Knotens mit j ∈ V j K d Anzahl an Knoten pro Tag

Anzahl an Knoten pro Woche, mit K w = (|V| − 2)\|W| K w λ(·) Verhältnis der Lösungszeit zur Anzahl an erstellten (EL)

M

N D Maximale Anzahl an Diensten pro Woche

viii

Symbolverzeichnis - Allgemein und MIP

Anzahl an Überstunden in der Woche w ∈ W 0 o w P Index für Pause

q q j,j +

Binärvariable, mit 1, wenn der Arzt in der Periode (j − , j) q j − ,j

mit j ∈ V eine Mittagspause absolviert, 0 sonst Index für Ressourcen, mit r ∈ T r R A Anzahl an Arbeitsstunden, welche in Woche w nicht zur Ver-

w

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 Höchstdauer der Ressource r ∈ T R r

R P Anzahl an Stunden, welche vor Beginn des Planungshorizonts bereits pausiert wurden R r (a) Höhe der Ressource r ∈ T im Knoten a ∈ V Mindestdauer der Ressource r ∈ T R r 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 T late T post Mindestdauer an Arbeit nach Beendigung einer Mittagspause T pre Mindestdauer an Arbeit vor Aufnahme einer Mittagspause T win Maximale Länge zwischen frühestem und spätestem Arbeitsbeginn pro

Woche Anzahl an „Fehlstunden“ in der Woche w ∈ W u w v Vertragliche Wochenarbeitszeit

i ∈ V} ⊂ V

V Menge der untenliegenden Knoten, mit V = {j|j mod 2 = 0 : j ∈ V} ⊂ V

Symbolverzeichnis - Allgemein und MIP

D ˆ V Teilmenge der untenliegenden Knoten bei denen der Dienst

w

V e Teilmenge des letzten untenliegenden Knotens der Woche w,

w

V non Menge der Knoten, bei denen die Variable χ ∈

χ

W

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

Binärvariable, mit 1, wenn der Arzt in Periode (j − , j) pau- x j − j siert, 0 sonst

Binärvariable, mit 1, wenn der Arzt in Periode (i − , i) arbei- x i − i tet, 0 sonst

y i − i

Binärvariable, mit 1, wenn der Arzt in der Periode (j − y j − j o , j)

Symbolverzeichnis - DP

Symbolverzeichnis - DP

a j

A j (x j )

a ∗

b Index für eine Mittagspause bei der Entscheidung a j

d δ dem

j

δ D Wert der Dualvariablen der Dienstnachfrage- j

(d so ) k

j

(e) k

j

(l) k

j

EF F (X j ) Methode des Algorithmus im dynamischen Programm, welche die Zustände x j ∈ X j auf Effizienz überprüft e win Zeitpunkt des Endes eines Startzeitfensters

˜ f 1

(j) f 3

Γ

24/7 angibt, dass es möglich ist, rund um die Uhr zu arbeiten I {A} (x) Indikatorfunktion (auch charakteristische Funktion genannt)

j Index für eine Stufe j so Index für eine Stufe, auf welcher an einem Sonntag der Dienst

D

beginnt

K j

Symbolverzeichnis - DP

L k

j

l (mp) k

(obj) k

j

∧ 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-

P(Ω) Potenzmenge einer beliebigen Menge Ω, wobei in dieser Arbeit ∅ / ∈ P(Ω) definiert sei

p Φ r(x j ,a j ) Ertragsfunktion r init Wert der Zielfunktion auf der Stufe j = 0 R P Minimaler Wert der Pausenressource R P von allen Endzu- min,VW

ständen einer Vorwoche (R r ) k

j

S

(s mo ) k

j

s win Zeitpunkt des Beginns eines Startzeitfensters t(x j ,a j ) T r ansformationsfunktion im dynamischen Programm, wobei

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-

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 Notwendigkeit 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- gewandtePflegeforschung (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äfte) 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 gleichen Zeitraum ein Aufbau des ärztlichen Personals in erheblichem Umfang (+19,5%). Die Belastungszahl des Pflegedienstes nach Fällen stieg in zehn Jahren von 48 Patienten auf 59, was einem Plus von 23% entspricht!“

Weitere Informationen, die bestätigen, dass dieser Trend im Jahr 2008 fortgesetzt wurde, sind im Bericht des Statistischen Bundesamtes „Grunddaten der Krankenhäuser“ (Statistisches Bundesamt 2009) zu finden. Oben beschriebene Entwicklungen verstärken die Notwendigkeit eine effiziente Schichtplanung für das im Krankenhaus eingesetzte Personal zu entwickeln. Der Großteil der aktuellen Forschung bezieht sich auf die Planung des Pflegepersonals (nurse scheduling). Eine Übersicht über bisherige Veröffentlichungen hierzu gibt Cheang et al. (2003) und Burke et al. (2004). Bisherige entwickelte Methoden, welche für einen kurzen bzw. mittleren Planungshorizont 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 Problem 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 ¹ 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ücksichtigen. 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. Hierbei 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 Arbeitszeit wird der regulären Wochenarbeitszeit angerechnet. Nach einer Arbeit bzw. einem Dienst muss eine Mindestpausenlänge eingehalten werden. Weitere Restriktionen sind die Berücksichtigung einer maximalen Wochenarbeitszeit und einer Mittagspause. Da die Arbeit eines Arztes zu einem beliebigen Zeit- punkt ineiner 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 sieben 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 (Mittagspause 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 hellgrau hinterlegten Einsen erkennbar ist. Diese findet jeweils von 12 bis 13 Uhr

¹ 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

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 Mindestpausenlänge von zwölf Stunden eingehalten wird. Bei der Erstellung eines Schichtplans für einen einzelnen Arzt ist der pe- riodenabhängigeNutzen 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 reduzierten Kosten einer Spalte. Es sei daran erinnert, dass die Schichtplangenerierung die Erzeugung einer Spalte im Subproblem darstellt und diese bei einem B&P so lange fortgesetzt wird, bis der Nutzen einer Spalte nichtnegativ 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 Netzwerk 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 Programmierung (DP) gewählt.

Im folgenden Kapitel 2 wird eine Übersicht über die Literatur gegeben. Hierbei wird auf bisherige Forschungsarbeiten im Zusammenhang der Schichtplanung (scheduling) eingegangen und insbesondere jene dargestellt, welche im Lösungsverfahren ein Netzwerk bzw. ein RCSP wählen. Überdies werden Arbeiten erwähnt, welche die dynamische Programmierung als Lösung verwenden. 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 entsprechenden 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 beschrieben und der Zusammenhang zur Schichtplanung dargestellt. In Kapitel 4.2 werden 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 Mindestpausendauer 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 Startzeitfenster 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 Problem und kann, wenn als dynamisches Programm (DP) formuliert, in pseudopolynomialer Zeit gelöst werden.

Da das Kürzeste Wege Problem mit Ressourcenbeschränkung als MIP keine 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 dargestellt. Hierbei wird deutlich, dass die Lösung des RCSP als MIP im Durchschnitt 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 verschiedener 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 Symbole, welche ausschließlich für die Beschreibung des dynamischen Programms verwendet werden. Alle weiteren Symbole, welche in den anderen Kapiteln erstmals 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 Schichtplanungsproblem 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ösungsverfahren 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 Forschungen in der Schichtplanung (scheduling und rostering) wobei in Ernst et al. (2004a) eine kommentierte Übersicht von 700 Veröffentlichungen zusammengestellt ist. Die am meisten eingesetzte Lösungsmethode ist die ganzzahlige Programmierung (ohne spezielle Lösungsalgorithmen) und Heuristiken, welche 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. ² 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 Bereich von Call Center behandeln, gibt Mandelbaum (2006). Diese Arbeit enthält auch Verweise zur Schichtplanung bei Call Centern.

² 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 Spaltengenerierungsverfahrens verwendet.

Desrochers und Soumis (1989) beschreiben ein crew scheduling Problem an- handder 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 maximale Anzahl an Arbeitspaketen pro Fahrer, eine einzuhaltende Pause zwischen zwei Arbeitspaketen, eine Höchstarbeitszeit pro Tag und eine maximale Anwesenheitsdauer 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 wirdmit 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 betrachtet. (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, inwelchen gearbeitet werden kann, und Präferenzen bzgl. gewisser Schichten können ebenso wie Engpässe in der Deckung der Nachfrage berücksichtigt 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 zulä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 Schichtplanung 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): Ausgehend 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 Krankenhaus. Es werden sieben verschiedene feste Schichttypen über drei Tageszeiten (Tag, Abend, Nacht) berücksichtigt. (ii): Als Nebenbedingungen werden die maximale Arbeitszeit, die Einhaltung einer Anzahl an arbeitsfreien Wochenenden 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 mehrere 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- handdes 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 Krankenschwestern gegeben.

8

2 Literaturüberblick

Schichtplanung mit dynamischer Programmierung

Ernst et al. (2004a) zählt 17 Veröffentlichungen, welche die dynamische Programmierung 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 Beispiels 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 eine 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, welchesdie Dienstblöcke erstellt, wird ähnlich wie in Desrochers und Soumis (1989) als RCSP modelliert und mit einem DP gelöst. (iv): Es werden 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äferenzen 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 einzelnen 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 behandelt. Die Besonderheit liegt in der großen Flexibilität des Ansatzes, der variable 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 Mindestpausenlänge zwischen zwei Schichten zu berücksichtigen sind. Das beschriebene Subproblem, welches als MIP gelöst wird, liefert nur für einfache Probleminstanzen 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 Problem reformuliert und auch mit einem DP gelöst wird. Bisher wurde jedoch kein Ansatz veröffentlicht, welcher durch die Gestaltung der Nebenbedingungen 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 ³ aus

Brunner et al. (2010) dargestellt. Im letzten Abschnitt werden die Nebenbedingungen erläutert.

3.1 Begriffe der Schichtplanung

In dieser Arbeit werden insbesondere folgende Begriffe verwendet. Um Unklarheiten zu vermeiden, werden diese nun definiert.

Arbeit Die reguläre Tätigkeit eines Arztes, welche eine Mindest-

Dienst Ein Dienst ist die Abkürzung für den Bereitschaftsdienst.

Schicht

Arzt in der Arbeit oder im Dienst tätig ist. Schichtplan Ein Schichtplan stellt über einen begrenzten Zeithorizont

Mittagspause Während einer Arbeit muss ein Arzt eine Mittagspause ver-

Pause Nach einer Schicht muss ein Arzt eine gewisse Zeit pausie- ren,in welcher keine neue Schicht begonnen werden darf.

³ 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 Abbildung 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 Kosten minimiert, welche durch Zuteilung von Ärzten auf die Schichtpläne entstehen. Hierbei würde durch die Generierung aller möglichen Schichtpläne am Anfang zu viele Kombinationsmöglichkeiten berücksichtigt werden müssen, sodass 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- gebenenDualvariablen zugeordnet werden. Diese sind:

NB I (δ dem ab ) stellt ein ausreichendes Angebot an Ärzten zu jeder Peri-

NBII (δ D ab )

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

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 Kosten, 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:

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 entsprechenden nichtnegativen Dualvariable δ dem bzw. δ D ab gezeigt werden. Die

ab

Dualvariable δ dem ist in Perioden (a, b), in welchen im Masterproblem keine

ab

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

wobei x ab bzw. y ab eine Binärvariable ist, welche Eins ist, falls in der Periode (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 entsprechende 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 Spalten 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 erlä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 Zielfunktion 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ülltsein 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 ergibtsich aus den gearbeiteten Schichten und der nicht aus- bezahltenArbeitszeit bei den Diensten. Eine Mindestwochenarbeitszeit wird nicht modelliert. Diese ist im Tarifvertrag festgesetzt, jedoch werden 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 definierten 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 kompensiert 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 einer 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 Ressourcenbeschrä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 optimiert. 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. ⁴ 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.

Graph Sei G = (V, A) ein gerichteter, azyklischer Graph mit n = |V| topologisch sortierten Knoten v 1 , ...v n und m = |A| Kanten. ⁵ 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 ⁶ 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.

⁴ Graphen, Netzwerke und Kürzeste Wege Probleme werden ausführlich in Ahuja et al.

(1993) und Jungnickel (1994) dargestellt.

⁵ Die Notation |A| beschreibt die Mächtigkeit der Menge A.

⁶ 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:

• j = (j − 2) ⁺ = (i − 2) ⁺ • i − 2 = i − = j −

• 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 Periode (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 − 2endet, 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ßendwurde 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 Fortsetzung 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. ⁷ Ein Pfad repräsentiert einen Schichtplan. Kanten (i − , i) stellen eine Arbeitsperiode im Schichtplan dar und Kanten (j − , j) eine Pausenperiode.

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.

⁷ Es gilt für die Anzahl der durchschrittenen Knoten vom Quellknotenpaar zum Senkekno-

tenpaar, dass |P | = 1 2 (|V| − 2) = 1

4 Formulierung als Kürzeste Wege Problem

Kantengewichte Um den Aufbau des Netzwerkes zu vervollständigen, werden den Kanten des Graphen G Gewichte zugeordnet, sodass der bisherige

Graph G = (V, A) zu G = (V, A, δ) erweitert wird. Hierbei entspricht δ einem 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önnen 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 0. Der Wert der Dualvariable für denen gearbeitet werden kann, ist δ dem

ab

den Dienst ist stets Null, bis auf die Periode, in welcher der Dienst gestartet ab 0. werden kann. In dieser Periode ist δ D

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 Nebenbedingungen eines Schichtplans zu ermöglichen. Eine ausführliche Grundlage über die generelle Formulierung eines RCSPs wird in Zhu (2005) und Grünert und Irnich (2005b) gegeben.

Ressourcen Es werden vier verschiedene Ressourcenvariablen eingeführt, welche 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 Knoten a ∈ V zugeordnet. ⁸ 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önnen in bestimmten Situationen auf einen Anfangswert zurückgesetzt werden, z.B. werden die Ressource P , A und D am Ende der ersten Periode einer Pause, 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 Knoten 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

⁸ 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 modelliert 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 Verbrauch an Arbeit, Dienst bzw. Pause pro Periode somit genau Eins ist. Da in Kapitel 5 einer Kante (a, b) binäre Entscheidungsvariablen zugeordnet werden, welche Eins sind, wenn diese Kante durchschritten wird, kann der Ressourcenverbrauch weggelassen werden. Wird eine Kante (a, b) durchschritten, 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. Beispielsweise müsste bei einer halbstündigen Periodeneinteilung die maximale Wochenarbeitszeit von 48 auf 96 Einheiten verdoppelt werden.

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

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, Ressourcenvariablen und Kantengewichten. Um den Graphen übersichtlich zu halten, sind die Ressourcenfenster bzw. Ressourcenvariablen nur für jeweils zwei Knoten 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 formuliert. Zuerst wird das Grundmodell des MIPs beschrieben. Dieses berücksichtigt Mindest- und Höchstdauern an Arbeit, Wochenarbeit und Pause. In Abschnitt 5.2 wird dieses Modell erweitert. Nebenbedingungen für den Dienst, die Überstunden, die Mittagspause und das Zeitfenster der verschiedenen Startzeitpunkte werden ergänzt. Das vollständige Modell des MIPs mit allen Nebenbedingungen 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 =

⎪ ⎩

und

⎧

⎪ ⎨ x j − j =

⎪ ⎩

Die beiden Variablen x i − i bzw. x j − j unterscheiden sich darin, auf welchen Kanten 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- periodean.

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 erkennt, dass die Kanten mit den Binärvariablen x (j−2)i bzw. x (i−2)i eine Arbeits- periode unddie Kanten mit x j(j+2) bzw. x i(j+2) eine Pausenperiode darstellen.

x (i−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 Kombination der Binärvariablen kann somit ein Schichtplan erstellt werden. Abbildung 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 s V Teilmenge der obenliegenden Knoten bei dem seit Beginn der Woche

w

s w eine Periode vergangen ist, mit V w = {i|i mod K w = 3 : i ∈ V} ⊂ V T Menge der Ressourcen, mit T = {A, WA, P, D} Index eines obenliegenden Knotens, mit i ∈ V i

Index eines untenliegenden Knotens, mit j ∈ V j 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| Höchstdauer der Ressource r ∈ T R r

Mindestdauer der Ressource r ∈ T R r δ dem Wert der Dualvariable der Nebenbedingung I aus dem Masterproblem,

ab

mit (a, b) ∈ A Positive, genügend große Zahl ⁹ M

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

unter den Bedingungen, dass

NB: Flusserhaltung

r∈(q) +

p∈a −

r∈(t−1) −

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) ∀i ∈ V R A (i) M (1 − x i − i ) + 1 (7) ∀i ∈ V R A (i) x i − i (8)

⁹ 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)

s R WA (i) = x i − i + x i − i ∀i ∈ V (10)

w

s R WA (i) = R WA (i − ) + x i − i + x i − i ∀i ∈ V \ V (11)

w

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äutert.

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 Flussbedingungen 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 bedeutet, 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 Mengeneinheit 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 Bedingungen (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 notwendig sind, da keine Maximalpausenlänge vorhanden ist. Als Folge wurden die Nebenbedingungen so formuliert, dass die Pausenlänge R P (a) nach einer Pausenperiode 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 Bedingung (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 Woche) 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-

s tenmenge V w beschrieben und beinhaltet nicht die Anfangsknoten der

nullten sondern der ersten Periode. ¹⁰ 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 s Knoten aus V 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 ¹¹ 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-

¹⁰ Esist 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

s Null ergeben. Die Einführung von V w ist wichtig für die Berechnung von Überstunden

und Fehlstunden, welche in Kapitel 5.2.2 besprochen werden.

¹¹ 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 Nebenbedingungen (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 .

s w ergibt sich R WA (i) nach (10) aus Addition von binären Va- • Für i ∈V riablen.

s w errechnet sich R WA (i) nach (11) aus der Addition von • Für i ∈ V \ V

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ücksichtigen, 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ächste zu beginnen. Dies ist der Fall, da die δ dem bzw. δ D ab nur ungleich Null sein

ab

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ösungsverfahren 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 Bedingung (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ücksichtigt werden können. Kapitel 5.2.3 erweitert das bisherige Modell um eine Mittagspause und Kapitel 5.2.4 behandelt die Einschränkung der unterschiedlichen Startzeitpunkte in einer Woche.

Am Anfang jedes dieser Kapitel wird eine Problembeschreibung gegeben. Darauf folgend werden notwendige Ergänzungen der Notation und der Nebenbedingungen im Vergleich zum Grundmodell eingeführt. In einem dritten Abschnitt werden jeweils die neuen bzw. modifizierten Nebenbedingungen erlä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 ¹² 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 Wochenarbeitszeit 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.

Freitag 8 1 6

Samstag

Sonntag

Tab. 1: Zur Wochenarbeitszeit angerechnete und ausbezahlte Stunden eines

Dienstes.

¹² 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.

¹³ 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 ⎧

⎪ ⎨ 1, wenn der Arzt in der Periode (i − , i) mit i ∈ V einen Dienst hat

y i − i =

⎪ ⎩

0, sonst

und

⎧

⎪ ⎪ ⎪ ⎪ ⎨ 1, wenn der Arzt in der Periode (j − , j) mit j ∈ V die erste Periode

y j − j = 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 eingefü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.

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 Wert der Dualvariablen der Nebenbedingung II aus dem

ab

Masterproblem, mit (a, b) ∈ A V D Teilmenge der untenliegenden Knoten bei denen der Dienst D in

w

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 r (i) 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 Bedingungen (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 Variablen 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

5 Gemischt ganzzahliges Programm

gilt.

Die hinzugefügten Binärvariablen müssen auch in den Flussbedingungen integriert 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.

p∈a −

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 Bedingungen (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 fortgesetzt wird.

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 Bedingungen (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:

p∈i −

p∈i −

(

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.

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 Minimierung der Zielfunktion berücksichtigt. Die Zielfunktion ändert sich zu

Zu berücksichtigen ist, dass der Parameter δ D i − i lediglich in der ersten Periode 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. Abweichendvon dieser Arbeitszeit kann er maximal insgesamt

R WA Stunden pro Woche arbeiten. Der größte Wert der Variable o w ∈ N 0 , welche 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 folgenden Woche angerechnet. Um dies zu berücksichtigen, wird eine Knoten- D menge ˆ V 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

D Menge berücksichtigt sind. In ˆ V 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} D ˆ V Teilmenge der untenliegenden Knoten bei denen der Dienst D

w

in Woche w startet zur Berechnung von v V e Teilmenge des letzten untenliegenden Knotens der Woche w,

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

Anzahl an Überstunden in Woche w ∈ W 0 o w

Anzahl an „Fehlstunden“ in Woche w ∈ W u w

Anzahl an ausbezahlten Überstunden in Woche w ∈ W h w

Folgende Bedingungen ergänzen das bisherige Modell, um die Werte von o w , u w und h w bestimmen zu können.

v =

∀w ∈ W h w o w−1 − u 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)

¹⁴ 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) berechnet, 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- geglichenwerden 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

Die Bedingung (1c) stellt die Zielfunktion dar, falls keine Mittagspause berü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 ganzzahlig. 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 Ganzzahligkeit 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.

¹⁵ 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 eineMittagspause über eine Periode berücksichtigt. Für einen Dienst wird keine Mittagspause bestimmt. Vor einer Mittagspause muss der Arzt mindestens 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

⎧

⎪ ⎪ ⎪ ⎪ ⎨ 1, wenn der Arzt in der Periode (j − , j) mit j ∈ V eine

q j − ,j = Mittagspause hat ⎪ ⎪ ⎪ ⎪ ⎩ 0, sonst

und

⎧

⎪ ⎪ ⎪ ⎪ ⎨ 1, wenn der Arzt nach einer Mittagspause in der Periode (j, j ⁺ )

mit j ∈ V die erste Periode arbeitet q j,j + =

⎪ ⎪ ⎪ ⎪ ⎩ 0, sonst

Abbildung 7 zeigt eine Mittagspause auf dem Graphen G. Auf den durchgezogenen Kanten sind die angegebenen Binärvariablen Eins. Die Mittagspause

erfolgt in Periode (i-2,j), sodass die Variable q (i−2)j = 1 ist. ¹⁶ 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.

x (i−4)(i−2) x (i+2)(i+4)

... i − 4

... j − 4

¹⁶ 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 folgende 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

(w − 1)K w + dK d : j ∈ V, w ∈ W, d ∈ D} ⊂ V

Für die Einhaltung der Mittagspause werden folgende Bedingungen im Modell 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) (x jj + − q j − j ) = 0 ∀w ∈ W, d ∈ D (39) j∈V w,d q i − i , q ii ⁺ ∈ {0, 1} ∀ i ∈ V (40)

Erläuterung Im Folgenden werden die Bedingungen (35)-(40) näher erläutert.

• 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 gearbeitet werden. Dies wird durch die Bedingung (37) sichergestellt. Hierbei

wurde im Knoten j − die Mittagspause begonnen, sodass die vor Aufnahme 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 Ende 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 ebenso 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 geschrieben 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) s R WA (i) = R WA (i − ) + x i − i + x i − i + q i − i ∀i ∈ V \ V (11b)

w

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 Bedingungen beinhalten auch die Änderungen, welche sich durch Einführung des Dienstes ergaben, bisher jedoch nicht vermerkt wurden.

r∈q +

(x pa + y pa + q pa )−

p∈a −

∀a ∈ V \ {q, q + 1, t − 1, t} (3c) (x as + y as + q as ) = 0

s∈a+

r∈(t−1) −

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, welche in die Senkeknoten münden, kann durch Bedingung (4b) ebenso nur eine

¹⁷ 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 Flusserhaltung 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

5.2.4 Berücksichtigung eines Zeitfensters

Problembeschreibung Der Startzeitpunkt der Arbeit ist beliebig, liegt jedoch 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 Arbeitsbeginns nicht zu sehr auseinander weichen, werden diese auf maximal T win Stunden 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 →

Die folgenden Nebenbedingungen bestimmen den spätesten Startzeitpunkt und sorgen für die Einhaltung des Zeitfensters T win . ⎛ ⎞ ⎞

l w

l w −

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 zwischen den verschiedenen Startzeiten der Arbeit in einer Woche w auf T win . Hierbei berechnet Bedingung (41) den spätesten Schichtbeginn in der Woche 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 x jj + = 1, so

j∈V w,d

folgt aus Bedingung (42), dass die Differenz zwischen dem spätesten Schichtbeginn 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 x jj + = 1,

j∈V w,d

also an einem Tag d gearbeitet wird. Auf der linken Seite wird von l w etwas Ganzzahliges abgezogen. Es wird nun überprüft, ob l w abzüglich etwas Ganzzahligem kleiner oder gleich dem ganzzahligen Zeitfenster ist. Ein maximales 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- R P gibt an, wieviele 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

übergibt die bisherige Pausendauer an die Ressourcenvariable des unteren Quellknotens q+1. Falls die Arbeit zu jedem Zeitpunkt am ersten Tag des

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 R P = −8 berücksichtigt.

Falls in einer Woche nicht die maximale Wochenarbeitszeit R WA zur Verfü- w mit w ∈ W berücksichtigt,wel- R A

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 R A w ab- gebildetwerden. Hierfür muss die Bedingung (30) abgeändert werden, indem R A w dazugezählt wird:

v =

j∈V

5.3 Preprocessing

Die Anzahl der Variablen und Nebenbedingungen des ganzen Modells inklusive 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 zugewiesen werden kann. Berücksichtigt man den Zeitrahmen, in dem ein Arzt eine Arbeit ausführen kann bzw. einen Dienst beginnen kann, die Mindestarbeitszeit 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 notwendig. 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 nehmen, 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 Menge V non eingeführt. Hierbei sei i stets aus den oberen Knoten V und p i :=

χ

¹ (i mod K d ) − 1 . Dabei gibt p i einen Zeitpunkt zwischen 0 und 23 Uhr an,

2

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 berechnet. 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 = V non

x i − i

V non

x i − i V non

x ii +

V non

q ii ⁺ V non

q i − i V non

y ii ⁺ V non = V \ V D

y i − i w

Im Folgenden werden die einzelnen Mengen kurz erläutert. Bei der Interpretation 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 Eine fortgesetzte Arbeitsperiode kann nicht früher als eine Periode nach

x i − i

Arbeitsbeginn S A oder später als das Arbeitsende E A existieren.

V non Eine Arbeit kann nicht vor Arbeitsbeginn S A beginnen. Auch ist ein

x i − i

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 Die erste Pausenperiode nach einer Arbeit kann frühestens nach Ab- x ii +

solvierung der Mindestarbeitszeit und einer Mittagspause stattfinden. Zudem kann sie nicht später als das Arbeitsende E A erfolgen.

V non Die Mittagspause kann nicht vor Absolvierung von T pre Arbeitstunden

q ii +

nach Arbeitsbeginn S A erfolgen. Zudem müssen bis zum Arbeitsende E A noch mindestens T post Arbeitsperioden vorhanden sein.

V non Die erste Arbeitsperiode nach einer Mittagspause kann frühestens nach

q i − i

dem Arbeitsbeginn und T pre Arbeitstunden und einer Mittagspause erfolgen. Nach dieser ersten Arbeitsperiode müssen bis zum Arbeitsende E A noch mindestens T post Arbeitsperioden vorhanden sein.

V non Die erste Pausenperiode nach einem Dienst kann nur zur selben Zeit

y ii +

beginnen, wie auch der Dienst selber, da der Dienst einen ganzen Tag dauert.

V non Ein Dienst kann nur in den spezifizierten Knoten V D w beginnen.

y i − i

Die Auswirkung dieser Einschränkung der Variablen auf die Lösungszeit ist deutlich. Kapitel 7 enthält Zeitanalysen, welche diesen Sachverhalt verdeutlichen. 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, beschleunigt die Lösungsdauer. Das Problem des Festsetzens der optimalen Arbeitsschichten wird hierdurch in Tagesprobleme zerlegt, welche durch die Einhaltung der Pausen zwischen den Tagen, der maximalen Wochenarbeitszeit und des Zeitfensters für den Arbeitsbeginn innerhalb einer Woche zusammenhängen.

5.4 Komplexität des RCSPs

Bei der vorliegenden Formulierung als MIP entspricht die Anzahl an Nebenbedingungen und Variablen O(|V |). Das MIP wird mit dem Simplex Verfahren mithilfe eines Branch & Bound (B&B) gelöst. Allgemein gilt, dass Kürzeste 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 ¹⁸ 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

¹⁸ 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 werden.

44

6 Dynamisches Programm

6 Dynamisches Programm

Dieses Kapitel behandelt die Lösung des Schichtplanungsproblems als dynamisches 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 dargelegt. Das vollständige DP befindet sich nochmals in Anhang B. Kapitel 6.4 behandelt eine Möglichkeit, die Lösungsdauer des Algorithmus zu beschleunigen, 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 wirdin Wochenprobleme zerlegt, wobei dies in bestimmten Situationen 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 Problemstellungen aufzuzeigen, für welche die dynamische Programmierung angewandt werden kann.

Diese ist keine eigenständige Lösungsmethode, sondern ein Optimierungs- prinzip. Einekurze Einführung kann in Hans (2001) und Beliën (2006) gefunden 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äutert.

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. Simplexverfahren). 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- grammingoder auch Dynamische Programmierung mit Rückwärts-Induktion bezeichnet. Im Falle der Erzeugung des Schichtplans über eine Woche mit einstü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 ¹⁹ 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 werden, 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 spezifischen Zustand der Stufe j kennzeichnen, so wird im späteren Teil die Notation j mit k ∈ K j verwendet. Die Menge K j beinhaltet hierbei die Indizes aller x k Zustände auf der Stufe j.

Je nach Problemstellung ist die Charakterisierung eines Zustands unterschiedlich. 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 definiert 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öglich sind.

¹⁹ 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. Beispielsweise könnte die Aktion „Fahre weiter“ in einem Wegenetz nicht möglich sein, wenn bereits der ganze Benzinvorrat - welcher den Zustand charakterisiertverbraucht 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 zurü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 optimale 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) ²¹ 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.“

²⁰ Für eine ausführliche Darstellung zur Modellierung und Lösung von Knapsack Problemen

mit der dynamischen Programmierung siehe Kellerer et al. (2004).

²¹ zitiert nach Seinfeld und Lapidus (1968, S. 475).

47

6 Dynamisches Programm

Damit das Optimalitätsprinzip angewendet werden kann, müssen beim Problem, welches mit dynamischer Programmierung gelöst werden soll, zwei Bedingungen erfüllt sein. Diese werden u. a. in Cooper und Cooper (1981, Kapitel 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önnen, wird eine Rekursionsgleichung verwendet, welche eine Verbindung zwischen den kumulierten Erträgen bis zu einer Stufe mit den Erträgen der nächsten Stufen herstellt.

Rekursionsgleichung Mathematisch ausgedrückt ergibt das Optimalitätsprinzip eine Rekursionsgleichung. Diese gibt im Fall der Vorwärts-Induktion für ein Minimierungsproblem die rekursive Folge von Wertfunktionen V (x j ) an. Hierbei 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

unter den Nebenbedingungen

gegeben. Wenn deutlicher ausgedrückt werden soll, dass die Wertfunktionwie im Bellmanschen Optimalitätsprinzip postuliert - nur von den Zuständen x j und Entscheidungen a j abhängt, lässt sich die Gleichung zu

6 Dynamisches Programm

unter den Nebenbedingungen

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 ²² dar und ist daher

auch unter diesem Namen bekannt.

Politik Eine Politik stellt eine Folge a = (a 0 , ..., a n−1 ) von Entscheidungsvariablen 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 ∗ male Politik für DP (x ∗ j ) und x

∗ optimale Politik ist die Folge von Entscheidungen, welche die Wertfunktion optimiert.

Einteilung von Modellen der dynamischen Programmierung Folgende Unterscheidungen können im Allgemeinen bei Modellen der dynamischen Programmierung getroffen werden:

• Je nach Modellierung der Stufen (stetig oder diskret) werden die Modelle in kontinuierliche bzw. diskrete dynamische Programmierung unterteilt.

²² 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.

²³ 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

Die dazugehörige Folge von Zuständen wird durch x ∗ ausgedrückt. Somit ist a ∗

eine optimale Politik für DP (x ∗

6 Dynamisches Programm

• Ist das Resultat der Entscheidungen r j (x j , a j ) mit Unsicherheit verbunden, 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 bekannten 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. Stochastische 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 hierbeiderjenige ist, durch dessen Anwendung die kleinsten reduzierten Kosten entstehen.

Das allgemeine dynamische Programm sieht bei Minimierung der reduzierten Kosten C wie folgt aus.

unter den Nebenbedingungen

Zuerst wird in Kapitel 6.2.1 die dynamische Programmierung auf das vereinfachte Modell angewandt. Das vereinfachte Modell des dynamischen Programms beschränkt sich auf dieselben Nebenbedingungen wie das grundlegende 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 Induktionsreihenfolge 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ösungsmethode für das in Kapitel 4 formulierte RCSP modelliert werden kann. Hierbei 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 Planungshorizont ü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 kennzeichnen. 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.

Jeder Stufe werden Zustände zugewiesen. Jeder Zustand x j auf der Stufe 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, Arbeitund 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} ²⁴ sind im Grundmodell durch Arbeit l (engl. labour ²⁵ ) 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 Entscheidung 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 Zielfunktion 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

· I {l} (a j )) geschrieben. ²⁶ Ob in der Zielfunktion ein weite- j∈{0,...n−1} (−δ dem

j

res −δ dem addiert wird, hängt nur von der Entscheidung a j ab. Diese hängt

j

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 Transformationsfunktion t von keinen weiteren Variablen abhängt. Die Transformationsfunktion und die Rekursionsgleichung für die Schicht- planung werdenin 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 optimalen 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

²⁴ 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.

²⁵ 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.

²⁶ 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) der beste Endzustand, welcher vom