Staff Assignment Problem with Gurobi
Recently, we made a staffing assignment model for a hypothetic clinic. The goal is to provide clinic managers a tool to assign staff to each shift with the lowest cost.
The model is achieved by using Excel-based OpenSolver. I found that though the Excel model is easy to read and operate, it lacks flexibility especially when we want to add new staff or adjust current staff number.
So, I can’t help think about the question: can this be achieved by coding? Then Google quickly showed me to Gurobipy Python Package:
https://www.gurobi.com/documentation/9.1/quickstart_mac/cs_grbpy_the_gurobi_python.html
Users can set up a Gurobi model by adding changing variables, objective functions, and constraints, which works similarly to Solver setup. So, with Gurobipy I easily set up the staff assignment model in 6 steps as below:
Before start:
# import packagesfrom gurobipy import *
import pandas as pd
import matplotlib.pyplot as plt
import numpy as np
Step 1: Set up Basic Information:
In our case, basic information includes: employee, costday, costnight, minimum request, supply. (We assumed: there are 18 employees of the clinic: 4*receptionists, 4*doctors, 6*nurses, 4*cleaning staff; there are 3 shifts on Monday, Wednesday, Friday, 2 shifts on Tuesday, Thursday, Saturday, and 1 shift on Sunday)
employee = ['reception', 'doctor', 'nurse', 'cleaningstaff']
willingness = {}
for h in employee:
for i in range (1,7):
for j in range (1,8):
if (h == 'reception' or h == 'doctor' or h == 'cleaningstaff') and i > 4:
willingness[(h,i,j)] = 0
elif j == 7 :
willingness[(h,i,j)] = 3
else:
willingness[(h,i,j)] = 6costday = {'reception': 30,
'doctor': 50,
'nurse':40,
'cleaningstaff':20}costnight = {'reception': 35,
'doctor': 9999,
'nurse':45,
'cleaningstaff':55}# min request should be the outcome from Customer Estimation model, here we simply input as an constantminimum_request = {'reception':[2,1,1,1,2,0,2,1,1,2,2,0,2,2,1,2,2,0,0,0,1],
'doctor':[1,1,0,1,2,0,1,1,0,1,2,0,1,2,0,2,2,0,0,0,0],
'nurse': [1,2,2,2,3,0,2,2,2,2,3,0,2,3,2,3,3,0,0,0,0],
'cleaningstaff':[1,2,1,1,2,0,1,2,1,1,2,0,2,2,1,2,2,0,0,0,0]}required = {}
for h in employee:
l = 0
for j in range(1,8):
for k in range(1,4):
required[(h,j,k)] = minimum_request[h][l]
l = l+1supply = {'mask': 1,
'gloves':2,
'sanitized suit':20}
Step 2: Set up the Gurobi Model
Model = gurobipy.Model("Work Schedule")Step 3: Set up the Decision Variables
Here, we set up two sets of variables:
- X h,i,j,k , (binary) which represents whether a specific person: position (h:job type), series number (i) is schedules to work on day (j: Mon-Sun), Shift (k: 1–3).
- Y h,i,j, (binary) which represents whether a specific person: position (h:job type), series number (i) is schedules to work on day (j: Mon-Sun).
x = Model.addVars(employee,range (1,7),range(1,8),range(1,4),vtype = gurobipy.GRB.BINARY, name="assign")y = Model.addVars(employee,range (1,7),range(1,8), vtype = gurobipy.GRB.BINARY, name="assignday")
Step 4: Set up the Objective Function:
Here, we want to minimize the total cost of both staffing wages and necessity supply cost: Min ((Staffing Cost) + (Supply Cost))
Model.setObjective(gurobipy.quicksum(x[h,i,j,k]*costday[h]*3+x[h,i,j,3]*costnight[h]*3 +x[h,i,j,k]*3+y[h,i,j]*20 for h in employee for i in range(1,7) for j in range(1,8) for k in range (1,3)),sense = gurobipy.GRB.MINIMIZE)Step 5: Add Constraints
We have set 5 constraints as below:
- Minimum staff for each shift should fulfill minimum request.
- Decision variables should be binary decision.
- Scheduling hour should be less than individual willingness.
- No consecutive night-day or day-night shift.
- Minimize staff number per day.
#Add Constraint#1: Minimum staff for each shift should fulfill minimum request.
Model.addConstrs(x.sum(h,'*',j,k) >= required [(h,j,k)] for h in employee for k in range(1,4) for j in range(1,8))
Model.update()#Add Constraint#3: Scheduling hour should less than individual willingness.
Model.addConstrs(x.sum(h,i,j,'*')*3 <= willingness[(h,i,j)] for h in employee for i in range(1,7) for j in range(1,8))
Model.update()#Add Constraint#4: No consecutive night-day or day-night shift.
Model.addConstrs(x[h,i,j,3] + x[h,i,(j+1),1] <= 1 for h in employee for i in range(1,7) for j in range(1,7))
Model.update()#Add Constraint#5: Minimize staff number per day.
Model.addConstrs(x[h,i,j,1] <= y[h,i,j] for h in employee for i in range(1,7) for j in range(1,8))
Model.update()
Model.addConstrs(x[h,i,j,2] <= y[h,i,j] for h in employee for i in range(1,7) for j in range(1,8))
Model.update()
Model.addConstrs(x[h,i,j,3] <= y[h,i,j] for h in employee for i in range(1,7) for j in range(1,8))
Model.update()
Step 6: Optimize
Model.optimize()Then the job is basically done! The rest work is just to output and visualize the result.
Results output :
# Convert the output into a list of lists
matrix = []
for v in Model.getVars():
# print(v.varName, v.x)
matrix.append(v.x)
matrix
i = 0
new = []
while i<(len(matrix)-168):
new.append(matrix[i:i+21])
i+=21# Convert the result list of lists into array
staff = ["reception1", "reception2", "reception3", "reception4","reception5", "reception6",
"doctor1","doctor2","doctor3","doctor4","doctor5","doctor6",
"nurse1","nurse2","nurse3","nurse4","nurse5","nurse6",
"cleaningstaff1","cleaningstaff2","cleaningstaff3","cleaningstaff4","cleaningstaff5","cleaningstaff6"]shift = ["Mon_s1", "Mon_s2", "Mon_s3",
"Tue_s1", "Tue_s2", "Tue_s3",
"Wed_s1", "Wed_s2", "Wed_s3",
"Thu_s1", "Thu_s2", "Thu_s3",
"Fri_s1", "Fri_s2", "Fri_s3",
"Sat_s1", "Sat_s2", "Sat_s3",
"Sun_s1", "Sun_s2", "Sun_s3"]schedule = np.array(new)#Adjust format and output the schedule
print('Assigments')
print('Symbols: \'-\': not working, \'S\': Scheduled')
a = pd.DataFrame(schedule, columns = shift)
a = a.replace(0, '-')
a = a.replace(1, 'S')
a['new_index'] = staff
a = a.set_index('new_index')
a = a.drop(['reception5', 'reception6','doctor5','doctor6','cleaningstaff5','cleaningstaff6'])
a = a.drop (['Tue_s3', 'Thu_s3','Sat_s3','Sun_s1','Sun_s2'], axis=1)
a
Finally we can see a result as below:
And with a little code, we can also make some statistics easily as below:
Conclusion
After the trial, I feel Gurobi + Python gives more flexibility and expansion power to such assignment problems compared with Excel bases Solver solutions. We can see that users can easily update the basic information without touching other domains (objective function, constraints). And using for - loop iterations within constraints makes summation easier both horizontally and vertically.
