Research Review: Optimization methods based on Harmony Search Algorithm for Nurse Rostering Problems

 

Research Review: Optimization methods based on Harmony Search Algorithm for Nurse Rostering Problems
2013-06-27
Time 1500 until 1600
Viva Room 7th Floor
Mr. Mohammed A. M. Awadallah
Prof. Ahamad Tajudin Khader
Dr. Mohammed Azmi Al-Betar
This thesis presents an optimization methods based on Harmony Search Algorithm (i.e. HSA) for Nurse Rostering Problems (i.e. NRP) using a dataset published in the first International Nurse Rostering Competition (INRC2010). The NRP is a combinatorial optimization problem that is tackled by assigning a set of nurses with different skills and contracts to different types of shifts, over a predefined rostering period. In practice, the NRP is subject to two types of constraints: hard and soft. Hard constraints must be satisfied, while the violations of the soft constraints are allowed but should be avoided, if possible. The HSA is a population-based metaheuristic method which mimics the improvisation process; it has been successfully applied to a wide range of optimization problems, yet not explored for NRP. The original HSA iteratively improvises the new solution using three operators: memory consideration, random consideration, and pitch adjustment. The initial exploration of applying the HSA to NRP is one of the main objectives of this thesis. This method is called Basic HSA (i.e. BHSA) for NRP. Although it reveals practical results, some possible improvement regarding to the HSA operators with relation to NRP search space complexity are diagnosis and addressed sequentially. The first improvement is on memory consideration where it is modified to speed up the convergence by replacing the original random selection of memory consideration with a set of selection method inspired from the other evolutionary techniques such as tournament, proportional, and liner rank derived from Genetic Algorithm, and global-best derived from Particle Swarm Optimization. The yielded method from the first improvement is called Modified Memory consideration of HSA (i.e. MMHSA). The second improvement which complements the first is done into the pitch adjustment operator where it is modified to be invoked after the improvisation process is completed rather than in the process of construction the new solution. This modification is useful to consider some of the soft constraints that cannot be controlled during the construction process. Restate, the violations of some soft constraints can be avoided when a complete roster is constructed rather than in the process of construction partial roster. The yielded method from the second improvement is called Modified Pitch adjustment of HSA (i.e. MPHSA). The third improvement removes the pitch adjustment and implements the hill climbing optimizer instead of pitch adjustment. This is to empower the exploitation capability of the MPHSA. This method is called Hybrid HSA (i.e. HHSA). In conclusion, the harmony search-based methods (i.e., BHSA, MMHSA, MPHSA, and HHSA) outperform the other competitive methods in five instances and obtained the best published results in 33 others out of 69 instances of INRC2010 dataset.
N/A
none
2012/13
2
N/A