Technical University of Denmark
Department of Management Engineering Anders Dohn
Andrew Mason Jesper Larsen
Demands
A Roster
A Roster‐line
A Roster‐line
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
Roster‐line
A gap between academic research and practice
“… practitioners do not accept academically produced management and computer science solutions to the
nurse‐scheduling problem.”
‐ Kellogg and Walczak
“… very few of the developed approaches are suitable for directly solving difficult real world problems”
‐ Burke et al.
Applicability of the system
• For the system to be useful, we must model the real world problem accurately.
• We cannot change the current operation.
• We must be able to model also individual rules.
• It has to be “easy” to adapt to a new rostering problem.
• Ideally, we only change parameters between different setups.
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.
• Some combinations of on/off days prohibited.
• A minimum rest period after a shift is required.
• Specific shift transitions are not allowed.
• Single days‐on / days‐off are undesirable.
• Each nurse has individual preferences.
• May have shift assignments which a fixed in advance.
Individual rules and agreements
• On all days: at least one of the nurses was also there the day before [BT5].
• Never two consecutive weekends [P1].
• Minimize the number of different shifts in a stretch [P2].
• One week with 60 hours allows only 16 hours the following week [P3].
• If working night shifts, at least to consecutive night shifts must be scheduled [N].
Individual rules and agreements
• If a set of days on ends with a night shift, then the following on‐stretch must not begin early, unless there is a ‘long’ off‐
stretch in‐between [N].
• Nurses have a weekly off day called a zero‐day. For each nurse, it is preferred that zero‐days are always on the same day of the week [P1].
• Special shift type covered by the same employees for a whole week [P3].
6
3 2
Column generation
1 1 1 1 0 0 0 0 = 1 0 0 0 0 1 1 0 0 = 1 0 0 0 0 0 0 1 1 = 1 1 1 0 0 1 1 0 ≥ 2 0 0 1 0 0 0 1 ≥ 1 0 0 1 1 0 0 0 ≥ 1 0 0 0 0 0 1 1 ≥ 1 1 0 0 0 1 0 0 ≥ 1 0 1 1 1 0 0 0 ≥ 1 0 1 0 0 0 0 1 ≥ 1 Nurse 1
Nurse 2 Nurse 3 Shift 1 Shift 2 Shift 3 Shift 4 Shift 5 Shift 6 Shift 7
Master Problem
1
4 5
7
Subproblem
π1 π2
π5 π4 π3
π6 π7 τ1 τ2 τ3
Utilizing the roster‐line structure
• Build on‐stretch from shifts
• Build work‐stretches from on‐stretches and off‐stretches
• Build roster‐lines from work‐stretches
Utilizing the roster‐line structure
L D
N A
L D
N A
L D
N A
L D
N A
L D
N A
L D
N A
L D
N A
L D
N A
L D
N A
L D
N A
L D
N A
L D
N A
D L L N N A
L L L D D A
OFF2 OFF3
OFF4
OFF2 OFF
D L L N N A
D L L N N A
L L L D D A
Work‐stretch 1:
Work‐stretch 2:
Work‐stretch 3:
Work‐stretch 4:
Work‐stretch 5:
Utilizing the roster‐line structure
1
0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Work‐stretches:
Work‐stretches:
D D - - D L - A A - - D L A A - - D -
Oops!
A generic solution algorithm
• Master problem
• Is generic by default
• Subproblem
• Resources are used to represent attributes.
• Solution algorithm is able to handle a number of templates.
• To use for a specific application:
• An expert is needed to setup the framework for each application.
• The core framework is not adjusted.
• A specialized solution package is compiled for the new customer.
• Interaction between master‐ and subproblem is generic.
Preprocessor metaprogramming
Results
• Three setups have been modeled
• We are able to model all constraints.
• The setup for a new problem involves no problem specific coding.
• The setup process is fast.
• Usually data collection is the most time demanding task.
• Solutions
• We are able to find optimal or near‐optimal solutions, but…
• The run times vary dramatically and are prohibitively large.
• The subproblem and branching will be made heuristic to decrease run times.
