algorithm - 约束编程 : Scheduling speakers in shortest time

Question

我正在尝试通过 Hakan Kjellerstrand 调整一个已经解决的约束规划问题(@hakankless) 需要一些帮助。

原来解决的问题:有 6 个公共(public)演讲者和 6 个房间。每个演讲者都应分配到一个房间，没有空房间，每个演讲者只能在一个房间内。

此处的解决方案:Google OR-Tools & MiniZinc

帮助进行此改编:有 3 位公共(public)演讲者和 6 个时段(即一个房间)。每个发言者都应分配到一个时隙，目的是尽量减少从起始时隙开始的持续时间(假设从时隙 1 开始，或者如果所有人都忙，则从下一个可用时隙开始)。

+---+------+------+------+
|   |  A   |  B   |  C   |
+---+------+------+------+
| 1 |      | Busy |      |
| 2 | Busy | Busy | Busy |
| 3 | Busy | Busy |      |
| 4 |      |      |      |
| 5 |      |      | Busy |
| 6 | Busy | Busy |      |
+---+------+------+------+

解决方案是 (A,1), (C,3), (B,4)。如果我们从 (C,1) 开始，那么它将以 (A,5) 或 (B,5) 结束。因为 4 < 5，所以第一个解是正确的。 我该如何解决这个问题？

视觉解决方案:

+---+----------+----------+----------+
|   |    A     |    B     |    C     |
+---+----------+----------+----------+
| 1 | SELECTED | Busy     |          |
| 2 | Busy     | Busy     | Busy     |
| 3 | Busy     | Busy     | SELECTED |
| 4 |          | SELECTED |          |
| 5 |          |          | Busy     |
| 6 | Busy     | Busy     |          |
+---+----------+----------+----------+

Answer 1

这会将您的满意度问题转变为优化问题。也就是说，仅找到 解决方案是不够的，您需要最佳 解决方案。所以对于 MiniZinc 模型，您需要更改

solve :: int_search(x, first_fail, indomain_min, complete) satisfy;

类似于

solve :: int_search(x, first_fail, indomain_min, complete) minimize max(x);

最小化最大分配时间。