员工将问题联系在一起
员工将问题联系在一起
提问于 2019-04-13 21:07:32
我有一个Employee列表和一个Mission列表。每个特派团都有一个启动时间和一个持续时间。
在cp模型(Google CpSat，from或-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);
}但是现在，这个约束根本不起作用:联系的轮班不是由同一个员工实现的。
，我的推理有什么问题？为什么我的模型不可行？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-12-10 22:18:55
问题中描述的推理似乎很好，但是，如果没有一个最小的工作示例，就很难进行验证。
我能够实现您的方法(在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)，其中链接的任务由同一名员工根据需要执行。
因此，总而言之，虽然我无法确定问题所在，但正如上面的代码所示，这种方法似乎是合理的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55669907
复制相关文章
相似问题
腾讯云开发者
