Solve scheduling model using a greedy heurisitc
AnsweredI have the following scheduling problem. Relatively simple and not very complex (only serves as an example). The indexes are \(I\) worker, \(T\) days and \(J\) shift. The decision variable is \(x_{ijt}\), which is 1 if a person works a certain shift. I also have variables for udnerstaffing \(u_{tj}\) and overstaffing \(o_{jt}\). I have the parameters \(D_{jt}\) demand. The goal is to minimize under and overstaffing. Since my whole model is very complex for large model instances, I would like to solve it with a greedy heuristic (on the advice of a colleague), but I am not familiar with the theory and especially with the implementation in Gurobi. How would I suspend the theory and the implementation in Gruboi? I would be very grateful for any help.
This is my model:
\[\begin{align}
&\min\sum_j\sum_j( o_{jt}+u_{jt})&\\
&\sum_j x_{ijt} + u_{jt}o_{jt}=D_{jt}\quad&\forall j,t\\
&\sum_j x_{ijt}\leq 1\quad &\forall i,t\\
&x_{ijt}\in \left\{ 0,1 \right\}\quad &\forall i,t,j
\end{align}\]
The gurobi code is:
from gurobipy import *
# Create a new model
m = Model("Scheduling Problem")
# Define the indices
num_workers = 10
num_days = 5
num_shifts = 3
I = range(num_workers) # Set of workers
T = range(num_days) # Set of days
J = range(num_shifts) # Set of shifts
# Define the demand parameter as a dictionary
D = {}
D[(0,0)] = 4
D[(0,1)] = 3
D[(0,2)] = 5
D[(0,3)] = 2
D[(0,4)] = 6
D[(1,0)] = 3
D[(1,1)] = 4
D[(1,2)] = 2
D[(1,3)] = 5
D[(1,4)] = 3
D[(2,0)] = 5
D[(2,1)] = 2
D[(2,2)] = 6
D[(2,3)] = 3
D[(2,4)] = 4
# Create the decision variables
x = m.addVars(I, J, T, vtype=GRB.BINARY, name="x")
u = m.addVars(J, T, lb=0, name="u")
o = m.addVars(J, T, lb=0, name="o")
# Set the objective function
obj = quicksum(u[j,t] + o[j,t] for j in J for t in T)
m.setObjective(obj, GRB.MINIMIZE)
# Add the constraints
for j in J:
for t in T:
m.addConstr(quicksum(x[i,j,t] for i in I) + u[j,t]  o[j,t] == D[j,t])
for i in I:
for t in T:
m.addConstr(quicksum(x[i,j,t] for j in J) <= 1)
# Solve the problem
m.optimize()

Hi Lorenz,
You mentioned "Since my whole model is very complex for large model". Does this mean the model formulation is as above, but runtime increases as you add workers/shifts/days? Can you give an indication of the model dimensions, and the runtime you observe? Are there other complexities that are not shown above (e.g. labor rules related to consecutive shifts for the same worker) which could have an impact?
If you're willing to sacrifice global optimality, you could consider solving a series of subproblems where each subproblem contains a subset of workers, days and/or shifts. One common approach is rolling horizon. You'd first solve the problem for days 17. Then you fix the assignments for day 1, and solve the model for days 28 (but include fixed variables for day 1), then for days 39 after fixing days 12 etcetera. Other alternatives exist, e.g. repeatedly solve for different subsets of employees. You could even start with rolling horizon, then iteratively reoptimize for subsets of days and/or employees. There's many options out there  but ideally you'd first try to solve the full MIP.
Kind regards,
Ronald0
Please sign in to leave a comment.
Comments
1 comment