3 Presentations

• 
  03:30 PM - 03:55 PM

  Two-machine reentrant open shop scheduling problem with no-wait and exact time lags constraints

  • Kenza Alioui, presenter, AOTI ESG UQAM
  • Karim Amrouche, University of Algiers 3, Algeria
  • Mourad Boudhar, University of Science and Technology Houari Boumediene, Algeria

  In this work, we consider the two-machine reentrant open shop scheduling problem with no-wait and exact time lags constraints. It should be noted that each job has to return back to the first machine, i.e. reentrance, to execute its second operation on the latter after an exact time lag that separates the two operations of the first machine. The no-wait constraint is applied between the two machines, where a job should start its execution on the second machine at its completion time on the first machine, and vice versa. The objective is to minimize the makespan.
  We first prove that this problem is NP-hard in the strong sense, then we provide some polynomial sub-problems. To solve the general problem, we have proposed three lower bounds, then we have developed a constructive heuristic (H1) and a genetic algorithm (GA). Furthermore, two different hybridizations are proposed between H1 and GA. Computational experiments have been conducted in order to assess the performance of the proposed algorithms.

  Keywords: open shop, makespan, time lags, no-wait, reentrant, heuristics, metaheuristics.

• 
  03:55 PM - 04:20 PM

  Solving an integrated lot sizing and preventive maintenance planning problem for a single machine

  • Harcènage Dansou, presenter, ESG-UQÀM
  • Matthieu Gruson, UQÀM - CIRRELT
  • Francois Lamothe, UQAM
  • Julien Legavre, ESG-UQÀM

  In manufacturing industries, production and maintenance operations are closely linked but are generally planned and optimized separately. Planning preventive maintenance operations makes it possible to determine the appropriate periods for carrying out maintenance upstream of production. Then, production planning consists of determining the quantity and timing of production of several items over a time horizon. This study proposes new mathematical formulations for a problem integrating preventive maintenance planning with the Capacitated Lot Sizing Problem (CLSP). One of these formulations (M1) is based on the redefinition of the variables linked to preventive maintenance planning and another is a Dantzig-Wolfe decomposition formulation (M2). We demonstrate that the formulation M1 gives a relaxation equivalent to the column generation based on M2. Subsequently, we use a relax-and-fix heuristic combined with fix-and-optimize to solve this problem. Relax-and-fix is used to build an initial solution and fix-and-optimize allows us to improve the built solution. Computational experiments evaluate the performance of the heuristics and the models solved with Gurobi. The results show that the solutions obtained by the heuristic are close to those obtained by the models in terms of gap and in a reduced time.

• 
  04:20 PM - 04:45 PM

  Estimating Capacity Bounds in Large-Scale Ad Hoc Networks: A Geometric and Convex Optimization Approach

  • Reza Khalvandi Ilezoole, presenter, Polytechnique Montréal
  • Brunilde Sansò, GERAD, Polytechnique Montréal

  This study addresses the pivotal challenge of estimating the capacity ceiling in wireless distributed networks, a key factor for the feasibility of expansive Ad Hoc networks. We analyze this through two main angles within a symmetric node setup: the average single-hop transmission capacity per node and the expected number of hops for each point-to-point connection. Our findings reveal that the average capacity for a single-hop transmission is consistent with available frequency ranges, even in large networks. Additionally, the expected hop count per connection significantly depends on distance-based interaction probabilities, following a power-law distribution from real-world data. We employ a method that sums up 12 concave integrals to estimate the expected hop count, using geometric techniques to show the sum square of these integrals' upper limits is constant regardless of the source node position in a 2D network. Through convex optimization, we prove the highest expected hop count occurs when the source node is at the network's center. This leads to a defined upper bound for the hop count per node and, by extension, the maximum point-to-point capacity based on the network size. Our research offers valuable insights into the scalability and practicality of large-scale Ad Hoc networking, highlighting its potential viability.