A Two-Stage Stochastic Programming for Nurse Scheduling in Razavi Hospital

Document Type : Original Article


1 Department of Industrial Engineering, Sadjad University of Technology, Mashhad, IR Iran

2 Research and Education Department, Razavi Hospital, Mashhad, IR Iran



Background: One of most important operations research problems is Nurse Scheduling Problem (NSP) that tries to find an optimal way to assign nurses to shifts with a set of hard constraints. Most of the researches are dealing with this problem in deterministic environment with constant parameters. While In the real world applications of NSP, the stochastic nature of some parameters like number of arriving patients, stay periods, etc. are some sources of uncertainties that need to be controlled to provide a qualified schedule. Objectives: In this article we propose our model in an uncertain environment in Department of Heart Surgery in Razavi Hospital. Materials and Methods: The demand and stay period of patients are stochastic whose the distribution is determined from historical data. Finally, the demand of nurses in each shift in planning horizon is calculated regarding the priority (vitality) of patients. Results: The stochastic optimization is adapted for our problem and the Sample Average Approximation (SAA) method is used to obtain a optimal schedule with respect to minimizing the regular and over time assignment costs. The results have been analyzed and show the validity of our model. Conclusions: In this model the demand and stay period of patients are stochastic whose the distribution is determined from historical data. We also consider the priority (vitality) of patients in our model.


  1. 1.Warner DM. Scheduling Nursing Personnel According to Nursing Preference: A Mathematical Programming Approach. Oper Res. 1976;24(5):842–56.

    1. Millar HH, Kiragu M. Cyclic and non-cyclic scheduling of 12 h shift nurses by network programming. Eur J Oper Res. 1998;104(3):582– 92.
    2. Venkataraman R, Brusco MJ. An integrated analysis of nurse staffing and scheduling policies. Omega. 1996;24(1):57–71.
    3. Ozkarahan I. A flexible nurse scheduling support system. Comput Methods Programs Biomed. 1989;30(2-3):145–53.
    4. Jaumard B, Semet F, Vovor T. A generalized linear programming model for nurse scheduling. Eur J Oper Res. 1998;107(1):1–18.
    5. Klinz B, Pferschy U, Schauer J. ILP Models for a Nurse Scheduling Problem. In: Waldmann KH, Stocker U editors. Operations Research Proceedings. Berlin Heidelberg: Springer; 2007. pp. 319–24. 7. Bard JF, Purnomo HW. Short-term nurse scheduling in response to daily fluctuations in supply and demand. Health Care Manag Sci. 2005;8(4):315–24.
    6. Hattori H, Ito T, Ozono T, Shintani T. A Nurse Scheduling System Based on Dynamic Constraint Satisfaction Problem. In: Ali M, Esposito F editors. Innovations in Applied Artificial Intelligence. Berlin Heidelberg: Springer; 2005. pp. 799–808.
    7. Parr D, Thompson JM. Solving the multi-objective nurse scheduling problem with a weighted cost function. Ann Oper Res. 2007;155(1):279–88.
    8. Punnakitikashem P, Rosenberger JM, Behan DB. Stochastic programming for nurse assignment. Comput Optim Appl. 2008;40(3):321–49.
    9. Fan N, Mujahid S, Zhang J, Georgiev P, Papajorgji P, Steponavice I, et al. The Application of Bayesian Optimization and Classifier Systems in Nurse Scheduling. In: Pardalos PM, Georgiev PG, Papajorgji P, Neugaard B editors. Systems Analysis Tools for Better Health Care Delivery. New York: Springer; 2013. pp. 65–98.
    10. Li J, Aickelin U. The Application of Bayesian Optimization and Classifier Systems in Nurse Scheduling. In: Bullinaria J, Rowe J, Tino, A. P. , Kaban, A. , Schwefel, H. P. editors. Parallel Problem Solving from Nature - PPSN VIII . Springer: Berlin Heidelberg; 2004. pp. 581–90.
    11. Topaloglu S, Selim H. Nurse Scheduling Using Fuzzy Multiple Objective Programming. In: Okuno H, Ali M editors. New Trends in Applied Artificial Intelligence . Berlin Heidelberg: Springer; 2007. pp. 54–63.
    12. Topaloglu S, Selim H. Nurse scheduling using fuzzy modeling approach. Fuzzy Sets Syst. 2010;161(11):1543–63.
    13. Maenhout B, Vanhoucke M. An electromagnetic meta-heuristic for the nurse scheduling problem. J Heuristics. 2007;13(4):359–85.
    14. Landa silva D, Le K. A Simple Evolutionary Algorithm with Selfadaptation for Multi-objective Nurse Scheduling. In: Cotta C, Sevaux M, Sörensen K editors. Adaptive and Multilevel Metaheuristics. Berlin Heidelberg: Springer; 2008. pp. 133–55.
    15. Tsai CC, Li SHA. A two-stage modeling with genetic algorithms for the nurse scheduling problem. Expert Syst Appl. 2009;36(5):9506– 12.
    16. Ohki M, Uneme SY, Kawano H. Effective Mutation Operator and Parallel Processing for Nurse Scheduling. In: Sgurev V, Hadjiski M, Kacprzyk J editors. Intelligent Systems: From Theory to Practice. Berlin Heidelberg: Springer; 2010. pp. 229–42.
    17. Zhang Z, Hao Z, Huang H. Hybrid Swarm-Based Optimization Algorithm of GA & VNS for Nurse Scheduling Problem. In: Liu B, Chai C editors. Information Computing and Applications. Berlin Heidelberg: Springer; 2011. pp. 375–82.
    18. Stougie L, Van Der Vlerk MH. Approximation in stochastic integer programming. Berlin: University of Groningen; 2003. Available from: http://edoc.hu-berlin.de/docviews/abstract.php?id=26729.
    19. Birge JR, Louveaux F. Introduction to stochastic programming.: Springer Science & Business Media; 2011.
    20. Shapiro A, Philpott A. A tutorial on stochastic programming. Manuscript. 2007.
    21. Kleywegt AJ, Shapiro A, Homem-de-Mello T. The sample average approximation method for stochastic discrete optimization. SIAM J Optim. 2002;12(2):479–502.
    22. Ahmed S, Alexander S, Shapiro ER. The sample average approximation method for stochastic programs with integer recourse. 2007.
    23. Shapiro A, Homem-de-Mello T. On the rate of convergence of optimal solutions of Monte Carlo approximations of stochastic programs. SIAM J Optim. 2000;11(1):70–86.
    24. Mak WK, Morton DP, Wood RK. Monte Carlo bounding techniques for determining solution quality in stochastic programs. Oper Res Lett. 1999;24(1):47–56.