[rules-users] Continuous Planning values for task planning
Josef Bajada
josef.bajada at gmail.com
Mon Sep 10 22:02:56 EDT 2012
Hi Geoffrey,
I managed to implement the solution with the relative end Times. (I haven't
yet used the incremental score calculation because I haven't quite
understood how I implement it)
However I am facing one problem with our approach:
Lets say we have 3 tasks A, B, and C, each of duration 1 just for
simplicity, with these constraints:
a) B can only start between A.endTime + 10 and A.endTime + 100
b) C can only start between A.endTime + 50 and A.endTime + 100
c) C can only start between B.endTime + 10 and B.endTime + 20
With our approach of B.startTime = max(prev.endTime, A.endTime + 10) B
will always be scheduled to start at time 11 (and end at time 12) given the
hard constraints above.
On the other hand C cannot start before time 51, thus violating constaint
C.
The only solution to this would be to move B forward to start at time 30.
Is there any technique to detect these situations and make such adjustments?
thanks again,
Josef
On 20 August 2012 09:46, Geoffrey De Smet <ge0ffrey.spam at gmail.com> wrote:
> You 'll want incremental score calculation (with delta's) for your "end
> times".
>
> http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html_single/index.html#incrementalScoreCalculation
>
> So that naturally puts the calculation of those end times in the scoreDRL
> (or IncrementalJavaCalculator if you're not using drools).
> Whether or not that endTime should be a property on the model (at least
> the model that Planner works with), is an open design question.
> If it isn't, you can use insertLogicals in DRL, like I did in
> nurserostering to calculate the number of sequential weekends being worked
> etc.
> If it is a property on your model, either the DRL must first "correct it"
> (with higher salience rules for example),
> or custom moves must "correct it" as they are being done (which is very
> hard as it entails constraints functionality).
>
> As for the cloning: it's quite simple:
> Either the model's entity contains the endTime property, then clone it.
> If it doesn't, then there's nothing to clone.
> I don't see any problems related to the cloning.
>
> Op 18-08-12 01:53, Josef Bajada schreef:
>
> Hi Geoffrey,
>
> Following your advice and after gaining some more understanding of
> planner, I think approaching the problem as a chain of tasks one of the
> other makes sense. It would have some 'wait' time between tasks where the
> end time of the previous task is smaller than the minimum time the task has
> to wait after its dependency (which could be different from the previous
> task).
>
> I've noticed that in most examples (TSP and VRP), there is some
> separation between the model and the planning entity that is being moved
> around in the chain, which also makes sense. (For instance in TSP, Visit is
> the planning entity while City is the data entity). When the planning
> entity gets cloned, the data entity gets assigned to the clone.
>
> I am concerned however, that with my dependency between tasks and their
> end times (which are as such a property of the planning entity not the data
> entity) I won't be able to model them in this way. (For a task to know
> whether it has violated its hard constraint it needs to get access to the
> end time of its dependency, which is in the planning entity). My concern is
> that I might end up with a whole mess when it comes to the cloning of
> tasks. I am also concerned about the performance of computing the end time
> of each node recursively based on its previous task and dependent tasks.
>
> What is the best approach in this case?
>
> thanks,
>
> Josef
>
>
>
> On 25 July 2012 08:30, Geoffrey De Smet <ge0ffrey.spam at gmail.com> wrote:
>
>>
>> Op 24-07-12 23:14, Josef Bajada schreef:
>>
>> Hi Geoffrey,
>>
>> Thanks for your reply.
>>
>> > Does it make sense to wait longer than 7 mins after task A (presuming
>> no other task forces occupies the user at that time)?
>> > Put differently: Can we say that the starting time of B =
>> Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
>> > If we can say that, it's pointless to investigate the solutions where
>> task B starts 8 minutes after task A and the user doing no task that last
>> minute.
>>
>> Yes, the starting time of B = Math.max((endTime of task before B),
>> (endTime of task A + 7mins)) as long as it is smaller than (endTime of task
>> A + 8mins).
>> Yes, it is pointless to investigate the solutions where task B starts 8
>> minutes after task A and the user doing no task that last minute.
>> The 8 minute is just a constraint that the task in between tasks A and B
>> cannot take longer than 7:59s.
>>
>> I am thinking that maybe instead of using time itself as the planning
>> variable, we would use time just to determine the Hard and Soft scores.
>> So if Task B is scheduled after Task A + 8mins by the solver, then it
>> inflicts on the hard score. Similarly if Task B is scheduled before Task A
>> + 7 mins.
>> Does my reasoning make sense in any way?
>>
>> Yes, but personally, I 'd design it differently (although I have no proof
>> that my way would be better), like this:
>> "Task B is scheduled after Task A + 8mins by the solver" => make this a
>> hard constraint
>> "Task B is scheduled before Task A + 7 mins" => make this a build-in hard
>> constraint (= not a constraint in the scoreDRL or ScoreCalculator, but by
>> design, see manual).
>> Each Task is assigned to a previousTaskOrPerson (and this variable is
>> chained). It does not know it's startingTime directly.
>> The scoreDRL or ScoreCalculator calculates the startingTime of a Task
>> dynamically, by applying this logic:
>> starting time of B = Math.max((endTime of previousTaskOrPerson of B),
>> (endTime of task A + 7mins))
>> Note: "Chained=true" guarantees that there are no cycles of Tasks and
>> that no Tasks exists with a previousTaskOrPerson == null.
>> Note: "(endTime of task A + 7mins)" is not hard coded in the score
>> function: you won't find "7" or "A" in there.
>>
>>
>>
>> thanks,
>> Josef
>>
>>
>>
>> On 24 July 2012 20:46, Geoffrey De Smet <ge0ffrey.spam at gmail.com> wrote:
>>
>>>
>>> Op 23-07-12 16 <23-07-12%2016>:26, Josef Bajada schreef:
>>>
>>> Hi Geoffrey,
>>>
>>> Well I want to leave 'space' between tasks in the situations where
>>> there are hard constraints that require me to put this space.
>>>
>>> This makes the chaining technique harder to model, but I wouldn't write
>>> it off yet.
>>>
>>>
>>> As a simple example:
>>>
>>> Task A: Put pasta in boiling water (duration 40 seconds)
>>> Task B: Take pasta out of boiling water (duration 50 seconds, cannot
>>> start before 7 mins after Task A finishes, cannot start after 8 mins after
>>> Task A finishes)
>>>
>>> Does it make sense to wait longer than 7 mins after task A (presuming
>>> no other task forces occupies the user at that time)?
>>> Put differently: Can we say that the starting time of B =
>>> Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
>>> If we can say that, it's pointless to investigate the solutions where
>>> task B starts 8 minutes after task A and the user doing no task that last
>>> minute.
>>> If we can say that, then chaining can calculate the the starting time of
>>> a task on the fly differently.
>>>
>>> Task C: Chop vegetables (duration 2 minutes).
>>>
>>> This will evidently leave some gaps. The ideal result from the solver
>>> should be:
>>>
>>> Task A: at time 0 (ends at 40s)
>>> Task C: at time 41s (ends at 2:41)
>>> Task B: at time 7:40
>>>
>>> There is a gap between C and B which is OK.
>>>
>>> If another Task is added to the story:
>>> Task D: Prepare sauce (duration 7 minutes)
>>>
>>> I would want the following result:
>>>
>>> Task A: at time 0 (ends at 40s)
>>> Task D: at time 41s (ends 7:41s)
>>> Task B: at time 8:42s (ends 9:32s)
>>> Task C: at time 9:33s (ends 11:33s)
>>>
>>> Task C can actually take place before Task A too.
>>>
>>> I still need to read and understand the chaining functionality
>>> properly. Do you think it would allow me to achieve the above?
>>>
>>> I don't know.
>>> But using continuous variables in a search problem such as this that
>>> smells discrete with discrete constraints (A must start before B, ...),
>>> could blow up the search space unnecessarily.
>>>
>>> If you want to look into using continuous variables: the support for it
>>> is limited currently.
>>> you can reuse the Drools Planner metaheuristic algorithms (including
>>> termination, score, ...), but there's no decent generic move factory
>>> support for continuous variables yet.
>>> So you 'll have to write a custom MoveFactory that creates a limited
>>> subset of moves.
>>> Also, construction heuristics can't handle continuous variables yet, so
>>> you 'll have to write a custom SolutionIntializer.
>>> There are examples with a custom MoveFactory and a custom
>>> SolutionIntializer where you can copy paste from, but none with continuous
>>> variables at the moment.
>>>
>>> thanks,
>>>
>>> Josef
>>>
>>>
>>>
>>> On 22 July 2012 20:05, Geoffrey De Smet <ge0ffrey.spam at gmail.com> wrote:
>>>
>>>> Presuming that you don't want to leave space between tasks, you can
>>>> design your model differently by using the "chained" functionality:
>>>> it will be far more efficient and the planning variable won't be
>>>> continuous.
>>>>
>>>> Let's presume you're scheduling Tasks to Persons.
>>>>
>>>> @PlanningEntity
>>>> class Task implements TaskOrPerson {
>>>>
>>>> ...
>>>>
>>>> @PlanningVariable(chained = true)
>>>> @ValueRanges({
>>>> @ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
>>>> solutionProperty = "taskList"),
>>>> @ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
>>>> solutionProperty = "personList",
>>>> excludeUninitializedPlanningEntity = true)})
>>>> public TaskOrPerson getPreviousTaskOrPerson() {
>>>> return previousTaskOrPerson;
>>>> }
>>>>
>>>> public int getDuration() {
>>>> return duration;
>>>> }
>>>>
>>>> public int getStartingTime() {
>>>> int startingTime = 0;
>>>> TaskOrPerson taskOrPerson = getPreviousTaskOrPerson();
>>>> while (taskOrPerson instanceof Task) { // Every chain is
>>>> guarantee to end up with an anchor (= Person)
>>>> startingTime += ((Task) taskOrPerson).getDuration();
>>>> taskOrPerson = ((Task)
>>>> taskOrPerson).getPreviousTaskOrPerson()
>>>> }
>>>> return startingTime;
>>>> }
>>>>
>>>> }
>>>>
>>>> class Person implements TaskOrPerson {
>>>>
>>>> }
>>>>
>>>> For a good example, take a look at the VehicleRouting example.
>>>> For more info about chaining, in the manual see section 4.3.4.2.6.
>>>> Chained
>>>>
>>>> http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html_single/index.html
>>>>
>>>> Op 22-07-12 18 <22-07-12%2018>:00, Josef Bajada schreef:
>>>>
>>>> Hi,
>>>>
>>>> I am new to Drools and Drools Planner, so apologies if I am asking
>>>> anything obvious.
>>>>
>>>> My objective is to implement a simple (for now) planner which
>>>> schedules tasks according to 2 main criteria:
>>>> - Their duration (in seconds)
>>>> - Their dependencies on other tasks (e.g. Hard Constraint that Task B
>>>> has to start between 180 and 200 seconds after Task A finishes).
>>>>
>>>> Since there are gaps between dependent tasks as part of the hard
>>>> constraints other tasks can be fitted in between dependent tasks.
>>>> So the Solver needs to find the optimal start time for each task that
>>>> satisfies the hard constraints, and in the shortest total timeline possible
>>>> to complete all tasks (soft constraint).
>>>>
>>>> The main problem I am finding is that this start time, which is
>>>> essentially the planning variable is a continuous variable.
>>>> Chapter 4 of the Drools documentation mentions very briefly (Section
>>>> 4.3.4.1) that planning variables can be continuous, but there does not
>>>> seem to be any more details about how to achieve this.
>>>>
>>>> Even if the planning variable was discrete (say bins of 5 second
>>>> intervals), there is no upper bound as such.
>>>>
>>>> How is it best to handle such planning variables in Drools Planner?
>>>>
>>>> thanks,
>>>> josef
>>>>
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> rules-users mailing listrules-users at lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>>>>
>>>>
>>>> --
>>>> With kind regards,
>>>> Geoffrey De Smet
>>>>
>>>>
>>>> _______________________________________________
>>>> rules-users mailing list
>>>> rules-users at lists.jboss.org
>>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>>
>>>>
>>>
>>>
>>> _______________________________________________
>>> rules-users mailing listrules-users at lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>>>
>>>
>>> --
>>> With kind regards,
>>> Geoffrey De Smet
>>>
>>>
>>> _______________________________________________
>>> rules-users mailing list
>>> rules-users at lists.jboss.org
>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>
>>>
>>
>>
>> _______________________________________________
>> rules-users mailing listrules-users at lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>> --
>> With kind regards,
>> Geoffrey De Smet
>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users at lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>
>
> _______________________________________________
> rules-users mailing listrules-users at lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>
>
> --
> With kind regards,
> Geoffrey De Smet
>
>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20120911/c4ee961b/attachment-0001.html
More information about the rules-users
mailing list