Employee Scheduling Optimization¶

Description: Employee scheduling model from the Analytical Decision Modeling course at the Arizona State University.

Tags: educational, mip, scheduling, amplpy, gurobi, highs

Notebook author: Yimin Wang <yimin_wang@asu.edu>, Marcos Dominguez Velad <marcos@ampl.com>

Model author: Yimin Wang <yimin_wang@asu.edu>

References:

Analytical Decision Modeling course at W. P. Carey School of Business. Syllabus: https://catalog.apps.asu.edu/catalog/classes/classlist?keywords=86683&searchType=all&term=2237&collapse=Y

Objective and Prerequisites¶

This Employee Scheduling Optimization problem shows you how to determine the optimal number of employees on the payroll in order to:

Satisfy demand for each day’s staffing requirement,
Minimize the payroll cost of all employees, and
Prescribe the actual staffing levels achieved for each day.

This modeling example is at the introductory level, where we assume that you know Python and that you have some knowledge of how to build mathematical optimization models.

Problem Description¶

A small business requires different numbers of full-time employees on different days of the week. The company implements a flexible working policy, which states that each full-time employee can work any five days and take two days off in a week. For example, an employee can work on Monday to Thursday and Saturday while taking Friday and Sunday off. The company wants to meet its daily requirements using only full-time employees. The employees are paid $200 pay day if they work on regular weekdays while receive an additional $100 per day if they work over the weekend. The company’s objective is to minimize its payroll expenses.

The following table lists the staffing requirements on each day of the week.

Day of the Week	Required Staffing Level
Monday	177
Tuesday	134
Wednesday	158
Thursday	191
Friday	149
Saturday	165
Sunday	116

In this example, the goal is to identify how many workers to hire and schedule them so that the total payroll cost is minimized. This example shows how a linear programming model can help the business to:

How to best utilize their employees,
How many workers to hire, and
How they should be scheduled so that the total payroll cost is minimized. This Jupyter Notebook is based on the MSBA SCM518 class contents.

Model Formulation¶

Indices¶

$i \in {1..21}$: Index of possible working schedules (e.g., which days an employee works and which days are off).

$j \in {1..7}$: Index of work days.

Parameters¶

$d_{j}$: Required staffing level on day $j$.

$p_R$: Daily pay for weekdays.

$p_O$: Daily pay for weekends.

$p_{j}$: Daily pay for day $j$.

$a_{ij} \in {0,1}$: An availability table that captures whether employees working under schedule $i$ is available for day $j$.

Decision Variables¶

$x_{i}$: How many employees to hire for work schedule $i$.

Objective Function¶

Cost. We want to minimize the total payroll cost.

\begin{equation} \text{Min}{x_i} \quad \sum{j \in {1…7}} p_j \left(\sum_{i \in {1…21}} a_{ij}\times x_i\right) \tag{0} \end{equation}

Constraints¶

Staffing Requirement. Satisfy staffing requirement for each day.

\begin{equation} \sum_{i \in {1…21}} a_{i,j}\times x_{i} \geq d_j \quad \forall j \in {1…7} \tag{1} \end{equation}

\begin{equation} x_i \geq 0 \quad \forall i \in {1…21} \tag{2} \end{equation}

Python Implementation¶

We now import the AMPL Python Module and other Python libraries.

# Install dependencies
%pip install -q amplpy

# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
    modules=["gurobi", "highs"],  # modules to install
    license_uuid="default",  # license to use
)  # instantiate AMPL object and register magics

Helper Functions¶

We first create a function that helps us to generate an employee availability table based on different work schedules

# compute number of combinations
def nCr(n, r):
    return int(factorial(n) / (factorial(r) * factorial(n - r)))


# compute availability table
# w is the length of the shift, d is number of days off
def schedule(w, d):
    # number of shifts
    v = nCr(w, d)
    s = [[1 for x in range(w)] for x in range(v)]

    i = 0
    for j in range(v):
        for k in range(j + 1, w):
            s[i][j] = 0
            s[i][k] = 0
            i = i + 1
    return s

Generate the availability table and take a look at the table

# generate the schedule availability table
a = schedule(7, 2)

# print the table to visualize
print(np.matrix(a))

