4 Presentations

• 
  03:30 PM - 03:55 PM

  Resource-constrained Activity Sequencing Problem

  • Xiao Li, presenter, HEC Montréal
  • Hugo Deschênes, Croesus
  • Maxime Dumas, Croesus
  • Okan Arslan, GERAD, HEC Montréal
  • Robert Pellerin, École Polytechnique de Montréal

  In modern supply chains, efficient warehouse management is a key element for achieving operational excellence. In this talk, we introduce the Resource-constrained Activity Sequencing Problem (RASP) that optimizes the sequencing of activities within a time horizon. Each activity either supplies products to the warehouse or demands them from it, and these activities are splittable. Unlike traditional stock management models that assume that the time a demand arrives is exogenous, we consider the timing as a decision. Demand is satisfied instantaneously, while the supply requires a lead time. The RASP has three hierarchical objectives: minimizing the timespan of executing all activities, minimizing the inventory levels at the warehouse and minimizing the number of split activities. We present a model and develop an efficient hybrid heuristic algorithm for solving the RASP. Through extensive computational experiments, we demonstrate that our hybrid heuristic performs well on a wide range of problem instances.

• 
  03:55 PM - 04:20 PM

  A Nested Logic-Based Benders Decomposition for the Multi-Shop Car Resequencing Problem with A Painted Body Storage

  • Xinyi Guo, presenter, Tsinghua University
  • Jean-François Côté, Laval University
  • Canrong Zhang, Tsinghua University
  • Lixin Miao, Tsinghua University

  The cost of producing different cars depends on their order in the body shop, paint shop, and assembly shop. Before entering the downstream assembly shop, the upstream car sequence in the body shop and paint shop can be altered by a buffer named the painted body storage (PBS), which comprises several first-in-first-out lanes. Our car resequencing problem aims to determine the two sequences and the car-to-lane assignment to minimize the total costs of the three shops. To solve it, we propose a nested logic-based Benders decomposition (LBBD) method with three levels. The body and color of each car are determined in the first level. Once the configuration and the downstream position of each car are determined in the second level, we seek a feasible allocation of cars to lanes in the third level. To improve our nested LBBD, we reformulate the first-level car sequencing problem as two shortest-path problems. Based on the first reformulation, we transform the standard LBBD iterative procedure into a k-simple shortest path problem. Other enhancements include a lower bound, three valid inequalities, and a math-heuristic method. Experimental results on real-world and larger instances show our nested LBBD can handle 120 cars in one hour.

• 
  04:20 PM - 04:45 PM

  Interprétation et conséquence de la notion de flow shop de permutation en présence d'opérations manquantes

  • Randa Ouchene, presenter, Université du Québec à Chicoutimi
  • Djamal Rebaine, Université du Québec à Chicoutimi
  • Pierre Baptiste, Polytechnique Montréal

  Les recherches sur les flow shops se concentrent souvent sur les ordonnancements de permutation, traditionnellement définis comme une séquence de tâches identique sur toutes les machines. Cette définition classique peut s'avérer ambiguë pour les flow shops avec des opérations manquantes ou Flow shops hybrides, car la séquence des tâches peut varier d'une machine à l'autre. De cette définition classique émergent deux visions distinctes de la permutation : l'existence d'un ordre sous-jacent et la stricte absence de dépassement entre les tâches.
  Une définition alternative de la permutation, basée sur la règle du Premier Entré, Premier Sorti (FIFO), est présente dans la littérature. Selon cette définition, toutes les files d'attente des machines adhèrent à la règle FIFO. Cela signifie qu'une tâche ne peut pas "dépasser" une autre en attendant dans une file d'attente d'une machine.
  Dans le contexte des flow shops sans opérations manquantes, la définition classique et celle utilisant la règle FIFO sont équivalentes. Cependant, cette équivalence disparaît dans les cas où des opérations sont manquantes. Cette étude vise à explorer l'impact de ces définitions sur le makespan et le temps moyen d'achèvement des tâches, particulièrement dans le contexte des problèmes de flow shops avec opérations manquantes.

• 
  04:45 PM - 05:10 PM

  A heursitic method with random walk approximations to solve an assignment problem

  • Hugo Tremblay, Université du Québec à Chicoutimi
  • Sara Séguin, Université du Québec à Chicoutimi
  • Léo Monteiro, presenter, Université du Québec à Chicoutimi

  In the context of Robotic Process Automation (RPA), we are studying the following assignment problem: given different transactions types to be performed at predefined time periods throughout the day, finding a valid assignment of software-robots while minimizing the number of robots. For small instances, the exact solution is obtained using an integer programming model. As the problem size increases, we employ heuristics to obtain an upper bound on the number of robots. Here, we present a heuristic based on the random walk approximation of a graph to obtain an upper bound for the number of robots.