改进粒子群算法求解分布式柔性车间调度问题

doi:10.16180/j.cnki.issn1007-7820.2021.10.010

摘要/Abstract

摘要：

文中提出一种改进粒子群算法来求解复杂的分布式柔性车间调度问题。针对该问题的特点,提出了一种2层粒子的编码与解码方式,使粒子群算法能够有效地解决该离散型优化问题。此外,采用改进的拥挤距离策略从众多非支配解中筛选出高质量的候选解。在迭代过程中,采用任务分配策略来平衡粒子的勘探与开采。最终在2工厂和3工厂生产模式下,通过总计20组分布式柔性车间测试算例验证了所提算法的性能。实验结果表明,该方法能够有效地解决分布式柔性车间调度问题,并可在其中的11组算例中得到较好的调度方案。

关键词: 分布式柔性车间调度问题, 拥挤距离, 任务分配, 编码, 解码, 粒子群算法, 非支配解, 离散型

Abstract:

An improved particle swarm optimization is proposed in this study for the complex distribution and flexible job-shop scheduling problem. According to the characteristics of the problem, this study proposes a two-layer particle encoding and decoding method, so that the particle swarm algorithm can effectively solve the discrete optimization problem. Additionally, an improved crowded distance is used to select high-quality candidate solutions from many non-dominated solutions. In the iterative process, the task assignment strategy is used to balance the exploration and exploitation of particles. Finally, in the production modes of 2 factories and 3 factories, the performance of the algorithm is evaluated by 20 sets of distribution and flexible job-shop scheduling test cases. Experimental results show that the proposed algorithm can effectively solve distribution and flexible job-shop scheduling problem, and can obtain a better scheduling scheme in 11 sets of examples.

Key words: distribution and flexible job-shop scheduling problem, crowded distance, task assignment strategy, encoding, decoding, particle swarm algorithm, non-dominated solutions, discrete

中图分类号:

TP18

陈强,王宇嘉,林炜星,陈万芬. 改进粒子群算法求解分布式柔性车间调度问题[J]. 电子科技, 2021, 34(10): 63-68.

CHEN Qiang,WANG Yujia,LIN Weixing,CHEN Wanfen. An Improve Particle Swarm Optimization Algorithm for Distribution and Flexible Job-Shop Scheduling Problem[J]. Electronic Science and Technology, 2021, 34(10): 63-68.

图/表 8

表1

表2

图1

图2

表3

表4

参数设置"

算法	参数
PSO-OCO	ω=[0.4,0.9],c₁=c₂=2,p_m=1/n,η_m=5
IGASA	p_m=0.1,p_c=0.9,f=0.8,η=1.005,g=0.9
NSGA-II	P_c=1,P_m= $1 n$ ,η_c=20,η_m=8

表4

表5

表6

参考文献 18

[1]	Chan F T S, Chung S H, Chan P L Y. Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems[J]. International Journal of Production Research, 2006, 44(3):523-543. doi: 10.1080/00207540500319229
[2]	Giovanni L D, Pezzella F. An improved genetic algorithm for the distributed and flexible job-shop scheduling problem[J]. European Journal of Operational Research, 2010, 200(2):395-408. doi: 10.1016/j.ejor.2009.01.008
[3]	Chang H C, Liu T K. Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms[J]. Journal of Intelligent Manufacturing, 2017, 28(8):1973-1986. doi: 10.1007/s10845-015-1084-y
[4]	吴锐, 郭顺生, 李益兵, 等. 改进人工蜂群算法求解分布式柔性作业车间调度问题[J]. 控制与决策, 2019, 34(12):2527-2536.
	Wu Rui, Guo Shunsheng, Li Yibing, et al. An improved artificial bee colony algorithm for distributed and flexible job-shop scheduling problem[J]. Control and Decision, 2019, 34(12):2527-2536.
[5]	Lu P H, Wu M C, Tan H, et al. A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems[J]. Journal of Intelligent Manufacturing, 2018, 29(1):19-34. doi: 10.1007/s10845-015-1083-z
[6]	凌海峰. 基于参数控制的蚁群算法求解分布式柔性车间作业调度问题[C]. 合肥:第十届中国管理学年会, 2015.
	Ling Haifeng. Distributed and flexible job-shop scheduling problem based on parameter adaptive ant colony algorithm[C]. Hefei:The Tenth China Management Annual Conference, 2015.
[7]	李冬. 基于组合拍卖机制的分布式柔性车间优化调度的研究[D]. 沈阳:沈阳工业大学, 2015.
	Li Dong. Research on distributed and flexible job-shop scheduling optimization based on combinatorial auction[D]. Shenyang:Shenyang University of Technology, 2015.
[8]	Kennedy J, Eberhart R. Particle swarm optimization[C]. Perth:Proceedings of ICNN’95 International Conference on Neural Networks, 1995.
[9]	杜美君, 张伟, 谢亚莲. 基于粒子群算法的PID控制器参数优化[J]. 电子科技, 2019, 32(6):7-11.
	Du Meijun, Zhang Wei, Xie Yalian. Particle swarm optimization based PID controller parameter optimization[J]. Electronic Science and Technology, 2019, 32(6):7-11.
