Manpower Planning: Rostering Anders Høeg Dohn

Manpower Planning: Rostering Anders Høeg Dohn

Who am I? Anders Høeg Dohn, 29 years old. Cand. Polyt. in 2006 (from DTU). – Applied mathematics with specialization in Operations Research. – Master’s thesis about a practical crew scheduling problem. PhD in Operations Research in 2010 (from DTU). – “Rostering and Task Scheduling – Applications in Manpower Planning” – Supervisors: Jens Clausen and Jesper Larsen. From July 2010: – Operations Analyst at Copenhagen Airports A/S. Board member and treasurer of the Danish Operations Research Society (DORS) – www.dorsnet.dk 2 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Outline of the Remaining Three Lectures Rostering – Introduction to Manpower Planning – What is Rostering? – Solving Rostering Problems with Column Generation Task Scheduling – What is Task Scheduling? – Solving Task Scheduling Problems with Column Generation – Your Assignment Other OR-Problems in Airports – “Being an Operations Analyst in an Airport is like being a kid in a candy store”! – Questioning session on the assignment 3 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Scope During these lectures I will: – Go over some of the practical problems encountered in manpower planning. Rostering Task Scheduling – Propose models that can be used to solve these problems, i.e. present case studies of these methods. Integer Programming Set Partitioning Formulations Column Generation Branch & Price 4 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Motivation for using OR in manpower planning Large savings of structured manpower planning have been documented in the literature. The planning process consists of a number of steps and starts several months before the day of operation. – Each step is an interesting operations research problem, where structured forecasting, simulation and optimization may introduce significantly improved results. In many cases, rostering and task scheduling can be modeled and solved as well defined optimization problems. 5 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Manpower Planning Long term Forecasting / Strategic Planning Mid term Shift generation / Demand estimation 3 months Short term Rostering 1-2 months Real time Task scheduling 1-2 weeks Disruption management Day of operation From: Long term strategic planning To: Disruption management on the day of operation Forecasting / Strategic Planning 6 Shift generation / Demand estimation DTU Management Engineering, Technical University of Denmark Rostering Task scheduling Disruption management Rostering 01/04/23

Manpower Planning Skill E Skill D Skill C Skill B Skill A Monday Forecasting / Strategic Planning 7 Tuesday Shift generation / Demand estimation DTU Management Engineering, Technical University of Denmark Wednesday Thursday Rostering Friday Task scheduling Saturday Sunday Disruption management Rostering 01/04/23

Manpower Planning N1: E1: E2: E3: D1: M1: L1: L2: L3: N2: N3: 04:45 05:00 06:00 06:30 08:00 09:30 13:30 14:30 15:00 18:00 22:30 13:15 13:30 14:30 15:00 16:30 18:00 22:00 23:00 23:30 02:30 07:00 0 13 13 16 14 5 11 10 8 1 2 Forecasting / Strategic Planning 8 Shift generation / Demand estimation DTU Management Engineering, Technical University of Denmark Rostering Task scheduling Disruption management Rostering 01/04/23

Manpower Planning N1: E1: E2: E3: D1: M1: L1: L2: L3: N2: N3: 04:45 05:00 06:00 06:30 08:00 09:30 13:30 14:30 15:00 18:00 22:30 13:15 13:30 14:30 15:00 16:30 18:00 22:00 23:00 23:30 02:30 07:00 0 13 13 16 14 5 11 10 8 1 2 Forecasting / Strategic Planning 9 Emplo yee 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Mon 06aug L3 L2 L2 L2 D1 D1 L3 D1 L3 D1 D1 D1 L2 L2 L2 E1 E1 E1 E3 E3 Shift generation / Demand estimation DTU Management Engineering, Technical University of Denmark Tue 07aug L3 L3 L2 L2 E3 E3 L3 E2 L3 E3 E1 E1 L2 L3 L2 E1 E1 E1 E3 E3 Wed 08aug L2 L3 L1 L1 E1 E1 M1 N1 N2 E3 E3 E3 M1 L1 N2 E1 E1 E1 E3 E3 Thu 09aug M1 L3 D1 D1 E2 E2 E1 E1 L2 E3 E3 E3 E1 D1 L2 E3 E3 E3 E1 E1 Rostering Fri 10aug E2 M1 E3 E3 E2 E2 E1 E3 L1 E3 E3 E3 E3 E3 L3 - Sat 11aug - Sun 12aug - Mon 13aug E1 E1 E1 L2 L2 Tue 14aug L3 L3 L3 L3 L2 L2 L3 L3 L3 L3 L3 L3 L2 L3 L2 E2 E2 E2 L2 L2 Task scheduling Wed 15aug L3 L3 L2 L2 L1 L1 L2 L3 L3 M1 L2 L2 M1 M1 L1 E2 E2 E2 L2 L2 Thu 16aug L3 L3 L2 L2 L2 L2 L2 L2 L3 E2 M1 M1 E3 E1 L1 E3 E3 E3 M1 M1 Fri 17aug L2 L1 L2 L2 L3 L3 L2 L3 L3 E3 E3 E3 E3 E2 D1 E3 E3 E3 E1 E1 Sat 18aug M1 M1 M1 M1 L1 L1 L2 M1 M1 E3 E2 E2 E1 E3 E3 E1 E1 E1 E3 E3 Sun 19aug E2 E3 E2 E2 D1 D1 L3 E3 E2 E3 E1 E1 E1 E3 E2 - Disruption management Rostering 01/04/23

