A real-life problem is the rostering of nurses at hospitals. It is a famous nondeterministic, polynomial time (NP) -hard combinatorial optimization problem. Handling the real-world nurse rostering problem (NRP) constraints in distributing workload equally between available nurses is still a difficult task to achieve. The international shortage of nurses, in addition to the spread of COVID-19, has made it more difficult to provide convenient rosters for nurses. Based on the literature, heuristic-based methods are the most commonly used methods to solve the NRP due to its computational complexity, especially for large rosters. Heuristic-based algorithms in general have problems striking the balance between diversification and intensification. Therefore, this paper aims to introduce a novel metaheuristic hybridization that combines the enhanced harmony search algorithm (EHSA) with the simulated annealing (SA) algorithm called the annealing harmony search algorithm (AHSA). The AHSA is used to solve NRP from a Malaysian hospital. The AHSA performance is compared to the EHSA, climbing harmony search algorithm (CHSA), deluge harmony search algorithm (DHSA), and harmony annealing search algorithm (HAS). The results show that the AHSA performs better than the other compared algorithms for all the tested instances where the best ever results reported for the UKMMC dataset.

One highly constrained scheduling problem is the rostering of nurses in hospitals. Nurse rostering addresses distributing shifts fairly among available nurses to cover a certain period while satisfying several constraints. Nurse Rostering Problem (NRP) is a challenging problem for which no single solution model can be applied to solve all instances of the problem [

Nurse rostering is a popular research areas due to several factors that are intensifying the NRP, including an international shortage of nurses due to high turnover, inconvenient working environment, and the high risks that nurses face due to direct interaction with COVID-19 [

Inspired by the relationship with the music spontaneous creation measure, the harmony search algorithm (HSA) is an evolutionary algorithm that was presented in 2001 by Geem et al. [

To overcome some of the drawbacks of the original HSA, the research in [

The main contribution in this research is the novel hybridization introduced between the enhanced harmony search algorithm (EHSA) with a simulated annealing (SA) called the annealing harmony search algorithm (AHSA). AHSA then used to solve a real-world NRP belonging to the medical centre of National University Malaysia (UKMMC). To show the strength of the introduced algorithm, the AHSA is evaluated and compared against previous variants of the HSA in [

This research is an extension of previous works aimed at improving the EHSA [

Based on the literature, it is clear that metaheuristic algorithms have gained the attention of researchers to solve the NRP. The SA algorithm [

HSA applied successfully to solve NRP, recently as in [

Researchers in [

The UKMMC dataset is a nurse rostering dataset representing a real-world NRP belonging to the UKMMC, where approximately 1400 nurses serve the patients. The UKMMC dataset includes eight instances. It also has seven hard constraints and five soft constraints. For further details about the mathematical model, constraints, coverage demand, types of nurses, and penalty values of the UKMMC dataset, please refer to [

_{s}_{s}

^{th}

^{th}

^{th}

^{th}

^{th}

_{p}

In this mathematical model, we have four working shifts: morning (M), evening (E), night (N) and a day off (o). These 4 shifts are represented by the set

As with other scheduling problems, constraints can be classified as hard and soft. Hard constraints cannot be violated under any condition while soft constraints can be violated, but we add a penalty for each constraint violated based on how many times the violation occurs. The UKMMC dataset has the following hard and soft constraints.

1). The coverage demand for nurses must be fulfilled.

2). One-shift a day is the highest number of shifts for each nurse each day.

3). It is obligatory to have at least one senior-nurse for each working-shift.

4). An isolated working shift is not allowed where the nurse has off before and after a single working shift.

5). For a roster period of 14 days, 12 days is the maximum number of working days whilst 10 days is the minimum.

6). A nurse is not allowed to work more than four working days consecutively.

7). If the nurse works four consecutive night shifts, then s/he is entitled to get two days off.

1). Equal allocation for working days and days off for all working nurses.

2). It is highly preferable to assign a day off during weekends (Saturday or Sunday).

3). Four consecutive morning shifts followed by a day off is highly preferable.

4). Four evening shifts consecutively followed by a day off is highly preferable.

5). Four night shifts followed by evening shift or day off after the 2 days off that follows the patterns of night shift (NNNNxxE) or (NNNNxxx).

Soft Constraints (1) and (2) are the most desired constraints to be satisfied according to the extracted information from the UKMMC Nursing Department. For soft constraints 1, 2, 3, 4, and 5, the associated penalty values (PVs) are 100, 100, 10, 10, and 1, respectively. The constraint that has a higher PV specifies the significance of that constraint. For example, it is more important that the constraint with PV 100 is satisfied than that with PV 10 or 1.

For the coverage demand required to cover selected instances of the UKMMC dataset, the number of nurses, senior nurses, and required nurses for the morning (M), evening (E), and night (N) shifts on weekdays and weekends are presented in

Weekdays Mon-Fri | Weekend Sat and Sun | |||||||
---|---|---|---|---|---|---|---|---|

