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