Scheduling Problems

Introduction

In workforce management, scheduling means choosing how many resources to assign to each shift based on projected demand by interval. For example, after using ErlangC to estimate hourly call center requirements, scheduling can decide how many agents should be assigned to the available morning, afternoon, night, or mixed shifts.

The meaning of “optimal” depends on the objective function. A schedule might minimize the total number of scheduled resources, or it might minimize the absolute difference between required and planned resources.

pyworkforce includes two scheduling solvers:

MinAbsDifference
MinRequiredResources

The following sections explain each method, first intuitively and then with the mathematical formulation and examples.

For both methods, we’ll introduce the following variables and notation:

Name	Type	Description
\(D\)	Set	Days on the planning horizon
\(S\)	Set	Shifts in a day
\(P\)	Set	Periods or intervals in a day
\(E_{sp}\)	Parameter	1 if the shift s covers the period p, 0 otherwise
\(\beta\)	Parameter	Maximum number of resources that are allowed in a shift
\(\gamma\)	Parameter	Maximum number of resources that are allowed in a period
\(N_{dp}\)	Parameter	Number of resources required at day d for the period p
\(X_{ds}\)	Decision variable	Number of resources to schedule at day d for the shift s

The period definition can use any time granularity: 24 one-hour intervals, 48 half-hour intervals, or another structure that matches your requirements data.

MinAbsDifference

This method minimizes the absolute difference between required and scheduled resources. Because it minimizes differences in both directions, the solution may schedule more or fewer resources than required in a given interval.

Under this definition, the objective function is formulated as:

\[min \sum_{d, p} \left | X_{ds}*E_{sp} - N_{dp} \right |\]

Notice that the term \(X_{ds}*E_{sp}\) would result in the number of scheduled resources for a period and day, and the term \(N_{dp}\) is the required resources, so the objective is to minimize the absolute difference over all days and periods of the requirements vs. the actual scheduling.

The model uses these restrictions:

The number of scheduled resources for a period p and day d cannot exceed the maximum allowed capacity.

\[0 \leq X_{ds}*E_{sp} \leq \gamma \; \forall d \in D, \forall p \in P\]

The number of scheduled resources on the same shift cannot exceed the maximum allowed capacity.

\[0 \leq X_{ds} \leq \beta \; \forall d \in D, \forall s \in S\]

Positive integer restriction

\[\begin{split}X_{ds}, \gamma, N_{dp} \in \mathbb{Z}^{*} \; \forall d \in D, \forall s \in S, \forall p \in P \\\end{split}\]

Boolean restriction

\[\begin{split}E_{sp} \in \{0, 1\} \; \forall s \in S, \forall p \in P \\\end{split}\]

This is how to solve the problem with pyworkforce. The comments reference the notation above. The example solves a two-day scheduling problem with 24 one-hour intervals per day.

from pyworkforce.scheduling import MinAbsDifference
from pprint import PrettyPrinter

# Columns are an hour of the day, rows are the days
# N_dp
required_resources = [
    [9, 11, 17, 9, 7, 12, 5, 11, 8, 9, 18, 17, 8, 12, 16, 8, 7, 12, 11, 10, 13, 19, 16, 7],
    [13, 13, 12, 15, 18, 20, 13, 16, 17, 8, 13, 11, 6, 19, 11, 20, 19, 17, 10, 13, 14, 23, 16, 8]
]

# Each shift has 24 entries, one per hour of the day
# E_sp
shifts_coverage = {"Morning": [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                   "Afternoon": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
                   "Night": [1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
                   "Mixed": [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]}

scheduler = MinAbsDifference(num_days=2,  # S
                             periods=24,  # P
                             shifts_coverage=shifts_coverage,
                             required_resources=required_resources,
                             max_period_concurrency=27,  # gamma
                             max_shift_concurrency=25)   # beta

solution = scheduler.solve()
pp = PrettyPrinter(indent=2)
pp.pprint(solution)

The solver will print this solution:

{ 'cost': 157.0,
  'resources_shifts': [ {'day': 0, 'resources': 11, 'shift': 'Morning'},
                        {'day': 0, 'resources': 11, 'shift': 'Afternoon'},
                        {'day': 0, 'resources': 9, 'shift': 'Night'},
                        {'day': 0, 'resources': 1, 'shift': 'Mixed'},
                        {'day': 1, 'resources': 13, 'shift': 'Morning'},
                        {'day': 1, 'resources': 14, 'shift': 'Afternoon'},
                        {'day': 1, 'resources': 13, 'shift': 'Night'},
                        {'day': 1, 'resources': 0, 'shift': 'Mixed'}],
  'status': 'OPTIMAL'}

The OPTIMAL status means that the solver found the best feasible solution for the model. The cost is the value of the objective function. resources_shifts is the shift schedule, represented by \(X_{ds}\); it tells you how many resources to schedule for each day and shift.

MinRequiredResources

This method minimizes the total scheduled resources while ensuring that every interval has at least the required number of resources. It often schedules more resources than MinAbsDifference because understaffing is not allowed.

In addition to the variables used by MinAbsDifference, this method accepts an optional shift-cost parameter:

Name	Type	Description
\(C_{s}\)	Parameter	Cost or weight in the objective function for shift s

In this case, the objective function is:

\[min \sum_{d, s} C_{s}*X_{ds}\]