我正在使用Google OR Tools来解决维护计划问题。我有五台机器，最初都坏了。我需要为两名技术人员安排任务来修复机器，以最大限度地减少总输出损失。每个技术人员都可以修理任何一台机器。然而，修复每台机器所花费的时间是不同的(但每台机器事先都知道(。每台机器的输出都是相同的。因此，最佳解决方案是首先完成最快的任务(机器修复(，以便尽可能多的机器尽快启动并运行。(这是一个玩具问题，让我开始处理更复杂的事情。(
我已经破解了作业车间的问题，为一名技术人员解决了这个问题(请参阅下面的工作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中的布尔值列表，以确保仅由一名技术人员完成。每个技术人员的间隔设置不重叠。
有效但我不确定的一件事是最佳实践：我最小化丢失的输出目标函数，该函数求出所有任务的结束时间，包括具有tech_for_task=False的物理上无意义的任务。从解决方案来看，ends=0适用于这些情况，因此它们对目标函数没有贡献。然而，如果一开始就不把这些包括在总额中，那就太好了。这里建议的加权和(谷歌OR工具-列车调度问题(看起来不错，但在我的代码中，它似乎引入了一种非线性，这是禁止的。
代码似乎给出了合理的结果。有多个技术人员的十个任务案例需要一段时间才能运行，但结果显示每个技术人员的任务都按升序排序，这似乎是合理的。谢谢大家。
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代码。
你必须用开始时间数组的和来重新定义你的目标函数。