Node:Cumulative Scheduling, Previous:N Queens, Up:Example Programs
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 ?