柔性作业车间AGV与机器双资源集成调度研究

doi:10.16182/j.issn1004731x.joss.20-0796

摘要/Abstract

摘要：

针对含有AGV（automated guided vehicle）的柔性作业车间调度问题，建立了以最小化最大完工时间为目标的双资源集成调度优化模型。在种群初始化过程中提出一种启发式初始化方法，提高种群初始解的质量，加快算法的收敛速度。针对离散粒子群算法易早熟的弊端，结合竞争学习机制和随机重启机制提出一种可有效避免早熟的混合离散粒子群优化算法。在考虑工件运输的柔性作业车间调度的基准数据集上做仿真实验，结果表明启发式初始化方法和混合离散粒子群算法求解此类问题时可行高效。

关键词: 柔性作业车间调度, 自动引导车, 离散粒子群算法, 集成调度

Abstract:

Aiming at the flexible job shop scheduling problem with AGV (automated guided vehicle), a dual resource integrated scheduling optimization model with the objective of minimizing makespan is established. In the process of population initialization, a heuristic initialization method is proposed to improve the quality of population initial solution and accelerate the convergence speed of the algorithm. A hybrid discrete particle swarm optimization algorithm that can effectively avoid premature maturation is proposed by combining the competitive learning mechanism and the random restart mechanism to address the disadvantages of discrete particle swarm algorithms that are prone to premature maturation. Simulation experiments are carried out on the baseline data set of flexible job shop scheduling considering job transport. The results show that heuristic initialization method and hybrid discrete particle swarm optimization algorithm are feasible and efficient in solving such problems.

Key words: flexible job shop scheduling, automated guided vehicle, discrete particle swarm algorithm, integrated scheduling

中图分类号:

TP391.9

陈魁, 毕利, 王文雅. 柔性作业车间AGV与机器双资源集成调度研究[J]. 系统仿真学报, 2022, 34(3): 461-469.

Kui Chen, Li Bi, Wenya Wang. Research on Integrated Scheduling of AGV and Machine in Flexible Job Shop[J]. Journal of System Simulation, 2022, 34(3): 461-469.

图/表 13

图1

图2

图3

图4

图5

图6

表1

图7

表2

图8

表3

表4

图9

参考文献 23

1	杨智飞, 苏春, 胡祥涛, 等. 面向智能生产车间的多AGV系统多目标调度优化[J]. 东南大学学报(自然科学版), 2019, 49(6): 1033-1040.
	Yang Zhifei, Su Chun, Hu Xiangtao, et al. Multi-Objective Scheduling Optimization for Multi-AGV Systems of Intelligent Jobshop[J]. Journal of Southeast University(Natural Science Edition), 2019, 49(6): 1033-1040.
