Re: [eclipse-clp-users] Very simple scheduling problem

From: Thorsten Winterer <thorsten_winterer_at_web.de>
Date: Fri, 25 May 2012 10:03:54 +0200
Hi Lorenzo,

the problem with your code is that findall/3 generates copies of the 
domain variables. So you are constraining these copies instead of the 
original variables.

For example:

test(X,Y) :-
     X #:: 0..1,
     Y #:: 0..1,
     findall(Z, member(Z, [X,Y]), L),
     L = [A,B],
     A #> B,
     writeln(L).

gives this:

?- test(X, Y).
[1, 0]
X = X{[0, 1]}
Y = Y{[0, 1]}
Yes (0.00s cpu)


As you can see, A and B (the copies generated by findall/3) have been 
constrained (and instantiated), whereas X and Y (the original variables) 
have been left unconstrained.

You would need to update your program to avoid using the findall/3 call 
to determine the OtherDomains list for each domain variable.

However, the best would be to use the cumulative/4 scheduling constraint 
provided by ECLiPSe's edgefinder library:

:- lib(ic).
:- lib(ic_edge_finder).

schedule(Domains):-
         getTasks(Tasks),
         (
             foreach(task(_,Dur), Tasks),
             foreach(Dur, Durations),
             foreach(1, Resources),
             foreach(Dom, Domains)
         do
             Dom #:: 0..59
         ),
         cumulative(Domains, Durations, Resources, 1),
         labeling(Domains).

% the rest of the program stays unchanged


Cheers,
Thorsten



Am 23.05.2012 18:03, schrieb Lorenzo Stoakes:
> Hi all,
>
> I am trying to leverage CLP in order to solve a rather simple 
> scheduling problem. the problem consists of a series of tasks, each of 
> which with a specified length.
>
> I want to determine all the permutations of start times, with the 
> constraint that they cannot run at the same time.
>
> I define these tasks as facts in the knowledge base, e.g.:-
>
> task(a, 3),
> task(b, 2).
>
> So far, I have been resorting to writing very imperative code littered 
> with for's and foreach's to constrain things. I write code to use 
> findall/3 to obtain all N tasks, then I generate N domain variables, 
> setting them to 0..59 (minutes in one hour). I then use (perhaps 
> rather unwisely), remove/3 to get each element in the list along with 
> every other element, to which I apply the constraint Domain #\= 
> OtherDomain + I for I = 0 to Length-1.
>
> I have two problems here. 1, this code is rather awful and really, a 
> twisty turny version of imperative code bending over backwards to try 
> to work in prolog, and 2 - it doesn't work. I am getting the following 
> response:-
>
> [eclipse 41]: top.
> [0, 0]
>
> Delayed goals:
> -(_285{0 .. 59}) + _267{0 .. 59} #\= 0
> -(_285{0 .. 59}) + _267{0 .. 59} #\= 1
> -(_285{0 .. 59}) + _267{0 .. 59} #\= 2
> -(_321{0 .. 59}) + _303{0 .. 59} #\= 0
> -(_321{0 .. 59}) + _303{0 .. 59} #\= 1
> Yes (0.00s cpu, solution 1, maybe more) ?
>
> Which means that variables are somehow getting reassigned, which 
> rather confuses me.
>
> I know this might be a rather 'send me the codez' sort of question, 
> but I am rather stuck and I am sure one of you CLP experts must be 
> able to come up with a simpler, more declarative and all-round more 
> CLP-y way of doing things, and also perhaps something that works :)
>
> I would appreciate any help anybody could give, massively.
>
> Cheers,
> Lorenzo
>
> Exhibit A, The Code:-
>
> The code:-
>
> :- lib(ic).
>
> task(a, 3).
> task(b, 2).
>
> % We want to schedule these tasks to take up 60 minutes. So 
> essentially permutations.
>
> remove(X, [X|Rest], Rest).
> remove(X, [Y|Rest], [Y|RestAnswer]):-
>         remove(X, Rest, RestAnswer).
>
> getTasks(Tasks):-
>         findall(task(Name, Length), task(Name, Length), Tasks).
>
> schedule(Domains):-
>         getTasks(Tasks),
>         length(Tasks, N),
>         length(Domains, N),
>         Domains :: 0..59,
>         findall([Domain,OtherDomains], remove(Domain, Domains, 
> OtherDomains), SplitDomains),
>         (foreach(task(_, Length), Tasks), foreach([Domain, 
> OtherDomains], SplitDomains) do
>             (foreach(OtherDomain, OtherDomains), param(Domain, Length) do
>                 (for(I,0,Length-1), param(Domain, OtherDomain) do
>                     (
>                         Domain #\= OtherDomain+I
>                     )
>                 )
>             )
>         ),
>         labeling(Domains).
>
> top:-
>         schedule(Domains),
>         writeln(Domains).
>
>
> ------------------------------------------------------------------------------
> Live Security Virtual Conference
> Exclusive live event will cover all the ways today's security and
> threat landscape has changed and how IT managers can respond. Discussions
> will include endpoint security, mobile security and the latest in malware
> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
>
>
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
Received on Fri May 25 2012 - 08:04:06 CEST

This archive was generated by hypermail 2.2.0 : Sat Jun 02 2012 - 06:14:11 CEST