Integer programming techniques for the nurse rostering problem

This work presents integer programming techniques to tackle the problem of the International Nurse Rostering Competition. Starting from a compact and monolithic formulation in which the current generation of solvers performs poorly, improved cut generation strategies and primal heuristics are proposed and evaluated. A large number of computational experiments with these techniques produced the following results: the optimality of the vast majority of instances was proved, the best known solutions were improved by up to 15 % and strong dual bounds were obtained. In the spirit of reproducible science, all code was implemented using the Computational Infrastructure for Operations Research.     

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 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.     

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 hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem

This paper is concerned with the development of intelligent decision support methodologies for nurse rostering problems in large modern hospital environments. We present an approach which hybridises heuristic ordering with variable neighbourhood search. We show that the search can be extended and the solution quality can be significantly improved by the careful combination and repeated use of heuristic ordering, variable neighbourhood search and back-tracking. The amount of computational time that is allowed plays a significant role and we analyse and discuss this. The algorithms are evaluated against a commercial Genetic Algorithm on commercial data. We demonstrate that this methodology can significantly outperform the commercial algorithm. This paper is one of the few in the scientific nurse rostering literature which deal with commercial data and which compare against a commercially implemented algorithm.     

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.     

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.     

Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem

Airline crew scheduling problem is a complex and difficult problem faced by all airline companies.To tackle this problem, it was often decomposed into two subproblems solved successively. First, the airline crew-pairing problem, which consists on finding a set of trips – called pairings – i.e. sequences of flights, starting and ending at a crew base, that cover all the flights planned for a given period of time. Secondly, the airline crew rostering problem, which consists on assigning the pairings found by solving the first subproblem, to the named airline crew members. For both problems, several rules and regulations must be respected and costs minimized.It is sure that this decomposition provides a convenient tool to handle the numerous and complex restrictions, but it lacks, however, of a global treatment of the problem. For this purpose, in this study we took the challenge of proposing a new way to solve both subproblems simultaneously. The proposed approach is based on a hybrid genetic algorithm. In fact, three heuristics are developed here to tackle the restriction rules within the GA’s process.     

Progress control in iterated local search for nurse rostering

This paper describes an approach in which a local search technique is alternated with a process which ‘jumps’ to another point in the search space. After each ‘jump’ a (time-intensive) local search is used to obtain a new local optimum. The focus of the paper is in monitoring the progress of this technique on a set of real world nurse rostering problems. We propose a model for estimating the quality of this new local optimum. We can then decide whether to end the local search based on the predicted quality. The fact that we avoid searching these bad neighbourhoods enables us to reach better solutions in the same amount of time. We evaluate the approach on five highly constrained problems in nurse rostering. These problems represent complex and challenging real world rostering situations and the approach described here has been developed during a commercial implementation project by ORTEC bv.     

Metaheuristics approach to the aircrew rostering problem

The solution of the aircrew-scheduling problem is represented by a set of rotations developed from a given set of flight segments. Once the set of rotations to be made by aircrew members has been determined, the air carrier must solve the aircrew rostering problem that entails the monthly assignment of aircrew members to planned rotations. This paper attempts to solve the aircrew rostering problem, thus constructing personalized monthly schedules using Simulated Annealing, Genetic Algorithms, and Tabu Search techniques. The developed models are tested on numerical examples that consist of constructing schedules for pilots. Dimensions of the considered examples are characteristic of small and medium-sized airlines.     

Local search neighbourhoods for dealing with a novel nurse rostering model

A novel nurse rostering model is developed to represent real world problem instances more accurately. The proposed model is generic in the sense that it allows modelling of essentially different problem instances. Novel local search neighbourhoods are implemented to take advantage of the problem properties represented by the model. These neighbourhoods are used in a variable neighbourhood search and in an adaptive large neighbourhood search algorithm. The performance of the solution method is evaluated empirically on real world data. The proposed model is open to further extensions for covering personnel planning problems in different sectors and countries.     

Mathematical programming based heuristics for improving LP-generated classifiers for the multiclass supervised classification problem

Mathematical programming is used as a nonparametric approach to supervised classification. However, mathematical programming formulations that minimize the number of misclassifications on the design dataset suffer from computational difficulties. We present mathematical programming based heuristics for finding classifiers with a small number of misclassifications on the design dataset with multiple classes. The basic idea is to improve an LP-generated classifier with respect to the number of misclassifications on the design dataset. The heuristics are evaluated computationally on both simulated and real world datasets.     

