model for shift scheduling

Hi, I'm new in optimazation modeling. I want to create a programming model for assigning workers to shifts.

I used the Gurobi Python API to solve athe assignment problem and used this as a starting help.

The problem involves assigning workers to shifts, with the objective of minimizing the total number of workers assigned. The number of workers required for each shift is given by shiftRequirements, and the availability of each worker for each shift is given by availability.

# Number of workers required for each shift
 shifts, shiftRequirements = gp.multidict({
    "0":  1,
    "1":  2,
    "2":  2,
    "3":  2,
    "4":  2,
    "5":  2,
    "6":  3,
    "7":  3,
    "8":  3,
    "9":  3,
    "10": 2,
    "11": 2,
    "12": 2,
    })

# Worker availability
availability = gp.tuplelist([
     ('Amy', '0'),('Amy', '1'), ('Amy', '2'), ('Amy', '3'), ('Amy', '4'),
      ('Amy', '5'), ('Amy', '6'), ('Amy', '7'),
      ('Bob', '1'),('Bob', '2'), ('Bob', '3'), ('Bob', '4'), ('Bob', '5'),
      ('Bob', '6'), ('Bob', '7'), ('Bob', '8'),
      ('Ed', '6'),('Ed', '7'), ('Ed', '8'), ('Ed', '9'), ('Ed', '10'),
      ('Ed', '11'), ('Ed', '12')
      ])

The code first creates the Gurobi model object m and the assignment variable x. The assignment variable is a binary decision variable that takes the value 1 if worker w is assigned to shift s, and 0 otherwise. The code sets the objective of the model to minimize the total number of workers assigned, which is calculated as the sum of x[w, s] over all workers w and shifts s.

# Model
m = gp.Model("assignment")

# Assignment variables: x[w,s] == 1 if worker w is assigned to shift s.
# Since an assignment model always produces integer solutions, we use
# continuous variables and solve as an LP.
x = m.addVars(availability, ub=1, name="x")


# The objective is to minimize the total number of workers assigned
m.setObjective(gp.quicksum(x[w, s] for w, s in availability), GRB.MINIMIZE)

The code then adds two constraints to the model. The first constraint ensures that each shift is assigned exactly shiftRequirements[s] workers. This is implemented using the x.sum('*', s) expression, which sums the values of x over all workers w for a given shift s. The constraint is created for each shift s using a generator expression and the m.addConstrs() method.

# Constraint: assign exactly shiftRequirements[s] workers to each shift s
reqCts = m.addConstrs((x.sum('*', s) == shiftRequirements[s] for s in shifts), name="_")

The second constraint limits the number of shifts that each worker can be assigned to max 7. This is implemented using the x.sum(w, '*') expression, which sums the values of x over all shifts s for a given worker w. The constraint is created for each worker w using a generator expression and the m.addConstrs() method.

# constraint: max 7 shifts per worker
reqCts_1 = m.addConstrs((x.sum(w,'*') <= 7 for w in workers), name="__")

Finally, the code calls the m.optimize() method to solve the model. The optimal solution is stored in the x variable, which is a dictionary of the form {(w, s): value} where value is the value of x[w, s] in the optimal solution.

# Optimize
m.optimize()

Now I want to change the second constraint. Each worker should not have to work max 7 shifts.The difference between the index of the last scheduled shift and the first scheduled shift should max 7.

Could you please help me to do the required changes in the code?

Thank you!

Riley Clement

Gurobi Staff

February 28, 2023 00:30

Hi niccc,

Let's say Amy was rostered on shift 0. This means you want to stop them from being rostered on shift 8, and shift 9 and so on, if I understand correctly?

If you have a constraint

x["Amy", 0] + x["Amy", 8] <= 1

then Amy cannot be assigned to both shift 0 and shift 8. In general, for each shift i, and each person p you will want the following constraints

x[p, i] + x[p, j] <= 1, for all j such that j - i > 7

I don't want to spoil the fun so I will leave this as an exercise for you.

- Riley

niccc

February 28, 2023 21:14 Edited

Hi Riley,

thank you for your response and you support.

Yes, I want to reach exactly this constraint.

I changed the reqCts_1 to:

reqCts_1 = m.addConstrs((x[w,i] + x[w,j] <= 1 for w, i in availability for p, j in availability if int(j) - int(i) > 7), name="__")

knowing that this is not looking good.

I get a KeyError ("Amy", "8") because there is no ("Amy", "8") in availability.

What did I get wrong?

March 01, 2023 08:09 Edited

There is no ("Amy", "8") in availability so we have to make sure we don't try and use this index pair in the formulation.

Since you're generator expression is going through all keys in the dictionary, and it's a small problem we can just add the condition that w == p (in your current code p isn't doing anything). This ensures that (w,j) is a key in availability, and hence x[w,j] exists.

reqCts_1 = m.addConstrs(
    (x[w,i] + x[w,j] <= 1 for w, i in availability for p, j in availability
    if int(j) - int(i) > 7 and w==p),
    name="__",
)

March 02, 2023 12:56

thank you, that works for me!

model for shift scheduling

Comments

Didn't find what you were looking for?