Enhanced Harmony Search Algorithm for Nurse Rostering Problems

INTRODUCTION

Within the area of healthcare there is a worldwide shortage in nursing personals; a phenomenon known as the “crisis in nursing”. High workloads, inflexible schedules and unfair distribution of duty shift slots are among the key issues that cause nurses’ job dissatisfaction. This dissatisfaction has a negative impact on the personal life of the staff nurses resulting in high turnover and low rate of nursing recruitment (Burke et al., 2004). Consequently, the overall quality of patient care is badly affected. Nurse Rostering Problem (NRP) is an NP-hard combinatorial optimization problems. It involves the task to assign nurses to be on duty shifts for specific period of time, specifying the days on and off duty for each nurse (Glass and Knight, 2009). The constraints that accompany NRPs are divided into types known as hard and soft constraints. Hard constraints represent the mandatory rules and regulations that must be fulfilled. Whereas soft constraints can be violated (if necessary) and are used to evaluate the quality of the generated roster. That is, the more soft constraints are satisfied, the better the quality of the roster. Though it does not promise reaching the optimal solution, approximation approaches are widely adopted to solve NRP.

The NRPs are well known to be a fully-constrained problem and some researchers considered it to be an over-constrained problem (Thornton and Sattar, 1997; Bilgin et al., 2012). A wide range of real-world NRPs have been introduced by many researchers in the literature of timetabling (Burke et al., 2004). Complex NRPs are considered to be among of the NP-hard problems (Burke et al., 2004). The difficulty of NRPs is because of the wide range of the associated hard constraints and soft constraints that sometimes conflicting with each other (Burke et al., 2004; Cheang et al., 2003). Many meta-heuristic approaches have been used to tackle NRP (in general) due to its ability to cope with various constraints and can generate good solutions in a reasonable execution time. Example of these approaches are genetic algorithms (Aickelin and Dowsland, 2004), scatter search algorithm (Burke et al., 2010), ant colony optimization (Gutjahr and Rauner, 2007) and improved squeaky wheel optimization (Aickelin et al., 2009).

According to Talbi (2009) meta-heuristics can be defined as upper level general methodologies which used as guiding strategies in designing underlying heuristics to tackle optimization problems. Meta-heuristic approaches are generally categorized into two main methods. The first one is local search methods which are very fast in finding better quality solutions but only in local region where it starts the searching without global view of other solutions in the search space (Blum et al., 2008). The second one is population-based methods, which are better in identifying the location of good solutions by exploring and capturing a global picture of the search space. However, they are usually not efficient in exploiting the desired solutions in the search space as they focus more in exploration (Blum et al., 2008). Therefore, the hybridization between population methods and local search methods to create a right balance between exploration and exploitation is highly recommended (Talbi, 2009; Blum et al., 2011). In most respects, these characteristics are found in a new algorithm called Harmony Search Algorithm (HSA) which is a population based method that has some components of local search methods.

HSA is a meta-heuristic algorithm inspired by the improvisation of Jazz musicians (Geem et al., 2001). In music performance, each musical player plays one musical note each time and those musical notes combine together to form a harmony. In the optimization process, each variable has a value at each time and those values all together form a solution vector (Ingram and Zhang, 2009). HSA uses stochastic random search that depends on the Harmony Memory Considering Rate (HMCR) and Pitch Adjusting Rate (PAR). HSA combines different characteristics of existing meta-heuristic algorithms. By using the harmony memory, HSA is similar to tabu search algorithm in the ability of preserving the history of previous vectors. Further, it is similar to genetic algorithm in the ability of managing several solution vectors simultaneously. The dynamic change of the parameters of HSA during the run acts is similar to simulated annealing algorithm (Lee and Geem, 2004).

