Scheduling of tasks to a single resource using Prolog

Question

I searched through here as best I could and though I found some relevant questions, I don't think they covered the question at hand:

Assume a single resource and a known list of requests to schedule a task. Each request includes a start_after, start_by, expected_duration, and action.

The goal is to schedule the tasks for execution as soon as possible while keeping each task scheduled between start_after and start_by.

I coded up a simple Prolog example that I "thought" should work but I've been unfortunately getting errors during run time: ">=/2: Arguments are not sufficiently instantiated".

Any help or advice would be greatly appreciated

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: conflicts goal wasn't quite right: needed extra T>T1 clause.

Edit: Apparently my schedule goal works if I supply valid Request,Time pairs ... but I'm stuck trying to force Prolog to find valid values for T1..3 when given R1..3?

Answer 1

There are a couple of problems with the original implementation. It might work OK (with minor modifications) in a constraint logic programming system, but not in straight Prolog. In Prolog, the ordering of goals is crucial. I have modified the code so that it will work:

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 added the use of the between/3 predicate (a defined builtin in some Prolog implementations). It generates the integers between two given endpoints.

I added inequality checks in schedule/6 to force R1, R2, and R3 to be different values.

Finally, I reordered the goals in schedule/6 to ensure that the can_run/2 predicate was evaluated for a pair of Ri/Ti variables before those variables were checked by conflicts/3.

The query schedule(R1,T1,R2,T2,R3,T3) runs for several minutes and finally produces:

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

There are much more efficient implementations for this problem.