Research on the AGV Scheduling Problem in the No-buffer Assembly Line

doi:10.12068/j.issn.1005-3026.2024.01.008

Abstract

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

CLC Number:

TP 278

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.

Figures/Tables 18

Fig. 1 Processing diagram in assembly line

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$ 的距离

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$ 的距离

Fig. 2 AGV scheduling in assembly line

Fig. 3 Two steps of a transportation task

Fig. 4 Solution structure of tabu search algorithm

Fig. 5 Neighbor solution generation by reallocating AGV

Fig. 6 Neighbor solution generation by inserting tasks

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

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

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

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

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

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

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

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

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

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

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

References 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]	Ze-ning MA, Cheng-man SHA, Ming-hao LU. Critical Slip Surface Search for Pile-Anchor Supported Deep Foundation Pits Based on Hybrid Fruit Fly Algorithm [J]. Journal of Northeastern University(Natural Science), 2024, 45(1): 120-128.
[2]	ZHOU Bing-hai， FEI Qian-ran. Multi-objective Scheduling Algorithm for Mixed-Model Assembly Line Considering Energy Consumption [J]. Journal of Northeastern University Natural Science, 2020, 41(2): 258-264.