员工轮班问题 - link 任务一起

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])))

此代码生成可行分配（最佳完工时长=18），其中链接任务由同一员工按要求执行。

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

员工轮班问题 - link 任务一起

Employees shift problem - link missions together

c#

or-tools

sat

cp-sat-solver

问题：

编辑：