Previous: N Queens, Up: CLPFD Example Programs [Contents][Index]
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)). schedule(Ss, End) :- Ss = [S1,S2,S3,S4,S5,S6,S7], Es = [E1,E2,E3,E4,E5,E6,E7], Tasks = [task(S1,16,E1, 2,0), task(S2, 6,E2, 9,0), task(S3,13,E3, 3,0), task(S4, 7,E4, 7,0), task(S5, 5,E5,10,0), task(S6,18,E6, 1,0), task(S7, 4,E7,11,0)], domain(Ss, 1, 30), domain(Es, 1, 50), domain([End], 1, 50), maximum(End, Es), cumulative(Tasks, [limit(13)]), append(Ss, [End], Vars), labeling([minimize(End)], Vars). % label End last %% End of file | ?- schedule(Ss, End). Ss = [1,17,10,10,5,5,1], End = 23