Hybrid particle swarm optimization algorithm for flow shop scheduling problem

Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (9): 33-36.

• 研究、探讨 • Previous Articles Next Articles

Hybrid particle swarm optimization algorithm for flow shop scheduling problem

QI Xuemei1，2, LUO Yonglong1，2, ZHAO Cheng1，2

1.School of Mathematics and Computer Science, Anhui Normal University, Wuhu, Anhui 241003, China
2.Network and Information Security Engineering Research Center, Anhui Normal University, Wuhu, Anhui 241003, China

Received:1900-01-01 Revised:1900-01-01 Online:2012-03-21 Published:2012-04-11

求解流水车间调度问题的混合粒子群算法

齐学梅1，2，罗永龙1，2，赵诚1，2

1.安徽师范大学数学计算机科学学院，安徽　芜湖 241003
2.安徽师范大学网络与信息安全工程技术研究中心，安徽　芜湖 241003

Abstract

Abstract: A Hybrid Particle Swarm optimization Algorithm（HPSA） is presented to solve the flow shop scheduling problem with total flowtime minimization. The initial particle swarms are generated by heuristics. It combines the particle swarm optimization algorithm, genetic operators and local search strategies together. Taillard’s benchmark program is used to generate a large number of random instances. The experimental results indicate that the quality of solutions is improved using HPSA through the improvement of the option mode of population and a bigger searching scope. The performance of the proposed method is superior to the efficient heuristics currently used and hybrid tabu search algorithms. The average relation percentage deviation and standard deviation are reduced evidently, and the percent of optimal solutions increases obviously.

Key words: particle swarm optimization, flow shop scheduling, local search, total flowtime

摘要： 针对最小化流水车间调度总完工时间问题，提出了一种混合的粒子群优化算法（Hybrid Particle Swarm Algorithm，HPSA），采用启发式算法产生初始种群，将粒子群算法、遗传操作以及局部搜索策略有效地结合在一起。用Taillard’s基准程序随机产生大量实例，实验结果显示：HPSA通过对种群选取方法的改进和搜索范围的扩大提高了解的质量，在性能上均优于目前较有效的启发式算法和混合的禁忌搜索算法，产生最好解的平均百分比偏差和标准偏差均显著下降，最优解所占比例大幅度提高。

关键词: 粒子群优化, 流水车间调度, 局部搜索, 总完工时间

QI Xuemei1，2, LUO Yonglong1，2, ZHAO Cheng1，2. Hybrid particle swarm optimization algorithm for flow shop scheduling problem[J]. Computer Engineering and Applications, 2012, 48(9): 33-36.

齐学梅1，2，罗永龙1，2，赵诚1，2. 求解流水车间调度问题的混合粒子群算法[J]. 计算机工程与应用, 2012, 48(9): 33-36.

[1]	SHI Chuntian, ZENG Yanyang, HOU Shouming. Summary of Application of Swarm Intelligence Algorithms in Image Segmentation [J]. Computer Engineering and Applications, 2021, 57(8): 36-47.
[2]	LI Jingxing, YANG Youlong. Feature Selection of Markov Blanket for High Dimensional Data [J]. Computer Engineering and Applications, 2021, 57(6): 58-66.
[3]	ZHU Jiaying, GAO Maoting. AUV Path Planning Based on Particle Swarm Optimization and Improved Ant Colony Optimization [J]. Computer Engineering and Applications, 2021, 57(6): 267-273.
[4]	HU Xiaomin, WANG Mingfeng, ZHANG Shourong, LI Min. New Differential Evolution with Particle Swarm Optimization Algorithm for Text Clustering [J]. Computer Engineering and Applications, 2021, 57(4): 61-67.
[5]	WANG Jiayue, SHI Li. Research on Path Optimization and Charging Strategy of Electric Refrigerated Vehicle Considering Cost of Battery Capacity Degradation [J]. Computer Engineering and Applications, 2021, 57(24): 283-289.
[6]	XU Chenhua, LUO Zhuguang, WU Guanhong, LIU Bin. Grey Wolf Optimization Algorithm Based on Sine Factor and Quantum Local Search [J]. Computer Engineering and Applications, 2021, 57(24): 83-89.
[7]	CHEN Wanfen, WANG Yujia, LIN Weixing. Heterogeneous Ensemble Surrogate Assisted Multi-objective Particle Swarm Optimization Algorithm [J]. Computer Engineering and Applications, 2021, 57(23): 71-80.
[8]	DU Shouxin, WU Tao. Study on Application of Double Population Hybrid Genetic Algorithm in Cut Order Planning [J]. Computer Engineering and Applications, 2021, 57(22): 182-189.
[9]	LIN Weixing, WANG Yujia, CHEN Wanfen, LIANG Haina. High-Dimensional Data Feature Selection Algorithm Based on Multifactor Particle Swarm Optimization [J]. Computer Engineering and Applications, 2021, 57(22): 199-207.
[10]	HAO Xiang, HE Yichao, ZHU Xiaobin, ZHAI Qinglei. Discrete Hybrid Multi-verse Optimization Algorithm for Solving Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2021, 57(18): 103-113.
[11]	LI Leixiao, DENG Dan, LI Jie, WANG Yongsheng. All-to-All Comparison Computing Data Distribution Strategy Based on Particle Swarm Optimization [J]. Computer Engineering and Applications, 2021, 57(15): 109-117.
[12]	YU Guolong, ZHAO Yong, WU Lian, CUI Zhongwei. Improvement of QPSO Algorithm and Its Application in DBN Parameter Optimization [J]. Computer Engineering and Applications, 2021, 57(10): 154-162.
[13]	LIAO Weilin, CHENG Shan, SHANG Dongdong, WEI Zhaobin. Particle Swarm Optimization Algorithm Integrated with Multiple-Strategies [J]. Computer Engineering and Applications, 2021, 57(1): 69-76.
[14]	HUO Lin, LU Yinli. Improved Particle Swarm Optimization for Android Malware Detection [J]. Computer Engineering and Applications, 2020, 56(7): 96-101.
[15]	CHEN Qiuju, XU Jianguo. Optimized Orthogonal Matching Pursuit and Short-Time Spectrum Estimation for Sound Recognition [J]. Computer Engineering and Applications, 2020, 56(7): 162-169.

Hybrid particle swarm optimization algorithm for flow shop scheduling problem

求解流水车间调度问题的混合粒子群算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics