Solving Staff Scheduling Problem using Linear Programming

Learn how to use Linear Programming to solve Staff Scheduling problems.

As Senior operation manager, your job is to optimize scarce resources, improve productivity, reduce cost and maximize profit. For example, scheduling workers’ shifts for the most effective utilization of manpower. We need to consider the various restrictions of the total working hours of each employee, the number of shifts, shift hours, and other constraints. Such a problem can be considered an optimization problem.

Staff or workforce scheduling is used in numerous use-cases like nurse staff scheduling in a hospital, air flight scheduling, staff scheduling in the hotel, and scheduling of drivers. Such schedules can be created based on various time periods like hours, days, weeks, and months. Various organizations use spreadsheets and software. Poorly managed schedule causes overlapping of employee allocation, no breaks between shifts. Ultimately it will cause poor employee performance. For effective workforce scheduling, we need to consider the number of constraints and formulate them in the right manner. Workforce scheduling will help in effective human resource utilization, balanced timing, balanced workload, reduce employee fatigue and give importance to individual preferences (link).

Linear programming is a mathematical model for optimizing the linear function. We can achieve the best results using linear programming for a given specific set of constraints. Linear programming is widely used in management and economic science problems such as production planning, network routing, resource scheduling, and resource allocation. Linear programming can also be helpful in scheduling human resources. Such type of problem is known as Staff Scheduling or Workforce Scheduling problems.

In this tutorial, we are going to cover the following topics:

Staff Scheduling Problem

In this problem, a saloon owner wants to determine the schedule for staff members. The staff consists of the full-time shift of 9 hours and part-time shift of 3 hours.  The saloon’s opening hours are divided into 4 shifts of 3 hours each. In each shift, different levels of demands are there that need the different number of staff members in each shift.

The required number of nurses for each shift is mentioned in the below table:

There is at least 1 full-time employee we need in each shift. The full-time employee will get $150 for 9 hours shift and the part-time employee will get $45 per shift.

Modeling Linear Programming Using Python PuLP

PuLP is an open-source library in Python for solving linear programming problems. In order to solve linear programming problems using PuLP, we need to formulate the objective function. PuLP will optimize to maximize or minimize the objective function. PuLP modeling process has the following steps for solving LP problems:

• Initialize Model
• Define Decision Variable
• Define Objective Function
• Define the Constraints
• Solve Model

Understand the problem

Decision Variables

x_i = Number of full-time employees scheduled in shift i.

y_i = number of part-time employees scheduled in shift i.

Objective Function:

minimize Z= 150( x₀ + x₁ + x₂ + x₃ ) + 45( y₀ + y₁ + y₂ + y₃ )

Constraints 1:

• Employee starting shift constraints

x₀ + y₀ ≥ 6

x₀ + x₁ + y₁ ≥ 8

x₁ + x₂ + y₂ ≥ 11

x₂ + x₃ + y₃ ≥ 6

Constraints 2:

• Minimum full-time employees during any shift/period

x₀ ≥ 1

x₁ ≥ 1

x₂ ≥ 1

Initialize LP Model

In this step, we will import all the classes and functions of pulp module and create a Minimization LP problem using LpProblem class.

# Import all classes of PuLP module
from pulp import *

# Initialize Class
model = LpProblem("StaffSchedulingProblem", LpMinimize)

# Create Shifts
shifts = list(range(4))

Define Decision Variable

In this step, we will define the decision variables. In our problem, we have three variables wood tables, chairs, and bookcases. Let’s create them using LpVariable.dicts() class. LpVariable.dicts() used with Python’s list comprehension. LpVariable.dicts() will take the following four values:

• First, prefix name of what this variable represents.
• Second is the list of all the variables.
• Third is the lower bound on this variable.
• Fourth variable is the upper bound.
• Fourth is essentially the type of data (discrete or continuous). The options for the fourth parameter are LpContinuous or LpInteger.

# Define Decision Variables
x = LpVariable.dicts('fulltimeshift_', shifts, lowBound=0, cat='Integer')
y = LpVariable.dicts('parttimeshift_', shifts, lowBound=0, cat='Integer')

Define Objective Function

In this step, we will define the minimum objective function by adding it to the LpProblem object. lpSum(vector) is used here to define multiple linear expressions. It also used list comprehension to add multiple variables.

# Define Objective
model += 150 * lpSum([x[i] for i in shifts]) + 45 * lpSum([y[i] for i in shifts])

In this code, we have summed up the two variables(full-time and part-time) list values in an additive fashion.

Define the Constraints

Here, we are adding two types of constraints: employee starting shift constraints and minimum full-time employees during any period. We have added the 4 constraints defined in the problem by adding them to the LpProblem object.

# Define Constraints: For Employee starting the shift
model += x[0]+y[0]>=6
model += x[0]+x[1]+y[1]>=8
model += x[1]+x[2]+y[2]>=11
model += x[2]+x[3]+y[3]>=6

# Define Constraints: At least full-time employee during any shift
model += x[0]>=1
model += x[1]>=1
model += x[2]>=1

Solve Model

In this step, we will solve the LP problem by calling solve() method. We can print the final value by using the following for loop.

# The problem is solved using PuLP's choice of Solver
model.solve()

# Print the variables optimized value
for v in model.variables():
    print(v.name, "=", v.varValue)
    
# The optimised objective function value is printed to the screen
print("Total Cost of Staff = ", value(model.objective))

Output:
fulltimeshift__0 = 1.0
fulltimeshift__1 = 1.0
fulltimeshift__2 = 1.0
fulltimeshift__3 = 0.0
parttimeshift__0 = 5.0
parttimeshift__1 = 6.0
parttimeshift__2 = 9.0
parttimeshift__3 = 5.0

Total Cost of Staff =  1575.0

Summary

In this article, we have learned about Staff Scheduling problems, Problem Formulation, and implementation in the python PuLp library. We have solved the staff scheduling problem using a Linear programming problem in Python. Of course, this is just a simple case study, we can add more constraints to it and make it more complicated. In upcoming articles, we will write more on different optimization problems and its solution using Python. You can revise the basics of mathematical concepts in this article and learn about Linear Programming in this article.