Re: cumulative predicate

From: Joachim Schimpf <j.schimpf_at_icparc.ic.ac.uk>
Date: Fri 07 Oct 2005 02:21:42 PM GMT
Message-ID: <43468476.1080608@icparc.ic.ac.uk>
Krzychu ƚwidziƄski wrote:
> ...
 > My not-working code in ECLiPSe looks like this:
> 
> :- lib(fd).
> :- lib(ic_edge_finder).
> ...


This is the first problem: you mix the fd library with a library from
the ic group (Eclipse gives you a warning about this). You have to
decide wheter to use the (older) fd group or the (newer) ic group of
libraries. Let's assume in the following that we want to use ic.

The second problem is with the schedule's end time (Koniec/End).
In CHIP you wrote

 > cumulative(LS, LD, LR, LK, unused, Limit, Koniec, unused),

Unlike CHIP's cumulative, Eclipse's cumulative does not have arguments
for the end times of the tasks (LK) or the total end time (Koniec/End).
You have to express them with additional constraints.
The resulting code then looks like:


:- lib(ic).
:- lib(ic_edge_finder).		% for cumulative/4
:- lib(branch_and_bound).	% for minimize/2

top(LS, LK, Limit, End) :-
	LS = [S1,S2,S3,S4,S5,S6,S7],	% start times
	LD = [16, 6,13, 7, 5,18, 4],	% duration times
	LR = [2,9,3,7,10,1,11],		% resurce used by tasks

	LS :: 1..100,
	Limit :: 1..13,	%we can't use more than 13 resources at the same time

	% setup a list of end times LK
	( foreach(S,LS),foreach(D,LD),foreach(K,LK) do
		K #= S+D
	),
	End #= max(LK),			% latest end time of all tasks
	cumulative(LS, LD, LR, Limit),

	minimize(labeling(LS), End).


This gives the expected solution:

?- top(LS, LK, Limit, End).
LS = [1, 17, 10, 10, 5, 5, 1]
LK = [17, 23, 23, 17, 10, 23, 5]
Limit = 13
End = 23
Yes (0.14s cpu)


Warning: the simple search procedure used here (labeling the start
times in input order) will not scale up to much larger problems.
Alternatives you can try here:

1. replace labeling/1 by search/6 and experiment with different
    variable/value selection and search strategies.
2. replace minimize/2 with bb_min/3 and experiment with different
    strategies.
3. Look at http://www.icparc.ic.ac.uk/eclipse/examples/jobshop.html
    for how to search by labeling task orders before labeling start
    times. The Eclipse tutorial also has some material about dealing
    with this kind of disjunctive constraint.


All the best,
-- 
  Joachim Schimpf              /             phone: +44 20 7594 8187
  IC-Parc                     /      mailto:J.Schimpf@imperial.ac.uk
  Imperial College London    /    http://www.icparc.ic.ac.uk/eclipse
Received on Fri Oct 07 15:25:48 2005

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:39 PM GMT GMT