A Modified Genetic Algorithm with Local Search Strategies and Multi-Crossover Operator for Job Shop Scheduling Problem
It is not uncommon for today’s problems to fall within the scope of the well-known class of NP-Hard problems. These problems generally do not have an analytical solution, and it is necessary to use meta-heuristics to solve them. The Job Shop Scheduling Problem (JSSP) is one of these problems, and fo...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-09-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/20/18/5440 |
| _version_ | 1797552993848000512 |
|---|---|
| author | Monique Simplicio Viana Orides Morandin Junior Rodrigo Colnago Contreras |
| author_facet | Monique Simplicio Viana Orides Morandin Junior Rodrigo Colnago Contreras |
| author_sort | Monique Simplicio Viana |
| collection | DOAJ |
| description | It is not uncommon for today’s problems to fall within the scope of the well-known class of NP-Hard problems. These problems generally do not have an analytical solution, and it is necessary to use meta-heuristics to solve them. The Job Shop Scheduling Problem (JSSP) is one of these problems, and for its solution, techniques based on Genetic Algorithm (GA) form the most common approach used in the literature. However, GAs are easily compromised by premature convergence and can be trapped in a local optima. To address these issues, researchers have been developing new methodologies based on local search schemes and improvements to standard mutation and crossover operators. In this work, we propose a new GA within this line of research. In detail, we generalize the concept of a massive local search operator; we improved the use of a local search strategy in the traditional mutation operator; and we developed a new multi-crossover operator. In this way, all operators of the proposed algorithm have local search functionality beyond their original inspirations and characteristics. Our method is evaluated in three different case studies, comprising 58 instances of literature, which prove the effectiveness of our approach compared to traditional JSSP solution methods. |
| first_indexed | 2024-03-10T16:09:07Z |
| format | Article |
| id | doaj.art-d2aece02130e402c8087de362d93cd8b |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-03-10T16:09:07Z |
| publishDate | 2020-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-d2aece02130e402c8087de362d93cd8b2023-11-20T14:41:06ZengMDPI AGSensors1424-82202020-09-012018544010.3390/s20185440A Modified Genetic Algorithm with Local Search Strategies and Multi-Crossover Operator for Job Shop Scheduling ProblemMonique Simplicio Viana0Orides Morandin Junior1Rodrigo Colnago Contreras2Department of Computing, Federal University of São Carlos, São Carlos, SP 13565-905, BrazilDepartment of Computing, Federal University of São Carlos, São Carlos, SP 13565-905, BrazilDepartment of Applied Mathematics and Statistics, University of São Paulo, São Carlos, SP 13566-590, BrazilIt is not uncommon for today’s problems to fall within the scope of the well-known class of NP-Hard problems. These problems generally do not have an analytical solution, and it is necessary to use meta-heuristics to solve them. The Job Shop Scheduling Problem (JSSP) is one of these problems, and for its solution, techniques based on Genetic Algorithm (GA) form the most common approach used in the literature. However, GAs are easily compromised by premature convergence and can be trapped in a local optima. To address these issues, researchers have been developing new methodologies based on local search schemes and improvements to standard mutation and crossover operators. In this work, we propose a new GA within this line of research. In detail, we generalize the concept of a massive local search operator; we improved the use of a local search strategy in the traditional mutation operator; and we developed a new multi-crossover operator. In this way, all operators of the proposed algorithm have local search functionality beyond their original inspirations and characteristics. Our method is evaluated in three different case studies, comprising 58 instances of literature, which prove the effectiveness of our approach compared to traditional JSSP solution methods.https://www.mdpi.com/1424-8220/20/18/5440genetic algorithmlocal searchmulti-crossoverjob shop scheduling problemcombinatorial optimization |
| spellingShingle | Monique Simplicio Viana Orides Morandin Junior Rodrigo Colnago Contreras A Modified Genetic Algorithm with Local Search Strategies and Multi-Crossover Operator for Job Shop Scheduling Problem Sensors genetic algorithm local search multi-crossover job shop scheduling problem combinatorial optimization |
| title | A Modified Genetic Algorithm with Local Search Strategies and Multi-Crossover Operator for Job Shop Scheduling Problem |
| title_full | A Modified Genetic Algorithm with Local Search Strategies and Multi-Crossover Operator for Job Shop Scheduling Problem |
| title_fullStr | A Modified Genetic Algorithm with Local Search Strategies and Multi-Crossover Operator for Job Shop Scheduling Problem |
| title_full_unstemmed | A Modified Genetic Algorithm with Local Search Strategies and Multi-Crossover Operator for Job Shop Scheduling Problem |
| title_short | A Modified Genetic Algorithm with Local Search Strategies and Multi-Crossover Operator for Job Shop Scheduling Problem |
| title_sort | modified genetic algorithm with local search strategies and multi crossover operator for job shop scheduling problem |
| topic | genetic algorithm local search multi-crossover job shop scheduling problem combinatorial optimization |
| url | https://www.mdpi.com/1424-8220/20/18/5440 |
| work_keys_str_mv | AT moniquesimplicioviana amodifiedgeneticalgorithmwithlocalsearchstrategiesandmulticrossoveroperatorforjobshopschedulingproblem AT oridesmorandinjunior amodifiedgeneticalgorithmwithlocalsearchstrategiesandmulticrossoveroperatorforjobshopschedulingproblem AT rodrigocolnagocontreras amodifiedgeneticalgorithmwithlocalsearchstrategiesandmulticrossoveroperatorforjobshopschedulingproblem AT moniquesimplicioviana modifiedgeneticalgorithmwithlocalsearchstrategiesandmulticrossoveroperatorforjobshopschedulingproblem AT oridesmorandinjunior modifiedgeneticalgorithmwithlocalsearchstrategiesandmulticrossoveroperatorforjobshopschedulingproblem AT rodrigocolnagocontreras modifiedgeneticalgorithmwithlocalsearchstrategiesandmulticrossoveroperatorforjobshopschedulingproblem |