无缓存流水线生产系统中AGV调度问题的研究

doi:10.12068/j.issn.1005-3026.2024.01.008

摘要/Abstract

摘要：

针对无缓存流水线生产系统中的AGV（automated guided vehicle）调度问题提出了复合评分的启发式调度算法，降低了系统中AGV执行任务的间隔等候时间.首先，通过建立数学模型，对目前主流的AGV规模估计方法做出了改进.其次，提出了一种新的基于复合评分禁忌搜索的AGV前瞻调度算法.不同于目前主流的以空驶距离为优化目标的调度算法，该算法能够以最小化工件延误时间、最小化AGV空驶距离等多目标来统筹调度AGV.最后，为验证所提算法的有效性，从多个角度与已有算法进行了实验对比.仿真实验结果表明，相较于其他算法，提出的前瞻调度算法能够更有效地解决无缓存流水线生产系统这一新场景的AGV调度问题.实车实验也证明了该算法在实际生产中的有效性.

关键词: AGV调度算法, AGV规模确定算法, 禁忌搜索算法, 流水线生产系统

Abstract:

To solve the AGV（automated guided vehicle） scheduling problem in the no-buffer assembly line， a heuristic scheduling algorithm base on composite score is proposed， reducing the waiting time of AGVs when execute tasks in the system. Firstly， the classical AGV fleet size determination algorithm based on the mathematical model is improved. Then， an improved tabu search-based AGV look-ahead scheduling algorithm （LSA） is proposed， which has a composite score strategy. Different from the most reported algorithms， LSA takes parts delay time， AGV empty travel distance and other objects into account. Finally， the proposed algorithms are compared with other reported algorithms. The simulation experiments prove that LSA has better performance than other algorithms. The robotic experiments prove that the proposed algorithm works well in actual production scenarios.

Key words: AGV scheduling algorithm, AGV fleet sizing algorithm, tabu search algorithm, assembly line

中图分类号:

TP 278

汪星恺, 吴维敏, 邢子超, 牛昊一. 无缓存流水线生产系统中AGV调度问题的研究[J]. 东北大学学报（自然科学版）, 2024, 45(1): 58-67.

Xing-kai WANG, Wei-min WU, Zi-chao XING, Hao-yi NIU. Research on the AGV Scheduling Problem in the No-buffer Assembly Line[J]. Journal of Northeastern University(Natural Science), 2024, 45(1): 58-67.

图/表 18

图1 流水线生产加工示意图

Fig. 1 Processing diagram in assembly line

表1 数学符号

Table 1 Mathematical symbols

数学符号	说明
$T$	运输任务集合，大小为 $t$ ， $T = T i \| i = 1,2, …, t$
$R$	AGV集合，大小为 $r$ ， $R = R i \| i = 1,2, …, r$
$M$	设备集合，大小为 $m$ ， $M = M i \| i = 1,2, …, m$
$F i$	任务 $T i$ 运输总花费时间
$X i j$	任务分配决策变量
$t i j 0$	AGV执行任务的空驶时间
$t i j 1$	AGV执行任务的载货时间
$t L$	AGV载货动作时间
$t U$	AGV卸货动作时间
$t i W$	任务等候后序设备空闲的时间
$t i S$	任务取货完成时间
$t i F$	任务所运送货物的运抵当前设备时间
$M i → M j$	加工先后顺序，先由 $M i$ 加工后由 $M j$ 加工
$d (M i, M j)$	设备 $M i$ 到设备 $M j$ 的距离
$d (R i, M j)$	AGV $R i$ 到设备 $M j$ 的距离

表1 数学符号

Table 1 Mathematical symbols

数学符号	说明
$T$	运输任务集合，大小为 $t$ ， $T = T i \| i = 1,2, …, t$
$R$	AGV集合，大小为 $r$ ， $R = R i \| i = 1,2, …, r$
$M$	设备集合，大小为 $m$ ， $M = M i \| i = 1,2, …, m$
$F i$	任务 $T i$ 运输总花费时间
$X i j$	任务分配决策变量
$t i j 0$	AGV执行任务的空驶时间
$t i j 1$	AGV执行任务的载货时间
$t L$	AGV载货动作时间
$t U$	AGV卸货动作时间
$t i W$	任务等候后序设备空闲的时间
$t i S$	任务取货完成时间
$t i F$	任务所运送货物的运抵当前设备时间
$M i → M j$	加工先后顺序，先由 $M i$ 加工后由 $M j$ 加工
$d (M i, M j)$	设备 $M i$ 到设备 $M j$ 的距离
$d (R i, M j)$	AGV $R i$ 到设备 $M j$ 的距离

