New approaches to nurse rostering benchmark instances

This paper presents the results of developing a branch and price algorithm and an ejection chain method for nurse rostering problems. The approach is general enough to be able to apply it to a wide range of benchmark nurse rostering instances. The majority of the instances are real world applications. They have been collected from a variety of sources including industrial collaborators, other researchers and various publications. The results of entering these algorithms in the 2010 International Nurse Rostering Competition are also presented and discussed. In addition, incorporated within both algorithms is a dynamic programming method which we present. The algorithm contains a number of heuristics and other features which make it very effective on the broad rostering model introduced.     

The nurse rostering problem: A critical appraisal of the problem structure

This paper is concerned with the problem of nurse rostering within hospitals. We analyse a class of four benchmark instances from the nurse rostering literature to provide insight into the nature of the problem. By highlighting the structure of the problem we are able to reduce the relevant solution space. A mixed integer linear programme is then able to find optimal solutions to all four instances of this class of benchmark problems, each within half an hour. Our second contribution is to extend current mathematical approaches to nurse rostering to take better account of the practical considerations. We provide a methodology for handling rostering constraints and preferences arising from the continuity from one scheduling period to the next.     

A variable neighborhood search based matheuristic for nurse rostering problems

A practical nurse rostering problem, which arises at a ward of an Italian private hospital, is considered. In this problem, it is required each month to assign shifts to the nursing staff subject to various requirements. A matheuristic approach is introduced, based on a set of neighborhoods iteratively searched by a commercial integer programming solver within a defined global time limit, relying on a starting solution generated by the solver running on the general integer programming formulation of the problem. Generally speaking, a matheuristic algorithm is a heuristic algorithm that uses non trivial optimization and mathematical programming tools to explore the solutions space with the aim of analyzing large scale neighborhoods. Randomly generated instances, based on the considered nurse rostering problem, were solved and solutions computed by the proposed procedure are compared to the solutions achieved by pure solvers within the same time limit. The results show that the proposed solution approach outperforms the solvers in terms of solution quality. The proposed approach has also been tested on the well known Nurse Rostering Competition instances where several new best results were reached.     

A scatter search methodology for the nurse rostering problem

The benefits of automating the nurse scheduling process in hospitals include reducing the planning workload and associated costs and being able to create higher quality and more flexible schedules. This has become more important recently in order to retain nurses and to attract more people into the profession. Better quality rosters also reduce fatigue and stress due to overwork and poor scheduling and help to maximise the use of leisure time by satisfying more requests. A more contented workforce will lead to higher productivity, increased quality of patient service and a better level of healthcare. This paper presents a scatter search approach for the problem of automatically creating nurse rosters. Scatter search is an evolutionary algorithm, which has been successfully applied across a number of problem domains. To adapt and apply scatter search to nurse rostering, it was necessary to develop novel implementations of some of scatter search's subroutines. The algorithm was then tested on publicly available real-world benchmark instances and compared against previously published approaches. The results show the proposed algorithm is a robust and effective method on a wide variety of real-world instances.     

A hybrid scatter search/electromagnetism meta-heuristic for project scheduling

In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics.     

A systematic two phase approach for the nurse rostering problem

Nurse rostering is an NP-hard combinatorial problem which makes it extremely difficult to efficiently solve real life problems due to their size and complexity. Usually real problem instances have complicated work rules related to safety and quality of service issues in addition to rules about quality of life of the personnel. For the aforementioned reasons computer supported scheduling and rescheduling for the particular problem is indispensable. The specifications of the problem addressed were defined by the First International Nurse Rostering Competition (INRC2010) sponsored by the leading conference in the Automated Timetabling domain, PATAT-2010. Since the competition imposed quality and time constraint requirements, the problem instances were partitioned into sub-problems of manageable computational size and were then solved sequentially using Integer Mathematical Programming. A two phase strategy was implemented where in the first phase the workload for each nurse and for each day of the week was decided while in the second phase the specific daily shifts were assigned. In addition, local optimization techniques for searching across combinations of nurses’ partial schedules were also applied. This sequence is repeated several times depending on the available computational time. The results of our approach and the submitted software produced excellent solutions for both the known and the hidden problem instances, which in respect gave our team the first position in all tracks of the INRC-2010 competition.     

