Rostering complexity

The staff rostering problem is classified according to mathematical complexity theory as NP-Hard. For problems within this complexity group there is no known algorithm for finding provably optimal solutions within practical time limits. Theoretically there could be instances of the problem which the best known algorithms may take as long to solve as, say, the estimated age of the universe! In fact, whether an algorithm exists or not which can solve these problems in practical (polynomial) computation times is one of the major open questions in mathematics and computer science (P vs. NP). One of the reasons why these problems are so difficult to solve is due to their exponentially large search spaces (a search space is all the possible solutions for a particular instance). Consider a problem instance with 19 employees, 3 shift types and a planning horizon of 28 days. Even this relatively small instance has a search space of 10320 (one followed by 320 zeros). To put that into perspective, the estimated age of the universe is approximately a mere 1018 seconds and planet Earth is thought to contain around 1050 atoms. Both are tiny numbers in comparison to an average search space size.

Fortunately however, there are algorithms which can find optimal and near optimal solutions for these challenging problems very quickly (often within a few seconds). They just cannot guarantee an optimal solution on every possible instance. Also, even near optimal solutions are almost always much better than those produced by expert human planners.

How the solvers work

Different algorithms solve the problem in different ways but they all need to be able to differentiate between good rosters and bad rosters. The user provides the algorithms with the information to do this by modelling the problem using constraints and objectives. For example, there are usually laws and regulations related to night shifts, so the model may include a constraint which imposes a certain number of days rest after a series of night shifts. There may be constraints to ensure each employee gets their requested days off. There will be constraints to ensure there are the correct number of employees working during each shift, and so on. In most staff rostering problems though, there are so many conflicting constraints that if they all had to be satisfied then a feasible solution would not exist. Therefore, in practice, some of the constraints are relaxed by the user. These are called soft constraints or objectives. These soft constraints may also be given different priorities by using weights which are simply number values and the more important the constraint the higher the number. Using this information the algorithm can now differentiate between good and bad solutions. It does this by counting the number of violations within a solution of each soft constraint and multiplying these values by each constraint's weight and then adding it all up. This gives a score for each solution which represents its quality. The lower the score the better the roster as a low score indicates that most of the important constraints have been satisfied. A solution with a score of zero has no violations at all. As mentioned though, those perfect, zero-score rosters rarely exist due to the over-constrained nature of the problem. Instead the algorithms try to produce solutions with a score as close to zero as possible.

For more information on creating the model and the variety of constraints that can be used see the XML format documentation and the modelling FAQs.