2

この動作中の 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     |          |
+---+----------+----------+----------+
4

2 に答える 2

5

ハカン（原型製作者）です。私がそれを正しく理解していれば、あなたの質問は、実際にはソリューション自体を見つけることではなく、最適なソリューションの表を提示する方法です (私がテストしたすべての FlatZinc ソルバーはすぐに解決しました)。

テーブルを作成する 1 つの方法は、スピーカーが選択されている (1)、話し中 (-1)、または利用できない (0) 場合の情報を含むヘルプ マトリックス ("m") を用意することです。

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: もう 1 つの方法は、より効果的な no_overlap/4 の代わりにcumulative/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 を最小化する」の代わりに、別の検索ヒューリスティックをテストしたい場合があります。)

于 2013-12-23T20:18:06.203 に答える
2

以前の質問Constraint Programming: Scheduling Speaker in shortest timeについてコメントしたように、これには累積的な制約が適しています。Minizinc コードは手元にありませんが、ECLiPSe ( http://eclipseclp.org ) にモデルがあります。

:- lib(ic).
:- lib(ic_edge_finder).
:- lib(branch_and_bound).

solve(JobStarts, Cost) :-
    AllUnavStarts = [[2,6],[1,6],[2,5]],
    AllUnavDurs   = [[2,1],[3,1],[1,1]],
    AllUnavRess   = [[1,1],[1,1],[1,1]],
    JobDurs = [1,2,1],
    Ressources = [1,1,1],
    length(JobStarts, 3),
    JobStarts :: 1..9,

    % the jobs must not overlap with each other
    cumulative(JobStarts, JobDurs, Ressources, 1),

    % for each speaker, no overlap of job and unavailable periods
    (
        foreach(JobStart,JobStarts),
        foreach(JobDur,JobDurs),
        foreach(UnavStarts,AllUnavStarts),
        foreach(UnavDurs,AllUnavDurs),
        foreach(UnavRess,AllUnavRess)
    do
        cumulative([JobStart|UnavStarts], [JobDur|UnavDurs], [1|UnavRess], 1)
    ),

    % Cost is the maximum end date
    ( foreach(S,JobStarts), foreach(D,JobDurs), foreach(S+D,JobEnds) do true ),
    Cost #= max(JobEnds),

    minimize(search(JobStarts,0,smallest,indomain,complete,[]), Cost).
于 2013-12-23T21:24:42.627 に答える