Innovative Applications of O.R.A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems
Introduction
Employee scheduling has been extensively studied by operational researchers and computer scientists for more than 40 years (see survey papers in [8], [11], [28]). It can be thought of as the problem of assigning employees to shifts or duties over a scheduling period so that certain constraints (organizational and personal) are satisfied. In the field of hospital nurse rostering, this is particularly challenging due to the presence of different nurse requirements on different days and shifts. Unlike most other organizations, hospitals and medical institutes work around the clock, and thus irregular shift work has an effect on the nurses’ well being and job satisfaction [36]. The development of robust and powerful nurse rostering systems that can handle a wide range of requirements and constraints would provide significant benefits for hospital administrators and staff.
Nurse rostering is a type of resource-allocation problem, in which the workload needs to be assigned to nurses periodically, taking into account a number of constraints and requirements. Hard constraints are those that must be satisfied in order to have a feasible schedule. They are often generated by physical resource restrictions and legislation. When requirements are desirable but not obligatory they are referred to as soft constraints. Such constraints are often used to evaluate the quality of feasible schedules. In nurse rostering, there are a large number of variations on legal regulations and individual preferences, depending on different countries and institutions. Typical issues concern coverage demand, day-off requirements, weekend-off requirements, minimum and maximum workforce among others [18].
Most nurse rostering problems in the real world are NP-hard [30] and were regarded as being more complex than the travelling salesman problem by [37]. Over the years, a wide variety of methodologies and models have been developed to deal with them. Introduction to many of these methods can be found in [19]. A number of survey papers [15], [21], [39] give an overview of the area. The available techniques can roughly be classified into two main categories: exact algorithms and (meta)heuristics. Mathematical programming is the traditional exact method [6], [7], [9], [33], [41], which guarantees to find an optimal solution on nurse rostering for every instance of a problem. However, computational difficulties exist with this approach due to the enormous size of the search spaces that are generated. To reduce complexity, some researchers have restricted the problem dimensions and developed simplified models. However, this leads to solutions that are not applicable to real hospital situations.
The above observations have led to attempts to solve the real problems by investigating heuristics. In this case, the guarantee of finding optimal solutions is sacrificed for the sake of getting good solutions within a reasonable amount of time. Early heuristic approaches [10], [40] were investigated with some success and metaheuristics have attracted significant attention since the 1990’s. Genetic and memetic algorithms form an important class of metaheuristics that have been extensively applied in nurse rostering [2], [3], [16], [26], [31]. A number of attempts have also been made by using other metaheuristics, such as simulated annealing [13], tabu search [14], variable neighbourhood search [17], [18] and estimation of distribution algorithms [4].
However, the major drawback of these metaheuristics is they cannot provably produce optimal solutions nor can they provably reduce the search space. Also, they usually do not have well defined stopping criteria. Moreover, most nurse rostering problems are highly constrained problems which means that the feasible regions of their solution space are disconnected (i.e. separated by the infeasible area). Metaheuristics generally have difficulty in dealing with this situation. Considering the advantages and disadvantages of both categories of approaches, this research is looking at new attempts for an appropriate integration. The long-term aim of this research is to investigate efficient ways of decomposing real-world personnel scheduling problems into tractable subproblems, without losing much optimality.
In the field of nurse rostering, some decomposition techniques have been investigated over recent years. Aickelin and Dowsland [3] developed a genetic algorithm with an indirect representation. Different heuristic decoders (i.e. decomposers) were employed to construct the schedule, taking care of coverage and nurses’ preferences from different aspects. Ikegami and Niwa [3] grouped the constraints into shift constraints and nurse constraints. Based on this, the problems were decomposed into subproblems and solved repeatedly by tabu search. Brucker et al. [12] implemented decomposition by cyclically assigning predefined blocks of shifts to groups of nurses. The rest of the shifts were then assigned by hand and the resulting schedule was improved by local search.
In this paper, we present a new decomposition technique by combining integer programming (IP) and variable neighbourhood search (VNS) to deal with constraints and requirements. More details about these techniques can be seen in [19]. The IP is first used to solve a subproblem including all hard constraints and a subset of soft constraints. When determining if a soft constraint should be included in the subset, we give more priority to the constraints that have the following characteristics: low complexity (i.e. the number of variables and constraints it may add in the IP model), high importance (i.e. the degree to which the constraint is considered to be desirable by the hospital), or a trade-off between complexity and importance. In this paper, we exclude Constraint set SC7 (i.e. avoiding certain shift type successions) from the IP model and leave it to be addressed by the VNS. We can certainly partition the constraint sets in different ways.
The VNS is then used as a postprocessing procedure to make the improvement, and the satisfaction of the constraints that are not included in the subset would be the major concern in designing the VNS’s neighbourhood structures. Note that in the first IP phase, it is not necessary to solve the subproblem to optimality because, under most circumstances, this process would still take an extremely long time to finish. We can obtain an intermediate solution by setting up a stopping condition (e.g. maximum runtime or acceptable solution quality) to the IP.
The rest of the paper is organized as follows. We first describe the nurse rostering problem to be addressed and formulate its full multi-objective IP model by taking into account all the constraints. We then formulate an alternative heuristic model and propose a basic VNS approach to deal with it. Later, we carry out the experiments on 12 real instances arising in a Dutch hospital and demonstrate how the proposed IP and the VNS are not capable of solving the problem in their own right, and how the suggested combination can achieve high quality solutions. Finally, we give concluding remarks and possible future research directions.
Section snippets
Problem description
The nurse rostering problem we are tackling is provided by ORTEC, an international consultancy company specializing in planning, optimization and decision support solutions. The problem is based on the situation of intensive care units in a Dutch hospital, which involves assigning four types of shifts (i.e. shifts of early, day, late and night) within a scheduling period of 5 weeks to 16 nurses of different working contracts in a ward. The problem has the following key characteristics:
- 1.
Dutch
A multi-objective mathematical model
To specify the above problem, slack and surplus variables can be introduced into the soft constraints, and the objectives are to minimize the values of individual variables. We formulate the entire problem associated with a 5-week scheduling period as the following IP model, which can be altered to adapt to other problems with different constraints.Parameters: I set of nurses available; subset of nurses that work 20, 32, 36 hours per week respectively, ; J set of indices of the
A multi-objective heuristic model and variable neighbourhood search (VNS)
This section presents an alternative heuristic model and a VNS metaheuristic to deal with the problem.
Computational results
Whilst the hard constraints of our problem are requirements that must be met under any circumstance, the objectives for both our IP model and our heuristic model are to satisfy the soft constraints as much as possible. Regarding the degree of desirability for the soft constraints listed in Section 2, we have the following priority ordering: [SC1, SC2] SC3 [SC4, SC5, SC6] [SC7], where ‘’ denotes “be more preferred than”. This ordering has been determined by the hospital.
Accordingly,
Conclusions
This paper proposes a hybrid model within a multi-objective framework for real world hospital nurse rostering, in which IP and VNS are combined for global optimization. The IP is used to solve an easily handled subproblem by only including the constraints that would cause less computing complexity or which are regarded as more important by users. A VNS with the neighbourhood of swapping blocks of shifts is then used to make the improvement on the LP’s resulting solution, mainly from the aspects
Acknowledgement
The work was funded by the UK’s Engineering and Physical Sciences Research Council (EPSRC), under Grant GR/S31150/01.
References (42)
- et al.
An indirect genetic algorithm for a nurse scheduling problem
Computers and Operations Research
(2004) - et al.
Preference scheduling for nurses using column generation
European Journal of Operational Research
(2005) Scheduling staff using mixed integer programming
European Journal of Operational Research
(1997)- et al.
A multi-objective approach to nurse scheduling with both hard and soft constraints
Socio-Economic Planning Science
(1996) - et al.
A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem
European Journal of Operational Research
(2008) - et al.
Nurse rostering problems – A bibliographic survey
European Journal of Operational Research
(2003) - et al.
A distributed genetic algorithm for deterministic and stochastic labor scheduling problems
European Journal of Operational Research
(1999) - et al.
Staff scheduling and rostering: A review of applications, methods and models
European Journal of Operational Research
(2004) - et al.
Variable neighbourhood search
Computers and Operations Research
(1997) - S. Abdullah, E.K. Burke, B. McCollum, An investigation of variable neighbourhood search for university course...
Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem
Journal of Scheduling
An estimation of distribution algorithm for nurse scheduling
Annals of Operations Research
A comparative evaluation of labor tour scheduling methods
Decision Sciences
Multishift personnel scheduling with a microcomputer
Personnel Administrator
Continuous personnel scheduling algorithms: A literature review
Journal of the Society for Health Systems
A simulated annealing approach to the cyclic staff-scheduling problem
Naval Research Logistics
A hybrid tabu search algorithm for the nurse rostering problem
The state of the art of nurse rostering
Journal of Scheduling
A memetic approach to the nurse rostering problem
Applied Intelligence
Cited by (139)
Solving a real-world nurse rostering problem by Simulated Annealing
2023, Operations Research for Health CareE-platooning: Optimizing platoon formation for long-haul transportation with electric commercial vehicles
2023, European Journal of Operational ResearchThe impact of the optimal buffer configuration on production line efficiency: A VNS-based solution approach
2021, Expert Systems with ApplicationsA hybrid fix-and-optimize and simulated annealing approaches for nurse rostering problem
2020, Computers and Industrial EngineeringLP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup
2024, International Transactions in Operational ResearchConstructing modified variable neighborhood search approaches to solve a nurse scheduling problem
2024, International Journal of Production Research