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, Mehrdad Mohammadi, Bastien Pasdeloup and Patrick Meyer

European Journal of Operational Research, 2023, vol. 304, issue 3, 1296-1330

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.

Keywords: Combinatorial optimization; Iterated greedy meta-heuristic; Reinforcement learning; Q-Learning algorithm; Permutation flowshop scheduling problem (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722002788
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:304:y:2023:i:3:p:1296-1330

DOI: 10.1016/j.ejor.2022.03.054

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().