Adding Consecutive Shifts COnstraint

Comments

1 comment

  • Eli Towle

    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

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk