A Novel Population-based Local Search for Nurse Rostering Problem

Mutasem K. Alsmadi


Population-based approaches regularly are better than single based (local search) approaches in exploring the search space. However, the drawback of population-based approaches is in exploiting the search space. Several hybrid approaches have proven their efficiency through different domains of optimization problems by incorporating and integrating the strength of population and local search approaches. Meanwhile, hybrid methods have a drawback of increasing the parameter tuning. Recently, Population-Based Local Search (PB-LS) was proposed for a university course-timetabling problem with fewer parameters than existing approaches, the proposed approach proves its effectiveness. PB-LS employs two operators to intensify and diversify the search space. The first operator is applied to a single solution, while the second is applied for all solutions. This paper aims to investigate the performance of PB-LS for the nurse rostering problem. The INRC2010 database with a dataset composed of 69 instances is used to test the performance of PB-LS. A comparison was made between the performance of PB-LS and other existing approaches in the literature. Results show good performances of PB-LS compared to other approaches (PB-LS provides best results in 55 cases over 69 instances used in experiments).


Nurse Rostering Problem, Population-Based Approaches, Local Search and Gravitational Emulation


Brucker, P., Qu, R., Burke, E., "Personnel scheduling: models and complexity," Eur. J. Oper. Res, 2011, vol. 210 (3), pp. 467–473.

Dorigo, M., Stützle, T., "Ant colony optimization: overview and recent advances," Handbook of Metaheuristics. Springer, 2010, pp. 227–263.

Bartholdi III, J.J., "A guaranteed-accuracy round-off algorithm for cyclic scheduling and set covering," Oper. Res.,1981, vol. 29 (3), pp. 501–510.

Millar, H.H., Kiragu, M., "Cyclic and non-cyclic scheduling of 12 h shift nurses by network programming," Eur. J. Oper. Res., 1998, vol. 104 (3), pp. 582–592.

Lü, Z., Hao, J.-K., "Adaptive neighborhood search for nurse rostering," Eur. J. Oper. Res., 2012, vol. 218 (3), pp. 865–876.

Jaradat, G.M., Al-Badareen, A., Ayob, M., Al-Smadi, M., Al-Marashdeh, I., Ash-Shuqran, M., Al-Odat, E., "Hybrid Elitist-Ant System for Nurse-Rostering Problem," Journal of King Saud University – Computer and Information Sciences 2018, https://doi.org/10.1016/j.jksuci.2018.02.00.

Rajeswari, M., Amudhavel, J., Pothula, S., Dhavachelvan, P., "Directed Bee Colony Optimization Algorithm to Solve the Nurse Rostering Problem," Comput. Intell. Neurosci. 2017.

Awadallah, M.A., Al-Betar, M.A., Khader, A.T., Bolaji, A.L.a., Alkoffash, M., "Hybridization of harmony search with hill climbing for highly constrained nurse rostering problem," Neural Comput. Appl., 2017, vol. 28(3), pp. 463–482.

Santos, H.G., Toffolo, T.A., Gomes, R.A., Ribas, S., "Integer programming techniques for the nurse rostering problem," Ann. Oper. Res., 2016, vol. 239 (1), pp. 225–251.

Awadallah, M.A, Bolaji, A.L.a, Al-Betar, M.A., "A hybrid artificial bee colony for a nurse rostering problem," Appl. Soft Comput., 2015, vol. 35, pp. 726–739.

Burke, E.K., Curtois, T., "New approaches to nurse rostering benchmark instances," Eur. J. Oper. Res., 2014, vol. 237 (1), pp. 71–81.

Bilgin, B., Demeester, P., Misir, M., Vancroonenburg, W., Berghe, G.V., "One hyper-heuristic approach to two timetabling problems in health care," J.Heuristics, 2012, vol. 18 (3), pp. 401–434.

Valouxis, C., Gogos, C., Goulas, G., Alefragis, P., Housos, E., "A systematic two phase approach for the nurse rostering problem," Eur. J. Oper. Res., 2012, vol. 219 (2), pp. 425–433.

Nonobe, K.,. "INRC2010: An approach using a general constraint optimization solver," The First International Nurse Rostering Competition, PATAT 2010 (http://www. kuleuven-kortrijk.be/nrpcompetition).

Blum, C., Roli, A., "Metaheuristics in combinatorial optimization: overview and conceptual comparison," ACM Comput Surv, 2003, vol. 35(3), pp. 268–308

Ayvaz, D., Topcuoglu, H., Gurgen, F.," Performance evaluation of evolutionary heuristics in dynamic environments," Appl Intell, 2012, vol. 37(1), pp. 130–144.

Cheshmehgaz H.R., Desa, M., Wibowo, A., "Effective local evolutionary searches distributed on an island model solving bi-objective optimization problems," Appl Intell , 2013, vol. 38(3), pp. 331–356. doi:10.1007/s10489-012-0375-7

Abuhamdah, A., Ayob, M., Kendall, G., Sabar, NR.," Population based local search for university course timetabling problems," Appl Intell, 2013, vol. 40(1), pp. 44–53.

Webster, BL., "Solving combinatorial optimization problems using a new algorithm based on gravitational attraction," PhD thesis, College of Engineering at Florida Institute of Technology, 2004.

Abuhamdah, A., Ayob, M., "MPCA-ARDA for solving course timetabling problems," In: 3rd conference on data mining and optimization (DMO). IEEE Press, New York, 2011, pp.171–177

Farah, I.R., Boulila, W., Ettabaa, K.S., Solaiman, B., Ahmed, M.B., "Interpretation of multi-sensor remote sensing images: multi-approach fusion of uncertain information," IEEE Transactions on Geoscience and Remote Sensing, 2008, vol. 46 (12), pp. 4142–4152.

Grolimund, S. and Ganascia, J.G., "Driving tabu search with case-based reasoning," European Journal of Operational Research, 1997, vol. 103(2), pp. 326–338.

DOI: http://doi.org/10.11591/ijece.v11i1.pp%25p
Total views : 0 times

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

ISSN 2088-8708, e-ISSN 2722-2578