optimization - 优化工作调度MiniZinc代码——约束规划

Question

请你帮忙优化this工作 MiniZinc 代码:

任务:有一个有 6 个时间段的 session 。有 3 位演讲者参加了 session ，每个人都可以在特定的时段出席。每个演讲者将在预定数量的时段内进行演讲。

目标:制定发言者最早结束的时间表。

示例:演讲者 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)
     )
 )

;

然后矩阵“m”可以这样打印:

% ...
++
[ 
   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

] ;

一如既往，有不止一种方法可以做到这一点，但我决定采用这种方法，因为它非常直接。

这是完整的模型: http://www.hakank.org/minizinc/scheduling_speakers_optimize.mzn

更新:添加模型的输出:

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             
----------
==========

更新 2: 另一种方法是使用 cumulative/4 而不是 no_overlap/4 这应该更有效，即

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)
;

这是修改后的版本(结果相同) http://www.hakank.org/minizinc/scheduling_speakers_optimize2.mzn (我还跳过了表示矩阵“m”，并在输出部分进行了所有表示。)

对于这个简单的问题实例，没有明显的区别，但对于更大的实例，这应该更快。 (对于更大的实例，人们可能想要测试不同的搜索启发式而不是“解决最小化 z”。)