A hybrid integer and constraint programming approach to solve nurse rostering problems

Rahimian, Erfan and Akartunali, Kerem and Levine, John (2017) A hybrid integer and constraint programming approach to solve nurse rostering problems. Computers & Operations Research, 82. pp. 83-94. ISSN 0305-0548

[img]
Preview
 Text (Rahimian-etal-COR-2017-A-hybrid-integer-and-constraint-programming-approach)
Rahimian_etal_COR_2017_A_hybrid_integer_and_constraint_programming_approach.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (609kB)| Preview

    Abstract

    The Nurse Rostering Problem can be defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some limitations and preferences. The inherent benefits of generating higher-quality schedules are a reduction in outsourcing costs and an increase in job satisfaction of employees. In this paper, we present a hybrid algorithm, which combines Integer Programming and Constraint Programming to efficiently solve the highly-constrained Nurse Rostering Problem. We exploit the strength of IP in obtaining lower-bounds and finding an optimal solution with the capability of CP in finding feasible solutions in a co-operative manner. To improve the performance of the algorithm, and therefore, to obtain high-quality solutions as well as strong lower-bounds for a relatively short time, we apply some innovative ways to extract useful information such as the computational difficulty of in- stances and constraints to adaptively set the search parameters. We test our algorithm using two different datasets consisting of various problem instances, and report competitive results benchmarked with the state-of-the-art algorithms from the recent literature as well as standard IP and CP solvers, showing that the proposed algorithm is able to solve a wide variety of instances effectively.

    Author(s):Rahimian, Erfan ORCID logoORCID: https://orcid.org/0000-0003-0532-0700, Akartunali, Kerem ORCID logoORCID: https://orcid.org/0000-0003-0169-3833 and Levine, John ORCID logoORCID: https://orcid.org/0000-0001-7016-2978
    Item type:Article
    ID code:59727
    Keywords:timetabling, nurse rostering, hybrid algorithm, integer programming, constraint programming, Mathematics, Management. Industrial Management, Artificial Intelligence, Management Science and Operations Research, Software, Leadership and Management
    Subjects:Science > Mathematics
    Social Sciences > Industries. Land use. Labor > Management. Industrial Management
    Department:Strathclyde Business School > Management Science
    Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:08 Feb 2017 09:32
    Last modified:12 Feb 2020 04:18
    URI:https://strathprints.strath.ac.uk/id/eprint/59727
    Export data:
    CORE (COnnecting REpositories)