A graph-based formulation for the shift rostering problem
| Autor: | Wout Dullaert, Janny M. Y. Leung, David S.W. Lai, Inês Marques |
|---|---|
| Přispěvatelé: | Operations Analytics, Amsterdam Business Research Institute |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
SDG 16 - Peace Information Systems and Management General Computer Science Computer science Scheduling Graph based SDG 16 - Peace Justice and Strong Institutions Time horizon Management Science and Operations Research Justice and Strong Institutions Industrial and Manufacturing Engineering Graph Scheduling (computing) Network model Shift rostering Modeling and Simulation Graph (abstract data type) Human resource planning Personnel rostering |
| Zdroj: | Lai, D, Leung, J M Y, Dullaert, W & Marques, I 2020, ' A graph-based formulation for the shift rostering problem ', European Journal of Operational Research, vol. 284, no. 1, pp. 285-300 . https://doi.org/10.1016/j.ejor.2019.12.019 European Journal of Operational Research, 284(1), 285-300. Elsevier |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2019.12.019 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect