Efficient heuristics for solving precedence constrained scheduling problems

Kalfay, Amy, Crispin, Alan and Crockett, Keeley ORCID: https://orcid.org/0000-0003-1941-6201 (2020) Efficient heuristics for solving precedence constrained scheduling problems. In: Intelligent Systems Conference (IntelliSys) 2019, 05 September 2019 - 06 September 2019, London, United Kingdom.

Preview

Accepted Version Available under License In Copyright. Download (238kB) | Preview

Abstract

This paper discusses the occurrence of dependency relationships within NP hard personnel scheduling problems. These dependencies, commonly referred to as precedence constraints, arise in a number of industries including but not limited to: maintenance scheduling, home health care, and unmanned aerial vehicle scheduling. Precedence relationships, as demonstrated in this research, can significantly impact the quality of solution that can be obtained. In such a competitive market it is imperative that new and innovative ways of finding high quality solutions in short computational times are discovered. This paper presents novel datasets, containing 100-1000 jobs to allocate, that are used to benchmark two heuristic algorithms; an intelligent decision heuristic and a greedy heuristic. Each heuristic is coupled with a multi start metaheuristic to provide a set of benchmark results.