
Research Article


Enhanced Harmony Search Algorithm for Nurse Rostering Problems 

Masri Ayob,
Mohammed Hadwan,
Mohd. Zakree Ahmad Nazri
and
Zulkifli Ahmad



ABSTRACT

Drawing up the nurses’
duty roster is one of the main key issues that are faced by hospital managements,
this study focuses on Nurse Rostering Problem (NRP), an NPhard problem, that
is difficult to solve for optimality. Harmony Search Algorithm (HSA) refers
to the metaheuristic algorithm inspired by the improvisation of Jazz musicians.
Due to the problem of slow convergence of the basic HSA, this study attempted
to enhance basic HSA (called EHSA). This is done by using a semi cyclic shift
patterns in the initialization step to generate the initial harmonies (population)
rather than using a fully random mechanism in basic HSA. Furthermore, a dynamic
mechanism was employed in EHSA to update the parameter values of harmony memory
considering rate and pitch adjusting rate instead of fixed values in basic HSA.
A real world dataset from large hospital in Malaysia was used to evaluate the
performance of EHSA. Results showed that EHSA can produce high quality rosters
in shorter execution time compared to basic HSA. A comparison between EHSA and
Adaptive Harmony Search (AHS) is also presented to demonstrate the performance
of the proposed method. Better results have been obtained by EHSA compared to
AHS.





Received: March 20, 2013;
Accepted: May 29, 2013;
Published: July 19, 2013


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 NPhard 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 fullyconstrained problem and some researchers
considered it to be an overconstrained problem (Thornton
and Sattar, 1997; Bilgin et al., 2012).
A wide range of realworld 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 NPhard 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 metaheuristic 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) metaheuristics can be defined
as upper level general methodologies which used as guiding strategies in designing
underlying heuristics to tackle optimization problems. Metaheuristic 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 populationbased 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 metaheuristic 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 metaheuristic 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 (AlBetar
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 lowdiscrepancy 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, offday
followed by workingday 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 semicyclic 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 pseudocode
of building the HM with the modification of using a semicyclic 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 pseudocode 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 pseudocode of building the HM using SCSPA 

Fig. 2: 
The pseudo code of improvisation step in EHSA 
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 boxandwhiskers 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: 
Boxandwhiskers plot for the results (out of 20 runs) based
on penalty values (yaxis) obtained by EHSA on UKMMC dataset (xaxis) 

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 searchbased 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).

