自动化轮班时间，同时考虑约束
Automate shift times whilst accounting for constraints
我有一个脚本可以根据可用性和各种限制生成自动轮班时间。这些是：
- 在任何给定时间段，您必须满足最低人员配置要求
- 一个人有他们可以做的最小和最大小时数
- 只能安排员工在可用时间内工作
- 一个人每天只能工作一个班次
- 一个人最晚8点可以开始
为了提供流程概览，staff_availability df 包含可供选择的员工 ['Person']，他们可以工作的最短 - 最长工作时数 ['MinHours']-['MaxHours']，他们得到多少报酬 ['HourlyWage']，以及可用时间，以小时 ['Availability_Hr'] 和 15 分钟片段 ['Availability_15min_Seg'].
表示
staffing_requirements df 包含一天中的时间 ['Time'] 和这些时段所需的工作人员 ['People']。
脚本 returns a df 'availability_per_member' 显示每个时间点有多少员工可用。所以 1 表示可以安排， 0 表示不可用。然后，它旨在分配轮班时间，同时使用 pulp 来考虑约束。
我的问题是关于第 5 个约束。这是一个编码问题。我已经对此进行了注释，因此脚本可以正常工作。约束和错误贴在下面：
# Do not start people later than 8PM
for timeslot in timeslots:
prob += (sum([staffed[(timeslot, person)] for person in persons])
<= staffing_requirements.loc[person, 'Availability_Hr'] <= 52)
错误：
KeyError: 'the label [C11] is not in the [index]'
脚本：
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.dates as dates
staffing_requirements = pd.DataFrame({
'Time' : ['0/1/1900 8:00:00','0/1/1900 9:59:00','0/1/1900 10:00:00','0/1/1900 12:29:00','0/1/1900 12:30:00','0/1/1900 13:00:00','0/1/1900 13:02:00','0/1/1900 13:15:00','0/1/1900 13:20:00','0/1/1900 18:10:00','0/1/1900 18:15:00','0/1/1900 18:20:00','0/1/1900 18:25:00','0/1/1900 18:45:00','0/1/1900 18:50:00','0/1/1900 19:05:00','0/1/1900 19:07:00','0/1/1900 21:57:00','0/1/1900 22:00:00','0/1/1900 22:30:00','0/1/1900 22:35:00','1/1/1900 3:00:00','1/1/1900 3:05:00','1/1/1900 3:20:00','1/1/1900 3:25:00'],
'People' : [1,1,2,2,3,3,2,2,3,3,4,4,3,3,2,2,3,3,4,4,3,3,2,2,1],
})
staff_availability = pd.DataFrame({
'Person' : ['C1','C2','C3','C4','C5','C6','C7','C8','C9','C10','C11'],
'MinHours' : [5,5,5,5,5,5,5,5,5,5,5],
'MaxHours' : [10,10,10,10,10,10,10,10,10,10,10],
'HourlyWage' : [26,26,26,26,26,26,26,26,26,26,26],
'Availability_Hr' : ['8-18','8-18','8-18','9-18','9-18','9-18','12-1','12-1','17-3','17-3','17-3'],
'Availability_15min_Seg' : ['1-41','1-41','1-41','5-41','5-41','5-41','17-69','17-79','37-79','37-79','37-79'],
})
''' Generate availability at each point in time '''
staffing_requirements['Time'] = ['/'.join([str(int(x.split('/')[0])+1)] + x.split('/')[1:]) for x in staffing_requirements['Time']]
staffing_requirements['Time'] = pd.to_datetime(staffing_requirements['Time'], format='%d/%m/%Y %H:%M:%S')
formatter = dates.DateFormatter('%Y-%m-%d %H:%M:%S')
# 15 Min
staffing_requirements = staffing_requirements.groupby(pd.Grouper(freq='15T',key='Time'))['People'].max().ffill()
staffing_requirements = staffing_requirements.reset_index(level=['Time'])
staffing_requirements.index = range(1, len(staffing_requirements) + 1)
staff_availability.set_index('Person')
staff_costs = staff_availability.set_index('Person')[['MinHours', 'MaxHours', 'HourlyWage']]
availability = staff_availability.set_index('Person')[['Availability_15min_Seg']]
availability[['first_15min', 'last_15min']] = availability['Availability_15min_Seg'].str.split('-', expand=True).astype(int)
availability_per_member = [pd.DataFrame(1, columns=[idx], index=range(row['first_15min'], row['last_15min']+1))
for idx, row in availability.iterrows()]
availability_per_member = pd.concat(availability_per_member, axis='columns').fillna(0).astype(int).stack()
availability_per_member.index.names = ['Timeslot', 'Person']
availability_per_member = (availability_per_member.to_frame()
.join(staff_costs[['HourlyWage']])
.rename(columns={0: 'Available'}))
''' Generate shift times based off availability '''
import pulp
prob = pulp.LpProblem('CreateStaffing', pulp.LpMinimize) # Minimize costs
timeslots = staffing_requirements.index
persons = availability_per_member.index.levels[1]
# A member is either staffed or is not at a certain timeslot
staffed = pulp.LpVariable.dicts("staffed",
((timeslot, staffmember) for timeslot, staffmember
in availability_per_member.index),
lowBound=0,
cat='Binary')
# Objective = cost (= sum of hourly wages)
prob += pulp.lpSum(
[staffed[timeslot, staffmember] * availability_per_member.loc[(timeslot, staffmember), 'HourlyWage']
for timeslot, staffmember in availability_per_member.index]
)
# Staff the right number of people
for timeslot in timeslots:
prob += (sum([staffed[(timeslot, person)] for person in persons])
>= staffing_requirements.loc[timeslot, 'People'])
# Do not staff unavailable persons
for timeslot in timeslots:
for person in persons:
if availability_per_member.loc[(timeslot, person), 'Available'] == 0:
prob += staffed[timeslot, person] == 0
# Do not underemploy people
for person in persons:
prob += (sum([staffed[(timeslot, person)] for timeslot in timeslots])
>= staff_costs.loc[person, 'MinHours']*4) # timeslot is 15 minutes => 4 timeslots = hour
# Do not overemploy people
for person in persons:
prob += (sum([staffed[(timeslot, person)] for timeslot in timeslots])
<= staff_costs.loc[person, 'MaxHours']*4) # timeslot is 15 minutes => 4 timeslots = hour
# Do not start people later than 8PM
for timeslot in timeslots:
prob += (sum([staffed[(timeslot, person)] for person in persons])
<= staffing_requirements.loc[person, 'Availability_Hr'] <= 52)
# If an employee works and then stops, they can't start again
num_slots = max(timeslots)
for timeslot in timeslots:
if timeslot < num_slots:
for person in persons:
prob += staffed[timeslot+1, person] <= staffed[timeslot, person] + \
(1 - (1./num_slots) *
sum([staffed[(s, person)] for s in timeslots if s < timeslot]))
prob.solve()
print(pulp.LpStatus[prob.status])
output = []
for timeslot, staffmember in staffed:
var_output = {
'Timeslot': timeslot,
'Staffmember': staffmember,
'Staffed': staffed[(timeslot, staffmember)].varValue,
}
output.append(var_output)
output_df = pd.DataFrame.from_records(output)#.sort_values(['timeslot', 'staffmember'])
output_df.set_index(['Timeslot', 'Staffmember'], inplace=True)
if pulp.LpStatus[prob.status] == 'Optimal':
print(output_df)
评论里有人讨论这是OR问题还是python/pulp编码问题。我觉得两者兼而有之。
我不明白你的晚上 8 点后开始的无班次代码应该如何工作。这可能是因为我还没有看到你的数学公式（如评论中所建议的）。
我的做法如下 - 您不希望在晚上 8 点之后开始轮班。我假设这是您尝试这样做的时间段 52。鉴于您不允许拆分班次，我认为应用此约束的最简单方法是说（在伪代码中）
对于每个人，如果他们在晚上 8 点之前或之后没有空位，那么他们在晚上 8 点之后将不允许有任何空位。
在代码中：
for person in persons:
prob += pulp.lpSum([staffed[timeslot, person] for timeslot in timeslots if timeslot > 52]) <= \
pulp.lpSum([staffed[timeslot, person] for timeslot in timeslots if timeslot <= 52])*30
要了解这是如何工作的，请考虑这两种情况。
首先针对晚上 8 点或之前没有轮班的人（即 timeslot <= 52）。对于那个人，此约束的 right-hand-side 变为 <=0，因此在晚上 8 点后无法使用任何时段 (timeslot > 52)。
另一方面，如果在晚上 8 点之前安排了至少一个班次，则右侧变为 <=30（或者 <= 如果在晚上 8 点之前存在多个班次，则为更大的数字），因此约束为 non-active（晚上 8 点之后只有 27 个可能的时段，因此只要在此之前有一个时段工作，post-8PM 的工作就没有限制。
我有一个脚本可以根据可用性和各种限制生成自动轮班时间。这些是：
- 在任何给定时间段，您必须满足最低人员配置要求
- 一个人有他们可以做的最小和最大小时数
- 只能安排员工在可用时间内工作
- 一个人每天只能工作一个班次
- 一个人最晚8点可以开始
为了提供流程概览，staff_availability df 包含可供选择的员工 ['Person']，他们可以工作的最短 - 最长工作时数 ['MinHours']-['MaxHours']，他们得到多少报酬 ['HourlyWage']，以及可用时间，以小时 ['Availability_Hr'] 和 15 分钟片段 ['Availability_15min_Seg'].
staffing_requirements df 包含一天中的时间 ['Time'] 和这些时段所需的工作人员 ['People']。
脚本 returns a df 'availability_per_member' 显示每个时间点有多少员工可用。所以 1 表示可以安排， 0 表示不可用。然后，它旨在分配轮班时间，同时使用 pulp 来考虑约束。
我的问题是关于第 5 个约束。这是一个编码问题。我已经对此进行了注释，因此脚本可以正常工作。约束和错误贴在下面：
# Do not start people later than 8PM
for timeslot in timeslots:
prob += (sum([staffed[(timeslot, person)] for person in persons])
<= staffing_requirements.loc[person, 'Availability_Hr'] <= 52)
错误：
KeyError: 'the label [C11] is not in the [index]'
脚本：
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.dates as dates
staffing_requirements = pd.DataFrame({
'Time' : ['0/1/1900 8:00:00','0/1/1900 9:59:00','0/1/1900 10:00:00','0/1/1900 12:29:00','0/1/1900 12:30:00','0/1/1900 13:00:00','0/1/1900 13:02:00','0/1/1900 13:15:00','0/1/1900 13:20:00','0/1/1900 18:10:00','0/1/1900 18:15:00','0/1/1900 18:20:00','0/1/1900 18:25:00','0/1/1900 18:45:00','0/1/1900 18:50:00','0/1/1900 19:05:00','0/1/1900 19:07:00','0/1/1900 21:57:00','0/1/1900 22:00:00','0/1/1900 22:30:00','0/1/1900 22:35:00','1/1/1900 3:00:00','1/1/1900 3:05:00','1/1/1900 3:20:00','1/1/1900 3:25:00'],
'People' : [1,1,2,2,3,3,2,2,3,3,4,4,3,3,2,2,3,3,4,4,3,3,2,2,1],
})
staff_availability = pd.DataFrame({
'Person' : ['C1','C2','C3','C4','C5','C6','C7','C8','C9','C10','C11'],
'MinHours' : [5,5,5,5,5,5,5,5,5,5,5],
'MaxHours' : [10,10,10,10,10,10,10,10,10,10,10],
'HourlyWage' : [26,26,26,26,26,26,26,26,26,26,26],
'Availability_Hr' : ['8-18','8-18','8-18','9-18','9-18','9-18','12-1','12-1','17-3','17-3','17-3'],
'Availability_15min_Seg' : ['1-41','1-41','1-41','5-41','5-41','5-41','17-69','17-79','37-79','37-79','37-79'],
})
''' Generate availability at each point in time '''
staffing_requirements['Time'] = ['/'.join([str(int(x.split('/')[0])+1)] + x.split('/')[1:]) for x in staffing_requirements['Time']]
staffing_requirements['Time'] = pd.to_datetime(staffing_requirements['Time'], format='%d/%m/%Y %H:%M:%S')
formatter = dates.DateFormatter('%Y-%m-%d %H:%M:%S')
# 15 Min
staffing_requirements = staffing_requirements.groupby(pd.Grouper(freq='15T',key='Time'))['People'].max().ffill()
staffing_requirements = staffing_requirements.reset_index(level=['Time'])
staffing_requirements.index = range(1, len(staffing_requirements) + 1)
staff_availability.set_index('Person')
staff_costs = staff_availability.set_index('Person')[['MinHours', 'MaxHours', 'HourlyWage']]
availability = staff_availability.set_index('Person')[['Availability_15min_Seg']]
availability[['first_15min', 'last_15min']] = availability['Availability_15min_Seg'].str.split('-', expand=True).astype(int)
availability_per_member = [pd.DataFrame(1, columns=[idx], index=range(row['first_15min'], row['last_15min']+1))
for idx, row in availability.iterrows()]
availability_per_member = pd.concat(availability_per_member, axis='columns').fillna(0).astype(int).stack()
availability_per_member.index.names = ['Timeslot', 'Person']
availability_per_member = (availability_per_member.to_frame()
.join(staff_costs[['HourlyWage']])
.rename(columns={0: 'Available'}))
''' Generate shift times based off availability '''
import pulp
prob = pulp.LpProblem('CreateStaffing', pulp.LpMinimize) # Minimize costs
timeslots = staffing_requirements.index
persons = availability_per_member.index.levels[1]
# A member is either staffed or is not at a certain timeslot
staffed = pulp.LpVariable.dicts("staffed",
((timeslot, staffmember) for timeslot, staffmember
in availability_per_member.index),
lowBound=0,
cat='Binary')
# Objective = cost (= sum of hourly wages)
prob += pulp.lpSum(
[staffed[timeslot, staffmember] * availability_per_member.loc[(timeslot, staffmember), 'HourlyWage']
for timeslot, staffmember in availability_per_member.index]
)
# Staff the right number of people
for timeslot in timeslots:
prob += (sum([staffed[(timeslot, person)] for person in persons])
>= staffing_requirements.loc[timeslot, 'People'])
# Do not staff unavailable persons
for timeslot in timeslots:
for person in persons:
if availability_per_member.loc[(timeslot, person), 'Available'] == 0:
prob += staffed[timeslot, person] == 0
# Do not underemploy people
for person in persons:
prob += (sum([staffed[(timeslot, person)] for timeslot in timeslots])
>= staff_costs.loc[person, 'MinHours']*4) # timeslot is 15 minutes => 4 timeslots = hour
# Do not overemploy people
for person in persons:
prob += (sum([staffed[(timeslot, person)] for timeslot in timeslots])
<= staff_costs.loc[person, 'MaxHours']*4) # timeslot is 15 minutes => 4 timeslots = hour
# Do not start people later than 8PM
for timeslot in timeslots:
prob += (sum([staffed[(timeslot, person)] for person in persons])
<= staffing_requirements.loc[person, 'Availability_Hr'] <= 52)
# If an employee works and then stops, they can't start again
num_slots = max(timeslots)
for timeslot in timeslots:
if timeslot < num_slots:
for person in persons:
prob += staffed[timeslot+1, person] <= staffed[timeslot, person] + \
(1 - (1./num_slots) *
sum([staffed[(s, person)] for s in timeslots if s < timeslot]))
prob.solve()
print(pulp.LpStatus[prob.status])
output = []
for timeslot, staffmember in staffed:
var_output = {
'Timeslot': timeslot,
'Staffmember': staffmember,
'Staffed': staffed[(timeslot, staffmember)].varValue,
}
output.append(var_output)
output_df = pd.DataFrame.from_records(output)#.sort_values(['timeslot', 'staffmember'])
output_df.set_index(['Timeslot', 'Staffmember'], inplace=True)
if pulp.LpStatus[prob.status] == 'Optimal':
print(output_df)
评论里有人讨论这是OR问题还是python/pulp编码问题。我觉得两者兼而有之。
我不明白你的晚上 8 点后开始的无班次代码应该如何工作。这可能是因为我还没有看到你的数学公式（如评论中所建议的）。
我的做法如下 - 您不希望在晚上 8 点之后开始轮班。我假设这是您尝试这样做的时间段 52。鉴于您不允许拆分班次，我认为应用此约束的最简单方法是说（在伪代码中）
对于每个人，如果他们在晚上 8 点之前或之后没有空位，那么他们在晚上 8 点之后将不允许有任何空位。
在代码中：
for person in persons:
prob += pulp.lpSum([staffed[timeslot, person] for timeslot in timeslots if timeslot > 52]) <= \
pulp.lpSum([staffed[timeslot, person] for timeslot in timeslots if timeslot <= 52])*30
要了解这是如何工作的，请考虑这两种情况。
首先针对晚上 8 点或之前没有轮班的人（即 timeslot <= 52）。对于那个人，此约束的 right-hand-side 变为 <=0，因此在晚上 8 点后无法使用任何时段 (timeslot > 52)。
另一方面，如果在晚上 8 点之前安排了至少一个班次，则右侧变为 <=30（或者 <= 如果在晚上 8 点之前存在多个班次，则为更大的数字），因此约束为 non-active（晚上 8 点之后只有 27 个可能的时段，因此只要在此之前有一个时段工作，post-8PM 的工作就没有限制。