Manpower Planning Forecasting / Strategic Planning 10 Shift generation / Demand estimation DTU Management Engineering, Technical University of Denmark Rostering Task scheduling Disruption management Rostering 01/04/23

Manpower Planning Empl oyee 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Mon Tue Wed Thu Fri Sat Sun Mon Tue Wed Thu Fri Sat Sun 06aug L3 L2 L2 L2 D1 D1 L3 D1 L3 D1 D1 D1 L2 L2 L2 E1 E1 E1 E3 E3 10aug E2 M1 E3 E3 E2 E2 E1 E3 L1 E3 E3 E3 E3 E3 L3 - 11aug - 12aug - 17aug L2 L1 L2 L2 L3 L3 L2 L3 L3 E3 E3 E3 E3 E2 D1 E3 E3 E3 E1 E1 18aug M1 M1 M1 M1 L1 L1 L2 M1 M1 E3 E2 E2 E1 E3 E3 E1 E1 E1 E3 E3 19aug E2 E3 E2 E2 D1 D1 L3 E3 E2 E3 E1 E1 E1 E3 E2 - 07aug L3 L3 L2 L2 E3 E3 L3 E2 L3 E3 E1 E1 L2 L3 L2 E1 E1 E1 E3 E3 08aug L2 L3 L1 L1 E1 E1 M1 N1 N2 E3 E3 E3 M1 L1 N2 E1 E1 E1 E3 E3 09aug M1 L3 D1 D1 E2 E2 E1 E1 L2 E3 E3 E3 E1 D1 L2 E3 E3 E3 E1 E1 Forecasting / Strategic Planning 11 13aug E1 E1 E1 L2 L2 14aug L3 L3 L3 L3 L2 L2 L3 L3 L3 L3 L3 L3 L2 L3 L2 E2 E2 E2 L2 L2 15aug L3 L3 L2 L2 L1 L1 L2 L3 L3 M1 L2 L2 M1 M1 L1 E2 E2 E2 L2 L2 16aug L3 L3 L2 L2 L2 L2 L2 L2 L3 E2 M1 M1 E3 E1 L1 E3 E3 E3 M1 M1 Shift generation / Demand estimation DTU Management Engineering, Technical University of Denmark Rostering Task scheduling Disruption management Rostering 01/04/23

Rostering Long term Forecasting / Strategic Planning Mid term Shift generation / Demand estimation 3 months 1-2 months Short term Rostering 1-2 weeks Real time Task scheduling Disruption management Day of operation Allocate employees to shifts Assuming that: – Shift demands exist – The staff is fixed – We don’t specify tasks during shifts 12 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Some general characteristics Fixed planning period. Fixed number of shifts. Time norm for each employee. Maximum number of days on in a week / on-stretch. A minimum rest period after a shift is required. Specific shift transitions are not allowed. Each employee may have individual preferences. 13 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Demands 14 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

A Roster 15 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

A Roster-line 16 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

17 DTU Management Engineering, Technical University of Denmark Rostering Shift Shift Shift Shift Shift Shift Shift Shift Shift Shift Shift Shift Shift Shift Shift Shift Shift On-stretch Off-stretch On-stretch Off-stretch On-stretch Off-stretch On-stretch Off-stretch On-stretch Work-stretch Work-stretch Work-stretch Work-stretch Work-stretch A Roster-line Roster-line 01/04/23

