Pianificazione delle attività di una singola risorsa utilizzando Prolog

Question

Ho cercato di qui come meglio ho potuto e anche se ho trovato alcune domande pertinenti, non credo che hanno coperto la questione a portata di mano:

Si supponga una singola risorsa e un elenco noto di richieste per pianificare un'attività. Ogni richiesta include uno start_after, start_by, expected_duration, e l'azione.

L'obiettivo è quello di pianificare le attività per l'esecuzione nel più breve tempo possibile, mantenendo ogni operazione pianificata tra lo start_after e start_by.

ho codificato un semplice esempio Prolog che ho "pensato" dovrebbe funzionare, ma ho purtroppo ottenendo gli errori in fase di esecuzione: "> = / 2: Gli argomenti non sono sufficientemente istanze".

Qualsiasi aiuto o consiglio sarebbe molto apprezzato

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

Modifica: conflitti obiettivo non era giusto: necessario ulteriore T> clausola T1

.

Modifica: A quanto pare il mio obiettivo programma funziona se fornisco valida richiesta, coppie di tempo ... ma mi sono bloccato cercando di forzare Prolog per trovare i valori validi per T1..3 quando somministrato R1..3?

Answer 1

Ci sono un paio di problemi con l'implementazione originale. Potrebbe funzionare OK (con piccole modifiche) in un sistema di programmazione logica forzatamente, ma non in Prolog rettilineo. In Prolog, l'ordinamento degli obiettivi è fondamentale. Ho modificato il codice in modo che funzioni:

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

Ho aggiunto l'uso del fra / 3 predicato (un definito BuiltIn in alcune implementazioni Prolog). Esso genera i numeri interi tra due date finali.

Ho aggiunto controlli disuguaglianza nella pianificazione / 6 forzare R1, R2, e R3 come valori diversi.

Infine, riordinate gli obiettivi di programma / 6 per garantire che il / 2 predicato can_run è stato valutato per un paio di Ri / variabili Ti prima quelle variabili sono stati controllati da conflitti / 3.

La query schedule (R1, T1, R2, T2, R3, T3) viene eseguito per diversi minuti e infine produce:

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

Non ci sono implementazioni molto più efficienti per questo problema.