Nurse scheduling problem based on hydrologic cycle optimization

Building the work timetables for staff in healthcare institutions is known to be a highly constrained and NP-hard problem. In this research, a mathematical programming model, maximizing nurses' preference for work shifts and rest days while minimizing hospital operating costs, is proposed to solve the nurse scheduling problem (NSP) optimally. Then, we apply a new optimization algorithm-HCOMA, HCO based memetic algorithm, combining entropy-based decision-making mechanism and local search, to heuristically solve the NSP. In the global search, the entropy is calculated to assess population diversity following by every specified iteration. By analyzing the change of diversity, the population can identify the stagnation of search and perform local search at the best time. In summary, the local search includes three core parts: Meta-Lamarckian learning strategy, cooling schedule and Metropolis Criterion. Three neighborhood structures are utilized to exchange or reset the nurse's shifts, expanding the feasible solution area of the search and generating high-quality solutions. The Meta-Lamarckian learning strategy is used to automatically choose the best search structure based on their performance. The performance of HCOMA was tested with sufficient experimentations. The test problems were generated based on the actual situation of a hospital, including an instance and 30 random problems. The results indicate that the proposed algorithm was superior to the standard HCO and three well-known evolutionary algorithms in solution quality and convergence rate.