Scheduling large real world problems is a complex process and finding high quality
solutions is not a trivial task. In cooperation with Trimble MRM Ltd., who provide
scheduling solutions for many large companies, a problem is identified and modelled. It
is a general model which encapsulates several important scheduling, routing and
resource allocation problems in literature. Many of the state-of-the-art heuristics for
solve scheduling problems and indeed other problems require specialised heuristics
tailored for the problem they are to solve. While these provide good solutions a lot of
expert time is needed to study the problem, and implement solutions.
This research investigates methods to enhance existing search based methods.
We study hyperheuristic techniques as a general search based heuristic. Hyperheuristics
raise the generality of the solution method by using a set of tools (low level heuristics)
to work on the solution. These tools are problem specific and usually make small
changes to the problem. It is the task of the hyperheuristic to determine which tool to
use and when. Low level heuristics using exact/heuristic hybrid method are used in this
thesis along with a new Tabu based hyperheuristic which decreases the amount of CPU
time required to produce good quality solutions. We also develop and investigate the
Variable Fitness Function approach, which provides a new way of enhancing most
search-based heuristics in terms of solution quality. If a fitness function is pushing hard
in a certain direction, a heuristic may ultimately fail because it cannot escape local
minima. The Variable Fitness Function allows the fitness function to change over the
search and use objective measures not used in the fitness calculation. The Variable
Fitness Function and its ability to generalise are extensively tested in this thesis.
The two aims of the thesis are achieved and the methods are analysed in depth.
General conclusions and areas of future work are also identified.
| Identifer | oai:union.ndltd.org:BRADFORD/oai:bradscholars.brad.ac.uk:10454/4310 |
| Date | January 2009 |
| Creators | Remde, Stephen M. |
| Contributors | Cowling, Peter I., Dahal, Keshav P. |
| Publisher | University of Bradford, Department of Computing |
| Source Sets | Bradford Scholars |
| Language | English |
| Detected Language | English |
| Type | Thesis, doctoral, PhD |
| Rights | <a rel="license" href="http://creativecommons.org/licenses/by-nc-nd/3.0/"><img alt="Creative Commons License" style="border-width:0" src="http://i.creativecommons.org/l/by-nc-nd/3.0/88x31.png" /></a><br />The University of Bradford theses are licenced under a <a rel="license" href="http://creativecommons.org/licenses/by-nc-nd/3.0/">Creative Commons Licence</a>. |
Page generated in 0.0024 seconds