2	魏永来, 龙伟, 李炎炎, 等. 基于混合禁忌蝙蝠算法的AGV物料配送调度研究[J]. 组合机床与自动化加工技术, 2018, 1(11): 145-149.
	Wei Yonglai, Long Wei, Li Yanyan, et al. Research on AGV Material Delivery Scheduling Problem Based on Hybrid Tabu Bat Algorithm[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2018, 1(11): 145-149.
3	刘二辉, 姚锡凡, 陶韬, 等. 基于改进花授粉算法的共融AGV作业车间调度[J]. 计算机集成制造系统, 2019, 25(9): 2219-2236.
	Liu Erhui, Yao Xifan, Tao Tao, et al. Improved Flower Pollinaton Algorithm for Job Shop Scheduling Problems Integrated with AGVs[J]. Computer Integrated Manufacturing Systems, 2019, 25(9): 2219-2236.
4	肖海宁, 楼佩煌, 严伟国, 等. 柔性作业车间中机床与自动引导车在线调度方法[J]. 农业机械学报, 2013, 44(4): 280-286.
	Xiao Haining, Lou Peihuang, Yan Weiguo, et al. On-Line Scheduling Method for Simultaneous Scheduling of Machines and Automated Guided Vehicles in Flexible Job Shop[J]. Transactions of the Chinese Societr for Agricultural Machinery, 2013, 44(4): 280-286.
5	Zeng Chengkuan, Tang Jiafu, Yan Chongjun. Scheduling of no Buffer Job Shop Cells with Blocking Constraints and Automated Guided Vehicles[J]. Applied Soft Computing (S1568-4968), 2014, 28(8): 1033-1046.
6	Houssem Eddine Nouri, Olfa Belkahla Driss, Ghédira Khaled. Simultaneous Scheduling of Machines and Transport Robots in Flexible Job Shop Environment Using Hybrid Metaheuristics Based on Clustered Holonic Multiagent Model[J]. Computers & Industrial Engineering (S0360-8352), 2016, 24(2): 488-501.
7	Mousavi Maryan, Hwa Jen Yap, Siti Nurmaya Musa, et al. Multi-Objective AGV Scheduling in an FMS Using a Hybrid of Genetic Algorithm and Particle Swarm Optimization[J]. PLoS One (S1932-6203), 2017, 1(3): 1-24.
8	杨煜俊, 陈业. 求解柔性机器人车间调度问题的混合蚁群算法[J]. 计算机工程与应用, 2018, 54(13): 160-167.
	Yang Yujun, Chen Ye. Hybrid Ant Colony Optimization for Flexible Robotic Manufacturing Cell Scheduling Problem[J]. Computer Engineering and Applications, 2018, 54(13): 160-167.
9	陆远, 冯睽睽, 胡莹. 单个AGV多个搬运请求的调度算法研究[J]. 组合机床与自动化加工技术, 2019, 1(2): 157-160.
	Lu Yuan, Feng Kuikui, Hu Ying. An Automated Guided Vehicle Deals with Scheduling Algorithm for Multiple Transport Requests[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2019, 1(2): 157-160.
10	Heger Jens, Voß Thomas. Dynamic Priority Based Dispatching of AGVs in Flexible Job Shops[J]. Procedia CIRP (S2212-8271), 2019, 79: 445-449.
11	Chawla V K, Chanda A K, Angra Surjit. Efect of Natureinspired Algorithms and Hybrid Dispatching Rules on the Performance of Automatic Guided Vehicles in the Fexible Manufacturing System[J]. Journal of the Brazilian Society of Mechanical Sciences and Engineering (S1678-5878), 2019, 41(9): 390-406.
12	李广博, 于东, 胡毅. 基于变邻域遗传算法的离散制造物料配送调度优化[J]. 组合机床与自动化加工技术, 2019, 1(11): 152-155.
	Li Guangbo, Yu Dong, Hu Yi. Distribution Scheduling Optimization of Discrete Manufacturing Materials Based on Variable Neighborhood Genetic Algorithms[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2019, 1(11): 152-155.
13	徐云琴, 叶春明, 曹磊. 含有AGV的柔性车间调度优化研究[J]. 计算机应用研究, 2018, 35(11): 3271-3275.
	Xu Yunqin, Ye Chunming, Cao Lei. Research on Flexible Job-Shop Scheduling Problem with AGV Constraints[J]. Application Research of Computers, 2018, 35(11): 3271-3275.
14	Bilge Umit, Ulusoy Gunduz. A Time Window Approach to Simultaneous Scheuling of Machines Ang Material Handling System in an FMS[J]. Operations Research (S4306-1058), 1995, 43(6): 1058-1070.
15	Fethi Achouri, Mehdi Souier. The Effect of AGVs Number on a Flexible Manufacturing System[C]// ICAAID: The 3rd International Conference on Applied Automation and Industrial Diagnostics. Piscataway, NJ. USA: IEEE, 2019.
16	田旻, 张光军, 刘人境. 粒子群遗传混合算法求解考虑运输时间的FJSP[J]. 运筹与管理, 2019, 28(4): 78-88.
	Tian Min, Zhang Guangjun, Liu Renjing. Solve FJSP Considering Transport Time Via Particle Swarm Genetic Hybrid Algorithm[J]. Operations Research and Management Science, 2019, 28(4): 78-88.
17	张静, 王万良, 徐新黎, 等. 基于改进粒子群算法求解柔性作业车间批量调度问题[J]. 控制与决策, 2012, 27(4): 513-518.
	Zhang Jing, Wang Wanliang, Xu Xinli, et al. Improved Particle Swarm Algorithm for Batch Splitting Flexible Job Shop Scheduling[J]. Control and Decision, 2012, 27(4): 513-518.
18	李小华. 基于粒子群算法的车间作业调度研究[D]. 武汉: 武汉科技大学, 2009.
	Li Xiaohua.Research on Job-Shop Scheduling Problem Based on Particle Swarm Optimization Algorithom[D]. Wuhan: Wuhan University of Science and Technology, 2009.
19	刘明, 董明刚, 敬超. 基于定期竞争学习的多目标粒子群优化算法[J]. 计算机应用, 2019, 39(2): 330-335.
	Liu Ming, Dong Minggang, Jing Chao. Scheduled Competition Learning Based Multi-Objective Particle Swarm Optimization Algorithm[J]. Journal of Computer Applications, 2019, 39(2): 330-335.
20	Deroussi L, Norre S. Simultaneous Scheduling of Machines and Vehicles for the Flexible Job Shop Problem[C]// International Conference on Metaheuristics and Nature Inspired Computing. Heidelberg, Germany: Springer, 2010: 1-2.
21	Jarboui Bassem, Siarry Patrick, Teghem Jacques. Metaheuristics for Production Scheduling[M]. New Jersey USA: John Wiley & Sons, Inc., 2013: 465-493.
22	Qiao Zhang, Maniera Hervé, Manier Marie-Ange. A Modified Shifting Bottleneck Heuristic and disjunctive Graph for Job Shop Scheduling Problems with Transportation Constraints[J]. International Journal of Production Research (S0020-7543), 2014, 52(12): 985-1002.
23	Huang Xiaobao, Yang Lixi. A Hybrid Genetic Algorithm for Multi-Objective Flexible Job Shop Scheduling Problem Considering Transportation Time[J]. International Jour-nal of Intelligent Computing and Cybernetics (S1756-378X), 2019,12(2): 154-174.

数据集	初始解		最优解
数据集	随机	启发式	随机	启发式
FJSP₁	266.71	207.47	191.96	184.71
FJSP₂	223.81	174.67	157.68	152.25
FJSP₃	241.79	186.32	167.14	161.54
FJSP₄	234.97	185.30	163.25	161.52
FJSP₅	171.42	135.57	117.65	112.66
FJSP₆	258.38	203.79	188.75	183.08
FJSP₇	229.74	178.48	162.70	159.80
FJSP₈	327.09	244.87	235.71	229.19
FJSP₉	275.10	213.96	194.65	185.80
FJSP₁₀	330.92	253.54	243.98	237.05
提升效率		57.58		5.59

数据集	SBN	Tabu	DPSO		HDPSO
数据集	SBN	Tabu	Best	Mean	Best	Mean
FJSP₁	156	160	152	156.2	148	154.4
FJSP₂	124	128	126	132.0	118	130.4
FJSP₃	140	162	132	137.4	130	135.4
FJSP₄	132	126	132	138.2	126	133.4
FJSP₅	96	100	96	97.8	94	95.2
FJSP₆	148	152	154	158.2	150	154.0
FJSP₇	132	132	126	134.8	126	131.0
FJSP₈	191	188	188	192.5	186	190.3
FJSP₉	154	162	154	157.8	152	154.8
FJSP₁₀	-	-	192	199.2	190	196.8

数据集	Tran0~1		Tran1~5
数据集	DPSO	HDPSO	DPSO	HDPSO
8×8	17.63	16.46	28.00	24.23
10×10	9.08	8.46	15.79	12.00
15×10	19.52	18.19	50.62	28.50

数据集	W
数据集	1	2	3	4	5
FJSP₁	214	148	132	132	132
FJSP₂	180	118	116	114	114
FJSP₃	190	130	122	120	120
FJSP₄	198	126	112	104	102
FJSP₅	142	94	94	94	94
FJSP₆	202	150	138	134	134
FJSP₇	210	126	108	100	94
FJSP₈	250	186	178	178	178
FJSP₉	206	152	144	134	134
FJSP₁₀	264	190	178	168	168
提升效率		63.6	9.8	4.4	0.8

[1]	陈魁, 毕利. 改进粒子群算法在考虑运输时间下的FJSP研究[J]. 系统仿真学报, 2021, 33(4): 845-853.
[2]	李珂, 王艳, 纪志成. 基于混合策略的入侵杂草算法的FJSP问题研究[J]. 系统仿真学报, 2018, 30(5): 1918-1926.
[3]	张新, 李珂, 严大虎, 纪志成. 改进入侵杂草算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2018, 30(11): 4469-4476.
[4]	张晓星, 王艳, 严大虎, 纪志成. 改进的混合蛙跳算法求解柔性作业车间调度[J]. 系统仿真学报, 2017, 29(9): 2093-2099.
[5]	许世鹏, 吴定会, 孔飞, 纪志成. 基于改进鸡群算法的柔性作业车间调度问题求解[J]. 系统仿真学报, 2017, 29(7): 1497-1505.
[6]	戴月明, 王明慧, 王春, 王艳. 骨干双粒子群算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2017, 29(6): 1268-1276.
[7]	张国辉, 吴立辉, 聂黎, 王永成. 考虑机器故障的柔性作业车间鲁棒调度方法[J]. 系统仿真学报, 2016, 28(4): 867-873.
[8]	田娜, 纪志成. 改进量子粒子群求解多目标柔性作业车间调度[J]. 系统仿真学报, 2015, 27(12): 2948-2957.