基于改进粒子群算法作业车间调度问题的优化

doi:10.6040/j.issn.1672-3961.0.2018.540

摘要/Abstract

摘要：

针对作业车间调度问题,提出一种基于自适应权重和混沌的改进粒子群优化算法。构建以机器加工时间最短为优化目标的多约束作业车间调度模型,采用基于工序排列的编码方式得到粒子参数与工序序列的映射关系;基于自适应权重改进粒子群算法中的惯性系数和加速因子,使得算法可以根据适应度值动态调整参数因子;采用反向学习策略改善种群初始解的质量;引入莱维飞行、变邻域搜索、混沌,增强了算法的搜索能力,避免陷入局部最优解。试验结果表明:改进粒子群算法可以有效地提高粒子利用率,平衡全局搜索与局部搜索能力,改善传统粒子群算法易早熟的缺点,得到更优的解。

关键词: 作业车间调度, 自适应权重, 混沌, 莱维飞行, 粒子群优化

Abstract:

An improved particle swarm optimization algorithm was proposed based on adaptive weights and chaos aiming at the job shop scheduling. A multiple constrained job shop scheduling model was built with the shortest machining time as the optimization goal. The mapping relationship between particle parameters and operation sequences was obtained by coding method based on ranked order value. The inertial coefficient and acceleration factor in the particle swarm optimization algorithm were improved based on the adaptive weights, so that the algorithm could dynamically adjust parameters based on the fitness value. The reverse learning was used to improve the quality of initial solution. Considering the problem of local optimum, some measures were used to enhance the search of algorithm, such as Lévy flight, variable neighborhood search and chaos. The results showed that improved particle swarm optimization could effectively improve utilization of particles, balance the global search and local search, avoid the premature convergence of the traditional particle swarm optimization algorithm, and get better results.

Key words: job shop scheduling, adaptive weights, chaos, Lévy flight, particle swarm optimization

中图分类号:

TP391

刘洪铭,曾鸿雁,周伟,王涛. 基于改进粒子群算法作业车间调度问题的优化[J]. 山东大学学报 (工学版), 2019, 49(1): 75-82.

Hongming LIU,Hongyan ZENG,Wei ZHOU,Tao WANG. Optimization of job shop scheduling based on improved particle swarm optimization algorithm[J]. Journal of Shandong University(Engineering Science), 2019, 49(1): 75-82.

图/表 3

图1

表1

图2

参考文献 25

1	RUDOLPH G . Convergence analysis of canonical genetic algorithms[J]. IEEE Transactions on Neural Networks, 1994, 5 (1): 96- 101. doi: 10.1109/72.265964
2	BHOSALE K C , PAWAR P J . Material flow optimization of flexible manufacturing system using real coded genetic algorithm(RCGA)[J]. Materials Today Proceedings, 2018, 5 (2): 7160- 7167. doi: 10.1016/j.matpr.2017.11.381
3	CRUZCHÁVEZ M A , MARTÍNEZRANGEL M G , CRUZROSALES M H . Accelerated simulated annealing algorithm applied to the flexible job shop scheduling problem[J]. International Transactions in Operational Research, 2017, 24 (5): 1119- 1137. doi: 10.1111/itor.2017.24.issue-5
4	BERTSIMAS D , TSITSIKLIS J . Simulated annealing[J]. Statistical Science, 1993, 8 (1): 10- 15. doi: 10.1214/ss/1177011077
5	陈知美, 顾幸生. 基于蚁群算法的不确定条件下的Job Shop调度[J]. 山东大学学报(工学版), 2005, 35 (4): 74- 79. doi: 10.3969/j.issn.1672-3961.2005.04.018
	CHEN Zhimei , GU Xingsheng . Job shop scheduling with uncertain processing time based on ant colony system[J]. Journal of Shandong University (Engineering Science), 2005, 35 (4): 74- 79. doi: 10.3969/j.issn.1672-3961.2005.04.018
6	DORIGO M , BIRATTARI M , STUTZLE T . Ant colony optimization[J]. IEEE Computational Intelligence Magazine, 2007, 1 (4): 28- 39.
7	NIU Qun , JIAO Bin , GU Xingsheng . Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time[J]. Applied Mathematics and Computation, 2008, 205 (1): 148- 158. doi: 10.1016/j.amc.2008.05.086
8	DU Hui , LIU Dacheng , ZHANG Mianhao , et al. A hybrid algorithm based on particle swarm optimization and artificial immune for an assembly job shop scheduling problem[J]. Mathematical Problems in Engineering, 2016, 2016 (2): 1- 10.
9	AMIN J , MOHAMMAD A S , REZA T M . A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2011, 54 (1/4): 309- 322.
10	DONG Wenyong , KANG Lanlan , ZHANG Wensheng . Opposition-based particle swarm optimization with adaptive mutation strategy[J]. Soft Computing, 2017, 21 (17): 5081- 5090. doi: 10.1007/s00500-016-2102-5
11	MAY B R . Simple mathematical models with very complicated dynamics[J]. Nature, 1976, 261 (5560): 459- 467. doi: 10.1038/261459a0
12	WANG H , WU Z , RAHNAMAYAN S , et al. Enhancing particle swarm optimization using generalized opposition-based learning[J]. Information Sciences, 2011, 181 (20): 4699- 4714. doi: 10.1016/j.ins.2011.03.016
13	李荣雨, 王颖. 基于莱维飞行的改进粒子群算法[J]. 系统仿真学报, 2017, 29 (8): 1685- 1691, 1701.
	LI Rongyu , WANG Ying . Improved particle swarm optimization based on Lévy flights[J]. Journal of System Simulation, 2017, 29 (8): 1685- 1691, 1701.
14	姜天华. 猫群优化算法求解柔性作业车间调度问题[J]. 计算机工程与应用, 2018, 54 (23): 259- 263, 270. doi: 10.3778/j.issn.1002-8331.1708-0297
	JIANG Tianhua . Cat swarm optimization for solving flexible job shop scheduling problem[J]. Computer Engineering and Applications, 2018, 54 (23): 259- 263, 270. doi: 10.3778/j.issn.1002-8331.1708-0297
15	RATNAWEERA A , HALGAMUGE S K , WATSON H C . Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J]. IEEE Transactions on Evolutionary Computation, 2004, 8 (3): 240- 255.
16	BEAN J . Genetic algorithms and random keys for sequencing and optimization[J]. Orsa Journal on Computing, 1994, 6 (2): 154- 160. doi: 10.1287/ijoc.6.2.154
17	张飞, 耿红琴. 基于混沌粒子群算法的车间作业调度优化[J]. 山东大学学报(工学版), 2013, 43 (3): 19- 22, 37.
	ZHANG Fei , GENG Hongqin . Optimization of job shop scheduling problem based on chaos particle swarm optimization algorithm[J]. Journal of Shandong University(Engineering Science), 2013, 43 (3): 19- 22, 37.
18	ELGOHARY A , ALRUZAIZA A S . Chaos and adaptive control in two prey, one predator system with nonlinear feedback[J]. Chaos Solitons & Fractals, 2007, 34 (2): 443- 453.
19	OUYANG X , ZHOU Y , LUO Q , et al. A novel discrete cuckoo search algorithm for spherical traveling salesman problem[J]. Applied Mathematics & Information Sciences, 2013, 7 (2): 777- 784.
20	YANG X S , KARAMANOGLU M , HE X . Flower pollination algorithm: a novel approach for multiobjective optimization[J]. Engineering Optimization, 2014, 46 (9): 1222- 1237. doi: 10.1080/0305215X.2013.832237
21	HANSEN P , MLADENOVIC N . Variable neighborhood search: principles and applications[J]. European Journal of Operational Research, 2001, 130 (3): 449- 467. doi: 10.1016/S0377-2217(00)00100-4
22	潘全科, 王文宏, 朱剑英, 等. 基于粒子群优化和变邻域搜索的混合调度算法[J]. 计算机集成制造系统, 2007, 13 (2): 323- 328. doi: 10.3969/j.issn.1006-5911.2007.02.019
	PAN Quanke , WANG Wenhong , ZHU Jianying , et al. Hybrid heuristics based on particle swarm optimization and variable neighborhood search for job shop scheduling[J]. Computer Integrated Manufacturing Systems, 2007, 13 (2): 323- 328. doi: 10.3969/j.issn.1006-5911.2007.02.019
23	钱晓雯. 求解作业车间调度问题的变邻域动态烟花算法[J]. 实验室研究与探索, 2018, 37 (1): 19- 21, 124. doi: 10.3969/j.issn.1006-7167.2018.01.006
	QIAN Xiaowen . Dynamic fireworks algorithm based on variable neighborhood search for job shop scheduling problem[J]. Research and Exploration in Laboratory, 2018, 37 (1): 19- 21, 124. doi: 10.3969/j.issn.1006-7167.2018.01.006
