IDEAS home Printed from https://ideas.repec.org/p/rug/rugwps/05-339.html
   My bibliography  Save this paper

Characterisation and Generation of Nurse Scheduling Problem Instances

Author

Listed:
  • M. VANHOUCKE
  • B. MAENHOUT

Abstract

In this paper, we propose different complexity indicators for the well-known nurse scheduling problem (NSP). The NSP assigns nurses to shifts per day taking both hard and soft constraints into account. The objective is to maximize the nurses’ preferences and to minimize the total penalty cost from violations of the soft constraints. The problem is known to be NP-hard. Due to its complexity and relevance in practice, the operations research literature has been overwhelmed by different procedures to solve the problem. The complexity has resulted in the development of several (meta-)heuristic procedures, able to solve a NSP instance heuristically in an acceptable time limit. The practical relevance has resulted in a never-ending amount of different NSP versions, taking practical, case-specific constraints into account. The contribution of this paper is threefold. First, we describe our complexity indicators to characterize a nurse scheduling problem instance. Secondly, we develop a NSP generator to generate benchmark instances to facilitate the evaluation of existing and future research techniques. Finally, we perform some preliminary tests on a simple IP model to illustrate that the proposed indicators can be used as predictors of problem complexity.

Suggested Citation

  • M. Vanhoucke & B. Maenhout, 2005. "Characterisation and Generation of Nurse Scheduling Problem Instances," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/339, Ghent University, Faculty of Economics and Business Administration.
  • Handle: RePEc:rug:rugwps:05/339
    as

    Download full text from publisher

    File URL: http://wps-feb.ugent.be/Papers/wp_05_339.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Jan Lepoutre & Nikolay Dentchev & Aimé Heene, 2007. "Dealing With Uncertainties When Governing CSR Policies," Journal of Business Ethics, Springer, vol. 73(4), pages 391-408, July.
    2. W. Bruggeman & P. Everaert & S. R. Anderson & Y. Levant, 2005. "Modeling Logistics Costs using Time-Driven ABC: A Case in a Distribution Company," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/332, Ghent University, Faculty of Economics and Business Administration.
    3. H. De Witte & E. Verhofstadt & E. Omey, 2005. "Testing Karasek’s learning- and strain hypothesis on young workers in their first job," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/326, Ghent University, Faculty of Economics and Business Administration.
    4. B. Merlevede & K. Schoors, 2005. "How to Catch Foreign Fish? FDI and Privatisation in EU Accession Countries," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/309, Ghent University, Faculty of Economics and Business Administration.
    5. G. Sarens & I. De Beelde, 2005. "Internal Auditor’s Perception about their Role in Risk Management Comparison between Belgian and US Companies," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/304, Ghent University, Faculty of Economics and Business Administration.
    6. A. Karas & K. Schoors, 2005. "Heracles or Sisyphus? Finding, cleaning and reconstructing a database of Russian banks," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/327, Ghent University, Faculty of Economics and Business Administration.
    7. Arne Schollaert & Dirk Van de gaer, 2008. "Boycotts, Power Politics, or Trust Building: How to Prevent Conflict?," Journal of Institutional and Theoretical Economics (JITE), Mohr Siebeck, Tübingen, vol. 164(2), pages 356-379, June.
    8. P. Everaert & G. Sarens, 2005. "Outsourcing bij Vlaamse Ondernemingen: een Exploratief Onderzoek," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/306, Ghent University, Faculty of Economics and Business Administration.
    9. Bert Weijters & Maggie Geuens, 2002. "Evaluation of age-related labels by senior citizens," Vlerick Leuven Gent Management School Working Paper Series 2002-22, Vlerick Leuven Gent Management School.
    10. M Vanhoucke & S Vandevoorde, 2007. "A simulation and evaluation of earned value metrics to forecast the project duration," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(10), pages 1361-1374, October.
    11. G. Lanine & R. Vander Vennet, 2005. "Failure prediction in the Russian bank sector with logit and trait recognition models," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/329, Ghent University, Faculty of Economics and Business Administration.
    12. N. Geeroms & P. Van Kenhove & W. Verbeke, 2005. "Health Advertising to promote Fruit and Vegetable Intake: Application of need-related Health Audience Segmentation," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/336, Ghent University, Faculty of Economics and Business Administration.
    13. V. Vansteeger, 2005. "The current state of accounting harmonization: impediments to and benefits from harmonization," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/322, Ghent University, Faculty of Economics and Business Administration.
    14. L. Pozzi, 2005. "Income Uncertainty and Aggregate Consumption," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/334, Ghent University, Faculty of Economics and Business Administration.
    15. M. Knockaert & A. Lockett & B. Clarysse & M. Wright, 2005. "Do human capital and fund characteristics drive follow-up behaviour of early stage high tech VCs?," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/325, Ghent University, Faculty of Economics and Business Administration.
    16. Vandevoorde, S. & Vanhoucke, M., 2005. "A comparison of different project duration forecasting methods using earned value metrics," Vlerick Leuven Gent Management School Working Paper Series 2005-16, Vlerick Leuven Gent Management School.
    17. M. Vanhoucke & D. Debels, 2005. "The Discrete Time/Cost Trade-Off Problem Under Various Assumptions Exact And Heuristic Procedures," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/314, Ghent University, Faculty of Economics and Business Administration.
    18. G. Poels & A. Maes & F. Gailly, 2005. "User Attitudes towards Pattern-Based Enterprise Information Models: A Replicated Experiment with REA Diagrams," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/315, Ghent University, Faculty of Economics and Business Administration.
    19. M. Buelens & D. Bouckenooghe & D. De Clercq & A. Willem, 2005. "An Assessment of Validity in Small Business and Entrepreneurship Research," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/328, Ghent University, Faculty of Economics and Business Administration.
    20. G. Poels & F. Gailly & A. Maes & R. Paemeleire, 2005. "Object Class or Association Class? Testing the User Effect on Cardinality Interpretation," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/323, Ghent University, Faculty of Economics and Business Administration.
    21. P. Windels & J. Christiaens, 2005. "Management Reform in Flemish Local Authorities: Testing the Institutional Framework," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/331, Ghent University, Faculty of Economics and Business Administration.
    22. L. Pozzi, 2005. "Income uncertainty and aggregate consumption," Working Paper Research 77, National Bank of Belgium.
    23. I. Vermeir & M. Geuens, 2005. "Need for Closure and Youngsters’ Leisure Time Preferences," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/318, Ghent University, Faculty of Economics and Business Administration.
    24. A. Heirman & B. Clarysse, 2005. "The imprinting effect of initial resources and market strategy on the early growth path of start-Ups," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/310, Ghent University, Faculty of Economics and Business Administration.
    25. S. CLAEYS & G. LANINE & K. SCHOORs, 2005. "Bank Supervision Russian Style: Rules vs Enforcement and Tacit Objectives," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/307, Ghent University, Faculty of Economics and Business Administration.
    26. D. Vantomme & M. Geuens & S. Dewitte, 2005. "How to Portray Men and Women in Advertisements? Explicit and Implicit Evaluations of Ads Depicting Different Gender Roles," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/319, Ghent University, Faculty of Economics and Business Administration.
    27. J. Albrecht & M. Neyt & T. Verbeke, 2005. "Bureaucratisation and the growth of health care expenditures in Europe," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/335, Ghent University, Faculty of Economics and Business Administration.
    28. W. Buckinx & G. Verstraeten & D. Van Den Poel, 2005. "Predicting Customer Loyalty Using The Internal Transactional Database," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/324, Ghent University, Faculty of Economics and Business Administration.
    29. W. Buckinx & D. Van Den Poel, 2005. "Assessing and exploiting the profit function by modeling the net impact of targeted marketing," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/330, Ghent University, Faculty of Economics and Business Administration.
    30. repec:zbw:bofitp:2005_010 is not listed on IDEAS
    31. A. Maes & G. Poels & F. Gailly & R. Paemeleire, 2005. "Measuring User Beliefs and Attitudes towards Conceptual Models: A Factor and Structural Equation Model," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/311, Ghent University, Faculty of Economics and Business Administration.
    32. B. Maenhout & M. Vanhoucke, 2005. "An Electromagnetic Meta-Heuristic for the Nurse Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/316, Ghent University, Faculty of Economics and Business Administration.
    33. E. Labro & M. Vanhoucke, 2005. "A simulation analysis of interactions between errors in costing system design," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/333, Ghent University, Faculty of Economics and Business Administration.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Broos Maenhout & Mario Vanhoucke, 2008. "Comparison and hybridization of crossover operators for the nurse scheduling problem," Annals of Operations Research, Springer, vol. 159(1), pages 333-353, March.
    2. Vanhoucke, Mario & Maenhout, Broos, 2009. "On the characterization and generation of nurse scheduling problem instances," European Journal of Operational Research, Elsevier, vol. 196(2), pages 457-467, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. H. Ooghe & C. Spaenjers & P. Vandermoere, 2005. "Business failure prediction: simple-intuitive models versus statistical models," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/338, Ghent University, Faculty of Economics and Business Administration.
    2. Jan Lepoutre & Nikolay Dentchev & Aimé Heene, 2007. "Dealing With Uncertainties When Governing CSR Policies," Journal of Business Ethics, Springer, vol. 73(4), pages 391-408, July.
    3. M. Dossche & G. Everaert, 2005. "Measuring inflation persistence: a structural time series approach," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/340, Ghent University, Faculty of Economics and Business Administration.
    4. B. Maenhout & M. Vanhoucke, 2005. "New Computational Results for the Nurse Scheduling Problem: A Scatter Search Algorithm," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/341, Ghent University, Faculty of Economics and Business Administration.
    5. J. Albrecht & M. Neyt & T. Verbeke, 2005. "Bureaucratisation and the growth of health care expenditures in Europe," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/335, Ghent University, Faculty of Economics and Business Administration.
    6. N. Geeroms & P. Van Kenhove & W. Verbeke, 2005. "Health Advertising to promote Fruit and Vegetable Intake: Application of need-related Health Audience Segmentation," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/336, Ghent University, Faculty of Economics and Business Administration.
    7. L. Pozzi, 2005. "Income Uncertainty and Aggregate Consumption," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/334, Ghent University, Faculty of Economics and Business Administration.
    8. E. Labro & M. Vanhoucke, 2005. "A simulation analysis of interactions between errors in costing system design," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/333, Ghent University, Faculty of Economics and Business Administration.
    9. W. Bruggeman & P. Everaert & S. R. Anderson & Y. Levant, 2005. "Modeling Logistics Costs using Time-Driven ABC: A Case in a Distribution Company," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/332, Ghent University, Faculty of Economics and Business Administration.
    10. P. Windels & J. Christiaens, 2005. "Management Reform in Flemish Local Authorities: Testing the Institutional Framework," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/331, Ghent University, Faculty of Economics and Business Administration.
    11. W. Buckinx & D. Van Den Poel, 2005. "Assessing and exploiting the profit function by modeling the net impact of targeted marketing," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/330, Ghent University, Faculty of Economics and Business Administration.
    12. A. Karas & K. Schoors, 2005. "Heracles or Sisyphus? Finding, cleaning and reconstructing a database of Russian banks," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/327, Ghent University, Faculty of Economics and Business Administration.
    13. G. Poels & F. Gailly & A. Maes & R. Paemeleire, 2005. "Object Class or Association Class? Testing the User Effect on Cardinality Interpretation," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/323, Ghent University, Faculty of Economics and Business Administration.
    14. Bert Weijters & Maggie Geuens, 2002. "Evaluation of age-related labels by senior citizens," Vlerick Leuven Gent Management School Working Paper Series 2002-22, Vlerick Leuven Gent Management School.
    15. H. De Witte & E. Verhofstadt & E. Omey, 2005. "Testing Karasek’s learning- and strain hypothesis on young workers in their first job," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/326, Ghent University, Faculty of Economics and Business Administration.
    16. Knockaert, M. & Lockett, A. & Clarysse, B. & Wright, M., 2005. "Do human capital and fund characteristics drive follow-up behaviour of early stage high tech vcs?," Vlerick Leuven Gent Management School Working Paper Series 2005-20, Vlerick Leuven Gent Management School.
    17. V. Vansteeger, 2005. "The current state of accounting harmonization: impediments to and benefits from harmonization," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/322, Ghent University, Faculty of Economics and Business Administration.
    18. S. Steenhaut & P. Van Kenhove, 2005. "An Empirical Investigation of the Relationships among a Consumer’s Personal Values, Ethical Ideology and Ethical Beliefs," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/321, Ghent University, Faculty of Economics and Business Administration.
    19. M. Buelens & D. Bouckenooghe & D. De Clercq & A. Willem, 2005. "An Assessment of Validity in Small Business and Entrepreneurship Research," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/328, Ghent University, Faculty of Economics and Business Administration.
    20. W. Buckinx & G. Verstraeten & D. Van Den Poel, 2005. "Predicting Customer Loyalty Using The Internal Transactional Database," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/324, Ghent University, Faculty of Economics and Business Administration.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:rug:rugwps:05/339. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Nathalie Verhaeghe (email available below). General contact details of provider: https://edirc.repec.org/data/ferugbe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.