优化工作调度 MiniZinc 代码——约束编程

Question

请你帮助优化这个工作的 MiniZinc 代码：

任务：有一个有 6 个时隙的会议。有 3 位演讲者参加了会议，每个人都可以在特定的时段使用。每个扬声器将出现预定数量的插槽。

目标：生成发言者最早完成的时间表。

示例：演讲者 A、B 和 C。演讲时长 = [1, 2, 1]

扬声器可用性：

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

链接到工作 MiniZinc 代码：http ://pastebin.com/raw.php?i=jUTaEDv0

我希望优化的内容：

% ensure allocated slots don't overlap and the allocated slot is free for the speaker
constraint 
    forall(i in 1..num_speakers) (
        ending_slot[i] = starting_slot[i] + app_durations[i] - 1
    ) /\
    forall(i,j in 1..num_speakers where i < j) (
        no_overlap(starting_slot[i], app_durations[i], starting_slot[j], app_durations[j])
    ) /\
    forall(i in 1..num_speakers) (
        forall(j in 1..app_durations[i]) (
            starting_slot[i]+j-1 in speaker_availability[i]
        )
    ) 
;

预期解决方案：

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

Answer 1

我是 hakank（原始模型的作者）。如果我理解正确，那么您现在的问题是如何呈现最佳解决方案的表格，而不是真正找到解决方案本身（我测试的所有 FlatZinc 求解器都立即解决了它）。

创建表格的一种方法是使用帮助矩阵 ("m")，其中包含选择 (1)、忙碌 (-1) 或不可用 (0) 发言人的信息：

array[1..num_slots, 1..num_speakers] of var -1..1: m;

然后必须连接矩阵中的信息和其他决策变量（“starting_slot”和“ending_slot”）：

% connect to matrix m
constraint
   forall(t in 1..num_slots) (
      forall(s in 1..num_speakers) (
         (not(t in speaker_availability[s]) <-> m[t,s] = -1) 
          /\
          ((t >= starting_slot[s] /\ t <= ending_slot[s]) <-> m[t,s] = 1)
     )
 )

;

Then the matrix "m" can be printed like this:

% ...
++
[ 
   if s = 1 then "\n" else " " endif ++
   if fix(m[t,s]) = -1 then 
      "Busy    " 
   elseif fix(m[t,s]) =  1 then 
      "SELECTED" 
   else
      "        "
   endif
 | t in 1..num_slots, s in 1..num_speakers

] ;

As always, there are more than one way of doing this, but I settled with this since it's quite direct.

Here's the complete model: http://www.hakank.org/minizinc/scheduling_speakers_optimize.mzn

Update: Adding the output of the model:

Starting:  [1, 4, 3]
Durations: [1, 2, 1]
Ends:      [1, 5, 3]
z:         5

SELECTED Busy             
Busy     Busy     Busy    
Busy     Busy     SELECTED
         SELECTED         
         SELECTED Busy    
Busy     Busy             
----------
==========

Update 2: Another way is to use cumulative/4 instead of no_overlap/4 which should be more effective, i.e.

constraint 
    forall(i in 1..num_speakers) (
    ending_slot[i] = starting_slot[i] + app_durations[i] - 1
    ) 
    % /\ % use cumulative instead (see below)
    % forall(i,j in 1..num_speakers where i < j) (
    %   no_overlap(starting_slot[i], app_durations[i], starting_slot[j], app_durations[j])
    % ) 
    /\
    forall(i in 1..num_speakers) (
    forall(j in 1..app_durations[i]) (
        starting_slot[i]+j-1 in speaker_availability[i]
           )
    ) 

    /\ cumulative(starting_slot, app_durations, [1 | i in 1..num_speakers], 1)
;

Here's the altered version (which give the same result) http://www.hakank.org/minizinc/scheduling_speakers_optimize2.mzn (I've also skipped the presentation matrix "m" and do all presentation in the output section.)

For this simple problem instance, there is no discernible difference, but for larger instances this should be faster. (And for larger instances, one might want to test different search heuristics instead of "solve minimize z".)