You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
I've been working on a workforce scheduling problem using linear programming in Python with the PuLP library. I'm trying to assign employees to different brands, ensuring certain conditions are met. Here's a detailed explanation of the problem and the code I've implemented:
Problem Statement:
Assign a fixed number of employees to different brands.
Ensure that an employee works on only one brand per day.
An employee can work a maximum of 9 hours and a minimum of 5 hours consecutively.
Need to fulfill staffing requirements for each brand.
Code:
# ImportsimportpulpfrompulpimportLpMinimize, LpProblem, LpVariable, lpSum, LpMaximizefrompulp.apisimportPULP_CBC_CMDimportpandasaspd# Variable definition# Define datanumber_of_weeks=1days_per_week=7total_days=number_of_weeks*days_per_weekdays=list(range(1, total_days+1))
shop_open=10# 10 AMshop_close=20# 8 PMhours=list(range(shop_open, shop_close))
max_working_hours=9min_working_hours=5number_of_employee=20# 5-day or 4-day contract type (50% each for now)five_days_count=int(number_of_employee*0.5)
employees=list(range(1, number_of_employee+1))
employee_type= ["5_days"ife<=five_days_countelse"4_days"foreinemployees]
categories= ["PHONE", "TV"]
brands= {
"PHONE": ["PHONE1", "PHONE2"],
"TV": ["TV1", "TV2", "TV3"]
}
list_of_brands= []
forkey, valuesinbrands.items():
list_of_brands.extend(values)
staffing_requirements= {
"PHONE": {"PHONE1": 1, "PHONE2": 1},
"TV": {"TV1": 1, "TV2": 1, "TV3": 1}
}
flat_staffing_requirements= {brand: reqforcategoryinstaffing_requirementsforbrand, reqinstaffing_requirements[category].items()}
# Initialize the problemmodel=LpProblem(name="workforce-planning", sense=LpMinimize)
# Variables# Work on a day for a brand on a specific hourx=LpVariable.dicts("x", [(e, d, h, b) foreinemployeesfordindaysforhinhoursforbinlist_of_brands], cat="Binary")
# Work on a day for a brandy=LpVariable.dicts("y", [(e, d, b) foreinemployeesfordindaysforbinlist_of_brands], cat="Binary")
# Gapg=LpVariable.dicts("g", [(e, d, h, b) foreinemployeesfordindaysforhinhoursforbinlist_of_brands], cat="Binary")
# Objective: Minimize employees working per daymodel+=lpSum(x[e, d, h, b] foreinemployeesfordindaysforhinhoursforbinlist_of_brands)
# An employee can only work on one brand of a category per dayforeinemployees:
fordindays:
# For each employee and day, the sum of all brands they work for should be at most 1. # This ensures that an employee works for only one brand a day.model+=lpSum(y[e, d, b] forbinlist_of_brands) <=1# Connect x to yforeinemployees:
fordindays:
forbinlist_of_brands:
# If y is 1, then the employee can work for that brand up to max_working_hours.# If y is 0, then they don't work for that brand.model+=lpSum(x[e, d, h, b] forhinhours) <=max_working_hours*y[e, d, b]
# If the employee works any hour for that brand, then y must be 1.# This ensures that if an employee is working, they are assigned to a brand.model+=lpSum(x[e, d, h, b] forhinhours) >=y[e, d, b]
foreinemployees:
fordindays:
forbinlist_of_brands:
fori, hinenumerate(hours):
# 1. If a sequence begins at hour h, the following hours within max_working_hours (or until the end of the day) # must also be worked hours. This ensures consecutive hours.max_hrs=min(len(hours) -i, max_working_hours)
forjinrange(max_hrs):
ifi+j<len(hours):
# This constraint enforces that if g is 1 (sequence starts at hour h), # the following hours are set to work hours.model+=x[e, d, hours[i+j], b] >=g[e, d, h, b]
# 2. If an employee works at a certain hour h, then a work sequence must have started # at that hour or some previous hour within the range of max_working_hours. This # constraint ties together the concept that a worked hour is part of some sequence.# The sum checks for all possible starting hours of the sequence leading up to hour h.model+=x[e, d, h, b] <=lpSum(g[e, d, hours[i-k], b] forkinrange(min(i+1, max_working_hours)))
# Staffing requirements for each hourfordindays:
forhinhours:
forbinlist_of_brands:
model+=lpSum(x[e, d, h, b] foreinemployees) ==flat_staffing_requirements[b]
# Solve the modelmodel.solve(PULP_CBC_CMD(msg=1))
# Create an empty DataFrame with the desired structurecolumns= []
fordindays:
columns.extend([f"Day_{d}_Start", f"Day_{d}_End", f"Day_{d}_Brand"])
df=pd.DataFrame(index=employees, columns=columns)
# Populate the DataFrameforeinemployees:
fordindays:
assigned_brand=Nonestart_time=None# Resetting for each employee and day combinationend_time=None# Resetting for each employee and day combinationforhinhours:
forbinlist_of_brands:
ifx[e, d, h, b].varValue==1:
assigned_brand=bifstart_timeisNone: # First assignment for this day for this employeestart_time=hend_time=h+1else:
start_time=min(start_time, h)
end_time=max(end_time, h+1) # h+1 because if they start at a particular hour, they work that entire hour# Use 'REST' if no assignment is detecteddf.loc[e, f"Day_{d}_Start"] =start_timeifassigned_brandelse"REST"df.loc[e, f"Day_{d}_End"] =end_timeifassigned_brandelse"REST"df.loc[e, f"Day_{d}_Brand"] =assigned_brandifassigned_brandelse"REST"df.head(30)
The provided code works and provides an optimal solution when I don't consider the 5 hours minimum working constraint. The execution time is 17s, which seems a bit long for the dataset size. Here's a sample output:
Day_1_Start
Day_1_End
Day_1_Brand
19
20
TV1
10
19
TV1
...
...
...
However, when I add the constraint to ensure a minimum of 5 hours of work, the problem becomes infeasible. Here are the changes I made to the original code :
# Connect x to yforeinemployees:
fordindays:
forbinlist_of_brands:
# If y is 1, then the employee can work for that brand up to max_working_hours.# If y is 0, then they don't work for that brand.model+=lpSum(x[e, d, h, b] forhinhours) <=max_working_hours*y[e, d, b]
model+=lpSum(x[e, d, h, b] forhinhours) >=min_working_hours*y[e, d, b]
# If the employee works any hour for that brand, then y must be 1.# This ensures that if an employee is working, they are assigned to a brand.model+=lpSum(x[e, d, h, b] forhinhours) >=y[e, d, b]
foreinemployees:
fordindays:
forbinlist_of_brands:
fori, hinenumerate(hours[:-4]): # Exclude the last 4 hours to prevent a sequence that doesn't respect the 5-hour minimum# If a sequence starts at hour h, then the next 4 hours should also be worked hours to ensure 5 consecutive hours.forjinrange(5): # 5 hours including the current hourmodel+=x[e, d, hours[i+j], b] >=g[e, d, h, b]
# 2. If an employee works at a certain hour h, then a work sequence must have started # at that hour or some previous hour within the range of max_working_hours. This # constraint ties together the concept that a worked hour is part of some sequence.# The sum checks for all possible starting hours of the sequence leading up to hour h.model+=x[e, d, h, b] <=lpSum(g[e, d, hours[i-k], b] forkinrange(min(i+1, max_working_hours)))
When adding the 5-hour minimum working constraint, the problem turns infeasible, and I'm unsure why. I'd appreciate any insights or corrections on the approach or code. Thank you!
I have posted this on stackoverflow aswell.
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
-
I've been working on a workforce scheduling problem using linear programming in Python with the
PuLP
library. I'm trying to assign employees to different brands, ensuring certain conditions are met. Here's a detailed explanation of the problem and the code I've implemented:Problem Statement:
Code:
The provided code works and provides an optimal solution when I don't consider the 5 hours minimum working constraint. The execution time is 17s, which seems a bit long for the dataset size. Here's a sample output:
However, when I add the constraint to ensure a minimum of 5 hours of work, the problem becomes infeasible. Here are the changes I made to the original code :
When adding the 5-hour minimum working constraint, the problem turns infeasible, and I'm unsure why. I'd appreciate any insights or corrections on the approach or code. Thank you!
I have posted this on stackoverflow aswell.
Beta Was this translation helpful? Give feedback.
All reactions