Setup-Zeit mit Kumulativen ausdrücken

Question

Es gibt viele Familien von Planungsproblemen. Ich untersuche ein Problem, wo Ich habe Familien von Jobs/Aufgaben, wo der Übergang von einer Familie zu einer anderen Familie erfordern Neukonfiguration der Maschine (Setup-Zeit).

Ich benutze cumulatives[2/3], um dieses Problem zu lösen, aber ich bin unsicher, wie die Setup-Zeit ausgedrückt werden könnte.

In diesem kleinen Beispiel habe ich 10 Aufgaben, die zu 3 verschiedenen Familien gehören. Jeder Task kann auf jedem Computer ausgeführt werden, aber ein Wechsel von einer Task in einer Familie zu einer anderen Task in einer anderen Familie erfordert das Hinzufügen einer Setup-Zeit.

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

Ein gültiger Zeitplan (aber optimal nicht) können sein:

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

Wie ist der beste Weg, dies mit cumulatives[2/3] Verwendung zusammen auszudrücken? Indem Sie die Dauer jeder Aufgabe zu einer Domänenvariablen machen und zusätzliche Einschränkungen hinzufügen?

Answer 1

Erstens, kumulatives/[2,3] hat keine Option für Ausdruck-Setup-Zeiten, also muss man explizite Bedingungen posten, wenn "zwei Aufgaben verschiedener Familien auf demselben Rechner laufen, dann muss ein Lücke zwischen dem Ende der Vorgängeraufgabe und dem Beginn der Nachfolgeraufgabe ".

Dies kann durch den Aufruf codiert werden:

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]), 

wie folgt definiert:

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

Zweitens, wenn die Maschinen austauschbar wie in Ihrem Beispiel sind, können Sie Symmetrien brechen durch das 1 Einführung erfolgen soll vor 2 und 2 sollte vor 3 auftreten in ms:

definiert als:

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

Drittens ist es eine viel bessere Suchstrategie, alle Maschinen vor allen Startzeiten zu reparieren. Noch eine weitere Verfeinerung ist (a) fixieren die Maschinen, (b) verengen die Intervalle der Aufgaben genug, um eine Bestellung pro Maschine zu verhängen, (c) fixieren die Startzeiten:

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

Mit diesen Änderungen die optimale Lösung mit einem Optimalitätsnachweis wird in einigen 550 ms erhalten:

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