[eclipse-clp-users] Very simple scheduling problem

From: Lorenzo Stoakes <lorenzo_at_rulemotion.com>
Date: Wed, 23 May 2012 17:03:57 +0100
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).
Received on Wed May 23 2012 - 16:30:19 CEST

This archive was generated by hypermail 2.2.0 : Sat May 26 2012 - 06:13:56 CEST