Skip to main content

Research Repository

Advanced Search

Lookahead policy and genetic algorithm for solving nurse rostering problems

Peng, Shi; Dario, Landa-Silva

Authors

Shi Peng



Abstract

Previous research has shown that value function approximation in dynamic programming does not perform too well when tackling difficult combinatorial optimisation problem such as multi-stage nurse rostering. This is because the large action space that need to be explored. This paper proposes to replace the value function approximation by a genetic algorithm in order to generate solutions to the stages before applying the lookahead policy to evaluate the future effect of decisions made in previous stages. Then, the paper proposes a hybrid approach that generates sets of weekly rosters through a genetic algorithm for consideration by the lookahead procedure that assembles a solution for the whole planning horizon of several weeks. Results indicate that this hybrid between an evolutionary algorithm and the lookahead policy mechanism from dynamic programming performs more competitive than the value function approximation dynamic programming investigated before. Results also show that the proposed algorithm is ranked well in respect of several other algorithms applied to the same set of problem instances. The intended contribution of this paper is towards a better understanding of how to successfully apply dynamic programming mechanisms to tackle difficult combinatorial optimisation problems.

Citation

Peng, S., & Dario, L. (2018). Lookahead policy and genetic algorithm for solving nurse rostering problems. In n/a

Conference Name 4th International Conference on Machine Learning, Optimization and Data Science (LOD 2018)
Start Date Sep 13, 2018
End Date Sep 16, 2018
Acceptance Date Jul 15, 2018
Online Publication Date Sep 16, 2018
Publication Date Sep 16, 2018
Deposit Date Oct 8, 2018
Publicly Available Date
Book Title n/a
Chapter Number n/a
ISBN n/a
Keywords hybrid algorithm, genetic algorithm, lookahead policy evaluation, dynamic programming, nurse rostering problem
Public URL https://nottingham-repository.worktribe.com/output/1150326
Related Public URLs https://lod2018.icas.xyz/