A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern

The integrated vehicle-crew-roster problem with days-off pattern aims to simultaneously determine minimum cost vehicle and daily crew schedules that cover all timetabled trips and a minimum cost roster covering all daily crew duties according to a pre-defined days-off pattern. This problem is formulated as a new integer linear programming model and is solved by a heuristic approach based on Benders decomposition that iterates between the solution of an integrated vehicle-crew scheduling problem and the solution of a rostering problem. Computational experience with data from two bus companies in Portugal and data from benchmark vehicle scheduling instances shows the ability of the approach for producing a variety of solutions within reasonable computing times as well as the advantages of integrating the three problems.     

Workforce staffing and scheduling: Hospital nursing specific models

Decisions relating to hospital nurse staffing and scheduling are among the most important decisions made in hospitals today. Staffing and scheduling choices must be made which will result in timely and high-quality care to patients. These choices are complicated by the requirement for round-the-clock staffing in many hospital nursing units, a severe nursing shortage, and an outcry from many quarters to cut costs of health care. In general, patients today are kept in hospitals only if they are in need of highly skilled nursing care. In this paper we present a review of some of the issues in health care currently influencing the hospital nurse staffing and scheduling environment. In addition, we review the literature that illustrates nurse manager's concerns, and approaches taken in the past by operations researchers to address those concerns. We present some data from a recent study of nurse managers in 31 hospitals that illustrates the complexity of the issues. We conclude with a discussion of future research directions in hospital nurse staffing and scheduling.     

Locally Optimized Crossover for the Traveling Umpire Problem

This paper presents a genetic algorithm (GA) to solve the Traveling Umpire Problem, which is a recently introduced sports scheduling problem that is based on the most important features of the real Major League Baseball umpire scheduling problem. In our GA, contrary to the traditional way of randomly obtaining new solutions from parent solutions, we obtain partially optimized solutions with a Locally Optimized Crossover operator. This operator also presents a link between the evolutionary mechanism on a population of solutions and the local search on a single solution. We present improved results over other methods on benchmark instances.     

A comparison of two approaches to nurse rostering problems

Despite decades of research into automated methods for nurse rostering and some academic successes, one may notice that there is no consistency in the knowledge that has been built up over the years and that many healthcare institutions still resort to manual practices. One of the possible reasons for this gap between the nurse rostering theory and practice is that often the academic community focuses on the development of new techniques rather than developing systems for healthcare institutions. In addition, methods suitable for one problem are usually not easily transferable to other problems. In real-world healthcare environments, a personnel manager cannot afford to model a problem and construct a roster using available approaches in order to quantitatively determine which one suits best. There is a lack of criteria for the comparison of approaches to provide a clear picture about their advantages and disadvantages and therefore their suitability to a problem in hand. This paper introduces seven criteria: expressive power, flexibility, algorithmic power, learning capabilities, maintenance, rescheduling capabilities, and parameter tuning, that may offer guidance to researchers and developers of systems for nurse rostering. Two approaches to nurse rostering, which are of very different nature, are evaluated and compared against the introduced criteria. One approach is based on meta-heuristics, while the other employs case-based reasoning.     

A matheuristic approach for solving a home health care problem

We deal with a Home Health Care Problem (HHCP) which objective consists in constructing the optimal routes and rosters for the health care staffs. The challenge lies in combining aspects of vehicle routing and staff rostering which are two well known hard combinatorial optimization problems. To solve this problem, we initially propose an integer linear programming formulation (ILP) and we tested this model on small instances. To deal with larger instances we develop a matheuristic based on the decomposition of the ILP formulation into two problems. The first one is a set partitioning like problem and it represents the rostering part. The second problem consists in the routing part. This latter is equivalent to a Multi-depot Traveling Salesman Problem with Time Windows (MTSPTW).     

