Article ID: | iaor20082965 |
Country: | Germany |
Volume: | 155 |
Issue: | 1 |
Start Page Number: | 257 |
End Page Number: | 277 |
Publication Date: | Nov 2007 |
Journal: | Annals of Operations Research |
Authors: | Tsang Edward, Mills Patrick, Ford John, Bradwell Richard, Williams Richard, Scott Paul |
Keywords: | programming: constraints |
The profitability and morale of many organizations (such as factories, hospitals and airlines) are affected by their ability to schedule their personnel properly. Sophisticated and powerful constraint solvers such as ILOG, CHIP, ECliPSe, etc. have been demonstrated to be extremely effective on scheduling. Unfortunately, they require non-trivial expertise to use. This paper describes ZDC-rostering, a constraint-based tool for personnel scheduling that addresses the software crisis and fills a void in the space of solvers. ZDC-rostering is easier to use than the above constraint-based solvers and more effective than Microsoft's Excel Solver. ZDC-rostering is based on an open-source computer-aided constraint programming package called ZDC, which decouples problem formulation (or modelling) from solution generation in constraint satisfaction. ZDC is equipped with a set of constraint algorithms, including Extended Guided Local Search, whose efficiency and effectiveness have been demonstrated in a wide range of applications. Our experiments show that ZDC-rostering is capable of solving realistic-sized and very tightly-constrained problems efficiently. ZDC-rostering demonstrates the feasibility of applying constraint satisfaction techniques to solving rostering problems, without having to acquire deep knowledge in constraint technology.