Home > Archive > Prolog > January 2006 > Simple resource allocation problem
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Simple resource allocation problem
|
|
|
| Greetings,
I am looking at a resource allocation problem that can be simplified as
follows:
two resources X and Y
X :: 1..5
Y :: 1..5
I want to allocate resources to 5 tasks each using one of each
resource. No doubleup. i.e you can only use the pair X1,Y1 once
Ususally you would use an alldifferent, but how to use this if multiple
resources are involved?
I am currently looking at writing with Eclipse.
Thanks in advance.
Pat
| |
| Bart Demoen 2006-01-10, 4:10 am |
| Pat wrote:
> Greetings,
>
> I am looking at a resource allocation problem that can be simplified as
> follows:
>
> two resources X and Y
>
> X :: 1..5
> Y :: 1..5
>
> I want to allocate resources to 5 tasks each using one of each
> resource. No doubleup. i.e you can only use the pair X1,Y1 once
>
> Ususally you would use an alldifferent, but how to use this if multiple
> resources are involved?
Many possibilitie - here are two:
(X1,Y1) \== (X2,Y2) iff (X1 \== X2) or (Y1 \== Y2)
another one
for the range described:
(X1,Y1) \== (X2,Y2) iff 7*X1+Y1 \== 7*X2+Y2
Cheers
Bart Demoen
| |
| Markus Triska 2006-01-10, 7:57 am |
| Hi!
Pat wrote:
>
> Ususally you would use an alldifferent, but how to use this if multiple
> resources are involved?
You create a relation that contains all pairs of resources, augmented
with a unique ID per pairing, constrain the variables (extended with an
initially free variable to hold the ID) to belong to that relation
(fd_relation/2 in GNU Prolog, tuples_in/2 in SWI-Prolog) and constrain
the variables that correspond to IDs to be all distinct. In SWI Prolog:
:- use_module(library(bounds)).
make_table(Ts) :-
findall([X,Y], (between(1,5,X),between(1,5,Y)), Pairs0),
maplist(pair_with_id, Pairs0, Ts).
pair_with_id([X,Y], [X,Y,ID]) :-
ID is (X-1)*5 + Y - 1.
tuples_res1s_res2s_ids([], [], [], []).
tuples_res1s_res2s_ids([[R1,R2,ID]|Ts], [R1|R1s], [R2|R2s], [ID|IDs]) :-
tuples_res1s_res2s_ids(Ts, R1s, R2s, IDs).
extend([A,B], [A,B,_]).
res(XYs0, R1s, R2s) :-
maplist(extend, XYs0, XYs1),
make_table(Table),
tuples_in(XYs1, Table),
tuples_res1s_res2s_ids(XYs1, R1s, R2s, IDs),
all_different(R1s),
all_different(R2s),
all_different(IDs).
Now you can query:
?- Tasks = [[_,_],[_,_],[_,_],[_,_],[_,_]], res(Tasks, R1s, R2s),
label(R1s), label(R2s).
Tasks = [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]] ;
Tasks = [[1, 1], [2, 2], [3, 3], [4, 5], [5, 4]] ;
Tasks = [[1, 1], [2, 2], [3, 4], [4, 3], [5, 5]] ;
Tasks = [[1, 1], [2, 2], [3, 4], [4, 5], [5, 3]] ;
.... etc.
All the best,
Markus.
| |
|
|
|
| On 10 Jan 2006 08:31:43 -0800, "arv832" <andrew.verden@ifcomputer.de>
wrote:
>
>Pat schrieb:
>
>
>Why dont you also take a look at IF/Prolog:
>
>http://www.ifcomputer.de/Products/Prolog/home_en.html
>
"Take a look" or "take a try"?.. Are the licensing terms for IF/Prolog
the same as for Eclipse?... Eclipse id free for academic applications.
A.L.
| |
| Joachim Schimpf 2006-01-10, 9:58 pm |
| Pat wrote:
> Greetings,
>
> I am looking at a resource allocation problem that can be simplified as
> follows:
>
> two resources X and Y
>
> X :: 1..5
> Y :: 1..5
>
> I want to allocate resources to 5 tasks each using one of each
> resource. No doubleup. i.e you can only use the pair X1,Y1 once
>
> Ususally you would use an alldifferent, but how to use this if multiple
> resources are involved?
>
> I am currently looking at writing with Eclipse.
I may be overlooking something in your problem description,
but why not simply have an alldifferent per resource?
:- lib(ic).
solve(NTasks, MaxRes, Tasks) :-
(
for(_,1,NTasks),
foreach(t(X,Y), Tasks),
foreach(X, Xs),
foreach(Y, Ys)
do
true
),
Xs :: 1..MaxRes,
Ys :: 1..MaxRes,
alldifferent(Xs),
alldifferent(Ys),
labeling(Xs),
labeling(Ys).
?- solve(5, 5, T).
T = [t(1, 1), t(2, 2), t(3, 3), t(4, 4), t(5, 5)]
Yes (0.00s cpu, solution 1, maybe more)
T = [t(1, 1), t(2, 2), t(3, 3), t(4, 5), t(5, 4)]
Yes (0.00s cpu, solution 2, maybe more)
T = [t(1, 1), t(2, 2), t(3, 4), t(4, 3), t(5, 5)]
Yes (0.00s cpu, solution 3, maybe more)
....
-- Joachim
| |
|
|
Thanks all for your help.
The complicating factor here was that we did not want a doubleup of the
*combination* of resources. Implementing an alldifferent on each
resource restricts valid combinations. An example, (X,Y) =
[(1,1),(1,2),(1,3),(1,4),(1,5)] is acceptable but (X,Y) =
[(1,1),(1,2),(1,3),(1,4),(1,1)] is not as there is a repeated (1,1).
Barts suggestion is a private email was to build a combination list and
alldiff that. To keem them integers, the list would be filled with
100*X+Y.
Will post code shortly
| |
| Markus Triska 2006-01-10, 9:58 pm |
| Pat wrote:
> The complicating factor here was that we did not want a doubleup of the
> *combination* of resources. Implementing an alldifferent on each
> resource restricts valid combinations.
Just remove the other two all_different constraints and leave only the
one on the IDs intact for that. You then obtain:
?- length(Tasks, 5), res(Tasks, R1s, R2s), label(R1s), label(R2s).
Tasks = [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5]]
R1s = [1, 1, 1, 1, 1]
R2s = [1, 2, 3, 4, 5] ;
Tasks = [[1, 1], [1, 2], [1, 3], [1, 5], [1, 4]]
R1s = [1, 1, 1, 1, 1]
R2s = [1, 2, 3, 5, 4] ;
Tasks = [[1, 1], [1, 2], [1, 4], [1, 3], [1, 5]]
R1s = [1, 1, 1, 1, 1]
R2s = [1, 2, 4, 3, 5] ;
Tasks = [[1, 1], [1, 2], [1, 4], [1, 5], [1, 3]]
R1s = [1, 1, 1, 1, 1]
R2s = [1, 2, 4, 5, 3] ;
Tasks = [[1, 1], [1, 2], [1, 5], [1, 3], [1, 4]]
R1s = [1, 1, 1, 1, 1]
R2s = [1, 2, 5, 3, 4] ;
Tasks = [[1, 1], [1, 2], [1, 5], [1, 4], [1, 3]]
R1s = [1, 1, 1, 1, 1]
R2s = [1, 2, 5, 4, 3]
.... etc.
All the best,
Markus.
| |
| arv832 2006-01-11, 7:01 pm |
| We try to keep our licensing fairly priced for both academics and
industrial users.
In general, academic licences are not free, but I think you will find
that our prices reflect our serious committment to our customers and
the continued support of a quality product.
A "free for academic applications" licence usually implies you are
"free from all support"!
If you would like to develop and support software at such a risk then
that is your
choice, but it would not be mine.
Andrew Verden
|
|
|
|
|