prolog - Expresando el tiempo de configuración con acumulativos

job-scheduling constraint-programming

Question

Hay muchas familias de problemas de programación. Estoy investigando un problema en el que tengo familias de trabajos / tareas en los que la transición de una familia a otra requiere la reconfiguración de la máquina (tiempo de configuración).

Estoy usando cumulatives[2/3] para resolver este problema, pero no estoy seguro de cómo se puede expresar el tiempo de configuración.

En este pequeño ejemplo, tengo 10 tareas que pertenecen a 3 familias diferentes. Cualquier tarea puede ejecutarse en cualquier máquina, pero un cambio de una tarea en una familia a otra tarea en otra familia requiere un tiempo de configuración para ser agregado.

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

Un horario válido (pero no óptimo) podría ser:

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

¿Cuál es la mejor manera de expresar esto junto con el uso de cumulatives[2/3] ? ¿Al hacer que la duración de cada tarea sea una variable de dominio y agregarle restricciones adicionales?

Answer 1

Primero, acumulativos / [2,3] no tiene una opción para los tiempos de configuración de la expresión, por lo que uno tiene que publicar restricciones explícitas que expresen "si dos tareas de familias diferentes se ejecutan en la misma máquina, entonces debe haber un espacio entre el final de la tarea predecesora y el inicio de la tarea sucesora ".

Esto se puede codificar llamando:

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

definido como:

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

En segundo lugar, si las máquinas son intercambiables como en su ejemplo, puede romper simetrías imponiendo que 1 debe ocurrir antes de que 2 y 2 ocurran antes de 3 en Ms:

value_order(Ms),

definido como:

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

En tercer lugar, arreglar todas las máquinas antes de todas las horas de inicio es una estrategia de búsqueda mucho mejor. Sin embargo, otro refinamiento es (a) reparar las máquinas, (b) reducir los intervalos de las tareas lo suficiente como para imponer una orden por máquina, (c) fijar las horas de inicio:

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

Con estos cambios, la solución óptima con la prueba de optimalidad se obtiene en unos 550 ms:

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