Cumulative Scheduling

This example is a very small scheduling problem. We consider seven tasks where each task has a fixed duration and a fixed amount of used resource:

     TASK    DURATION        RESOURCE
     ====    ========        ========
     t1            16               2
     t2             6               9
     t3            13               3
     t4             7               7
     t5             5              10
     t6            18               1
     t7             4              11
     

The goal is to find a schedule that minimizes the completion time for the schedule while not exceeding the capacity 13 of the resource. The resource constraint is succinctly captured by a cumulative/4 constraint. Branch-and-bound search is used to find the minimal completion time.

This example was adapted from [Beldiceanu & Contejean 94].

     :- use_module(library(clpfd)).
     :- use_module(library(lists), [append/3]).
     
     schedule(Ss, End) :-
             length(Ss, 7),
             Ds = [16, 6,13, 7, 5,18, 4],
             Rs = [ 2, 9, 3, 7,10, 1,11],
             domain(Ss, 1, 30),
             domain([End], 1, 50),
             after(Ss, Ds, End),
             cumulative(Ss, Ds, Rs, 13),
             append(Ss, [End], Vars),
             labeling([minimize(End)], Vars). % label End last
     
     after([], [], _).
     after([S|Ss], [D|Ds], E) :- E #>= S+D, after(Ss, Ds, E).
     
     %% End of file
     
     | ?- schedule(Ss, End).
     Ss = [1,17,10,10,5,5,1],
     End = 23 ?