[rules-users] Continuous Planning values for task planning
Geoffrey De Smet
ge0ffrey.spam at gmail.com
Tue Jul 24 14:46:36 EDT 2012
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
> <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
> 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/20120724/4360e7b1/attachment-0001.html
More information about the rules-users
mailing list