Adding Consecutive Shifts COnstraint

Answered

January 29, 2020 22:12

Hello,

I appreciate any and all that can be provided. I'm working through the workforce1.py example (link below) and I was curious as to how one would add the constraint that a given workers shifts must all be consecutive? For example, if Amy is to work 2 shifts, they would be Mon1 and Tue2.

Thanks for any assistance!

workforce_1.py example: https://www.gurobi.com/documentation/9.0/examples/workforce1_py.html

-J

Comments

2 comments

Official comment
Simranjit Kaur

Gurobi Staff

December 06, 2024 00:50
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.

Eli Towle

Gurobi Staff

January 31, 2020 20:32 Edited

Hi Jerry,

Let $ W $ be number of available workers and $ S $ the number of shifts. Let $ c_i $ be the cost of paying worker $ i = 1, \ldots, W $ to work one day. Let $ r_j $ be the required number of workers to cover shift $ j = 1, \ldots, S $. We assume each worker can work a single consecutive set of shifts in the two-week period.

First, let's write down the mathematical formulation of the model of the workforce problem where workers must work consecutive shifts. We define the following variables:

$ x_{ij} $ is $ 1 $ if worker $ i = 1, \ldots, W $ works shift $ j = 1, \ldots, S $, $ 0 $ otherwise
$ z_{ij} $ is $ 1 $ if worker $ i = 1, \ldots, W $ works shift $ j = 1, \ldots, S $ but not the previous shift, $ 0 $ otherwise.

Then, we model the problem as follows. This approach is inspired by a modeling technique in the unit commitment problem, where generators are switched "on" for a consecutive set of time periods.

$$\begin{alignat}{3}
\min_{x,z} && \sum_{i = 1}^{W} \sum_{j = 1}^S c_i &x_{ij} \\
\textrm{s.t.}\ \ && x_{ij} - x_{i,j-1} &\leq z_{i, j} && i = 1, \ldots, W,\ j = 2, \ldots, S \\
&& x_{i,1} &= z_{i,1} && i = 1, \ldots, W \\
&& \sum_{j = 1}^S z_{ij} &\leq 1 && i = 1, \ldots, W \\
&& \sum_{i = 1}^W x_{ij} &= r_j && j = 1, \ldots, S \\
&& x_{ij}, z_{ij} &\in \{0, 1\} \qquad && i = 1, \ldots, W,\ j = 1, \ldots, S
\end{alignat}$$

The idea is that worker $ i $ starts a series of consecutive shifts with shift $ j $ if they did not work the previous shift ( $ x_{i,j-1} = 0 $ ), but they do work the current shift ( $ x_{ij} = 1 $ ). By the above constraints, this forces our new variable $ z_{ij} $ equal to $ 1 $. Then, we include a constraint to ensure that a worker's schedule can only exhibit this pattern once ( $ \sum_{j = 1}^S z_{ij} \leq 1 $ ).

Below is the modified Python code. A few notes:

It is not possible to cover all of the shifts in the original workforce.py example if the workers can only work a single set of consecutive shifts. Thus, we give ourselves a few extra workers to use.
This is much easier to model if we define our variables for every combination of shifts and workers (unavailabilities can be captured by fixing certain variables to 0). For this reason, I defined the "availability" tuplelist differently.
I defined the variables as binary rather than continuous on the interval $[0,1]$. The latter was allowable in the original workforce.py example because of the assignment problem structure. Perhaps we can relax the integrality on the variables in this extended problem, but we would have to check the problem structure first.

import gurobipy as gp
from gurobipy import GRB

# Number of workers required for each shift
shifts, shiftRequirements = gp.multidict({"Mon1": 3, "Tue2": 2, "Wed3": 4, "Thu4": 4, "Fri5": 5, "Sat6": 6, "Sun7": 5, "Mon8": 2, "Tue9": 2, "Wed10": 3, "Thu11": 4, "Fri12": 6, "Sat13": 7, "Sun14": 5})

# Amount each worker is paid to work one shift
# Use 13 workers instead of 7
workers, pay = gp.multidict({"Amy": 10, "Bob": 12, "Cathy": 10, "Dan": 8, "Ed": 8, "Fred": 9, "Gu": 11, "Jerry": 10,"Eli": 8, "Kaladin": 9, "Rand": 11, "Kvothe": 10, "Frodo": 9})

# Worker availability (redefined)
availability = gp.tuplelist([(w,s) for w in workers for s in shifts])

# Create model
m = gp.Model("consecutiveAssignment")

# Assignment variables: x[w,s] == 1 if worker w is assigned to shift s.
x = m.addVars(availability, vtype=GRB.BINARY, name="x")

# New variables: z[w,s] == 1 if worker w works shift s, but not shift s-1
z = m.addVars(availability, vtype=GRB.BINARY, name="start")

# The objective is to minimize the total pay costs
m.setObjective(gp.quicksum(pay[w]*x[w, s] for w, s in availability), GRB.MINIMIZE)

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

# New constraints: z[w,s] == 1 if worker w works shift s, but not shift s-1
m.addConstrs((x[w, s2] - x[w, s1] <= z[w, s2]) for w in workers for s1,s2 in zip(shifts, shifts[1:]))
m.addConstrs(x[w, shifts[0]] == z[w, shifts[0]] for w in workers)

# New constraints: each worker can start a single series of consecutive shifts
m.addConstrs(z.sum(w, '*') <= 1 for w in workers)

# Optimize
m.optimize()

if m.status == GRB.OPTIMAL:
    # Print solution
    print("\nTotal cost: ${}\n". format(m.ObjVal))
    whoCovers = {s: [] for s in shifts}
    workedShifts = {w: [] for w in workers}
    for w in workers:
        for s in shifts:
            if x[w, s].X > 0.5:
                whoCovers[s].append(w)
                workedShifts[w].append(s)
        numShifts = len(workedShifts[w])
        if numShifts > 0:
            plural = "" if numShifts == 1 else "s"
            print("{} works {} day{}: {}".format(w, numShifts, plural, ", ".join(workedShifts[w])))
        else:
            print("{} works 0 days".format(w))

    print()
    for s in shifts:
        numWorkers = len(whoCovers[s])
        if numWorkers > 0:
            plural = "" if numWorkers == 1 else "s"
            print("{} is covered by {} employee{}: {}".format(s, numWorkers, plural, ", ".join(whoCovers[s])))
        else:
            print("{} is covered by 0 employees".format(s))
else:
    print("Optimal solution not found.")

This produces the following output (after optimizing):

Total cost: $502.0

Amy works 2 days: Fri12, Sat13
Bob works 0 days
Cathy works 2 days: Fri12, Sat13
Dan works 7 days: Mon1, Tue2, Wed3, Thu4, Fri5, Sat6, Sun7
Ed works 12 days: Wed3, Thu4, Fri5, Sat6, Sun7, Mon8, Tue9, Wed10, Thu11, Fri12, Sat13, Sun14
Fred works 5 days: Wed3, Thu4, Fri5, Sat6, Sun7
Gu works 1 day: Sat6
Jerry works 3 days: Fri5, Sat6, Sun7
Eli works 14 days: Mon1, Tue2, Wed3, Thu4, Fri5, Sat6, Sun7, Mon8, Tue9, Wed10, Thu11, Fri12, Sat13, Sun14
Kaladin works 4 days: Thu11, Fri12, Sat13, Sun14
Rand works 1 day: Mon1
Kvothe works 2 days: Sat13, Sun14
Frodo works 5 days: Wed10, Thu11, Fri12, Sat13, Sun14

Mon1 is covered by 3 employees: Dan, Eli, Rand
Tue2 is covered by 2 employees: Dan, Eli
Wed3 is covered by 4 employees: Dan, Ed, Fred, Eli
Thu4 is covered by 4 employees: Dan, Ed, Fred, Eli
Fri5 is covered by 5 employees: Dan, Ed, Fred, Jerry, Eli
Sat6 is covered by 6 employees: Dan, Ed, Fred, Gu, Jerry, Eli
Sun7 is covered by 5 employees: Dan, Ed, Fred, Jerry, Eli
Mon8 is covered by 2 employees: Ed, Eli
Tue9 is covered by 2 employees: Ed, Eli
Wed10 is covered by 3 employees: Ed, Eli, Frodo
Thu11 is covered by 4 employees: Ed, Eli, Kaladin, Frodo
Fri12 is covered by 6 employees: Amy, Cathy, Ed, Eli, Kaladin, Frodo
Sat13 is covered by 7 employees: Amy, Cathy, Ed, Eli, Kaladin, Kvothe, Frodo
Sun14 is covered by 5 employees: Ed, Eli, Kaladin, Kvothe, Frodo

This method can be generalized to include things like unavailabilities, shift-dependent employee pay, allowing multiple consecutive shifts each week, restrictions on the number of days an employee can work, etc.

Eli

Post is closed for comments.

Adding Consecutive Shifts COnstraint

Comments

Didn't find what you were looking for?