7

调度问题有很多族。我正在研究一个问题，我有一系列工作/任务，从一个家庭过渡到另一个家庭需要重新配置机器（设置时间）。

我正在使用cumulatives[2/3]来解决这个问题，但我不确定如何表达设置时间。

在这个小例子中，我有 10 个任务属于 3 个不同的家庭。任何任务都可以在任何机器上运行，但是从一个系列中的一个任务切换到另一个系列中的另一个任务需要添加设置时间。

:- 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]什么？通过使每个任务的持续时间成为域变量并为其添加额外的约束？

4

1 回答 1

8

首先，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
于 2014-05-26T09:51:07.373 回答