Shift Scheduling Problem

Consider the following shift scheduling problem, which aims to find a schedule that minimizes the total worker cost.

There are 6 workers and a planning horizon of 31 days, from day 1 to day 31. For simplicity, we assume that all workers are off on day 0 and day 32.
Exactly 4 workers must be scheduled on each day from day 1 to day 31.
The following constraints must be satisfied for each worker:
- works for either 20 or 21 days,
- works no more than 6 consecutive days,
- works no fewer than 3 consecutive days,
- has no isolated day off; days off must be consecutive.

Formulation of the shift scheduling problem

The formulation uses a $6\times 33$ matrix of binary variables $X=(x_{i,j})$ ($0\leq i\leq 5, 0\leq j\leq 32$) where worker $i$ works on day $j$ if and only if $x_{i,j}=1$.

Since all workers are off on day 0 and day 32, we fix

\[\begin{aligned} x_{i,0}=x_{i,32}=0 & &(0\leq i\leq 5). \end{aligned}\]

The constraints are formulated as follows. The minimum consecutive working days and no isolated day off constraints are written as products, representing the forbidden working patterns, that must be 0.

Daily staffing constraint

Exactly 4 workers must be scheduled on each day:

\[\begin{aligned} \sum_{i=0}^{5} x_{i,j} = 4& &(1\leq j\leq 31) \end{aligned}\]

Total working days constraint

Each worker must work for either 20 or 21 days:

\[\begin{aligned} 20\leq \sum_{j=0}^{32} x_{i,j} \leq 21& &(0\leq i\leq 5) \end{aligned}\]

Maximum consecutive working days constraint

No worker may work for more than 6 consecutive days; that is, any 7 consecutive days contain at most 6 working days:

\[\begin{aligned} \sum_{k=j}^{j+6} x_{i,k} \leq 6 & &(0\leq i\leq 5, 0\leq j\leq 26)\\ \end{aligned}\]

Minimum consecutive working days constraint

Each working period must consist of at least 3 consecutive working days:

\[\begin{aligned} \bar{x}_{i,j}x_{i,j+1}x_{i,j+2}\bar{x}_{i,j+3} = 0 & &(0\leq i\leq 5, 0\leq j\leq 29)\\ \bar{x}_{i,j}x_{i,j+1}\bar{x}_{i,j+2} = 0 & & (0\leq i\leq 5, 0\leq j \leq 30) \end{aligned}\]

No isolated day off constraint

No worker may have a single day off between two working days:

\[\begin{aligned} x_{i,j}\bar{x}_{i,j+1}x_{i,j+2} = 0 & &(0\leq i\leq 5, 0\leq j\leq 30)\\ \end{aligned}\]

Total worker cost

Let $C=(c_i)$ be a cost vector, where $c_i$ denotes the daily cost of assigning worker $i$. The total worker cost is formulated as:

\[\begin{aligned} \sum_{i=0}^5\sum_{j=0}^{32} c_i x_{i,j} \end{aligned}\]

This objective function is minimized subject to the constraints described above.

PyQBPP program for the shift scheduling

The shift scheduling problem defined above can be formulated and solved using PyQBPP as follows:

import pyqbpp as qbpp

days = 31
worker_cost = qbpp.array([13, 13, 12, 12, 11, 10])
workers = len(worker_cost)

x = qbpp.var("x", shape=(workers, days + 2))

workers_each_day = qbpp.vector_sum(x, axis=0)
each_day_4_workers = qbpp.cons(workers_each_day[1:days + 1] == 4)

workers_working_days = qbpp.vector_sum(x)
work_20_21_days = qbpp.cons(workers_working_days, between=(20, 21))

no_more_than_6_consecutive_working_days = 0
for w in range(workers):
    for j in range(days - 4):
        work = qbpp.sum(x[w][j:j + 7])
        no_more_than_6_consecutive_working_days += qbpp.cons(work <= 6)

no_less_than_3_consecutive_working_days = 0
for w in range(workers):
    for j in range(days - 1):
        no_less_than_3_consecutive_working_days += qbpp.cons(
            ~x[w][j] * x[w][j+1] * x[w][j+2] * ~x[w][j+3])
    for j in range(days):
        no_less_than_3_consecutive_working_days += qbpp.cons(
            ~x[w][j] * x[w][j+1] * ~x[w][j+2])

