I may not be an expert, but I may give you some tips.
Read below....
Patrik Dufresne
On Mon, Apr 9, 2012 at 1:57 PM, HarrySimons <simonsharry(a)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-deta...
Sent from the Drools: User forum mailing list archive at
Nabble.com.
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users