users-prolog
[Top][All Lists]

need help on complex constraints

 From: Jean-Paul Berger Subject: need help on complex constraints Date: Tue, 08 Jan 2002 12:15:17 +0000

```hi,

```
i am trying to implement a scheduling algorithm in gprolog using finite domains. but when i try to constrain the used ressources (steps/jobs may not overlap) it takes far too much time for prolog to calculate this (10min for 20 steps and 4 ressources!)
```
```
now, i am quite new to CLP, so there may be many mistakes within my code. does anyone know a site, where an explanation about FD can be found (exspecially about gprolog). or is there any open-source scheduling-algorithm using FDs?
```

cu,
jean

```
PS: here is the code i used. maybe someone can tell me about my mistake...? (the problem seems to be in constrain_ressources/2)
```

:- op(255, xfx, in).
in(A,B) :- member(A,B).

% not used
ressource(1,1,'class1','res1').
ressource(2,1,'class1','res2').
ressource(3,1,'class1','res3').
ressource(4,1,'class1','res42').

% step(ID, Start, End, Duration, Used_Ressources, Depencies, Name)
step(1,_,_,30,[(1,1)],[],'step1').
step(2,_,_,45,[(2,1)],[1],'step2').
step(3,_,_,21,[(3,1)],[1],'step3').
step(4,_,_,31,[(4,1)],[2,3],'step4').
step(5,_,_,25,[(1,1),(2,1)],[15],'step5').
step(6,_,_,9,[(1,1),(2,1)],[13],'step6').
step(7,_,_,57,[(2,1)],[12,13],'step7').
step(8,_,_,100,[(1,1)],[2,5],'step8').
step(9,_,_,63,[(1,1)],[12],'step9').
step(10,_,_,15,[(4,1)],[12],'step10').
step(11,_,_,27,[(4,1)],[13],'step11').
step(12,_,_,1023,[(1,1),(2,1),(3,1),(4,1)],[1,13],'step12').
step(13,_,_,547,[(1,1),(4,2)],[4],'step13').
step(14,_,_,3,[(2,1)],[7],'step14').
step(15,_,_,99,[(2,1)],[13],'step15').
step(16,_,_,4,[(1,1),(4,1)],[14,15],'step16').
step(17,_,_,12,[(3,1),(2,1)],[5,7],'step17').
step(18,_,_,78,[(4,1),(3,1)],[7,8,9],'step18').
step(19,_,_,77,[(3,1)],[11],'step19').
step(20,_,_,27,[(3,1)],[],'step20').

% In a list of steps, set the domain of Start and End for each step,
% End = Start + Duration
get_fd_domain([step(_,A,B,D,_,_,_)|C],S,E) :-
fd_domain([A,B],S,E),
B #=# A+D,
get_fd_domain(C,S,E).
get_fd_domain([], _, _).

% In a list of steps, when there is a step with a non-empty list of
% depencies let its Start be greater then the steps it depends on End
constrain_depencies([step(_,A,_,_,_,[N|M],_)|C],S) :-
step(N,_,E,_,_,_,_) in S,
A #># E,
constrain_depencies([step(_,A,_,_,_,M,_)|C],S).
constrain_depencies([step(_,_,_,_,_,[],_)|C],S) :-
constrain_depencies(C,S).
constrain_depencies([],_).

% In a list of steps, when there is a step with a non-empty list of
% required ressources its Start and End may not overlap with
% the Start and End of other steps using the same ressource
constrain_ressources([step(V,A,B,_,[(N,_)|M],_,_)|C],S) :-
findall([X,Y], (step(W,X,Y,_,D,_,_) in S, (N,_) in D, V\=W), [I|L]),!,
findall([X,Y], ([X,Y] in [I|L],
no_intervall_intersection([A,B],[X,Y])),_),
write(V), write([I|L]), nl,
constrain_ressources([step(V,A,B,_,M,_,_)|C],S).
constrain_ressources([step(V,_,_,_,[_|M],_,_)|C],S) :-
write(V), write('No Conflict'), nl,
constrain_ressources([step(_,_,_,_,M,_,_)|C],S).
constrain_ressources([step(V,_,_,_,[],_,_)|C],S) :-
write(V), write('None'), nl,
constrain_ressources(C,S).
constrain_ressources([],_).

% Just label all Start and End in a list of steps
label_them([step(_,A,B,_,_,_,_)|C]) :-
fd_minimize(fd_labelingff([A,B]), A),
label_them(C).
label_them([]).

% Two intervalls don't overlap, if the distance of the two centers
% is greater than the sum of the radiusses.
% (Be sure that A =< B and X =< Y)
no_intervall_intersection([A,B],[X,Y]) :-
C_AB   #=#     (A + B) // 2,  % center
C_XY   #=#     (X + Y) // 2,
R_AB   #=#     (B - A) // 2,  % radius
R_XY   #=#     (Y - X) // 2,
D_ABXY #=# dist(C_AB,C_XY),   % distance
D_ABXY #># R_AB + R_XY + 1.

% Saves writing ;)
steps(L) :- findall(step(A,B,C,D,E,F,G), step(A,B,C,D,E,F,G), L).

% A principal test for no_intervall_intersection/2
test_intervalls([A,B],[C,D]) :-
fd_domain([A,B,C,D],1,20),
B #=# A+5, D #=# C+12,
no_intervall_intersection([A,B],[C,D]),
fd_labeling([A,B]), fd_labeling([C,D]).

% A test for the whole planing procedure
test_plan(L) :-
fd_set_vector_max(3000),
get_fd_domain(L,1,2500), write('DOMAIN GOT'), nl,
constrain_depencies(L,L), write('DEPENCIES CONSTRAINED'), nl,
constrain_ressources(L,L), write('RESSOURCES CONSTRAINED'), nl,
label_them(L), write('LABELING'), nl.

_________________________________________________________________
```
MSN Photos is the easiest way to share and print your photos: http://photos.msn.com/support/worldwide.aspx
```

```