6

我正在为 Job-Shop 问题实施类似的解决方案，但有一个区别：我不知道必须执行每项任务的机器。解决这个问题也是问题的一部分。事实上，我们可以说，我正在尝试解决护士问题和工作车间问题的结合。

更具体地说，我有一些持续时间为 D 的任务 T，由于其性质 N（比如说前端任务、后端任务等），必须由某些特定员工 E 以特定顺序 O 执行。

我有：

  • 一个 T int 变量数组，可以获取 E 范围内的值（将执行任务的员工）。
  • 一组固定的持续时间间隔变量（在知道它的持续时间 D 的情况下安排它们）。
  • E 序列变量应该是员工将要执行的任务序列（间隔变量）。
  • 任务和员工之间关系 N 的一些约束。
  • 订单 O 的一些其他约束。

解决这个问题的一种方法是：首先解决分配问题，然后安排任务。我已经实现了这一点。

但是我想将它作为一个独特的解决方案来实现。

我被困在这个问题上：如何创建一个依赖于我之前创建的 int vars 的析取约束？

给需要看代码的人：

for i in range(number_employees):
    disj = solver.DisjunctiveConstraint([interval_var[task_id] if int_var[task_id] == i] ,'i_name')
   [...]

当然，这是行不通的。

我真的很感激任何建议。

4

2 回答 2

4

应该看看 CP-SAT 求解器。它支持半具体化的约束。

也就是说，（在python中）：

model.AddNoOverlap([区间列表]).OnlyEnforceIf(boolvar)

model.Add(x == i).OnlyEnforceIf(boolvar)

model.Add(x != i).OnlyEnforceIf(boolvar.Not())

请参阅：https ://github.com/google/or-tools/blob/master/ortools/sat/doc/index.md

于 2018-07-21T03:01:44.073 回答
0

Laurent Perron，我修改了 no_overlap_sample_sat.py以遵循您的建议，但它不起作用。我修改的是：

# No Overlap constraint.
boolvar = model.NewBoolVar('boolvar')
i = model.NewIntVar(0, 10, 'i')
x = model.NewIntVar(0, 10, 'x')
model.Add(i - x == 0)
model.AddNoOverlap(
    [task_0, task_1, task_2, weekend_0, weekend_1, weekend_2]).OnlyEnforceIf(boolvar)
model.Add(x == i).OnlyEnforceIf(boolvar)
model.Add(x != i).OnlyEnforceIf(boolvar.Not())

输出是：

求解器以非最佳状态退出：1

你还有什么建议吗？

于 2019-12-07T05:30:24.800 回答