[gecode-users] Cumulatives for scheduling

[Baptiste Soyer]

Hi,

I've run into some issue while trying to implement a scheduler using
gecode. I hope someone can help me...
My goal is to make a schedule of different tasks with the following
requirements :

   - Some task consumes resources. They are defined by :
      - The type of resources that it consumes
      - The amount consumed
      - The duration of the task
      - The earliest and latest start time (earliest start time + time out
      time)  allowed
   - Some task can produce resources. They are defined by :
   - The type of resources that it produces
      - The amount produced
      - The start time (no timeout, the start time is a fixed value) and
      duration of the production

My end goal is to have the possible start time for producer, so that the
amount of resource is always greater or equal to 0.

>From all the above, I thought that the cumulatives constraint implemented
in gecode would be suitable (use of machines for different type of
resources, positive or negative usage for production and consumption,...).

So what I'm doing is defining 2 variables array representing the start time
and end time of each task, and then constraining the start time to be
between the earliest start time and latest start time (same value for
producers). The end time is constraint for fixed duration tasks. And
finally I'm posting the cumulatives constraint.

The gecode code looks something like that :

for(unsigned int i = 0;i<n;i++)
    {
        Booking booking = Bookings[i];//Get the current booking

        //Set Duration, Capacity and Machine arguments
        Duration[i] = booking.getDuration();
        Capacity[i] = booking.getCapacity();
        Machine[i]  = ResourceList[i];

        //Constraint the domain of the StartValue
        StartTime[i] =
IntVar(*this,booking.earliestStart(),booking.latestStart());

        //Constraint to a fixed duration activity
        rel(*this,EndTime[i] == StartTime[i] + Duration[i]);

}

// Constrain the problem with a cumulative scheduling constraint

cumulatives(*this,Machine,StartTime,Duration,EndTime,Capacity,Zero,false);

// Choose the branching mechanism
    branch(*this, EndTime, INT_VAR_MAX_MAX, INT_VAL_MAX);
    branch(*this, StartTime, INT_VAR_MIN_MIN, INT_VAL_MIN);

So my problem (after this long introduction...). I'm checking that gecode
gives me the expected schedule for simple problem. I have 2 consumers and 1
producer which have the following value.

consumer 1(Power:2)
Start Time :0
Duration   :5
TimeOut    :4

consumer 2(Power:9)
Start Time :0
Duration   :5
TimeOut    :5

producer 1(Power:10)
Start Time :0
Duration   :10
TimeOut    :0

Which gives me the following value for the cumulative constraint on :
    Machine :{0, 0, 0}
    StartTime :{[0..4], [0..5], 0}
    Duration :{5, 5, 10}
    EndTime :{[0..10], [0..10], 10}
    Capacity :{-2, -9, 10}

So I'm expecting to have 1 solution :consumer 1 starting at 0 and consumer
2 starting at 5. But my code finds no solutions.

If I'm putting the time out for the first producer at 5 I find 1 solutions
where I should find 2 (both producer are interchangeable). The solution
found depends on the branching selected (which I understand in a way, but
it should still find me both solutions).

So I'm sure I'm doing something wrong, but I can't find out what.

I hope I made myself clear.

Cheers,

Baptiste
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20121018/36d2e08e/attachment.html>