need help on complex constraints

[Jean-Paul Berger]

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) :-
        steps(L), write('STEPS LOADED'), nl,
        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