图2 AGV作业调度

Fig. 2 AGV scheduling in assembly line

图3 运输任务的两个阶段

Fig. 3 Two steps of a transportation task

图4 禁忌搜索算法解构建

Fig. 4 Solution structure of tabu search algorithm

图5 改派AGV生成邻域

Fig. 5 Neighbor solution generation by reallocating AGV

图6 插入执行任务生成邻域

Fig. 6 Neighbor solution generation by inserting tasks

图7 基于禁忌搜索的前瞻调度算法流程图

Fig. 7 Flow chart of look‐ahead scheduling algorithm based on tabu search

表3 标准数据集实验结果

Table 3 Experiment results on benchmark

案例	搜索时间/s		搜索结果		已发表最优值
案例	文献［8］	LSA	文献［8］	LSA	已发表最优值
EX11	18.6	2.5	96	98.8	96
EX21	28.7	4.2	103.2	105.9	100
EX31	33.9	5.9	103.2	104.8	99
EX41	47.6	4.2	115.4	116.8	112
EX51	19.4	3.7	87.7	94.6	87
EX61	45.5	8.1	120.7	123.4	118
EX71	61.4	11.9	118.4	118.2	111
EX81	57.5	5.2	161	161.1	161
EX91	34.9	2.9	117.1	122.7	116
EX101	65.4	7.9	150.8	160.9	146
EX12	18.0	0.4	82	81.9	82
EX22	30.1	4.1	77.8	80.6	76
EX32	34.2	4.6	85	86.3	85
EX42	47.2	5.0	90.9	92.5	87
EX52	18.3	3.8	69	72.8	69
EX62	44.9	4.3	99	101.9	98
EX72	62.6	7.7	83.9	81.1	79
EX82	58.4	6.9	151	151.4	151
EX92	32.3	6.4	102.6	104.7	102
EX102	66.8	8.7	136.9	138.4	135
EX13	18.9	4.0	84	84.7	84
EX23	28.2	4.2	86	86.0	86
EX33	37.3	6.1	86.3	86.6	86
EX43	49.0	5.9	93	92.7	89
EX53	21.1	1.9	74.6	76.6	74
EX63	53.6	6.9	103.9	104.9	103
EX73	72.9	9.1	88.3	90.2	83
EX83	65.2	5.0	153	153.5	153
EX93	43.7	5.3	106.1	105.3	105
EX103	74.5	6.6	141.2	140.0	137
EX14	17.3	0.7	103.2	107.8	103
EX24	29.2	5.8	113.8	116.9	108
EX34	35.9	4.2	114.2	113.2	111
EX44	48.5	7.6	130.1	129.2	121
EX54	17.7	3.4	96.8	98.6	96
EX64	44.0	6.1	125.9	122.9	120
EX74	63.2	7.9	133.6	138.3	126
EX84	54.9	6.4	163	163.4	163
EX94	32.4	3.3	123.3	123.0	120
EX104	65.7	8.8	164.3	161.9	157

表4 实验1结果

Table 4 Results of experiment 1

算法	案例	AGV数量	单任务耗时/s	工件耗时/min	与理论差距/%	加工耗时下限/min
LSA+FSDA	4-9	6	96.4	57.9	3.4	56.0
NN+TS	4-9	2	127.2	73.2	30.7	56.0
LSA+FSDA	8-9	6	95.8	99.2	3.3	96.0
NN+TS	8-9	2	127.0	103.8	8.1	96.0
LSA+FSDA	12-9	6	95.8	139.2	2.4	136.0
NN+TS	12-9	2	135.4	144.8	6.5	136.0
LSA+FSDA	4-18	15	92.1	111.3	2.1	109.0
NN+TS	4-18	3	141.2	202.6	85.9	109.0
LSA+FSDA	8-18	9	95.9	197.5	6.8	185.0
NN+TS	8-18	2	127.7	308.0	66.5	185.0
LSA+FSDA	12-18	6	96.7	267.7	2.6	261.0
NN+TS	12-18	2	125.8	315.4	20.8	261.0

图8 “12-18”案例不同车数加工时间

Fig. 8 Makespan of case “12-18” with different AGVs

图9 “12-18”案例4车甘特图

Fig. 9 Gantt chart of case “12-18” with 4 AGVs

图10 “12-18”案例6车甘特图

Fig. 10 Gantt chart of case “12-18” with 6 AGVs

表5 实验2结果

Table 5 Results of experiment 2