Instance | Total number of Nurses | Senior nurses | M | E | N | M | E | N |

CICU | 11 | 8 | 3 | 3 | 2 | 2 | 2 | 2 |

SGY5 | 18 | 11 | 4 | 4 | 3 | 4 | 4 | 2 |

MD1 | 19 | 12 | 4 | 4 | 3 | 4 | 4 | 2 |

NICU | 49 | 29 | 10 | 10 | 10 | 8 | 8 | 7 |

N50 | 50 | 31 | 10 | 10 | 10 | 10 | 10 | 10 |

ED | 57 | 32 | 13 | 13 | 10 | 11 | 11 | 8 |

GICU | 73 | 38 | 16 | 16 | 15 | 15 | 15 | 14 |

ICU | 79 | 41 | 17 | 17 | 16 | 16 | 16 | 15 |

The objective function for the UKMMC dataset is to reduce all penalty values that occur because of violating the soft constraints.

The EHSA is an enhanced variant of the basic HSA that uses the semicyclic shift patterns approach (SCSPA) introduced in [

After the allocation, the process is done and then the repair mechanism is used to repair the infeasible initial solution produced by the SCSPA. Regarding the patterns containing night shifts, we select a shift pattern with the same night shifts and different M and E shifts than the allocated pattern to replace one of the allocated patterns that contain night shifts. One rule that governs the replacement and swapping process is that they should be performed within the same duty roster. If the shift pattern to be replaced or swapped is from the duty roster of the first week, it must be swapped with another shift pattern from the first week N shift patterns. The same rule applies when replacing or swapping a shift pattern in the duty roster of the second week. An example of applying the moves of the repair mechanism of the SCSPA is presented in

Rather than using fixed parameter values for the HMCR and the PAR, it is recognized that the performance of any population-based method is affected by the values of its parameters, which are problem dependent. Thus, to overcome these shortcomings, several methods have been proposed to control the problem of parameter tuning. To overcome the above-addressed weaknesses in the EHSA in this research, the HMCR and PAR were updated dynamically instead of through the fixed methods used in the basic HSA [_{min} and HMCR_{max}. This facilitates more exploration. Towards the end of the search process, the value of the HMCR should be increased to facilitate more exploration. Furthermore, the value of the PAR should be as high as possible in the range of PAR_{min} and PAR_{max} at the beginning of the search process. This facilitates making higher exploration. Towards the end, these values of the PAR are decreased to facilitate exploring the candidate solutions.

The main idea in this research is to hybridize the EHSA in [

However, the stopping conditions for SA as follows: (i) when the PV of the best harmony equals zero (f (_{k}) <

The AHSA updates the values of the HMCR and the PAR parameters dynamically. SA improves the promising solutions where it optimizes the best harmony reached by the EHSA to further enhance it. To balance the processes of diversification and intensification, the best harmony is only selected to be improved using SA. This helps speed up the execution time, as SA only runs one time. The enhanced harmony is then stored again in the location of the best harmony HM [0].

The harmony annealing search (HAS) [

In the initial stage of filling the HM, the HAS uses the random mechanism, whereas the AHSA uses the SCSPA mechanism.

The HAS applied SA to improve the solutions that come from the random selection based on the probability of the HMCR, while the AHSA uses SA to improve the best solution after the EHSA reaches one of the stopping criteria.

For each instance, 20 runs were performed, and the obtained results are reported. The same experimental design is used for both the AHSA and HAS to fairly compare them. The stopping criteria are as follows: 1) 1000 iterations (based on a preliminary test), 2) PV = 0, and 3) 600 s of execution time. A 32-bit Intel laptop with 1.73 GHz, and 2 GB RAM were used to perform the experiments. The parameter values of HMCR_{min} and HMCR_{max} are 0.1 and 0.95, respectively [_{min} and PAR_{max} are 0.01 and 0.99, respectively, [

The results obtained by applying the AHSA to solve the UKMMC dataset are presented in

Instances | Best-PV | Average-PV | Worst-PV | Stddv. | Desirable patterns | Run-Time (s) |
---|---|---|---|---|---|---|

CICU | 0 | 0 | 0 | 0 | 17 | 80 |

SGY5 | 0 | 0 | 0 | 0 | 24 | 86 |

MD1 | 0 | 0 | 0 | 0 | 25 | 86 |

NICU | 17 | 19.5 | 24 | 2.21 | 65 | 154 |

N50 | 18 | 20.2 | 23 | 1.88 | 64 | 126 |

ED | 18 | 21.5 | 27 | 3.08 | 66 | 296 |

GICU | 18 | 22.1 | 28 | 2.91 | 92 | 332 |

ICU | 29 | 33.5 | 38 | 3.12 | 101 | 423 |

Based on the obtained results, AHSA was able to produce an optimal solution for small instances as produced roster didn't break any of the soft constraints. For medium and large instances, very promising results were reported. Soft constraints 1 and 2 that have the higher value didn't break.

The computational results obtained by applying the HAS algorithm to solve the UKMMC dataset are presented in

Instances | Best-PV | Average-PV | Worst-PV | Stddv. | Desirable patterns | Run-Time (s) |
---|---|---|---|---|---|---|

CICU | 111 | 116.6 | 125 | 3.34 | 7 | 600 |

SGY5 | 118 | 121.6 | 131 | 3.66 | 10 | 600 |

MD1 | 120 | 126.1 | 135 | 5.23 | 10 | 600 |

NICU | 211 | 225.6 | 245 | 9.68 | 23 | 600 |

N50 | 212 | 230.5 | 251 | 11.56 | 24 | 600 |

ED | 278 | 287.7 | 312 | 7.74 | 29 | 600 |

GICU | 314 | 328.5 | 345 | 8.92 | 33 | 600 |

ICU | 345 | 359.9 | 377 | 9.29 | 39 | 600 |

To further evaluate the performance of the AHSA, it is compared to previously published work of other HSA hybridized algorithms (EHSA, CHSA and DHSA), in addition to comparing to the results of the HAS. The results are shown in

Instances | Criteria | EHSA | CHSA | DHSA | HAS | AHSA |
---|---|---|---|---|---|---|

CICU | Average PV | 80.75 | 76 | 50.7 | 116.6 | |

Stddv. | 2.78 | 2.94 | 3.41 | 3.34 | ||

DPs | 10 | 11 | 12 | 7 | ||

Time (Sec) | 45.7 | 62.1 | 600 | 80 | ||

SGY5 | Average PV | 72.85 | 71.3 | 62.2 | 121.6 | |

Stddv. | 2.66 | 2.15 | 5.19 | 3.66 | ||

DPs | 18 | 19 | 19 | 10 | ||

Time (Sec) | 62 | 73.8 | 600 | 86 | ||

MD1 | Average PV | 86.85 | 80.9 | 67.5 | 126.1 | |

Stddv. | 2.62 | 2.42 | 4.68 | 5.23 | ||

DPs | 20 | 20 | 21 | 10 | ||

Time (Sec) | 67.8 | 72.9 | 600 | 86 | ||

NICU | Average PV | 95.55 | 88.6 | 76.1 | 225.6 | |

Stddv. | 8.178 | 4.73 | 3.95 | 9.68 | ||

DPs | 52 | 53 | 53 | 23 | ||

Time (Sec) | 110.1 | 116.9 | 600 | 154 | ||

N50 | Average PV | 135.65 | 97.7 | 85.1 | 230.5 | |

Stddv. | 10.784 | 5.81 | 3.30 | 11.56 | ||

DPs | 55 | 56 | 55 | 24 | ||

Time (Sec) | 110 | 118.2 | 600 | 126 | ||

ED | Average PV | 151.75 | 109.3 | 86.6 | 287.7 | |

Stddv. | 11.231 | 12.71 | 2.40 | 7.74 | ||

DPs | 58 | 59 | 59 | 29 | ||

Time (Sec) | 208.9 | 223.5 | 600 | 296 | ||

GICU | Average PV | 179.65 | 141.3 | 104.1 | 328.5 | |

Stddv. | 11.721 | 13.35 | 4.74 | 8.92 | ||

DPs | 75 | 75 | 75 | 33 | ||

Time (Sec) | 243.2 | 287.4 | 600 | 332 | ||

ICU | Average PV | 280.45 | 249.7 | 123.8 | 359.9 | |

Stddv. | 12.151 | 13.12 | 11.19 | 9.29 | ||

DPs | 85 | 86 | 86 | 39 | ||

Time (Sec) | 378.5 | 398.2 | 600 | 423 |

The average PVs, Stddv. of PVs and the DPs in addition to the computational time of each compared algorithm are used in this comparison. The results in bold show the best-obtained results.

Based on the results in

The obtained results in

In this paper, a novel hybridization between EHSA and SA is introduced. The AHSA is applied to solve a real-world dataset collected from UKMMC Malaysia. AHSA was employed to construct ideal duty rosters with minimum PVs and the maximum number of DPs, taking into consideration all of the associated constraints. The AHSA is then compared to the EHSA alone, the CHSA, and the DHSA algorithms to demonstrate its performance. The results showed that the AHSA yields the best results. It is observed that the success of the AHSA is because of the ability to maintain the balance between diversification and intensification in the solution search pool, in addition to the strong mechanism of SA in escaping local optima. Moreover, the comparison between the AHSA and the HAS (both use SA to enhance the constructed solution but in different stages) showed that the AHSA performed extremely better than the HAS in all UKMMC instances for all comparison criteria. This is due to the premature convergence that occurred for the population of the solutions in the HM caused by running the SA several times in the HAS.

For future work, it is highly recommended to hybridize the EHSA with enhanced variants of SA, which might further enhance the mechanism of the HSA and help construct high-quality rosters for nurses.

The researcher would like to thank the Deanship of Scientific Research, Qassim University for funding the publication of this project.