优化工作计划的MiniZinc代码-约束编程 [英] Optimizing working scheduling MiniZinc code - constraint programming

问题描述

请帮助您优化此有效的MiniZinc代码:

Please can you help optimize this working MiniZinc code:

任务:有一个会议有6个时隙.有3位发言人参加会议，每个发言人在某些时段可用.每个扬声器将出现预定数量的插槽.

Task: There is a conference which has 6x time slots. There are 3 speakers attending the conference who are each available at certain slots. Each speaker will present for a predetermined number of slots.

目标:制定安排时间最早的演讲者.

Objective: Produce the schedule that has the earliest finish of speakers.

示例:演讲者A，B和C.通话时间= [1、2、1]

Example: Speakers A, B & C. Talk durations = [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

Link to working MiniZinc code: 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     |          |
+---+----------+----------+----------+

推荐答案

我是hakank(原始模型的作者).如果我理解正确，那么您现在的问题是如何显示最佳解决方案表，而不是真正地找到解决方案本身(我测试过的所有FlatZinc求解器都很快就解决了该问题).

I'm hakank (author of the original model). If I understand it correctly, your question now is how to present the table for the optimal solution, not really about finding the solution itself (all FlatZinc solvers I tested solved it in no time).

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

One way of creating the table is to have a help matrix ("m") which contain information if a speaker is selected (1), busy (-1) or not available (0):

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

然后必须在矩阵和其他决策变量("starting_slot"和"ending_slot")中连接信息:

Then one must connect info in this the matrix and the other decision variables ("starting_slot" and "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":

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.

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

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

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

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

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

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

对于这个简单的问题实例，没有明显的区别，但是对于较大的实例，这应该更快. (对于较大的实例，可能要测试不同的搜索试探法，而不是求解最小化z".)

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".)

这篇关于优化工作计划的MiniZinc代码-约束编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！