4 Presentations

• 
  03:30 PM - 03:55 PM

  Nurse Scheduling Problem With Soft Constraints

  • Antoine Legrain, presenter, Polytechnique Montréal
  • Jeremy Omer, Univ Rennes, INSA Rennes, CNRS, IRMAR - UMR 6625, F-35000 Rennes, France

  The Nurse scheduling problem is very challenging as it generally computes personalized schedules. The talk will focus on the deterministic version of the problem described in the INRC-II competition. One specificity is that most constraints are soft and thus can be violated at the price of a penalty. Classical branch-and-price algorithms underperform with soft constraints as they generally solve a classical resource-constrained shortest-path. In this talk, I will present a different approach to implement more aggressive domination functions for soft constraints, allowing to solve optimally many instances from the INRC-II involving up to 120 nurses and 4 shifts over a 4 to 8-weeks horizon.

• 
  03:55 PM - 04:20 PM

  Implicit and Explicit Approaches for Solving the Nurse Scheduling Problem

  • Aymen Ben Said, presenter, University of Regina
  • Malek Mouhoub, University of Regina

  The Nurse Scheduling Problem (NSP) is one of the challenging combinatorial optimization problems encountered in the healthcare sector. Solving the NSP consists in building weekly schedules by assigning nurses to shift patterns, such that workload constraints are satisfied while nurses’ preferences are maximized. The NSP is a highly dynamic optimization application often affected by unpredictable events. The latter force automatic scheduling to adapt to the first possible solution that satisfies work conditions without considering the competing interest of nurse satisfaction. In this context, we propose an alternative solving approach that relies on implicitly learning NSP constraints and preferences from historical data without any prior knowledge. Although these approximate methods may have the time advantage in solving the NSP, they come with a degree of uncertainty as a trade-off for optimality. We consider an explicit solving approach using the Weighted Constraint Satisfaction Problems (WCSP) framework to overcome this limitation. The WCSP represents both NSP requirements (hard constraints) and quantitative nurses’ preferences over shift patterns (soft constraints). To efficiently solve the WCSP in practice, we apply the Branch-&-Bound (B&B) backtracking algorithm together with constraint propagation techniques and variable ordering heuristics.

• 
  04:20 PM - 04:45 PM

  Nurse scheduling using linear integer programming and random forests to predict well-being to prevent absenteeism

  • Yoan Villeneuve, presenter, Université du Québec à Chicoutimi
  • Sara Séguin, UQAC, GERAD
  • Julien Maitre, Université du Québec à Chicoutimi
  • Renaud Grimard, Timesphere

  In the last decade, the Québec health system underwent a major reform resulting in the creation of the integrated university health and social services centers (CIUSSS). These changes have brought several difficulties in terms of human resources, including the assignment of employees to different care units and the creation of efficient schedules for each sector. A review of the literature shows a distinct dissatisfaction on the part of nurses. This has been reflected by lower work performance, a reduction in the quality of the services offered and an increase in the rate of absenteeism. In this presentation, a linear integer model is proposed to create 14-day schedules for nurse units that aim at reducing the workload and dissatisfaction among nurses. Precisely, the model aims a reducing the amount of overtime shifts while also distributing regular shifts fairly by using parameters obtained from a random forest algorithm to predict the well-being of each nurse based on historical schedule data. Numerical results are conducted on real data provided by the Saguenay Lac-St-Jean CIUSSS.

• 
  04:45 PM - 05:10 PM

  A stochastic preference-based integer programming approach to staffing shortage scheduling

  • Carl Perreault-Lafleur, presenter, Université de Montréal
  • Margarida Carvalho, Université de Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  Employee absences can have a critical impact on the quality of service offered by companies. Therefore, some enterprises use a specific pool of workers, called extra-boards in the transit industry, who are used to cover the regular employees’ absences. In contrast to the known-in-advance absences such as employee vacations, long term absences and open work, the unknown absences that are declared close to the operation day result in uncertainty about when to schedule extra-boards work. It is important that the number of extra-boards scheduled everyday matches the demand in terms of the shortage of regular employees to avoid service cancellation or overstaffing. To address these challenges, we formulate this problem that is defined over a two-week horizon as a two-stage stochastic integer program with mixed-integer recourse. The first-stage decisions consist in finding a days-off pattern for each extra-board. After the unknown absences are revealed, the second-stage decisions are to schedule the extra-board workdays. We incorporate the extra-boards’ days-off pattern preferences into the model to see how employee satisfaction may affect their own absence rates. We validate our approach on one year of data from a large Californian city.