Prolog's CLP over Finite Domains library performance

Question

I'm programming a task scheduler/planner in Prolog and for that I'm planning to use the CLPFD library (on SWIPL). I was wondering how powerful it is to use finite domains to solve scheduling problems and what the impact would be in CPU load if I do use it.

The scheduling problem would be based on the assertions stated in page 10 of this paper: "Constraint-Based Scheduling". In fact my tasks/activities will be very heterogeneous (some will be preemptable while others won't) and the activity resources will have different capacities. Right now, I'm just working on a simple case (non-preemptible, disjunctive scheduling) and I've come to something like this:

/* Non-preemptive, disjunctive scheduling. *******************************/
planner :- 
    /* 'S' stands for start point. 
       'E' stands for end point. */
    set(a1,S1,E1),
    set(a2,S2,E2),
    set(a3,S3,E3),
    interval(intersection,[S1,E1],[S2,E2],[]), % Tests whether activities 
    interval(intersection,[S2,E2],[S3,E3],[]), % intersect. If they do,  
    interval(intersection,[S3,E3],[S1,E1],[]), % backtracking occurs and 
    (...).                                     % an alternative solution
                                               % will be looked for.

/* A set of times in which activity A executes (non-preemptive) */
set(A,[S],[E]) :-
    /* 'A' is the activity.
       'R' is release point and 'D' deadline point. 
       'Lst' stands for Latest Start Point.
       'Eet' stands for Earliest End Point. */
    preemptable(A,no),
    rd(A,R,D),
    p(A,P),
    Lst is D-P,
    Eet is R+P,

    S in R..D,
    E in R..D,

    S #=< Lst,
    E #>= Eet,
    S #< E,
    P #= E-S,
    indomain(S),
    indomain(E).
set(A,[],[]). /* When the activity can't be scheduled. */

It does work, and it's really fast (intstantaneous in fact). But this is just a simple case with three activities, when in my final program I'll have hundreds of them, and the scheduling problem will be much more complex than this.

Thanks for your advice!

Answer 1

In general, CLP(FD) is a suitable and well-established way to solve such kinds of problems. Note however that there are many different ways to model your problem even within library(clpfd): You can for example use the global constraints serialized/2 or cumulative/1 to express it. Other Prolog systems will often give you much better performance than SWI-Prolog, but the way you model your problem and search for solutions typically affects performance much more than the optimizations of any specific implementation.