consecutive shifts constrains
Answered
Hi, i have a schedule problem in which i need to assign consecutive shift:
if nurse "Telly" is assigned to day 3, she must work on "multis" consecutive days. 3,3+1,3+2,...,3+multis-1.
I need to build a general constraint to capture this for all nurses.
here is my code:
numday = 15
num_nurses = ["a","b","c","Telly","e"]
multis = 3
m = Model('nsp')
x = m.addVars(num_nurses,range(numday), vtype=GRB.BINARY,name='x')
m.setObjective(quicksum(x[i,j] for i in num_nurses for j in range(numday) ),GRB.MAXIMIZE)
#every day must be assigned exclusively to one nurse
m.addConstrs(quicksum(x[i,j] for i in num_nurses) == 1 for j in range(numday))
#every nurse need approximately a mean quantity of assigned days
m.addConstrs(quicksum(x[i,j] for j in range(numday)) >= trunc(numday/len(num_nurses)) for i in num_nurses)
m.addConstrs(quicksum(x[i,j] for j in range(numday)) <= trunc((numday/len(num_nurses))+1) for i in num_nurses)
# shift are assigned in consecutive "multis" group of days
r = m.addVars(num_nurses,range(numday-multis+1), vtype=GRB.BINARY,name='r')
m.addConstrs(quicksum(r[i,j] for i in num_nurses)==1 for j in range(numday-multis+1))
m.addConstrs(quicksum(x[i,k] for k in range(j,j+multis)) == (multis*r[i,j]) for j in range(numday-multis+1) for i in num_nurses)
I have tried building a constrain with binary slack to reflect the that if that slack is on, then the shift is assigned to a nurse, and the consecutive days are assigned too. then the scheduler must assign the rest of days to the other nurses.
Using this, the model is infeasible.
Could you help me please? what am i doing wrong?
-
I forgot to add: all nurses have to work just in three days consecutive (our shift are by days). One day shift and 2 days shift nurses are treated separately
0 -
Hi Bernardo,
Have you thought about changing the definition of your binary variables? Instead of using "x[i,j] = 1 if nurse i works shift j", you could use "x[i,j] = 1 if nurse i works starts a 3 shift sequence with shift j".
You would have to change the definition of your constraints to match, but this is the approach that immediately comes to my mind.
- Riley
0 -
Hello Riley, thanks for your response.
How can i build that variable definition? I am not sure, how to put "start a 3 shift sequence" in my var definition.
And i want to ask you: if i decided to put in one model nurses with 3 day shift and nurses with one day shift? How could i build the constrains?
0 -
Hi Bernardo,
How can i build that variable definition? I am not sure, how to put "start a 3 shift sequence" in my var definition.
You won't have to change the variable definition in gurobipy, other than perhaps not needing as many for the later shifts. It is your interpretation of what the variables mean that changes. See below for example.
from gurobipy import *
numday = 15
num_nurses = ["a","b","c","Telly","e"]
multis = 3
m = Model('nsp')
x = m.addVars(num_nurses,range(numday), vtype=GRB.BINARY,name='x')
# Don't allow nurses to start a 3-day shift that goes past day 15.
# We do this by setting the upper bound to zero on these variables.
m.setAttr("UB", x.select("*", range(numday-multis+1, numday)), 0)
# I've commented the objective out, as it doesn't make much sense to me.
#m.setObjective(quicksum(x[i,j] for i in num_nurses for j in range(numday) ),GRB.MAXIMIZE)
#every day must be assigned exclusively to one nurse
# for every day we count the 3-day shifts that started on that day, but also the
# day before, and the day before (when multis=3)
m.addConstrs(
quicksum(x.get((i,k),0) for i in num_nurses for k in range(j-multis+1, j+1)) == 1
for j in range(numday)
)
#every nurse need approximately a mean quantity of assigned days
m.addConstrs(multis*quicksum(x[i,j] for j in range(numday)) >= int(numday/len(num_nurses)) for i in num_nurses)
m.addConstrs(multis*quicksum(x[i,j] for j in range(numday)) <= int((numday/len(num_nurses))+1) for i in num_nurses)Note that your "mean quantity" constraints will only work if the number of days is divisible by multis multiplied by the number of nurses. As such I expect this is not what you want. If you're trying to spread the work out evenly, then you could introduce variables for the minimum, and maximum, of the amount of x variables = 1 for any nurse, and then make sure that these min and max variables have value at most 1 apart.
If you want to allow the "multis" number to be nurse dependent then you will need to make some tweaks - for starters multis should become a dictionary, indexed by the nurses.
- Riley
0 -
Thanks!
My objective function doesn't make sense with the actual constrains, but i have an additional constrains (nurses vacations and spaces between shifts) that makes me want maximize the days scheduled as objective.
Now i understand what you mean with the interpretation of the variables, thanks for the explanation.
About this: "If you want to allow the "multis" number to be nurse dependent then you will need to make some tweaks - for starters multis should become a dictionary, indexed by the nurses."
Yes, this is exactly what i want, including an additional constrain about the minimum quantity of days that a nurse should wait for their next shift.
Thinking in your response, it could be something like this:
#first element in the list is the multis number,
#and the second is the amount of days that nurse must wait to her next assignment
multis = { "a":[1,3],"b":[1,3],"c":[3,6],"Telly":[4,8],"e":[2,5]] }
#this is would be my new constrain for multis
m.addConstrs(
quicksum(x.get((i,k),0) for i in num_nurses for k in range(j-multis[i][0]+1, j+1)) == multis[i][0]
for j in range(numday)
)
#this is would be my new constrain for spacing between shifts
m.addConstrs(
quicksum(x.get((i,j),0) for i in num_nurses >= multis[i][1]
for j in range(numday)
)But something is wrong and i cant see where the problem is. Could you help me to find it?
About the mean quantity: yeah, i want to spread the work evenly between nurses. But it must be nurse-day dependent, for that reason i am not sure if your idea could work in this case. fixing a minimum = 1 makes sense to me, but i am not sure how to set the maximum being nurse-day dependant.
Thanks for your all help Riley!
0 -
Hi Bernado,
A few things look to be going wrong here. Let's take a look at these constraints
#this is would be my new constrain for multis
m.addConstrs(
quicksum(x.get((i,k),0) for i in num_nurses for k in range(j-multis[i][0]+1, j+1)) == multis[i][0]
for j in range(numday)
)Python won't be able to understand what multis[i][0] is on the RHS of the constraints, since it doesn't know what i is. The variable i is defined inside your generator expression for quicksum, you can't use i outside of this expression. If I have understood correctly then you will want your RHS value to be 1. The quicksum expression is counting up how many nurses are working for a particular day. If the number of nurses changes each day for example then you could define a dictionary called shift_requirements whose keys would be the day numbers, then the RHS would be shift_requirements[j]. However it seems that you only want one nurse per day and so the RHS can just be 1.
The second set of constraints have similar problems
#this is would be my new constrain for spacing between shifts
m.addConstrs(
quicksum(x.get((i,j),0) for i in num_nurses >= multis[i][1]
for j in range(numday)
)Firstly, you are missing a closing bracket for your quicksum. I.e. a ) after "for i in num_nurses". But you also have the same problem as above where you are trying to use i outside of the expression. Unlike the above constraints though these will need a complete overhaul - this structure won't get you what you want.
The way to approach it is to calculate for each nurse the minimum days between the start of two shift-sequences. Let's use "Telly" as an example. Once they begin, Telly is on for 4 days, then off for at least 8 days. If Telly starts a shift sequence on day d, i.e. x["Telly", d] = 1, then they cannot start again until at least day d+12. We can prevent this with the following constraint:
x["Telly", d] + x["Telly", d+1] + ... + x["Telly", d+11] <= 1
or equivalently (by substituting s = d+11)
x["Telly", s-11] + x["Telly", s-10] + ... + x["Telly", s] <= 1
These are the constraints you need:
m.addConstrs(
quicksum(x[i,k] for k in range(j-multis[i][0]-multis[i][1]+1, j+1)) <= 1
for i in num_nurses
for j in range(multis[i][0]+multis[i][1]-1, numday)
)There will be one constraint for each nurse/day combination.
- Riley
0 -
Hi Riley,
Your logic for the spacing between shift is just what i want, but the RHS needed a fix:
m.addConstrs(
quicksum(x[i,k] for k in range(j-multis[i][0]-multis[i][1]+1, j+1)) <= multis[i][0]
for i in num_nurse
for j in range(multis[i][0]+multis[i][1]-1, numday)
)because the constraint should count days assigned:
1 2 3 4 5 6 7 8 9 10 11 12 13 Telly 1 1 1 1 0 0 0 0 0 0 0 0 1 if telly start her turn in 1 and she has 4 consecutive shifts, then the sum must be 4 or 0, and her next turn should be in 13 (the wait is 8 before the last consecutive).
Case nurse with 2 consecutive shift and 4 wait days :
1 2 3 4 5 6 7 8 9 10 11 12 13 b 1 1 0 0 0 0 1 1 0 0 0 0 1 in this case the sum must be 2 or 0 and her next turn must be in 7.
That is for the constrain for the spacing between shifts.
As for consecutive shift constrain, it could be something like this:
m.addConstrs(
quicksum(x[i,k] for k in range(j, j+ multis[i][0])) == multis[i][0]
for i in num_nurse
for j in range(numday-multis[i][0])
)this is still unfeasible, but the problem that i see here is:
quicksum(x[i,k] for k in range(j, j+ multis[i][0])) == multis[i][0] , must be multis[i][0] or 0,
and i have some doubts if this is ok for multi = 1, because for bigger multis might work.
Do you have any ideas about this?
Thanks in advance for your help Riley!
-Bernardo
0 -
Hi Bernardo,
It seems you are using your original interpretation of x variables, rather than the one I suggested
Have you thought about changing the definition of your binary variables? Instead of using "x[i,j] = 1 if nurse i works shift j", you could use "x[i,j] = 1 if nurse i works starts a 3 shift sequence with shift j".
You would have to change the definition of your constraints to match, but this is the approach that immediately comes to my mind.In the way I was suggesting, a solution where Telly starts on day 1 and 13 would look like this
Day 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Telly 1 0 0 0 0 0 0 0 0 0 0 0 1 0I think it will be very hard to model what you want to without using this approach.
- Riley
0 -
Oh! I was thinking that we get back to the first approach because i dont see how the dictionary for multis enters with your redefinition.
But lets get back to your way.
If i follow you: if you have 3 nurses:
telly with 3 consecutive shift and 4 wait shitft.
Gia with 4 consecutive shift and 5 waits,
and lois with 1 and 2.
With your approach you will have something like this:
starting in 1 - without limit of nurses constraint 1 2 3 4 5 6 7 8 9 10 Telly (3,4) 1 0 0 0 0 0 0 1 0 0 Gia (4,5) 1 0 0 0 0 0 0 0 0 1 Lois (1,2) 1 0 0 1 0 0 1 0 0 1 the ones in telly are 3 consecutive days, but the ones in Gia are 4 consecutive days.
and Posible solution - with limit of nurses constraint 1 2 3 4 5 6 7 8 9 10 Telly (3,4) 1 0 0 0 0 0 0 0 1 0 Gia (4,5) 0 0 0 1 0 0 0 0 0 0 Lois (1,2) 0 0 0 0 0 0 0 1 0 0 Your approach can be able to get this posible solution? just with this constrain for the spacing?
m.addConstrs(
quicksum(x[i,k] for k in range(j-multis[i][0]-multis[i][1]+1, j+1)) <= 1
for i in num_nurse
for j in range(multis[i][0]+multis[i][1]-1, numday)
)0 -
from gurobipy import *
numday = 15
num_nurses = ["a","b","c","Telly","e"]
multis = { "a":[1,3],"b":[1,3],"c":[3,6],"Telly":[4,8],"e":[2,5] }
m = Model('nsp')
x = m.addVars(num_nurses,range(numday), vtype=GRB.BINARY,name='x')
# Don't allow nurses to start a 3-day shift that goes past day 15.
# We do this by setting the upper bound to zero on these variables.
for i in num_nurses:
for j in range(numday-multis[i][0]+1, numday):
x[i,j].ub=0
# I've commented the objective out, as it doesn't make much sense to me.
#m.setObjective(quicksum(x[i,j] for i in num_nurses for j in range(numday) ),GRB.MAXIMIZE)
#every day must be assigned exclusively to one nurse
# for every day we count the 3-day shifts that started on that day, but also the
# day before, and the day before (when multis=3)
m.addConstrs(
quicksum(x.get((i,k),0) for i in num_nurses for k in range(j-multis[i][0]+1, j+1)) == 1
for j in range(numday)
)
# minimum days off
m.addConstrs(
quicksum(x[i,k] for k in range(j-multis[i][0]-multis[i][1]+1, j+1)) <= 1
for i in num_nurses
for j in range(multis[i][0]+multis[i][1]-1, numday)
)
m.optimize()
starts = [k for k,v in x.items() if v.X > 0.5]
roster = {(nurse,day):"." for nurse in num_nurses for day in range(numday)}
for nurse, day in starts:
for j in range(day, day+multis[nurse][0]):
if (nurse,j) in roster:
roster[nurse,j] = "x"
for j in range(day+multis[nurse][0], day+multis[nurse][0]+multis[nurse][1]):
if (nurse,j) in roster:
roster[nurse,j] = "-"
for i in num_nurses:
print(f"{i:<6}", " ".join([roster[i,j] for j in range(numday)]))The output:
a x - - - . . . . . . x - - - x
b . . . . . . . . . . . . . x -
c . . . x x x - - - - - - . . .
Telly . . . . . . x x x x - - - - -
e . x x - - - - - . . . x x - -There are no shift balancing constraints in this code, but this is better handled in the objective in my opinion
- Riley
0 -
Hi Riley,
This is exactly what i was looking for!
You're right, it looks like shift balancing is not needed.
Thanks a lot!
Cheers!
Bernardo
0
Please sign in to leave a comment.
Comments
11 comments