Strategic roster planning and control using Mixed Integer Linear Programming with applications to health services and call centres

Submitting Institution

City University, London

Unit of Assessment

Mathematical Sciences

Summary Impact Type

Societal

Research Subject Area(s)

Information and Computing Sciences: Computation Theory and Mathematics
Medical and Health Sciences: Public Health and Health Services
Economics: Applied Economics


Download original

PDF

Summary of the impact

Poor staff rosters are at the heart of socially-unacceptable working patterns, inadequate rest times and increased levels of stress. They lead to poor productivity, low levels of engagement and additional costs associated with high levels of staff turnover and absenteeism. Research undertaken at City University London has harnessed the power of `Optimisation' techniques to assist managers to draw up good quality staff rosters in hospitals, call centres and other large workforce organisations. The state-of-the-art electronic rostering programme improves use of resources, reduces reliance on costly agency staff, reduces the risk of fines for breaching legal requirements such as the European Working Time Directive and leads to significant savings in the health and social care sectors.

Underpinning research

Rostering is necessary for the day-to-day operations of many organisations, particularly in the health and social care sectors. A roster informs the employer who is covering each required duty and informs the employee of their work schedule. The nature of rostering can be captured mathematically in the form of a constrained allocation problem. Nurse rostering in particular has become a classic problem and is one of a large family of problems which have been classified as being `Non-deterministic Polynomial-time (NP)-hard' in the field of Combinatorial Optimisation. This classification is key to selecting a suitable computational approach, as it determines whether large instances of the problem are likely to be solvable. For this reason the literature focuses on heuristic approaches, even though these may produce an incomplete or poor quality solution. In addition, these rosters can have a negative impact on people's well-being as the human aspect is ignored. City University London staff adopted an alternative approach based upon Optimisation techniques incorporating human factors, which provides a robust generic rostering solution procedure.

The staff rostering project brings together the expertise of Celia Glass (at City since 1999, now a Professor) and Dr Roger Knight, an expert in Call Centre Workforce Management who came to study with Glass for a PhD in 2005. The project began in 2005, although the origins of the approach are derived from Glass' earlier research on comparative algorithms where she studied the performance of contemporary heuristics, such as Simulated Annealing, Tabu Search and Genetic algorithms, to understand the relative performance on a range of combinatorial problems. Later she produced a parsimonious formulation of the problem and then exploited the relative simplicity of its solution space representation using an appropriate algorithm1,2. Knight's research question was whether a rostering programme could be driven for employee well-being. The challenge involved capturing the following competing imperatives: maintaining sufficient staffing levels to cover demand without incurring the additional costs associated with overstaffing or the use of agency staff; satisfying working practices and employment contracts; and having due regard for staff well-being and individual preferences.

Shift patterns can have a profound effect on well-being, especially if they include night shifts. Nonetheless, staff well-being had not previously featured within rostering software. Glass and Knight identified fatigue metrics from the Human Resources literature that would suitably capture staff well-being and used them in linear constraints within their rostering model. As it is not generally possible to satisfy all of the constraints simultaneously, the Lagrange multiplier approach was used to reduce selected constraints to soft goals with measurements of their violation. The Call Centre Rostering problem was then amenable to an Integer Linear Programming (ILP) formulation, albeit too slow to handle larger instances. The key advance was to capture succinctly the underlying features of call centre rostering in an implicit formulation which could then be used for optimisation3 4. Glass and Knight were thus able to produce a higher quality roster for benchmark real world call centre data than was found elsewhere in the literature or from available commercial rostering packages4.

Their primary achievement was to solve the problem to optimality, in the face of contrary claims in the literature that such large instances of this NP-hard problem could only be solved approximately. The quality objective relating to staff fatigue and workplace risk make the approach particularly attractive. An additional benefit arose from the counter-intuitive outcome of being able to minimise cost simultaneously so that there need be no quality-cost trade off3. Using the optimisation algorithm can provide a company with the cheapest possible roster which simultaneously offers the most employee-friendly low risk roster.

Armed with this general approach, Glass and Knight then addressed the most commonly-studied rostering problem in the literature, that of Nurse Rostering. They found that their approach adapted well4. To prove its veracity they focussed on producing a quality roster for three widely-publicised, open benchmark problems, which they solved to optimality5.

In 2008, they extended the research in response to various real world situations. Reformulation in each case produced a successful outcome and indicated the transferability of the implicit ILP approach. For trainee doctors, the additional features of fairness criteria, a longer time horizon and legal requirements were added to the roster optimiser. The working practice of using rotational rosters (rotas) in the NHS was reflected in an alternative variant of the ILP formulation. For care homes the different levels of expertise of nurses and carers and pre-existing shift patterns were accommodated by additional constraints.

