The goal of the Nurse Scheduling Problem is to find an assignment of nurses to shifts according to specific requirements. Frequently, a computed schedule may become not usable because of sudden absences of some nurses. In this cases, Nurse Rescheduling amounts to the computation of a new schedule, which has to satisfy the original requirements and the new absences. Additionally, a good solution to the Nurse Rescheduling Problem must be as similar as possible to the original schedule, which practically means that the number of changes has to be minimized. This paper focuses on the requirements specified by an Italian hospital, and recently addressed by an approach based on Answer Set Programming (ASP). Even if promising results have been obtained with ASP, the original encoding presents some intrinsic weaknesses, which are identified and eventually circumvented in this paper. The new encoding is designed by taking into account both intrinsic properties of Nurse Scheduling and internal details of ASP solvers, such as cardinality and weight constraint propagators. The performance gain of clingo and wasp is empirically verified on instances from ASP literature. As an additional contribution, the performance of clingo and wasp is compared to other declarative frameworks, namely SAT and ILP; the best performance is obtained by clingo running the new ASP encoding. The advanced ASP encodings are then extended to solve Nurse Rescheduling, and an empirical evaluation is conducted with clingo and wasp.
Get full access to this article
View all access options for this article.
References
1.
AbíoI., StuckeyP.J., Encoding linear constraints into SAT. In
O’SullivanB., editor, CP, volume of LNCS, 2014, pp. 75–91. Springer. https://doi.org/10.1007/978-3-319-10428-7_9
2.
AbseherM., GebserM., MusliuN., SchaubT. and WoltranS., Shift design with answer set programming, Fundam Inform147(1) (2016), 1–25. https://doi.org/10.3233/FI-2016-1396
AlvianoM., FaberW., The complexity boundary of answer set programming with generalized atoms under the FLP semantics, In LPNMR volume 8148 of LNCS, 2013, pp. 67–72. Springer. http://dx.doiorg/10.1007/978-3-642-40564-8_7
AlvianoM., DodaroC., RiccaF., A MaxSAT Algorithm Using Cardinality Constraints of Bounded Size, In IJCAI 2015, 2015, pp. 2677–2683. AAAI Press.
8.
AlvianoM., DodaroC. and MarateaM., An advanced answer set programming encoding for nurse scheduling, In AI*IA, volume to appear, 2017.
9.
AudemardG., SimonL., Extreme cases in SAT problems. In
CreignouN. and BerreD.L., editors, SAT, volume 9710 of LNCS, 2016, pp. 87–103. Springer. https://doi.org/10.1007/978-3-319-40970-2_7
BalducciniM., GelfondM., WatsonR., NogueiraM., The USA-advisor: A case study in answer set planning, In LPNMR volume 2173 of LNCS, 2001, pp. 439–442. Springer. https://doi.org/10.1007/3-540-45402-0_39
12.
BardJ.F. and PurnomoH.W., Preference scheduling for nurses using column generation, European Journal of Operational Research164(2) (2005), 510–534. https://doi.org/10.1016/j.ejor.2003.06.046
13.
BardJ.F. and PurnomoH.W., Incremental changes in the workforce to accommodate changes in demand, Health Care Management Science9(1) (2006), 71–85. https://doi.org/10.1007/s10729-006-6281-y
14.
BäumeltZ., DvorákJ., SuchaP. and HanzálekZ., A novel approach for nurse rerostering based on a parallel algorithm, European Journal of Operational Research251(2) (2016), 624–639. https://doi.org/10.1016/j.ejor.2015.11.022
CalimeriF., GebserM., MarateaM. and RiccaF., Design and results of the fifth answer set programming competition, Artif Intell231 (2016), 151–181. https://doi.org/10.1016/j.artint.2015.09.008
20.
CeschiaS., ThanhN.D.T., CausmaeckerP.D., HaspeslaghS., Schaerf.A., Second international nurse rostering competition (INRC-II) – problem description and rules - . CoRR, abs/1501.04177, 2015. http://arxiv.org/abs/1501.04177
21.
ChanP., WeilG., Cyclical staff scheduling using constraint logic programming, In PATAT volume 2079 of LNCS, 2000, pp. 159–175. Springer. https://doi.org/10.1007/3-540-44629-X_10
22.
CheangB., LiH., LimA. and RodriguesB., Nurse rostering problems - a bibliographic survey, European Journal of Operational Research151(3) (2003), 447–460. https://doi.org/10.1016/S0377-2217(03)00021-3
23.
ClarkA., MouleP., ToppingA. and SerpellM., Rescheduling nursing shifts: Scoping the challenge and examining the potential of mathematical model based tools, Journal of Nursing Management23(4) (2015), 411–420. http://dx.doi.org/10.1111/jonm.12158
DodaroC., LeoneN., NardiB., RiccaF., Allotment problem in travel industry: A solution based on ASP, In RR volume 9209 of LNCS, 2015, pp. 77–92. Springer. https://doi.org/10.1007/978-3-319-22002-4_7
26.
DodaroC., GasteigerP., LeoneN., MusitschB., RiccaF. and SchekotihinK., Combining answer set programming and domain heuristics for solving hard industrial problems (application paper), TPLP16(5-6) (2016), 653–669. https://doi.org/10.1017/S1471068416000284
GavanelliM., NonatoM. and PeanoA., An ASP approach for the valves positioning optimization in a water distribution system, J Log Comput25(6) (2015), 1351–1369. https://doi.org/10.1093/logcom/ext065
GebserM., KaufmannB., KaminskiR., OstrowskiM., SchaubT. and SchneiderM.T., Potassco: The potsdam answer set solving collection, AI Commun24(2) (2011), 107–124. https://doi.org/10.3233/AIC-2011-0491
31.
GebserM., SchaubT., ThieleS. and VeberP., Detecting inconsistencies in large biological networks with answer set programming, TPLP11(2-3) (2011), 323–360. https://doi.org/10.1017/S1471068410000554
GebserM., KaminskiR., KaufmannB., OstrowskiM., SchaubT., WankoP., Theory solving made easy with clingo 5, In ICLP TCs volume 52 of OASICS, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, pp. 2:1–2:15. https://doi.org/10.4230/OASIcs.ICLP.2016.2
34.
GelfondM. and LifschitzV., Classical negation in logic programs and disjunctive databases, New Generation Comput9(3/4) (1991), 365–386.
GutjahrW.J. and RaunerM.S., An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria, Computers & OR34(3) (2007), 642–666. https://doi.org/10.1016/j.cor.2005.03.018
37.
HaspeslaghS., CausmaeckerP.D., SchaerfA. and StølevikM., The first international nurse rostering competition 2010, Annals OR218(1) (2014), 221–236. https://doi.org/10.1007/s10479-012-1062-0
38.
KitadaM. and MorizawaK., A heuristic method for nurse rerostering problem with a sudden absence for several consecutive days, International Journal of Emerging Technology and Advanced Engineering3(11) (2013), 353–361.
39.
KoponenL., OikarinenE., JanhunenT. and SäiläL., Optimizing phylogenetic supertrees using answer set programming, TPLP15(4-5) (2015), 604–619. https://doi.org/10.1017/S1471068415000265
40.
MaenhoutB. and VanhouckeM., An evolutionary approach for the nurse rerostering problem, Computers & OR38(10) (2011), 1400–1411. https://doi.org/10.1016/j.cor.2010.12.012
41.
MaenhoutB., VanhouckeM., An artificial immune system based approach for solving the nurse re-rostering problem, In EvoCOP 2013 volume 7832 of LNCS, 2013, pp. 97–108. Springer. https://doi.org/10.1007/978-3-642-37198-1_9
42.
MarileoM.C. and BertossiL.E., The consistency extractor system: Answer set programs for consistent query answering in databases, Data Knowl Eng69(6) (2010), 545. https://doi.org/10.1016/j.datak.2010.01.005
43.
MillerH.E., PierskallaW.P. and RathG.J., Nurse scheduling using mathematical programming, Operations Research24(5) (1976), 857–870. https://doi.org/10.1287/opre.24.5.857
44.
MorgadoA., DodaroC., Marques-SilvaJ., Core-Guided MaxSAT with Soft Cardinality Constraints, In CP volume 8656 of LNCS, 2014, pp. 564–573. Springer. https://doi.org/10.1007/978-3-319-10428-7_41
45.
MozM. and PatoM.V., Solving the problem of rerostering nurse schedules with hard constraints: New multicommodity flow models, Annals OR128(1-4) (2004), 179–197. https://doi.org/10.1023/B:ANOR.0000019104.39239.ed
MutingiM. and MbohwaC., The nurse rerostering problem: An explorative study, In International Conference on Industrial Engineering and Operations Management (IEOM), 2017. http://ieomsociety.org/ieom2017/papers/563.pdf
48.
PatoM.V. and MozM., Solving a biobjective nurse rerostering problem by using a utopic pareto genetic heuristic, J Heuristics14(4) (2008), 359–374. https://doi.org/10.1007/s10732-007-9040-4
49.
PhilippT., SteinkeP., Pblib - A library for encoding pseudo-boolean constraints into CNF, , In SAT volume 9340 of LNCS, 2015, pp. 9–16. Springer. https://doi.org/10.1007/978-3-319-24318-4_2
50.
RiccaF., GrassoG., AlvianoM., MannaM., LioV., IiritanoS. and LeoneN., Team-building with answer set programming in the gioiatauro seaport, TPLP12(3) (2012), 361–381. https://doi.org/10.1017/S147106841100007X
