Scheduler critique

[jjtolton]

I adapted the resource constrained scheduler code from Prolog Programming for Artificial Intelligence.

It runs, and I think it's monotonic-ish, but I feel like there is a lot of room for improvement. In particular I feel like it's not really making good use of the more advanced features of clpz.

I've been manually checking results but I'm not exactly sure how to "prove" correctness.

Let me know what you think!

Gist: https://gist.github.com/jjtolton/d4d708c38a6769c64434a7869a26eabb

Code:

:- use_module(library(lists)).
:- use_module(library(dif)).
:- use_module(library(debug)).
:- use_module(library(simplex)).
:- use_module(library(clpz)).
:- use_module(library(reif)).


precedence_constr( [], [], FinTime).
precedence_constr( [T/D | TDs], [T/Proc/Start/D | Rest], FinTime) :-
        Start #>= 0,            % Earliest start at 0
        Start + D #=< FinTime , % Must finish by FinTime
        precedence_constr( TDs, Rest, FinTime),
        prec_constr( T/Proc/Start/D, Rest).

prec_constr( T/P/S/D, []).
prec_constr( T/P/S/D, [T1/P1/S1/D1 | Rest]) :-
        (   prec(T,T1), #=<(S+D, S1)
        ;   prec(T1,T), #=<(S1+D1, S)
        ;   true
        ),
        prec_constr( T/P/S/D, Rest).

assign_processors( [], FinTime).
assign_processors( [T/P/S/D|Schedule], FinTime) :-
        resource(T, Resources),
        member(P, Resources),
        assign_processors(Schedule, FinTime),
        resource_constr(T/P/S/D, Schedule).

resource_constr(_, []).
resource_constr(Job, [Job1|Schedule]) :-
        no_conflict(Job,Job1),
        resource_constr(Job, Schedule).

% noconflict(Job1, Job2): not conflicting if different processors or same processor with no time overlap
no_conflict( T/P/S/D, T1/P1/S1/D1) :-
        (   dif(P,P1) 
        ;   S+D#=<S1
        ;   S1+D1#=<S
        ).
            

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Environment
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

% List of tasks to ;be scheduled
tasks( [t1/4,t2/2,t3/2, t4/20, t5/20, t6/11, t7/11]).

% Precedence constraints
prec( t1, t4). prec( t1, t5). prec( t2, t4). prec( t2, t5).
prec( t2, t6). prec( t3, t5). prec( t3, t6). prec( t3, t7).

% resource( Task, Processors):
% Any processor in Processors suitable for Task
resource( _, [1,2,3]).   % Three processors, all suitable for any task

% should probably be a lambda, for forcing enumeration of start times
start(_/_/S/_, S).


schedule(FinTime, Schedule, Task) :- 
        tasks(TasksDurs),
        precedence_constr(TasksDurs, Schedule, FinTime),
        assign_processors(Schedule, FinTime),
        maplist(start, Schedule, Starts),
        labeling([ff], Starts).
        
              
?- FinTime #=< 26, schedule(FinTime, Schedule, Task).
%@    FinTime = 26, Schedule = [t1/1/2/4,t2/1/0/2,t3/2/0/2,t4/1/6/20,t5/2/6/20,t6/3/2/11,t7/3/13/11]
%@ ;  FinTime = 26, Schedule = [t1/1/2/4,t2/1/0/2,t3/2/0/2,t4/1/6/20,t5/2/6/20,t6/3/2/11,t7/3/14/11]
%@ ;  FinTime = 26, Schedule = [t1/1/2/4,t2/1/0/2,t3/2/0/2,t4/1/6/20,t5/2/6/20,t6/3/2/11,t7/3/15/11]
%@ ;  FinTime = 26, Schedule = [t1/1/2/4,t2/1/0/2,t3/2/0/2,t4/1/6/20,t5/2/6/20,t6/3/3/11,t7/3/14/11]
%@ ;  ... .

Original code from book:

