I may not be an expert, but I may give you some tips.<div><br></div><div>Read below....</div><div><br></div><div><br clear="all">Patrik Dufresne<br>
<br><br><div class="gmail_quote">On Mon, Apr 9, 2012 at 1:57 PM, HarrySimons <span dir="ltr"><<a href="mailto:simonsharry@gmail.com">simonsharry@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi,<br>
<br>
I'm new both to Drools Planner and to metaheuristic algorithms like Tabu<br>
Search. Though I have done some preliminary reading on the Net on how this<br>
algorithm 'generally' works -- including reading the 'plain-English'<br>
portions of Chapter 8 of the 'Essentials of Metaheuristics' book -- it still<br>
isn't perfectly clear to me how an actual implementation of the algorithm<br>
would code the 'Tweak' / 'Next Move' function (other than via a random<br>
combination of planning variables) in an application such as Employee Shift<br>
Rostering with a very large search space and with multiple planning<br>
variables.<br></blockquote><div><br></div><div>If you look closer to the Nurse-Rostering example, you will notice the most important moves are <span class="final-path" style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;border-top-width:0px;border-right-width:0px;border-bottom-width:0px;border-left-width:0px;border-style:initial;border-color:initial;font:inherit;background-color:rgb(255,255,255)"><span style="font-family:Helvetica,arial,freesans,clean,sans-serif;line-height:25px">EmployeeChangeMove and ShiftAssignmentSwapMove. Those moves may be qualify as small moves. As recommended in the Drool-planner user guide, Tabu search perform great with small moves (see Chapter 8.5). It's generally very simple to implement this type of moves and may be </span><font face="Helvetica, arial, freesans, clean, sans-serif"><span style="line-height:25px">sufficient</span></font><span style="font-family:Helvetica,arial,freesans,clean,sans-serif;line-height:25px"> for your problem.</span></span></div>
<div><span class="final-path" style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;border-top-width:0px;border-right-width:0px;border-bottom-width:0px;border-left-width:0px;border-style:initial;border-color:initial;font:inherit;background-color:rgb(255,255,255)"><font face="Helvetica, arial, freesans, clean, sans-serif"><span style="line-height:25px">As I understand, you generally create all the possible moves. Then drools-planner will select them randomly. </span></font></span></div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
On the page (<a href="http://www.jboss.org/drools/drools-planner.html" target="_blank">http://www.jboss.org/drools/drools-planner.html</a>) where Drools<br>
Planner is compared side-by-side to other naive (greedy algorithms-based)<br>
approachesfor various kinds of problems, could it be the case that the<br>
algorithms used in Drools Planner were able to perfectly solve the<br>
highlighted problems only because of the use of extremely small search<br>
spaces / input datasets?! A wikipedia entry related to metaheuristic<br>
algorithms says that not only is it possible that such an algorithm may not<br>
give an optimal solution, it may not even give any solution at all(!!) due<br>
to the algorithm reaching its timeout limit specified by the user. I'm<br>
assuming it won't be possible to specify a timeout value in days or even<br>
hours for any metaheuristics-based approach to a real-world problem of a<br>
real-world scale.<br></blockquote><div><br></div><div>In real-world problem involving workforce management, you should get a feasible solution very fast. With drools-planner you can configure a construction heuristic to get a first feasible solution -- the nurse-rostering example use one. Then the tabu search is used to improve the solution. You may then consider the solution created by the construction heuristic as the worst solution.</div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Lastly, from looking at the pseudocode of Tabu Search, it *appears* that the<br>
core, 'driver portion' of the algorithm may itself be not all that hard to<br>
implement; it is rather the call-back portion of the algorithm (such as the<br>
problem-specific Tweak / Next Move function, which the driver portion calls<br>
back) that may be hardest to implement. Given this, what would be the<br>
advantages of using Drools Planner over a from-scratch, hand-coded version<br>
of Tabu Search (other than its declarative, rule-based flexibility which a<br>
hand-coded, from-scratch version may not want to implement due to its focus<br>
on solving a specific planning problem vs. a whole slew of generic planning<br>
problems requiring a generic piece of code such as Drools Planner)?<br>
<br></blockquote><div>I would definitely recommend drools-planner to your own implementation of the Tabu search just to benefit from the drools engine it self which provide you a very fast way to calculate the solution's score. The score is calculated using an accumulate and then doesn't required to calculate the score from scratch. I benchmark drools vs a plain java score function and drools is way way faster.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Would greatly appreciate if someone more knowlegeable than me could clarify<br>
/ elaborate on the above getting-started questions of mine.<br>
<br>
Regards,<br>
/HS<br>
<br>
--<br>
View this message in context: <a href="http://drools.46999.n3.nabble.com/Employee-Shift-Rostering-algorithm-details-tp3897546p3897546.html" target="_blank">http://drools.46999.n3.nabble.com/Employee-Shift-Rostering-algorithm-details-tp3897546p3897546.html</a><br>
Sent from the Drools: User forum mailing list archive at Nabble.com.<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>
</blockquote></div><br></div>