La programación de tareas a un solo recurso utilizando Prolog

Question

He buscado por aquí lo mejor que pude y aunque he encontrado algunas preguntas pertinentes, no creo que cubrían la cuestión que nos ocupa:

Supongamos que un solo recurso y una lista conocida de solicitudes para programar una tarea. Cada petición incluye un start_after, start_by, expected_duration, y la acción.

El objetivo es programar las tareas para la ejecución tan pronto como sea posible, manteniendo cada tarea programada entre start_after y start_by.

I codificado por un simple ejemplo Prolog que "pensaba" debería funcionar, pero por desgracia he estado recibiendo errores en tiempo de ejecución: "> = / 2: Los argumentos no se crean instancias suficientemente".

Cualquier ayuda o consejo sería muy apreciada

startAfter(1,0).
startAfter(2,0).
startAfter(3,0).

startBy(1,100).
startBy(2,500).
startBy(3,300).

duration(1,199).
duration(2,199).
duration(3,199).

action(1,'noop1').
action(2,'noop2').
action(3,'noop3').

can_run(R,T) :- startAfter(R,TA),startBy(R,TB),T>=TA,T=<TB.
conflicts(T,R1,T1) :- duration(R1,D1),T=<D1+T1,T>T1.
schedule(R1,T1,R2,T2,R3,T3) :- 
           can_run(R1,T1),\+conflicts(T1,R2,T2),\+conflicts(T1,R3,T3),
           can_run(R2,T2),\+conflicts(T2,R1,T1),\+conflicts(T2,R3,T3),
           can_run(R3,T3),\+conflicts(T3,R1,T1),\+conflicts(T3,R2,T2).

% when traced I *should* see T1=0, T2=400, T3=200

Editar: conflictos objetivo no era del todo bien:. T necesaria adicional> cláusula T1

Editar: Al parecer, mi objetivo programación funciona si yo proporciono solicitud válida, pares de tiempo ... pero estoy atascado tratando de forzar Prolog para encontrar los valores válidos para T1..3 cuando se administra R1..3?

Answer 1

Hay un par de problemas con la implementación original. Puede que funcione bien (con modificaciones menores) en un sistema de programación lógica limitación, pero no en Prolog recta. En Prolog, el orden de los objetivos es crucial. He modificado el código para que se trabajará:

can_run(R, T) :-
    startAfter(R,TA),
    startBy(R,TB),
    between(TA,TB,T).

conflicts(T,R1,T1) :- 
    duration(R1,D1),
    T=<D1+T1,
    T>=T1.

schedule(R1,T1,R2,T2,R3,T3) :- 
    can_run(R1,T1), 
    can_run(R2,T2), 
    R1 \= R2,
    \+ conflicts(T1,R2,T2),
    can_run(R3,T3),
    R3 \= R1, 
    R3 \= R2,
    \+ conflicts(T1,R3,T3),
    \+ conflicts(T2,R1,T1),
    \+ conflicts(T2,R3,T3),
    \+ conflicts(T3,R1,T1),
    \+ conflicts(T3,R2,T2).

between(Low, High, Between) :-
    Between is Low
    ;
    Low < High,
    Next is Low + 1,
    between(Next, High, Between).

I añade el uso de la entre / 3 predicado (una orden interna definida en algunas implementaciones Prolog). Genera los números enteros entre dos puntos finales dadas.

I añadió comprobaciones de desigualdad en horario / 6 para forzar R1, R2, y R3 para ser valores diferentes.

Finalmente, reordena los objetivos de la Lista / 6 para asegurar que el / 2 predicado can_run se evaluó por un par de variables Ri / Ti antes de que esas variables fueron comprobados por conflictos / 3.

El horario de consulta (R1, T1, R2, T2, R3, T3) tiene una duración de varios minutos y, finalmente, produce:

?-schedule(R1,T1,R2,T2,R3,T3)
R1 = 1
T1 = 0
R2 = 2
T2 = 400
R3 = 3
T3 = 200

Existen implementaciones mucho más eficiente para este problema.