[gecode-users] Cumulatives for scheduling

[Guido Tack]

Hi,

I can't reproduce your problem on my machine.  Can you please have a look at the attached source code and check if it models the problem correctly.  If this does not give the expected answers, please let me know exactly which version of Gecode you're using, which operating system etc.

Cheers,
Guido



On 19/10/2012, at 8:41 AM, Baptiste Soyer <baptiste.soyer at opencubeproject.org> wrote:

> 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
> 
> 
> 
> 
> 
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20121022/eb963bf3/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cumul.cpp
Type: application/octet-stream
Size: 1270 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20121022/eb963bf3/attachment.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20121022/eb963bf3/attachment-0001.html>