Nurse Rostering

Select By Year:

Select By Subject Area:

Google Scholar

You can also find out about my published research on Google Scholar, which, as well as providing links to the papers and their abstracts, additionally provides the latest citation counts and index values.

Overview

My research career began when my wife, Nicolette, took over responsibility for working out the staff rosters for the hospital ward in which she worked. At the time I was studying computing at university and I thought it would be easy enough to write a program to generate the rosters automatically. Little did I know what complexity lay hidden in this apparently simple problem, a problem that someone with sufficient knowledge could solve by hand in a couple of hours or so. For it was not enough simply to put the right number of nurses on duty for each of the three daily shifts. You also had to satisfy, as closely as possible, each nurse’s preference for working certain shifts on certain days, and for having certain days off. Usually it was impossible to satisfy all these preferences and also provide sufficient staff coverage for each shift. Instead the task was to find a solution that provided safe and legal staffing levels and satisfied as many as possible of the nurse preferences. Although I did not know it at the time, these kinds of problems had already been studied in the operations research and artificial intelligence research communities. Instead of looking there, I made up my own algorithm, which involved roughly assigning each nurse a set of shifts and then trying to improve the answer by swapping shifts between nurses until no further improvement was possible. This followed the way that Nicolette and her colleagues already tackled the problem. But in the world of computer science it turned out that I had created a local search algorithm.

I found solving this problem so fascinating that I could think of little else. And then I discovered I could spend another year at university and turn my work on rostering into an honours research project. This resulted in the pubication of my first thesis: An Enhanced Local Search Algorithm for Nurse Rostering in 1995. I then wrote a series of papers that elaborated the work in the thesis and enrolled in a PhD in artificial intelligence. For it turned out the nurse rostering problem is an example of a larger class of over-constrained constraint satisfaction problems that are of great interest to the artificial intelligence research community. At this point I became involved in the much broader area of developing algorithms to solve any kind of constraint satisfaction problem, rather than writing specialised algorithms to solve specialised problems, like the rostering problem. Nevertheless nurse rostering still figured as a test bed for the various algorithms I was working with in my PhD thesis, and it was one of these constraint weighting algorithms that ended up generating the rosters for a ward on the Gold Coast Hospital for a number of years – until Nicolette moved onward and upward in her career.

2000

Thornton, J. R. (2000). Contraint Weighting Local Search for Constraint Satisfaction. PhD Thesis, School of Computing and Information Technology, Griffith University, Brisbane, Australia, pp. 160.

Abstract: One of the challenges for the constraint satisfaction community has been to develop an automated approach to solving Constraint Satisfaction Problems (CSPs) rather than creating specific algorithms for specific problems. Much of this work has concentrated on the development and improvement of general purpose backtracking techniques. However, the success of relatively simple local search techniques on larger satisfiability problems [Selman et al. 1992] and CSPs such as the n-queens [Minton et al. 1992] has caused interest in applying local search to constraint satisfaction. In this thesis we look at the usefulness of constraint weighting as a local search technique for constraint satisfaction. The work is based on the clause weighting ideas of Selman and Kautz [1993] and Morris [1993] and applies, evaluates and extends these ideas from the satisfiability domain to the more general domain of CSPs. Specifically, the contributions of the thesis are:

The introduction of a local search taxonomy. We examine the various better known local search techniques and recognise four basic strategies: restart, randomness, memory and weighting.
The extension of the CSP modelling framework. In order to represent and efficiently solve more realistic problems we extend the CSP modelling framework to include array-based domains and array-based domain use constraints.
The empirical evaluation of constraint weighting. We compare the performance of three constraint weighting strategies on a range of CSP and satisfiability problems and with several other local search techniques. We find that no one technique dominates in all problem domains.
The characterisation of constraint weighting performance. Based on our empirical study we identify the weighting behaviours and problem features that favour constraint weighting. We conclude weighting does better on structured problems where the algorithm can recognise a harder sub-group of constraints.
The extension of constraint weighting. We introduce an efficient arc weighting algorithm that additionally weights connections between constraints that are simultaneously violated at a local minimum. This algorithm is empirically shown to outperform standard constraint weighting on a range of CSPs and within a general constraint solving system. Also we look at combining constraint weighting with other local search heuristics and find that these hybrid techniques can do well on problems where the parent algorithms are evenly matched.
The application of constraint weighting to over constrained domains. Our empirical work suggests constraint weighting does well for problems with distinctions between constraint groups. This led us to investigate solving real-world over constrained problems with hard and soft constraint groups and to introduce two dynamic constraint weighting heuristics that maintain a distinction between hard and soft constraint groups while still adding weights to violated constraints in a local minimum. In an empirical study, the dynamic schemes are shown to outperform other fixed weighting and non-weighting systems on a range of real world problems. In addition, the performance of weighting is shown to degrade less severely when soft constraints are added to the system, suggesting constraint weighting is especially applicable to realistic, hard and soft constraint problems.

1998

Thornton, J. R., & Sattar, A. (1998). Dynamic Constraint Weighting for Over Constrained Problems. PRICAI 1998: 5th Pacific Rim International Conference on Artificial Intelligence, Lecture Notes in Computer Science, 1531, 377-388, Springer, ISSN 0302-9743.

1997

Thornton, J. R., & Sattar, A. (1997). Applied Partial Constraint Satisfaction Using Weighted Iterative Repair. AI 1997: 10th Australian Joint Conference on Artificial Intelligence, Lecture Notes in Computer Science, 1342. Springer, ISSN 0302-9743.

Thornton, J. R., & Sattar, A. (1997). Nurse Rostering and Integer Programming Revisited. In: ICCIMA 1997: Proceedings of the International Conference on Computational Intelligence and Multimedia Applications, Griffith University, pp. 49-58.

1996

Thornton, J. R., & Sattar, A. (1996). An Integer Programming-Based Nurse Rostering System. In ASIAN 1996: 2nd Asian Computing Science Conference, Lecture Notes in Computer Science, 1179, 357-358, Springer, ISSN 0302-9743.

1995

Thornton, J. R. (1995). An Enhanced Cyclic Descent Algorithm for Nurse Rostering. Honours Thesis, Faculty of Engineering and Applied Science, Griffith University, Gold Coast, Australia, 145 pp.

Abstract: The study introduces an enhanced cyclic descent algorithm for nurse rostering. The algorithm is compared to four other rostering algorithms and to manually generated roster solutions obtained from the Gold Coast Hospital. Three criteria are developed with which the roster generation methods are assessed: these are roster schedule quality, roster shift allocation quality and execution time. A statistical analysis shows that the enhanced cyclic descent algorithm has the best overall performance. An integer linear programming algorithm and an enhanced simulated annealing algorithm are also shown to perform well with smaller problems.