[10]	周静, 崔国民, 彭富裕, 等. 基于正弦调整的粒子群算法应用于换热网络[J]. 电子科技, 2016, 29(4):37-40.
	Zhou Jing, Cui Guomin, Peng Fuyu, et al. Particle swarm optimization (PSO) with sinusoidal changing inertia weight for heat exchange network synjournal[J]. Electronic Science and Technology, 2016, 29(4):37-40.
[11]	Chyan G S, Ponnambalam S G. Obstacle avoidance control of redundant robots using variants of particle swarm optimization[J]. Robotics and Computer-integrated Manufacturing, 2012, 28(2):147-153.
[12]	喻明让, 陈云, 张志刚. 离散粒子群优化算法求解多目标柔性作业车间调度问题[J]. 制造技术与机床, 2019(1):159-165.
	Yu Mingrang, Chen Yun, Zhang Zhigang. Adiscrete version of particle swarm optimization for multi-objective flexible job-shop scheduling problems[J]. Manufacturing Technology & Machine Tool, 2019(1),159-165.
[13]	Zhang L, Sun J, Guo C, et al. A multi-swarm competitive algorithm based on dynamic task allocation particle swarm optimization[J]. Arabian Journal for Science and Engineering, 2017, 43(12):8255-8274. doi: 10.1007/s13369-017-2820-8
[14]	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
[15]	Brandimarte P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research, 1993, 41(3):157-183. doi: 10.1007/BF02023073
[16]	Pan Q K, Wang L, Qian B. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems[J]. Computers and Operations Research, 2009, 36(8):2498-2511. doi: 10.1016/j.cor.2008.10.008
[17]	Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197. doi: 10.1109/4235.996017
[18]	蓝萌. 基于混合邻域搜索算法的分布式车间调度系统的研究与实现[D]. 苏州:苏州大学, 2010.
	Lan Meng. Research and implementation of distributed shop floor scheduling system based on hybrid neighborhood search algorithm[D]. Suzhou:Soochow University, 2010.

符号	定义
n	工件的总个数
p	工件的索引,p=1,2,…,n
J = {J₁,J₂,…,J_n}	工件的集合,J_p表示第p件工件
z_p	第p件工件工序数
j	工序的索引号, j=1,2,3,…,z
m	机器的总个数
k	第k台机器,k=1,2,…,m
q	工厂的索引号, q=1,2,…,s
s	工厂的总数
Q_q	第q间工厂包含的机器数
M_qk	第q间工厂的第k台机器
O_pj	第p件工件的第j道工序
t_pjk	O_pj在第k台机器上的加工时间
w_k	第k台机器上总的加工时间
T	所有机器消耗的总时间
C_p	工件P最后一道工序的完成时间
C_max	系统最后完工时间

算例	n	z	m	A_v	PT	TT
DMK01	10	[5,6]	[4,6]	3	[1,10]	[5,10]
DMK02	10	[5,6]	[4,6]	6	[1,10]	[5,10]
DMK03	15	[3,13]	[6,8]	5	[1,20]	[10,20]
DMK04	15	[3,13]	[6,8]	3	[1,10]	[5,10]
DMK05	15	[4,9]	[3,4]	2	[1,10]	[5,10]
DMK06	10	[13,17]	[15,17]	5	[1,10]	[5,10]
DMK07	20	[4,9]	[3,5]	5	[1,20]	[10,20]
DMK08	20	[13,17]	[8,13]	2	[1,20]	[10,20]
DMK09	20	[13,17]	[8,13]	5	[1,20]	[10,20]
DMK10	20	[13,17]	[15,17]	5	[1,20]	[10,20]

算例	2工厂						3工厂
	IGASA		NSGA-II		IMPSO		IGASA		NSGA-II		IMPSO
	mean	Gap	mean	Gap	mean	Gap	mean	Gap	mean	Gap	mean	Gap
DMK01	0.348	4.523	0.175	1.778	0.063	0.000	0.015	0.000	0.104	5.933	0.047	2.133
DMK02	0.028	0.000	0.101	2.607	0.058	1.071	0.036	0.091	0.281	7.515	0.033	0.000
DMK03	0.029	0.160	0.068	1.720	0.025	2.270	0.042	0.000	0.084	1.000	0.044	0.047
DMK04	0.069	2.632	0.046	1.421	0.019	0.000	0.316	0.541	0.310	0.512	0.205	0.000
DMK05	0.014	0.000	0.057	3.071	0.032	1.285	0.288	1.851	0.101	0.000	0.104	0.029
DMK06	0.069	3.059	0.017	0.000	0.022	2.294	0.159	1.741	0.107	0.844	0.058	0.000
DMK07	0.033	0.000	0.140	3.242	0.069	1.091	0.038	0.727	0.129	4.864	0.022	0.000
DMK08	0.024	0.000	0.165	5.875	0.064	1.667	0.012	0.091	0.038	2.455	0.011	0.000
DMK09	0.049	0.485	0.064	0.939	0.033	0.000	0.057	3.385	0.013	0.000	0.016	0.231
DMK10	0.039	1.428	0.048	2.000	0.016	0.000	0.059	1.107	0.104	2.714	0.028	0.000

工厂		工件分配	f(1)	f(2)	f(3)
2工厂	q₁	4、5、7、9	52	189	34
2工厂	q₂	1、2、3、6、8、10	52	189	34
3工厂	q₁	3、5、9	40	196	18
	q₂	4、6、10
	q₃	1、2、7、8