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

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]	韦修喜,陶道,黄华娟. 改进果蝇算法优化BP神经网络预测汽油辛烷值[J]. 山东大学学报 (工学版), 2023, 53(5): 20-28.
[2]	范海雯,郝旭东,赵康,邢法财,蒋哲,李常刚. 基于卷积神经网络的含分布式光伏配电网静态等值[J]. 山东大学学报 (工学版), 2023, 53(4): 140-148.
[3]	孙东磊, 鉴庆之, 李智琦, 韩学山, 王明强, 陈博, 付一木. 源网协调的电力系统均匀性规划[J]. 山东大学学报 (工学版), 2022, 52(5): 92-101.
[4]	贾红艳,陈忠告,石文欣,韩晓光. 一个具有多稳定流的广义Hamiltonian保守混沌系统[J]. 山东大学学报 (工学版), 2022, 52(2): 74-79.
[5]	黄澄,袁东风,张海霞. 基于狮群算法的数字孪生车间调度问题优化[J]. 山东大学学报 (工学版), 2021, 51(4): 17-23.
[6]	程春蕊,毛北行. 一类非线性混沌系统的自适应滑模同步[J]. 山东大学学报 (工学版), 2020, 50(5): 1-6.
[7]	孟晓玲,毛北行. 含对数项分数阶T混沌系统的滑模同步[J]. 山东大学学报 (工学版), 2020, 50(5): 7-12.
[8]	程春蕊. 分数阶Brussel系统混沌同步的三种控制方案[J]. 山东大学学报 (工学版), 2020, 50(4): 46-51.
[9]	王春彦,邸金红,毛北行. 基于新型趋近律的参数未知分数阶Rucklidge系统的滑模同步[J]. 山东大学学报 (工学版), 2020, 50(4): 40-45.
[10]	李彩虹,方春,王志强,夏斌,王凤英. 基于超混沌同步控制的移动机器人全覆盖路径规划[J]. 山东大学学报 (工学版), 2019, 49(6): 63-72.
[11]	方波,陈红梅. 一种新的双策略进化果蝇优化算法[J]. 山东大学学报 (工学版), 2019, 49(3): 22-31.
[12]	薛薇,谭东程,张妹,刘世龙. 基于FPGA的四翼超混沌系统同步及其保密视频通信[J]. 山东大学学报 (工学版), 2019, 49(3): 1-7.
[13]	刘萌,徐陶阳,李常刚,吴越,王智,史方芳,苏建军,张国辉,李宽. 基于粒子群算法的受端电网紧急切负荷优化[J]. 山东大学学报 (工学版), 2019, 49(1): 120-128.
[14]	王东晓. 具有纠缠项的分数阶五维混沌系统滑模同步的两种方法[J]. 山东大学学报 (工学版), 2018, 48(5): 85-90.
[15]	毛北行. 纠缠混沌系统的比例积分滑模同步[J]. 山东大学学报(工学版), 2018, 48(4): 50-54.