HSA has proved its ability to solve many difficult optimization problems (Ingram and Zhang, 2009) such as university course timetabling (Al-Betar and Khader, 2010), vehicle routing (Geem et al., 2005) and other optimization problems (Ingram and Zhang, 2009). However, the problem of slow convergence has been noticed in most of the existing works. Thus, the improvement of the basic HSA has attracted many researchers. Among the earlier studies that attempted to enhance the performance of basic HSA is performed by Mahdavi et al. (2007), which proposed to use a dynamic mechanism to change the parameter values of PAR and the Bandwidth (BW) instead of using a fixed PAR and BW. The proposed algorithm is called Improved Harmony Search (IHS) and it is inspired by many of the following variants of HSA Mahdavi et al. (2007). Another modification to HSA is done by Omran and Mahdavi (2008), where they have developed another variant of HSA called Global best Harmony Search (GHS) inspired by the idea of swarm intelligence. The GHS differs from IHS in the step of improvisation where they modified the pitch adjustment rule as follows: improvising new solution is affected by the best harmony in the harmony memory instead of moving to the neighbor of current value. The BW is removed in GHS (Omran and Mahdavi, 2008). In study of Coelho and Mariani (2009) another HSA variant that included the grade of the solution vectors is reported. Most of the proposed modification in the state of the art of HSA was directed to enhance the improvisation step. Another essential modification to the improvisation step were introduced by Saka and Hasancebi (2009) and Hasancebi et al. (2010) to change the parameter values of HMCR and PAR instead of changing the values of PAR and BW during the algorithm running. Less attention has been paid to improve the initialization step where the initial harmonies generated and filled up randomly. Few attempts were reported to improve the step of initializing the harmony memory. In Degertekin (2008) modified HM initialization step by generating solution vectors twice as the HMS then filling up the HM with the best solution vectors. Wang and Huang (2010) made another attempted of using low-discrepancy sequences instead of random mechanism.

Thus, for the purpose of enhancing HSA convergence, this work proposes a new method for generating the initial harmonies (population of solutions) for NRP. In particular, we use a semi cyclic shift patterns in the initialization step to generate the initial harmonies (population) rather than using a fully random mechanism of basic HSA. The goal of this work is to investigate the effect of using different initialization method for HSA when solving NRP. To do this, we tested the proposed algorithm on a real world dataset obtained from a large hospital in Malaysia. Experimental results show that our proposed HSA produces better quality rosters for all considered instances than a basic HSA.

UNIVERSITI KEBANGSAAN MALAYSIA MEDICAL CENTRE (UKMMC)

Universiti Kebangsaan Malaysia Medical Center (UKMMC) is an educational hospital that belongs to National University Malaysia (UKM) working around the clock to provide its services for the public. The hospital has a workforce exceeding 1400 nurses attending more than 900 beds for 24 h a day and 7 days a week. For more details about the NRP of UKMMC refer to (Hadwan and Ayob, 2009, 2011; Hadwan et al., 2013).

Hard and soft constraints: Based on the abstraction of the information gathered from the interviews, observations and questionnaires at UKMMC, the problem we are dealing with has the following constraints:

UKMMC Hard constraints: Based on the abstraction of gathered data, we have the following hard constraints:

For the UKMMC NRP, we have identified the following hard constraints:

•	HC1: The coverage demand for each shift must be fulfilled. Understaffing is not allowed
•	HC2: All nurses work one shift per day at most
•	HC3: One senior nurse must be allocated for every shift
•	HC4: An isolated working day is prohibited. For instance, off-day followed by working-day then followed by off day
•	HC5: For each fourteen days, the maximum working days are 12 days whilst the minimum are 10 days
•	HC6: Each nurse works no more than 4 consecutive working days
•	HC7: Night shift must be in the form of 4 consecutive night shifts followed by two days off

UKMMC soft constraints: Based on the analysis of the gathered data, there is a group of soft constraints which can be listed as follows:

•	SC1: Attempts to allocate equal number of working days and days off to all nurses during the roster’s period
•	SC2: Attempts to allocate at least one day off in the weekend during the rostering period
•	SC3: For the overall roster, try to allocate more morning and evening shifts than night shifts
•	SC4: Attempts to allocate patterns of 4 consecutive morning shifts followed by one day off
•	SC5: Attempts to allocate patterns of 4 consecutive evening shifts followed by one day off
•	SC6: Attempt to give either a day off or evening shift after the two days off that follow night shift pattern (NNNNxxE) or (NNNNxxx)
•	SC7: Attempts to give at least 12 h rest for the nurses before starting new shift. This would try not to give evening shift followed by morning (EM)

