约束编程：在最短的时间内安排演讲者

Question

我正在尝试改编 Hakan Kjellerstrand (@hakankless) 已经解决的约束编程问题，并且需要一些帮助。

原来解决的问题：有6个公共扬声器和6个房间。每个发言者应分配到一个房间，不能留有任何房间，并且每个发言者只能在一个房间内。

解决方案在这里：Google OR-Tools & MiniZinc

帮助进行此调整：有 3 位公共演讲者和 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, the first solution is correct. 我该如何解决这个问题？

视觉解决方案：

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

Answer 1

这会将您的满意度问题变成优化问题。也就是说，仅仅找到a解决方案是不够的，您需要最优解决方案。因此对于 MiniZinc 型号，您需要更改

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

类似的事情

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

最小化最大分配时间。

Answer 2

你的数组尺寸混淆了。如果您为变量提供更有意义的名称，使其更明显，那么它的范围会有所帮助。

include "globals.mzn";

int: n = 3; % number of speakers
int: s = 6; % number of slots
array[1..n] of set of 1..s: available; % the available slots
array[1..n] of var 1..s: speaks_at; % the allotted speaker slot

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

constraint
   all_different(speaks_at)
   /\
   forall(i in 1..n) (
      speaks_at[i] in available[i]
   )
;

% at which slot is each speaker available to speak
available = [
    {1,4,5},  
    {4,5},  
    {1,3,4,6}  
];

output
[
    show(speaks_at)
];

这给出了预期的答案：

% Starting search
Found a solution with cost 4
speaks_at = array1d(1..3, [1,4,3]);
% Minimum objective value = 4
% Total time 0.016s cpu (0.000 setup + 0.000 search)
----------