Integer programming model extensions for a multi-stage nurse rostering problem

Annals of Operations Research - In the variant of the well studied nurse rostering problem proposed in the Second International Nurse Rostering Competition, multiple stages have to be solved...     

Adaptive neighborhood search for nurse rostering

This paper presents an adaptive neighborhood search method (ANS) for solving the nurse rostering problem proposed for the First International Nurse Rostering Competition (INRC-2010). ANS uses jointly two distinct neighborhood moves and adaptively switches among three intensification and diversification search strategies according to the search history. Computational results assessed on the three sets of 60 competition instances show that ANS improves the best known results for 12 instances while matching the best bounds for 39 other instances. An analysis of some key elements of ANS sheds light on the understanding of the behavior of the proposed algorithm.     

A Neural Network Application in Personnel Scheduling

In this paper, we present and evaluate a neural network model for solving a typical personnel-scheduling problem, i.e. an airport ground staff rostering problem. Personnel scheduling problems are widely found in servicing and manufacturing industries. The inherent complexity of personnel scheduling problems has normally resulted in the development of integer programming-based models and various heuristic solution procedures. The neural network approach has been admitted as a promising alternative to solving a variety of combinatorial optimization problems. While few works relate neural network to applications of personnel scheduling problems, there is great theoretical and practical value in exploring the potential of this area. In this paper, we introduce a neural network model following a relatively new modeling approach to solve a real rostering case. We show how to convert a mixed integer programming formulation to a neural network model. We also provide the experiment results comparing the neural network method with three popular heuristics, i.e. simulated annealing, Tabu search and genetic algorithm. The computational study reveals some potential of neural networks in solving personnel scheduling problems.     

Patrol scheduling in urban rail network

This paper presents the problem of scheduling security teams to patrol a mass rapid transit rail network of a large urban city. The main objective of patrol scheduling is to deploy security teams to stations of the network at varying time periods subject to rostering as well as security-related constraints. We present several mathematical programming models for different variants of this problem. To generate randomized schedules on a regular basis, we propose injecting randomness by varying the start time and break time for each team as well as varying the visit frequency and visit time for each station according to their reported vulnerability. Finally, we present results for the case of Singapore mass rapid transit rail network and synthetic instances.     

Long-term staffing based on qualification profiles

Manpower still is one of the most expensive resources, in spite of increasing automation. While employee scheduling and rostering has been the topic of extensive research over the past decades, usually it is assumed that the demand for staff is either given or can be obtained without difficulty. In this research we provide an integer programming model for long-term staffing decisions which fits to the needs of manufacturing-to-order companies. The model is based on qualification profiles, the number of which grows exponentially in terms of the number of processes considered. In order to compute tight lower bounds we provide a column generation technique. The subproblem is a shortest path problem in a network where the arcs have multiple weights. Upper bounds, that is, feasible solutions are calculated by means of local search. We present computational results for randomly generated instances and empirical results for examples from practice. The results show that substantial cost savings can be achieved.     

An electromagnetic meta-heuristic for the nurse scheduling problem

In this paper, we present a novel meta-heuristic technique for the nurse scheduling problem (NSP). This well-known scheduling problem assigns nurses to shifts per day maximizing the overall quality of the roster while taking various constraints into account. The problem is known to be NP-hard. Due to its complexity and relevance, many algorithms have been developed to solve practical and often case-specific models of the NSP. The huge variety of constraints and the several objective function possibilities have led to exact and meta-heuristic procedures in various guises, and hence comparison and state-of-the-art reporting of standard results seem to be a utopian idea. We present a meta-heuristic procedure for the NSP based on the framework proposed by Birbil and Fang (J. Glob. Opt. 25, 263–282, 2003). The Electromagnetic (EM) approach is based on the theory of physics, and simulates attraction and repulsion of sample points in order to move towards a promising solution. Moreover, we present computational experiments on a standard benchmark dataset, and solve problem instances under different assumptions. We show that the proposed procedure performs consistently well under many different circumstances, and hence, can be considered as robust against case-specific constraints.