Based on the discussion with the head nurses at UKMMC, we found that (S1) and (S2) are more important than the others. Each soft constraint is associated with a particular weight. Normally, the higher weight indicates the main importance of satisfying the constraints. Refer to Table 1 for the weight of each soft constraint.

Coverage demand: The coverage demand is the most important constraint that must be satisfied. This constraint indicates the minimum required number of nurses and the needed skills combinations for each shift and day (Table 2). For example (Table 2), for CICU instance, the total number of nurses is 11 with 8 senior nurses and the coverage demand for weekdays (morning, evening, night) and weekend (morning, evening, night) are (3, 3, 2) and (2, 2, 2), respectively.

Table 1:	The weight of soft constraints for each violation of the constraint

Table 2:	The minimum coverage demand for UKMMC dataset

We deal with coverage demand as a hard constraint that cannot be violated at any time.

ENHANCED HARMONY SEARCH ALGORITHM FOR NRPS

Enhanced Harmony Search Algorithm (EHSA) is a HSA variant that employed the idea of semi-cyclic shift patterns approach that proposed by Hadwan and Ayob (2011) to construct the feasible shift patterns rather than filling up the harmony memory randomly. Also the idea of updating the HMCR and PAR dynamically is used rather than using fixed HMCR and PAR (Hasancebi et al., 2010). In the initialization step of basic HSA, the candidate solutions are filled up randomly to the HM (Geem et al., 2001; Lee and Geem, 2005; Geem, 2010). The procedure of basic HSA has five: Step 1. Initialize the HSA parameters and the optimized problem, Step 2. Build the Harmony Memory (HM), Step 3. Improvise new solution, Step 4. Update the HM, and Step 5. Repeat step 4 and 5 until reach one of the stopping criterion. Figure 1 presents the pseudo-code of building the HM with the modification of using a semi-cyclic shift pattern approach instead of the fully random mechanism of Basic HSA. However, the remaining steps were kept the same as basic HSA.

Figure 2 presents the pseudo-code of improvisation step where we used dynamic HMCR and PAR. In this modification, the parameter values of HMCR and PAR keep changed during the run based on the Eq. 1 and 2.


Fig. 1:	The pseudo-code of building the HM using SCSPA


Fig. 2:	The pseudo code of improvisation step in EHSA

(1)

(2)

where, HMCR(gn) and PAR(gn) are the HMCR and PAR in generation g, respectively; NI is the maximum number of iterations and g is the current number of iterations; HMCR_min and HMCR_max are the minimum and the maximum of HMCR values respectively; PAR_min and PAR_max are the minimum and the maximum PAR values, respectively.

COMPUTATIONAL EXPERIMENTS AND RESULTS

Here, we report the results of applying the basic HSA (Geem et al., 2001) that implemented herein and the EHSA. The main goal of the following experiments is to measure the improvement of the convergence of the EHSA compared to the BHSA. The same experiments resources used to test the BHSA and EHSA. Table 3 shows the used parameter values of BHSA and EHSA. For BHSA, we experimentally identify the used parameter values in Table 3. For EHSA, the parameter values of HMCR_min and HMCR_max we followed Barzegari et al. (2010) and for PARmin and PARmax we followed the parameter values of Omran and Mahdavi (2008). For the HMS, BW and NI, we used the same parameter setting as in BHSA. We have used the UKMMC dataset to test EHSA and AHS.

Comparing the results of BHSA and EHSA: This section presents a comparison between the results obtained by applying the BHSA and the EHSA using the same problem instances and parameter values in Table 3. In Table 4, the average, the median, the Standard Deviation (Stddv.), the number of Desirable Patterns (DPs) and the execution time are used in the comparison. Based on the results presented in Table 4, the EHSA outperforms the BHSA in all the instances. EHSA produced better results compared with BHSA in terms of lower penalty values, number of Dps and execution time (highlighted in bold font in Table 4). For example, for CICU instance, the average penalty value obtained by EHSA is better than BHSA (i.e., 72.1 and 316.5, for EHSA and BHSA, respectively). This is attributed to the proposed changes to the way of building the initial HM and the use of the dynamic HMCR and PAR rather than using fixed values for these operators.

