Liu Ruochen, Ma Chenlin, Ma Wenping, Li Yangyang
Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University, Xi'an 710071, China.
ScientificWorldJournal. 2013 Dec 15;2013:387194. doi: 10.1155/2013/387194. eCollection 2013.
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.
置换流水车间调度问题（PFSSP）是生产调度的一部分，属于最难的组合优化问题。本文提出了一种基于多种群粒子群优化（PSO）的混合算法（MPSOMA）。在所提算法中，整个粒子群被划分为三个子群，每个粒子通过标准粒子群优化算法进行自身进化，然后使用不同的局部搜索策略（如可变邻域搜索（VNS）和个体改进策略（IIS））对每个子群进行更新。接着，从每个子群中选择最优粒子，利用分布估计算法（EDA）构建概率模型，并从概率模型中采样三个粒子来更新每个子群中的最差个体。整个粒子群中的最优粒子用于更新全局最优解。将所提的MPSOMA与最近提出的两种算法，即基于粒子群优化的混合算法（PSOMA）和带分布估计算法的混合粒子群优化算法（PSOEDA），在从OR库中选取的29个著名的PFFSP上进行比较，实验结果表明它是解决PFFSP的一种有效方法。
