A Multipopulation PSO Based Memetic Algorithm for Permutation Flow Shop Scheduling
The permutation flow shop scheduling problem (PFSSP) is part of production scheduling, which belongs to the hardest combinatorial optimization problem. In this paper, a multipopulation particle swarm optimization (PSO) based memetic algorithm (MPSOMA) is proposed in this paper. In the proposed algo...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2013/387194 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849410076061728768 |
|---|---|
| author | Ruochen Liu Chenlin Ma Wenping Ma Yangyang Li |
| author_facet | Ruochen Liu Chenlin Ma Wenping Ma Yangyang Li |
| author_sort | Ruochen Liu |
| collection | DOAJ |
| description | The permutation flow shop scheduling problem (PFSSP) is part of production scheduling, which belongs to the hardest combinatorial optimization problem. In this paper, a multipopulation particle swarm optimization (PSO) based memetic algorithm (MPSOMA) is proposed in this paper. In the proposed algorithm, the whole particle swarm population is divided into three subpopulations in which each particle evolves itself by the standard PSO and then updates each subpopulation by using different local search schemes such as variable neighborhood search (VNS) and individual improvement scheme (IIS). Then, the best particle of each subpopulation is selected to construct a probabilistic model by using estimation of distribution algorithm (EDA) and three particles are sampled from the probabilistic model to update the worst individual in each subpopulation. The best particle in the entire particle swarm is used to update the global optimal solution. The proposed MPSOMA is compared with two recently proposed algorithms, namely, PSO based memetic algorithm (PSOMA) and hybrid particle swarm optimization with estimation of distribution algorithm (PSOEDA), on 29 well-known PFFSPs taken from OR-library, and the experimental results show that it is an effective approach for the PFFSP. |
| format | Article |
| id | doaj-art-80a2bec900f04ac38f17ccec703b70a7 |
| institution | Kabale University |
| issn | 1537-744X |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-80a2bec900f04ac38f17ccec703b70a72025-08-20T03:35:15ZengWileyThe Scientific World Journal1537-744X2013-01-01201310.1155/2013/387194387194A Multipopulation PSO Based Memetic Algorithm for Permutation Flow Shop SchedulingRuochen Liu0Chenlin Ma1Wenping Ma2Yangyang Li3Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Xi’an 710071, ChinaKey Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Xi’an 710071, ChinaKey Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Xi’an 710071, ChinaKey Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Xi’an 710071, ChinaThe permutation flow shop scheduling problem (PFSSP) is part of production scheduling, which belongs to the hardest combinatorial optimization problem. In this paper, a multipopulation particle swarm optimization (PSO) based memetic algorithm (MPSOMA) is proposed in this paper. In the proposed algorithm, the whole particle swarm population is divided into three subpopulations in which each particle evolves itself by the standard PSO and then updates each subpopulation by using different local search schemes such as variable neighborhood search (VNS) and individual improvement scheme (IIS). Then, the best particle of each subpopulation is selected to construct a probabilistic model by using estimation of distribution algorithm (EDA) and three particles are sampled from the probabilistic model to update the worst individual in each subpopulation. The best particle in the entire particle swarm is used to update the global optimal solution. The proposed MPSOMA is compared with two recently proposed algorithms, namely, PSO based memetic algorithm (PSOMA) and hybrid particle swarm optimization with estimation of distribution algorithm (PSOEDA), on 29 well-known PFFSPs taken from OR-library, and the experimental results show that it is an effective approach for the PFFSP.http://dx.doi.org/10.1155/2013/387194 |
| spellingShingle | Ruochen Liu Chenlin Ma Wenping Ma Yangyang Li A Multipopulation PSO Based Memetic Algorithm for Permutation Flow Shop Scheduling The Scientific World Journal |
| title | A Multipopulation PSO Based Memetic Algorithm for Permutation Flow Shop Scheduling |
| title_full | A Multipopulation PSO Based Memetic Algorithm for Permutation Flow Shop Scheduling |
| title_fullStr | A Multipopulation PSO Based Memetic Algorithm for Permutation Flow Shop Scheduling |
| title_full_unstemmed | A Multipopulation PSO Based Memetic Algorithm for Permutation Flow Shop Scheduling |
| title_short | A Multipopulation PSO Based Memetic Algorithm for Permutation Flow Shop Scheduling |
| title_sort | multipopulation pso based memetic algorithm for permutation flow shop scheduling |
| url | http://dx.doi.org/10.1155/2013/387194 |
| work_keys_str_mv | AT ruochenliu amultipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT chenlinma amultipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT wenpingma amultipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT yangyangli amultipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT ruochenliu multipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT chenlinma multipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT wenpingma multipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT yangyangli multipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling |