安排两个人之间不重叠的任务
Schedule non-overlapping tasks between two people
我正在使用 Google OR-Tools 来解决维护计划问题。我有五台机器，最初都是坏的。我需要为两名技术人员安排任务来修理机器，以最大程度地减少总产量损失。每个技术人员都可以修理任何机器。但是，修复每台机器所花费的时间是不同的（但事先知道每台机器）。每台机器的输出都是一样的。因此，最佳解决方案是首先执行最快的任务（机器修复），以便尽快启动和 运行ning 尽可能多的机器。 （这是一个让我开始做更复杂的事情的玩具问题。）
我已经解决了作业车间的问题，为一名技术人员解决了这个问题（请参阅下面的工作 python 脚本），但我无法尝试将其应用于两名技术人员，因为我不知道如何解决处理两组技术人员任务之间的无重叠情况。
from ortools.sat.python import cp_model
import pandas as pd
model = cp_model.CpModel()
horizon = 12 # just put a large enough horizon (time endpoint) here for now
#start and end times for each task as int variables
t00 = model.NewIntVar(0, horizon, 't00')
t01 = model.NewIntVar(0, horizon, 't01')
t10 = model.NewIntVar(0, horizon, 't10') # task 1 start
t11 = model.NewIntVar(0, horizon, 't11') # task 1 end
t20 = model.NewIntVar(0, horizon, 't20') # task 2 start
t21 = model.NewIntVar(0, horizon, 't21') # task 2 end
t30 = model.NewIntVar(0, horizon, 't30')
t31 = model.NewIntVar(0, horizon, 't31')
t40 = model.NewIntVar(0, horizon, 't40')
t41 = model.NewIntVar(0, horizon, 't41')
#create intervals for each task with given durations
i0 = model.NewIntervalVar(t00, 3, t01, 'i0')
i1 = model.NewIntervalVar(t10, 1, t11, 'i1')
i2 = model.NewIntervalVar(t20, 1, t21, 'i2')
i3 = model.NewIntervalVar(t30, 2, t31, 'i3')
i4 = model.NewIntervalVar(t40, 1, t41, 'i4')
#only one technician so no overlap between any of the task intervals
model.AddNoOverlap([i0, i1, i2, i3, i4])
#minimize sum of all start points (equivalent to minimizing total machine downtime)
model.Minimize(t00+t10+t20+t30+t40)
solver = cp_model.CpSolver()
status = solver.Solve(model)
#present results in a schedule of tasks
df=pd.DataFrame()
df['task']=[0,1,2,3,4]
df['start']=[solver.Value(x) for x in [t00,t10,t20,t30,t40]]
df['end']=[solver.Value(x) for x in [t01,t11,t21,t31,t41]]
df=df.sort_values(by='start').reset_index(drop=True)
print(df)
在我成功的代码中（对于一名技术人员），我安排了五个标记为 0,1,2,3,4 且持续时间分别为 3,1,1,2,1 单位的任务。单技术员脚本通过将任务按 1,2,4,3,0.
顺序正确优化
据我从其他一些帖子中看到的（例如）我认为我需要为每台机器引入两个布尔变量来指示哪个技术人员（称他们为a和b）执行每项任务.例如。我需要任务 0（修复机器 0）：
bool_0a=model.NewBoolVar('bool_0a') # if True means task 0 done by technician a
bool_0b=model.NewBoolVar('bool_0b') # if True means task 0 done by technician b
那我需要介绍一下model.AddBoolOr([bool_0a, bool_0b])，防止两个技术人员修同一台机器
但是我现在遇到的问题是如何处理 AddNoOverlaps 条件。以前是 model.AddNoOverlap([i0, i1, i2, i3, i4]) 除了现在我需要将它应用于两组间隔（每个技术人员一组）并且在我解决问题之前我不知道哪个任务在哪个组中。
请有人建议我如何做到这一点。或者也许我使用了错误的想法来转移到双技术人员案例，这在某种程度上不是单技术人员案例的简单扩展。
添加：评论和回答后的工作代码
下面是答案和评论之后问题的工作代码。每个任务-技术员对都被赋予一个布尔变量 tech_for_task。由技术人员执行的任务是 True，否则 False。对于每项任务，model.AddBoolOr 应用于 tech_for_task 中的布尔值列表，以确保仅由一名技术人员完成。每个技术人员都不会将重叠应用于他们的间隔集。
有一件事可行但我不确定是最佳实践：我最小化丢失的输出 objective 函数，该函数总结所有任务的结束时间，包括具有 tech_for_task=False 的物理上无意义的任务.查看解决方案，ends=0 对于这些情况，因此它们不会对 objective 函数产生影响。但是，最好不要首先将这些包括在总和中。此处建议的加权和 () 看起来不错，但在我的代码中它似乎引入了非线性，这是 verboten。
代码似乎给出了合理的结果。具有多个技术人员的 10 个任务案例需要一段时间 运行，但结果显示每个技术人员的任务都按升序排序，这似乎是合理的。谢谢大家。
from ortools.sat.python import cp_model
import pandas as pd
n_techs = 2 # number technicians
#different scenarios for testing {machine:duration to fix}
durations = {0: 3, 1: 1, 2: 1, 3: 2, 4: 1}
# durations = {0: 10, 1: 9, 2: 8, 3: 7, 4: 6,5: 5, 6: 4, 7: 3, 8: 2, 9: 1, 10:1}
model = cp_model.CpModel()
n_tasks=len(durations)
all_techs=range(n_techs)
all_tasks=range(n_tasks)
#horizon is sum of all durations (conservative)
horizon=sum(durations.values())
#boolean variable for each combination of technician and task. if True then technician works on this task
tech_for_task={}
for tech in all_techs:
for task in all_tasks:
tech_for_task[(tech,task)]=model.NewBoolVar('tech_{0}_on_task_{1}'.format(tech,task))
#for each task, apply sum(tech_for_task)==1 to ensure one tech works on each task only
for task in all_tasks:
model.Add(sum([tech_for_task[(tech,task)] for tech in all_techs])==1)
#boolean or condition to ensure that only one tech works on each task (replaced by sum==1 following comment)
# for task in all_tasks:
# model.AddBoolOr([tech_for_task[(tech,task)] for tech in all_techs])
#start,end and interval for each task
starts = {}
ends = {}
intervals = {}
for tech in all_techs:
for task in all_tasks:
starts[(tech,task)] = model.NewIntVar(0, horizon, 'tech_{0}_task_{1}_start'.format(tech,task))
ends[(tech,task)] = model.NewIntVar(0, horizon, 'tech_{0}_task_{1}_end'.format(tech,task))
#this optional interval is only live when a technician is working on a task (tech_for_task=True)
intervals[(tech,task)]=model.NewOptionalIntervalVar(starts[(tech,task)],
durations[task],
ends[(tech,task)],
tech_for_task[(tech,task)],
'tech_{0}_task_{1}_opt_interval'.format(tech,task))
#the tasks for each technician should not overlap
for tech in all_techs:
model.AddNoOverlap([intervals[(tech,task)] for task in all_tasks])
# minimize sum of end time points for all tasks. ends=0 when tech_for_task=False so not cause problem
obj_fun=[]
for tech in all_techs:
for task in all_tasks:
obj_fun.append(ends[(tech,task)])
model.Minimize(sum(obj_fun))
#thought this would minimize the endpoints of active intervals but its nonlinear so doesnt work
# model.Minimize(sum( ends[(tech,task)] * tech_for_task[(tech,task)] for tech in all_techs for task in all_tasks ))
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print('solved ok')
c_starts={}
c_ends={}
c_tech_for_task={}
c_tech={}
c_task={}
for tech in all_techs:
for task in all_tasks:
tt=(tech,task)
c_starts[tt]=solver.Value(starts[tt])
c_ends[tt]=solver.Value(ends[tt])
c_tech_for_task[tt]=solver.Value(tech_for_task[tt])
c_tech[tt]=tech
c_task[tt]=task
df=pd.DataFrame()
df['task']=c_task.values()
df['tech']=c_tech.values()
df['start']=c_starts.values()
df['end']=c_ends.values()
df['tech_for_task']=c_tech_for_task.values()
#sort chronologically
df=df.sort_values(by='start').reset_index(drop=True)
df['duration']=df['task'].map(durations)
#get only the tasks which were done by a tech (tech_for_task=0 are not meaningful)
df=df[df.tech_for_task==1]
print(df)
elif status==cp_model.MODEL_INVALID:
print('Model invalid :-(')
您可以通过创建一个变量数组 technicianForTask[task] 来对其建模，这些变量指示哪个技术人员正在执行每项任务。然后为每对间隔添加无重叠约束，但仅当技术人员对这两个任务相同时才强制执行。
我没有有效的 Python 安装，但等效的 c# 代码如下所示：
int nTasks = 10;
int nTechnicians = 3;
IntVar[] technicianForTask = new IntVar[nTasks];
IntVar[] start = new IntVar[nTasks];
IntVar[] end = new IntVar[nTasks];
IntervalVar[] interval = new IntervalVar[nTasks];
for (int i = 0; i < nTasks; i++)
{
technicianForTask[i] = model.NewIntVar(0, nTechnicians - 1, $"Technician for task {i}");
start[i] = model.NewIntVar(0, horizon, $"Start of task {i}");
end[i] = model.NewIntVar(0, horizon, $"End of task {i}");
interval[i] = model.NewIntervalVar(start[i], 3, end[i], $"Interval for task {i}"); // You'll have to put the right duration in here
}
for (int i = 0; i < nTasks - 1; i++)
{
for (int j = i + 1; j < nTasks; j++)
{
IntVar sameTechnician = model.NewBoolVar($"Job {i} and {j} have the same technician.");
model.Add(technicianForTask[i] == technicianForTask[j]).OnlyEnforceIf(sameTechnician);
model.Add(technicianForTask[i] != technicianForTask[j]).OnlyEnforceIf(sameTechnician.Not());
model.AddNoOverlap(new List<IntervalVar>() { interval[i], interval[j] }).OnlyEnforceIf(sameTechnician);
}
}
我确定您可以转换为等效的 Python 代码。
您必须使用开始时间数组的总和重新定义 objective 函数。
我正在使用 Google OR-Tools 来解决维护计划问题。我有五台机器，最初都是坏的。我需要为两名技术人员安排任务来修理机器，以最大程度地减少总产量损失。每个技术人员都可以修理任何机器。但是，修复每台机器所花费的时间是不同的（但事先知道每台机器）。每台机器的输出都是一样的。因此，最佳解决方案是首先执行最快的任务（机器修复），以便尽快启动和 运行ning 尽可能多的机器。 （这是一个让我开始做更复杂的事情的玩具问题。）
我已经解决了作业车间的问题，为一名技术人员解决了这个问题（请参阅下面的工作 python 脚本），但我无法尝试将其应用于两名技术人员，因为我不知道如何解决处理两组技术人员任务之间的无重叠情况。
from ortools.sat.python import cp_model
import pandas as pd
model = cp_model.CpModel()
horizon = 12 # just put a large enough horizon (time endpoint) here for now
#start and end times for each task as int variables
t00 = model.NewIntVar(0, horizon, 't00')
t01 = model.NewIntVar(0, horizon, 't01')
t10 = model.NewIntVar(0, horizon, 't10') # task 1 start
t11 = model.NewIntVar(0, horizon, 't11') # task 1 end
t20 = model.NewIntVar(0, horizon, 't20') # task 2 start
t21 = model.NewIntVar(0, horizon, 't21') # task 2 end
t30 = model.NewIntVar(0, horizon, 't30')
t31 = model.NewIntVar(0, horizon, 't31')
t40 = model.NewIntVar(0, horizon, 't40')
t41 = model.NewIntVar(0, horizon, 't41')
#create intervals for each task with given durations
i0 = model.NewIntervalVar(t00, 3, t01, 'i0')
i1 = model.NewIntervalVar(t10, 1, t11, 'i1')
i2 = model.NewIntervalVar(t20, 1, t21, 'i2')
i3 = model.NewIntervalVar(t30, 2, t31, 'i3')
i4 = model.NewIntervalVar(t40, 1, t41, 'i4')
#only one technician so no overlap between any of the task intervals
model.AddNoOverlap([i0, i1, i2, i3, i4])
#minimize sum of all start points (equivalent to minimizing total machine downtime)
model.Minimize(t00+t10+t20+t30+t40)
solver = cp_model.CpSolver()
status = solver.Solve(model)
#present results in a schedule of tasks
df=pd.DataFrame()
df['task']=[0,1,2,3,4]
df['start']=[solver.Value(x) for x in [t00,t10,t20,t30,t40]]
df['end']=[solver.Value(x) for x in [t01,t11,t21,t31,t41]]
df=df.sort_values(by='start').reset_index(drop=True)
print(df)
在我成功的代码中（对于一名技术人员），我安排了五个标记为 0,1,2,3,4 且持续时间分别为 3,1,1,2,1 单位的任务。单技术员脚本通过将任务按 1,2,4,3,0.
据我从其他一些帖子中看到的（例如
bool_0a=model.NewBoolVar('bool_0a') # if True means task 0 done by technician a
bool_0b=model.NewBoolVar('bool_0b') # if True means task 0 done by technician b
那我需要介绍一下model.AddBoolOr([bool_0a, bool_0b])，防止两个技术人员修同一台机器
但是我现在遇到的问题是如何处理 AddNoOverlaps 条件。以前是 model.AddNoOverlap([i0, i1, i2, i3, i4]) 除了现在我需要将它应用于两组间隔（每个技术人员一组）并且在我解决问题之前我不知道哪个任务在哪个组中。
请有人建议我如何做到这一点。或者也许我使用了错误的想法来转移到双技术人员案例，这在某种程度上不是单技术人员案例的简单扩展。
添加：评论和回答后的工作代码
下面是答案和评论之后问题的工作代码。每个任务-技术员对都被赋予一个布尔变量 tech_for_task。由技术人员执行的任务是 True，否则 False。对于每项任务，model.AddBoolOr 应用于 tech_for_task 中的布尔值列表，以确保仅由一名技术人员完成。每个技术人员都不会将重叠应用于他们的间隔集。
有一件事可行但我不确定是最佳实践：我最小化丢失的输出 objective 函数，该函数总结所有任务的结束时间，包括具有 tech_for_task=False 的物理上无意义的任务.查看解决方案，ends=0 对于这些情况，因此它们不会对 objective 函数产生影响。但是，最好不要首先将这些包括在总和中。此处建议的加权和 (
代码似乎给出了合理的结果。具有多个技术人员的 10 个任务案例需要一段时间 运行，但结果显示每个技术人员的任务都按升序排序，这似乎是合理的。谢谢大家。
from ortools.sat.python import cp_model
import pandas as pd
n_techs = 2 # number technicians
#different scenarios for testing {machine:duration to fix}
durations = {0: 3, 1: 1, 2: 1, 3: 2, 4: 1}
# durations = {0: 10, 1: 9, 2: 8, 3: 7, 4: 6,5: 5, 6: 4, 7: 3, 8: 2, 9: 1, 10:1}
model = cp_model.CpModel()
n_tasks=len(durations)
all_techs=range(n_techs)
all_tasks=range(n_tasks)
#horizon is sum of all durations (conservative)
horizon=sum(durations.values())
#boolean variable for each combination of technician and task. if True then technician works on this task
tech_for_task={}
for tech in all_techs:
for task in all_tasks:
tech_for_task[(tech,task)]=model.NewBoolVar('tech_{0}_on_task_{1}'.format(tech,task))
#for each task, apply sum(tech_for_task)==1 to ensure one tech works on each task only
for task in all_tasks:
model.Add(sum([tech_for_task[(tech,task)] for tech in all_techs])==1)
#boolean or condition to ensure that only one tech works on each task (replaced by sum==1 following comment)
# for task in all_tasks:
# model.AddBoolOr([tech_for_task[(tech,task)] for tech in all_techs])
#start,end and interval for each task
starts = {}
ends = {}
intervals = {}
for tech in all_techs:
for task in all_tasks:
starts[(tech,task)] = model.NewIntVar(0, horizon, 'tech_{0}_task_{1}_start'.format(tech,task))
ends[(tech,task)] = model.NewIntVar(0, horizon, 'tech_{0}_task_{1}_end'.format(tech,task))
#this optional interval is only live when a technician is working on a task (tech_for_task=True)
intervals[(tech,task)]=model.NewOptionalIntervalVar(starts[(tech,task)],
durations[task],
ends[(tech,task)],
tech_for_task[(tech,task)],
'tech_{0}_task_{1}_opt_interval'.format(tech,task))
#the tasks for each technician should not overlap
for tech in all_techs:
model.AddNoOverlap([intervals[(tech,task)] for task in all_tasks])
# minimize sum of end time points for all tasks. ends=0 when tech_for_task=False so not cause problem
obj_fun=[]
for tech in all_techs:
for task in all_tasks:
obj_fun.append(ends[(tech,task)])
model.Minimize(sum(obj_fun))
#thought this would minimize the endpoints of active intervals but its nonlinear so doesnt work
# model.Minimize(sum( ends[(tech,task)] * tech_for_task[(tech,task)] for tech in all_techs for task in all_tasks ))
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print('solved ok')
c_starts={}
c_ends={}
c_tech_for_task={}
c_tech={}
c_task={}
for tech in all_techs:
for task in all_tasks:
tt=(tech,task)
c_starts[tt]=solver.Value(starts[tt])
c_ends[tt]=solver.Value(ends[tt])
c_tech_for_task[tt]=solver.Value(tech_for_task[tt])
c_tech[tt]=tech
c_task[tt]=task
df=pd.DataFrame()
df['task']=c_task.values()
df['tech']=c_tech.values()
df['start']=c_starts.values()
df['end']=c_ends.values()
df['tech_for_task']=c_tech_for_task.values()
#sort chronologically
df=df.sort_values(by='start').reset_index(drop=True)
df['duration']=df['task'].map(durations)
#get only the tasks which were done by a tech (tech_for_task=0 are not meaningful)
df=df[df.tech_for_task==1]
print(df)
elif status==cp_model.MODEL_INVALID:
print('Model invalid :-(')
您可以通过创建一个变量数组 technicianForTask[task] 来对其建模，这些变量指示哪个技术人员正在执行每项任务。然后为每对间隔添加无重叠约束，但仅当技术人员对这两个任务相同时才强制执行。
我没有有效的 Python 安装，但等效的 c# 代码如下所示：
int nTasks = 10;
int nTechnicians = 3;
IntVar[] technicianForTask = new IntVar[nTasks];
IntVar[] start = new IntVar[nTasks];
IntVar[] end = new IntVar[nTasks];
IntervalVar[] interval = new IntervalVar[nTasks];
for (int i = 0; i < nTasks; i++)
{
technicianForTask[i] = model.NewIntVar(0, nTechnicians - 1, $"Technician for task {i}");
start[i] = model.NewIntVar(0, horizon, $"Start of task {i}");
end[i] = model.NewIntVar(0, horizon, $"End of task {i}");
interval[i] = model.NewIntervalVar(start[i], 3, end[i], $"Interval for task {i}"); // You'll have to put the right duration in here
}
for (int i = 0; i < nTasks - 1; i++)
{
for (int j = i + 1; j < nTasks; j++)
{
IntVar sameTechnician = model.NewBoolVar($"Job {i} and {j} have the same technician.");
model.Add(technicianForTask[i] == technicianForTask[j]).OnlyEnforceIf(sameTechnician);
model.Add(technicianForTask[i] != technicianForTask[j]).OnlyEnforceIf(sameTechnician.Not());
model.AddNoOverlap(new List<IntervalVar>() { interval[i], interval[j] }).OnlyEnforceIf(sameTechnician);
}
}
我确定您可以转换为等效的 Python 代码。
您必须使用开始时间数组的总和重新定义 objective 函数。