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
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
cumul.cpp