1
$\begingroup$

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()
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – PeterD
    Commented Jun 12 at 12:01
  • $\begingroup$ Cross-posted here $\endgroup$
    – A.Omidi
    Commented Jun 12 at 12:51
  • $\begingroup$ 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? $\endgroup$
    – PeterD
    Commented Jun 12 at 13:34
  • $\begingroup$ You are right, these problems are due to the models simplicicty $\endgroup$
    – Uni ewr
    Commented Jun 12 at 14:04
  • $\begingroup$ In that case, you should add some of your model complexity to the question, such that the problem will be non-trivial to solve. $\endgroup$
    – PeterD
    Commented Jun 12 at 14:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.