A hybrid fix-and-optimize and simulated annealing approaches for nurse rostering problem

Turhan A. M., BİLGEN B.

COMPUTERS & INDUSTRIAL ENGINEERING, cilt.145, 2020 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 145
  • Basım Tarihi: 2020
  • Doi Numarası: 10.1016/j.cie.2020.106531
  • Dergi Adı: COMPUTERS & INDUSTRIAL ENGINEERING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, ABI/INFORM, Aerospace Database, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, Metadex, DIALNET, Civil Engineering Abstracts
  • Anahtar Kelimeler: OR in health services, Nurse rostering problem, Fix-and-relax, Fix-and-optimize, Simulated annealing, VARIABLE NEIGHBORHOOD SEARCH, GENETIC ALGORITHM, SCHEDULING PROBLEMS, PROGRAMMING-MODEL, TABU SEARCH, STAFF, PERSONNEL, INTEGER, ALLOCATION, SOFT
  • Dokuz Eylül Üniversitesi Adresli: Evet

Özet

The Nurse Rostering Problem (NRP) is a complex scheduling problem in which nurses must be assigned to shifts according to a set of constraints. The NRP is difficult to solve to optimality due to its combinatorial structure. In this paper, we propose a hybrid solution algorithm that combines Mixed Integer Programming (MIP) based heuristics-namely Fix-and-Relax (F&R) and Fix-and-Optimize (F&O)-and Simulated Annealing (SA) to solve the NRP. In MIP-based heuristics, a problem is decomposed into a set of smaller problems and each problem is iteratively solved to optimality. In the hybrid approach, high-quality initial solutions are obtained via the F&R algorithm and fed to the SA part of the algorithm. When solutions can no longer be improved, the F&O algorithm is inserted into the SA algorithm. This enables the hybrid algorithm to diversify the search space and provide better solutions. To assess the quality and efficiency of the hybrid approach, we use 24 publicly available test instances recently introduced in literature in the field. Computational results show that the hybrid method outperforms other advanced solution techniques in most of the test data and seven new best-known results are reported.