A heuristic algorithm based on multiassignment procedures for nurse scheduling
This paper tackles a Nurse Scheduling Problem which consists of generating work schedules for a set of nurses while considering their shift preferences and other requirements. The objective is to maximize the satisfaction of nurses? preferences and minimize the violation of soft constraints. This pa...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Published: |
Springer
2014
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/31328/ |
| _version_ | 1848794178096463872 |
|---|---|
| author | Constantino, Ademir Aparecido Landa-Silva, Dario de Melo, Everton Luiz de Mendonza, Candido Ferreira Xavier Rizzato, Douglas Baroni Romao, Wesley |
| author_facet | Constantino, Ademir Aparecido Landa-Silva, Dario de Melo, Everton Luiz de Mendonza, Candido Ferreira Xavier Rizzato, Douglas Baroni Romao, Wesley |
| author_sort | Constantino, Ademir Aparecido |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | This paper tackles a Nurse Scheduling Problem which consists of generating work schedules for a set of nurses while considering their shift preferences and other requirements. The objective is to maximize the satisfaction of nurses? preferences and minimize the violation of soft constraints. This paper presents a new deterministic heuristic algorithm, called MAPA (multi-assignment problem-based algorithm), which is based on successive resolutions of the assignment problem. The algorithm has two phases: a constructive phase and an improvement phase. The constructive phase builds a full schedule by solving successive assignment problems, one for each day in the planning period. The improvement phase uses a couple of procedures that re-solve assignment problems to produce a better schedule. Given the deterministic nature of this algorithm, the same schedule is obtained each time that the algorithm is applied to the same problem instance. The performance of MAPA is benchmarked against published results for almost 250,000 instances from the NSPLib dataset. In most cases, particularly on large instances of the problem, the results produced by MAPA are better when compared to best-known solutions from the literature. The experiments reported here also show that the MAPA algorithm finds more feasible solutions compared with other algorithms in the literature, which suggest that this proposed approach is effective and robust. |
| first_indexed | 2025-11-14T19:12:03Z |
| format | Article |
| id | nottingham-31328 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:12:03Z |
| publishDate | 2014 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-313282020-05-04T20:13:53Z https://eprints.nottingham.ac.uk/31328/ A heuristic algorithm based on multiassignment procedures for nurse scheduling Constantino, Ademir Aparecido Landa-Silva, Dario de Melo, Everton Luiz de Mendonza, Candido Ferreira Xavier Rizzato, Douglas Baroni Romao, Wesley This paper tackles a Nurse Scheduling Problem which consists of generating work schedules for a set of nurses while considering their shift preferences and other requirements. The objective is to maximize the satisfaction of nurses? preferences and minimize the violation of soft constraints. This paper presents a new deterministic heuristic algorithm, called MAPA (multi-assignment problem-based algorithm), which is based on successive resolutions of the assignment problem. The algorithm has two phases: a constructive phase and an improvement phase. The constructive phase builds a full schedule by solving successive assignment problems, one for each day in the planning period. The improvement phase uses a couple of procedures that re-solve assignment problems to produce a better schedule. Given the deterministic nature of this algorithm, the same schedule is obtained each time that the algorithm is applied to the same problem instance. The performance of MAPA is benchmarked against published results for almost 250,000 instances from the NSPLib dataset. In most cases, particularly on large instances of the problem, the results produced by MAPA are better when compared to best-known solutions from the literature. The experiments reported here also show that the MAPA algorithm finds more feasible solutions compared with other algorithms in the literature, which suggest that this proposed approach is effective and robust. Springer 2014-07 Article PeerReviewed Constantino, Ademir Aparecido, Landa-Silva, Dario, de Melo, Everton Luiz, de Mendonza, Candido Ferreira Xavier, Rizzato, Douglas Baroni and Romao, Wesley (2014) A heuristic algorithm based on multiassignment procedures for nurse scheduling. Annals of Operations Research, 218 (1). pp. 165-183. ISSN 1572-9338 nurse scheduling personnel scheduling assignment problem heuristics metaheuristics http://link.springer.com/article/10.1007/s10479-013-1357-9 doi:10.1007/s10479-013-1357-9 doi:10.1007/s10479-013-1357-9 |
| spellingShingle | nurse scheduling personnel scheduling assignment problem heuristics metaheuristics Constantino, Ademir Aparecido Landa-Silva, Dario de Melo, Everton Luiz de Mendonza, Candido Ferreira Xavier Rizzato, Douglas Baroni Romao, Wesley A heuristic algorithm based on multiassignment procedures for nurse scheduling |
| title | A heuristic algorithm based on multiassignment procedures for nurse scheduling |
| title_full | A heuristic algorithm based on multiassignment procedures for nurse scheduling |
| title_fullStr | A heuristic algorithm based on multiassignment procedures for nurse scheduling |
| title_full_unstemmed | A heuristic algorithm based on multiassignment procedures for nurse scheduling |
| title_short | A heuristic algorithm based on multiassignment procedures for nurse scheduling |
| title_sort | heuristic algorithm based on multiassignment procedures for nurse scheduling |
| topic | nurse scheduling personnel scheduling assignment problem heuristics metaheuristics |
| url | https://eprints.nottingham.ac.uk/31328/ https://eprints.nottingham.ac.uk/31328/ https://eprints.nottingham.ac.uk/31328/ |