Cargando…
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 algor...
Autores principales: | , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Hindawi Publishing Corporation
2013
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3876833/ https://www.ncbi.nlm.nih.gov/pubmed/24453841 http://dx.doi.org/10.1155/2013/387194 |
_version_ | 1782297550088306688 |
---|---|
author | Liu, Ruochen Ma, Chenlin Ma, Wenping Li, Yangyang |
author_facet | Liu, Ruochen Ma, Chenlin Ma, Wenping Li, Yangyang |
author_sort | Liu, Ruochen |
collection | PubMed |
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 | Online Article Text |
id | pubmed-3876833 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2013 |
publisher | Hindawi Publishing Corporation |
record_format | MEDLINE/PubMed |
spelling | pubmed-38768332014-01-16 A Multipopulation PSO Based Memetic Algorithm for Permutation Flow Shop Scheduling Liu, Ruochen Ma, Chenlin Ma, Wenping Li, Yangyang ScientificWorldJournal Research Article 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. Hindawi Publishing Corporation 2013-12-15 /pmc/articles/PMC3876833/ /pubmed/24453841 http://dx.doi.org/10.1155/2013/387194 Text en Copyright © 2013 Ruochen Liu et al. https://creativecommons.org/licenses/by/3.0/ This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Research Article Liu, Ruochen Ma, Chenlin Ma, Wenping Li, Yangyang A Multipopulation PSO Based Memetic Algorithm for Permutation Flow Shop Scheduling |
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 |
topic | Research Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3876833/ https://www.ncbi.nlm.nih.gov/pubmed/24453841 http://dx.doi.org/10.1155/2013/387194 |
work_keys_str_mv | AT liuruochen amultipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT machenlin amultipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT mawenping amultipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT liyangyang amultipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT liuruochen multipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT machenlin multipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT mawenping multipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling AT liyangyang multipopulationpsobasedmemeticalgorithmforpermutationflowshopscheduling |