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 there is no known algorithm that 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.

To help test and develop the algorithms we have compiled a diverse and challenging collection of benchmark test instances from various sources including industrial collaborators and scientific publications. The data sets are categorised into two groups: Shift scheduling problems and tour/sub-daily scheduling problems. In the shift scheduling problems the planning period 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 such as 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 modelled using Staff Roster Solutions' xml based modelling format. It is a flexible format which handles the range of rules and requirements found in different workplaces. The data files can also be read by Staff Roster Solutions' modelling software - Roster Booster. Roster Booster is a graphical user interface which can be used to create and test new instances and solutions. It also contains solvers for creating optimal and near optimal rosters and calculating lower bounds for instances.

See also:

• - A spreadsheet of published results and papers under review.
• - Lower bounds.
• - A formal description and model for the BCV instances (a zip file containing all the BCV instances is available here).

*proven optimal solution