schedule( BestSchedule, BestTime) :-
        (   tasks(TasksDurs),
            precedence_constr( TasksDurs, Schedule, FinTime), % Set up precedence inequalities
            initialize_bound,
            assign_processors( Schedule, FinTime), % Assign processors to tasks
            minimize( FinTime),
            update_bound( Schedule, FinTime),
            fail                % Backtrack to find more schedules
        ;   bestsofar( BestSchedule, BestTime)
        ).         % Final best


% precedence_constr( TasksDurs, Schedule, FinTime):
% For given tasks and their durations, construct a structure Schedule
% comprising start time variables. These variables and finishing time FinTime
% are constrained by inequalities due to precedences.
precedence_constr( [], [], FinTime).
precedence_constr( [T/D | TDs], [T/Proc/Start/D | Rest], FinTime) :-
        { Start >= 0,           % Earliest start at 0
          Start + D =< FinTime }, % Must finish by FinTime
        precedence_constr( TDs, Rest, FinTime),
        prec_constr( T/Proc/Start/D, Rest).

prec_constr( _, []).
prec_constr( T/P/S/D, [T1/P1/S1/D1 | Rest]) :-
        (   prec(T,T1), !, { S+D =< S1}
        ;   prec( T1, T),!, { S1+D1 =< S}
        ;   true
        ),
        prec_constr( T/P/S/D, Rest).

% assign_processors( Schedule, FinTime):
% Assign processors to tasks in Schedule
assign_processors( [], FinTime).
assign_processors( [T/P/S/D | Rest], FinTime) :-
        assign_processors( Rest, FinTime),
        resource( T, Processors), % T can be executed by any of Processors
        member( P, Processors),   % Choose one of suitable processors
        resource_constr( T/P/S/D, Rest), % Impose resource constraints
        bestsofar( _, BestTimeSoFar),
        { FinTime < BestTimeSoFar }. % New schedule better than best so far

% resource_constr( ScheduledTask, TaskList):
% Construct constraints to ensure no resource conflict
% between ScheduledTask and TaskList
resource_constr( _, []).
resource_constr( Task, [Task1 | Rest]) :-
        no_conflict( Task, Task1),
        resource_constr( Task, Rest).

no_conflict( T/P/S/D, T1/P1/S1/D1) :-
        P \== P1,     !,         % Different processors
        prec( T, T1), !,         % Already constrained
        prec( T1, T), !,         % Already constrained
        (   S + D =< S1         % Same processor, no time overlap
        ;   S1 + D1 =< S
        ).
                                

initialize_bound :-
        (   retract(bestsofar(_,_)), fail
        ;   assert( bestsofar( dummy_schedule, 9999))
        ).  

% update_bound( Schedule, FinTime):
% update best schedule and time
update_bound( Schedule, FinTime) :-
        retract( bestsofar( _, _)), !,
        assert( bestsofar( Schedule, FinTime)).

% List of tasks to be scheduled
tasks( [t1/4,t2/2,t3/2, t4/20, t5/20, t6/11, t7/11]).

% Precedence constraints
prec( t1, t4). prec( t1, t5). prec( t2, t4). prec( t2, t5).
prec( t2, t6). prec( t3, t5). prec( t3, t6). prec( t3, t7).
% resource( Task, Processors):
% Any processor in Processors suitable for Task
resource( _, [1,2,3]).   % Three processors, all suitable for any task


?- schedule(BestSchedule, BestTime).

[jjtolton]

If feels like this could/should be done with DCGs again 🤔

I will say this section took me awhile to figure out how it worked:

precedence_constr( [], [], FinTime).
precedence_constr( [T/D | TDs], [T/Proc/Start/D | Rest], FinTime) :-
        Start #>= 0,            % Earliest start at 0
        Start + D #=< FinTime , % Must finish by FinTime
        precedence_constr( TDs, Rest, FinTime),
        prec_constr( T/Proc/Start/D, Rest).

prec_constr( T/P/S/D, []).
prec_constr( T/P/S/D, [T1/P1/S1/D1 | Rest]) :-
        (   prec(T,T1), #=<(S+D, S1)
        ;   prec(T1,T), #=<(S1+D1, S)
        ;   true
        ),
        prec_constr( T/P/S/D, Rest).

At first I thought it had to be some kind of mistake because this is at least an O(N^2 log^2 N) assignment of constraints, but I tried to find a better way to enforce the contraints, but I could not.

The assign_processors predicate does the same O(N^2 log^2 N) constraint assignment as well.

[hurufu]

(Side note, not relevant to your code) For tasks that involve scheduling with limited resources I really like linear logic it fits that problem space so well.

[jjtolton]

Wow that's cool! This linear logic?

[hurufu]

Yes it has nice interpretation that is useful for resource allocation. But implementing it in Prolog isn't trivial ;) I made an attempt in the past, it worked but had subtle bugs that were too hard to fix.

[jjtolton]

Ok, my cursory analysis of this program is that clp(z) does all the heavy lifting. I realize in full generality this is an NP-hard problem, but I was still a little shocked at how slow this implementation was. The book version uses a number of hacks such as !/0 and assertz/1ing a global bestsofar(BestSchedule, BestFinTime) to prune the search space, but I don't like that. It feels like we can do better while staying monotonic.

These predicates:

• precedence_constr (and helper predicate prec_constr)
• assign_processors (and helper predicates resource_constr and no_conflict)

exist to assign constraints clp(z) constraints.

clp(z), esp labeling/2, does all the work, as far as I can tell.

My maplist/3 -> labeling/2 usage in schedule/3 feels like a lucky hack that happened to work out. 🍀 🤔

This tantalizing clue in the clpz docs makes me think that much better use could be made of the simplex library in conjunction with clpz to get much better yields on this and more complex problems.

[jjtolton]

Actually, I'm not so sure it's that slow. I found this rather impressive:

schedule(FinTime, Schedule, Task) :- 
        tasks(TasksDurs),
        precedence_constr(TasksDurs, Schedule, FinTime),
        assign_processors(Schedule, FinTime),
        labeling([], [FinTime]),
        maplist(start, Schedule, Starts),
        labeling([], Starts).
        
?- FinTime #=< 22, schedule(FinTime, Schedule, Task).
%@    FinTime = 22, Schedule = [t1/1/2/4,t2/1/0/2,t3/2/0/2,t4/1/2/20,t5/2/2/20,t6/3/11/11,t7/3/0/11]
%@ ;  FinTime = 22, Schedule = [t1/1/3/4,t2/1/0/2,t3/2/0/2,t4/1/2/20,t5/2/2/20,t6/3/11/11,t7/3/0/11]
%@ ;  ... .

This found a lower bound than the version in the book, and fairly quickly.

What's even more impressive to me is this:

?- FinTime #=< 21, schedule(FinTime, Schedule, Task).
%@    false.

WOW! Now THAT is impressive! It fairly quickly determined that 21 is an (exclusive) lower bound!!

[jjtolton]

I'm going to open another discussion about how to automatically find the lower bound so that I don't hijack the thread again. 😓

[triska]

One comment regarding the discussions themselves: Personally, I see no reason to close such discussion topics: People barely had a few days to even see this, and the topic may be interesting and attract comments even years into the future!

[UWN]

And, GitHub does not show the closing date in discussions. Only in issues. But it alerts the notifications which is thus noise only.

[jjtolton]

One comment regarding the discussions themselves: Personally, I see no reason to close such discussion topics: People barely had a few days to even see this, and the topic may be interesting and attract comments even years into the future!

Ah ok! Well it's not a problem to reopen them, I just didn't want these to pile up and become a nuisance.

[triska]

I think closing makes sense if someone raises an issue and that issue is decisively addressed or solved. But for such open-ended discussions, why ever close them? The most recent discussions will automatically be shown first.