A Hybrid Discrete Memetic Algorithm for Solving Flow-Shop Scheduling Problems
Flow-shop scheduling problems are classic examples of multi-resource and multi-operation scheduling problems where the objective is to minimize the makespan. Because of the high complexity and intractability of the problem, apart from some exceptional cases, there are no explicit algorithms for find...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-08-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/16/9/406 |
| _version_ | 1827727628754223104 |
|---|---|
| author | Levente Fazekas Boldizsár Tüű-Szabó László T. Kóczy Olivér Hornyák Károly Nehéz |
| author_facet | Levente Fazekas Boldizsár Tüű-Szabó László T. Kóczy Olivér Hornyák Károly Nehéz |
| author_sort | Levente Fazekas |
| collection | DOAJ |
| description | Flow-shop scheduling problems are classic examples of multi-resource and multi-operation scheduling problems where the objective is to minimize the makespan. Because of the high complexity and intractability of the problem, apart from some exceptional cases, there are no explicit algorithms for finding the optimal permutation in multi-machine environments. Therefore, different heuristic approaches, including evolutionary and memetic algorithms, are used to obtain the solution—or at least, a close enough approximation of the optimum. This paper proposes a novel approach: a novel combination of two rather efficient such heuristics, the discrete bacterial memetic evolutionary algorithm (DBMEA) proposed earlier by our group, and a conveniently modified heuristics, the Monte Carlo tree method. By their nested combination a new algorithm was obtained: the hybrid discrete bacterial memetic evolutionary algorithm (HDBMEA), which was extensively tested on the Taillard benchmark data set. Our results have been compared against all important other approaches published in the literature, and we found that this novel compound method produces good results overall and, in some cases, even better approximations of the optimum than any of the so far proposed solutions. |
| first_indexed | 2024-03-10T23:08:04Z |
| format | Article |
| id | doaj.art-f6f8d2a1c91c4d79b317eb1003acaa3c |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T23:08:04Z |
| publishDate | 2023-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-f6f8d2a1c91c4d79b317eb1003acaa3c2023-11-19T09:12:42ZengMDPI AGAlgorithms1999-48932023-08-0116940610.3390/a16090406A Hybrid Discrete Memetic Algorithm for Solving Flow-Shop Scheduling ProblemsLevente Fazekas0Boldizsár Tüű-Szabó1László T. Kóczy2Olivér Hornyák3Károly Nehéz4Institute of Information Engineering, University of Miskolc, H-3515 Miskolc, HungaryDepartment of Information Technology, Szechenyi Istvan University, H-9026 Győr, HungaryDepartment of Information Technology, Szechenyi Istvan University, H-9026 Győr, HungaryInstitute of Information Engineering, University of Miskolc, H-3515 Miskolc, HungaryInstitute of Information Engineering, University of Miskolc, H-3515 Miskolc, HungaryFlow-shop scheduling problems are classic examples of multi-resource and multi-operation scheduling problems where the objective is to minimize the makespan. Because of the high complexity and intractability of the problem, apart from some exceptional cases, there are no explicit algorithms for finding the optimal permutation in multi-machine environments. Therefore, different heuristic approaches, including evolutionary and memetic algorithms, are used to obtain the solution—or at least, a close enough approximation of the optimum. This paper proposes a novel approach: a novel combination of two rather efficient such heuristics, the discrete bacterial memetic evolutionary algorithm (DBMEA) proposed earlier by our group, and a conveniently modified heuristics, the Monte Carlo tree method. By their nested combination a new algorithm was obtained: the hybrid discrete bacterial memetic evolutionary algorithm (HDBMEA), which was extensively tested on the Taillard benchmark data set. Our results have been compared against all important other approaches published in the literature, and we found that this novel compound method produces good results overall and, in some cases, even better approximations of the optimum than any of the so far proposed solutions.https://www.mdpi.com/1999-4893/16/9/406flow-shopscheduling problemdiscrete bacterial memetic evolutionary algorithmhybrid DBMEAMonte Carlo tree searchsimulated annealing |
| spellingShingle | Levente Fazekas Boldizsár Tüű-Szabó László T. Kóczy Olivér Hornyák Károly Nehéz A Hybrid Discrete Memetic Algorithm for Solving Flow-Shop Scheduling Problems Algorithms flow-shop scheduling problem discrete bacterial memetic evolutionary algorithm hybrid DBMEA Monte Carlo tree search simulated annealing |
| title | A Hybrid Discrete Memetic Algorithm for Solving Flow-Shop Scheduling Problems |
| title_full | A Hybrid Discrete Memetic Algorithm for Solving Flow-Shop Scheduling Problems |
| title_fullStr | A Hybrid Discrete Memetic Algorithm for Solving Flow-Shop Scheduling Problems |
| title_full_unstemmed | A Hybrid Discrete Memetic Algorithm for Solving Flow-Shop Scheduling Problems |
| title_short | A Hybrid Discrete Memetic Algorithm for Solving Flow-Shop Scheduling Problems |
| title_sort | hybrid discrete memetic algorithm for solving flow shop scheduling problems |
| topic | flow-shop scheduling problem discrete bacterial memetic evolutionary algorithm hybrid DBMEA Monte Carlo tree search simulated annealing |
| url | https://www.mdpi.com/1999-4893/16/9/406 |
| work_keys_str_mv | AT leventefazekas ahybriddiscretememeticalgorithmforsolvingflowshopschedulingproblems AT boldizsartuuszabo ahybriddiscretememeticalgorithmforsolvingflowshopschedulingproblems AT laszlotkoczy ahybriddiscretememeticalgorithmforsolvingflowshopschedulingproblems AT oliverhornyak ahybriddiscretememeticalgorithmforsolvingflowshopschedulingproblems AT karolynehez ahybriddiscretememeticalgorithmforsolvingflowshopschedulingproblems AT leventefazekas hybriddiscretememeticalgorithmforsolvingflowshopschedulingproblems AT boldizsartuuszabo hybriddiscretememeticalgorithmforsolvingflowshopschedulingproblems AT laszlotkoczy hybriddiscretememeticalgorithmforsolvingflowshopschedulingproblems AT oliverhornyak hybriddiscretememeticalgorithmforsolvingflowshopschedulingproblems AT karolynehez hybriddiscretememeticalgorithmforsolvingflowshopschedulingproblems |