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

doi:10.16180/j.cnki.issn1007-7820.2021.10.010

Abstract

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

CLC Number:

TP18

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.

Figures/Tables 8

Table 1

Table 2

Figure 1.

Figure 2.

Table 3

Table 4

Parameter settings"

算法	参数
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

Table 4

Table 5

Table 6

References 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

An Improve Particle Swarm Optimization Algorithm for Distribution and Flexible Job-Shop Scheduling Problem

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 18

Related Articles 15

Metrics

Comments

Recommended 0

[1]	HE Shaofang,ZHOU Li. Anonymous Interaction Algorithm of Access Control in Searchable Voice Encryption Mechanism [J]. Electronic Science and Technology, 2021, 34(4): 1-5.
[2]	WANG Tong,WANG Lihua,CHEN Jiaming,LI Xianzeng. Research on Settlement Characteristics of Ballasted Ballast Based on Discrete Element and Finite Element Coupling [J]. Electronic Science and Technology, 2021, 34(3): 53-59.
[3]	YANG Yuwei,SONG Fang,ZHANG Wei. Interval Estimation of Sensor Fault for Attitude Control System of UAV [J]. Electronic Science and Technology, 2021, 34(10): 56-62.
[4]	ZHANG Yugui,HU Xuechen,WANG Yi. Research about Bandwidth Utilization of Static Segment Based on FlexRay Bus [J]. Electronic Science and Technology, 2019, 32(6): 12-16.
[5]	LONG Pin. Research on Mobile Signaling Data Acquisition Technology under LTE Core Network Architecture [J]. Electronic Science and Technology, 2019, 32(12): 80-83.
[6]	ZHANG Bingbing. Research on Discrete Event System for LAN Attack [J]. , 2017, 30(9): 169-.
[7]	YE Danmin. Application of Fast Copying Data Decoded By GPU [J]. , 2016, 29(9): 132-.
[8]	TANG Kunpeng,CHEN Qingkui. Design and Implementation of Multistream Hddecoder Based on Cuda [J]. , 2016, 29(4): 71-.
[9]	HE Shaofang. A Public Key Traitor Tracing Scheme Based on Random Sequence [J]. , 2016, 29(4): 180-.
[10]	ZHOU Shuang,XIE Shaobin,WAN Kang. A Synchronization Method for Discrete Chaotic Systems Based on Nonlinear Controller Design [J]. , 2016, 29(1): 65-.
[11]	GU Yangyang,FU Daowen. Design of an IRIGB Decoder Based on FPGA [J]. , 2015, 28(5): 39-.
[12]	LI Chao. Design and Realization of TPC Coding Based on FPGA [J]. , 2015, 28(5): 121-.
[13]	GAO Fei,HUANG Bo. A Direction-Finding Method Based on Harmonic Analysis of Two-Element Time Modulated Arrays [J]. , 2015, 28(12): 158-.
[14]	WANG Hongru,LIU Shike. Robust H_∞Filtering for Discrete Markov Jump System [J]. , 2014, 27(9): 16-.
[15]	MENG Kai. Reed-Solomon (255,239) Encoder and Decoder Based on FPGA [J]. , 2014, 27(8): 33-.