There are two theoretical aspects which allow Glass and Knight's approach to handle larger problem instances than others. One is the depiction of the problem and its consequent representation in an implicit form, which vastly reduces the solution space. The other is the use of a Totally Unimodular constraint matrix in an ILP formulation, for which there are efficient algorithms. The existence of solutions which minimise the staffing costs of the roster without compromising quality could only arise within a(n originally) vast solution space. It is particularly rewarding that the optimisation approach is strong enough to find them.

Further insights relate to the importance of grounding the problem formulation firmly in context. For example, their nurse rostering algorithm takes account of month-on-month continuity, while the failure of earlier algorithms to do so provided poor solutions in practice5. The methodology also quantifies both the undesirable effects of a roster such as unconducive night shift patterns which affect both staff fatigue and workplace risk and the desirable effects from satisfying personal preferences and maintaining fairness between staff, both of which affect staff morale. This differentiates the work from both previous academic and other commercial approaches. The impact of the research flows from the robustness of the underpinning mathematical algorithm combined with a careful capturing of contextual aspects of the problem.

References to the research

1. Gerodimos A.E., Glass C.A. & Potts C.N. (2001) Scheduling of customized jobs on a single machine under item availability, IIE Transactions, 33(11), 975-984

 
 
 
 

2. Glass C.A. & Prugel-Bennett A. (2005) A polynomially searchable exponential neighbourhood for graph colouring, Journal of the Operational Research Society, 56(3), 324-330

 
 
 
 

3. Knight, R. A., (2008) Optimisation methods for staff scheduling and rostering: an employee-friendly approach. PhD thesis, City University London.

4. Glass C.A. & Knight R.A. (2013) Call centre tour scheduling with employee preferences, working paper, Cass Business School, City University London.

5. Glass C.A. & Knight R.A. (2010) The nurse rostering problem: A critical appraisal of the problem structure, European Journal of Operations Research, 202(2), 379-389

 
 
 
 

IIE Transactions, Journal of the Operational Research Society and European Journal of Operations Research are among the highest-rated journals in the field of operations research and apply a stringent peer-review process prior to accepting articles for publication.

Details of the impact

The underpinning research demonstrated how complex mathematical optimisation techniques can bring about significant positive impacts on the quality of rostering for staff and employers across areas as far-reaching as call centres, hospitals and care homes.

Call centres. Initially the impact was realised within the call centres at Scottish and Southern Energy (SSE). SSE had succeeded in strengthening its customer base substantially by 2008, due in large part to the high quality of its call centre agents. A sophisticated team-working system was being used, based on a complex rotational roster. Glass was approached "to assess the degree to which SSE's current rostering methodology is `employee friendly', and to offer a `health check' on workforce management practices"[1].Glass and Knight successfully adapted their implicit ILP optimiser methodology to handle the complexity of team-working, to accommodate fairness between staff and to improve night working arrangements and rest periods between shifts, in line with ergonomic guidelines [2]. The accuracy of the optimiser enabled them to match staff availability to requirements with 12% fewer staff, equivalent to a year-on-year saving of £5.5M p.a. At a follow-on meeting SSE confirmed that: "City's employee rostering approach fits well with our focus on Customer Experience ... it has the potential to keep employees happier while at the same time reducing employment costs."[3]

Doctor and nurse rostering in the NHS. Around the time of the SSE work, there were increasing concerns in the NHS with regard to the rostering of nurses and junior doctors and compliance with the newly-introduced European Working Time Directive (EWTD) and the New Deal. The importance of rostering was highlighted by the Royal College of Physicians' 2006 report [4] which identified a 35% reduction in fatigue factors of doctors achieved by good rota-making practice alone. As a result, Glass and Knight started to work on how City's optimiser could enhance the quality of rosters for both doctors and nurses in the NHS. Between 2008 and 2009 they worked with collaborators at two NHS hospitals: Dr Landau of Whittington Hospital, London and Dr Todd of the Horton Hospital, Oxfordshire.

Glass and Knight worked with Dr Landau to capture the challenge of rostering junior doctors in the Emergency Department. They developed optimised rosters with ergonomic features, within the NHS mode of rotational rolling rosters, known as rotas. Dr Landau was "delighted with the quality of the rotas and being able to quickly produce a rota for any number of doctors of different levels of seniority. We usually work from a long-standing template, but on this occasion we needed to accommodate an extra doctor into the rota, which is extremely difficult to do manually. In addition, it saves me the many hours of work it would otherwise take to produce a compliant rota." [5]

Dr Todd was responsible for rostering the Accident & Emergency Department's junior doctors. An initial four-month trial of the City software was undertaken in 2009. Dr Todd's evaluation is that "the new rosters produced for junior doctors accommodate most holiday requests and distribute fairly the number of hours worked, days on leave, weekends off and bank holidays, none of which are normally considered. The quality of the rosters is greatly improved by the fact that they are able to limit both number of consecutive night duties and the number of consecutive days while still covering the work and complying with the New Deal and EWTD. Feedback from Junior Doctors confirmed that the computer-generated rostering system helpfully improves on fixed rolling rotas." [6]

