logo

SCIENTIA SINICA Informationis, Volume 46, Issue 7: 834-854(2016) https://doi.org/10.1360/N112015-00284

Weighted tabu search for multi-stage nurse rostering problem

More info
  • ReceivedMar 8, 2016
  • AcceptedApr 14, 2016

Abstract

This paper presents a study of the multi-stage nurse rostering problem, which was proposed in the Second International Nurse Rostering Competition. We propose a weighted tabu search algorithm for solving this rostering problem, which is a very important problem in healthcare optimization. The algorithm employs the following neighborhood structures: $3$ structures that are exclusive to each other and $1$ compound structure. The possibilities of selecting a neighborhood to search are tuned dynamically by the extent to which they are adaptive. Meanwhile, the balance between intensification and diversification during the search procedure is achieved by adjusting the weight of the penalty for each nurse. We address the problem caused by the lack of global information within each independent stage by proposing an approximate evaluation strategy for spanning constraints. The algorithm employs a cache for neighborhood move evaluation with the purpose of reducing the overall computational cost for the adaptive neighborhood selection strategy, which improves the efficiency of the algorithm further. The benchmark result of our algorithm on $60$ instances from the competition shows good solving quality and ranks fourth in the final of the Second International Nurse Rostering Competition. Furthermore, we compare and analyze some key factors in the algorithm and demonstrate their rationality.


Funded by

国家自然科学基金(61370183)

国家自然科学基金(61100144)


References

[1] Cheang B, Li H B, Lim A, et al. Nurse rostering problems--a bibliographic survey. Eur J Oper Res, 2003, 151: 447 CrossRef Google Scholar

[2] Burke E K, de Causmaecker P, Berghe G V, et al. The state of the art of nurse rostering. J Scheduling, 2004, 7: 441 CrossRef Google Scholar

[3] de Causmaecker P, Berghe G V. A categorisation of nurse rostering problems. J Scheduling, 2011, 14: 3 CrossRef Google Scholar

[4] Isken M W. An implicit tour scheduling model with applications in healthcare. Ann Oper Res, 2004, 128: 91 CrossRef Google Scholar

[5] Glass C A, Knight R A. The nurse rostering problem: a critical appraisal of the problem structure. Eur J Oper Res, 2010, 202: 379 CrossRef Google Scholar

[6] Beli{ë}n J, Demeulemeester E. A branch-and-price approach for integrating nurse and surgery scheduling. Eur J Oper Res, 2008, 189: 652 CrossRef Google Scholar

[7] He F, Qu R. A constraint programming based column generation approach to nurse rostering problems. Comput Oper Res, 2012, 39: 3331 CrossRef Google Scholar

[8] Burke E, de Causmaecker P, Berghe G V. A hybrid tabu search algorithm for the nurse rostering problem. In: Proceedings of Simulated Evolution and Learning. Berlin: Springer, 1999. 187-194. Google Scholar

[9] Burke E, Cowling P, de Causmaecker P, et al. A memetic approach to the nurse rostering problem. Appl Intell, 2001, 15: 199 CrossRef Google Scholar

[10] Burke E, de Causmaecker P, Petrovic S, et al. Variable neighborhood search for nurse rostering problems. In: Proceedings of Metaheuristics: Computer Decision-Making. Berlin: Springer, 2004. 153-172. Google Scholar

[11] Burke E K, Curtois T, Post G, et al. A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem. Eur J Oper Res, 2008, 188: 330 CrossRef Google Scholar

[12] Burke E K, Curtois T, Qu R, et al. A scatter search methodology for the nurse rostering problem. J Oper Res Soc, 2010, 61: 1667 CrossRef Google Scholar

[13] Burke E K, Curtois T, Qu R, et al. A time predefined variable depth search for nurse rostering. INFORMS J Comput, 2013, 25: 411 CrossRef Google Scholar

[14] Bai R, Burke E K, Kendall G, et al. A hybrid evolutionary approach to the nurse rostering problem. IEEE Trans Evol Comput, 2010, 14: 580 CrossRef Google Scholar

[15] Anwar K, Awadallah M, Khader A T, et al. Hyper-heuristic approach for solving nurse rostering problem. In: Proceedings of IEEE Symposium on Computational Intelligence in Ensemble Learning (CIEL), Orlando, 2014. 1-6. Google Scholar

[16] Huang H, Lin W J, Lin Z Y, et al. An evolutionary algorithm based on constraint set partitioning for nurse rostering problems. Neural Comput Appl, 2014, 25: 703 CrossRef Google Scholar

[17] Haspeslagh S, de Causmaecker P, Schaerf A, et al. The first international nurse rostering competition 2010. Ann Oper Res, 2014, 218: 221 CrossRef Google Scholar

[18] Ceschia S, Dang N T T, de Causmaecker P, et al. Second international nurse rostering competition (INRC-II)--problem description and rules--. arXiv:1501.04177, 2015. Google Scholar

[19] Valouxis C, Gogos C, Goulas G, et al. A systematic two phase approach for the nurse rostering problem. Eur J Oper Res, 2012, 219: 425 CrossRef Google Scholar

[20] Burke E K, Curtois T. New approaches to nurse rostering benchmark instances. Eur J Oper Res, 2014, 237: 71 CrossRef Google Scholar

[21] L{ü} Z P, Hao J K. Adaptive neighborhood search for nurse rostering. Eur J Oper Res, 2012, 218: 865-876 CrossRef Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1