[rules-users] Employee Shift Rostering: algorithm details

[ge0ffrey]

Drools Planner has 7 real examples, which use large datasets and are solved
near optimal in reasonable time. For example, the nurse rostering example
have search spaces over 10^2000. Research competions show that
metaheuristics are the only algorithems that can handle it in robuust way.

Wikipedia's notes are correct: there is no guarentee that the optimal
solution is found, but exact methods take forever and simplex like methods
perform much worse overall in the competitions.
For example, in the nurserostering example, the medium hint 01 example
performed 100 times ( 10 000%) on a well known simplex framework (the other
datasets were around 5% better or worse).

Tabu search is easy to implement, but there are many optimizations that
Planner implements, such as aspiration, ... Its been improved and under
constant benchmarking since 2006, so it would take some work to replicate
:-)

--
View this message in context: http://drools.46999.n3.nabble.com/Employee-Shift-Rostering-algorithm-details-tp3897546p3897706.html
Sent from the Drools: User forum mailing list archive at Nabble.com.