[rules-users] Continuous Planning values for task planning
Geoffrey De Smet
ge0ffrey.spam at gmail.com
Wed Jul 25 02:30:48 EDT 2012
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
> <mailto:ge0ffrey.spam at gmail.com>> wrote:
>
>
> Op 23-07-12 16 <tel: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
>> <mailto: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 <tel: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 list
>>> rules-users at lists.jboss.org <mailto:rules-users at lists.jboss.org>
>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>> --
>> With kind regards,
>> Geoffrey De Smet
>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users at lists.jboss.org <mailto:rules-users at lists.jboss.org>
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users at lists.jboss.org <mailto:rules-users at lists.jboss.org>
>> https://lists.jboss.org/mailman/listinfo/rules-users
>
> --
> With kind regards,
> Geoffrey De Smet
>
>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org <mailto:rules-users at lists.jboss.org>
> https://lists.jboss.org/mailman/listinfo/rules-users
>
>
>
>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20120725/9c248b5f/attachment-0001.html
More information about the rules-users
mailing list