4 Presentations

• 
  10:30 AM - 10:55 AM

  Data Mining-Driven Shift Enumeration for Accelerating the Solution of Large-Scale Personnel Scheduling Problems

  • Farin Rastgar Amini, presenter, Polytechnique Montreal
  • Daniel Aloise, Polytechnique Montreal
  • Claudio Contardo, Concordia University
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  This study addresses large-scale personnel scheduling problems in the service industry by combining mathematical programming with data mining techniques to enhance efficiency. The studied problem aims at efficiently scheduling skilled employees over a one-week planning horizon, minimizing costs while meeting diverse job demands. In service industries, shift planning is intricately tied to customer presence, leading to a multitude of potential shifts and to a difficult optimization problem that cannot be easily solved using a commercial mixed-integer programming solver. Nevertheless, these problems are categorized as recurrent problems, where distinct instances share common characteristics and solution structures that differ only in a few parameters over time. Consequently, we propose to use a data mining technique, namely, the k-nearest neighbors algorithm, to expedite the solution process while upholding solution quality. In particular, we suggest using schedules of past solutions to reduce the problem size. Specifically, for an upcoming instance, we identify similar historical instances and streamline the enumeration of shifts to align with the comparable historical instances' schedules. This approach allows us to effectively address the problem using a commercial solver within a reasonable timeframe while preserving solution quality. Significantly, our methodology offers decision-makers the flexibility to determine the extent to which they wish to scale down the problem. Our experiments, conducted on a total of 80 instances with up to 12 jobs and 190 employees, yield an average removal of 85.5% of decision variables. This resulted in a noteworthy average speedup factor of 15.5, with a marginal average cost increase of 1.2%.

• 
  10:55 AM - 11:20 AM

  From centralized learning to decentralized decision support: Exploring the design space of deep reinforcement learning for the flexible job shop scheduling problem

  • Alexandre Jesus, presenter, CEMMPRE/ARISE, University of Coimbra, Portugal
  • Arthur Corrêa, CEMMPRE/ARISE, University of Coimbra, Portugal
  • Catarina Marques, INESC-TEC Porto, Portugal
  • Miguel Vieira, CEG-IST, University of Lisbon, Portugal
  • Cristóvão Silva, CEMMPRE/ARISE, University of Coimbra, Portugal
  • Samuel Moniz, CEMMPRE/ARISE, University of Coimbra, Portugal

  Alongside industrial technology, scheduling models have experienced significant expansion with the emergence of learning-based methods. While pursuing the optimality provided by mathematical frameworks from operations research, learning-based approaches have demonstrated a compelling potential in attaining fast solutions to large shop scheduling problems. In this field, deep reinforcement learning has been highlighted as a prominent driver of decentralized decision support. However, the result-oriented nature of the literature in the field hides potential trade-offs across different architectural options on the same method. To better understand how the problem structure may shape the configuration of experience-based models, this work delves into the flexible job-shop scheduling problem. We adopt a centralized learning approach to train a multi-agent deep Q-learning algorithm with decentralized action execution, where common knowledge guides the agents towards collaboration. On this baseline setting, we explore multiple sets of hyper-parameters, state-action spaces, reward functions, state representations, and deep Q-learning extensions, on controlled problem parameters. A state-of-the-art constraint programming model is employed as the main performance benchmark across experiments. Whilst reaching similar performance to centralized approaches, we were able to measure the sensitivity of solving efficiency to each design stage, providing useful insights to the options available in the literature.

• 
  11:20 AM - 11:45 AM

  MORBDD: Multiobjective Restricted Binary Decision Diagrams by Learning to Sparsify

  • Rahul Mihir Patel, presenter, University of Toronto
  • Khalil Elias, Polytechnique Montreal / University of Toronto
  • David Bergman, University of Connecticut

  In multicriteria decision-making, a user seeks a set of non-dominated solutions to a (constrained) multiobjective optimization problem, the so-called Pareto frontier. In this work, we seek to bring a state-of-the-art method for exact multiobjective integer linear programming into the heuristic realm. We focus on binary decision diagrams (BDDs) which first construct a graph that represents all feasible solutions to the problem and then traverse the graph to extract the Pareto frontier. Because the Pareto frontier may be exponentially large, enumerating it over the BDD can be time-consuming. We explore how restricted BDDs, which have already been shown to be effective as heuristics for single-objective problems, can be adapted to multiobjective optimization through the use of machine learning (ML).
  MORBDD, our ML-based BDD sparsifier, first trains a binary classifier to eliminate BDD nodes that are unlikely to contribute to Pareto solutions, then post-processes the sparse BDD to ensure its connectivity via optimization. Experimental results on multiobjective knapsack problems show that MORBDD is highly effective at producing very small restricted BDDs with excellent approximation quality, outperforming width-limited restricted BDDs and the well-known evolutionary algorithm NSGA-II.

• 
  11:45 AM - 12:10 PM

  Development of an autoregressive recurrent neural network for the short-term hydropower scheduling problem

  • Yoan Villeneuve, presenter, UQAC
  • Sara Séguin, UQAC
  • Abdellah Chehri, Royal Military College of Canada
  • Kenjy Demeester, Rio Tinto

  Quebec relies mostly on hydropower for its electricity production, where efficiency is of significant importance. Currently, hydropower production relies heavily on Mixed-integer linear programming (MILP) models, which represent the problem of short-term hydroelectric scheduling (STHS) as a set of parameters, constraints and objectives. These models seek the optimal value of variables representing, among other things, the reservoir water volume and the flow rate to use each hour to maximize energy production. This research proposes to compare the results obtained by a MILP model with those of a neural model based on a Long Short-Term Memory (LSTM) model on a system composed of two hydropower plants. The latter is chosen for its ability to recognize short and long-term trends in a sequential data set. Using twelve years of hourly data collected from both Chute-du-Diable and Chute-Savane power plants on the Péribonka River in Saguenay-Lac-Saint-Jean, this project aims to train an LSTM model adopting an autoregressive approach to predict a future interval of water flow for both power stations. This research paves the way for the use of neural modeling techniques to improve the efficiency of short-term hydroelectric production.