关键词: 护士排班, 智能多样化变邻域搜索, 并行增量式计算

Abstract:

Nurse rostering problem, NRP is an NP-hard optimization problem with multiple constraints. Good nurse rostering is of great significance to improve the efficiency of nurses’ work and optimize the allocation of human resources in hospitals. However,most existing NRP algorithms not only suffer from a non-effective balance between computational time and solution quality, but also deal with the large-scale NRP with difficulty. Motivated to overcome the above problem, in this paper, an intelligent and efficient two-steps parallel nurse rostering algorithm IEPNR is presented with some intelligent and efficient optimization strategies. First, the IEPNR adopts a heuristic method to sort initial stochastic solutions to obtain its high-quality initial solution. Then, a novel intelligent parallel diversified variable neighborhood search and incremental computing strategy are used to quickly obtain optimal solutions. Meanwhile, the random disturbances and a taboo list are introduced to efficiently escape from local optimal solutions and to avoid redundant calculations. Extensive experiments on the benchmarks show that the proposed algorithm IEPNR outperforms the state-of-the-art algorithms in the average solution quality and running time, and that it is more suitable for the large-scale NRP.

Key words: nurse rostering, intelligent variable neighborhood search, parallel incremental computing