[[0 0 1 1 1 1 1]
 [0 1 0 1 1 1 1]
 [0 1 1 0 1 1 1]
 [0 1 1 1 0 1 1]
 [0 1 1 1 1 0 1]
 [0 1 1 1 1 1 0]
 [1 0 0 1 1 1 1]
 [1 0 1 0 1 1 1]
 [1 0 1 1 0 1 1]
 [1 0 1 1 1 0 1]
 [1 0 1 1 1 1 0]
 [1 1 0 0 1 1 1]
 [1 1 0 1 0 1 1]
 [1 1 0 1 1 0 1]
 [1 1 0 1 1 1 0]
 [1 1 1 0 0 1 1]
 [1 1 1 0 1 0 1]
 [1 1 1 0 1 1 0]
 [1 1 1 1 0 0 1]
 [1 1 1 1 0 1 0]
 [1 1 1 1 1 0 0]]

Set up the model and solve

%%writefile employee_sch.mod


# Parameters
param num_days default 7;
param num_shifts; # with 2 free days, 7 nCr 2 = 21

# Sets
set days = 0..num_days-1;
set shifts = 0..num_shifts-1;

param d{days}; # staffing level
param pay{days}; # pay per day

param a{shifts, days};

# Variables
var assign{shifts} integer >= 0;

# Constraints
staff_req{j in days}:
  sum{i in shifts : a[i,j] = 1} assign[i] >= d[j];

# equivalent to:
# staff_req{j in days}:
  #sum{i in shifts} a[i,j]*assign[i] >= d[j];

# Objective
minimize payroll_cost : sum{i in shifts, j in days : a[i,j] = 1} pay[j]*assign[i];

Overwriting employee_sch.mod

p = [200, 200, 200, 200, 200, 300, 300]  # pay
d = [177, 134, 158, 191, 149, 165, 116]  # staff lev

ampl.eval("reset;")
ampl.read("employee_sch.mod")
ampl.param["num_shifts"] = 21
ampl.param["d"] = d
ampl.param["pay"] = p

shift = [*range(0, 21)]
day = [*range(0, 7)]
# fill availability with a dictionary, position (i,j) in 'a' becomes a[i][j]
ampl.param["a"] = {(i, j): a[i][j] for i in shift for j in day}

# visualize the model
# ampl.eval('expand;')
ampl.option["solver"] = "gurobi"
ampl.solve()
assign = ampl.var["assign"]

Gurobi 11.0.1: Gurobi 11.0.1: optimal solution; objective 246100
10 simplex iterations
1 branching node

Take a look at the results on number of employees on the payroll

#####################################################
#         Number of employees on each shift
#####################################################

print(f"\n\n___Optimal employees on each shift________")
total_employee = 0
for t in shift:
    print("The number of employee on shift %2d is %3d" % (t, assign[t].value()))
    # print(f"The number of employee on shift {t} is {x[t].x}")
    total_employee += assign[t].value()

print("The total number of emploee is %3d " % (total_employee))

___Optimal employees on each shift________
The number of employee on shift  0 is   0
The number of employee on shift  1 is   0
The number of employee on shift  2 is  10
The number of employee on shift  3 is   0
The number of employee on shift  4 is   0
The number of employee on shift  5 is  31
The number of employee on shift  6 is  37
The number of employee on shift  7 is   0
The number of employee on shift  8 is  46
The number of employee on shift  9 is   0
The number of employee on shift 10 is   1
The number of employee on shift 11 is   0
The number of employee on shift 12 is  23
The number of employee on shift 13 is   0
The number of employee on shift 14 is   0
The number of employee on shift 15 is   0
The number of employee on shift 16 is   0
The number of employee on shift 17 is  17
The number of employee on shift 18 is   0
The number of employee on shift 19 is   0
The number of employee on shift 20 is  53
The total number of emploee is 218 

Take a look at the staffing coverage for each day of the week.

#####################################################
#     Actual coverage on each day
#####################################################

print(f"\n\n____Actual coverage on each day_____")
for t in day:
    actual_employee = 0
    for s in shift:
        actual_employee += assign[s].value() * a[s][t]
    print(
        "The number of employee on shift %1d is %3d where demand is %3d"
        % (t, actual_employee, d[t])
    )

____Actual coverage on each day_____
The number of employee on shift 0 is 177 where demand is 177
The number of employee on shift 1 is 134 where demand is 134
The number of employee on shift 2 is 158 where demand is 158
The number of employee on shift 3 is 191 where demand is 191
The number of employee on shift 4 is 149 where demand is 149
The number of employee on shift 5 is 165 where demand is 165
The number of employee on shift 6 is 116 where demand is 116

