Efficient heuristics for solving precedence constrained scheduling problems

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