A graph-based formulation for the shift rostering problem

David Lai, Janny M.Y. Leung, Wout Dullaert, Inês Marques

Research output: Contribution to JournalArticleAcademicpeer-review

486 Downloads (Pure)


This paper investigates a shift rostering problem – the assignment of staff to shifts over a planning horizon such that work rules are observed. Traditional integer-programming models are not able to solve shift rostering problems effectively for large number of staff and feasible shift patterns. We formulate work rules in terms of newly-proposed prohibited meta-sequences and resource constraints. A graph-based formulation and a specialized graph construction algorithm are proposed where the set of feasible shift patterns is represented by paths of a graph. The formulation size depends on the structure of the work-rule constraints and is independent of the number of staff. This approach results in smaller networks allowing large-scale rostering problems with hard constraints to be solved efficiently using standard commercial solvers. Moreover, it allows finding multiple optimal solutions which are beneficial for managerial decision makers. Computational results show that the proposed approach can obtain new best-known solutions and identify proven optimal solutions for almost all NSPLIB instances at significantly lower CPU times.
Original languageEnglish
Pages (from-to)285-300
Number of pages16
JournalEuropean Journal of Operational Research
Issue number1
Early online date16 Dec 2019
Publication statusPublished - 1 Jul 2020


  • Human resource planning
  • Network model
  • Personnel rostering
  • Scheduling
  • Shift rostering


Dive into the research topics of 'A graph-based formulation for the shift rostering problem'. Together they form a unique fingerprint.

Cite this