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/2
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