An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering

This paper proposes a new memetic evolutionary algorithm to achieve explicit learning in rule-based nurse rostering, which involves applying a set of heuristic rules for each nurse's assignment. The main framework of the algorithm is an estimation of distribution algorithm, in which an ant-miner methodology improves the individual solutions produced in each generation. Unlike our previous work (where learning is implicit), the learning in the memetic estimation of distribution algorithm is explicit, that is, we are able to identify building blocks directly. The overall approach learns by building a probabilistic model, that is, an estimation of the probability distribution of individual nurse–rule pairs that are used to construct schedules. The local search processor (ie the ant-miner) reinforces nurse–rule pairs that receive higher rewards. A challenging real-world nurse rostering problem is used as the test problem. Computational results show that the proposed approach outperforms most existing approaches. It is suggested that the learning methodologies suggested in this paper may be applied to other scheduling problems where schedules are built systematically according to specific rules.     

Metaheuristics approach for solving personalized crew rostering problem in public bus transit

The crew rostering problem in public bus transit aims at constructing personalized monthly schedules for all drivers. This problem is often formulated as a multi-objective optimization problem, since it considers the interests of both the management of bus companies and the drivers. Therefore, this paper attempts to solve the multi-objective crew rostering problem with the weighted sum of all objectives using ant colony optimization, simulated annealing, and tabu search methods. To the best of our knowledge, this is the first paper that attempts to solve the personalized crew rostering problem in public transit using different metaheuristics, especially the ant colony optimization. The developed algorithms are tested on numerical real-world instances, and the results are compared with ones solved by commercial solvers.     

A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems

This paper presents a hybrid multi-objective model that combines integer programming (IP) and variable neighbourhood search (VNS) to deal with highly-constrained nurse rostering problems in modern hospital environments. An IP is first used to solve the subproblem which includes the full set of hard constraints and a subset of soft constrains. A basic VNS then follows as a postprocessing procedure to further improve the IP’s resulting solutions. The satisfaction of the excluded constraints from the preceding IP model is the major focus of the VNS. Very promising results are reported compared with a commercial genetic algorithm and a hybrid VNS approach on real instances arising in a Dutch hospital. The comparison results demonstrate that our hybrid approach combines the advantages of both the IP and the VNS to beat other approaches in solving this type of problems. We also believe that the proposed methodology can be applied to other resource allocation problems with a large number of constraints.     

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.     

A multi-level bottleneck assignment approach to the bus drivers' rostering problem

The problem of finding a work assignment for drivers in a given time horizon, in such a way as to have an even distribution of the workload, is considered. This problem is formulated as a Multi-level Bottleneck Assignment Problem (MBA). The MBA problem is studied: it is shown that it is NP-complete and an asymptotically optimal algorithm is presented. Some computational results are illustrated which prove the efficiency of the algorithm.     

Decision functions for chain classifiers based on Bayesian networks for multi-label classification

Multi-label classification problems require each instance to be assigned a subset of a defined set of labels. This problem is equivalent to finding a multi-valued decision function that predicts a vector of binary classes. In this paper we study the decision boundaries of two widely used approaches for building multi-label classifiers, when Bayesian network-augmented naive Bayes classifiers are used as base models: Binary relevance method and chain classifiers. In particular extending previous single-label results to multi-label chain classifiers, we find polynomial expressions for the multi-valued decision functions associated with these methods. We prove upper boundings on the expressive power of both methods and we prove that chain classifiers provide a more expressive model than the binary relevance method.     

A formula for multiple classifiers in data mining based on Brandt semigroups

A general approach to designing multiple classifiers represents them as a combination of several binary classifiers in order to enable correction of classification errors and increase reliability. This method is explained, for example, in Witten and Frank (Data Mining: Practical Machine Learning Tools and Techniques, 2005, Sect. 7.5). The aim of this paper is to investigate representations of this sort based on Brandt semigroups. We give a formula for the maximum number of errors of binary classifiers, which can be corrected by a multiple classifier of this type. Examples show that our formula does not carry over to larger classes of semigroups.