<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<br>
<div class="moz-cite-prefix">Op 11-09-12 04:02, Josef Bajada
schreef:<br>
</div>
<blockquote
cite="mid:CAJOvgLLbx6fdcKE6466Go_UQSoP6p7sd0RbhCRJHgCUUbZXA+g@mail.gmail.com"
type="cite">Hi Geoffrey,
<div><br>
</div>
<div>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)</div>
</blockquote>
If you use DRL, the incremental score calculation comes
automatically.<br>
Basically, the average calculation score count should be above
1000/s, even for cases with 1000+ entities. Without incremental
score calcluation, the average calculation score count won't be
anywhere near that when the entityList size scales out.<br>
<blockquote
cite="mid:CAJOvgLLbx6fdcKE6466Go_UQSoP6p7sd0RbhCRJHgCUUbZXA+g@mail.gmail.com"
type="cite">
<div>
<br>
</div>
<div>However I am facing one problem with our approach:</div>
<div><br>
</div>
<div>Lets say we have 3 tasks A, B, and C, each of duration 1 just
for simplicity, with these constraints:</div>
<div><br>
</div>
<div>a) B can only start between A.endTime + 10 and A.endTime +
100</div>
<div>b) C can only start between A.endTime + 50 and A.endTime +
100 </div>
<div>c) C can only start between B.endTime + 10 and B.endTime + 20</div>
<div><br>
</div>
<div>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.</div>
<div>On the other hand C cannot start before time 51, thus
violating constaint C. <br>
</div>
</blockquote>
Good point. The question is whether you need to go for an
implementation<br>
1) for which B can have any gap with A between 10 and 100<br>
or 2) for which B can only chose from a specific set of gap lengths
between 10 and 100: 11, 99, 51, (51 - B length), ...<br>
I think 2) is probably not realistic, if you start adding many other
tasks it becomes unmanageable (unless we are overlooking a clever
way to filter potential gaps).<br>
<br>
Ok, so the question is if we want this design:<br>
<br>
1) @PlanningEntity class Task {<br>
@PlanningVariable Task previousTask;<br>
@PlanningVariable int gap;<br>
}<br>
<br>
Or your original design:<br>
<br>
0) @PlanningEntity class Task {<br>
@PlanningVariable int startTime;<br>
}<br>
<br>
(there might be other designs too)<br>
<br>
It kinda depends on your planning window length what might works
best:<br>
Presume you have a planning window length of 100000 and 200 tasks
and an average maximum gap of 100.<br>
In case 0), each of 200 tasks will have 1 variable with 100000
values. => that's a search space of 100000^200 = 10^1000.<br>
In case 1), each of 200 tasks will have 2 variables, one var with
200 values and one var with on average 100 values. => that's a
search space of (100 * 200)^200 = 10^860.<br>
Note that those kind of search space sizes are ok, don't let the
numbers scare you.<br>
<br>
<blockquote
cite="mid:CAJOvgLLbx6fdcKE6466Go_UQSoP6p7sd0RbhCRJHgCUUbZXA+g@mail.gmail.com"
type="cite">
<div>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?</div>
</blockquote>
In a custom MoveFactory you could detect these situations and
generate moves for them.<br>
The advantage of design 1) is that you 'd be effectively pushing all
the tasks dependent on the task that get moved too.<br>
If those dependent task don't get pushed back, they 'll cause a hard
constraint to trigger and the move will be very unlikely to win the
local search step.<br>
This is known as a "score trap" (see manual).<br>
<br>
You might also want to take a long hard look at as complex as
BedDesignationPillarPartSwapMoveFactory in the hospital bed planning
example.<br>
The idea is to swap 2 chains of tasks, instead of just 2 tasks.<br>
<br>
<blockquote
cite="mid:CAJOvgLLbx6fdcKE6466Go_UQSoP6p7sd0RbhCRJHgCUUbZXA+g@mail.gmail.com"
type="cite">
<div><br>
</div>
<div>thanks again,</div>
<div><br>
</div>
<div>Josef</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
<br>
<div class="gmail_quote">On 20 August 2012 09:46, Geoffrey De
Smet <span dir="ltr"><<a moz-do-not-send="true"
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"> You 'll want
incremental score calculation (with delta's) for your "end
times".<br>
<a moz-do-not-send="true"
href="http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html_single/index.html#incrementalScoreCalculation"
target="_blank">http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html_single/index.html#incrementalScoreCalculation</a><br>
<br>
So that naturally puts the calculation of those end times
in the scoreDRL (or IncrementalJavaCalculator if you're
not using drools).<br>
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.<br>
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.<br>
If it is a property on your model, either the DRL must
first "correct it" (with higher salience rules for
example),<br>
or custom moves must "correct it" as they are being done
(which is very hard as it entails constraints
functionality).<br>
<br>
As for the cloning: it's quite simple:<br>
Either the model's entity contains the endTime property,
then clone it.<br>
If it doesn't, then there's nothing to clone.<br>
I don't see any problems related to the cloning.<br>
<br>
<div>Op 18-08-12 01:53, Josef Bajada schreef:<br>
</div>
<div>
<div>
<blockquote type="cite">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
moz-do-not-send="true"
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>
<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><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
moz-do-not-send="true"
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
moz-do-not-send="true"
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
moz-do-not-send="true"
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
moz-do-not-send="true"
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
moz-do-not-send="true"
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 moz-do-not-send="true" href="mailto:rules-users@lists.jboss.org" target="_blank">rules-users@lists.jboss.org</a>
<a moz-do-not-send="true" 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
moz-do-not-send="true"
href="mailto:rules-users@lists.jboss.org" target="_blank">rules-users@lists.jboss.org</a><br>
<a
moz-do-not-send="true"
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 moz-do-not-send="true" href="mailto:rules-users@lists.jboss.org" target="_blank">rules-users@lists.jboss.org</a>
<a moz-do-not-send="true" 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 moz-do-not-send="true"
href="mailto:rules-users@lists.jboss.org"
target="_blank">rules-users@lists.jboss.org</a><br>
<a moz-do-not-send="true"
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 moz-do-not-send="true" href="mailto:rules-users@lists.jboss.org" target="_blank">rules-users@lists.jboss.org</a>
<a moz-do-not-send="true" 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 moz-do-not-send="true"
href="mailto:rules-users@lists.jboss.org"
target="_blank">rules-users@lists.jboss.org</a><br>
<a moz-do-not-send="true"
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 moz-do-not-send="true" href="mailto:rules-users@lists.jboss.org" target="_blank">rules-users@lists.jboss.org</a>
<a moz-do-not-send="true" 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 moz-do-not-send="true"
href="mailto:rules-users@lists.jboss.org" target="_blank">rules-users@lists.jboss.org</a><br>
<a moz-do-not-send="true"
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 class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
rules-users mailing list
<a class="moz-txt-link-abbreviated" href="mailto:rules-users@lists.jboss.org">rules-users@lists.jboss.org</a>
<a class="moz-txt-link-freetext" href="https://lists.jboss.org/mailman/listinfo/rules-users">https://lists.jboss.org/mailman/listinfo/rules-users</a>
</pre>
</blockquote>
<br>
</body>
</html>