Research on Integrated Scheduling of AGV and Machine in Flexible Job Shop

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

Abstract

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

CLC Number:

TP391.9

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.

Figures/Tables 13

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Table 1

Fig. 7

Table 2

Fig. 8

Table 3

Table 4

Fig. 9

References 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]	Hongliang Zhang, Renman Ding, Gongjie Xu. Energy-Efficient Scheduling of Multi-objective Flexible Job Shop Considering Interval Processing Time [J]. Journal of System Simulation, 2022, 34(9): 1976-1987.
[2]	Jianlin Fu, Guofu Ding, Jian Zhang, Haifan Jiang, Peipei Guo. Multi-Objective Optimization Configuration of AGV System Based on Response Surface and NSGA-II [J]. Journal of System Simulation, 2022, 34(5): 994-1002.
[3]	Chen Kui, Bi Li. Research on FJSP of Improved Particle Swarm Optimization Algorithm Considering Transportation Time [J]. Journal of System Simulation, 2021, 33(4): 845-853.
[4]	Zhang Xiang, Wang Yan, Ji Zhicheng. Research on Dynamic Flexible Job Shop Scheduling Problem Based on Dynamic Interaction Layer [J]. Journal of System Simulation, 2020, 32(11): 2129-2137.
[5]	Li Ke, Wang Yan, Ji Zhicheng. Research on FJSP Problem of Invasive Weed Optimization Based on Hybrid Strategy [J]. Journal of System Simulation, 2018, 30(5): 1918-1926.
[6]	Zhang Xin, Li Ke, Yan Dahu, Ji Zhicheng. Improved Intrusion Weed Algorithm for Solving Flexible Job Shop Scheduling Problem [J]. Journal of System Simulation, 2018, 30(11): 4469-4476.
[7]	Zhang Xiaoxing, Wang Yan, Yan Dahu, Ji Zhicheng. Improved Shuffled Frog-Leaping Algorithm for Solving Flexible Job Shop Scheduling Problem [J]. Journal of System Simulation, 2017, 29(9): 2093-2099.
[8]	Chen Chao, Wang Yan, Yan Dahu, Ji Zhicheng. Research on Dynamic Flexible Job Shop Scheduling Problem for Energy Consumption [J]. Journal of System Simulation, 2017, 29(9): 2168-2175.
[9]	Zhang Guohui, Wu Lihui, Nie Li, Wang Yongcheng. Robust Flexible Job Shop Scheduling Method with Machine Breakdowns [J]. Journal of System Simulation, 2016, 28(4): 867-873.