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