no_single_day_off = 0
for w in range(workers):
    for j in range(days):
        no_single_day_off += qbpp.cons(x[w][j] * ~x[w][j+1] * x[w][j+2])

total_worker_cost = qbpp.sum(worker_cost * workers_working_days)

constraints = (work_20_21_days + no_less_than_3_consecutive_working_days +
               no_more_than_6_consecutive_working_days +
               no_single_day_off + each_day_4_workers)
f = total_worker_cost + 10000 * constraints

ml = {x[i][0]: 0 for i in range(workers)}
ml.update({~x[i][0]: 1 for i in range(workers)})
ml.update({x[i][days + 1]: 0 for i in range(workers)})
ml.update({~x[i][days + 1]: 1 for i in range(workers)})
f.simplify_as_binary()

g = qbpp.replace(f, ml)
g.simplify_as_binary()

solver = qbpp.EasySolver(g)
sol = solver.search(time_limit=5.0)

full_sol = qbpp.Sol(f).set(sol, ml)

for i in range(workers):
    wd = full_sol(workers_working_days[i])
    bits = "".join(str(full_sol(x[i][j])) for j in range(1, days + 1))
    print(f"Worker {i}: {wd} days worked: {bits}")

day_counts = "".join(str(full_sol(workers_each_day[d])) for d in range(1, days + 1))
print(f"Workers each day        : {day_counts}")
print(f"Total worker cost: {full_sol(total_worker_cost)}")
print(f"Violated constraints: {f.cons(full_sol)}")

In this program, the variables and expressions are defined as follows:

x: A $6\times 33$ matrix of binary variables,
workers_each_day: An array containing the column-wise sums of x, representing the number of workers assigned to each day.
each_day_4_workers: The constraints that exactly four workers are assigned to each day. The slice workers_each_day[1:days + 1] extracts the elements for days 1 to 31; applying == 4 to this array gives 31 element-wise equalities, and enclosing them in qbpp.cons() declares all 31 constraints at once.
workers_working_days: An array of row-wise sums of x, representing the total number of working days for each worker.
work_20_21_days: The constraints that each worker works for either 20 or 21 days.
no_more_than_6_consecutive_working_days: The constraints that any 7 consecutive days contain at most 6 working days. x[w][j:j + 7] holds the variables of worker w for the 7 days starting from day j; their qbpp.sum is compared with <= 6.
no_less_than_3_consecutive_working_days: The constraints that every working period lasts at least 3 days. The products representing a working period of one or two days must be 0.
no_single_day_off: The constraints that no worker has a single day off between two working days. The products representing a single day off must be 0.
constraints: The sum of all constraints.
total_worker_cost: An expression representing the total worker cost. worker_cost * workers_working_days is the element-wise product, giving the cost of each worker, and qbpp.sum adds them up.

Solving

Each constraint is declared with qbpp.cons(), so the solver treats it as a constraint. For the working-pattern constraints, the products are enclosed in qbpp.cons(); such a constraint is satisfied when the product is 0. By summing total_worker_cost and constraints with a weight of 10000, we obtain an expression f.

A Python dict ml is used to fix the values of the variables corresponding to day 0 and day 32. Applying qbpp.replace() to f with ml yields a new expression g.

The Easy Solver is then applied to g, and the resulting solution is stored in sol. To evaluate the original expressions (which still refer to the fixed variables), we build full_sol = qbpp.Sol(f).set(sol, ml), which combines the fixed values in ml with the values in sol.

The obtained solution is as follows:

Worker 0: 20 days worked: 1111001111110011100001111000111
Worker 1: 20 days worked: 0000111111000111110011111001111
Worker 2: 21 days worked: 1111110011111001111100111110000
Worker 3: 21 days worked: 1111110001111100111110011111000
Worker 4: 21 days worked: 0000111100111111001111100111111
Worker 5: 21 days worked: 1111001110001110011111000111111
Workers each day        : 4444444444444444444444444444444
Total worker cost: 1465
Violated constraints: 0

f.cons(full_sol) is the number of violated constraints. We observe that a feasible shift schedule with a total worker cost of 1465 is obtained, and all constraints are satisfied. The total number of working days is $4\times 31=124$, so if each of the 6 workers works 20 or 21 days, four of them work 21 days and two work 20 days. Letting the four cheapest workers work 21 days gives $21\times(12+12+11+10)+20\times(13+13)=1465$, which is the minimum total worker cost.