REFERENCES 
1: AlBetar, M.A. and A.T. Khader, 2012. A harmony search algorithm for university course timetabling. Ann. Operat. Res., 194: 331. CrossRef  Direct Link 
2: Aickelin, U. and K.A. Dowsland, 2004. An indirect genetic algorithm for a nursescheduling problem. Comput. Oper. Res., 31: 761778. Direct Link 
3: Aickelin, U., E.K. Burke and J. Li, 2009. An evolutionary squeaky wheel optimization approach to personnel scheduling. IEEE Trans. Evol. Comput., 13: 433443. CrossRef  Direct Link 
4: Barzegari, M., S.M.T. Bathaee and M. Alizadeh, 2010. Optimal coordination of directional overcurrent relays using harmony search algorithm. Proceedings of the 9th International Conference on Environment and Electrical Engineering, May 1619, 2010, Prague, Czech Republic, pp: 321324
5: Bilgin, B., P. De Causmaecker, B. Rossie and G. Vanden Berghe, 2012. Local search neighbourhoods for dealing with a novel nurse rostering model. Ann. Oper. Res., 194: 3357. Direct Link 
6: Blum, C., M.J.B. Aguilera, A. Roli and M. Samples, 2008. Hybrid Metaheuristics: An Emerging Approach to Optimization. Vol. 114, Springer, Heidelberg, Germany
7: Blum, C., J. Puchinger, G.R. Raidl and A. Roli, 2011. Hybrid metaheuristics in combinatorial optimization: A survey. Applied Soft Comput., 11: 41354151. CrossRef 
8: Burke, E.K., P. De Causmaecker, G.V. Berghe and H. Van Landeghem, 2004. The state of the art of nurse rostering. J. Scheduling, 7: 441499. CrossRef  Direct Link 
9: Burke, E.K., T. Curtois, R. Qu and G.V. Berghe, 2010. A scatter search methodology for the nurse rostering problem. J. Oper. Res. Soc., 61: 16671679. CrossRef  Direct Link 
10: Cheang, B., H. Li, A. Lim and B. Rodrigues, 2003. Nurse rostering problems: A bibliographic survey. Eur. J. Oper. Res., 151: 447460. CrossRef  Direct Link 
11: Coelho, L.D.S. and V.C. Mariani, 2009. An improved harmony search algorithm for power economic load dispatch. Energy Convers. Manage., 50: 25222526. CrossRef  Direct Link 
12: Degertekin, S.O., 2008. Optimum design of steel frames using harmony search algorithm. Struct. Multidi. Optim., 36: 393401. Direct Link 
13: Geem, Z.W., J.H. Kim and G.V. Loganathan, 2001. A new heuristic optimization algorithm: Harmony search. Simulation, 76: 6068. CrossRef  Direct Link 
14: Geem, Z.W., K.S. Lee and Y. Park, 2005. Application of harmony search to vehicle routing. Am. J. Applied Sci., 2: 15521557. Direct Link 
15: Geem, Z.W., 2010. Multiobjective optimization of timecost tradeoff using harmony search. J. Constr. Eng. Manage., 136: 711716. CrossRef  Direct Link 
16: Glass, C.A. and R.A. Knight, 2009. The nurse rostering problem: A critical appraisal of the problem structure. Eur. J. Oper. Res., 202: 379389. CrossRef  Direct Link 
17: Hadwan, M. and M.B. Ayob, 2009. An exploration study of nurse rostering practice at hospital Universiti Kebangsaan Malaysia. Proceedings of the 2nd Conference on Data Mining and Optimization, October 2728, 2009, Bangi, Selangor, Malaysia, pp: 100107 CrossRef  Direct Link 
18: Hadwan, M. and M. Ayob, 2011. A semicyclic shift patterns approach for nurse rostering problems. Proceedings of the 3rd Conference on Data Mining and Optimization, June 2829, 2011, Putrajaya, Malaysia, pp: 184189
19: Hadwan, M., M. Ayob, N.R. Sabar and R. Qu, 2013. A harmony search algorithm for nurse rostering problems. Inform. Sci., 233: 126140. CrossRef  Direct Link 
20: Ingram, G. and T. Zhang, 2009. Overview of Applications and Developments in the Harmony Search Algorithm. In: MusicInspired Harmony Search Algorithm, Geem, Z.W. (Ed.). Springer, Berlin/Heidelberg, pp: 1537
21: Lee, K.S. and Z.W. Geem, 2004. A new structural optimization method based on the harmony search algorithm. Comput. Struct., 82: 781798. CrossRef 
22: Gutjahr, W.J. and M.S. Rauner, 2007. An ACO algorithm for a dynamic regional nursescheduling problem in Austria. J. Comput. Oper. Res., 34: 642666. CrossRef 
23: Hasancebi, O., F. Erdal and M.P. Saka, 2010. An adaptive harmony search method for structural optimization. J. Struct. Eng., 136: 419431. CrossRef 
24: Lee, K. and Z. Geem, 2005. A new metaheuristic algorithm for continuous engineering optimization: harmony search theory and practice. Comput. Methods Applied Mechanics Eng., 194: 39023933.
25: Mahdavi, M., M. Fesanghari and E. Damangir, 2007. An improved harmony search algorithm for solving optimization problems. Applied Math. Comput., 188: 15671579. CrossRef 
26: Omran, M.G. and M. Mahdavi, 2008. Globalbest harmony search. Applied Math. Comput., 198: 643656.
27: Qu, R., E.K. Burke, B. McCollum, L.T. Merlot and S.Y. Lee, 2009. A survey of search methodologies and automated system development for examination timetabling. J. Schedul., 12: 5589. Direct Link 
28: Saka, M. and O. Hasancebi, 2009. Adaptive Harmony Search Algorithm for Design Code Optimization of Steel Structures. In: Harmony Search Algorithms for Structural Design Optimization, Geem, Z. (Ed.). Vol. 239, Springer, Berlin, Heidelberg, pp: 79120
29: Talbi, E.G., 2009. Metaheuristics: From Design to Implementation. John Wiley and Sons, USA., ISBN: 9780470496909, Pages: 500
30: Thornton, J.R. and A. Sattar, 1997. Applied partial constraint satisfaction using weighted iterative repair. Proceedings of the 10th Australian Joint Conference on Artificial Intelligence: Advanced Topics in Artificial Intelligence, November 30December 4, 1997, Australia, pp: 5766
31: Wang, C.M. and Y.F. Huang, 2010. Selfadaptive harmony search algorithm for optimization. Expert Syst. Appli., 37: 28262837. CrossRef  Direct Link 



