[gecode-users] Understanding cumulatives constraint

[Mikael Zayenz Lagerkvist]

On 7/3/06, Roberto Pinto <librarama at gmail.com> wrote:
> I'm trying to compile a really basic example using the cumulatives
> constraint, but I'm finding some problems that I hope you could help
> me to solve.

The problem with your example is very simple to solve, machines are
indexed starting from 0 and not from 1. I've added some comments on
some parts of your code below.


> /// START CODE---------------------------------------------------------------------
>       for (int i = 0; i < 4; i++)
>             {
>             height[i] = 1;    ///each task requires 1 unit of resource
> per period
>             duration[i] = 4;  /// each task lasts 4 periods
>                                    ///that is, each task requires 4
> resource units over 4 periods
>             machine[i] = 1;  ///all tasks are worked on machine 1

should be: machine[i] = 0;


>             }
>
>             limit = 1;            ///the machine has only one resource
> unit per period

should be: limit[0] = 1;


>       for(int i = 0; i<4; i++)
>             post(this, e[i] - duration[i] = q[i] );
> ///the ending date depends on the starting date and the duration

The above loop is not needed - making sure that start+duration=end is
handled by the cumulatives interface.


> ///Indeed, I did not understand its purpose
>   BasicScheduling(bool share, BasicScheduling& s) : Example(share,s) {
>     q.update(this, share, s.q);
>     e.update(this, share, s.e);
>   }
>
>   /// Perform copying during cloning
> /// same comment as above, I just cut&paste from queens.cc
>   virtual Space*
>   copy(bool share) {
>     return new BasicScheduling(share,*this);
>   }

These two functions are needed for keeping the q and e arrays
consistent in all new copies of the Space and for enabling copying of
the Space.


> ///END CODE--------------------------------------------------------
>
> I was expecting a solution like:
> 0:4, 5:9, 10:14, 15:19
>
> instead I obtained:
> 0:4, 0:4, 0:4, 0:4

Well, the actual solution one gets is
    0:4, 4:8, 8:12, 12:16,
This shows that a task may start and another task may begin at the same time.


Cheers,
Mikael

-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/