A generalized set partitioning formulation Model the problem as that of choosing the best feasible roster-line for each employee. – Meet the demands as well as possible with these roster-lines. A multi-objective problem – Meet demands – Maximize satisfaction – Minimize costs A subproblem generates the feasible roster-lines. – All rules concerning a single employee are handled in the subproblem. 18 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Branch & Price Necessary considerations: – How do we model and solve the master problem? – How do we model and solve the subproblem? – How do we ensure integrality in the master problem? 19 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

A generalized set partitioning formulation 20 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

A generalized set partitioning formulation The number of variables is HUGE. – Any legal combination of shifts constitutes a variable. – It is impossible to generate all varibles a priori. – Therefore, solving the model using column generation is a natural choice. Column generation is used directly on the generalized set partitioning formulation. – We are not decomposing a compact formulation. – The compact model can be “reverse engineered”, but it is not easy and the model usually isn’t very nice, anyway. 21 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Branch & Price Necessary considerations: – How do we model and solve the master problem? – How do we model and solve the subproblem? – How do we ensure integrality in the master problem? 22 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Column generation Master Problem Subproblem Nurse 1 1 1 1 1 0 0 0 0 1 τ1 Nurse 2 0 0 0 0 1 1 0 0 1 τ2 Nurse 3 0 0 0 0 0 0 1 1 1 τ3 Shift 1 1 1 0 0 1 1 0 2 π1 Shift 2 0 0 1 0 0 0 1 1 π2 Shift 3 0 0 1 1 0 0 0 1 π3 Shift 4 0 0 0 0 0 1 1 1 π4 Shift 5 1 0 0 0 1 0 0 1 π5 Shift 6 0 1 1 1 0 0 0 1 π6 Shift 7 0 1 0 0 0 0 1 1 π7 min cer d xd e d D 5 1 6 4 7 2 3 1 0 0 1 0 0 1 23 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Column Generation – Overview Solve current restricted master problem. Solve pricing problem (Column generation). Add routes to restricted master problem. Found route with negative reduced cost? Yes No 24 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Column generation Solve an LP-relaxation of the problem. One subproblem for each employee – The subproblems can be solved independently, in parallel or sequentially. – To terminate column generation, all subproblems must be unable to return new columns. – The subproblem can be solved as a Resource Constrained Shortest Path Problem. 25 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Dynamic Programming Resources – Anything that can affect feasibility or cost of a label must be considered when dominating labels. – Such measures are represented by resources. Domination – For each resource, we must specify what a “better” value is. – Domination must consider both feasibility and cost. – Sometimes, it is not better to have neither a smaller nor a larger value. Then domination only applies if values are equal. – All resources must allow domination (and cost must be lower) for one label to dominate another. 26 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Dynamic Programming s 27 D D D D D D D D D D D D L L L L L L L L L L L L A A A A A A A A A A A A N N N N N N N N N N N N O O O O O O O O O O O O D L L N N A O O O O L L DTU Management Engineering, Technical University of Denmark Rostering e 01/04/23

l (cost, hours, nightshifts) Dynamic Programming l1 (-3, 16, 0) -1 l2 (-2, 16, 0) -1 l3 D(-4, 16, D 2) D D D D D D D L L L L L L L L D D D L L L L -2 s A A A A A A A A A A A A N N N N N N N N N N N N -2 -2 O O O O O O O O O O O O e Assume that we have two resources: number of worked hours and number of night shifts. Assume that both D, L and N have a length of 8 hours. Is it better to have a smaller/larger number of hours? 28 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

l (cost, hours, nightshifts) Dynamic Programming l1 (-3, 16, 0) -1 l2 (-2, 16, 0) -1 l3 D(-4, 16, D 2) D D D D D D D L L L L L L L L D D D L L L L -2 s A A A A A A A A A A A A N N N N N N N N N N N N -2 -2 O O O O O O O O O O O O e l3 does not dominate l1 because it has a larger number of night shifts. – Assuming that lower is better. – Why is lower better? Must be defined in the individual case for each of the resources. – 29 Due to feasibility Due to costs which depend on resource values What if it is the other way around? DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Utilizing the roster-line structure Combine shifts into on-stretches Combine on-stretches and off-stretches into work-stretches Combine work-stretches into roster-lines Use dynamic programming to find only the non-dominated entities in each step. 30 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Utilizing the roster-line structure D D D D D D D D D D D D L L L L L L L L L L L L A A A A A A A A A A A A N N N N N N N N N N N N Work-stretch 1: D L L N N A OFF2 Work-stretch 2: D L L N N A Work-stretch 3: D L L N N A Work-stretch 4: L L L D D A OFF2 Work-stretch 5: L L L D D A Work-stretch 6: L L L D D A 31 DTU Management Engineering, Technical University of Denmark OFF3 OFF4 OFF3 OFF4 Rostering 01/04/23