24	姚远远, 叶春明. 求解作业车间调度问题的改进混合灰狼优化算法[J]. 计算机应用研究, 2018, 35 (5): 1310- 1314. doi: 10.3969/j.issn.1001-3695.2018.05.007
	YAO Yuanyuan , YE Chunming . Solving job shop scheduling problem using improved hybrid grey wolf optimizer[J]. Application Research of Computers, 2018, 35 (5): 1310- 1314. doi: 10.3969/j.issn.1001-3695.2018.05.007
25	BEASLEY J E. OR-Library[DB/OL]. (2004-09-07)[2018-10-24]. http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/jobshop1.txt.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

实例	问题规模	已知最优解/s	IPSO			PSO			最小值提升率/%	平均值提升率/%
实例	问题规模	已知最优解/s	最小值/ s	平均值/ s	寻优成功率/%	最小值/ s	平均值/ s	寻优成功率/%	最小值提升率/%	平均值提升率/%
FT06	6×6	55	55	55	100	56	58	0	1.79	5.17
FT10	10×10	930	975	1 027	0	1 075	1 196	0	9.30	14.13
FT20	20×5	1 165	1 206	1 222	0	1 429	1 526	0	15.6	19.92
LA01	10×5	666	666	666	100	666	709	5	0	4.58
LA06	15×5	926	926	926	100	926	938	35	0	1.28
LA11	20×5	1 222	1 222	1 222	100	1 222	1 259	15	0	2.94
LA16	10×10	945	973	1 011	0	1 043	1 118	0	9.40	9.57

[1]	刘萌,徐陶阳,李常刚,吴越,王智,史方芳,苏建军,张国辉,李宽. 基于粒子群算法的受端电网紧急切负荷优化[J]. 山东大学学报 (工学版), 2019, 49(1): 120-128.
[2]	王东晓. 具有纠缠项的分数阶五维混沌系统滑模同步的两种方法[J]. 山东大学学报 (工学版), 2018, 48(5): 85-90.
[3]	毛北行. 纠缠混沌系统的比例积分滑模同步[J]. 山东大学学报(工学版), 2018, 48(4): 50-54.
[4]	孟晓玲,王建军. 一类分数阶冠状动脉系统的混沌同步控制[J]. 山东大学学报(工学版), 2018, 48(4): 55-60.
[5]	宋正强,杨辉玲,肖丹. 基于在线粒子群优化方法的IPMSM驱动电流和速度控制器[J]. 山东大学学报(工学版), 2018, 48(1): 112-116.
[6]	毛北行,程春蕊. 分数阶Victor-Carmen混沌系统的自适应滑模控制[J]. 山东大学学报(工学版), 2017, 47(4): 31-36.
[7]	李庆宾,王晓东. 分数阶情绪模型的终端滑模控制混沌同步[J]. 山东大学学报(工学版), 2017, 47(3): 84-88.
[8]	毛北行,王东晓. 分数阶多涡卷系统滑模控制混沌同步[J]. 山东大学学报(工学版), 2017, 47(3): 79-83.
[9]	王常顺,肖海荣. 基于自抗扰控制的水面无人艇路径跟踪控制器[J]. 山东大学学报(工学版), 2016, 46(4): 54-59.
[10]	刘志军. 基于复合混沌与仿射变换的彩色图像加密算法[J]. 山东大学学报(工学版), 2016, 46(4): 1-8.
[11]	孙美美, 胡云安, 韦建明. 多涡卷超混沌系统自适应滑模同步控制[J]. 山东大学学报(工学版), 2015, 45(6): 45-51.
[12]	董红斌, 张广江, 逄锦伟, 韩启龙. 一种基于协同进化方法的聚类集成算法[J]. 山东大学学报(工学版), 2015, 45(2): 1-9.
[13]	张君捧, 张庆范, 杨红娟. 基于块特征和混沌序列的图像篡改检测与恢复[J]. 山东大学学报(工学版), 2014, 44(6): 63-69.
[14]	花景新, 薄煜明, 陈志敏. 基于改进粒子群优化神经网络的房地产市场预测[J]. 山东大学学报(工学版), 2014, 44(4): 22-30.
[15]	张飞,耿红琴. 基于混沌粒子群算法的车间作业调度优化[J]. 山东大学学报(工学版), 2013, 43(3): 19-22.