Improved Differential Evolution Algorithm for Flexible Job Shop Scheduling Problems
This research project aims to study and develop the differential evolution (DE) for use in solving the flexible job shop scheduling problem (FJSP). The development of algorithms were evaluated to find the solution and the best answer, and this was subsequently compared to the meta-heuristics from th...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-09-01
|
| Series: | Mathematical and Computational Applications |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2297-8747/24/3/80 |
| _version_ | 1818062176919748608 |
|---|---|
| author | Prasert Sriboonchandr Nuchsara Kriengkorakot Preecha Kriengkorakot |
| author_facet | Prasert Sriboonchandr Nuchsara Kriengkorakot Preecha Kriengkorakot |
| author_sort | Prasert Sriboonchandr |
| collection | DOAJ |
| description | This research project aims to study and develop the differential evolution (DE) for use in solving the flexible job shop scheduling problem (FJSP). The development of algorithms were evaluated to find the solution and the best answer, and this was subsequently compared to the meta-heuristics from the literature review. For FJSP, by comparing the problem group with the makespan and the mean relative errors (MREs), it was found that for small-sized Kacem problems, value adjusting with “DE/rand/1” and exponential crossover at position 2. Moreover, value adjusting with “DE/best/2” and exponential crossover at position 2 gave an MRE of 3.25. For medium-sized Brandimarte problems, value adjusting with “DE/best/2” and exponential crossover at position 2 gave a mean relative error of 7.11. For large-sized Dauzere-Peres and Paulli problems, value adjusting with “DE/best/2” and exponential crossover at position 2 gave an MRE of 4.20. From the comparison of the DE results with other methods, it was found that the MRE was lower than that found by Girish and Jawahar with the particle swarm optimization (PSO) method (7.75), which the improved DE was 7.11. For large-sized problems, it was found that the MRE was lower than that found by Warisa (1ST-DE) method (5.08), for which the improved DE was 4.20. The results further showed that basic DE and improved DE with jump search are effective methods compared to the other meta-heuristic methods. Hence, they can be used to solve the FJSP. |
| first_indexed | 2024-12-10T14:00:03Z |
| format | Article |
| id | doaj.art-f25c413f40d143ae99ff46f69c79aa6a |
| institution | Directory Open Access Journal |
| issn | 2297-8747 |
| language | English |
| last_indexed | 2024-12-10T14:00:03Z |
| publishDate | 2019-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematical and Computational Applications |
| spelling | doaj.art-f25c413f40d143ae99ff46f69c79aa6a2022-12-22T01:45:49ZengMDPI AGMathematical and Computational Applications2297-87472019-09-012438010.3390/mca24030080mca24030080Improved Differential Evolution Algorithm for Flexible Job Shop Scheduling ProblemsPrasert Sriboonchandr0Nuchsara Kriengkorakot1Preecha Kriengkorakot2Industrial Engineering, Department, Faculty of Engineering, Ubon Ratchathani University, Ubon Ratchathani 34190, ThailandIndustrial Engineering, Department, Faculty of Engineering, Ubon Ratchathani University, Ubon Ratchathani 34190, ThailandIndustrial Engineering, Department, Faculty of Engineering, Ubon Ratchathani University, Ubon Ratchathani 34190, ThailandThis research project aims to study and develop the differential evolution (DE) for use in solving the flexible job shop scheduling problem (FJSP). The development of algorithms were evaluated to find the solution and the best answer, and this was subsequently compared to the meta-heuristics from the literature review. For FJSP, by comparing the problem group with the makespan and the mean relative errors (MREs), it was found that for small-sized Kacem problems, value adjusting with “DE/rand/1” and exponential crossover at position 2. Moreover, value adjusting with “DE/best/2” and exponential crossover at position 2 gave an MRE of 3.25. For medium-sized Brandimarte problems, value adjusting with “DE/best/2” and exponential crossover at position 2 gave a mean relative error of 7.11. For large-sized Dauzere-Peres and Paulli problems, value adjusting with “DE/best/2” and exponential crossover at position 2 gave an MRE of 4.20. From the comparison of the DE results with other methods, it was found that the MRE was lower than that found by Girish and Jawahar with the particle swarm optimization (PSO) method (7.75), which the improved DE was 7.11. For large-sized problems, it was found that the MRE was lower than that found by Warisa (1ST-DE) method (5.08), for which the improved DE was 4.20. The results further showed that basic DE and improved DE with jump search are effective methods compared to the other meta-heuristic methods. Hence, they can be used to solve the FJSP.https://www.mdpi.com/2297-8747/24/3/80improved differential evolution algorithmflexible job shop scheduling problemlocal search and jump search |
| spellingShingle | Prasert Sriboonchandr Nuchsara Kriengkorakot Preecha Kriengkorakot Improved Differential Evolution Algorithm for Flexible Job Shop Scheduling Problems Mathematical and Computational Applications improved differential evolution algorithm flexible job shop scheduling problem local search and jump search |
| title | Improved Differential Evolution Algorithm for Flexible Job Shop Scheduling Problems |
| title_full | Improved Differential Evolution Algorithm for Flexible Job Shop Scheduling Problems |
| title_fullStr | Improved Differential Evolution Algorithm for Flexible Job Shop Scheduling Problems |
| title_full_unstemmed | Improved Differential Evolution Algorithm for Flexible Job Shop Scheduling Problems |
| title_short | Improved Differential Evolution Algorithm for Flexible Job Shop Scheduling Problems |
| title_sort | improved differential evolution algorithm for flexible job shop scheduling problems |
| topic | improved differential evolution algorithm flexible job shop scheduling problem local search and jump search |
| url | https://www.mdpi.com/2297-8747/24/3/80 |
| work_keys_str_mv | AT prasertsriboonchandr improveddifferentialevolutionalgorithmforflexiblejobshopschedulingproblems AT nuchsarakriengkorakot improveddifferentialevolutionalgorithmforflexiblejobshopschedulingproblems AT preechakriengkorakot improveddifferentialevolutionalgorithmforflexiblejobshopschedulingproblems |