A graph-based formulation for the shift rostering problem

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)


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.

Originele taal-2Engels
Pagina's (van-tot)285-300
Aantal pagina's16
TijdschriftEuropean Journal of Operational Research
Nummer van het tijdschrift1
StatusGepubliceerd - 1 jul 2020
Extern gepubliceerdJa

Vingerafdruk Duik in de onderzoeksthema's van 'A graph-based formulation for the shift rostering problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit