表達設置時間與累積值

有安排上的問題，許多家庭。我期待到那裏我的地方從一個家庭到另一個家庭過渡需要重新配置機器（建立時間）工作/家庭任務的一個問題。表達設置時間與累積值

我使用cumulatives[2/3]來解決這個問題，但我不確定如何設置時間可以表示。

在這個小例子，我有屬於3個不同家庭的10種任務。任何任務都可以在任何機器上運行，但是從一個系列中的一個任務切換到另一個系列中的另一個任務需要添加安裝時間。

:- use_module(library(clpfd)). 
:- use_module(library(lists)). 

go(Ss, Es, Ms, Tm, Lab) :- 

    Ss = [S1, S2, S3, S4,S5,S6,S7,S8,S9,S10], %Starttimes 
    Es = [E1, E2, E3, E4,E5,E6,E7,E8,E9,E10], %Endtimeds 
    Ms = [M1, M2, M3, M4,M5,M6,M7,M8,M9,M10], %MachineIds 



    domain(Ss, 1, 30), 
    domain(Es, 1, 30), 
    domain(Ms, 1, 3), 

    Tasks = [ 
     %Family 1: Setuptime, Su1 = 4, 
     task( S1, 6, E1, 1, M1), %Task T1 
     task( S2, 6, E2, 1, M2), %Task T2 
     task( S3, 3, E3, 1, M3), %Task T3 
     task( S4, 7, E4, 1, M4), %Task T4 
     %Family 2: Setuptime, Su2 = 3 
     task( S5, 5, E5, 1, M5), %Task T5 
     task( S6, 8, E6, 1, M6), %Task T6 
     task( S7, 4, E7, 1, M7), %Task T7 
     %Family 3: Setuptime, Su3 = 5 
     task( S8, 4, E8, 1, M8), %Task T8 
     task( S9, 4, E9, 1, M9), %Task T9 
     task(S10, 5, E10, 1, M10) %Task T10 
    ], 

    %All machines has resource capacity = 1 
    Machines = [ 
     machine( 1, 1), %M1 
     machine( 2, 1), %M2 
     machine( 3, 1) %M3 
    ], 

    cumulatives(Tasks, Machines, [bound(upper),task_intervals(true)]), 

    maximum(MaxEndTime, Es), 

    %Make the list of options to pass to the labeling predicate 
    append([ [minimize(MaxEndTime)], [time_out(Tm, _)], Lab ], LabOpt), 
    Vars=[S1,M1,S2,M2,S3,M3,S4,M4,S5,M5,S6,M6,S7,M7,S8,M8,S9,M9,S10,M10], 
    labeling(LabOpt, Vars).

一個有效的時間表（但不是最優的）可能是：

M1: Su1,T1,T2,Su3,T10 
M2: Su2,T5,T6,Su3,T8 
M3: Su1,T3,T4,Su2,T7,Su3,T9

如何與使用cumulatives[2/3]一起表達這一點的最好方法是什麼？通過使每個任務的持續時間成爲一個域變量並向其添加額外的約束條件？

來源

2014-05-23 MortenM

首先，累積值/ [2,3]沒有表達安裝時間的選擇，所以一個個有張貼明確的約束表達「如果不同家庭的兩個任務在同一臺機器上運行，則必須有一個前任任務結束和後繼任務開始之間的差距「。

這可以通過調用編碼：

setups(Ss, Ms, [6,6,3,7,5,8,4,4,4,5], [1,1,1,1,2,2,2,3,3,3], [4,4,4,4,3,3,3,5,5,5]),

定義爲：

% post setup constraints for start times Ss, machines Ms, durations 
% Ds, task families Fs, and setup times Ts 
setups(Ss, Ms, Ds, Fs, Ts) :- 
    ( fromto(Ss,[S1|Ss2],Ss2,[]), 
     fromto(Ms,[M1|Ms2],Ms2,[]), 
     fromto(Ds,[D1|Ds2],Ds2,[]), 
     fromto(Fs,[F1|Fs2],Fs2,[]), 
     fromto(Ts,[T1|Ts2],Ts2,[]) 
    do ( foreach(S2,Ss2), 
      foreach(M2,Ms2), 
      foreach(D2,Ds2), 
      foreach(F2,Fs2), 
      foreach(T2,Ts2), 
      param(S1,M1,D1,F1,T1) 
     do ( F1 = F2 -> true 
      ; % find forbidden interval for S2-S1 if on same machine 
       L is 1-(T1+D2), 
       U is (T2+D1)-1, 
       StartToStart in \(L..U), 
       (M1#\=M2 #\/ S2 - S1 #= StartToStart) 
      ) 
     ) 
    ).

其次，如果機器是可以互換的，如你的榜樣，您可以通過施加1應該出現打破對稱性在2和2之前應該發生在3之前的Ms：

value_order(Ms),

定義爲：

value_order(Ms) :- 
    automaton(Ms, [source(q0),sink(q0),sink(q1),sink(q2)], 
       [arc(q0,1,q1), 
       arc(q1,1,q1), arc(q1,2,q2), 
       arc(q2,1,q2), arc(q2,2,q2), arc(q2,3,q2)]).

第三，在所有開始時間之前修復所有機器是一個更好的搜索策略。又一個改進是：（a）固定的機器，（b）中縮小的任務足夠的間隔施加每臺機器的順序，（c）中固定的開始時間：

Q1 #= S1/6, 
    Q2 #= S2/6, 
    Q3 #= S3/3, 
    Q4 #= S4/7, 
    Q5 #= S5/5, 
    Q6 #= S6/8, 
    Q7 #= S7/4, 
    Q8 #= S8/4, 
    Q9 #= S9/4, 
    Q10 #= S10/5, 
    labeling([minimize(MaxEndTime)/*,time_out(Tm, _)*/|Lab], 
      [M1,M2,M3,M4,M5,M6,M7,M8,M9,M10, 
       Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8,Q9,Q10, 
       S1,S2,S3,S4,S5,S6,S7,S8,S9,S10]).

隨着這些變化，最佳的在一些550ms獲得具有最優的證明溶液：

| ?- statistics(runtime,_), go(Ss,Es,Ms,_,[step]), statistics(runtime,R). 
Ss = [1,7,1,13,7,12,17,1,5,9], 
Es = [7,13,4,20,12,20,21,5,9,14], 
Ms = [1,1,2,1,2,2,3,3,3,3], 
R = [1621540,550] ? 
yes

來源

2014-05-26 09:51:07

表達設置時間與累積值

回答

相關問題