Automatic scheduling of people and rooms
14 Jul 2015
Case Studies TechnologyOriginally posted at https://tech.labs.oliverwyman.com/blog/2015/07/14/automatic-scheduling-of-people-and-rooms/
So we’ve recently been doing some work for a large public-facing organisation regarding some of their issues with scheduling. They’ve got a large number of staff (tens of thousands) and a lot of locations (hundreds), and they need to do good scheduling for when/where members of the public should come in and talk to them. Now, at a small scale, this is just a matter of calendars and picking empty slots, and that can be done pretty easily manually with various off-the-shelf tools they’re already using for other purposes. Even once you start to factor in things like making sure you pick the right member of staff with the relevant experience, and pick the room with needed facilities (e.g. ground floor room for wheelchair accessibility), this is doable manually for a sufficiently skilled administrator who knows the local office.
This however starts to break down in several ways as you scale up. Firstly, it requires a person doing the scheduling, so self-service by the customer doesn’t happen, and you’ve either got a bottleneck around the staff member who knows everything about the office, or a variable quality of knowledge among a larger pool of people. Secondly, fair scheduling of tasks is hard to remember to do well without software support and especially in time-constrained instances, the favoured staff are more likely to get given additional appointments even if there’s someone less heavily loaded this week. Thirdly, rescheduling in the event of disruptive events (half your staff come down with norovirus), while maintaining fair scheduling and other such problems is hard, especially if the person that usually does the scheduling has caught the bug…
Therefore the obvious solution is to take the human factors out of the loop, or at least provide them with software support to guide them towards more optimal solutions. In fact, the field of Operations research is all about this sort of problem, with the Nurse scheduling problem being the particular type of problem we’re trying to solve. It’s a tricky one (in fact, it’s known to be NP-Hard), but that doesn’t mean we can’t use good heuristics to find us at least reasonable solutions to the problem, even if they’re technically sub-optimal.
We’ve been using an open-source general-purpose constraint satisfaction solver called OptaPlanner. It’s intended for all sorts of constraint problems, including the Nurse scheduling problem, but other examples include the Travelling salesman problem and the N-Queens problem. In general, provided you can define the problem domain and constraints clearly, it’s a good general-purpose tool for solving this sort of problem, and in open competitions it does very well (usually only being beaten by specialists in a very particular area).
You start by defining a series of Java objects that define the facts of the problem (literally referred to as “problem facts”) – so in our case, Agent (staff member), Room, Location, Booking (which specifies the fixed items about the booking such as it’s length and any requirements of the Agent or Room) – and some changeable entities (“planning entities”) – in this case, just BookingAssignment (which links a Booking to an Agent, Room and start date/time). You also provide a Solution object (AppointmentsSchedule) that contains a particular set of instances of planning entities that represent a particular possible solution – in our case, a series of possible BookingAssignments.
To this, we add a series of business rules that say which appointments we do and don’t like. This is written in the Drools rules language, and lets us specify both hard constraints (“anything that matches this is unusable”) and soft constraints (“we’d like this, but will accept solutions without it”), which let OptaPlanner score the different possible solutions.
The “when” section says which BookingAssignment’s match this rule, and the “then” section adds a hard constraint score to the items that match the “when” section. Note that it talks about “immovable bookings” which is how we model previously booked items v.s. new items that are being determined right now.
We also provide an XML configuration to OptaPlanner which sets up how to initialise things (i.e. how to make the first BookingAssignment to be tested), what search methods to use to find good solutions and how to generate “moves” which let you step from one solution to another possible one. OptaPlanner supports a wide variety of search algorithms, from Hill Climbing and Simulated Annealing, to more advanced solutions such as Step Counting Hill Climbing.
Overall we’ve been very happy with OptaPlanner. There’s been a few moments when it has output what appear to be very weird results, but after further inspection they turn out to make a lot of sense given the constraints that we’ve supplied (or that all the other options are really horrible for some other reason). Things that have helped this immensely are excellent documentation and a large collection of good examples, which for most problems means you can adapt approaches in an example to your specific problem domain.