1 comment

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 gpfrom gurobipy import GRB# Number of workers required for each shiftshifts, 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 7workers, 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 modelm = 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-1z = m.addVars(availability, vtype=GRB.BINARY, name="start")# The objective is to minimize the total pay costsm.setObjective(gp.quicksum(pay[w]*x[w, s] for w, s in availability), GRB.MINIMIZE)# Constraints: assign exactly shiftRequirements[s] workers to each shift sm.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-1m.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 shiftsm.addConstrs(z.sum(w, '*') <= 1 for w in workers)# Optimizem.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.0Amy works 2 days: Fri12, Sat13Bob works 0 daysCathy works 2 days: Fri12, Sat13Dan works 7 days: Mon1, Tue2, Wed3, Thu4, Fri5, Sat6, Sun7Ed works 12 days: Wed3, Thu4, Fri5, Sat6, Sun7, Mon8, Tue9, Wed10, Thu11, Fri12, Sat13, Sun14Fred works 5 days: Wed3, Thu4, Fri5, Sat6, Sun7Gu works 1 day: Sat6Jerry works 3 days: Fri5, Sat6, Sun7Eli works 14 days: Mon1, Tue2, Wed3, Thu4, Fri5, Sat6, Sun7, Mon8, Tue9, Wed10, Thu11, Fri12, Sat13, Sun14Kaladin works 4 days: Thu11, Fri12, Sat13, Sun14Rand works 1 day: Mon1Kvothe works 2 days: Sat13, Sun14Frodo works 5 days: Wed10, Thu11, Fri12, Sat13, Sun14Mon1 is covered by 3 employees: Dan, Eli, RandTue2 is covered by 2 employees: Dan, EliWed3 is covered by 4 employees: Dan, Ed, Fred, EliThu4 is covered by 4 employees: Dan, Ed, Fred, EliFri5 is covered by 5 employees: Dan, Ed, Fred, Jerry, EliSat6 is covered by 6 employees: Dan, Ed, Fred, Gu, Jerry, EliSun7 is covered by 5 employees: Dan, Ed, Fred, Jerry, EliMon8 is covered by 2 employees: Ed, EliTue9 is covered by 2 employees: Ed, EliWed10 is covered by 3 employees: Ed, Eli, FrodoThu11 is covered by 4 employees: Ed, Eli, Kaladin, FrodoFri12 is covered by 6 employees: Amy, Cathy, Ed, Eli, Kaladin, FrodoSat13 is covered by 7 employees: Amy, Cathy, Ed, Eli, Kaladin, Kvothe, FrodoSun14 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