代写FIT5216: Modelling Discrete Optimization Problems Assignment 2代做Python编程
- 首页 >> Matlab编程FIT5216: Modelling Discrete Optimization Problems
Assignment 2: Nurse Rostering
1 Overview
For this assignment, your task is to write a MiniZinc model for a given problem specification.
. Submit your work to the MiniZinc auto grading system (using the submit button in the MiniZinc IDE).
. Submit your model (copy and paste the contents of the .mzn file) and report using the Moodle assignment.
You have to submit by the due date (26th April 2024, 11:55pm), using MiniZinc and using the Moodle assignment, to receive full marks. You can submit as often as you want before the due date. Late submissions without special consideration receive a penalty of 10% of the available marks per day. Submissions are not accepted more than 7 days after the original deadline.
This is an individual assignment. Your submission has to be entirely your own work. We will use similarity detection software to detect any attempt at collusion, and the penalties are quite harsh. You may not use large langauge models for any part of this assignment. If in doubt, contact your teaching team with any questions!
2 Problem Statement
Your task is manage the roster a busy hospital
There are 5 kinds of shifts in the roster:
MORN the person works in the morning shift
DAY the person works on the day shift
EVEN the person works on the evening shift
NIGH the person works on the night shift
OFF the person has the day off
Your aim is to build a roster over a give number of days for a set of nurses, that satifies various constraints, about shift sequence, that has enough people available for each shift type. You must also assign nurses to wards, and satisfy constraints about wards assigned.
Input data is given in MiniZinc data format:
NURSE = ⟨ The set of people to roster ⟩;
nday = ⟨ The number of days to roster for ⟩;
rostered off = ⟨ For each nurse and day have they been already granted a day off ⟩;
maxweek = ⟨ The maximum work shifts allowed in any 7 day period ⟩;
maxnightfort = ⟨ The maximum number of NIGH shifts allowed in any 14 day period ⟩;
minfort = ⟨ The minimum work shifts allowed in any 14 day period ⟩;
minshift = ⟨ For each shift and day the minimum nurses rostered to each shift ⟩; shift cost = ⟨ The cost for rostering on each nurse for one day ⟩;
WARD = ⟨ The set of wards to assign ⟩;
dummy = ⟨ The ward representing a dummy (no ward) assignment ⟩;
minward = ⟨ For each ward and day the minimum nurses rostered to each ward ⟩; maxward = ⟨ The maximum wards any nurse can staff in the roster period ⟩;
SKILL = ⟨ The set of advanced skills nurses may have ⟩;
skill = ⟨ For each nurse the set of advanced skills they have ⟩;
desired = ⟨ For each ward the advanced skills they want ⟩;
emergency = ⟨ Which ward is the emergency ward if there is one ⟩;
Note that the emergency data can be omitted meaning there is no emergency department in the roster problem.
Here is a sample data set (given in nroster00.dzn):
NURSE = { A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P };
nday = 14;
rostered_off = [| true, false, false, false, false, false, false,
true, false, false, false, false, false, false
| . . too big to show . . |];
maxweek = 5;
minfort = 8;
maxnightfort = 4;
minshift = [| 1, 3, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1
| 2, 2, 6, 2, 4, 3, 6, 2, 6, 2, 2, 4, 3, 2
| 1, 5, 3, 2, 1, 2, 1, 3, 1, 1, 2, 1, 2, 1
| 2, 2, 2, 2, 6, 2, 2, 4, 2, 2, 5, 4, 4, 2
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
|];
shift_cost = [ 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 10, 10 ];
WARD = { GEN, EME, HRT, CAN, ’.’ };
dummy = ’.’;
minward = [| 2, 5, 2, 5, 0, 0, 2, 2, 5, 2, 5, 0, 0, 2
| 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 2, 2, 4, 4
| 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1
| 1, 1, 5, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1
| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
|];
maxward = 2;
SKILL = { SENIOR, EMERG, CARDIO, RADIO };
senior = SENIOR;
skill = [ {}, {}, {}, {}, {}, {}, {EMERG}, {EMERG}, {CARDIO}, {RADIO}, {SENIOR},
{SENIOR}, {EMERG,CARDIO}, {EMERG,RADIO}, {EMERG, SENIOR}, {CARDIO, SENIOR} ];
desired = [ {}, { EMERG }, { CARDIO }, {RADIO}, {} ];
emergency = EME;
This data requires building a roster for 16 employees over 14 days.
The decisions of the roster are
array[NURSE,DAYS] of var SHIFT: sh; % shift for each nurse on each day array[NURSE,DAYS] of var WARD: wd; % ward rostered for each nurse
var int: total_cost; % the total cost of the roster
The assignment is in stages, please attempt them in order. Note that if you do not complete all stages you cannot get full marks.
Stage A - Basic Rostering
Create a model nroster.mzn that takes data in the format specified above and decides on shifts for each person. For Stages A – C you can just set the wd to dummy for all nurses. For Stages A – B you can just set total cost to 0 .
For stage A we just need to ensure we make acceptable roster schedules for each nurse.
A1 First we need to ensure that every nurse is rostered OFF for each day where rostered off is true.
A2 Next we need to ensure that the model decides on shifts for each person that satisfy the shift regulation constraints, which are:
. No nurse works more than 3 NIGH shifts in a row
. No nurse works a MORN shift directly after a NIGH shift
. No nurse works a DAY shift directly after a NIGH shift
. No nurse works a MORN shift directly after an EVEN shift
. No nurse has more than 2 OFF shifts in a row
. No nurse that works a DAY shift has less than 2 DAY shifts in a row (except the last shift can be a lone DAY shift)
A possible sh solution for the data above to stage A is:
A: . E E E E E N . E E N E E D
B: M . E E E E E . . E E E E D
C: D D . E E E . M M . E E E D
D: E N N . E E E E D D . E E D
E: E E E . . E E E E E . . E D
F: E E E E N . E E E E . M . M
G: E E E E . M . E E E E . M .
H: . E E E N . M . E E E D D .
I: M . E E E E E . . N . E E D
J: E N . N . E E E E . E E E D
K: E E N . E E E E E N . . E D
L: E E E . . D D . E N N . E D
M: . E E E N . E E E E E E . M
N: E E E E . M . N . E E N N .
O: . E E N E E E E E E E N N .
P: M . E E E E E E E E E N . .
Where M = MORN, D = DAY, E = EVEN, N = NIGH and . = OFF. Note how the days off for nurse A align with where they are rostered off (days 1 and 8). No nurse roster violates any of the constraints, e.g. we dont see three days OFF in a row, or less than two DAY shifts in a row, except on the last day.
Note there are global constraints that can create very efficient models for this stage.
Stage B - Minimum Rostering Levels
Clearly the schedule above has many EVEN shifts. This is because without making sure each shift has enough people on it we get silly solutions.
B1 In this stage we need to ensure that each SHIFT types for each day d has at least minshift[s ,d] nurses rostered to it.
B2 We also need to enforce long term constraints on the shift sequences of nurses:
. No nurse works more than maxweek shifts (shifts other than OFF) in any 7 day period.
. No nurse works less than minfort shifts in any 14 day period.
. No nurse works more than maxnightfort NIGH shifts in any 14 day period.
Use global constraints where possible to encode these constraints.
A possible sh solution for the data above to stage A is:
B: E E N N . E . N N . E E : 9
C: E E . M M . D D D . D D . N : 10
D: M M N . N . D D D D D M : 10
E: N E D D . M . E D D N . M . : 10
F: M N . N N . E . D D D M . D : 10
G: D D D . N N . D D . E D D . : 10
H: . M . M E D D . N . N N N . : 9
I: M . M . D D D N . M . N E N : 10
J: M M . N . E D D M . N . N E : 10
K: N N E . M M . M D D M M : 10
L: D D D E N . M E E . M D : 10
M: . E N . N . M N E . E N : 8
O: . E E . N E . E N E . N N . : 9
P: D D D . N N . N N E . . : 8
MORN: 4 3 1 2 2 2 1 1 2 2 2 2 3 3
DAY: 2 3 6 3 4 3 6 4 6 3 2 4 3 2
EVEN: 1 5 3 2 1 2 1 3 2 2 3 1 2 2
NIGH: 2 2 2 2 6 2 2 4 2 2 5 4 4 2
OFF: 7 3 4 7 3 7 6 4 4 7 4 5 4 7
Where now we show the number of working shifts in the 14 day period for each nurse on the right. Note how in each 7 day period no nurse works more than 5 shifts, and no one works less than 8 shifts in the full 14 day roster. No nurse works more than 4 NIGH shifts over the 14 day roster.
The number of nurses on each shift for each day is shown below the roster. Note how each reaches the min required by minshift.
Stage C - Optimising Cost
Now we need to calculate the total shift cost, and minimize it. For every shift when a nurse is rostered on (not OFF) we need to pay the shift cost for that nurse given by shift cost . The total cost for the roster above is 484. But we can do better. Compute the total cost of the roster in variable total cost and minimize it .
Here is an optimal solution for Stages A – C. Note that the total cost is substantially reduced
B: N . N . E D D E E D D M : 10
C: E N . E N N . E N . E D D . : 10
D: N N E . N E . M N E . D D . : 10
E: . D D E D D D . M . M D : 9
F: D D D . N . D D D . N E : 9
G: . E D D N N E . . M N . : 8
H: . M D D D N M . D D . . : 8
I: M . D D D N . N . M E . : 8
J: . E . N D D D . N . E D : 8
K: . E E . N . E E . N M N : 8
L: . E N E . M N . M . N E : 8
M: . M . M M . N . D D D N : 8
N: D D D . M M . N . M N . : 8
O: . E D D D N . . N N N . : 8
P: M . E N N D D . N N . . : 8
MORN: 1 3 1 1 2 2 1 1 2 1 1 2 2 1
DAY: 2 3 6 3 4 3 6 4 6 2 2 4 3 2
EVEN: 1 5 3 2 1 2 1 3 1 1 2 1 2 1
NIGH: 2 2 2 2 6 2 2 4 2 2 5 4 4 2
OFF: 10 3 4 8 3 7 6 4 5 10 6 5 5 10
total_cost = 436;
Stage D - Ward Constraints
Each nurse that is rostered on has to be assigned to a WARD where their principal responsibilities lie. We have minimum staffing requirements for each ward on each day. Now you must decide the wd assignment of each nurse on each day to each ward. First for consistency we require that any nurse that is rostered OFF should be assigned to the dummy ward and vice versa. Note these constraints should always be turned on in stage F.
You model should satisfy the following ward constraints:
D1 For each ward w and each day d at least minward[w ,d] nurses should be assigned to that ward.
D2 There is one more restriction on ward assignments: No nurse can be assigned to more than maxward different wards (including the dummy ward) over the roster period.
Again use global constraints where possible to encode the constraints.
A solution that satisfies these constraints is:
B: N N E D D N . . D D M M : 10
C: N N . M M M . M M . N N . M : 10
D: D D D . N N . E D D N E : 10
E: D D D E M N E . E . N N : 10
F: . E E . N . D D D . N E . N : 9
G: . M D D D N D D N N . . : 9
H: . N N E N . N . D D M . : 8
I: N . M M . E . N . D D M : 8
J: M E . N D D D . . D D . : 8
K: . M M . D D D . N N E . : 8
L: N E . D D . D D N . N . : 8
M: . E D D N N . E . N . D : 8
N: . M D D D N . . M M N . : 8
O: . E E . N . D D D . E . E . : 8
P: E . E . N E E E N N . . : 8
MORN: 1 3 1 1 2 2 1 1 2 1 1 2 2 3
DAY: 2 2 6 4 4 3 6 3 6 3 2 4 3 2
EVEN: 1 5 3 2 1 2 1 3 1 1 2 1 2 1
NIGH: 2 2 2 2 6 2 2 4 2 2 5 4 4 2
OFF: 10 4 4 7 3 7 6 5 5 9 6 5 5 8
total_cost = 440;
A: . EME EME EME EME . EME . EME EME . EME EME EME
B: GEN . . GEN EME EME EME GEN . . GEN EME GEN GEN
C: EME GEN . GEN EME EME . GEN GEN . GEN EME . EME
D: EME GEN GEN . GEN EME . GEN GEN GEN . . GEN EME
E: GEN GEN GEN GEN . . GEN EME GEN . GEN . GEN GEN
F: . GEN CAN . GEN . GEN GEN GEN . GEN GEN . CAN
G: . GEN GEN GEN GEN CAN . . GEN CAN GEN CAN . .
H: . GEN . . EME EME EME . GEN . EME EME EME .
I: . . EME . EME EME . EME . EME . EME EME EME
J: CAN GEN . GEN . . GEN GEN GEN . . GEN GEN .
K: . GEN GEN . GEN GEN GEN . GEN GEN . . GEN .
L: . . CAN HRT . CAN CAN . CAN HRT HRT . HRT .
M: . HRT CAN CAN CAN . . HRT . HRT . CAN . HRT
N: . EME CAN EME CAN . . EME . . EME EME EME .
O: . CAN CAN . EME . EME CAN EME . CAN . CAN .
P: HRT . HRT . HRT HRT HRT HRT . . HRT HRT . .
GEN: 2 8 4 5 4 1 4 5 8 2 5 2 5 2
EME: 2 2 2 2 6 5 4 3 2 2 2 6 4 4
HRT: 1 1 1 1 1 1 1 2 0 2 2 1 1 1
CAN: 1 1 5 1 2 2 1 1 1 1 1 2 1 1
.: 10 4 4 7 3 7 6 5 5 9 6 5 5 8
Here we can see the ward allocations for each nurse and each day. Note how the dummy ward ’ . ’ lines up with days OFF exactly. The minimum ward allocations for each ward and day are satisfied. No nurse is assigned to more than two wards over the period.