7

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

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

我需要将每个任务分配给一个员工，显然一个员工不能同时实现两个任务。我已经写了这两个硬约束并且它们工作正常。

问题：

现在，一些任务被“联系”在一起，应该由同一名员工来实现。它们存储如下：

linkedMissions = {{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);
}

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

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

4

1 回答 1

0

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

我能够实现您的方法（在 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])))

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

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

于 2020-12-10T22:18:55.917 回答