Hybridization of Particle Swarm Optimization with Variable Neighborhood Search and Simulated Annealing for Improved Handling of the Permutation Flow-Shop Scheduling Problem
Permutation flow-shop scheduling is the strategy that ensures the processing of jobs on each subsequent machine in the exact same order while optimizing an objective, which generally is the minimization of makespan. Because of its NP-Complete nature, a substantial portion of the literature has mainl...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-04-01
|
| Series: | Systems |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-8954/11/5/221 |
| _version_ | 1797598200668880896 |
|---|---|
| author | Iqbal Hayat Adnan Tariq Waseem Shahzad Manzar Masud Shahzad Ahmed Muhammad Umair Ali Amad Zafar |
| author_facet | Iqbal Hayat Adnan Tariq Waseem Shahzad Manzar Masud Shahzad Ahmed Muhammad Umair Ali Amad Zafar |
| author_sort | Iqbal Hayat |
| collection | DOAJ |
| description | Permutation flow-shop scheduling is the strategy that ensures the processing of jobs on each subsequent machine in the exact same order while optimizing an objective, which generally is the minimization of makespan. Because of its NP-Complete nature, a substantial portion of the literature has mainly focused on computational efficiency and the development of different AI-based hybrid techniques. Particle Swarm Optimization (PSO) has also been frequently used for this purpose in the recent past. Following the trend and to further explore the optimizing capabilities of PSO, first, a standard PSO was developed during this research, then the same PSO was hybridized with Variable Neighborhood Search (PSO-VNS) and later on with Simulated Annealing (PSO-VNS-SA) to handle Permutation Flow-Shop Scheduling Problems (PFSP). The effect of hybridization was validated through an internal comparison based on the results of 120 different instances devised by Taillard with variable problem sizes. Moreover, further comparison with other reported hybrid metaheuristics has proved that the hybrid PSO (HPSO) developed during this research performed exceedingly well. A smaller value of 0.48 of ARPD (Average Relative Performance Difference) for the algorithm is evidence of its robust nature and significantly improved performance in optimizing the makespan as compared to other algorithms. |
| first_indexed | 2024-03-11T03:16:00Z |
| format | Article |
| id | doaj.art-03315cfd04eb4e5f905423d6cd017c71 |
| institution | Directory Open Access Journal |
| issn | 2079-8954 |
| language | English |
| last_indexed | 2024-03-11T03:16:00Z |
| publishDate | 2023-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Systems |
| spelling | doaj.art-03315cfd04eb4e5f905423d6cd017c712023-11-18T03:31:28ZengMDPI AGSystems2079-89542023-04-0111522110.3390/systems11050221Hybridization of Particle Swarm Optimization with Variable Neighborhood Search and Simulated Annealing for Improved Handling of the Permutation Flow-Shop Scheduling ProblemIqbal Hayat0Adnan Tariq1Waseem Shahzad2Manzar Masud3Shahzad Ahmed4Muhammad Umair Ali5Amad Zafar6Department of Mechanical Engineering, University of Wah, Wah Cantt 47040, PakistanDepartment of Mechanical Engineering, University of Wah, Wah Cantt 47040, PakistanDepartment of Mechatronics Engineering, University of Wah, Wah Cantt 47040, PakistanDepartment of Mechanical Engineering, Capital University of Science and Technology (CUST), Islamabad 44000, PakistanDepartment of Electronics Engineering, Hanyang University, Seoul 04763, Republic of KoreaDepartment of Intelligent Mechatronics Engineering, Sejong University, Seoul 05006, Republic of KoreaDepartment of Intelligent Mechatronics Engineering, Sejong University, Seoul 05006, Republic of KoreaPermutation flow-shop scheduling is the strategy that ensures the processing of jobs on each subsequent machine in the exact same order while optimizing an objective, which generally is the minimization of makespan. Because of its NP-Complete nature, a substantial portion of the literature has mainly focused on computational efficiency and the development of different AI-based hybrid techniques. Particle Swarm Optimization (PSO) has also been frequently used for this purpose in the recent past. Following the trend and to further explore the optimizing capabilities of PSO, first, a standard PSO was developed during this research, then the same PSO was hybridized with Variable Neighborhood Search (PSO-VNS) and later on with Simulated Annealing (PSO-VNS-SA) to handle Permutation Flow-Shop Scheduling Problems (PFSP). The effect of hybridization was validated through an internal comparison based on the results of 120 different instances devised by Taillard with variable problem sizes. Moreover, further comparison with other reported hybrid metaheuristics has proved that the hybrid PSO (HPSO) developed during this research performed exceedingly well. A smaller value of 0.48 of ARPD (Average Relative Performance Difference) for the algorithm is evidence of its robust nature and significantly improved performance in optimizing the makespan as compared to other algorithms.https://www.mdpi.com/2079-8954/11/5/221permutation flow-shop scheduling problems (PFSP)particle swarm optimization (PSO)makespanhybrid particle swarm optimization (HPSO)metaheuristic |
| spellingShingle | Iqbal Hayat Adnan Tariq Waseem Shahzad Manzar Masud Shahzad Ahmed Muhammad Umair Ali Amad Zafar Hybridization of Particle Swarm Optimization with Variable Neighborhood Search and Simulated Annealing for Improved Handling of the Permutation Flow-Shop Scheduling Problem Systems permutation flow-shop scheduling problems (PFSP) particle swarm optimization (PSO) makespan hybrid particle swarm optimization (HPSO) metaheuristic |
| title | Hybridization of Particle Swarm Optimization with Variable Neighborhood Search and Simulated Annealing for Improved Handling of the Permutation Flow-Shop Scheduling Problem |
| title_full | Hybridization of Particle Swarm Optimization with Variable Neighborhood Search and Simulated Annealing for Improved Handling of the Permutation Flow-Shop Scheduling Problem |
| title_fullStr | Hybridization of Particle Swarm Optimization with Variable Neighborhood Search and Simulated Annealing for Improved Handling of the Permutation Flow-Shop Scheduling Problem |
| title_full_unstemmed | Hybridization of Particle Swarm Optimization with Variable Neighborhood Search and Simulated Annealing for Improved Handling of the Permutation Flow-Shop Scheduling Problem |
| title_short | Hybridization of Particle Swarm Optimization with Variable Neighborhood Search and Simulated Annealing for Improved Handling of the Permutation Flow-Shop Scheduling Problem |
| title_sort | hybridization of particle swarm optimization with variable neighborhood search and simulated annealing for improved handling of the permutation flow shop scheduling problem |
| topic | permutation flow-shop scheduling problems (PFSP) particle swarm optimization (PSO) makespan hybrid particle swarm optimization (HPSO) metaheuristic |
| url | https://www.mdpi.com/2079-8954/11/5/221 |
| work_keys_str_mv | AT iqbalhayat hybridizationofparticleswarmoptimizationwithvariableneighborhoodsearchandsimulatedannealingforimprovedhandlingofthepermutationflowshopschedulingproblem AT adnantariq hybridizationofparticleswarmoptimizationwithvariableneighborhoodsearchandsimulatedannealingforimprovedhandlingofthepermutationflowshopschedulingproblem AT waseemshahzad hybridizationofparticleswarmoptimizationwithvariableneighborhoodsearchandsimulatedannealingforimprovedhandlingofthepermutationflowshopschedulingproblem AT manzarmasud hybridizationofparticleswarmoptimizationwithvariableneighborhoodsearchandsimulatedannealingforimprovedhandlingofthepermutationflowshopschedulingproblem AT shahzadahmed hybridizationofparticleswarmoptimizationwithvariableneighborhoodsearchandsimulatedannealingforimprovedhandlingofthepermutationflowshopschedulingproblem AT muhammadumairali hybridizationofparticleswarmoptimizationwithvariableneighborhoodsearchandsimulatedannealingforimprovedhandlingofthepermutationflowshopschedulingproblem AT amadzafar hybridizationofparticleswarmoptimizationwithvariableneighborhoodsearchandsimulatedannealingforimprovedhandlingofthepermutationflowshopschedulingproblem |