Annals of Computer Science and Information Systems, Volume 11

DOI: http://dx.doi.org/10.15439/2017F237

Citation: Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 11, pages 407–414 (2017)

Full text

Abstract. Nurse rostering problems are typically too large and hard to be solved exactly. In order to achieve quality solutions to these difficult problems, meta-heuristics are often employed. One such meta-heuristic is Ant Colony Optimisation (ACO), inspired by the pheromone trails left by ants. ACO works by guiding a heuristic solution construction by using these pheromones to direct weighted random choices. When the problem to be solved is highly constrained, finding feasible solutions is difficult, which can result in poor performance for ACO. To address this, we propose an ACO algorithm using an integer programming based solution construction method to ensure feasibility and select from a collection of schedules. The approach also uses a novel solution merging step that combines the information from multiple ants to generate a better final roster. We discuss several challenges inherent in this approach, and how they may be overcome. Computational results on highly constrained nurse rostering problem instances from the literature demonstrate the effectiveness of our proposed new hybrid metaheuristic.

References

1. A. T. Ernst, H. Jiang, M. Krishnamoorthy, and D. Sier, “Staff scheduling and rostering: A review of applications, methods and models,” European Journal of Operational Research, vol. 153, no. 1, pp. 3–27, Feb. 2004. http://dx.doi.org/10.1016/S0377-2217(03)00095-X
2. J. Van den Bergh, J. Belien, P. De Bruecker, E. Demeulemeester, and L. De Boeck, “Personnel scheduling: A literature review,” European Journal of Operational Research, vol. 226, no. 3, pp. 367–385, May 2013. http://dx.doi.org/10.1016/j.ejor.2012.11.029
3. M. Dorigo and T. Stutzle, “The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances,” in Handbook of Metaheuristics, ser. International Series in Operations Research & Management Science, F. Glover and G. A. Kochenberger, Eds. Springer US, 2003, no. 57, pp. 250–285. ISBN 978-1-4020-7263-5 978-0-306-48056-0. http://dx.doi.org/10.1007/0-306-48056-5_9
4. W. J. Gutjahr and M. S. Rauner, “An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria,” Computers & Operations Research, vol. 34, no. 3, pp. 642–666, Mar. 2007. http://dx.doi.org/10.1016/j.cor.2005.03.018
5. J. j. Wu, Y. Lin, Z. h. Zhan, W. n. Chen, Y. b. Lin, and J. y. Chen, “An Ant Colony Optimization Approach for Nurse Rostering Problem,” in 2013 IEEE International Conference on Systems, Man, and Cybernetics, Oct. 2013, pp. 1672–1676. http://dx.doi.org/10.1109/SMC.2013.288
6. B. Meyer, “Hybrids of Constructive Metaheuristics and Constraint Programming: A Case Study with ACO,” in Hybrid Metaheuristics, ser. Studies in Computational Intelligence, D. C. Blum, D. M. J. B. Aguilera, D. A. Roli, and D. M. Sampels, Eds. Springer Berlin Heidelberg, 2008, no. 114, pp. 151–183. ISBN 978-3-540-78294-0 978-3-540-78295-7. http://dx.doi.org/10.1007/978-3-540-78295-7_6
7. M. Khichane, P. Albert, and C. Solnon, “Integration of ACO in a Constraint Programming Language,” in SpringerLink. Springer, Berlin, Heidelberg, Sep. 2008, pp. 84–95. http://dx.doi.org/10.1007/978-3-540-87527-7_8
8. D. Thiruvady, A. Ernst, and M. Wallace, “A Lagrangian-ACO matheuristic for car sequencing,” EURO Journal on Computational Optimization; Heidelberg, vol. 2, no. 4, pp. 279–296, Nov. 2014. http://dx.doi.org/10.1007/s13675-014-0023-6
9. D. Thiruvady, G. Singh, and A. T. Ernst, “Hybrids of Integer Programming and ACO for Resource Constrained Job Scheduling,” in Hybrid Metaheuristics. Springer, Cham, Jun. 2014, pp. 130–144, http://dx.doi.org/10.1007/978-3-319-07644-7_10. http://dx.doi.org/10.1007/ 978-3-319-07644-7_10
10. S. Al-Shihabi, “A hybrid of maxâĂŞmin ant system and linear programming for the k-covering problem,” Computers & Operations Research, vol. 76, pp. 1–11, Dec. 2016. http://dx.doi.org/10.1016/j.cor.2016.06.006
11. H. Li, A. Lim, and B. Rodrigues, “A Hybrid AI Approach for Nurse Rostering Problem,” in Proceedings of the 2003 ACM Symposium on Applied Computing, ser. SAC ’03. New York, NY, USA: ACM, 2003. ISBN 978-1-58113-624-1 pp. 730–735. http://dx.doi.org/10.1145/952532.952675
12. C. Valouxis and E. Housos, “Hybrid optimization techniques for the workshift and rest assignment of nursing personnel,” Artificial Intelligence in Medicine, vol. 20, no. 2, pp. 155–175, Oct. 2000. http://dx.doi.org/10.1016/S0933-3657(00)00062-2
13. E. K. Burke, J. Li, and R. Qu, “A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems,” European Journal of Operational Research, vol. 203, no. 2, pp. 484–493, Jun. 2010. http://dx.doi.org/10.1016/j.ejor.2009.07.036
14. M. Stolevik, T. E. Nordlander, A. Riise, and H. Froyseth, “A Hybrid Approach for Solving Real-World Nurse Rostering Problems,” in Principles and Practice of Constraint Programming CP 2011. Springer, Berlin, Heidelberg, Sep. 2011, pp. 85–99. http://dx.doi.org/10.1007/978-3-642-23786-7_9
15. J. Puchinger and G. R. Raidl, “Combining Metaheuristics and Exact Algorithms in Combinatorial Optimization: A Survey and Classification,” in Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach. Springer, Berlin, Heidelberg, Jun. 2005, pp. 41–53. http://dx.doi.org/10.1007/11499305_5
16. B. Cheang, H. Li, A. Lim, and B. Rodrigues, “Nurse rostering problems - a bibliographic survey,” European Journal of Operational Research, vol. 151, no. 3, pp. 447–460, Dec. 2003. http://dx.doi.org/10.1016/S0377-2217(03)00021-3
17. E. K. Burke, P. D. Causmaecker, G. V. Berghe, and H. V. Landeghem, “The State of the Art of Nurse Rostering,” Journal of Scheduling, vol. 7, no. 6, pp. 441–499, Nov. 2004. http://dx.doi.org/10.1023/B:JOSH.0000046076.75950.0b
18. M. J. Brusco and L. W. Jacobs, “Cost analysis of alternative formulations for personnel scheduling in continuously operating organizations,” European Journal of Operational Research, vol. 86, no. 2, pp. 249–261, Oct. 1995. http://dx.doi.org/10.1016/0377-2217(94)00063-I
19. E. K. Burke, T. Curtois, G. Post, R. Qu, and B. Veltman, “A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem,” European Journal of Operational Research, vol. 188, no. 2, pp. 330–341, Jul. 2008. http://dx.doi.org/10.1016/j.ejor.2007.04.030
20. U. Aickelin and K. A. Dowsland, “An indirect Genetic Algorithm for a nurse-scheduling problem,” Computers & Operations Research, vol. 31, no. 5, pp. 761–778, Apr. 2004. http://dx.doi.org/10.1016/S0305-0548(03)00034-0
21. P. Brucker, E. K. Burke, T. Curtois, R. Qu, and G. V. Berghe, “A shift sequence based approach for nurse scheduling and a new benchmark dataset,” Journal of Heuristics, vol. 16, no. 4, pp. 559–573, Nov. 2008. http://dx.doi.org/10.1007/s10732-008-9099-6
22. T. Curtois and R. Qu, “New computational results for nurse rostering benchmark instances,” 2014. http://www.cs.nott.ac.uk/~psztc/new_computational_results_for_nurse_rostering_benchmark_instances.pdf
23. E. K. Burke and T. Curtois, “New approaches to nurse rostering benchmark instances,” European Journal of Operational Research, vol. 237, no. 1, pp. 71–81, Aug. 2014. http://dx.doi.org/10.1016/j.ejor.2014.01.039
24. E. Demirovic, N. Musliu, and F. Winter, “Modeling and Solving Staff Scheduling with Partial Weighted maxSAT,” in PATAT 2016: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling, Udine, Italy, Aug. 2016.
25. A. J. Mason and M. C. Smith, “A Nested Column Generator for solving Rostering Problems with Integer Programming,” in L. Caccetta; K. L. Teo; P. F. Siew; Y. H. Leung; L. S. Jennings, and V. Rehbock (eds.), Curtin University of Technology, Perth, Australia, Apr. 1998, pp. 827–834.
26. A. Dohn and A. Mason, “Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation,” European Journal of Operational Research, vol. 230, no. 1, pp. 157–169, Oct. 2013. http://dx.doi.org/10.1016/j.ejor.2013.03.018
27. C. Ansotegui, F. Didier, and J. Gabas, “Exploiting the Structure of Unsatisfiable Cores in MaxSAT,” in Proceedings of the 24th International Conference on Artificial Intelligence, ser. IJCAI’15. Buenos Aires, Argentina: AAAI Press, 2015. ISBN 978-1-57735-738-4 pp. 283–289.