Hi Geoffrey,<div><br></div><div>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).</div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>What is the best approach in this case?</div><div><br></div><div>thanks,</div><div><br>Josef</div><div><br></div><div><br><br><div class="gmail_quote">On 25 July 2012 08:30, Geoffrey De Smet <span dir="ltr"><<a href="mailto:ge0ffrey.spam@gmail.com" target="_blank">ge0ffrey.spam@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<br>
<div>Op 24-07-12 23:14, Josef Bajada
schreef:<br>
</div>
<blockquote type="cite">Hi Geoffrey,
<div><br>
</div><div class="im">
<div>Thanks for your reply.</div>
<div><br>
</div>
<div>> Does it make sense to wait longer than 7 mins after task
A (presuming no other task forces occupies the user at that
time)?<br>
> Put differently: Can we say that the starting time of B =
Math.max((endTime of task before B), (endTime of task A + 7
minutes))?<br>
> 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.<br>
</div>
<div><br>
</div>
<div>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).</div>
<div>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. </div>
<div>The 8 minute is just a constraint that the task in between
tasks A and B cannot take longer than 7:59s.</div>
<div><br>
</div>
<div>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. </div>
<div>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. </div>
<div>Does my reasoning make sense in any way?</div>
</div></blockquote>
Yes, but personally, I 'd design it differently (although I have no
proof that my way would be better), like this:<br>
"Task B is scheduled after Task A + 8mins by the solver" => make
this a hard constraint<br>
"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).<br>
Each Task is assigned to a previousTaskOrPerson (and this variable
is chained). It does not know it's startingTime directly.<br>
The scoreDRL or ScoreCalculator calculates the startingTime of a
Task dynamically, by applying this logic:<br>
starting time of B = Math.max((endTime of previousTaskOrPerson of
B), (endTime of task A + 7mins))<br>
Note: "Chained=true" guarantees that there are no cycles of Tasks
and that no Tasks exists with a previousTaskOrPerson == null.<br>
Note: "(endTime of task A + 7mins)" is not hard coded in the score
function: you won't find "7" or "A" in there.<div><div class="h5"><br>
<br>
<blockquote type="cite">
<div><br>
</div>
<div>thanks,</div>
<div>Josef</div>
<div><br>
</div>
<div><br>
<br>
<div class="gmail_quote">On 24 July 2012 20:46, Geoffrey De Smet
<span dir="ltr"><<a href="mailto:ge0ffrey.spam@gmail.com" target="_blank">ge0ffrey.spam@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"> <br>
<div>Op <a href="tel:23-07-12%2016" value="+35623071216" target="_blank">23-07-12 16</a>:26, Josef Bajada
schreef:<br>
</div>
<div>
<blockquote type="cite">Hi Geoffrey,
<div><br>
</div>
<div>Well I want to leave 'space' between tasks in the
situations where there are hard constraints that
require me to put this space.<br>
</div>
</blockquote>
</div>
This makes the chaining technique harder to model, but I
wouldn't write it off yet.
<div><br>
<blockquote type="cite">
<div><br>
</div>
<div>As a simple example:</div>
<div> <br>
</div>
<div>Task A: Put pasta in boiling water (duration 40
seconds)</div>
<div>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)</div>
</blockquote>
</div>
Does it make sense to wait longer than 7 mins after task A
(presuming no other task forces occupies the user at that
time)?<br>
Put differently: Can we say that the starting time of B =
Math.max((endTime of task before B), (endTime of task A +
7 minutes))?<br>
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.<br>
If we can say that, then chaining can calculate the the
starting time of a task on the fly differently.
<div><br>
<blockquote type="cite">
<div>Task C: Chop vegetables (duration 2 minutes).</div>
<div><br>
</div>
<div>This will evidently leave some gaps. The ideal
result from the solver should be:</div>
<div><br>
</div>
<div>Task A: at time 0 (ends at 40s)</div>
<div> Task C: at time 41s (ends at 2:41)</div>
<div>Task B: at time 7:40</div>
<div><br>
</div>
<div>There is a gap between C and B which is OK. </div>
<div><br>
</div>
<div>If another Task is added to the story:</div>
<div>
<div>Task D: Prepare sauce (duration 7 minutes)</div>
</div>
<div><br>
</div>
<div>I would want the following result:</div>
<div><br>
</div>
<div>Task A: at time 0 (ends at 40s)</div>
<div>Task D: at time 41s (ends 7:41s)</div>
<div>Task B: at time 8:42s (ends 9:32s)</div>
<div>Task C: at time 9:33s (ends 11:33s)</div>
<div><br>
</div>
<div>Task C can actually take place before Task A
too. </div>
<div><br>
</div>
<div>I still need to read and understand the chaining
functionality properly. Do you think it would allow
me to achieve the above?</div>
<div><br>
</div>
</blockquote>
</div>
I don't know.<br>
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.<br>
<br>
If you want to look into using continuous variables: the
support for it is limited currently.<br>
you can reuse the Drools Planner metaheuristic algorithms
(including termination, score, ...), but there's no decent
generic move factory support for continuous variables yet.<br>
So you 'll have to write a custom MoveFactory that creates
a limited subset of moves.<br>
Also, construction heuristics can't handle continuous
variables yet, so you 'll have to write a custom
SolutionIntializer.<br>
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.
<div>
<div><br>
<blockquote type="cite">
<div>thanks,</div>
<div><br>
</div>
<div>Josef</div>
<div><br>
</div>
<div><br>
<br>
<div class="gmail_quote">On 22 July 2012 20:05,
Geoffrey De Smet <span dir="ltr"><<a href="mailto:ge0ffrey.spam@gmail.com" target="_blank">ge0ffrey.spam@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
Presuming that you don't want to leave space
between tasks, you can design your model
differently by using the "chained"
functionality:<br>
it will be far more efficient and the
planning variable won't be continuous.<br>
<br>
Let's presume you're scheduling Tasks to
Persons.<br>
<br>
@PlanningEntity<br>
class Task implements TaskOrPerson {<br>
<br>
...<br>
<br>
@PlanningVariable(chained = true)<br>
@ValueRanges({<br>
@ValueRange(type =
ValueRangeType.FROM_SOLUTION_PROPERTY,
solutionProperty = "taskList"),<br>
@ValueRange(type =
ValueRangeType.FROM_SOLUTION_PROPERTY,
solutionProperty = "personList",<br>
excludeUninitializedPlanningEntity = true)})<br>
public TaskOrPerson
getPreviousTaskOrPerson() {<br>
return previousTaskOrPerson;<br>
}<br>
<br>
public int getDuration() {<br>
return duration;<br>
}<br>
<br>
public int getStartingTime() {<br>
int startingTime = 0;<br>
TaskOrPerson taskOrPerson =
getPreviousTaskOrPerson();<br>
while (taskOrPerson instanceof
Task) { // Every chain is guarantee to end
up with an anchor (= Person)<br>
startingTime += ((Task)
taskOrPerson).getDuration();<br>
taskOrPerson = ((Task)
taskOrPerson).getPreviousTaskOrPerson()<br>
}<br>
return startingTime;<br>
}<br>
<br>
}<br>
<br>
class Person implements TaskOrPerson {<br>
<br>
}<br>
<br>
For a good example, take a look at the
VehicleRouting example.<br>
For more info about chaining, in the manual
see section 4.3.4.2.6. Chained<br>
<a href="http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html_single/index.html" target="_blank">http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html_single/index.html</a><br>
<br>
<div>Op <a href="tel:22-07-12%2018" value="+35622071218" target="_blank">22-07-12
18</a>:00, Josef Bajada schreef:<br>
</div>
<blockquote type="cite">
<div>
<div>Hi,
<div><br>
</div>
<div>I am new to Drools and Drools
Planner, so apologies if I am asking
anything obvious.</div>
<div><br>
</div>
<div>My objective is to implement a
simple (for now) planner which
schedules tasks according to 2 main
criteria:</div>
<div>- Their duration (in seconds)</div>
<div>- Their dependencies on other
tasks (e.g. Hard Constraint that
Task B has to start between 180 and
200 seconds after Task A finishes).</div>
<div><br>
</div>
<div>Since there are gaps between
dependent tasks as part of the hard
constraints other tasks can be
fitted in between dependent tasks.</div>
<div>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).</div>
<div><br>
</div>
<div>The main problem I am finding is
that this start time, which is
essentially the planning variable is
a continuous variable. </div>
<div>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.</div>
<div><br>
</div>
<div>Even if the planning variable was
discrete (say bins of 5 second
intervals), there is no upper bound
as such.</div>
<div><br>
</div>
<div>How is it best to handle such
planning variables in Drools
Planner?</div>
<div><br>
</div>
<div>thanks,<br>
josef</div>
<div><br>
</div>
<div><br>
</div>
<br>
<fieldset></fieldset>
<br>
</div>
</div>
<pre>_______________________________________________
rules-users mailing list
<a href="mailto:rules-users@lists.jboss.org" target="_blank">rules-users@lists.jboss.org</a>
<a href="https://lists.jboss.org/mailman/listinfo/rules-users" target="_blank">https://lists.jboss.org/mailman/listinfo/rules-users</a><span><font color="#888888">
</font></span></pre>
<span><font color="#888888"> </font></span></blockquote>
<span><font color="#888888"> <br>
<pre cols="72">--
With kind regards,
Geoffrey De Smet</pre>
</font></span></div>
<br>
_______________________________________________<br>
rules-users mailing list<br>
<a href="mailto:rules-users@lists.jboss.org" target="_blank">rules-users@lists.jboss.org</a><br>
<a href="https://lists.jboss.org/mailman/listinfo/rules-users" target="_blank">https://lists.jboss.org/mailman/listinfo/rules-users</a><br>
<br>
</blockquote>
</div>
<br>
</div>
<br>
<fieldset></fieldset>
<br>
<pre>_______________________________________________
rules-users mailing list
<a href="mailto:rules-users@lists.jboss.org" target="_blank">rules-users@lists.jboss.org</a>
<a href="https://lists.jboss.org/mailman/listinfo/rules-users" target="_blank">https://lists.jboss.org/mailman/listinfo/rules-users</a>
</pre>
</blockquote>
<br>
<pre cols="72">--
With kind regards,
Geoffrey De Smet</pre>
</div>
</div>
</div>
<br>
_______________________________________________<br>
rules-users mailing list<br>
<a href="mailto:rules-users@lists.jboss.org" target="_blank">rules-users@lists.jboss.org</a><br>
<a href="https://lists.jboss.org/mailman/listinfo/rules-users" target="_blank">https://lists.jboss.org/mailman/listinfo/rules-users</a><br>
<br>
</blockquote>
</div>
<br>
</div>
<br>
<fieldset></fieldset>
<br>
<pre>_______________________________________________
rules-users mailing list
<a href="mailto:rules-users@lists.jboss.org" target="_blank">rules-users@lists.jboss.org</a>
<a href="https://lists.jboss.org/mailman/listinfo/rules-users" target="_blank">https://lists.jboss.org/mailman/listinfo/rules-users</a>
</pre>
</blockquote>
<br>
<pre cols="72">--
With kind regards,
Geoffrey De Smet</pre>
</div></div></div>
<br>_______________________________________________<br>
rules-users mailing list<br>
<a href="mailto:rules-users@lists.jboss.org">rules-users@lists.jboss.org</a><br>
<a href="https://lists.jboss.org/mailman/listinfo/rules-users" target="_blank">https://lists.jboss.org/mailman/listinfo/rules-users</a><br>
<br></blockquote></div><br></div>