Genetic Algorithm Combined with Gradient Information for Flexible Job-shop Scheduling Problem with Different Varieties and Small Batches
To solve the Flexible Job-shop Scheduling Problem (FJSP) with different varieties and small batches, a modified meta-heuristic algorithm based on Genetic Algorithm (GA) is proposed in which gene encoding is divided into process encoding and machine encoding, and according to the encoding mode, the m...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
EDP Sciences
2017-01-01
|
| Series: | MATEC Web of Conferences |
| Online Access: | https://doi.org/10.1051/matecconf/20179510001 |
| _version_ | 1828925414736658432 |
|---|---|
| author | Chen Ming Li Jie-Lin |
| author_facet | Chen Ming Li Jie-Lin |
| author_sort | Chen Ming |
| collection | DOAJ |
| description | To solve the Flexible Job-shop Scheduling Problem (FJSP) with different varieties and small batches, a modified meta-heuristic algorithm based on Genetic Algorithm (GA) is proposed in which gene encoding is divided into process encoding and machine encoding, and according to the encoding mode, the machine gene fragment is connected with the process gene fragment and can be changed with the alteration of process genes. In order to get the global optimal solutions, the crossover and mutation operation of the process gene fragment and machine gene fragment are carried out respectively. In the initialization operation, the machines with shorter manufacturing time are more likely to be chosen to accelerate the convergence speed and then the tournament selection strategy is applied due to the minimum optimization objective. Meanwhile, a judgment condition of the crossover point quantity is introduced to speed up the population evolution and as an important interaction bridge between the current machine and alternative machines in the incidence matrix, a novel mutation operation of machine genes is proposed to achieve the replacement of manufacturing machines. The benchmark test shows the correctness of proposed algorithm and the case simulation proves the proposed algorithm has better performance compared with existing algorithms. |
| first_indexed | 2024-12-13T23:14:02Z |
| format | Article |
| id | doaj.art-3bf58fc36e0e46ce963d949c1b4f7dba |
| institution | Directory Open Access Journal |
| issn | 2261-236X |
| language | English |
| last_indexed | 2024-12-13T23:14:02Z |
| publishDate | 2017-01-01 |
| publisher | EDP Sciences |
| record_format | Article |
| series | MATEC Web of Conferences |
| spelling | doaj.art-3bf58fc36e0e46ce963d949c1b4f7dba2022-12-21T23:27:59ZengEDP SciencesMATEC Web of Conferences2261-236X2017-01-01951000110.1051/matecconf/20179510001matecconf_icmme2017_10001Genetic Algorithm Combined with Gradient Information for Flexible Job-shop Scheduling Problem with Different Varieties and Small BatchesChen Ming0Li Jie-Lin1Sino-German College of Applied Sciences, Tongji UniversitySchool of Mechanical Engineering, Tongji UniversityTo solve the Flexible Job-shop Scheduling Problem (FJSP) with different varieties and small batches, a modified meta-heuristic algorithm based on Genetic Algorithm (GA) is proposed in which gene encoding is divided into process encoding and machine encoding, and according to the encoding mode, the machine gene fragment is connected with the process gene fragment and can be changed with the alteration of process genes. In order to get the global optimal solutions, the crossover and mutation operation of the process gene fragment and machine gene fragment are carried out respectively. In the initialization operation, the machines with shorter manufacturing time are more likely to be chosen to accelerate the convergence speed and then the tournament selection strategy is applied due to the minimum optimization objective. Meanwhile, a judgment condition of the crossover point quantity is introduced to speed up the population evolution and as an important interaction bridge between the current machine and alternative machines in the incidence matrix, a novel mutation operation of machine genes is proposed to achieve the replacement of manufacturing machines. The benchmark test shows the correctness of proposed algorithm and the case simulation proves the proposed algorithm has better performance compared with existing algorithms.https://doi.org/10.1051/matecconf/20179510001 |
| spellingShingle | Chen Ming Li Jie-Lin Genetic Algorithm Combined with Gradient Information for Flexible Job-shop Scheduling Problem with Different Varieties and Small Batches MATEC Web of Conferences |
| title | Genetic Algorithm Combined with Gradient Information for Flexible Job-shop Scheduling Problem with Different Varieties and Small Batches |
| title_full | Genetic Algorithm Combined with Gradient Information for Flexible Job-shop Scheduling Problem with Different Varieties and Small Batches |
| title_fullStr | Genetic Algorithm Combined with Gradient Information for Flexible Job-shop Scheduling Problem with Different Varieties and Small Batches |
| title_full_unstemmed | Genetic Algorithm Combined with Gradient Information for Flexible Job-shop Scheduling Problem with Different Varieties and Small Batches |
| title_short | Genetic Algorithm Combined with Gradient Information for Flexible Job-shop Scheduling Problem with Different Varieties and Small Batches |
| title_sort | genetic algorithm combined with gradient information for flexible job shop scheduling problem with different varieties and small batches |
| url | https://doi.org/10.1051/matecconf/20179510001 |
| work_keys_str_mv | AT chenming geneticalgorithmcombinedwithgradientinformationforflexiblejobshopschedulingproblemwithdifferentvarietiesandsmallbatches AT lijielin geneticalgorithmcombinedwithgradientinformationforflexiblejobshopschedulingproblemwithdifferentvarietiesandsmallbatches |