# 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 for a greedy heuristic for my model in Gurobi?

This is my model:

\begin{align} &\min\sum_j\sum_t( o_{jt}+u_{jt})&\\ &\sum_i 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()

• Are you looking for help with Gurobi (your code snippet seems to work fine) or for a greedy heuristic? Can you specify your question please. Commented Jun 12 at 12:01
• Cross-posted here Commented Jun 12 at 12:51
• I have two comments that might be related to the fact that your model is simplified. First, why do you need $o_{jt}$, since you dont require every person to work (Constraint 2), so this variable would always be 0. Second, wouldnt it be an optimal decision to just assign a random person to a task, until the demand is fulfilled? Commented Jun 12 at 13:34
• You are right, these problems are due to the models simplicicty Commented Jun 12 at 14:04
• In that case, you should add some of your model complexity to the question, such that the problem will be non-trivial to solve. Commented Jun 12 at 14:24