PowerPoint 簡報
Model & Solution approach
Hospital Staff Scheduling with different experience levels under varied work pattern
Pei-Chun Shih
1
Problem Description
Background: Shift scheduling for Physicians in hospital.
2 types of shifts
Shift o: easy task with longer shift time (12 hrs) 2 working periods (Day, Night)
Shift t: hard task with shorter shift time (8 hrs) 3 working periods (Day, Evening, Night)
2 levels of physicians.
Planning Horizon: 30 days
Each physician can issue 3 requests in the planning horizon, if the request is not met, a penalty cost will be incurred.
(eg. Physician requests “day” period in shift o on day 1.)
2
Schedule Pattern
8am 9 10 11 12 1pm 2 3 4 5 6 7 8 9 10 11 12am 1 2 3 4 5 6 7
Shift type o (easy, 12 hrs)
Day work
Night work
Shift type t (hard, 8 hrs)
8am 9 10 11 12 1pm 2 3 4 5 6 7 8 9 10 11 12am 1 2 3 4 5 6 7
Day work
Night work
Evening work
3
Schedule Example
Department Schedule
Physician A Personal Schedule
Shift type o (easy, 12 hrs)
Shift type t (hard, 8 hrs)
Date/ Work o, Day o, Night t, Day t, Evening t, Night
1 AZ BS CT DU EV
2 FW GX CY HZ BR
3 CY BS AU HZ DW
4 FR DT EY AV GS
5 EU HV BR FX GT
A o, Day o, Night t, Day t, Evening t, Night
1
2
3
4
5
4
Formulation
Sets
E: set of experience levels (Senior & Rookie)
D: set of days in the planning horizon (1~30)
Is: set of senior physicians
Ir: set of rookie physicians
K : type of shifts (o & t)
A : type of works (Day, Evening, Night)
5
Formulation (cont.)
Parameters
: hiring cost of senior physician i with level e
demand of shift k to physician level e in work period a
: max. days for all physicians perform shift k
: min. days for all physicians perform shift k
: penalty cost of senior physician I with level e
: max. consecutive working days
6
Formulation (cont.)
Binary decision variables
: 1, if physician i with level e works on day d with shift type k as work type a. (0, otherwise)
: 1, if the request of physician i with level e on day d with shift type k as work type a is
violated (physician i with level e has to perform other work type on day d)
Objective Function
7
7
Formulation (cont.)
Constraints
For each day, the demand for physicians with level e in each work type that should be met
For each day, each physician can only be assigned to one shift type with one work type.
Day work cannot be followed by Night work
Day work cannot be followed by Evening work
8
Formulation (cont.)
Constraints
For each physician, he/ she should have shift type k
that lower than upper bound. (in days)
For each physician, he/ she should have shift type k
that higher than lower bound. (in days)
For each physician, he/ she should not have consecutive working days more than s. (in days)
9
Solution Procedure
See the model as a set-covering formulation
See the problem as scheduling p working period patterns (columns).
Eg. Shift o Day working period patterns
Column generation
Divide whole problem into master & sub problems
Generate new columns in sub-problems in order to improve master problem
Method for finding new columns in sub-problem: Shorted path problem
Date o, Day
1 AB
2 CD
3 EF
Date o, Day
1 AC
2 DF
3 BE
10
Set covering model- Master Problem
: total cost of column t for working period a
: total number of columns for working period a
=1, if physician i with level e is scheduled in day d in column j for working period a
=1 , if column j was chosen for working period a (0, otherwise)
Min.
Subject to.
Dual price:
Dual price:
11
Sub-Problem
Reduced cost of a new column j for activity a
Min.
s.t.
12
Solve sub-problem as Shortest Path Problem
Purpose: finding better columns (schedules)
Each working period in each day has to be assigned to physicians, while satisfying constraints.
(eg. demanded physicians)
k: number of assignments (arc, with “cost” as value)
d: number of days in planning horizon
T: set of total physicians
Td: set of available physicians for day d
Expression: cost (d|Td) = min. {[cost (d-1|T(d-1)] + cost (d|Td)}
total cost to day d
available physicians
13
Example of “column” in sub-problem
Only “Day” and “Night” working periods per day
Activity: “Day” working period, for 3 days, 3 physicians
Day
work
1
2
3
1
2
3
1
2
3
D1
D2
D3
100€
90€
80€
Physician1 Physician2
Physician3
Day 1
Day 2
Day 3
Total cost of Day work: 240€
14
Example of “column” in sub-problem
Activity: “Night” working period, for 3 days, 3 physicians
Night
work
1
2
3
1
2
3
1
2
3
D1
D2
D3
100€
90€
80€
Physician1 Physician2
Physician3
Day 1
Day 2
Day 3
Total cost of Night work: 280€
15
Example of final schedule
Final schedule
Physician1 Physician2
Physician3
Day 1
Day 2
Day 3
Day work
Night work
Total cost : 240€ + 280€ = 520 €
16
Find out new column
Example: new column for “Night” work
Night
work
1
2
3
1
2
3
1
2
3
D1
D2
D3
100€
90€
80€
Physician1 Physician2
Physician3
Day 1
Day 2
Day 3
Total cost of Night work: 270€
(better than 280 € before )
17
Example of improving master problem
Final schedule
Physician1 Physician2
Physician3
Day 1
Day 2
Day 3
Day work
Night work
Total cost : 240€ + 270€ = 510 €
(better than 520 € before )
18
Case study- Hospital TUM Internal Medicine Dep.
Day (08-16) Evening (16-24) Night (24-08)
Assistant Physician- 5€/hr
(Ward inspection) 3 3 3
Senior Physician- 10€/hr
(Report analyze)
(Ward inspection) 3 3 3
Chief Physician- 15€/hr
(Report analyze)
(Management) 1 1 1
Prolong working hours of “administration” oriented jobs and reduce staffs.
Increase numbers of assist. Physicians to perform “high-demand” jobs in appropriate period.
(3,3,1)
(3,3,1)
(3,3,1)
Assist.
Senior
Chief
Total cost : 1440€
(4,1,0)
(4,1,0)
(3,1,0)
(0,1,1)
(0,1,1)
Total cost : 1280€
19
20
Original mathematic model
Set covering problem
Master problem Get dual value Get min. reduced cost
Solve sub-problem
See sub-problem as shortest path problem
Whenever a better solution is found add into master problem & improve objective function
See min. reduced cost as sub-problem
/docProps/thumbnail.jpeg