Optimisation heuristics for solving technician and task scheduling problems

Khalfay, Amy (2018) Optimisation heuristics for solving technician and task scheduling problems. Doctoral thesis (PhD), Manchester Metropolitan University.

Preview

Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (4MB) | Preview

Abstract

Motivated by an underlying industrial demand, solving intractable technician and task scheduling problems through the use of heuristic and metaheuristic approaches have long been an active research area within the academic community. Many solution methodologies, proposed in the literature, have either been developed to solve a particular variant of the technician and task scheduling problem or are only appropriate for a specific scale of the problem. The motivation of this research is to find general-purpose heuristic approaches that can solve variants of technician and task scheduling problems, at scale, balancing time efficiency and solution quality. The unique challenges include finding heuristics that are robust, easily adapted to deal with extra constraints, and scalable, to solve problems that are indicative of the real world. The research presented in this thesis describes three heuristic methodologies that have been designed and implemented: (1) the intelligent decision heuristic (which considers multiple team configuration scenarios and job allocations simultaneously), (2) the look ahead heuristic (characterised by its ability to consider the impact of allocation decisions on subsequent stages of the scheduling process), and (3) the greedy randomized heuristic (which has a flexible allocation approach and is computationally efficient). Datasets used to test the three heuristic methodologies include real world problem instances, instances from the literature, problem instances extended from the literature to include extra constraints, and, finally, instances created using a data generator. The datasets used include a broad array of real world constraints (skill requirements, teaming, priority, precedence, unavailable days, outsourcing, time windows, and location) on a range of problem sizes (5-2500 jobs) to thoroughly investigate the scalability and robustness of the heuristics. The key findings presented are that the constraints a problem features and the size of the problem heavily influence the design and behaviour of the solution approach used. The contributions of this research are; benchmark datasets indicative of the real world in terms of both constraints included and problem size, the data generators developed which enable the creation of data to investigate certain problem aspects, mathematical formulation of the multi period technician routing and scheduling problem, and, finally, the heuristics developed which have proved to be robust and scalable solution methodologies.