CORS / Optimization Days
HEC Montréal, May 29-31, 2023
CORS-JOPT2023
HEC Montreal, 29 — 31 May 2023
SC Scheduling
May 29, 2023 03:30 PM – 05:10 PM
Location: Demers Beaulne (green)
Chaired by Farin Rastgar Amini
4 Presentations
-
03:30 PM - 03:55 PM
An efficient scenario penalization matheuristic for a stochastic scheduling problem
We propose a new scenario penalization matheuristic for a stochastic scheduling problem based on both mathematical programming models and local search methods. The application considered is an NP-hard problem expressed as a mean-risk model involving quantiles related to value at risk which is formulated as a non-linear (generally non-convex) binary optimization problem with linear constraints. The proposed matheuritic involves a parameterization of the objective function that is progressively modified to generate feasible solutions which are improved by local search procedure based on the combination of shift and swap neighborhoods. This matheuristic is related to the ghost image process approach by Fred Glover (1994) [1] which is a highly general framework for heuristic search optimization. This approach won the first prize in the senior category of the EURO/ROADEF 2020 challenge [2]. Experimental results are presented which demonstrate the effectiveness of our approach on large instances provided by the French electricity transmission network RTE.
Keywords: Ghost Image Processes, Mixed Integer Programming, Local Search, Stochastic Scheduling, Mean-Risk
[1] Glover, F. (1994). Optimization by ghost image processes in neural networks. Computers & Operations Research, 21(8), 801-822.
[2] ROADEF/EURO challenge 2020, https://www.roadef.org/challenge/2020/en/ -
03:55 PM - 04:20 PM
Modèle d'optimisation de l'ordonnancement des travaux correctifs et de maintenance dans un contexte minier souterrain
L’ensemble des activités de maintenance et de réparations représentent des coûts significatifs dans l’industrie minière. Une gestion optimale de ces activités entraînent entre autres un grand nombre de bénéfices comme une diminution des arrêts non-planifiés, une baisse de la consommation énergétique des équipements et une hausse de la durée de vie des équipements. Le mémoire suivant traitera du développement d’un modèle permettant l’ordonnancement optimal des activités de maintenance et de réparations. Cet ordonnancement respecte les contraintes usuelles des planificateurs de la maintenance : assurer pour chaque type d’équipement un nombre minimum d’équipement actifs (non immobilisés), affecter les bonnes ressources (mécaniciens et équipement) selon la spécificité de chaque bon de travail (BT), ajuster la durée d’une tâche en fonction de l’assignation des ressources humaines, et accélérer autant que possible les travaux en arriéré (Backlog). Le modèle a pour objectif d’ordonnancer de façon robuste et de compiler rapidement le plus grand nombre d’activités prêtes à être effectuées en fonction de leurs indices de priorité (établis a priori) tout en minimisant la durée globale des travaux. Le modèle est validé sur des données réelles tirées d’applications minières.
-
04:20 PM - 04:45 PM
Robust selective maintenance optimization under maintenance duration and quality uncertainty
This paper studies the joint selective maintenance and repairperson assignment problem (JSM-RAP) when the duration and quality of the maintenance actions are uncertain. In practice, maintenance actions' quality and duration are influenced by factors such as repairpersons' expertise, methods, tools, and environmental variability. First, the nominal JSM-RAP is reformulated into a mixed-integer exponential conic program (MIECP). Next, maintenance quality uncertainty is captured via non-symmetric budget uncertainty sets that enable the level of conservatism to be controlled, and the robust problem's objective function affected by this uncertainty is tractably reformulated into a MIECP using Fenchel duality. Furthermore, distributionally-robust chance constraints (DRCCs) within a Wasserstein-1 ball are used to deal with the probabilistic maintenance duration, and a CVaR-based approximation is applied to convert the DRCCs into a mixed integer linear program that can be easily handled by off-the-shelf solvers. Extensive numerical experiments on benchmark instances show the favourable computational performance of the proposed reformulations and the value of considering the uncertainty of maintenance quality and duration when developing selective maintenance plans.
-
04:45 PM - 05:10 PM
Data Mining-Driven Shifts Enumeration for Accelerating the Solution of Large-Scale Personnel Scheduling Problems
This research focuses on solving personnel scheduling problems in the service industry using data mining techniques. The personnel scheduling problem involves finding the least cost work schedules for skilled employees to meet multiple jobs' demands over a planning horizon of one week. In the service industry, shifts depend on customers' presence, resulting in a large number of potential shifts. This makes the problem large and complicated, which cannot be solved easily by commercial solvers. However, these problems are classified as recurrent problems. The observations show that numerous instances of the problem possess distinctive characteristics and solution structures that vary only in a few parameters that change over time. Therefore, we propose using data mining methods to accelerate the solution process while maintaining solution quality for problems formulated as generalized set-covering models. Specifically, we consider a problem with multiple jobs, mono-job shifts, and a one-week horizon with a minimum number of days off to be assigned to each employee and we present two approaches to reducing problem size: one involves identifying patterns in data that do not conform to expected behavior, while the other involves clustering similar demand patterns for different jobs. Our methods can identify patterns in job demands that repeat over time and find clusters of similar demand patterns resulting in a significant reduction in problem size. This enables us to solve the problem using a general-purpose mixed-integer programming solver in a reasonable time while maintaining solution quality.