Schaus, Pierre
[UCL]
Régin, Jean-Charles
[Université de Nice-Sophia Antipolis]
Given a vector of finite domain variables, the spread constraint aims at minimizing the sum of squares of these variables while constraining the sum of these to be equal to a given value. We improve the existing filtering for spread achieving a bound-consistent filtering without increasing the complexity. Previous versions of the algorithm considered a relaxed version of the bound-consistency assuming interval domains defined on rational numbers rather than integers. We apply our new algorithm to a real-life problem: the daily assignment of newborn infant patients to nurses in a hospital. The objective is to balance the workload of the nurses, while satisfying a variety of side constraints. Prior work proposed a MIP model for this problem, which unfortunately did not scale to large instances and only approximated the objective function, since minimizing the variance cannot be expressed in a linear model. This paper presents a two-step approach, first assigning nurses to region of the hospital then assigning the patients to these nurses. We show that our approach allows to tackle large instances with hundreds of patients and nurses in a few seconds using the OscaR optimization system.
- Gorard Stephen, REVISITING A 90-YEAR-OLD DEBATE: THE ADVANTAGES OF THE MEAN DEVIATION, 10.1111/j.1467-8527.2005.00304.x
- Hentenryck Pascal Van, Michel Laurent, Nondeterministic Control for Hybrid Search, 10.1007/s10601-006-9005-5
- Ibaraki T, Katoh N (1988) Resource allocation problems: algorithmic approaches. The MIT Press, Cambridge
- Katoh N., Ibaraki T., Mine H., A Polynomial Time Algorithm for the Resource Allocation Problem with a Convex Objective Function, 10.1057/jors.1979.105
- Mullinax C, Lawley M, Assigning patients to nurses in neonatal intensive care, 10.1057/palgrave/jors/2601265
- OscaR Team (2012) OscaR: Scala in OR. https://bitbucket.org/oscarlib/oscar
- Pesant G (2008) Constraint-based rostering. In: Proceedings of the 7th international conference on the practice And theory of automated timetabling, Université de Montréal, 18–22 Aug 2008
- Pesant Gilles, Régin Jean-Charles, SPREAD: A Balancing Constraint Based on Statistics, Principles and Practice of Constraint Programming - CP 2005 (2005) ISBN:9783540292388 p.460-474, 10.1007/11564751_35
- Régin JC (1996) Generalized arc consistency for global cardinality constraint. In: AAAI-96, pp 209–215
- Schaus P (2009) Balancing and bin-packing constraints in constraint programming. PhD thesis, Université catholique de Louvain, INGI
- Schaus P, Deville Y, Dupont P, Régin J (2006) Simplification and extension of spread. In: 3rd workshop on constraint propagation and implementation
- Schaus P, Deville Y, Dupont P (2007a) Bound-consistent deviation constraint. In: 13th international conference on principles and practice of constraint programming (CP 2007), vol 4741
- Schaus P, Deville Y, Dupont P, Régin J (2007b) The deviation constraint. In: Proceedings of CP-AI-OR, vol 4510, pp 269–284
- Schaus Pierre, Van Hentenryck Pascal, Régin Jean-Charles, Scalable Load Balancing in Nurse to Patient Assignment Problems, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2009) ISBN:9783642019289 p.248-262, 10.1007/978-3-642-01929-6_19
- Shaw P (2004) A constraint for bin packing. In: Principles and practice of constraint programming CP 2004, pp 648–662
- Simonis Helmut, Models for Global Constraint Applications, 10.1007/s10601-006-9011-7
Bibliographic reference |
Schaus, Pierre ; Régin, Jean-Charles. Bound-consistent spread constraint : application to load balancing in nurse-to-patient assignments. In: EURO Journal on Computational Optimization, Vol. 2, no.3, p. 123-146 (2013) |
Permanent URL |
http://hdl.handle.net/2078.1/204780 |