创建可用值的分布 - Python
Create distribution of available values - Python
我希望创建一个 分布 来显示员工可以工作的时间。类似这个图，在这个linkstaff distribution找到。
为实现这一点，我创建了 staff_availability_df，其中包含要从中挑选的员工人数，可在 ['Person'] 列中找到。他们可以工作的 min - max 小时，他们得到的报酬是多少都这样标记。他们可以工作的可用时间被分成小时['Availability_Hr']，表示他们可以工作的时间，以小时表示。所以第一人称是'8-18'，也就是8:00:00am - 18:00:00pm。 ['Availability_15min_Seg'] 本质上是相同的，但小时分为 4 个部分。所以第一人称是'1-41'，又是8:00:00am - 18:00:00pm.
注意：标准班次在 8:00:00am - 3:30:00am 之间运行，因此大约 20 小时。
staff_requirements_df整个轮班显示Time和我需要的People
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.dates as dates
#This is the employee availability:
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-69','37-79','37-79','37-79'],
})
#These are the staffing requirements:
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],
})
我使用以下函数导出了发生在 8:00:00am - 3:30:00am 之间的 15 分钟片段中的人员配备要求。每15min分配给string'T'。所以 T1 = 8:00:00am 和 T79 = 3:00:00am
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')
staffing_requirements = staffing_requirements.groupby(pd.Grouper(freq='15T',key='Time'))['People'].max().ffill()
staffing_requirements = staffing_requirements.reset_index(level=['Time'])
staffing_requirements.insert(2, 'T', range(1, 1 + len(staffing_requirements)))
staffing_requirements['T'] = 'T' + staffing_requirements['T'].astype(str)
st_req = staffing_requirements['People'].tolist()
[1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 4.0, 4.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 3.0, 2.0]
我希望使用这些函数来创建 linear programming matrix return 每个员工可用工作时间的 分布 。但我希望使用 15 分钟的片段以及几个小时。例如注意：此导出将扩展到 3:30am。所以它将包含 79 个段。
注意：要清楚。我希望 return 发布时间表，以便将来使用。不只是一个数字。
有一些员工可用性 example 1 example 2 方法使用 mixed-integer linear programming，但它们使用闭源软件。我希望将其翻译成 Python。
根据我的想法，greedy algorithm 可以工作。选择一个最能增加您的优化功能的选项等；如果下一步没有可用的选项，则回溯并选择下一个最佳选项等
如 link 中所述，找到的解决方案的最优程度在很大程度上取决于优化函数的类型。
这对于整数规划来说确实是一个很棒的工作；您可以使用 pulp，您首先需要通过命令行安装它，例如pip install pulp
数据操纵为成功做好准备
然后，首先确保您的 DataFrames 处于最佳状态，以便我们解决问题：
# Since timeslots for staffing start counting at 1, also make the
# DataFrame index start counting at 1
staffing_requirements.index = range(1, len(staffing_requirements) + 1)
print(staffing_requirements.tail())
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'}))
其中 availability_per_member 现在是一个 MultiIndex DataFrame 每个人每个时间段一行，表示 his/her 可用性和工资：
# Available HourlyWage
#Timeslot Person
#1 C1 1 26
# C2 1 26
# C3 1 26
# C4 0 26
# C5 0 26
此外，我们稍微改变了必要条件，所以问题实际上是可以解决的；请参阅附录了解为什么这是必要的
import numpy as np
np.random.seed(42)
staffing_requirements['People'] = np.random.randint(1, 4, size=len(staffing_requirements))
staff_costs['MinHours'] = 3
用 pulp
解决整数规划问题
现在，我们可以让 pulp 工作了：以成本最小化为目标设置问题，并逐一添加您提到的约束，请参阅注释代码。 staffed 现在是一个纸浆字典，包含一个人是否在某个时间段（0 或 1）有人值班
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
然后，就是让pulp破案了：
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)
现在这将 return 一个 DataFrame output_df 每个时间段和每个人包含他们是否有人：
# Staffed
#Timeslot Staffmember
#1 C1 1.0
# C2 1.0
# C3 1.0
# C4 0.0
# C5 0.0
# C6 0.0
# C7 0.0
# C8 0.0
# C9 0.0
# C10 0.0
# C11 0.0
#2 C1 1.0
# C2 1.0
我已经改编了 http://benalexkeen.com/linear-programming-with-python-and-pulp-part-5/ 的代码，这是一个很好的纸浆和线性规划教程，所以一定要检查一下。
附录：您的要求不可行
以你的条件，这实际上会return 'Infeasible'。很容易看出这是为什么：
您可以看到在最后几个时间段中需要的工作人员多于可用的工作人员。此图由以下人员创建：
fig, ax = plt.subplots()
staffing_requirements.plot(y='People', ax=ax, label='Required', drawstyle='steps-mid')
availability_per_member.groupby(level='Timeslot')['Available'].sum().plot(ax=ax,
label='Available', drawstyle='steps-mid')
plt.legend()
我希望创建一个 分布 来显示员工可以工作的时间。类似这个图，在这个linkstaff distribution找到。
为实现这一点，我创建了 staff_availability_df，其中包含要从中挑选的员工人数，可在 ['Person'] 列中找到。他们可以工作的 min - max 小时，他们得到的报酬是多少都这样标记。他们可以工作的可用时间被分成小时['Availability_Hr']，表示他们可以工作的时间，以小时表示。所以第一人称是'8-18'，也就是8:00:00am - 18:00:00pm。 ['Availability_15min_Seg'] 本质上是相同的，但小时分为 4 个部分。所以第一人称是'1-41'，又是8:00:00am - 18:00:00pm.
注意：标准班次在 8:00:00am - 3:30:00am 之间运行，因此大约 20 小时。
staff_requirements_df整个轮班显示Time和我需要的People
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.dates as dates
#This is the employee availability:
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-69','37-79','37-79','37-79'],
})
#These are the staffing requirements:
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],
})
我使用以下函数导出了发生在 8:00:00am - 3:30:00am 之间的 15 分钟片段中的人员配备要求。每15min分配给string'T'。所以 T1 = 8:00:00am 和 T79 = 3:00:00am
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')
staffing_requirements = staffing_requirements.groupby(pd.Grouper(freq='15T',key='Time'))['People'].max().ffill()
staffing_requirements = staffing_requirements.reset_index(level=['Time'])
staffing_requirements.insert(2, 'T', range(1, 1 + len(staffing_requirements)))
staffing_requirements['T'] = 'T' + staffing_requirements['T'].astype(str)
st_req = staffing_requirements['People'].tolist()
[1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 4.0, 4.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 3.0, 2.0]
我希望使用这些函数来创建 linear programming matrix return 每个员工可用工作时间的 分布 。但我希望使用 15 分钟的片段以及几个小时。例如注意：此导出将扩展到 3:30am。所以它将包含 79 个段。
注意：要清楚。我希望 return 发布时间表，以便将来使用。不只是一个数字。
有一些员工可用性 example 1 example 2 方法使用 mixed-integer linear programming，但它们使用闭源软件。我希望将其翻译成 Python。
根据我的想法，greedy algorithm 可以工作。选择一个最能增加您的优化功能的选项等；如果下一步没有可用的选项，则回溯并选择下一个最佳选项等
如 link 中所述，找到的解决方案的最优程度在很大程度上取决于优化函数的类型。
这对于整数规划来说确实是一个很棒的工作；您可以使用 pulp，您首先需要通过命令行安装它，例如pip install pulp
数据操纵为成功做好准备
然后，首先确保您的 DataFrames 处于最佳状态，以便我们解决问题：
# Since timeslots for staffing start counting at 1, also make the
# DataFrame index start counting at 1
staffing_requirements.index = range(1, len(staffing_requirements) + 1)
print(staffing_requirements.tail())
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'}))
其中 availability_per_member 现在是一个 MultiIndex DataFrame 每个人每个时间段一行，表示 his/her 可用性和工资：
# Available HourlyWage
#Timeslot Person
#1 C1 1 26
# C2 1 26
# C3 1 26
# C4 0 26
# C5 0 26
此外，我们稍微改变了必要条件，所以问题实际上是可以解决的；请参阅附录了解为什么这是必要的
import numpy as np
np.random.seed(42)
staffing_requirements['People'] = np.random.randint(1, 4, size=len(staffing_requirements))
staff_costs['MinHours'] = 3
用 pulp
解决整数规划问题
现在，我们可以让 pulp 工作了：以成本最小化为目标设置问题，并逐一添加您提到的约束，请参阅注释代码。 staffed 现在是一个纸浆字典，包含一个人是否在某个时间段（0 或 1）有人值班
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
然后，就是让pulp破案了：
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)
现在这将 return 一个 DataFrame output_df 每个时间段和每个人包含他们是否有人：
# Staffed
#Timeslot Staffmember
#1 C1 1.0
# C2 1.0
# C3 1.0
# C4 0.0
# C5 0.0
# C6 0.0
# C7 0.0
# C8 0.0
# C9 0.0
# C10 0.0
# C11 0.0
#2 C1 1.0
# C2 1.0
我已经改编了 http://benalexkeen.com/linear-programming-with-python-and-pulp-part-5/ 的代码，这是一个很好的纸浆和线性规划教程，所以一定要检查一下。
附录：您的要求不可行
以你的条件，这实际上会return 'Infeasible'。很容易看出这是为什么：
您可以看到在最后几个时间段中需要的工作人员多于可用的工作人员。此图由以下人员创建：
fig, ax = plt.subplots()
staffing_requirements.plot(y='People', ax=ax, label='Required', drawstyle='steps-mid')
availability_per_member.groupby(level='Timeslot')['Available'].sum().plot(ax=ax,
label='Available', drawstyle='steps-mid')
plt.legend()