On Mon, Apr 9, 2012 at 1:57 PM, HarrySimons
<simonsharry@gmail.com> wrote:
Hi,
I'm new both to Drools Planner and to metaheuristic algorithms like Tabu
Search. Though I have done some preliminary reading on the Net on how this
algorithm 'generally' works -- including reading the 'plain-English'
portions of Chapter 8 of the 'Essentials of Metaheuristics' book -- it still
isn't perfectly clear to me how an actual implementation of the algorithm
would code the 'Tweak' / 'Next Move' function (other than via a random
combination of planning variables) in an application such as Employee Shift
Rostering with a very large search space and with multiple planning
variables.
If you look closer to the Nurse-Rostering example, you will notice the most important moves are 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 sufficient for your problem.
As I understand, you generally create all the possible moves. Then drools-planner will select them randomly.
On the page (http://www.jboss.org/drools/drools-planner.html) where Drools
Planner is compared side-by-side to other naive (greedy algorithms-based)
approachesfor various kinds of problems, could it be the case that the
algorithms used in Drools Planner were able to perfectly solve the
highlighted problems only because of the use of extremely small search
spaces / input datasets?! A wikipedia entry related to metaheuristic
algorithms says that not only is it possible that such an algorithm may not
give an optimal solution, it may not even give any solution at all(!!) due
to the algorithm reaching its timeout limit specified by the user. I'm
assuming it won't be possible to specify a timeout value in days or even
hours for any metaheuristics-based approach to a real-world problem of a
real-world scale.
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.
Lastly, from looking at the pseudocode of Tabu Search, it *appears* that the
core, 'driver portion' of the algorithm may itself be not all that hard to
implement; it is rather the call-back portion of the algorithm (such as the
problem-specific Tweak / Next Move function, which the driver portion calls
back) that may be hardest to implement. Given this, what would be the
advantages of using Drools Planner over a from-scratch, hand-coded version
of Tabu Search (other than its declarative, rule-based flexibility which a
hand-coded, from-scratch version may not want to implement due to its focus
on solving a specific planning problem vs. a whole slew of generic planning
problems requiring a generic piece of code such as Drools Planner)?
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.
Would greatly appreciate if someone more knowlegeable than me could clarify
/ elaborate on the above getting-started questions of mine.
Regards,
/HS
--
View this message in context: http://drools.46999.n3.nabble.com/Employee-Shift-Rostering-algorithm-details-tp3897546p3897546.html
Sent from the Drools: User forum mailing list archive at Nabble.com.
_______________________________________________
rules-users mailing list
rules-users@lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users