Utilizing the roster-line structure Work-stretches: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 - D L - A A Work-stretches: D D 32 - DTU Management Engineering, Technical University of Denmark - - D L A A - Rostering - D - 01/04/23

An optimal LP-solution 33 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Branch & Price Necessary considerations: – How do we model and solve the master problem? – How do we model and solve the subproblem? – How do we ensure integrality in the master problem? 34 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Branch & Price – Overview Solve current restricted master problem. Solve pricing problem (Column generation). Add routes to restricted master problem. Found route with negative reduced cost? Yes No 35 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Branch & Price – Overview When all nodes in tree have been fathomed / discarded Choose next node in branching tree. Solve current restricted master problem. Solve pricing problem (Column generation). Add routes to restricted master problem. Found route with negative reduced cost? Yes No Is lower bound less than incumbent? No Fathom current node. 36 DTU Management Engineering, Technical University of Denmark Yes Yes Is the solution feasible? No No Branch and add new nodes to tree. Update incumbent and discard current node. Rostering 01/04/23

Branching Variable branching is usually not a possibility in column generation. – How do you prohibit a variable from reappearing? Branch on a fractional shift allocation. When all shift allocations are integer the full master problem solution is integer. – As the constraint matrix for each employee is a perfect matrix. – For more on this: Follow the course “42122 The Set Partitioning Optimization Model and its Application in Practical Scheduling Problems”. 37 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Branching 38 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Branch & Price Necessary considerations: – How do we model and solve the master problem? – How do we model and solve the subproblem? – How do we ensure integrality in the master problem? Other considerations: – Master problem Solve it to optimality every time? Use dual stabilization? – Subproblem Use heuristics? In what order should the individual subproblems be solved? – Branching How do we search the branch-and-bound tree? 39 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Searching the Branch-and-Bound Tree Best first lb 1 – Theoretically the most efficient Depth first – Works very well in practice for lb 2 lb 3 lb 3 lb 3 rostering problems. – Efficient because many nodes have the same lower bound. ub 3 ub 1 – Often, a solution exists in the bottom of the tree with solution value equal to the lower bound. 40 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Branch & Price Necessary considerations: – How do we model and solve the master problem? – How do we model and solve the subproblem? – How do we ensure integrality in the master problem? Other considerations: – Master problem Solve it to optimality every time? Use dual stabilization? – Subproblem Use heuristics? In what order should the individual subproblems be solved? – Branching How do we search the branch-and-bound tree? 41 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

An optimal solution 2 10 10-7 3 2 2 2 2 10 10-7 13 42 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

An optimal solution: slack / surplus 43 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Rotation Patterns Some companies use rotation patterns. – Because that is how they have always done it. – Because they are easier to create and maintain manually. – Because they are easier to discuss with unions and managers. Rotation patterns are more restrictive than individual roster-lines. – Hence, less desirable from an optimization point of view. Monday Tuesday Wednesday Thursday Friday Saturday Sunday Employee 1 D D - - A N - Employee 2 L A L D D - - Employee 3 N - D D L L L Employee 4 - - - L N - - Total D, L, N D, A D, L 2 x D, L D, L, A, N L, N L 44 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Rotation Patterns We can no longer create an individual roster-line for each employee. Several employees share one rotation. – The rotation can be generated by solving the subproblem from before with some modifications. The pattern must have a feasible wrap. – Demands are given for each weekday (not for each calendar day). – Each rotation contributes with several shifts for each day in the roster. Works badly when individual skills are important and when we have varying demands on each individual day. Monday Tuesday Wednesday Thursday Friday Saturday Sunday Employee 1 D D - - A N - Employee 2 L A L D D - - Employee 3 N - D D L L L Employee 4 - - - L N - - Total D, L, N D, A D, L 2 x D, L D, L, A, N L, N L 45 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23

Summary What you should be able to remember from this lecture: – Manpower planning consists of several steps Each is an interesting optimization problem in its own right. – Rostering The practical problem The set partitioning formulation Characteristics and variations – Cost structure – Rotations – Solution method Column generation Dynamic programming Branching strategy and tree search strategy 46 DTU Management Engineering, Technical University of Denmark Rostering 01/04/23