$r × T M$	单任务耗时/s			产品加工耗时/min
$r × T M$	TS	IG	LSA	TS	IG	LSA
6×8	137.7	236.7	115.1	209.8	221.1	190.3
6×10	113.9	211.9	107.0	253.2	249.1	226.5
6×12	112.0	205.6	96.7	280.7	281.0	267.7
6×14	105.6	212.7	94.5	319.8	320.5	308.9
6×16	92.8	215.1	86.1	356.7	358.5	324.9
2×12	81.6	166.1	91.8	382.7	320.6	387.8
3×12	92.5	189.5	100.8	301.0	320.1	322.7
4×12	104.8	206.5	101.8	290.9	291.3	290.9
5×12	113.5	223.5	103.4	281.4	290.5	270.6

表5 实验2结果

Table 5 Results of experiment 2

$r × T M$	单任务耗时/s			产品加工耗时/min
$r × T M$	TS	IG	LSA	TS	IG	LSA
6×8	137.7	236.7	115.1	209.8	221.1	190.3
6×10	113.9	211.9	107.0	253.2	249.1	226.5
6×12	112.0	205.6	96.7	280.7	281.0	267.7
6×14	105.6	212.7	94.5	319.8	320.5	308.9
6×16	92.8	215.1	86.1	356.7	358.5	324.9
2×12	81.6	166.1	91.8	382.7	320.6	387.8
3×12	92.5	189.5	100.8	301.0	320.1	322.7
4×12	104.8	206.5	101.8	290.9	291.3	290.9
5×12	113.5	223.5	103.4	281.4	290.5	270.6

图11 “12-18”案例6车甘特图（对比）

Fig. 11 Gantt chart of case “12-18” with 6 AGVs （comparison）

表6 AGV性能参数

Table 6 AGV performance parameters

参数名称	参数值
满载加速度/（m·s^-2）	0.3
空载加速度/（m·s^-2）	0.4
满载最大速度/（m·s^-1）	0.8
空载最大速度/（m·s^-1）	1
装货时间/s	35
卸货时间/s	15

表7 实车测试结果

Table 7 Results of AGV experiments

工件序号	实际耗时/s	差距/%
1	1 001	3.5
2	979	1.2
3	988	2.2
4	1 025	6.0
5	969	0.2
6	1 035	7.1
7	980	1.4
8	1 011	4.6
16	978	1.2
17	973	0.6
18	1 029	6.4
19	1 092	12.9
20	989	2.3
21	1 015	5.0
22	977	1.1
23	985	1.8

参考文献 6

1	Zhou B H， Shen C Y.Multi‐objective optimization of material delivery for mixed model assembly lines with energy consideration［J］.Journal of Cleaner Production，2018，192：293-305.
2	Fazlollahtabar H.Scheduling of multiple autonomous guided vehicles for an assembly line using minimum cost network flow［J］.Journal of Optimization in Industrial Engineering，2018，11（1）：185-193.
3	Zhang L X， Hu Y G， Guan Y.Research on hybrid‐load AGV dispatching problem for mixed‐model automobile assembly line［J］.Procedia CIRP，2019，81：1059-1064.
4	Wang Y Q.The evaluation of buffer effects on bowl versus inverted bowl assembly line arrangements through a simulation model［J］.International Journal of Modelling and Simulation，1995，15（2）：60-64.
5	Buxey G M， Sadjadi D.Simulation studies of conveyor‐paced assembly lines with buffer capacity［J］.International Journal of Production Research，1976，14（5）：607-624.
6	Aziez I， Côté J F， Coelho L C.Fleet sizing and routing of healthcare automated guided vehicles［J］.Transportation Research Part E：Logistics and Transportation Review，2022，161：102679.

[1]	马泽宁, 沙成满, 路明浩. 基于混合果蝇算法的桩锚支护深基坑临界滑面搜索[J]. 东北大学学报（自然科学版）, 2024, 45(1): 120-128.
[2]	李琳;刘士新;唐加福;. B2C环境下订单配送问题的模型与算法[J]. 东北大学学报(自然科学版), 2009, 30(11): 1554-1557.
[3]	梁迪;谢里阳;隋天中;陶泽;. 基于遗传和禁忌搜索算法求解双资源车间调度问题[J]. 东北大学学报(自然科学版), 2006, 27(8): 895-898.
[4]	彭志刚;吴广宇;杨艳丽;徐心和. 一机两流的连铸生产计划模型与算法[J]. 东北大学学报(自然科学版), 2000, 21(3): 244-246.
[5]	李大卫;王梦光. 带有前序关系的旅行商问题的禁忌搜索算法[J]. 东北大学学报:自然科学版, 1997, 18(6): 4--.
[6]	-. 待发表文章摘要预报[J]. 东北大学学报:自然科学版, 1996, 17(4): 4--.