员工转移问题 - 将任务联系在一起

Question

我有一个Employee列表和一个Mission列表。 每个任务都有开始时间和持续时间。

在cp模型(Google CpSat，来自or-tools包)中，我定义了shifts = Dictionary<(int,int),IntVar>，其中shifts[(missionId, employeeId)] == 1当且仅当该员工实现此任务时。

我需要将每个任务分配给一名员工，显然一名员工无法同时完成两个任务。我已经编写了这两个硬约束，它们工作正常。

>问题：现在，一些任务被"链接"在一起，应该由同一名员工实现。它们的存储方式如下：

linkedMissions = {{1,2}, {3,4,5}}

在这里，任务1 和 2 必须由同一名员工一起实现，任务 3、4 和 5 也是如此。

---

为了写最后一个约束，我为每个员工收集了应该链接在一起的所有班次的列表，然后我使它们都相等。

foreach (var employee in listEmployeesIds)
foreach (var missionGroup in linkedMissionsIds)
{
var linkedShifts = shifts
.Where(o => o.Key.Item2 == employee
&& missionGroup.Contains(o.Key.Item1))
.Select(o => o.Value)
.ToList();
for (var i = 0; i < linkedShifts.Count - 1; i++) 
model.Add(linkedShifts[i] == linkedShifts[i + 1]);
}

然而，求解器告诉我这个模型是不可行的，但是用纸和笔，我可以很容易地找到一个可行的计划。我有 35 名员工和 25 个任务，链接在一起的任务不重叠，所以应该没有任何问题。

>编辑：作为另一种方法，正如 @Laurent Perron 所建议的那样，我尝试对所有必须在一起的移位使用相同的布尔变量：

var constraintBools = new List<IntVar>();
foreach (var missionGroup in linkedMissionsIds) {
var constraintBools = new List<IntVar>();
foreach (var employee in listEmployeesIds)
{
var linkedShifts = shifts
.Where(o => o.Key.Item2 == employee
&& missionGroup.Contains(o.Key.Item1))
.Select(o => o.Value)
.ToList();
var constraint = model.NewBoolVar($"{linkedShifts.GetHashCode()}");
model.AddBoolAnd(linkedShifts).OnlyEnforceIf(constraint);
constraintBools.Add(constraint);
}
model.AddBoolOr(constraintBools);
}

但是现在，这种约束根本不起作用：链接的班次不是由同一名员工实现的。

---

我的推理有什么问题？为什么我的模型不可行？

Answer 1

问题中描述的推理似乎很好，但是如果没有最小的工作示例，很难验证。

我能够实现您的方法(在 Python 中)并且它似乎有效，因此问题似乎出在代码的其他部分，或者出在实现中的某些技术问题中，与求解器和条件没有直接关系(例如，与 @Ian Mercer 评论中提出的惰性函数调用有关)。

根据您的描述，这是一个工作示例：

model = cp_model.CpModel()
employees = 35
tasks = 25
# 3 non overlapping groups of linked tasks (as an example)
linkedTasks = [[t+1 for t in range(tasks) if t%5 == 0], 
[t for t in range(tasks) if t%9 == 0], 
[22, 23, 24]]
#semi random durations, 1-6
task_durations = [t%6+1 for t in range(tasks)]
MAX_TIME = sum(task_durations)
#employee shift assignment: shifts[e,t] == 1 iff task t is assigned to employee e
shifts = {}
for e in range(employees):
for t in range(tasks):
shifts[e, t] = model.NewBoolVar('shift_%i_%i' % (e, t))
# task intervals. Intervals are optional - interval [e, t] is only in effect if 
# task t is performed by employee e        
task_starts = {}
task_ends = {}
task_intervals = {}
for e in range(employees):
for t in range(tasks):
task_starts[e, t] = model.NewIntVar(0, MAX_TIME, 'task_starts_%i_%i' % (e, t))
task_ends[e, t] = model.NewIntVar(0, MAX_TIME, 'task_ends_%i_%i' % (e, t))
task_intervals[e, t] = model.NewOptionalIntervalVar(task_starts[e, t], task_durations[t], task_ends[e, t], shifts[e, t], 'interval_%i_%i' % (e, t))
# employees tasks cannot overlap        
for e in range(employees):
model.AddNoOverlap(task_intervals[e, t] for t in range(tasks))

# all tasks must be realized
model.Add(sum(shifts[e, t] for e in range(employees) for t in range(tasks)) == tasks)
# each task is assigned exactly once
for t in range(tasks):
model.Add(sum(shifts[e, t] for e in range(employees)) == 1)
# make sure linked tasks are performed by the same employee (each consecutive pair of tasks in l, l[t] and l[t+1], 
# must both be performed by the same user e, or not both not performed by the user)
# Note: this condition can be written more elegantly, but I tried to stick to the way the question was framed
for l in linkedTasks:
for t in range(len(l)-1):
for e in range(employees):
model.Add(shifts[e, l[t]] == shifts[e, l[t+1]])
# Goal: makespan (end of last task)
obj_var = model.NewIntVar(0, MAX_TIME, 'makespan')
model.AddMaxEquality(obj_var, [
task_ends[e, t] for e in range(employees) for t in range(tasks)
])
model.Minimize(obj_var)

solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True     
solver.parameters.num_search_workers = 8
solver.parameters.max_time_in_seconds = 30
result_status = solver.Solve(model)

if (result_status == cp_model.INFEASIBLE): 
print('No feasible solution under constraints')
elif (result_status == cp_model.OPTIMAL):
print('Optimal result found, makespan=%i' % (solver.ObjectiveValue()))
elif (result_status == cp_model.FEASIBLE):                        
print('Feasible (non optimal) result found')
else:
print('No feasible solution found under constraints within time')  
for e in range(employees):
for t in range(tasks):
if (solver.Value(shifts[e, t]) > 0):
print('employee %i-> task %i (start: %i, end: %i)' % (e, t, solver.Value(task_starts[e, t]), solver.Value(task_ends[e, t])))

此代码产生可行的分配(最佳 makespan=18)，其中链接的任务根据需要由同一员工执行。

因此，总而言之，虽然我无法查明问题所在，但正如上面的代码所证明的那样，该方法似乎是合理的。