Enhancing the Performance of Search Heuristics. Variable Fitness Functions and other Methods to Enhance Heuristics for Dynamic Workforce Scheduling.

摘要

Scheduling large real world problems is a complex process and finding high qualityudsolutions is not a trivial task. In cooperation with Trimble MRM Ltd., who provideudscheduling solutions for many large companies, a problem is identified and modelled. Itudis a general model which encapsulates several important scheduling, routing andudresource allocation problems in literature. Many of the state-of-the-art heuristics forudsolve scheduling problems and indeed other problems require specialised heuristicsudtailored for the problem they are to solve. While these provide good solutions a lot ofudexpert time is needed to study the problem, and implement solutions.udThis research investigates methods to enhance existing search based methods.udWe study hyperheuristic techniques as a general search based heuristic. Hyperheuristicsudraise the generality of the solution method by using a set of tools (low level heuristics)udto work on the solution. These tools are problem specific and usually make smalludchanges to the problem. It is the task of the hyperheuristic to determine which tool touduse and when. Low level heuristics using exact/heuristic hybrid method are used in thisudthesis along with a new Tabu based hyperheuristic which decreases the amount of CPUudtime required to produce good quality solutions. We also develop and investigate theudVariable Fitness Function approach, which provides a new way of enhancing mostudsearch-based heuristics in terms of solution quality. If a fitness function is pushing hardudin a certain direction, a heuristic may ultimately fail because it cannot escape localudminima. The Variable Fitness Function allows the fitness function to change over theudsearch and use objective measures not used in the fitness calculation. The VariableudFitness Function and its ability to generalise are extensively tested in this thesis.udThe two aims of the thesis are achieved and the methods are analysed in depth.udGeneral conclusions and areas of future work are also identified.