A hybrid evolutionary approach to the nurse rostering problem
Nurse rostering is an important search problem with many constraints. In the literature, a number of approaches have been investigated including penalty function methods to tackle these constraints within genetic algorithm frameworks. In this paper, we investigate an extension of a previously propos...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/47488/ |
| _version_ | 1848797559363993600 |
|---|---|
| author | Bai, Ruibin Burke, Edmund K. Kendall, Graham Li, Jingpeng McCollum, Barry |
| author_facet | Bai, Ruibin Burke, Edmund K. Kendall, Graham Li, Jingpeng McCollum, Barry |
| author_sort | Bai, Ruibin |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | Nurse rostering is an important search problem with many constraints. In the literature, a number of approaches have been investigated including penalty function methods to tackle these constraints within genetic algorithm frameworks. In this paper, we investigate an extension of a previously proposed stochastic ranking method, which has demonstrated superior performance to other constraint handling techniques when tested against a set of constrained optimization benchmark problems. An initial experiment on nurse rostering problems demonstrates that the stochastic ranking method is better at finding feasible solutions, but fails to obtain good results with regard to the objective function. To improve the performance of the algorithm, we hybridize it with a recently proposed simulated annealing hyper-heuristic (SAHH) within a local search and genetic algorithm framework. Computational results show that the hybrid algorithm performs better than both the genetic algorithm with stochastic ranking and the SAHH alone. The hybrid algorithm also outperforms the methods in the literature which have the previously best known results. |
| first_indexed | 2025-11-14T20:05:48Z |
| format | Article |
| id | nottingham-47488 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T20:05:48Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-474882020-05-04T16:29:32Z https://eprints.nottingham.ac.uk/47488/ A hybrid evolutionary approach to the nurse rostering problem Bai, Ruibin Burke, Edmund K. Kendall, Graham Li, Jingpeng McCollum, Barry Nurse rostering is an important search problem with many constraints. In the literature, a number of approaches have been investigated including penalty function methods to tackle these constraints within genetic algorithm frameworks. In this paper, we investigate an extension of a previously proposed stochastic ranking method, which has demonstrated superior performance to other constraint handling techniques when tested against a set of constrained optimization benchmark problems. An initial experiment on nurse rostering problems demonstrates that the stochastic ranking method is better at finding feasible solutions, but fails to obtain good results with regard to the objective function. To improve the performance of the algorithm, we hybridize it with a recently proposed simulated annealing hyper-heuristic (SAHH) within a local search and genetic algorithm framework. Computational results show that the hybrid algorithm performs better than both the genetic algorithm with stochastic ranking and the SAHH alone. The hybrid algorithm also outperforms the methods in the literature which have the previously best known results. Institute of Electrical and Electronics Engineers 2010-08-31 Article PeerReviewed Bai, Ruibin, Burke, Edmund K., Kendall, Graham, Li, Jingpeng and McCollum, Barry (2010) A hybrid evolutionary approach to the nurse rostering problem. IEEE Transactions on Evolutionary Computation, 14 (4). pp. 580-590. ISSN 1089-778X Constrained optimization; constraint handling; evolutionary algorithm; local search; nurse rostering; simulated annealing hyper-heuristics https://doi.org/10.1109/tevc.2009.2033583 doi:10.1109/tevc.2009.2033583 doi:10.1109/tevc.2009.2033583 |
| spellingShingle | Constrained optimization; constraint handling; evolutionary algorithm; local search; nurse rostering; simulated annealing hyper-heuristics Bai, Ruibin Burke, Edmund K. Kendall, Graham Li, Jingpeng McCollum, Barry A hybrid evolutionary approach to the nurse rostering problem |
| title | A hybrid evolutionary approach to the nurse rostering problem |
| title_full | A hybrid evolutionary approach to the nurse rostering problem |
| title_fullStr | A hybrid evolutionary approach to the nurse rostering problem |
| title_full_unstemmed | A hybrid evolutionary approach to the nurse rostering problem |
| title_short | A hybrid evolutionary approach to the nurse rostering problem |
| title_sort | hybrid evolutionary approach to the nurse rostering problem |
| topic | Constrained optimization; constraint handling; evolutionary algorithm; local search; nurse rostering; simulated annealing hyper-heuristics |
| url | https://eprints.nottingham.ac.uk/47488/ https://eprints.nottingham.ac.uk/47488/ https://eprints.nottingham.ac.uk/47488/ |