###A variant of the model where employees must take two consequtive days off.

The mathematical model remains identical, where the only change is the availability table: instead of C(7,2)=21 rows, we now only have C(7,1)=7 rows. See below for details. Thus, there is no need to setup a separate mathematical model.

First compute the availability table.

# assuming employees must take two consequtive days off
# compute availability table
# w is the length of the shift, d is number of days off
def schedule(w, d):
    s = [[1 for x in range(w)] for x in range(w)]
    i = 0
    for j in range(w):
        s[i][j] = 0
        s[i][(j + 1) % w] = 0
        i = i + 1
    return s

Generate the availability table and take a look.

# generate the schedule availability table
a = schedule(7, 2)

# print the table to visualize
print(np.matrix(a))

[[0 0 1 1 1 1 1]
 [1 0 0 1 1 1 1]
 [1 1 0 0 1 1 1]
 [1 1 1 0 0 1 1]
 [1 1 1 1 0 0 1]
 [1 1 1 1 1 0 0]
 [0 1 1 1 1 1 0]]

Setup the model

ampl.eval("reset data;")

ampl.param["num_shifts"] = 7
ampl.param["d"] = d
ampl.param["pay"] = p

# new schedule, only 7 shifts
shift = [*range(0, 7)]
day = [*range(0, 7)]
# fill availability with a dictionary, position (i,j) in 'a' becomes a[i][j]
ampl.param["a"] = {(i, j): a[i][j] for i in shift for j in day}

# visualize the model
# ampl.eval('expand;')
ampl.option["solver"] = "highs"
ampl.solve()
assign = ampl.var["assign"]

HiGHS 1.7.0: HiGHS 1.7.0: optimal solution; objective 259100
8 simplex iterations
1 branching nodes

Take a look at the number of employees hired.

#####################################################
#         Number of employees on each shift
#####################################################

print(f"\n\n___Optimal employees on each shift________")
total_employee = 0
for t in shift:
    print("The number of employee on shift %2d is %3d" % (t, assign[t].value()))
    # print(f"The number of employee on shift {t} is {x[t].x}")
    total_employee += assign[t].value()

print("The total number of emploee is %3d " % (total_employee))

___Optimal employees on each shift________
The number of employee on shift  0 is   3
The number of employee on shift  1 is  73
The number of employee on shift  2 is   0
The number of employee on shift  3 is  40
The number of employee on shift  4 is   0
The number of employee on shift  5 is  66
The number of employee on shift  6 is  49
The total number of emploee is 231 

Take a look at the actual coverage.

#####################################################
#     Actual coverage on each day
#####################################################

print(f"\n\n____Actual coverage on each day_____")
for t in day:
    actual_employee = 0
    for s in shift:
        actual_employee += (assign[s].value()) * a[s][t]
    print(
        "The number of employee on shift %1d is %3d where demand is %3d"
        % (t, actual_employee, d[t])
    )

____Actual coverage on each day_____
The number of employee on shift 0 is 179 where demand is 177
The number of employee on shift 1 is 155 where demand is 134
The number of employee on shift 2 is 158 where demand is 158
The number of employee on shift 3 is 191 where demand is 191
The number of employee on shift 4 is 191 where demand is 149
The number of employee on shift 5 is 165 where demand is 165
The number of employee on shift 6 is 116 where demand is 116

As we can see, when the employee schedules are less flexible (two consequtive days off), the company needs to hire more people to satisfy daily demand. This is consistent with the theoretical predication: when more constraints are imposed, the objective can only get worse.

Conclusion¶

In this example, we addressed the employee scheduling problem. We determined the optimal number of employee to:

Satisfy demand for each day,
Minimize the total number of employees, and
Find number of employees to place in each shift.

We also consider variations of the model where employees must take two conseutive days off.

Our employee scheduling model can be used by many organizations to help make informed decisions about which shifts and how many employees to have in order to satisfy daily demand while minimizing the number of employees on the payroll.

References¶

[1] Sixty examples of business optimization models. https://ytyimin.github.io/tart-cherry/.

[2] AMPL python reference. https://amplpy.readthedocs.io/en/latest/reference.html

[3] This notebook is developed by Yimin Wang. If you have any suggestions or comments, please contact yimin_wang@asu.edu. Marcos Dominguez (marcos@ampl.com) also contributed to this notebook content.

Efficient Frontier with Google Sheets

Financial Portfolio Optimization with amplpy