首先,cumulatives/[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)
)
)
).
其次,如果机器像您的示例中那样可以互换,您可以通过在 Ms 中强制 1 应该出现在 2 之前并且 2 应该出现在 3 之前来打破对称性:
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]).
通过这些更改,可在约 550 毫秒内获得具有最优性证明的最佳解决方案:
| ?- 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