Pattern mining‐based pruning strategies in stochastic local searches for scheduling problems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue International Transactions in Operational Research Année : 2021

Pattern mining‐based pruning strategies in stochastic local searches for scheduling problems

Résumé

Scheduling problems are a subclass of combinatorial problems consisting of a set of tasks/activities/jobs to be processed by a set of resources usually to minimize a time criterion. Some optimization methods used to solve these problems are hybridized with knowledge discovery techniques to extract information during the optimization process and enhance it. However, most of these hybrid techniques are custom-designed and lack generalization. In this paper a module for knowledge extraction in Stochastic Local Searches is designed, aiming to be problem independent and plugged into optimisation methods that relies on multiple Stochastic Local Search replications. The objective is to prune parts of the search space for which the exploration is likely to lead to poor solutions. This is performed through the extraction of high-quality patterns occurring in locally optimal solutions. Benchmarked on two well-known scheduling problems, the Job-shop Problem and the Resource Constrained Project Scheduling Problem, the results show both a speed up in the convergence and the reaching of better local optima solutions.
Fichier principal
Vignette du fichier
ITOR____Stochastic_Local_Search__Recent_developments_and_trends_ (2).pdf (928.42 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03222340 , version 1 (10-05-2021)

Identifiants

Citer

Arnaud Laurent, Damien Lamy, Benjamin Dalmas, Vincent Clerc. Pattern mining‐based pruning strategies in stochastic local searches for scheduling problems. International Transactions in Operational Research, 2021, ⟨10.1111/itor.12984⟩. ⟨hal-03222340⟩
247 Consultations
164 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More