Planen von Aufgaben zu einer einzigen Ressource mit Prolog

Question

Ich suchte hier durch, so gut ich konnte, und obwohl ich einige relevanten Fragen gefunden, ich glaube nicht, dass sie die Frage auf der Hand bedeckt:

Nehmen Sie eine einzelne Ressource und eine bekannte Liste der Anfragen, eine Aufgabe zu planen. Jede Anforderung enthält eine start_after, start_by, expected_duration und Aktion.

Das Ziel ist es, die Aufgaben für die Ausführung zu planen, so bald wie möglich, während jede Aufgabe zwischen start_after und start_by geplant zu halten.

I codiert ein einfaches Prolog Beispiel, dass ich „dachte“ sollte funktionieren, aber ich habe leider wurden Fehler während der Laufzeit immer: „> = / 2: Argumente sind nicht ausreichend instanziiert“.

Jede Hilfe oder Ratschläge wäre sehr dankbar

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

Edit: Konflikte Ziel war es nicht ganz richtig. benötigte zusätzliche T> T1 Klausel

Edit: Offenbar mein Zeitplan Ziel funktioniert, wenn ich gültige Anforderung, Zeitpaare liefern ... aber ich bin fest versucht Prolog zu zwingen, gültige Werte für T1..3 zu finden, wenn R1..3 gegeben?

Answer 1

Es gibt ein paar Probleme mit der ursprünglichen Umsetzung. Es könnte OK (mit geringfügigen Änderungen) in einem Constraint-Logik-Programmiersystem arbeiten, aber nicht in geraden Prolog. In Prolog, ist die Reihenfolge der Ziele von entscheidender Bedeutung. Ich habe den Code so modifiziert, dass es funktionieren wird:

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

Ich habe die Verwendung des zwischen / 3-Prädikat (a definierte builtin in einigen Prolog-Implementierungen). Es erzeugt die ganzen Zahlen zwischen zwei vorgegebenen Endpunkten.

habe ich Ungleichheit Kontrollen im Zeitplan / 6 zu zwingen, R1, R2 und R3 unterschiedliche Werte zu sein.

Schließlich neu geordnet ich die Ziele in Zeitplan / 6, um sicherzustellen, dass das can_run / 2 Prädikat für ein Paar Ri / Ti Variablen ausgewertet wurde, bevor diese Variablen durch Konflikte / 3 geprüft wurden.

Der Abfragezeitplan (R1, T1, R2, T2, R3, T3) ausgeführt wird für mehrere Minuten und schließlich produziert:

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

Es gibt viele effizienten Implementierungen für dieses Problem.