Quote:
Originally Posted by IanWright
The program I need need only be very simple, but unfortunately I think the background problem isn't quite so simple and I'm not quite sure how to solve it.
You're right: rostering problems are the hardest NPC problems together with
a few other problems (e.g. capacitated vehicle routing problems). I personally
have never seen a robust heuristic that could solve a 'medium complicated'
rostering problem.
The feasible approaches are genetic algorithms or simulated annealing. The
latter approach is a bit simpler to implement: find a solution, any solution,
possiblty infeasible and assign a cost function to your solutions. Threat
infeasibilities as having a very high cost factor.
Given the current solution find another solution, possibly worse than the current
solution. Given the total cost of the current solution compute a 'chance' that
you will take an uphill step; if the step is a downhill step always take it. Google
for 'Boltzmann temperature' for details. Repeat this process until you're stuck. If the
last solution is acceptible in terms of the cost function stop, otherwise apply a
form of tabu search and start from that new solution again.
kind regards,
Jos
