A Two-Individual Based Evolutionary Algorithm for the Flexible Job Shop Scheduling Problem - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

A Two-Individual Based Evolutionary Algorithm for the Flexible Job Shop Scheduling Problem

, (1) , (2, 3) , (4) , (5) , (6)
1
2
3
4
5
6

Résumé

Population-based evolutionary algorithms usually manage a large number of individuals to maintain the diversity of the search, which is complex and time-consuming. In this paper, we propose an evolutionary algorithm using only two individuals, called master-apprentice evolutionary algorithm (MAE), for solving the flexible job shop scheduling problem (FJSP). To ensure the diversity and the quality of the evolution, MAE integrates a tabu search procedure, a recombination operator based on path relinking using a novel distance definition, and an effective individual updating strategy, taking into account the multiple complex constraints of FJSP. Experiments on 313 widely-used public instances show that MAE improves the previous best known results for 47 instances and matches the best known results on all except 3 of the remaining instances while consuming the same computational time as current state-of-the-art metaheuristics. MAE additionally establishes solution quality records for 10 hard instances whose previous best values were established by a well-known industrial solver and a state-of-the-art exact method.
Fichier non déposé

Dates et versions

hal-03636421 , version 1 (10-04-2022)

Identifiants

  • HAL Id : hal-03636421 , version 1

Citer

Junwen Ding, Zhipeng Lu, Chu-Min Li, Liji Shen, Liping Xu, et al.. A Two-Individual Based Evolutionary Algorithm for the Flexible Job Shop Scheduling Problem. THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, Feb 2019, Honolulu, United States. pp.2262-2271. ⟨hal-03636421⟩
39 Consultations
0 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More