Nurse Rostering: A Tabu Search Technique With Embedded Nurse Preferences

Nurse Rostering: A Tabu Search Technique With Embedded Nurse Preferences

The decision making in assigning all nursing staffs to shift duties in a hospital unit must be done appropriately because it is a crucial task due to various requirements and constraints that need to be fulfilled. The shift assignment or also known as roster has a great impact on the nurses’ operati...

Full description

Saved in:
Bibliographic Details
Main Author: Siti Nurin Ima, Ahmad
Format: Thesis
Language:eng
eng
Published: 2010
Subjects:
HD28-70 Management
Industrial Management
Online Access:https://etd.uum.edu.my/2804/1/Siti_Nurin_Ima_Ahmad.pdf
https://etd.uum.edu.my/2804/2/1.Siti_Nurin_Ima_Ahmad.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
id my-uum-etd.2804
record_format uketd_dc
institution Universiti Utara Malaysia
collection UUM ETD
language eng
eng
advisor Ramli, Razamin
topic HD28-70 Management
Industrial Management
spellingShingle HD28-70 Management
Industrial Management
Siti Nurin Ima, Ahmad
Nurse Rostering: A Tabu Search Technique With Embedded Nurse Preferences
description The decision making in assigning all nursing staffs to shift duties in a hospital unit must be done appropriately because it is a crucial task due to various requirements and constraints that need to be fulfilled. The shift assignment or also known as roster has a great impact on the nurses’ operational circumstances which are strongly related to the intensity of quality of health care. The head nurse usually spends a substantial amount of time developing manual rosters, especially when there are many staff requests. Yet, sometimes she could not ensure that all constraints are met. Therefore, this research identified the relevant constraints being imposed in solving the nurse rostering problem (NRP) and examined the efficient method to generate the nurse roster based on constraints involved. Subsequently, as part of this research, we develop a Tabu Search (TS) model to solve a particular NRP. There are two aspects of enhancement in the proposed TS model. The first aspect is in the initialization phase of the TS model, where we introduced a semi-random initialization method to produce an initial solution. The advantage of using this initialization method is that it avoids the violation of hard constraints at any time in the TS process. The second aspect is in the neighbourhood generation phase, where several neighbours need to be generated as part of the TS approach. In this phase, we introduced two different neighbourhood generation methods, which are specific to the NRP. The proposed TS model is evaluated for its efficiency, where 30 samples of rosters generated were taken for analysis. The feasible solutions (i.e. the roster) were evaluated based on their minimum penalty values. The penalty values were given based on different violations of hard and soft constraints. The TS model is able to produce efficient rosters which do not violate any hard constraints and at the same time, fulfill the soft constraints as much as possible. The performance of the model is certainly better than the manually generated model and also comparable to the existing similar nurse rostering model.
format Thesis
qualification_name masters
qualification_level Master's degree
author Siti Nurin Ima, Ahmad
author_facet Siti Nurin Ima, Ahmad
author_sort Siti Nurin Ima, Ahmad
title Nurse Rostering: A Tabu Search Technique With Embedded Nurse Preferences
title_short Nurse Rostering: A Tabu Search Technique With Embedded Nurse Preferences
title_full Nurse Rostering: A Tabu Search Technique With Embedded Nurse Preferences
title_fullStr Nurse Rostering: A Tabu Search Technique With Embedded Nurse Preferences
title_full_unstemmed Nurse Rostering: A Tabu Search Technique With Embedded Nurse Preferences
title_sort nurse rostering: a tabu search technique with embedded nurse preferences
granting_institution Universiti Utara Malaysia
granting_department College of Arts and Sciences (CAS)
publishDate 2010
url https://etd.uum.edu.my/2804/1/Siti_Nurin_Ima_Ahmad.pdf
https://etd.uum.edu.my/2804/2/1.Siti_Nurin_Ima_Ahmad.pdf
_version_ 1747827433478815744
spelling my-uum-etd.28042013-07-24T12:18:07Z Nurse Rostering: A Tabu Search Technique With Embedded Nurse Preferences 2010 Siti Nurin Ima, Ahmad Ramli, Razamin College of Arts and Sciences (CAS) College of Arts and Sciences HD28-70 Management. Industrial Management The decision making in assigning all nursing staffs to shift duties in a hospital unit must be done appropriately because it is a crucial task due to various requirements and constraints that need to be fulfilled. The shift assignment or also known as roster has a great impact on the nurses’ operational circumstances which are strongly related to the intensity of quality of health care. The head nurse usually spends a substantial amount of time developing manual rosters, especially when there are many staff requests. Yet, sometimes she could not ensure that all constraints are met. Therefore, this research identified the relevant constraints being imposed in solving the nurse rostering problem (NRP) and examined the efficient method to generate the nurse roster based on constraints involved. Subsequently, as part of this research, we develop a Tabu Search (TS) model to solve a particular NRP. There are two aspects of enhancement in the proposed TS model. The first aspect is in the initialization phase of the TS model, where we introduced a semi-random initialization method to produce an initial solution. The advantage of using this initialization method is that it avoids the violation of hard constraints at any time in the TS process. The second aspect is in the neighbourhood generation phase, where several neighbours need to be generated as part of the TS approach. In this phase, we introduced two different neighbourhood generation methods, which are specific to the NRP. The proposed TS model is evaluated for its efficiency, where 30 samples of rosters generated were taken for analysis. The feasible solutions (i.e. the roster) were evaluated based on their minimum penalty values. The penalty values were given based on different violations of hard and soft constraints. The TS model is able to produce efficient rosters which do not violate any hard constraints and at the same time, fulfill the soft constraints as much as possible. The performance of the model is certainly better than the manually generated model and also comparable to the existing similar nurse rostering model. 2010 Thesis https://etd.uum.edu.my/2804/ https://etd.uum.edu.my/2804/1/Siti_Nurin_Ima_Ahmad.pdf application/pdf eng validuser https://etd.uum.edu.my/2804/2/1.Siti_Nurin_Ima_Ahmad.pdf application/pdf eng public http://lintas.uum.edu.my:8080/elmu/index.jsp?module=webopac-l&action=fullDisplayRetriever.jsp&szMaterialNo=0000774166 masters masters Universiti Utara Malaysia Aickelin, U., & Dowsland, K.A. (2004). An indirect genetic algorithm for a nurse-scheduling problem, Computers & Operations Research, 761 – 778. Aickelin, U., & Li, J. (2007). An estimation of distribution algorithm for nurse scheduling, Journal of the Operational Research Society, 155: 289 – 309. Aickelin, U., & White, P. (2004). Building better nurse scheduling algorithms, Annals of Operations Research, 128, pp 159 – 177. Azaiez, M.N., & Al Sharif, S.S. (2005). A 0 – 1 goal programming model for nurse scheduling, Computer & Operations Research, 32: 491 – 507. Bai, R., Burke, E. K., Kendall, G., Li, J. & McCollum, B. (2008). A hybrid evolutionary approach to the nurse rostering problem, IEEE Transaction on Evolutionary Computation. Bailey, R.N., Garner, K.M., & Hobbs, M.F. (1997). Using simulated annealing and genetic algorithms to solve staff scheduling problems, Asia-Pacific Journal of Operational Research, 14, 27-43. Baker, K.R. (1976). Workforce allocation in cyclic scheduling problems: a survey, Operational Research Quarterly, 27 (1,ii): 155 – 67. Bard, J.F., & Purnomo, H.W. (2004). Preference scheduling for nurses using column generation, European Journal of Operational Research, 1-25. Bard, J.F., & Purnomo, H.W. (2007). Preference scheduling for nurses using column generation, Journal of Scheduling, 10: 5 – 23. Beddoe, G.R., & Petrovic, S. (2005). Selecting and weighting features using a genetic algorithm in a case-based reasoning approach to personnel rostering, European Journal of Operational Research. Bellanti, F., Carello, G., Croce, F.D., & Tadei, R. (2001). A tabu search approach to a nurse rostering problem, Proceedings of the 4th Metaheuristics International Conference, MIC 2001. Bellanti, F., Carello, G., Croce, F.D., & Tadei, R. (2004). A geedy-based neighborhood search approach to a nurse rostering problem, European Journal of Operational Research, 153, 28-40. Berrada, I., Ferland, J.A., & Michelon, P. (1996). A multi-objective approach to nurse scheduling with both hard and soft constraints, Socio-Economic Planning Science, 30 (3), 183-193. Bester, M.J., Nieuwoudt, I., Jan, H., & Van Vuuren. (2007). Finding good nurse duty schedules : a case study, Journal of Scheduling, 10: 387-405. Brucker, P., Qu, R., Burke, E., & Post, G. (2007). A decomposition, construction and post-processing approach for nurse rostering, MISTA 2005, 397-406. Brusco, M.J., & John, T.R. (1995). The effect of demand characteristics on labour scheduling methods, International Journal of Operations & Productions Management, 15(1):74–88. Burke, E.K., Causmaecker, P.De, & Vanden Berghe, G. (1998). A hybrid tabu search algorithm for the nurse rostering problem, Proceedings of the 2nd Asia Pacific Conference, Simulated Evolution and Learning Volume, Canberra, 1. Burke, E.K., Causmaecker, P.De, Petrovic, S., & Vanden Berghe, G. (2001). Variable neighbourhood search for nurse rostering problems, Proceedings of the 4th Metaheuristics International Conference, MIC 2001, Porto, 2, 755-776. Burke, E.K., Causmaecker, P. De, Petrovic, S., & Vanden Berghe, G. (2001). Fitness evaluation for nurse scheduling problems, Proceedings of the Congress on Evolutionary Computation, CEG 2001, Seoul, 1139-46. Burke, E.K., Causmaecker, P. De, Petrovic, S., & Vanden Berghe, G. (2002). A multi criteria meta-heuristic approach to nurse rostering, Proceedings of the 2002 congress on evolutionary computation, CEC 2002, Honolulu Hawaii, 1197-1202. Burke, E.K., Cowling, P., Causmaecker, P. De, & Vanden Berghe, G. (2001). A memetic approach to the nurse rostering problem, Applied Intelligent, 15 (3), 199-214. Burke, E.K., & Newall, J.P. (1999). A multi-stage evolutionary algorithm for the timetable, The IEEE Transactions on Evolutionary Computation, 3.1, 63-74. Burke, E.K., Causmaecker, P. De, Petrovic, S., & Vanden Berghe, G. (2004). Variable neighbourhood search for nurse rostering problems, Proceedings of the 4th Metaheuristics International Conference, MIC 2001. Cheang, B., Li, H., Lim, A., & Rodrigues, B. (2003). Nurse rostering problems – a bibliographic survey, European Journal of Operational Research, 151, 447-460. Chen, J.G., & Yeung, T.W. (1992). Development of a hybrid expert system for nurse shift scheduling, International Journal of Industrial Egronomics 9, 315-327. Cheng, B.M.W., Lee, J.H.M., & Wu, C.K. (1997). Nurse rostering system using constraint programming and redundant modeling, IEEE Trans Information Technol Biomed, 1, 44-54. Davis, L. (1991). Handbook of genetic algorithms, New York: Van Nostrand Reinhold. Dawkins, R. (1989). The evolution of evolvability, Artificial Life, 201 – 220. Dawkins, R. (1976). Hierarchical organisation: a candidate principle for ethology, Growing Points in Ethology, 7 – 54. Dias, T., Ferber, D., Souza, C., & Moura, A. (2003). Constructing nurse schedules at large hospitals, International Transactions in Operational Research, 245–265. Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A survey, Theoritical Computer Science, 344 (2 – 3): 243 – 278. Dowsland, K. (1998). Nurse scheduling with tabu search and strategic oscillation, European Journal of Operational Research, 106, 393-407. Engku Muhammad Nazri Engku Abu Bakar. (2001). A heuristic to scheduling security personnel at local universities in Malaysia. Unpublished Ph.D. Thesis. Universiti Utara Malaysia, Malaysia. Gutjahr, W.J., & Rauner, M.S. (2004). An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria, Computers & Operations Research. Glover, F. (1989). Tabu Search – Part I, ORSA Journal on Computing, 1(3): 190 – 206. Glover, F. (1990). Tabu Search – Part II, ORSA Journal on Computing, 2(1): 4 – 32. Glover, F. (1995). Tabu thresholding: improved search by nonmonotonic trajectories, ORSA Journal on Computing, 7(4): 426 – 442. Glover, F. (1997). Tabu Search, Kluwer Academic Publisher, Boston. Glover, F., & Laguna, M. (1997). Tabu Search, Kluwer Academic Publisher, Boston. Hertz, A. (1991). Tabu search for large scale timetabling problems, European Journal of Operational Research,54,39-47. Hasegawa, S., & Kosugi, Y. (2006). Solving nurse scheduling problem by integer-programming-based local search, IEEE International Conference. Ikegami, A., & Niwa, A. (2003). A subproblem-centric model and approach to the nurse scheduling problem, Mathematical Programming, 97: 517 – 541. Kawanaka, H., Yamammoto, K., Yoshikawa, T., Shinogi, T., & Tsuruoka, S. (2001). Genetic algorithm with the constraints for nurse scheduling problem, Journal of Scheduling. Kellogg, D.L., & Walczak, S. (2007). Nurse scheduling: from academia to implementation or not?, Interfaces, 37, 4. Kolodner, J. (1993). Case-based reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Kundu, S., & Acharyya, S. (2008). A SAT approach for solving the nurse scheduling problem, IEEE Region 10 Conference TENCON. Lao, H. C. (1996). On the complexity of manpower shift scheduling, Computer & Operation Research, 23(1), 93 – 102. Li, H., Lim, A., & Rodrigues, B. (2003). A hybrid AI approach for nurse rostering problem, Proceedings of the 2003 ACM Symposium on Applied Computing, SAC, Melbourne, 730 – 735. Li, J., & Aickelin, U. (2003). A bayesian optimization algorithm for the nurse scheduling problem, Proceedings of 2003 Congress on Evolutionary Computation, CEC 2003, 2149 – 2156. Li, J., & Aickelin, U. (2004). The application of bayesian optimization and classifier systems in nurse scheduling, Proceedings of the 8th International Conference on Parallel Problem Solving from Nature, PPSN VIII, 581 – 590. Liao, C.J., & Kao, C.Y. (1997). Scheduling nursing personnel on a microcomputer, Health Manpower Management, 23(2 – 3): 100 – 6. Maenhout, B., & Vanhoucke, M. (2008). Comparison and hibridization of crossover operators for the nurse scheduling problem, Annals of Operations Research, 159: 333 – 353. Mathews, C.H. (2005). Using linear programming to minimize the cost of nurse personnel, Journal of Health Care Finance, 32, 1. Michalewicz, Z., & Fogel, D.B. (2000). How to solve it: modern heuristics, Springer-Verlag, Berlin, Germany. Millar, H.H., & Kiragu, M. (1998). Cyclic and non-cyclic scheduling of 12 h shift nurses by network programming, European Journal of Operational Research, 104, 582-592. Moz, M., & Pato, M.V. (2005). A genetic algorithm approach to a nurse rerostering problem, Computer and Operations Research. Ohki, M, Uneme, S., & Kawano, H. (2008). Parallel processing of cooperative genetic algorithm for nurse scheduling, 4th International IEEE Conference “Intelligent Systems”. Oughalime, A., Ismail, W.R., & Yeun, L.C. (2008). A tabu search approach to the nurse scheduling problem, International Symposium on Information Technology, 1: 1 – 7. Ozkaharan, I., & Bailey, J.E. (1988). Goal programming model subsystem of a flexible nurse scheduling support system, IIE Transactions 20(3), 306-315. Ozkaharan, I. (1991). An integrated nurse scheduling model, Journal of Social and Health System, 3, 79-101. Nonobe, K., & Ibaraki, T. (1998). A tabu search approach to the constraint satisfaction problem as a general problem solver, European Journal of Operational Research, 106, 599-623. Parr, D., & Thompson, J.M. (2007). Solving the multi-objective nurse scheduling problem with a weighted cost function, Annals of Operations Research, 155: 279 – 288. Randhawa, S.U. & Sitompul, D. (1993). A heuristic-based computerized nurse scheduling system, Computers and Operations Research, 20, 837-844. Ramli, R., Khader, A. T., & Mustafa, A. (2002). Nurse scheduling models: recent advancements and future directions, International Conference on Operations Research for DevelopmntI, 27-30 December, Chennai, India. Ramli, R. (2004). An evolutionary algorithm for the nurse scheduling problem with circadian rhythms, Unpublished PhD Thesis, Universiti Sains Malaysia, Malaysia. Sitompul, D. (1992). Design and implementation of a heuristic-based decision support system for nurse scheduling, Unpublished Doctoral Thesis, Oregon State University. Sitompul, D., & Randhawa, S.U. (1990). Nurse scheduling models: a state-of-the-art review, Journal of the Society for Health Systems, 2(1): 62 – 72. Taillard, J., Philip, P., Chastang, J.F., Dienfenbach, K., & Bioulac, B. (2001). Is self-reported morbidity related to the circadian clock?, Journal of biological rhythms, 16 (2): 183 – 90. Thornton, J.R., & Sattar, A. (1997). Nurse rostering and integer programming revisited, International Conference on Computational Intelligence and Multimedia Applications, ICCIMA'97, 49-58. Valouxis, C., & Housos, E. (2000). Hybrid optimization techniques for the workshift and rest assignment of nursing personnel, Artificial Intelligence in Medicine, 20, 155-175. Vanhoucke, M., & Maenhout, B. (2005). NSPLib – A nurse scheduling problem library: A tool to evaluate (meta-) heuristic procedures., ORAHS Proceedings. Warner, D.M. (1976). Scheduling nursing personnel according to nursing preferences: a mathematical programming approach, Operations Research, Vol. 24, No. 5, 842-856. Wren, A. (1996). Scheduling, timetabling and rostering – a special relationship?, Lecture Note in Computer Science, Vol. LNCS 1153, 46-75.

Similar Items