Construction-based metaheuristics for personnel scheduling problems.

Goodman, Melissa Dee 2007. Construction-based metaheuristics for personnel scheduling problems. PhD Thesis, Cardiff University.

PDF - Accepted Post-Print Version Download (10MB)

Abstract

This thesis investigates the idea of balancing different constraints in order to find optimal solutions to two personnel scheduling problems, within the framework of constructive metaheuristic approaches. The two problems considered are a nurse scheduling problem, for which finding feasible solutions is known to be difficult and for which the hard and soft constraints are in direct conflict, and a medical student scheduling problem for which there is little relevant literature this second problem also has conflicting hard and soft constraints, but presents further conflict between the different soft constraints. The methods used to solve these problems are focused on two constructive metaheuristics in particular: Greedy Randomised Adaptive Search Procedures (GRASP) and Ant Colony Optimisation (ACO) and for each approach several construction heuristics are introduced and compared. Using GRASP, a number of local search neighbourhoods are established for each problem, while for ACO the suitability of three trail definitions are compared. In order to further explore the balance which may obtained between the different constraints and objectives for the two problems, hybrid constructions are investigated, incorporating exact methods which take advantage of the underlying structures of each problem with regards to feasibility. For medical student scheduling, this exact method was developed into a new type of construction mechanism providing much improved results over a standard heuristic approach. Further enhancements investigated include the use of problem-specific feedback for nurse scheduling and the use of an intelligent memory procedure for the medical student scheduling problem. For the nurse scheduling problem, the final algorithm developed was able to rival the best in the literature so far and produce optimal solutions for all available datasets. For the medical student scheduling problem, optimal solutions are not known, but the results obtained are very promising and provide a good basis for further study of the problem.

Item Type:	Thesis (PhD)
Status:	Unpublished
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
ISBN:	9781303212987
Funders:	EPSRC
Date of First Compliant Deposit:	30 March 2016
Last Modified:	12 Feb 2016 23:12
URI:	https://orca.cardiff.ac.uk/id/eprint/54698

Citation Data

Actions (repository staff only)

Edit Item