Solve scheduling model using a greedy heurisitc
回答済み
I 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 1-7. Then you fix the assignments for day 1, and solve the model for days 2-8 (but include fixed variables for day 1), then for days 3-9 after fixing days 1-2 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 -
Hi Ronald,
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 1-7. Then you fix the assignments for day 1, and solve the model for days 2-8 (but include fixed variables for day 1), then for days 3-9 after fixing days 1-2 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
Base on the above, please is there a Gurobi implementation rolling horizon? That involves the fixing of the decision from the non-overlapping horizon and then reoptimizing the decision of the overlapping horizon in the next horizon. If you can help with some examples on this, I will appreciate it.
Thanks
0 -
Hi Johnpaul,
We don't have a full example available. However, once you have the code for constructing and solving the full model, the changes are relatively small. Here are the tricks you need:
- After your first call to model.optimize(), you can make any changes needed. In your case, you would extend the planning horizon and therefore add a set of variables for the newly added day, plus constraints that involve these variables.
- To fix the variables for the first day in your horizon, you simply set the LB and UB attributes of the corresponding variables to their optimal solution from the previous iteration, e.g. var.LB = var.X; var.UB = var.X.
- Finally, to reoptimize, you simply call model.optimize() again. Gurobi will try to restart from its previous solution.
Kind regards,
Ronald0 -
Thanks so much for your quick response, Roland
0
サインインしてコメントを残してください。
コメント
4件のコメント