Flexible Shift Planning in the Service Industry (eBook)

Contents 6
List of Figures 8
1 Introduction 10
1.1 General Economic Situation in Hospitals 10
1.2 Complexity of Physician Scheduling 10
1.3 Topic of This Research 11
1.4 Outline 12
2 Literature Review on Personnel Scheduling 14
2.1 General Personnel Scheduling 14
2.2 Physician Scheduling 17
2.3 Implicit Shift Modeling 18
2.4 Column Generation and B& P
3 MIP Model for Flexible Shift Scheduling of Physicians 22
3.1 Basic MIP Model 22
3.1.1 Model Description 22
3.1.1.1 Hard Constraints 23
3.1.1.2 Soft Constraints 23
3.1.2 Model Formulation 26
3.2 Model Enhancements 32
3.2.1 On-Call Services 32
3.2.2 Time Window Restrictions 36
3.2.3 Break Assignment 37
3.2.3.1 Break Placement After a Predefined Time Span 37
3.2.3.2 Implicit Break Placement in a Defined Time Interval 38
3.2.3.3 Break Placements When Short Shifts are Considered 40
3.2.4 Holidays and Vacations 41
3.3 Case Study: Anesthetist Scheduling 43
3.3.1 Current Practice 43
3.3.2 Solution of the Model 44
4 Solution Methodologies 47
4.1 Preprocessing 47
4.2 Heuristic Decomposition Strategy 49
4.3 Column Generation and B& P Algorithm
4.3.1 Master Problem Formulation 54
4.3.2 Subproblem Formulation 57
4.3.3 Finding Integer Solutions 62
4.3.4 Branching on MP Variables (MPVarB) 63
4.3.5 Branching on SP Variables (SPVarB) 66
4.3.6 A Dual Point of View 69
4.3.6.1 Dual Space by MPVarB 69
4.3.6.2 Dual Space by SPVarB 70
4.3.7 Heuristics for the B& P Algorithm
4.3.7.1 Initialization Heuristic 71
4.3.7.2 Feasibility Heuristic to Find Integer Solutions 72
4.3.7.3 Rounding Heuristic to Find Integer Solutions 74
4.3.8 Enhancements for the B& P Algorithm
4.3.8.1 Lower Bounds and Early Termination 75
4.3.8.2 Aggregation of Subproblems 78
5 Experimental Investigations 81
5.1 Input Data From MRI 81
5.1.1 Demand Profiles 82
5.1.2 Basic Parameter Settings 87
5.2 Heuristic Decomposition 88
5.2.1 Analysis of Different Model Features 90
5.2.2 Parametric Analysis 92
5.2.2.1 Maximum Shift Length 92
5.2.2.2 Time Window Length 93
5.2.2.3 Number of Physicians 93
5.2.3 Analysis of Instances of Different Sites 94
5.3 B& P Algorithm
5.3.1 Two-Week Problems 100
5.3.2 Four-Week Problems 101
5.3.3 Six-Week Problems 101
5.3.4 General Observations 102
5.4 Comparison of Both Algorithms 102
6 Conclusions and Further Remarks 106
6.1 Summary and Conclusions 106
6.2 Final Remarks and Further Research Directions 108
Appendix 109
A.1 Abbreviations, Notation, and Symbols 109
Bibliography 116