Shift scheduling problems are found in a wide range of industries and settings. These include airlines, airports, armed forces, call/contact centres, emergency services (police, fire and ambulance crews), factories, healthcare (physicians and nurses), hospitality, retail, security personnel, transportation sector (train and bus drivers). Creating staff rosters is a challenging and time consuming process. In fact, it is known to belong to a mathematical class of problems (NP-Hard) considered intractable. Although no algorithm for this problem can guarantee optimal solutions in practical computation times, it is possible to generate rosters which are significantly better than those produced by an expert human planner, and in a fraction of the time. These models and algorithms are the focus of our research.

In order to test algorithms we have collected benchmark test instances from a number of scenarios around the world. These data sets are categorised into two groups: Shift scheduling problems and tour (sub-daily) scheduling problems. In the shift scheduling problems the planning period (scheduling horizon) is divided into time periods of one day. Each employee must then be assigned a day off or a particular shift (e.g. early shift, late shift, night shift etc) on each day (subject to all the constraints and objectives). In the tour scheduling problem, the planning period is typically split into much shorter time periods (e.g. 15 minutes) and each employee must be assigned a task (e.g. work, break etc) for each time period.

The benchmark instances and solutions are presented using xml. More information on the data format and model used for these rostering problems is available here. It is a very flexible model which allows it to be used in a wide range of scenarios and handle the range of regulations and requirements often unique to each organisation. The data files can also be read by Roster Booster. Roster Booster is a modelling tool which can be used to create and test new instances and solutions. It also contains the latest version of our rostering engine and solvers for creating optimal and near optimal rosters and calculating lower bounds for instances.

A further discussion on the benefits of automated scheduling is available here. A spreadsheet of published results (and papers under review) for these instances is available here. Lower bounds are available here.

*proven optimal solution