Skip to Main content Skip to Navigation
Journal articles

Learning to select operators in meta-heuristics: An integration of Q-learning into the iterated greedy algorithm for the permutation flowshop scheduling problem

Maryam Karimi-Mamaghan 1, 2 Mehrdad Mohammadi 1, 2 Bastien Pasdeloup 1, 2 Patrick Meyer 1, 2 
1 Lab-STICC_DECIDE - Equipe DECIDE
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance : UMR6285
Abstract : This paper aims at integrating machine learning techniques into meta-heuristics for solving combinatorial optimization problems. Specifically, our study develops a novel efficient iterated greedy algorithm based on reinforcement learning. The main novelty of the proposed algorithm is its new perturbation mechanism, which incorporates Q-learning to select appropriate perturbation operators during the search process. Through an application to the permutation flowshop scheduling problem, comprehensive computational experiments are conducted on a wide range of benchmark instances to evaluate the performance of the proposed algorithm. This evaluation is done against non-learning versions of the iterated greedy algorithm and seven state-of-the-art algorithms from the literature. The experimental results and statistical analyses show the better performance of the proposed algorithm in terms of optimality gaps, convergence rate, and computational overhead.
Document type :
Journal articles
Complete list of metadata

https://hal-imt-atlantique.archives-ouvertes.fr/hal-03723715
Contributor : Mehrdad MOHAMMADI Connect in order to contact the contributor
Submitted on : Friday, July 15, 2022 - 10:29:46 AM
Last modification on : Friday, August 5, 2022 - 2:54:52 PM

Identifiers

Citation

Maryam Karimi-Mamaghan, Mehrdad Mohammadi, Bastien Pasdeloup, Patrick Meyer. Learning to select operators in meta-heuristics: An integration of Q-learning into the iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, Elsevier, 2022, ⟨10.1016/j.ejor.2022.03.054⟩. ⟨hal-03723715⟩

Share

Metrics

Record views

0