确定价值分配 - Python
Determine allocation of values - Python
我正在尝试创建一个最佳的轮班时间表，为员工分配轮班时间。输出应该以花最少的钱为目标。棘手的部分是我需要考虑特定的限制。这些是：
1) At any given time period, you must meet the minimum staffing requirements
2) A person has a minimum and maximum amount of hours they can do
3) An employee can only be scheduled to work within their available hours
4) A person can only work one shift per day
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.
考虑约束
我得到一个输出，但轮班时间没有连续应用到员工。
我不符合第 4 个限制，因为员工每天只能工作一个班次
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.dates as dates
import pulp
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' : [3,3,3,3,3,3,3,3,3,3,3],
'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'],
})
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 '''
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
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)
以下是前两个小时（8 个 15 分钟时段）的输出。问题是轮班不是连续的。安排在前 8 个时间段的员工主要是不同的。我将有 5 个人在前 2 小时内开始。员工每天应该只工作一个班次。
Timeslot C
0 1 C2
1 2 C2
2 3 C1
3 4 C3
4 5 C6
5 6 C1
6 7 C5
7 8 C2
注意：这是对问题早期版本的回答。
我认为求解器返回的解是正确的；每个人 都是 工作他们的 MinHours，他们只是不连续。我运行你的代码，然后说
for person in persons:
print("{}: {}".format(person, sum([staffed[(timeslot, person)].value() for timeslot in timeslots])))
并得到：
C1: 12.0
C2: 12.0
C3: 12.0
C4: 20.0
C5: 23.0
C6: 18.0
C7: 22.0
C8: 29.0
C9: 22.0
C10: 27.0
C11: 32.0
所以每个人都至少工作 12 个班次，即 3 小时。
如果您希望轮班是连续的（即，一个人不能在第 1 个槽位工作，然后在第 3 个槽位工作），那么处理此问题的典型方法是使用一个决策变量来说明每个员工的开始时间他们的班次，而不是指定他们工作的每个时间段的变量。然后，引入一个参数，如 a[j][t]，如果在槽位 j 开始轮班的员工在槽位 t 工作，则该参数等于 1。从那里，您可以计算谁在哪个时段工作。
将 MinHours 设置为 5 时问题不可行的原因是它迫使太多人在特定时间段工作。例如，6 个人必须在时间段 41 之前完成轮班。这意味着 6 x 4 x 5 = 120 人的时间段需要在时间段 41 之前工作。但在时间段 1 和 41 之间只需要 97 人的时间段。
可以通过将 "Staff the right number of people" 约束从 == 更改为 >= 来解决此问题，前提是人员配备系统允许这样做。 （如果不是，那么您手上只有一个不可行的实例。）
（顺便说一句——您可能对 Operations Research and Analytics 上提议的新 Stack Exchange 网站感兴趣。我们会在那边解决类似这样的问题。:-)）
这是您修改后的问题的答案，即如何添加要求每个员工在连续时间段工作的约束条件。
我建议您添加以下约束（此处以代数方式编写）：
x[t+1,p] <= x[t,p] + (1 - (1/T) * sum_{s=1}^{t-1} x[s,p]) for all p, for all t < T
其中 x 是您的 staffed 变量（为了紧凑这里写成 x），t 是时间索引，T 是数字时间段的数量，p 是员工指数。
约束的逻辑是：如果x[t,p] = 0（员工在t期间没有工作）和x[s,p] = 1 for any s < t（该员工在之前的任何期间都在工作），则x[t+1,p]必须= 0（该员工不能在t+1期间工作。因此，一旦该员工停止工作，他们不能重新开始。请注意，如果 x[t,p] = 1 或 x[s,p] = 0 对于每个 s < t，则 x[t+1,p] 可以等于 1.
这是我在 pulp 中实现的这个约束：
# 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]))
我运行模型并得到：
Optimal
Staffed
Timeslot Staffmember
1 C2 1.0
2 C2 1.0
3 C2 1.0
4 C2 1.0
5 C2 1.0
6 C2 1.0
7 C2 1.0
8 C2 1.0
9 C2 1.0
C6 1.0
10 C2 1.0
C6 1.0
11 C2 1.0
C6 1.0
12 C2 1.0
C6 1.0
13 C3 1.0
C6 1.0
14 C3 1.0
C6 1.0
等因此，员工在连续的时间段内工作。
请注意，新约束会稍微减慢模型速度。它仍然会在 <30 秒左右的时间内解决。但是，如果您正在解决更大的实例，您可能需要重新考虑约束条件。
我正在尝试创建一个最佳的轮班时间表，为员工分配轮班时间。输出应该以花最少的钱为目标。棘手的部分是我需要考虑特定的限制。这些是：
1) At any given time period, you must meet the minimum staffing requirements
2) A person has a minimum and maximum amount of hours they can do
3) An employee can only be scheduled to work within their available hours
4) A person can only work one shift per day
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.
我得到一个输出，但轮班时间没有连续应用到员工。
我不符合第 4 个限制，因为员工每天只能工作一个班次
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.dates as dates
import pulp
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' : [3,3,3,3,3,3,3,3,3,3,3],
'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'],
})
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 '''
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
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)
以下是前两个小时（8 个 15 分钟时段）的输出。问题是轮班不是连续的。安排在前 8 个时间段的员工主要是不同的。我将有 5 个人在前 2 小时内开始。员工每天应该只工作一个班次。
Timeslot C
0 1 C2
1 2 C2
2 3 C1
3 4 C3
4 5 C6
5 6 C1
6 7 C5
7 8 C2
注意：这是对问题早期版本的回答。
我认为求解器返回的解是正确的；每个人 都是 工作他们的 MinHours，他们只是不连续。我运行你的代码，然后说
for person in persons:
print("{}: {}".format(person, sum([staffed[(timeslot, person)].value() for timeslot in timeslots])))
并得到：
C1: 12.0
C2: 12.0
C3: 12.0
C4: 20.0
C5: 23.0
C6: 18.0
C7: 22.0
C8: 29.0
C9: 22.0
C10: 27.0
C11: 32.0
所以每个人都至少工作 12 个班次，即 3 小时。
如果您希望轮班是连续的（即，一个人不能在第 1 个槽位工作，然后在第 3 个槽位工作），那么处理此问题的典型方法是使用一个决策变量来说明每个员工的开始时间他们的班次，而不是指定他们工作的每个时间段的变量。然后，引入一个参数，如 a[j][t]，如果在槽位 j 开始轮班的员工在槽位 t 工作，则该参数等于 1。从那里，您可以计算谁在哪个时段工作。
将 MinHours 设置为 5 时问题不可行的原因是它迫使太多人在特定时间段工作。例如，6 个人必须在时间段 41 之前完成轮班。这意味着 6 x 4 x 5 = 120 人的时间段需要在时间段 41 之前工作。但在时间段 1 和 41 之间只需要 97 人的时间段。
可以通过将 "Staff the right number of people" 约束从 == 更改为 >= 来解决此问题，前提是人员配备系统允许这样做。 （如果不是，那么您手上只有一个不可行的实例。）
（顺便说一句——您可能对 Operations Research and Analytics 上提议的新 Stack Exchange 网站感兴趣。我们会在那边解决类似这样的问题。:-)）
这是您修改后的问题的答案，即如何添加要求每个员工在连续时间段工作的约束条件。
我建议您添加以下约束（此处以代数方式编写）：
x[t+1,p] <= x[t,p] + (1 - (1/T) * sum_{s=1}^{t-1} x[s,p]) for all p, for all t < T
其中 x 是您的 staffed 变量（为了紧凑这里写成 x），t 是时间索引，T 是数字时间段的数量，p 是员工指数。
约束的逻辑是：如果x[t,p] = 0（员工在t期间没有工作）和x[s,p] = 1 for any s < t（该员工在之前的任何期间都在工作），则x[t+1,p]必须= 0（该员工不能在t+1期间工作。因此，一旦该员工停止工作，他们不能重新开始。请注意，如果 x[t,p] = 1 或 x[s,p] = 0 对于每个 s < t，则 x[t+1,p] 可以等于 1.
这是我在 pulp 中实现的这个约束：
# 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]))
我运行模型并得到：
Optimal
Staffed
Timeslot Staffmember
1 C2 1.0
2 C2 1.0
3 C2 1.0
4 C2 1.0
5 C2 1.0
6 C2 1.0
7 C2 1.0
8 C2 1.0
9 C2 1.0
C6 1.0
10 C2 1.0
C6 1.0
11 C2 1.0
C6 1.0
12 C2 1.0
C6 1.0
13 C3 1.0
C6 1.0
14 C3 1.0
C6 1.0
等因此，员工在连续的时间段内工作。
请注意，新约束会稍微减慢模型速度。它仍然会在 <30 秒左右的时间内解决。但是，如果您正在解决更大的实例，您可能需要重新考虑约束条件。