[rules-users] Continuous Planning values for task planning
Josef Bajada
josef.bajada at gmail.com
Tue Jul 24 17:14:17 EDT 2012
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?
thanks,
Josef
On 24 July 2012 20:46, Geoffrey De Smet <ge0ffrey.spam at gmail.com> wrote:
>
> Op 23-07-12 16: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: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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20120724/1b4de2ab/attachment-0001.html
More information about the rules-users
mailing list