Figure 3 shows the box-and-whiskers plot for results (out of 20 runs) based on solution quality (i.e., penalty value, where the lower value is better) obtained by EHSA tested on UKMMC datasets. It shows that in most instances (five out of eight), most of the solutions (i.e., the median value) are closer (in term of quality of solution) to the best solutions.

Table 3:	The parameter values used in BHSA and EHSA

Table 4:	Comparison results (out of 20 runs): EHSA and BHSA on UKMMC dataset

Table 5:	Comparison results (out of 20 runs): EHSA and AHS on UKMMC dataset


Fig. 3:	Box-and-whiskers plot for the results (out of 20 runs) based on penalty values (y-axis) obtained by EHSA on UKMMC dataset (x-axis)


Fig. 4:	The solution landscape (based on solution quality versus number of iteration) for CICU instance using BHSA and EHSA


Fig. 5:	The pseudo code of building the HM step in AHS

Figure 4 shows the solution landscape of the BHSA and the EHSA when solving CICU for instance. Where, the EHSA needs a lower number of iterations to develop the candidate solutions and could reach to lower penalty values after 10000 iterations. In contrast, the BHSA needs about 30000 iterations to reach closer to the penalty values obtained by the EHSA after being run for 10000 iterations. As the execution time is concerned, there is no remarkable difference between the BHSA and the EHSA. However, it is noticed that the EHSA was faster in all computational experiments.

A comparison between EHSA and AHS: Adaptive Harmony Search (AHS) is one of the new variants of the HSA proposed by Hasancebi et al. (2010). The main reason of comparing the EHSA with the AHS is that we used the same idea of updating the values of the HMCR and the PAR of both algorithms. However, the only point of difference is that the AHS uses a random mechanism in initializing the HM whilst we use the SCSPA mechanism in the EHSA. The same experiments design and parameter values as in Table 3 are used for both algorithms in order to make a fair comparison.


Fig. 6:	The pseudo code of improvisation step in AHS

Figure 5 and 6 present the pseudo code of building the HM and the improvisation of a new harmony, respectively.

Table 5 presents a comparison between the results of the EHSA and the AHS. Based on the results shown in Table 5, the EHSA outperforms the AHS in all the evaluation criteria. For example, for CICU instance, the average penalty value obtained by EHSA is better than AHS (i.e., 72.1 and 128.5, for EHSA and BHSA, respectively). This is attributed to the control of the randomness that we gain by using the SCSPA rather than the fully random manner that the AHS. Initializing the HM using the SCSPA helps in generating harmonies (population) with no violations of the constraints concerning the night shift patterns. Doing that, we have solved the most problematic part of the UKMMC dataset during the initialization step. This supports our assumption that using the SCSPA will reduce the violations of the night shift constraints and help the EHSA to start developing candidate solutions with a good quality (less penalty values).

CONCLUSION

This study has introduced the Enhanced Harmony Search Algorithm (EHSA) in which two modifications are employed in building the initial populations and controlling the main parameters of the improvisation step. We studied the behavior of the EHSA during the run in order to observe and compare its convergence with the BHSA. Then, we compared the EHSA and the BHSA in order to show the ability of the EHSA in overcoming the drawbacks of the BHSA in all the instances of UKMMC dataset. Another comparison that was conducted between the EHSA and the AHS shows that the EHSA outperform the AHS due to the poor initial populations that random mechanism generates using the AHS. In the future study, the attempt will be made to answer the following question “can the performance of the EHSA be further improved if we hybridize it with other local search algorithms?”. It is highly recommended by many researchers such as Talbi (2009), Blum et al. (2011) and Qu et al. (2009) to investigate the hybridization of population based and local search-based algorithms.

ACKNOWLEDGMENTS

The authors wish to thank Ministry of Higher Education for supporting this work under the FRGS Research Grant Scheme (FRGS/1/2012/SG05/UKM/02/11).