A 2011 report by the Economist Intelligence Unit [7] confirmed that City's nurse rostering software demonstrates improved quality and can accommodate flexible working. Dean Fathers, now Chair of Bassetlaw Primary Care Trust, testified that "City's system would help the NHS to avoid wasting resources and avoid hefty fines for non-compliance with regulations such as the Working Time Directive. Health sector employers are particularly vulnerable to litigation, given the long hours worked and the stressful conditions faced by many medical staff." Helen Young, Executive Clinical Director and Chief Nurse at NHS Direct, stated that inefficient rostering systems — manual or electronic — can result in financial penalties and clinical safety issues.

At this juncture, further research stopped temporarily due to the long-term sickness of Dr Knight and it resumed in 2011. In the intervening years, the NHS adopted so-called nurse e-rostering systems and the market is now dominated by a few large players. These have recently offered some automation but this is limited to heuristics with no account taken of the fatigue and risk aspects of a roster. Glass was approached by the Chief Executive of an NHS Trust in July 2013 seeking to investigate ways the City optimiser could be adopted to encourage better rostering practice.

Care homes have arguably the greatest need for automated rostering as almost all of the 18,000 care homes in the UK currently use labour-intensive manual rostering. In 2011 City started to collaborate with Ian Turner, currently National Chairman of the Registered Nursing Homes Association (RNHA), to develop a rostering system for care homes. A rudimentary system was trialled in 2012 by Turner's The Partnership in Care Group of nursing homes in Suffolk. As a result of feedback, an upgraded system, named Roster Care, was piloted in four additional nursing homes from June 2013 and received extremely positive feedback. The system has been found to save 12 days per year in staff time for producing rosters alone. Ian Turner observed: "This is a very exciting development for the care homes sector. The underlying software is good and we have worked closely on the user interface. Our staff have embraced the idea enthusiastically and they will certainly be looking to use it in our homes. ...the benefits offered by this innovation will apply equally across the whole sector. One of the key issues for us is that the majority of our staff work part-time and have other commitments, making rostering difficult for us. The idea that we can use this feature to our advantage through shift management and recruitment strategy has been a real eye-opener. Being able to prepare the roster so that it is fair to all staff, closely matches hourly requirements and also being able to juggle it in real time for unforeseen changes, helps us to ensure that quality of care is maintained at all times, our staff are not burnt out and that our budgets are being used as efficiently as possible." [8] The University is now exploring mechanisms for the commercialisation of Roster Care.

City's rostering software has already shown that it can make a significant impact in the health and welfare domain by improving outcomes in the NHS and social care sectors where all key stakeholders (organisations, employees and patients) are beneficiaries. It has improved the workforce planning and management of human resources in organisations where it has been trialled and piloted (the NHS and care homes); has demonstrated reduction in measurements of fatigue and risk (call centres and the NHS) and more conducive rosters to the satisfaction of staff (junior doctors and care homes); has demonstrated to the satisfaction of managers a new efficient way of implementing legislative changes affecting work patterns, hence reducing the number of fines (NHS); has been acclaimed for its cost-effectiveness and efficiency in delivering services through better matched staffing levels (all), for releasing staff time (doctors and care homes) and for its ability to reduce staff turnover through fairer rosters and more even workload (call centres and nurses); and challenged conventional wisdom over the benefits of e-rostering software for organisations (the NHS and care homes).

Sources to corroborate the impact

  1. Scottish and Southern Energy (June 2008) `Licence to Innovate' no 327.
  2. Glass, C. A. and Knight, R. A. (March 2009), Case study of employee-friendly rostering at Scottish and Southern Energy Business report for Scottish and Southern Energy, City University London.
  3. Scottish and Southern Energy and City University London project meeting 15th October 2009, minutes and progress report written 23rd October 2009.
  4. Horrocks, N. and Pounder, R. (2006) `Designing safer rotas for junior doctors (in the 48 hour week)', Table 7, Report of the Royal College of Physicians of London, ISBN 1-86016-288-6.
  5. Consultant, Emergency Department, Whittington Hospital, London, user feedback and testimony received April 2009.
  6. Associate Specialist in Emergency Medicine, Emergency Department, the Horton Hospital, Oxfordshire, user feedback and testimony, encompassing questionnaire feedback from junior doctors, 17 October 2013.
  7. Liz Hall (2011), Software that could save hospitals millions, Economist Intelligence Unit, Feature Report, pages: 22-24.
  8. National Chairman, Registered Nursing Homes Association, e-mails June and 20 October 2013.