The Workforce Scheduling Problem#
Optimization Model for Workforce Scheduling
The workforce scheduling problem is a common challenge faced by organizations across various industries, particularly those with large and diverse teams. At its core, it involves efficiently assigning tasks, shifts, or projects to employees while considering various constraints and objectives. These constraints may include labor regulations, employee preferences, skill levels, shift availability, and operational requirements
Problem Definition
This example focuses on addressing a workforce scheduling problem in a manufacturing workshop by creating and solving a mathematical model to optimize operations. The objective is to determine the ideal number of workers and their types while ensuring operational efficiency, meeting workstation demands, controlling labor costs, and maintaining employee satisfaction.
This workshop operates seven days a week with two shifts per day, requiring specific numbers of eligible workers for each workstation.
Two types of workers are available: temporary and contractual. Temporary workers can be assigned to any workstation without eligibility concerns and are hired per shift at a cost of 300 Euros per shift.
Contractual workers must work five shifts per week, with eligibility for specific workstations considered during recruitment, and incur a cost of 150 Euros per shift. Legal regulations limit workers to eight hours per day and prevent them from working consecutive shifts, also imposing a maximum number of shifts per week as five.
The problem formulation involves a workshop with four workstations, each requiring four workers to operate efficiently over a seven-day planning horizon with two shifts per day.
Libraries
To begin, we install and import the necessary libraries.
pip install quantagonia
import numpy as np
import pandas as pd
import random
from pulp import *
from quantagonia import HybridSolverParameters
import quantagonia.mip.pulp_adapter as pulp_adapter
API_KEY = "Your-API-KEY" # if you don't have one, head over to https://platform.quantagonia.com/ (free account available)
Problem Parameters
NUM_WORKERS: Number of Available Workers
NUM_WORKSTATIONS: Number of Workstations in the Workshop
NUM_WEEKLY_WORKING_DAYS: Number of Days that the Workshop Operates
NUM_DAILY_SHIFT: Number of Shifts that the Workshop Operates
DEMAND: Demand of the workstation in a particular day and shift
REQUIRED_SHIFTS: Number of shifts that a contractual worker have to work within a week
COST_CONTRACTUAL: Shift cost of a contractual worker
COST_TEMPORARY: Shift cost of a temporary worker
PARAM_ELIGIBLE\(_{i, j}\): If contractual worker \(i\) is eligible to work in workstation \(j\) then 1, otherwise 0 (Binary Matrix)
Note that: The PARAM_ELIGIBLE matrix is created assuming that every worker is eligible to work at two randomly assigned stations.
Other possible parameters to consider could be the skill level of workers and specific days workers are available. However, in this tutorial, we will focus on the parameters mentioned above.
# PARAMETERS
NUM_WORKERS = 100 # Number of Available Workers
NUM_WORKSTATIONS = 4 ## Number of Workstations in the Workshop
NUM_WEEKLY_WORKING_DAYS = 7 ## Number of Days that the Workshop Operates within a Week --> Maximum 7
NUM_DAILY_SHIFT = 2 ## Number of Shifts that the Workshop Operates
DEMAND = 4 ## Demand of each workstation in a single day and single shift
REQUIRED_SHIFTS = 5 ## Number of shifts that a contractual worker have to work within a week
COST_CONTRACTUAL = 150 ## Shift cost of a contractual worker
COST_TEMPORARY = 300 ## Shift cost of a temporary worker
### If contractual worker i is eligible to work in workstation j then 1, otherwise 0 (Binary Matrix)
PARAM_ELIGIBLE = np.zeros((NUM_WORKERS,NUM_WORKSTATIONS))
## Assume that every worker is eligible to work 2 different station
np.random.seed(0)
for i in range(NUM_WORKERS):
rondom_stations = np.random.choice(np.arange(0, NUM_WORKSTATIONS), size=2, replace=False)
PARAM_ELIGIBLE[i,rondom_stations[0]] = 1
PARAM_ELIGIBLE[i,rondom_stations[1]] = 1
Sets and Indices
\(i \in W = {0,1,..,\text{NumWorkers}}\) : Worker Indices
\(j \in WS = {0,1,..,\text{NumWorkstations}}\) : Workstation Indices
\(g \in D = {0,1,..,\text{NumWeeklyWorkingDay}}\) : Working Day Indices
\(n \in S = {0,..,\text{NumDailyShift}}\) : Shift Indices
# SETS
workerset = list(range(NUM_WORKERS)) ## Number of Workers (Currently max 63) # i
workstations = list(range(NUM_WORKSTATIONS)) ## Number of Workstations #j
weekdays = list(range(NUM_WEEKLY_WORKING_DAYS)) ## Number of days #g
shifts = list(range(NUM_DAILY_SHIFT)) ## List of Shift #n
Decision Variables
\(cw_{i, j, g, n} \in \{0, 1\}\): if Contractual Worker \(i\) is on duty at workstation \(j\) day \(g\) and shift \(n\), it is 1, otherwise 0.
\(\text{isHired}_{i} \in \{0, 1\}\): if Contractual Worker \(i\) is hired for whole week, it is 1, otherwise 0.
\(tw_{j, g, n} \in \mathbb{Z}^+\): Number of temporary workers hired for station \(j\), on day \(g\), shift \(n\)
#DECISION VARIABLES
### ContractualWorker variable --> BINARY --> , if Contractual Worker i is on duty at workstation j day g and shift n =1, otherwise 0
cw = []
for i in workerset:
cw.append([])
for j in workstations:
cw[i].append([])
for g in weekdays:
cw[i][j].append([])
for n in shifts:
cw[i][j][g].append(LpVariable(name = 'ContractualWorker(%d,%d,%d,%d)' % (i,j,g,n), cat='Binary'))
### If ContractualWorker i hired, it is 1 otherwise 0 --> BINARY --> if Contractual Worker i is hired for whole week 1, otherwise 0
isHired = []
for i in workerset:
isHired.append(LpVariable(name = 'isHired(%d)' % (i), cat='Binary'))
### Temporary worker variable --> Integer --> Number of temporary workers hired for station j, on day g, shift n
tw = []
for j in workstations:
tw.append([])
for g in weekdays:
tw[j].append([])
for n in shifts:
tw[j][g].append(LpVariable(name = 'TemporaryWorker(%d,%d,%d)' % (j,g,n), lowBound=0, cat='Integer'))
Objective Function
The objective function is minimizing the total cost.
When a contractual worker is hired, a direct cost of five shifts is incurred. Therefore, we calculate this cost by multiplying COST_CONTRACTUAL by the REQUIRED_SHIFTS and by summed isHired variable. Conversely, costs for temporary workers are incurred based solely on the total count of shifts.
prob = LpProblem("Schedule_Workforce", LpMinimize)
### OBJECTIVE FUNCTION
prob += (COST_CONTRACTUAL*REQUIRED_SHIFTS*lpSum(isHired[i] for i in workerset)
+ COST_TEMPORARY*lpSum(tw[j][g][n] for j in workstations for g in weekdays for n in shifts))
Constraints
Constraint 1:
Each Contractual Worker have to work REQUIRED_SHIFTS shifts in a week if they are hired.
Constraint 2:
Each Contractual Worker can work in one workstation in at the same time.
Constraint 3a:
Each Contractual Worker cannot work more than one shift in a same day.
Constraint 3b:
A Contractual Worker cannot work in consecutive shifts.
Constraint 4:
Demand Constraint for the Workstations
Constraint 5:
Each hired Contractual Worker should work in an eligible workstation
### CONSTRAINTS
# Constraint 1: Each Contractual Worker have to work REQUIRED_SHIFTS shifts in a week if they are hired
for i in workerset:
prob += (lpSum(cw[i][j][g][n] for j in workstations for g in weekdays for n in shifts)
== REQUIRED_SHIFTS*isHired[i], f"Constraint1_{i}")
# Constraint 2: Each Contractual Worker can work in one workstation in at the same time
for i in workerset:
for g in weekdays:
for n in shifts:
prob += (lpSum(cw[i][j][g][n] for j in workstations)
<=1, f"Constraint2_{i,g,n}")
# Constraint 3a: Each Contractual Worker cannot work 2 shift in a same day
for i in workerset:
for g in weekdays:
prob += (lpSum(cw[i][j][g][n] for n in shifts for j in workstations)
<=1, f"Constraint3a_{i,g}")
# Constraint 3b: A Contractual Worker cannot work in consecutive shifts
if NUM_DAILY_SHIFT>1:
for i in workerset:
for g in range(len(weekdays)-1):
prob += (lpSum(cw[i][j][g][NUM_DAILY_SHIFT-1] + cw[i][j][g+1][0] for j in workstations)
<=1, f"Constraint3b_{i,g}")
# Constraint 4: Demand Constraint for the Workstations
for j in workstations:
for g in weekdays:
for n in shifts:
prob += (lpSum(cw[i][j][g][n] for i in workerset)
+ tw[j][g][n] == DEMAND, f"Constraint4_{j,g,n}")
# Constraint 5: Each hired Contractual Worker should work in an eligible workstation
for i in workerset:
for j in workstations:
for g in weekdays:
for n in shifts:
prob += (cw[i][j][g][n]<=
PARAM_ELIGIBLE[i,j] ,f"Constraint5_{i,j,g,n}")
Defining Solver Parameters and Solve the Poblem
params = HybridSolverParameters()
params.set_time_limit(600)
params.set_seed(0)
q_solver = pulp_adapter.HybridSolver_CMD(api_key=API_KEY, params=params)
status = prob.solve(solver=q_solver)
print("Status:",LpStatus[status],"\nObjective Function Value: %.2f"%prob.objective.value())
✔ Queued job with jobid 3e86d007-e39e-42df-ae63-f086e95fcfbe...
✔ Job 3e86d007-e39e-42df-ae63-f086e95fcfbe unqueued, processing...
Quantagonia HybridSolver version 1.1.1841
Copyright (c) 2024 Quantagonia GmbH.
HybridSolver integrates various open-source packages; see release notes.
User-specified parameters:
Set parameter 'time_limit' to value '600.0'.
Set parameter 'seed' to value '0'.
Read 28adbc49ed5c4453914f3fe48048bbbe-pulp.mps in 0.62s.
Minimize a MILP with 8456 constraints and 5756 variables (5700 binary, 56 integer, 0 implied integer,0 continuous).
Presolving model. Presolved model in 0.0s.
Reduced model has 1456 constraints and 2956 variables (2900 binary, 56 integer, 0 continuous).
------------------------------------------------------------------------
Nodes | Incumbent | Bound | Gap (%) | Time (s) |
------------------------------------------------------------------------
1 | inf | 0.00000000 | inf | 0.00 |
* 1 | 64200.0000 | 33600.0000 | 47.66 | 0.01 |
* 1 | 34200.0000 | 33600.0000 | 1.75 | 0.02 |
1 | 34200.0000 | 34200.0000 | 0.00 | 0.56 |
------------------------------------------------------------------------
Optimal solution found (within relative tolerance 0.01%).
Solver Results:
- Solution Status: Optimal
- Wall Time: 0.56 seconds
- Objective: 34200.0000
- Bound: 34200.0000
- Absolute Gap: 0.0
- Relative Gap: 0.0%
- Nodes: 1
- Best solution found at node 1 after 0.0197 seconds
Finished processing job 3e86d007-e39e-42df-ae63-f086e95fcfbe...
Optimal
Status: Optimal
Objective Function Value: 34200.00
Creating the Outputs of the Solution
# Extract Contractual Workers
resultcw = np.zeros((len(workerset),len(workstations),len(weekdays),len(shifts)))
contractual_schedule_df = pd.DataFrame(columns = ['Weekday','Shift','WorkstationId','WorkerId'])
for i in workerset:
for j in workstations:
for g in weekdays:
for n in shifts:
resultcw[i,j,g,n]=cw[i][j][g][n].varValue
if resultcw[i,j,g,n]>0.1:
new_row = ({'Weekday': g, 'Shift': n, 'WorkstationId': j, 'WorkerId': 'Contractual Worker '+str(i)})
contractual_schedule_df = pd.concat([contractual_schedule_df, pd.DataFrame([new_row])], ignore_index=True)
contractual_schedule_df.sort_values(by=['Weekday','Shift','WorkstationId'],inplace=True,ignore_index=True)
contractual_schedule_df['Weekday']=contractual_schedule_df['Weekday'].replace({0: 'Monday', 1: 'Tuesday',2: 'Wednesday',
3: 'Thursday',4: 'Friday',5: 'Saturday',6: 'Sunday'})
if NUM_DAILY_SHIFT==1 or NUM_DAILY_SHIFT==2 or NUM_DAILY_SHIFT==3:
contractual_schedule_df['Shift']=contractual_schedule_df['Shift'].replace({0: 'Morning', 1: 'Afternoon', 2: 'Night'})
for i in workstations:
contractual_schedule_df['WorkstationId']=contractual_schedule_df['WorkstationId'].replace({i: 'Station '+str(i)})
contractual_schedule_df= contractual_schedule_df.astype(str)
# Extract Which Contractual Workers are Hired
resultisHired = np.zeros(len(workerset))
for i in workerset:
resultisHired[i] = isHired[i].varValue
# Extract How Many Temp. Workers are Assigned on a day, shift and workstation
number_temporary_df = pd.DataFrame(columns = ['Weekday','Shift','WorkstationId','Number_of_Workers'])
resulttw = np.zeros((len(workstations),len(weekdays),len(shifts)))
for j in workstations:
for g in weekdays:
for n in shifts:
resulttw[j,g,n]=tw[j][g][n].varValue
if resulttw[j,g,n]>0.1:
new_row = ({'Weekday': g, 'Shift': n, 'WorkstationId': j, 'Number_of_Workers': int(round(resulttw[j,g,n]))})
number_temporary_df = pd.concat([number_temporary_df, pd.DataFrame([new_row])], ignore_index=True)
if len(number_temporary_df) !=0:
number_temporary_df.sort_values(by=['Weekday','Shift','WorkstationId'],inplace=True,ignore_index=True)
number_temporary_df['Weekday']=number_temporary_df['Weekday'].replace({0: 'Monday', 1: 'Tuesday',2: 'Wednesday',
3: 'Thursday',4: 'Friday',5: 'Saturday',6: 'Sunday'})
if NUM_DAILY_SHIFT==1 or NUM_DAILY_SHIFT==2 or NUM_DAILY_SHIFT==3:
number_temporary_df['Shift']=number_temporary_df['Shift'].replace({0: 'Morning', 1: 'Afternoon', 2: 'Night'})
for i in workstations:
number_temporary_df['WorkstationId']=number_temporary_df['WorkstationId'].replace({i: 'Station ' + str(i)})
number_temporary_df = number_temporary_df.astype(str)
## Print the General Results
print("Total Number of Temporary Workers assigned to shifts: ",np.sum(resulttw))
print("Total Number of Contractual Workers: ",np.sum(resultisHired))
print("Total Operating Cost of the Workshop: ",prob.objective.value())
Total Number of Temporary Workers assigned to shifts: 4.0
Total Number of Contractual Workers: 44.0
Total Operating Cost of the Workshop: 34200.0
Results and Outcomes
In summary, the findings of this study reveal that by hiring 44 contractual workers and strategically assigning them five shifts per week, with 4 temporary worker that work for only a specific workstation for additional flexibility, the workshop can efficiently utilize its paid workforce potential. This optimal solution not only meets the demand requirements for each workstation but also ensures legal regulations about workers’ shift limits and consecutive working days are met. Additionally, the model considers the eligibility of contractual workers for specific workstations.
Below, you can see the schedule of the contractual workers and a separate table showing the number of temporary workers needed for the week.
contractual_schedule_df['Weekday_Shift'] = contractual_schedule_df['Weekday'] + ' ' + contractual_schedule_df['Shift']
# Pivot the data
pivot_df = contractual_schedule_df.pivot(index='WorkerId', columns='Weekday_Shift', values='WorkstationId')
if NUM_DAILY_SHIFT==1 or NUM_DAILY_SHIFT==2 or NUM_DAILY_SHIFT==3:
order = ['Monday Morning', 'Monday Afternoon', 'Monday Night', 'Tuesday Morning', 'Tuesday Afternoon', 'Tuesday Night',
'Wednesday Morning', 'Wednesday Afternoon', 'Wednesday Night', 'Thursday Morning', 'Thursday Afternoon', 'Thursday Night',
'Friday Morning', 'Friday Afternoon', 'Friday Night', 'Saturday Morning', 'Saturday Afternoon', 'Saturday Night',
'Sunday Morning', 'Sunday Afternoon', 'Sunday Night']
pivot_df = pivot_df.reindex(columns=order)
pivot_df.dropna(axis=1, how='all',inplace=True)
pivot_df=pivot_df.fillna('')
# Function to apply conditional formatting
def color_cells(val):
if val == '' or val == '0':
color = 'background-color: #d4edda; font-weight: bold; border: 1px solid black;' # light green
else:
color = 'background-color: #fff3cd; font-weight: bold; border: 1px solid black;' # light yellow
return color
html_df = pivot_df.style.applymap(color_cells)#.set_table_styles([{'selector': 'th', 'props': [('border', '1px solid black')]}])
# Save the DataFrame to an HTML file then display it
html = html_df.to_html()
with open('styled_schedule.html', 'w') as f:
f.write(html)
from IPython.display import display, HTML
display(HTML(html))
Weekday_Shift | Monday Morning | Monday Afternoon | Tuesday Morning | Tuesday Afternoon | Wednesday Morning | Wednesday Afternoon | Thursday Morning | Thursday Afternoon | Friday Morning | Friday Afternoon | Saturday Morning | Saturday Afternoon | Sunday Morning | Sunday Afternoon |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
WorkerId | ||||||||||||||
Contractual Worker 0 | Station 3 | Station 3 | Station 3 | Station 2 | Station 3 | |||||||||
Contractual Worker 1 | Station 2 | Station 0 | Station 0 | Station 0 | Station 0 | |||||||||
Contractual Worker 13 | Station 2 | Station 2 | Station 2 | Station 2 | Station 0 | |||||||||
Contractual Worker 15 | Station 2 | Station 2 | Station 2 | Station 3 | Station 2 | |||||||||
Contractual Worker 17 | Station 3 | Station 1 | Station 3 | Station 3 | Station 3 | |||||||||
Contractual Worker 22 | Station 1 | Station 2 | Station 1 | Station 1 | Station 1 | |||||||||
Contractual Worker 23 | Station 1 | Station 1 | Station 1 | Station 2 | Station 1 | |||||||||
Contractual Worker 25 | Station 2 | Station 2 | Station 2 | Station 3 | Station 3 | |||||||||
Contractual Worker 28 | Station 0 | Station 1 | Station 0 | Station 0 | Station 1 | |||||||||
Contractual Worker 3 | Station 0 | Station 1 | Station 1 | Station 1 | Station 1 | |||||||||
Contractual Worker 32 | Station 2 | Station 2 | Station 2 | Station 1 | Station 2 | |||||||||
Contractual Worker 39 | Station 0 | Station 0 | Station 0 | Station 2 | Station 0 | |||||||||
Contractual Worker 42 | Station 3 | Station 3 | Station 1 | Station 1 | Station 3 | |||||||||
Contractual Worker 43 | Station 3 | Station 3 | Station 3 | Station 0 | Station 0 | |||||||||
Contractual Worker 44 | Station 3 | Station 2 | Station 2 | Station 2 | Station 3 | |||||||||
Contractual Worker 49 | Station 1 | Station 1 | Station 1 | Station 0 | Station 0 | |||||||||
Contractual Worker 53 | Station 0 | Station 0 | Station 3 | Station 0 | Station 0 | |||||||||
Contractual Worker 54 | Station 1 | Station 1 | Station 0 | Station 0 | Station 0 | |||||||||
Contractual Worker 55 | Station 3 | Station 1 | Station 3 | Station 3 | Station 3 | |||||||||
Contractual Worker 57 | Station 1 | Station 3 | Station 1 | Station 3 | Station 1 | |||||||||
Contractual Worker 6 | Station 0 | Station 1 | Station 1 | Station 1 | Station 0 | |||||||||
Contractual Worker 60 | Station 0 | Station 3 | Station 0 | Station 3 | Station 0 | |||||||||
Contractual Worker 61 | Station 3 | Station 0 | Station 3 | Station 3 | Station 3 | |||||||||
Contractual Worker 63 | Station 3 | Station 3 | Station 3 | Station 3 | Station 2 | |||||||||
Contractual Worker 64 | Station 2 | Station 1 | Station 1 | Station 1 | Station 1 | |||||||||
Contractual Worker 65 | Station 3 | Station 1 | Station 3 | Station 3 | Station 1 | |||||||||
Contractual Worker 69 | Station 1 | Station 3 | Station 3 | Station 3 | Station 3 | |||||||||
Contractual Worker 70 | Station 0 | Station 2 | Station 0 | Station 0 | Station 2 | |||||||||
Contractual Worker 73 | Station 2 | Station 3 | Station 2 | Station 2 | Station 2 | |||||||||
Contractual Worker 74 | Station 3 | Station 0 | Station 0 | Station 0 | Station 0 | |||||||||
Contractual Worker 76 | Station 1 | Station 2 | Station 2 | Station 2 | Station 2 | |||||||||
Contractual Worker 78 | Station 2 | Station 0 | Station 0 | Station 2 | Station 2 | |||||||||
Contractual Worker 8 | Station 3 | Station 2 | Station 3 | Station 2 | Station 3 | |||||||||
Contractual Worker 81 | Station 1 | Station 1 | Station 1 | Station 1 | Station 0 | |||||||||
Contractual Worker 82 | Station 2 | Station 0 | Station 0 | Station 0 | Station 0 | |||||||||
Contractual Worker 83 | Station 1 | Station 0 | Station 1 | Station 0 | Station 1 | |||||||||
Contractual Worker 84 | Station 3 | Station 2 | Station 2 | Station 3 | Station 2 | |||||||||
Contractual Worker 86 | Station 0 | Station 0 | Station 0 | Station 1 | Station 1 | |||||||||
Contractual Worker 87 | Station 1 | Station 0 | Station 1 | Station 1 | Station 1 | |||||||||
Contractual Worker 90 | Station 2 | Station 2 | Station 2 | Station 2 | Station 2 | |||||||||
Contractual Worker 91 | Station 0 | Station 3 | Station 3 | Station 3 | Station 0 | |||||||||
Contractual Worker 92 | Station 2 | Station 2 | Station 2 | Station 1 | Station 1 | |||||||||
Contractual Worker 98 | Station 1 | Station 3 | Station 3 | Station 3 | Station 1 | |||||||||
Contractual Worker 99 | Station 0 | Station 2 | Station 2 | Station 0 | Station 0 |
Number of Temporary Workers Needed:
if len(number_temporary_df) !=0:
number_temporary_df['Weekday_Shift'] = number_temporary_df['Weekday'] + ' ' + number_temporary_df['Shift']
tw_pivot_df = number_temporary_df.pivot(index='WorkstationId', columns='Weekday_Shift', values='Number_of_Workers')
if NUM_DAILY_SHIFT==1 or NUM_DAILY_SHIFT==2 or NUM_DAILY_SHIFT==3:
order = [
'Monday Morning', 'Monday Afternoon', 'Monday Night', 'Tuesday Morning', 'Tuesday Afternoon', 'Tuesday Night',
'Wednesday Morning', 'Wednesday Afternoon', 'Wednesday Night', 'Thursday Morning', 'Thursday Afternoon', 'Thursday Night',
'Friday Morning', 'Friday Afternoon', 'Friday Night', 'Saturday Morning', 'Saturday Afternoon', 'Saturday Night',
'Sunday Morning', 'Sunday Afternoon', 'Sunday Night']
tw_pivot_df = tw_pivot_df.reindex(columns=order)
tw_pivot_df.dropna(axis=1, how='all',inplace=True)
tw_pivot_df=tw_pivot_df.fillna('0')
tw_html_df = tw_pivot_df.style.applymap(color_cells)#.set_table_styles([{'selector': 'th', 'props': [('border', '1px solid black')]}])
# Save the DataFrame to an HTML file then display it
html = tw_html_df.to_html()
with open('styled_schedule.html', 'w') as f:
f.write(html)
from IPython.display import display, HTML
display(HTML(html))
else:
print('No Temporary Workers Needed')
Weekday_Shift | Monday Afternoon | Tuesday Afternoon | Wednesday Morning | Sunday Morning |
---|---|---|---|---|
WorkstationId | ||||
Station 0 | 0 | 0 | 1 | 0 |
Station 1 | 1 | 0 | 0 | 0 |
Station 2 | 0 | 1 | 0 | 1 |
Need help with modeling? We are happy to coach you through your model formulation. Reach out to us at help@quantagonia.com or https://www.quantagonia.com/contact.