[rules-users] Employee Shift Rostering: algorithm details

[Patrik Dufresne]

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 at 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 at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20120409/e67ec743/attachment.html