员工轮班问题 - 将任务联系在一起

Question

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

在CP模型（谷歌CpSat，从或工具包），我定义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），其中链接的任务由同一员工根据需要执行。

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