Multi-load AGVS deadlock prevention task scheduling method based on improved imperialist competition algorithm

Abstract

Vehicle production involves a complex process and fast production pace, necessitating timely material delivery. The task scheduling problem of multi-load Automated Guided Vehicle System (AGVS) for auxiliary material distribution in automotive production workshops presents multiple optimization objectives and complex constraints. To enhance on-time delivery of auxiliary materials, this paper proposes a multi-load AGVS deadlock prevention task scheduling method based on improved Imperialist Competition Algorithm (ICA). First, a mathematical model for multi-load AGVS task scheduling is established, aiming to minimize task delivery distance and maximize the remaining time before the production line shuts down due to material shortages. By analyzing the conditions triggering deadlocks in multi-load AGVS, a deadlock prevention constraint based on the remaining trailer capacity of the buffer area is incorporated into the mathematical model. Second, an improved ICA (IICA) based deadlock prevention task scheduling method is designed. To enhance the initial national population quality of the IICA, a heuristic scheduling rule library is constructed to generate high-quality countries. An improved differential evolution algorithm is introduced during the assimilation process to improve convergence speed. Finally, a simulation platform for multi-load AGVS auxiliary material distribution is established. Experimental results indicate that the designed deadlock avoidance strategy effectively prevents deadlock occurrences while enhancing system productivity across all six algorithms. Compared to the other five algorithms, the proposed IICA achieves the highest unit hour production capacity, on-time task completion rate, and production line start-up rate, while maintaining the lowest average task execution time.

Introduction

In recent years, to meet the increasingly personalized and diversified needs of customers, automotive companies have transitioned from traditional large-scale, low-variety production models to mixed production models featuring multiple varieties in small batches [1]. This shift has significantly increased the types and quantities of materials required for automotive production lines. Improving the on-time delivery of materials required for automotive production lines has become a research focus for many automotive companies. The Automated Guided Vehicle System (AGVS) is a multi-mobile robot system used for material distribution, offering numerous advantages such as high flexibility and automation, low operating noise, and strong system scalability [2, 3]. Consequently, an increasing number of automobile companies have adopted AGVS to ensure efficient and timely material delivery.

Given that AGVS is a typical discrete event dynamic system, its planning, design, and control pose several challenges, including guidance path network design [4], task scheduling [5], path planning [6], and traffic management [7]. Among these, AGVS task scheduling primarily addresses the allocation of material distribution tasks to AGVs, which is crucial for achieving on-time material delivery. Despite the extensive literature on AGVS task scheduling, most studies focus on single load AGVS [8]. However, multi-load AGVS is emerging as a new trend in AGVS applications due to its advantages, such as higher transportation capacity and lower traffic congestion rates [9, 10–11]. Currently, research literature on the task scheduling problem of multi-load AGVS is relatively limited, with most studies concentrating on small-scale, low-density multi-load AGVS in general workshop environments.

Taking the environment of automobile assembly production as an example, the fast pace of vehicle production and the substantial need for timely material distribution make the application of multi-load AGVS in this context both large-scale and high-density. This results in the multi-load AGVS scheduling problem being highly complex, dynamic, and uncertain, presenting a significant challenge that automotive production enterprises urgently need to address. Thus, it is imperative to study task scheduling methods tailored to the operational characteristics of multi-load AGVS in automotive production environments.

The remaining sections of this paper are structured as follows. Section "Literature Review" provides a comprehensive review of relevant literature. Section "Problem description and mathematical model" introduces the multi-load AGVS task scheduling problem for auxiliary material distribution in automobile production and establishes the corresponding mathematical model. Section "IICA-based deadlock prevention task scheduling method for multi-load AGVS" designs an improved Imperialist Competition Algorithm (ICA) for the multi-load AGVS task scheduling method. Section "Experimental analysis" validates the effectiveness of the task scheduling method, and finally, conclusions are drawn, and future research prospects are presented.

Literature review

The AGVS task scheduling problem has always been a prominent topic in the field of AGVS research. In recent years, many scheduling methods have emerged to address the multi-load AGVS task scheduling problem under different application environments. These methods can generally be categorized into two types: static scheduling and dynamic scheduling.

Regarding static scheduling methods for multi-load AGVS, several significant contributions have been made [9]. Constructed a mathematical model that aimed at minimizing travel time and designed an improved memetic particle swarm optimization algorithm to address the multi-load AGV task scheduling problem in flexible manufacturing systems [12]. Focused on the multi-load task scheduling problem in container terminals, constructed corresponding mathematical models, and designed a shuffling frog jumping algorithm based on priority rules. Rahimikelarijani, Fazlollahtabar, and Nayeri; Rahimikelarijani, Saidi-Mehrabad, and Barzinpour developed a nonlinear mathematical programming model for multi-load AGVS based on tandem layout and designed a variable neighborhood search algorithm [13, 14]. Chol and Gun proposed a multi-agent scheduling method based on a genetic algorithm to minimize the operational time of tandem multi-load AGVs [15]. Dang et al. aimed at minimizing task delays and AGV travel costs by developing a mixed-integer linear programming model and designing an algorithm to address task scheduling with battery capacity constraints [16]. Wang and Wu proposed an improved ant colony optimization simulated annealing algorithm based on multi-attribute scheduling rules to solve the task scheduling problem of multi-load AGVS with buffer capacity, aiming at minimizing the maximum completion time [17]. Yan and Jackson developed a mathematical model using Colored Petri Nets to analyze the transport performance of multi-load AGVs under time constraints across various scenarios [18]. Li et al. established a mathematical model to optimize the total travel distance, AGV workload, and latest task deadline for AGV tasks, proposing an improved harmony search algorithm to solve the optimization problem [19]. However, as AGVS are typical discrete event dynamic systems, static scheduling methods often cannot adapt to the dynamic changes of the system. Therefore, dynamic scheduling methods based on heuristic scheduling rules or intelligent optimization algorithms are more practical.

In recent years, many dynamic scheduling methods based on heuristic scheduling rules and intelligent optimization algorithms have been developed to address multi-load AGVS task scheduling problems. For instance, Ho and Liu decomposed the multi-load AGVS task scheduling problem into four sub-problems: load/unload selection scheduling, unload scheduling, load point scheduling, and job selection scheduling [20]. Liu and Yih subsequently designed heuristic scheduling rules for these sub-problems [21]. Chawla and Angra compared the effectiveness of different job selection scheduling rules for multi-load AGVS, with simulation results indicating that the job selection scheduling rule based on the destination similarity criterion performed the best [22]. Angra and Chawla analyzed the actual scheduling effects of multi-load AGVS under five loading task selection scheduling rules [23]. Ramanaiah and Ashok evaluated the performance of heuristic scheduling rules for multi-load AGVS under different guide path layouts [24]. Building on these studies, researchers conducted computer simulations to evaluate the effectiveness of various scheduling [25, 26–27]. In addition, Azimi and Yarmohammadi applied stepwise regression methods to construct multi-objective optimization decision models [28]. Hu and Huang investigated conflict-free task scheduling methods for multi-load AGVS with a network layout [29]. They designed a task allocation method based on adjacent combinations and shortest paths, and proposed an optimization task allocation method using a variable neighborhood heuristic search algorithm. Krishnamoorthy et al. introduced a memory loop scheduling algorithm based on local search probability to solve the multi-load AGVS task scheduling problem in spinning mills, aiming at maximizing machine capacity [30]. Yu et al. addressed the multi-load AGVS task scheduling problem in automated sorting warehouses by designing a two-stage heuristic algorithm to minimize the maximum processing completion time [31]. Zou et al. constructed a mixed-integer linear programming model and proposed a new iterative greedy algorithm for a multi-compartment automated guided vehicle system, with the goal objective of minimizing total costs [32]. Huo et al. proposed a non-dominated sorting genetic algorithm II (NSGA-II) to address the multi-load AGV task scheduling problem, with the optimization objective of minimizing loading and unloading delays as well as total energy consumption [33]. Lin et al. introduced an improved NSGA-II based task scheduling method for autonomous storage and retrieval systems using multi-load AGVs [34]. Xiao et al. designed a multi-attribute heuristic scheduling rule for the task scheduling problem of multi-load AGVS in flexible job shop environments [35]. However, the aforementioned studies primarily target AGVS in general job shop environments. Compared to complex product assembly and production environments such as those in automotive and household appliance industries, AGVS in general job shop environments face lower requirements for material delivery timeliness, fewer constraints, and fewer AGVS quantities.

Using the multi-load AGVS in the automotive production environment as an example, the fast pace of automotive production, limited workshop space, and the need for timely material delivery create a highly complex and dense scheduling problem. The large scale and high density of multi-load AGVS in this setting significantly increase the difficulty of task scheduling. Dong et al. proposed a material distribution strategy that considers uncertain abnormal disturbances for addressing the multi-load AGVS task scheduling problem in automobile production workshops [36].

For the material distribution problem in the automotive production environment, Zhou et al. decomposed the issue into four sub decision problems: material handling task generation, scheduling decision, and material handling task selection. They constructed a scheduling rule knowledge base using simulation models and employed artificial neural networks [37], support vector machines [38], as well as reinforcement learning to dynamically select the optimal scheduling rules from the knowledge base, thereby improving the on-time delivery of materials [39]. All these methods, which are based on heuristic scheduling rules, offer short decision times and rapid response speeds. However, they lack the ability to predict or evaluate the actual scheduling effect, are deficient in global optimization capabilities, and struggle to achieve multi-objective optimization. In contrast, biologically inspired intelligent optimization algorithms provide advantages such as fast optimization, good robustness, and strong global optimization capability. Recently, researchers have introduced various intelligent optimization algorithms into AGVS scheduling. For example, Zhou and Zhao developed a mixed integer programming model and proposed a multi-objective quantum-inspired Archimedes optimization algorithm based on reinforcement learning to address the single-load AGV auxiliary material distribution problem in automotive hybrid assembly lines [40]. Xia et al. established a mixed-integer programming model and proposed a heuristic approach based on an artificial immune genetic algorithm [41]. Other notable intelligent optimization algorithms include genetic algorithms [42, 43], particle swarm optimization algorithms [44], evolutionary algorithms [45], and hyper-heuristic algorithms [46]. These studies suggest that combining the advantages of heuristic scheduling rules with intelligent optimization algorithms can achieve multi-objective global optimization while also providing shorter response times, offering a promising approach to solving multi-load AGVS task scheduling problems.

Additionally, there are two types of deadlock phenomena in AGVS: the first type caused by path conflicts between AGVs [47] and the second type caused by the limited capacity of material buffer zones [48]. Both types of deadlocks can paralyze AGVS operations, leading to irreversible losses. Therefore, avoiding these deadlocks is a critical challenge in AGVS scheduling. Currently, the first type of deadlock is generally addressed through deadlock-free traffic control methods [49, 50–51]. Consequently, this paper focuses on designing a strategy to avoid the second type of deadlock. There is some existing research on strategies to prevent the second type of deadlock. For instance, designed a deadlock avoidance strategy based on resource-oriented colored Petri nets to prevent deadlocks in single load AGVS [52]. However, Petri nets have limitations related to complexity and state space explosiveness [53], making them challenging to apply in large-scale AGVS. Park and Kim considered the capacity constraints of material buffer zones to prevent material congestion in production workshops and improve AGV scheduling efficiency [54]. Murakami thoroughly considered conflict avoidance, AGV capacity, and workstation buffer capacity constraints, constructing a time–space network (TSN) model, but did not provide a solution algorithm [55]. Moreover, previous research on the second type of deadlock mainly focuses on single-load AGVS in workshop environments. The conditions that trigger deadlocks in AGVS are closely related to the material distribution process and application environment. However, there is currently limited research on deadlock avoidance strategies for multi-load AGVS. Only Haining et al. have designed a deadlock avoidance rule for multi-load AGVS in the job shop environment [35]. There is currently no research literature on deadlock prevention strategies for multi-load AGVS in automotive production environments. Therefore, it is crucial to study the conditions that trigger deadlocks in multi-load AGVS within automotive production environments, design corresponding deadlock avoidance strategies, and integrate them into the task scheduling methods for multi-load AGVS.

ICA was first proposed by Atashpaz and Lucas, as an intelligent optimization algorithm that simulates the mechanisms of imperialist competition, annexation, and development [56]. Since its inception, ICA has been successfully applied in various fields such as job shop scheduling [31, 57], structural optimization [58], and flow shop scheduling [59]. These studies indicate that, compared with classical intelligent optimization algorithms like genetic algorithms and particle swarm optimization, ICA offers faster convergence and stronger global optimization capability, making it prominent in the field of metaheuristic algorithms. However, with the merger and demise of empires, traditional ICA struggles to maintain population diversity, leading to premature convergence. Therefore, further improvements are necessary to enhance its ability to escape local optima and improve optimization stability [46].

Based on the above analysis, the main contributions of this paper are as follows:

1. Currently, there is no existing model or algorithm specifically for multi-load AGVS task scheduling in the automotive production environments. This paper establishes a mathematical model for multi-load AGVS task scheduling for automotive production auxiliary material transportation. The model aims at minimizing task delivery distance and maximizing the remaining time before production line shutdown due to material shortages. By analyzing the triggering conditions of the second type of deadlock phenomenon, a deadlock avoidance constraint based on the remaining capacity of the trailer buffer area is established. This constraint is incorporated into the mathematical model to achieve multi-objective deadlock prevention task scheduling for multi-load AGVS.

2. Based on the characteristics of the constructed deadlock avoidance task scheduling model, the classical ICA has been improved, resulting in a deadlock avoidance scheduling method based on the improved ICA (IICA). By constructing a heuristic scheduling rule library to generate high-quality initial countries, the quality of the initial population is enhanced. To improve the convergence speed of the classical ICA, an improved differential evolution algorithm based on adaptive differential factors is introduced during the assimilation process. Additionally, to prevent the population from falling into local optima, a disturbance mechanism is introduced after assimilation and revolution.

Problem description and mathematical model

Problem description

Taking the auxiliary material distribution multi-load AGVS of a new energy automotive chassis assembly line as an example, its schematic layout is shown in Fig. 1. The chassis assembly line consists of 45 assembly stations and uses Electric Monorail System (EMS) carts as carriers for in-process vehicles. Vehicles enter the chassis assembly line at station 1 and sequentially pass through each assembly station. At each station, assembly equipment or operators assemble parts according to process requirements, and the vehicle exits the assembly line from station 45. Auxiliary materials required for assembly operations at each station are loaded into trailers and transported by multi-load AGVs to the buffer area at each station. To focus on the multi-load AGVS task scheduling problem, the following assumptions are made regarding the auxiliary material preparation and distribution process:

[See PDF for image]

Fig. 1

Multiple-load AGVS for auxiliary material distribution in the chassis assembly line of a new energy automobile

1. The chassis assembly line uses a production beat as the basic time unit, with each station consuming one set of auxiliary materials per beat. If the buffer is out of stock at the beginning of the operation, the entire assembly line will shut down due to material shortages. Therefore, the AGV task scheduling system must ensure that all assembly stations have a sufficient supply of auxiliary materials.

2. It is assumed that the auxiliary materials in the warehouse are sufficient. The required auxiliary materials for each workstation are pre-loaded into trailers in complete sets in the buffer area. Each trailer can only load the auxiliary materials required for the same workstation, but multiple sets can be loaded according to capacity. After loading, the trailer waits for AGV delivery in the buffer area.

3. The towing AGV achieves trailer towing through an automatic coupling and decoupling mechanism at the rear end, and the number of trailers that can be towed by each AGV is limited. After being fully loaded, the multi-load AGV departs from the buffer area and follows the last in, first out (LIFO) rule along the shortest transportation route to various assembly workstations to unload trailers. Due to limited trailer capacity at each workstation, if the AGV reaches a workstation without trailer unloading capacity, it will continue to run along the shortest circular path until sufficient capacity is obtained.

4. To avoid affecting the operation of other AGVs, idle AGVs run along their shortest circular path until they receive a new transportation task.

5. To simplify the problem, the impact of AGV charging and failures are not considered.

Since each workstation consumes a set of auxiliary materials for each production beat when the assembly line operates normally, the required auxiliary materials for each workstation during each scheduling cycle are predictable and deterministic (if the scheduling process is triggered periodically). When the scheduling process is triggered, the statuses of all AGVs and the auxiliary material inventory at each workstation are also determined. Consequently, the task scheduling within each scheduling cycle can be treated as a static scheduling problem, which can be effectively addressed using intelligent optimization algorithms.

Mathematical model

Symbol definition

See Table 1.

Table 1. Symbol definition

NO	Symbol	Definition
1	${\mathrm{\Omega }}_G=\{G_m\mid m\in Nand1\le m\le N_G\}$	The set of multi-load AGVs, where $N_G$ is the total number of multi-load AGVs in the system
2	${\mathrm{\Omega }}_W=\{W_i\mid i\in Nand1\le i\le N_W\}$	The set of assembly stations, where $N_W$ represents the total number of stations on the assembly line
3	${\mathrm{\Omega }}_P=\{P_j\mid j\in Nand1\le j\le N_W\}$	The set of parking points for trailers at each assembly station
4	$P_0$	The parking point for trailers in the material storage area
5	ν	The speed of AGV during operation
6	$S_m$	The total distance traveled by AGV ​$G_m$ to complete all tasks in a single operation
7	$d(P_i,P_j)$	The shortest distance from station $P_i$ to station $P_j$
8	$\tau (i,j)$	The average time for AGV to travel directly from station $P_i$ to station $P_j$, with an initial value of $d_{\mathit{ij}}/v$
9	$P(G_m)$	The current position of AGV $G_m$
10	$\overline{N_P}$	The average number of stations visited by all AGVs for a single delivery
11	$C^G$	The maximum number of trailers that AGV can tow
12	$C_i$	The number of trailers that station $W_i$ can accommodate
13	$J_i^t$	The number of sets of materials at station $W_i$ at time $t$, where $t=0$ indicates the current time
14	$K_i$	The maximum number of sets of materials that each trailer at station $K_i$​ can carry
15	$I_i^t$	The number of non-empty trailers at station $W_i$ at time $t$
16	$O_i^t$	The number of empty trailers at station $W_i$ at time $t$
17	$T_i^X$	The task of delivering full trailers to station $W_i$
18	$T_i^Y$	The task of returning empty trailers from station $W_i$
19	$\xi$	The production beat of the vehicle assembly line
20	$P(T_{m,n}^X)$	The target station for the $n$-th full trailer delivery task of AGV $G_m$​ in this operation
21	$P(T_{m,n}^Y)$	The location station for the $n$-th empty trailer return task of AGV $G_m$ in this operation
22	$S{Q}_m^x,i\in Nand1\le i\le N_W$	The execution order of the full trailer delivery tasks of AGV $G_m$​ in this operation
23	$S{Q}_m^Y,i\in Nand1\le i\le N_W$	The execution order of the empty trailer return tasks of AGV $G_m$​ in this operation
24	${\mathrm{\Omega }}_G^B=\{G_m\mid m\in Nand1\le m\le N_G^B\}$	The set of all blocked AGVs, where $N_G^B$ is the number of blocked AGVs in the system
25	${\mathrm{\Omega }}_G^A=\left\{G_m,\mid ,m,\in ,N,a,n,d,1,\le ,m,\le ,N_G^A\right\}$​	The set of all active AGVs, where $N_G^A$ is the number of active AGVs in the system
26	${\mathrm{\Omega }}_G^F=\{G_m\mid m\in Nand1\le m\le N_G^F\}$	The set of all idle AGVs, where $N_G^F$ is the number of idle AGVs in the system
27	${\mathrm{\Omega }}_G^{\mathit{FX}}=\{G_m\mid m\in Nand1\le m\le N_G^{\mathit{FX}}\}$	The set of idle AGVs for delivering full-load trailers, where $N_G^{\mathit{FX}}$ is the number of idle AGVs for delivering full-load trailers, typically $N_G^{\mathit{FX}}=N_G^F/2$
28	${\mathrm{\Omega }}_G^{\mathit{FY}}=\{G_m\mid m\in Nand1\le m\le N_G^{\mathit{FY}}\}$	The set of idle AGVs for delivering empty trailers, where $N_G^{\mathit{FY}}$ is the number of idle AGVs for delivering empty trailers, typically $N_G^{\mathit{FY}}=N_G^F/2$
29	$S{Q}^W=\left\{W_i,\cdots ,W_j,\cdots ,W_k\right\}$	Sequence of workstation replenishment orders
30	$\text{B}\left(T_{m,n}^X\right)$	The loading start time for AGV $G_m$ executing the full-load trailer delivery task $T_{m,n}^X$
31	$E\left(T_{m,n}^X\right)$	The unloading end time for AGV $G_m$ executing the full-load trailer delivery task $T_{m,n}^X$
32	$\text{B}\left(T_{m,n}^Y\right)$	The start loading time for AGV $G_m$ executing the empty trailer return task $T_{m,n}^Y$
33	$E\left(T_{m,n}^Y\right)$	The end unloading time for AGV $G_m$ executing the empty trailer return task $T_{m,n}^Y$

Decision variables

See Table 2.

Table 2. Decision between variables

NO	Variables	Definition
1	$X_i^m\in \left\{\text{0,1}\right\}$	The assignment relationship between the full-load trailer delivery task $T_i^X$ of workstation $W_i$ and AGV $G_m$, where 1 indicates that AGV $G_m$ executes the task for workstation $W_i$ otherwise 0
2	$L_{i,m}^X\in N$	The number of full-load trailers delivered to workstation $W_i$ by AGV $G_m$ in this delivery
3	$Y_i^m\in \left\{\text{0,1}\right\}$	The assignment relationship between the empty trailer return task $T_i^Y$ of workstation $W_i$ and AGV $G_m$, where 1 indicates that AGV $G_m$ executes the empty trailer return task for workstation $W_i$, otherwise 0
4	$L_{i,m}^Y\in N$	The number of empty trailers loaded from workstation $W_i$ by AGV $G_m$ in this delivery
5	${\mathit{SQ}}_m^X=\left\{T_{m,1}^X,\cdots ,T_{m,n}^X,\cdots ,T_{m,N_m^X}^X\right\}$	The sequence of execution of full-load trailer delivery tasks by AGV $G_m$ in this delivery, where $T_{m,n}^X$ is the n-th full-load trailer delivery task to be executed by AGV $G_m$ in this delivery, and $N_m^X$ represents the number of these tasks
6	${\mathit{SQ}}_m^Y=\left\{T_{m,1}^Y,\cdots ,T_{m,n}^Y,\cdots ,T_{m,N_m^Y}^Y\right\}$	The sequence of execution of empty trailer return tasks by AGV $G_m$ in this delivery, where $T_{m,n}^Y$ is the n-th empty trailer return task to be executed by AGV $G_m$ in this delivery, and $N_m^Y$ represents the number of these tasks

Optimization objectives

To enhance the operational efficiency of multi-load AGVS, it is crucial to optimize the order in which AGVs enter each workstation to reduce their travel distance. Therefore, the first optimization objective is to minimize the average distribution distance of tasks. The purpose of material delivery is to ensure an adequate supply of materials to each assembly workstation, thereby preventing assembly line shutdowns due to material shortages. Hence, the second optimization objective is to maximize the remaining time before the chassis assembly line shuts down due to material shortages. The two optimization objectives are expressed as follows:

(1) Minimization of the average task distribution distance:

1

$$f_1=min\overline{D}=\text{min}\frac{1}{N_G}\sum _{m=1}^{N_G}{D}_{m,}$$where:

2

$$\begin{array}{c}\hfill D_m\text{=}\left\{\begin{array}{c}\text{d}\left(\text{P},\left({\text{G}}_{\text{m}}\right),{\text{,P}}_0\right)\text{+d}\left({\text{P}}_0,\text{,P},\left({\text{T}}_{\text{m,}1}^{\text{X}}\right)\right)\text{+}{\sum }_{\text{n}=1}^{{\text{N}}_{\text{m}}^{\text{X}}-1}\text{d}\left(\text{P},\left({\text{T}}_{\text{m,n}}^{\text{X}}\right),\text{,P},\left({\text{T}}_{\text{m,n+}1}^{\text{X}}\right)\right)\text{if}{\text{SQ}}_{\text{m}}^{\text{X}}\ne \mathrm{\Phi }\hfill \\ \text{d}\left(\text{P},\left({\text{G}}_{\text{m}}\right),\text{,P},\left({\text{T}}_{\text{m,}1}^{\text{Y}}\right)\right)\text{+d}\left(\text{P},\left({\text{T}}_{\text{m,}{\text{N}}_{\text{m}}^{\text{Y}}}^{\text{Y}}\right),{\text{,P}}_0\right)\text{+}{\sum }_{\text{n=1}}^{{\text{N}}_{\text{m}}^{\text{Y}}-1}\text{d}\left(\text{P},\left({\text{T}}_{\text{m,n}}^{\text{Y}}\right),\text{,P},\left({\text{T}}_{\text{m,n+}1}^{\text{Y}}\right)\right)\text{if}{\text{SQ}}_{\text{m}}^{\text{Y}}\ne \mathrm{\Phi }\text{.}\hfill \end{array}\right)\end{array}$$

(2) Maximization of the remaining time before the chassis assembly line shutdown due to material shortages:

3

$$f_2=max\left(m,i,n,\left(\partial \right)\right),$$where:

4

$$min\left(\partial \right)=\underset{1\le i\le N_W}{\mathit{min}}{\partial }_i=\underset{1\le i\le N_W}{\mathit{min}}\xi J_i^t.$$

Constraint conditions

The optimization problems presented earlier are constrained by the following conditions:

5

$$\sum _{1\le i\le N_{\text{W}}}{X}_i^m\times \sum _{1\le i\le N_{\text{W}}}{Y}_i^m=0,\forall G_m={\mathrm{\Omega }}_{\text{G,}}$$

6

$$\sum _{1\le i\le N_{\text{W}}}{L}_{i,m}^{\text{X}}\le C^{\text{G}}and\sum _{1\le i\le N_W}{L}_{i,m}^Y\le C^G,\forall G_m={\mathrm{\Omega }}_G$$

7

$$I_i^t+O_i^t\le C_i,\forall W_i={\mathrm{\Omega }}_G$$

8

$$B\left(T_{m,n}^{\text{X}}\right)\ge \frac{d\left(P,\left(G_m\right),,,P_0\right)}{v},\forall T_{m,n}^{\text{X}}\in S{Q}_m^{\text{X}},ifS{Q}_m^{\text{X}}\ne \mathrm{\Phi }$$

9

$$\begin{array}{cc}\hfill E\left(T_{m,n}^{\text{X}}\right)& \ge E\left(T_{m,n-1}^{\text{X}}\right)+\frac{d\left(P,\left(T_{m,n-1}^{\text{X}}\right),,,P,\left(T_{m,n}^{\text{X}}\right)\right)}{v},\hfill \\ \hfill & \forall T_{m,n}^{\text{X}}\in S{Q}_m^{\text{X}},ifS{Q}_m^{\text{X}}\ne \mathrm{\Phi }\hfill \end{array}$$

10

$$B\left(T_{m,1}^{\text{Y}}\right)\ge \frac{d\left(P,\left(G_m\right),,,P,\left(T_{m,1}^{\text{Y}}\right)\right)}{v}ifS{Q}_m^Y\ne \mathrm{\Phi }$$

11

$$\begin{array}{c}\hfill B\left(T_{m,n}^{\text{Y}}\right)\ge B\left(T_{m,n-1}^{\text{Y}}\right)+\frac{d\left(P,\left(T_{m,n-1}^{\text{Y}}\right),,,P,\left(T_{m,n}^{\text{Y}}\right)\right)}{v},\forall T_{m,n}^{\text{Y}}\in S{Q}_m^{\text{Y}},ifS{Q}_m^{\text{Y}}\ne \mathrm{\Phi }\end{array}$$

12

$$\begin{array}{c}\hfill E\left(T_{m,n}^{\text{Y}}\right)\ge B\left(T_{m,N_m^{\text{Y}}}^{\text{Y}}\right)+\frac{d\left(P,\left(T_{m,N_m^{\text{Y}}}^{\text{Y}}\right),,,P_0\right)}{v},\forall T_{m,n}^{\text{Y}}\in S{Q}_m^{\text{Y}},ifS{Q}_m^{\text{Y}}\ne \mathrm{\Phi }\end{array}$$

Constraint (5) ensures that the same AGV $G_m$ cannot simultaneously execute empty trailer return tasks and full trailer delivery tasks. The number of trailers loaded by an AGV each time cannot exceed its maximum trailer capacity as stated in (6). The capacity limitation of the trailer buffer area at the workstation is represented in (7). Additionally, the sequence and time constraints that AGVs must satisfy when executing tasks are defined in (8)–(12). Specifically, full trailers can only be loaded when idle AGVs travel from their docking points to the parts storage area as indicated by (8), while (9) signifies that AGVs must deliver full trailers in sequence. Idle AGVs must travel from their docking positions to the corresponding workstation before the first empty trailer can be loaded, and AGVs must load empty trailers in sequence, as stated in (10) and (12), respectively. Finally, (12) indicates that AGVs must travel to the material storage area to unload all empty trailers after loading them.

System deadlock phenomenon and its triggering conditions

As illustrated in Fig. 2, AGV $G_m$ is currently executing a full material delivery task to Station 10. If the trailer buffer area at Station 10 is full and there are no other AGVs loading empty trailers at this station, AGV $G_m$ will not be able to unload the full trailer. Consequently, AGV $G_m$ can only operate along the shortest loop path where the unloading point is located, a situation referred to as AGV $G_m$ being blocked. If all AGVs are blocked, no one will be able to unload their full trailers, resulting in system deadlock. To determine whether an AGV is in a blocking state, it is necessary first to determine the remaining trailer space that each assembly workstation can accommodate. The remaining trailer space $R_i$ that workstation $W_i$​ can accommodate is defined as follows:

[See PDF for image]

Fig. 2

Schematic diagram of a blocking AGV

13

$$R_i=C_i-I_i^t-O_i^t-\sum _{1\le m\le N_{\text{G}}}{L}_{i,m}^{\text{X}}-\sum _{1\le m\le N_{\text{G}}}{L}_{i,m}^{\text{Y}}$$

Assuming AGV $G_m$​ undertakes a full-material trailer delivery task at a certain assembly station $W_i$​, if the remaining space in the trailer buffer area at station $W_i$​ is zero and there are no additional AGVs available to release the buffer space at $W_i$​, then $G_m$ is blocked. This can be described as:

14

$$if{T}_i^{\text{x}}\in S{Q}_m^{\text{x}}and{R}_i<0then{G}_m\in {\mathrm{\Omega }}_{\text{G}}^{\text{B}}$$

Therefore, the conditions for the system to enter deadlock are:

15

$$N_{\text{G}}^{\text{A}}=N_{\text{G}}-N_{\text{G}}^{\text{B}}=0$$

The deadlock avoidance strategy adopted in this paper ensures that there is always remaining capacity in the trailer buffer area of all stations at any given time, thereby preventing blocked AGVs and system deadlock:

16

$$R_i\ge 0\forall W_i\in {\mathrm{\Omega }}_{\text{W}}$$

IICA-based deadlock prevention task scheduling method for multi-load AGVS

The traditional multi-load AGVS scheduling methods primarily rely on heuristic scheduling rules, which offer the advantages of short decision-making time and fast response. However, these methods fall short in predicting or evaluating the actual scheduling effect, lack global optimization capabilities, and struggle to achieve multi-objective optimization [60]. ICA is a population-based intelligent optimization algorithm. Extensive research has demonstrated that ICA has fast optimization, good robustness, and strong global optimization ability (Zhang et al. 2020). Therefore, based on the characteristics of the mathematical model, this paper focuses on optimizing the order of station replenishment. By combining heuristic scheduling rules with intelligent optimization algorithms, we propose an IICA-based deadlock prevention task scheduling method for multi-load AGVS. The entire process of the method is illustrated in Fig. 3. First, a heuristic rule library is constructed for generating workstation replenishment sequences. This library is used to generate high-quality countries as members of the initial population. Each country undergoes individual multi-objective evaluations. During the evaluation process, heuristic allocation rules determine the relationship between each task and AGV, and prospective prediction mechanisms along with deadlock prevention strategies are used to determine the number of material allocation trailers required for each workstation and the number of empty trailers to be loaded. After completing the multi-objective evaluation of all countries, non-dominated sorting is performed on the initial population to establish the initial imperialist countries and their colonies. New countries are then generated through assimilation and revolution, followed by multi-objective evaluations. Finally, a perturbation mechanism is introduced to avoid the algorithm falling into local optima. The detailed procedures are as follows:

[See PDF for image]

Fig. 3

Overall process of a forward-looking deadlock prevention task scheduling method

Decision cycle of task scheduling process

Since the consumption of auxiliary materials at each workstation is measured by production beat $\xi$, this paper adopts the production beat $\xi$ as a decision cycle to trigger the task scheduling process. At the beginning of the scheduling process, it is necessary to gather information on trailer buffer space at each station in the system (e.g.,$O_i^t$, $I_i^t$, $J_i^t$) and identify the set of idle AGVs ${\mathrm{\Omega }}_G^F$.

Country encoding and decoding

Country encoding and initial country population generation strategy

(1) Country encoding

Although the decision variables for multi-load AGVS task scheduling in an automobile production line are numerous, the primary purpose of multi-load AGV scheduling is to ensure that each assembly workstation has a sufficient supply of auxiliary materials. Therefore, this paper uses the workstation replenishment sequence as the starting point. The workstation replenishment sequence serves as the country encoding, denoted as ${\mathit{SQ}}^W=\left\{W_i,\cdots ,W_j,\cdots ,W_k\right\}$. The order of workstations in the sequence represents the priority for AGV delivery of auxiliary materials. During decoding, a heuristic decoding process, combined with a forward-looking prediction mechanism and deadlock prevention strategy, transforms any workstation replenishment sequence into the corresponding scheduling plan. This encoding method effectively reduces the size of the solution space and helps quickly identify near-optimal solutions.

(2) Initial country population generation strategy

The quality of the initial states significantly affects the early convergence of the algorithm. To improve the quality of the initial states, various system status indicators are selected to monitor the auxiliary material consumption of each assembly workstation, and heuristic rules are designed for generating workstation material replenishment sequences.

In the context of multi-load AGVS for an automobile chassis production line, selectable state indicators mainly include the number of vacant trailers $O_i^t$ and non-vacant trailers $I_i^t$ at workstation $W_i$. By selecting these state indicators or combining multiple state indicators, a heuristic rule library for workstation material replenishment sequence is constructed. The utility value $A_i^t$ for each workstation $W_i$ corresponding to some heuristic rules is calculated as follows:

(a) Priority to workstations with a higher current number of empty trailers:

17

$$A_i^0\downarrow =O_i^0-\sum _{1\le m\le N_G}{L}_{i,m}^Y$$where ↓ indicates that this rule determines the workstation material replenishment sequence from high to low based on their utility value $A_i^0$​, and​${\sum }_{1\le m\le N_G}{L}_{i,m}^Y$ indicates the number of empty trailers in workstation $W_i$​ that have been assigned AGVs but have not yet been transported.

(b) Priority to workstations with fewer currently non-empty trailers:

18

$$A_i^0\uparrow =I_i^0-\sum _{1\le m\le N_G}{L}_{i,m}^X$$where ↑ indicates that this rule determines the workstation material replenishment sequence from low to high based on their utility value $A_i^0$​, and ${\sum }_{1\le m\le N_G}{L}_{i,m}^X$ indicates the number of fully loaded trailers that have been assigned AGVs for distribution but have not yet arrived at the workstation $W_i$.

(c) Multi-attribute rule based on the current system state:

19

$$A_i^0\downarrow =\left(O_i^0,-,\sum _{1\le m\le N_G},L_{i,m}^Y\right)-\left(I_i^0,-,\sum _{1\le m\le N_G},L_{i,m}^X\right)$$

(d) Priority to workstations with more empty trailers at the next replenishment:

20

$$A_i^{t=\tau (0,i)}\downarrow =O_i^0-\sum _{1\le m\le N_G}{L}_{i,m}^Y+\frac{\tau (0,i)}{K\xi }$$

(e) Multi-attribute rule based on the system status at the next workstation replenishment:

21

$$\begin{array}{cc}& A_i^{t=\tau (0,i)}\downarrow \hfill \\ \hfill & =O_i^0-\sum _{1\le m\le N_G}{L}_{i,m}^Y+\frac{\tau \left(0,,,i\right)}{K\xi }\hfill \\ \hfill & -\left(I_i^0,+,\sum _{1\le m\le N_G},L_{i,m}^X,+,C,e,i,l,\left(J_i^0,-,\frac{\tau \left(0,,,i\right)}{\xi }\right),/,K_i\right)\hfill \end{array}$$

The remaining rules in the heuristic rule library will not be elaborated further. Each heuristic rule can generate a workstation material replenishment sequence, thus forming a country in the initial country population. The other individuals in the initial country population will be generated randomly.

Heuristic decoding strategy

To obtain a scheduling scheme that satisfies all the constraints of the constructed mathematical model, this paper integrates proactive prediction mechanisms and deadlock prevention strategies to design a heuristic decoding decision process. This process transforms the currently available AGV set ${\mathrm{\Omega }}_G^F$ and the given workstation replenishment sequence into a deadlock prevention task scheduling plan that satisfies all constraint conditions. In addition, the designed heuristic decoding process ensures that any encoding can be converted into a corresponding feasible scheduling scheme, eliminating the need to address or discard infeasible encodings. The detailed decoding strategy is as follows.

(1) Idle AGVs grouping strategy

According to constraint Eq. (5), the same AGV $G_m$ cannot simultaneously perform both the empty trailer return task and the full trailer delivery task. Therefore, all idle AGVs in the system are divided into two groups: ${\mathrm{\Omega }}_G^{\mathit{FX}}\text{and}{\mathrm{\Omega }}_G^{\mathit{FY}}$. Group ${\mathrm{\Omega }}_G^{\mathit{FX}}$ is responsible for delivering loaded trailers, while group ${\mathrm{\Omega }}_G^{\mathit{FY}}$ handles returning empty trailers to the warehouse. To minimize the empty travel distance during the delivery process of full trailers, $N_G^{\mathit{FX}}$ AGVs closest to the auxiliary material storage area are selected to form the ${\mathrm{\Omega }}_G^{\mathit{FX}}$ group, while the remaining idle AGVs form the ${\mathrm{\Omega }}_G^{\mathit{FY}}$ group.

(2) Scheduling decision for empty trailer return tasks

First, according to the idle AGV grouping strategy, ${\mathrm{\Omega }}_G^{\mathit{FY}}$ is determined. Then, according to constraint Eq. (7), the capacity of the workstation trailer buffer is limited. To ensure timely distribution of auxiliary materials to each workstation based on the given workstation replenishment sequence $S{Q}^W$, this sequence is used as the priority sequence for each empty trailer return task. Therefore, the heuristic process illustrated in Fig. 4 sequentially assigns empty trailer return tasks to idle AGVs in ${\mathrm{\Omega }}_G^{\mathit{FY}}$​, thereby determining $Y_i^m$​, $L_{i,m}^Y$ Y​, and ${\mathit{SQ}}_m^Y$​. In the decision phase, empty trailer return tasks are assigned to the AGV that can arrive at the loading point first. A proactive prediction mechanism is used to predict the number of empty trailers $L_{i,m}^Y$. The detailed steps are as follows:

[See PDF for image]

Fig. 4

Decision-making process for scheduling empty trailer return tasks

Step 1: Input the workstation replenishment sequence ${\mathit{SQ}}^W$ and the set of idle AGVs ${\mathrm{\Omega }}_G^{\mathit{FY}}$ used for returning empty trailers to the warehouse. Initialize the start time of each AGV $G_m$​ in ${\mathrm{\Omega }}_G^{\mathit{FY}}$ to 0, initialize the idle trailer return task execution sequence ${\mathit{SQ}}_m^Y$ to empty, and proceed to Step 2 after completing all initializations.

Step 2: Sequentially select the next workstation from the workstation replenishment sequence ${\mathit{SQ}}^W$, suppose the workstation number is $W_i$, indicating that the current task to be assigned is $T_i^Y$​. Proceed to Step 3.

Step 3: Sequentially calculate the time for each non-fully loaded AGV in ${\mathrm{\Omega }}_G^{\mathit{FY}}$​ to reach workstation $W_i$ after completing the loading of all assigned empty trailers. Assign task $T_i^Y$​ to the AGV $G_m$​ that arrives earliest at workstation $W_i$, i.e., set $Y_i^m=1$, ${\mathit{SQ}}_m^Y={\mathit{SQ}}_m^Y\cup \left\{T_i^Y\right\}$ then proceed to Step 4.

Step 4: To satisfy the constraint Eqs. (10), (11), and (12), utilize the proactive prediction mechanisms to predict the time $B\left(T_{m,N_m^Y}^Y\right)$ when AGV $G_m$ arrives at workstation $W_i$ and the number of unallocated empty trailers $O_i^{B\left(T_{m,N_m^Y}^Y\right)}$ at workstation $W_i$ at that time:

22

$$O_i^{B\left(T_{m,N_m^Y}^Y\right)}=O_i^0+\frac{B\left(T_{m,N_m^Y}^Y\right)}{K\xi }-\sum _{1\le i\le N_W}{L}_{i,m}^Y$$

Based on this information, to satisfy the constraint Eq. (6), determine the number of empty trailers that $G_m$ needs to transport from workstation $W_i$ by Eq. (23), denoted as $L_{i,m}^Y$​, then proceed to Step 5:

23

$$L_{i,m}^Y=\text{min}\left[O_i^{B\left(T_{m,N_m^Y}^Y\right)},,,\left(C^G,-,\sum _{1\le i\le N_W},L_{i,m}^Y\right)\right]$$

Step 5: Update the information in ${\mathit{SQ}}_m^Y$​ and $R_G^{\mathit{FY}}$​. Workstation $W_i$ is removed from ${\mathit{SQ}}_m^Y$​. Additionally, if $G_m$ is fully loaded, it is removed from $R_G^{\mathit{FY}}$​, and proceed to Step 6.

Step 6: Check the information of ${\mathit{SQ}}_m^Y$​ and ${\mathrm{\Omega }}_G^{\mathit{FY}}$​. If both are not empty, proceed to Step 2. Otherwise, proceed to Step 7.

Step 7: The scheduling decision for empty trailer return tasks is completed. Output $Y_i^m$, $L_{i,m}^Y$, and ${\mathit{SQ}}_m^Y$.

(3) Scheduling decision for delivering full trailers

First, determine ${\mathrm{\Omega }}_G^{\mathit{FX}}$ according to the idle AGV grouping strategy. Then, to satisfy constraints (8) and (9), the heuristic process shown in Fig. 5 is used to assign each full trailer delivery task to idle AGVs in ${\mathrm{\Omega }}_G^{\mathit{FX}}$ following the given workstation supply sequence $S{Q}^W$, thereby determining $X_i^m$​, $L_{i,m}^X$, and ${\mathit{SQ}}_m^X$. To minimize AGV travel distance, the assignment of full trailer delivery tasks to idle AGVs is based on the distance between the destination station of the full trailer and the last task destination station of the AGV. A deadlock prevention strategy is employed to determine the number of full material trailers $L_{i,m}^X$ required at each workstation. The detailed steps are as follows:

[See PDF for image]

Fig. 5

Scheduling decision process for full material trailer delivery tasks

Step 1: Initialization. Input the workstation replenishment sequence $S{Q}^W$ and identify the set of idle AGVs ${\mathrm{\Omega }}_G^{\mathit{FX}}$ used for delivering full trailers. Set the start time for each AGV $G_m$​ in ${\mathrm{\Omega }}_G^{\mathit{FX}}$ as the time when $G_m$ begins moving from its docking point to the loading/unloading point $P_0$ in the auxiliary material storage area. Initialize the execution sequence ${\mathit{SQ}}_m^X$ for full trailer delivery tasks to empty. Proceed to Step 2 after completing all initializations.

Step 2: Sequentially select the next workstation number from the workstation replenishment sequence $S{Q}^W$. If the workstation number is $W_i$, this indicates that the current task to be allocated is $T_i^X$​. Proceed to Step 3.

Step 3: To satisfy the constraints (8) and (9), calculate the time for each non-full AGV in ${\mathrm{\Omega }}_G^{\mathit{FX}}$ to arrive at workstation $W_i$ after completing all previously allocated full material trailer delivery tasks. Assign task $T_i^X$ to the AGV $G_m$​ that can arrive at workstation $W_i$ the earliest. Set $X_i^m=1$, ${\mathit{SQ}}_m^X={\mathit{SQ}}_m^X\cup \left\{T_i^X\right\}$, then proceed to Step 4.

Step 4: To ensure that the AGV does not encounter blockages while executing $T_i^Y$, use Eq. (13) to calculate the remaining trailer space $R_i$ that workstation $W_i$ can accommodate. Based on the calculated $R_i$ and the AGV loading capacity constraint described in Eq. (6), the number of full material trailers $L_{i,m}^X$ delivered by $G_m$ to workstation $W_i$ is determined as follows:

24

$$L_{i,m}^X=min⌊R_i,,,\left(C^G,-,\sum _{1\le i\le N_W},L_{i,m}^X\right)⌋$$

If $L_{i,m}^X=R_i$, it indicates that the required full trailers for workstation $W_i$ have been fully allocated. Proceed to Step 5. If $L_{i,m}^X{<R}_i$, it indicates that there is still remaining trailer space at workstation $W_i$. Proceed to Step 3 to add another AGV to perform the full trailer delivery task $T_i^Y$ for workstation $W_i$.

Step 5: Update the information of $S{Q}^W$ and ${\mathrm{\Omega }}_G^{\mathit{FX}}$. Remove workstation $W_i$ from $S{Q}^W$. If $G_m$ is fully loaded, remove it from ${\mathrm{\Omega }}_G^{\mathit{FX}}$​, and proceed to Step 6.

Step 6: Check the information for $S{Q}^W$ and ${\mathrm{\Omega }}_G^{\mathit{FX}}$. If both $S{Q}^W$ and ${\mathrm{\Omega }}_G^{\mathit{FX}}$​ are not empty, proceed to Step 2. Otherwise, proceed to Step 7.

Step 7: The scheduling decision for full trailer delivery tasks is completed. Output $X_i^m$​, $L_{i,m}^X,{\mathit{andSQ}}_m^X$​.

Initializing the empires

Assume that the initial population of countries generated by the initialization strategy is denoted as ${\mathrm{\Omega }}_{\alpha }=\left\{{\alpha }_1,,,,,,,{\alpha }_i,,,,,,,{\alpha }_Q\right\}$, where each solution ${\alpha }_i$ represents an initial country and a potential solution to the original problem. The steps for generating the initial empires are as follows:

Step 1: Decode and evaluate each initial country in ${\mathrm{\Omega }}_{\alpha }$ to compute the objective function values, as described in Eqs. (1) and (3). Once all initial country solutions are evaluated, the objective functions of each country are standardized using deviation normalization, as expressed in Eqs. (25) and (26). For a given initial country ${\alpha }_i$, the deviation normalization formulas are:

25

$$F_1\left({\alpha }_i\right)=(f_1\left({\alpha }_i\right)-f_1^{\mathit{min}})/(f_1^{\mathit{max}}-f_1^{\mathit{min}})$$

26

$$F_2\left({\alpha }_i\right)=(f_2^{\mathit{max}}-f_2\left({\alpha }_i\right))/(f_2^{\mathit{max}}-f_2^{\mathit{min}})$$where $f_1^{max},f_1^{min},f_2^{max},and{f}_2^{min}$ represent the maximum and minimum values of the two objective functions for all individuals in the initial country population.

The deviation normalization process eliminates the varying dimensionalities among the optimization objectives, scales the function values to the range [0, 1], and converts both objectives into minimization problems. Once the normalization is complete, proceed to Step 2.

Step 2: Calculate the cost values for each country by converting the objective function values into cost values. This work introduces the hypervolume (HV) as the primary indicator for evaluating solution quality in multi-objective optimization problems [61]. A larger hypervolume reflects better solution quality and corresponds to a higher cost value. For an initial country ${\alpha }_i$, the cost value $c({\alpha }_i)$ is calculated as:

27

$$c\left({\alpha }_i\right)=HV\left({\alpha }_i,,,{\alpha }_{\text{ref}}\right)=volume\left(s,o,u,\left({\alpha }_i,,,{\alpha }_{\text{ref}}\right)\right)$$where ${\alpha }_{\text{ref}}$ represents the reference country, which is dominated by all countries in the population. The function volume() computes the hypervolume, and $sou\left({\alpha }_i,,,{\alpha }_{\text{ref}}\right)$ denotes the hypercube formed between the country ${\alpha }_i$ and the reference country ${\alpha }_{\text{ref}}$.

After calculating the cost values for all countries, proceed to Step 3.

Step 3: Construct empires and determine the power values for each empire by sorting the countries in descending order based on their cost values. The top $Q_{\text{imp}}$ countries with the highest cost values are designated as imperialists, while the remaining $Q_{\text{col}}$ countries become colonies, which are randomly distributed among the $Q_{\text{imp}}$ imperialists. The number of colonies controlled by an imperialist is determined by its power value. For the K-th imperialist ${\alpha }_{\text{imp}}^K$, its power value $P\left({\alpha }_{\text{imp}}^K\right)$, and the number of colonies $Q_K$ it controls are expressed as:

28

$$P\left({\alpha }_{\text{imp}}^K\right)=\left|c,\left({\alpha }_{\text{imp}}^K\right),/,{\sum }_{K=1}^{Q_{\text{imp}}},c,\left({\alpha }_{\text{imp}}^K\right)\right|$$

29

$$Q_K=round(Q_{\text{col}}\times P\left({\alpha }_{\text{imp}}^K\right))$$where Q represents the number of countries in the initial population, and $round()$ denotes the rounding function.

Each imperialist, along with its allocated colonies, forms an empire. For the imperialist ${\alpha }_{\mathit{imp}}^K$, the corresponding empire ${\mathrm{\Omega }}_K$ is represented as:

30

$${\mathrm{\Omega }}_K=\left\{{\alpha }_{\mathit{imp}}^K,,,{\alpha }_K^1,,,,,{\alpha }_K^j,,,,,,,{\alpha }_K^{Q_K}\right\}$$

Finally, a non-dominated sorting of all countries within each empire is performed. The hypervolume formed by the non-dominated frontier countries is then used to compute the new cost value for the empire. For the empire ${\mathrm{\Omega }}_K$, the cost value $c\left({\mathrm{\Omega }}_K\right)$ is calculated as:

31

$$\begin{array}{cc}\hfill c\left({\mathrm{\Omega }}_K\right)& =HV\left({\mathrm{\Omega }}_K,,,{\alpha }_{\text{ref}}\right)\hfill \\ \hfill & =volume\left(\bigcup _{{\alpha }_K^{1,j}\in {\mathrm{\Omega }}_k^1},s,o,u,\left({\alpha }_K^{1,j},{\alpha }_{\text{ref}}\right)\right)\hfill \end{array}$$where ${\alpha }_K^{1,j}$ represents a country located on the non-dominated frontier in the empire ${\mathrm{\Omega }}_K$; ${\mathrm{\Omega }}_K^1$ denotes the set of all non-dominated frontier countries in ${\mathrm{\Omega }}_K$; and $sou\left({\alpha }_K^{1,j},,,{\alpha }_{\mathit{ref}}\right)$ is the hypercube formed between ${\alpha }_K^{1,j}$ and the reference country ${\alpha }_{\mathit{ref}}$.

Assimilation

Colonial assimilation involves each colony moving towards the colonial imperialist to enhance the overall strength of the empire. Traditional ICA randomly moves colonies a certain distance towards their corresponding imperialists, which reduces population diversity and leads to slow convergence. Yang, Lai, and Xu (2023) introduced the Differential Evolution (DE) algorithm to improve the assimilation process of traditional ICA [62]. Experimental results showed that this improved assimilation process not only helps maintain population diversity but also achieves faster convergence. To further enhance the adaptive assimilation process, Liang et al. (2019) designed a differential factor adaptive adjustment mechanism to solve the mixed flow shop scheduling problem, verifying its superiority. Inspired by these studies, this article proposes an Adaptive Differential Evolution (ADE) to improve the colonial assimilation process. To perform mutation and crossover operations in the ADE, three types of operations, ⊝ , ⊕, and ⊗, are defined for the workstation replenishment sequence. The definitions of these operations are as follows:

Custom subtraction symbol " ⊝ ":

Taking two individuals ${\alpha }_K^i$ and ${\alpha }_K^j$ in the empire ${\mathrm{\Omega }}_K$ as an example, the result of the operation ${\alpha }_K^i\ominus {\alpha }_K^j$ is expressed as ${\alpha }_K^{i\ominus j}$. The principle of implementing ${\alpha }_K^i\ominus {\alpha }_K^j$ with 9 workstations is illustrated in Fig. 6. First, assign index numbers to the individual ${\alpha }_K^j$. Then, directly replace each workstation in individual ${\alpha }_K^i$ with its index number in ${\alpha }_K^j$, and use the replaced sequence as ${\alpha }_K^{i\ominus j}$. For example, if the first workstation number $W_4$ in ${\alpha }_K^j$ has an index number of 3, then the first workstation number in vector ${\alpha }_K^{i\ominus j}$ is $W_3$.

[See PDF for image]

Fig. 6

Subtraction operation in the mutation process of the ADE algorithm

Custom addition symbol " \oplus ":

Taking two individuals ${\alpha }_K^n$ and ${\alpha }_K^m$ in the empire ${\mathrm{\Omega }}_K$ as an example, the result of operation ${\alpha }_K^n\oplus {\alpha }_K^m$ is expressed as ${\alpha }_K^{n\oplus m}$. The principle of implementing ${\alpha }_K^n\oplus {\alpha }_K^m$ with 9 workstations is illustrated in Fig. 7. First, assign index numbers to the individual ${\alpha }_K^m$. Then, directly replace each workstation in individual ${\alpha }_K^n$ with the workstation number corresponding to the index number in ${\alpha }_K^m$, and use the replaced sequence as ${\alpha }_K^{n\oplus m}$. Considering the first workstation number $W_2$ as an example, if the index number 2 in individual ${\alpha }_K^m$ corresponds to workstation number $W_1$, then the first workstation number in vector ${\alpha }_K^{n\oplus m}$ is $W_1$.

[See PDF for image]

Fig. 7

Addition operation in mutation process of the ADE algorithm

Custom crossover symbol "⨂":

Taking two individuals ${\alpha }_K^l$ and ${\alpha }_K^h$ in the empire ${\mathrm{\Omega }}_K$ as an example, the result of the operation ${\alpha }_K^{l}otimes{\alpha }_K^h$ is expressed as ${\alpha }_K^{\mathit{lotimesh}}$. The principle of implementing ${\alpha }_K^{l}otimes{\alpha }_K^h$ with 9 workstations is illustrated in Fig. 8. First, randomly generate a crossover point to divide individual ${\alpha }_K^l$ into two parts. Copy the first half of ${\alpha }_K^l$ directly to ${\alpha }_K^{\mathit{lotimesh}}$. Then, rearrange the workstations in the second part of ${\alpha }_K^l$ according to their order in ${\alpha }_K^h$, and copy them to ${\alpha }_K^{\mathit{lotimesh}}$.

[See PDF for image]

Fig. 8

ADE algorithm crossover operation

(1) Mutation operation

To perform the mutation operation on any colony ${\alpha }_K^i$, the following method is applied: randomly select two colonies ${\alpha }_K^j$ and ${\alpha }_K^m$ from the colony set, and use ${\alpha }_K^{i\ominus j\oplus m}$ as the new colony mutated from ${\alpha }_K^i$. This can be expressed as:

32

$${\alpha }_K^{i\ominus j\oplus }={\alpha }_K^{m}F\odot {\alpha }_K^{i\ominus j}=\left\{\begin{array}{c}{\alpha }_K^m\oplus {\alpha }_K^{i\ominus j},ifrand\left(\text{0,1}\right)\le F\\ {\alpha }_K^{i\ominus j},otherwise\end{array}\right)$$

33

$${\alpha }_K^{i\ominus j}={\alpha }_K^i\ominus {\alpha }_K^j$$

34

$$\text{F}=F_{\mathit{min}}+\left(F_{\mathit{max}},-,F_{\mathit{min}}\right)\frac{G_{\mathit{max}}}{G_{\mathit{max}}+g}$$where F represents the mutation scaling factor, with $F_{\mathit{min}}$ and $F_{\mathit{max}}$ being the lower and upper limits of the mutation scaling factor, respectively, $F_{\mathit{max}}=0.9,F_{\mathit{min}}=0.1$,$G_{\mathit{max}}$ denotes the total number of iterations, and g represents the current iteration number.

(2) Crossover operation

To facilitate the movement of mutated colonies towards the imperialists and accelerate the convergence of the algorithm, the mutated colony ${\alpha }_K^{i\ominus j\oplus m}$ and its corresponding imperialist colony ${\alpha }_{\mathit{imp}}^K$ undergo a crossover operation. The resulting new colony is denoted as $N_{col\_c}^{\mathit{cross}}$, which can be represented as:

35

$${\alpha }_{col\_c}^{\mathit{cross}}=\left\{\begin{array}{cc}{\alpha }_K^{i\ominus j\oplus m}\otimes {\alpha }_{\mathit{imp}}^K,\hfill & ifrand(\text{0,1})\le CR\hfill \\ {\alpha }_K^{i\ominus j\oplus m},\hfill & otherwise\hfill \end{array}\right)$$

36

$$\text{CR}={\mathit{CR}}_{\mathit{min}}+\left({\mathit{CR}}_{\mathit{max}},-,{\mathit{CR}}_{\mathit{min}}\right)\frac{g}{G_{\mathit{max}}+g}$$where CR represents the crossover probability, with ${\mathit{CR}}_{\mathit{min}}$ and ${\mathit{CR}}_{\mathit{max}}$ being the lower and upper limits of the crossover probability, respectively. In this paper, ${\mathit{CR}}_{\mathit{max}}$ is set to 0.5 and ${\mathit{CR}}_{\mathit{min}}$ is set to 0.1. $G_{\mathit{max}}$ denotes the total number of iterations, and g represents the current iteration number.

From (34) and (36), it can be observed that as the number of iterations increases, the mutation scaling factor F gradually decreases, while the crossover probability CR gradually increases. This suggests that in the early iterations, a higher crossover probability is advantageous for expanding the search space and enhancing the global search capabilities. In the later iterations, reducing the mutation proportion factor helps retain dominant individuals, thereby accelerating convergence.

(3) Selection operation

Assuming the number of colonies in Empire K is $Q_K$, the $Q_K$ new colonies obtained through mutation and crossover operations are combined with the original $Q_K$ colonies to form a candidate colony population. Calculate the cost value of each individual in the candidate population and select $Q_K$ optimal and distinct individuals from the candidate population as the new population. If the cost value of the optimal colony in the new population is better than that of the original imperialist, then the optimal colony becomes the new imperialist of empire K. This selection operation ensures a steady increase in the overall power of empire K while maintaining diversity among the colonies, thereby avoiding local optima.

Revolution and exchange

The colonial revolution involves a random perturbation of the colony encoding order, causing certain colonies to mutate within the solution space. This operation effectively increases the algorithm’s search space. The colonial revolution operation is similar to the mutation operation in genetic algorithms (GA). As illustrated in Fig. 9, taking a sequence of six workstation replenishment orders as an example, the revolution operation is performed using four methods: random single-point exchange, random two-point exchange, random single-point forward insertion, and random two-point forward insertion.

[See PDF for image]

Fig. 9

Illustration of the revolution operation

Specifically, assuming the number of colonies in Empire K remains $Q_K$​, each colony undergoes the four types of revolution operations previously mentioned, meaning each original colony can generate four new colonies. Taking the random single-point exchange as an example, two positions, Pos 1 and Pos 2, are randomly selected, and the station numbers corresponding to Pos 1 and Pos 2 are swapped to form a new colony. After all colonies in Empire ${\mathrm{\Omega }}_K$ have undergone the four revolution operations, a new colony candidate set $\mathrm{\Omega }_K^{\ast }$ is obtained. The original and new colonies are combined into a candidate colony population. By calculating the cost values of each colony in the candidate colony population, the $Q_K$​ best colonies are selected as the new colony population. Finally, the imperialist is updated. If the cost value of the best colony in the new colony population is better than that of the original imperialist, the best colony becomes the new imperialist of empire ${\mathrm{\Omega }}_K$.

Disturbance mechanism

After assimilation and revolutionary operations, each colony gradually converges towards the colonial imperialist, reducing the difference between colonies and the colonial imperialist. This ultimately causes the empire ${\mathrm{\Omega }}_K$ to fall into local optima. To maintain diversity among the colonies of the empire, a disturbance mechanism was designed. Using 12 processing stations as an example, the implementation principle of this disturbance mechanism is illustrated in Fig. 10.

[See PDF for image]

Fig. 10

Implementation principle of the designed disturbance mechanism

The specific steps of the operation are as follows: select colonies ${\alpha }_K^a$ and ${\alpha }_K^b$ that have the same cost value within the empire ${\mathrm{\Omega }}_K$. Next, all workstations located in the same position in both colonies will be directly retained in the disturbed new colony based on their original locations, marked as ${\alpha }_K^{(ab)}$. Then, the remaining non-repeating stations will be retained as sequence ${\alpha }_K^{N(ab)}$. A rule will be randomly selected from the constructed heuristic rule library to reorder the sequence ${\alpha }_K^{N(ab)}$. The reordered sequence ${\alpha }_K^{N(ab)}$ will become a new sequence ${\alpha }_K^{Y(ab)}$. Finally, the sequence ${\alpha }_K^{Y(ab)}$ is inserted into the sequence ${\alpha }_K^{(ab)}$​ to form a new colony sequence, which directly replaces the original colony ${\alpha }_K^a$ with the new sequence ${\alpha }_K^{(ab)}$.

Imperial competition

For multi-objective optimization problems, non-dominated sorting must be performed on each imperial population before conducting imperial competition operations. This process involves determining the Pareto rank and crowding distance of each country. Each country is then ranked in ascending order based on their Pareto rank. For countries with the same rank, they are further ranked in descending order based on their crowding distance.

As an important step in ICA, the essence of imperial competition is that weaker empires are gradually absorbed by stronger ones. The comprehensive power of an empire includes the sum of its imperialist countries’ power and the power of all its colonies. For example, let the total power of empire ${\mathrm{\Omega }}_K$ be denoted as $P\left({\mathrm{\Omega }}_K\right)$, its calculation formula as follows:

37

$$P\left({\mathrm{\Omega }}_K\right)=c\left({\mathrm{\Omega }}_K\right)/\sum _{K=1}^{Q_{\text{imp}}}c\left({\mathrm{\Omega }}_K\right)$$

During each imperial competition, the empire with the weakest power will be divided among other empires. As weaker empires are gradually annexed by stronger ones, the algorithm terminates when only one empire with the strongest power remains.

Experimental analysis

To validate the effectiveness and superiority of the proposed deadlock prevention task scheduling method, a case study was conducted using a real-world new energy chassis production line in Nanchang, China. The schematic layout of the production line is illustrated in Fig. 21. The chassis assembly line is divided into two sections, front and rear, comprising a total of 45 assembly stations. Each station has a buffer zone that can accommodate 5 trailers. The full-load trailer loading/unloading zone and trailer parking area are both situated within the trailer buffer area. Auxiliary materials are consumed sequentially by picking up complete sets of parts from the trailer buffer zone, prioritizing trailers with fewer complete sets. The planned production cycle time for automotive chassis assembly, denoted as ξ, is 60 s, with each assembly station requiring one cycle time per operation. The maximum number of trailers that a multi load AGV can carry in a single trip is 4. The AGV runs at a speed of 1 m/s. Based on the layout and parameters of the production line, a corresponding multi-load AGV simulation platform was developed using the Plant Simulation 15.0 software from Siemens. Several validation experiments were conducted on the simulation platform to validate the proposed task scheduling method. All validation experiments were conducted using a Dell laptop equipped with an Intel(R) Core(TM) i5-6200U CPU @ 2.30 GHz 2.40 GHz, 8.00 GB RAM, running Windows 10 Enterprise LTSC (see Fig. 11).

[See PDF for image]

Fig. 11

Simulation platform interface for auxiliary material distribution with multiple-load AGVs in a new energy vehicle chassis assembly line

Verification of initial population generation strategy

To enhance the quality of the initial country population in IICA, this paper employs a carefully designed heuristic rule base to generate high-quality country individuals. To assess the effectiveness of this strategy, two initial population generation methods are compared: the proposed Initial Population Generation Strategy (PIPGS) and a Completely Random Generation Strategy (CRGS), where all individuals in the initial population are generated randomly. At the start of each scheduling process, ten initial populations are generated using the two strategies.

To evaluate the quality of two initial populations, the appropriate evaluation indicators were selected. According to these literatures [61, 63, 64–65], the main indicators were applied for evaluating population quality, including Inverse Generative Distance (IGD), Generative Distance (GD), Hypervolume (HV), and Epsilon Indicator. In this study, the most widely used IGD and HV were selected as evaluation indicators for population quality. The meanings of the two are:

IGD represents the average shortest Euclidean distance from the non-dominated frontier to the true non-dominated frontier of the evaluated population. The smaller the value of IGD, the closer the non-dominated frontier of the evaluated population is to the true non-dominated frontier, reflecting the superiority and diversity of the population.

HV represents the volume of the target space enclosed by each individual in the non-dominated frontier of the population to be evaluated and the reference individual. The larger HV, the better the superiority and diversity of the population.

To evaluate the quality of each initial population, two metrics are used: hypervolume (HV) and inverse generation distance (IGD). For IGD calculation, the combined non-dominated frontier of all populations is considered the true non-dominated frontier. The HV and IGD values of the initial populations associated with the two strategies across three distinct scenarios are presented in Figs. 12 and 13, respectively. As illustrated in Fig. 12, the HV values of the initial populations generated by the PIPGS method are significantly superior to those produced by CRGS. This observation holds true across all three scenarios when considering maximum, average, minimum, and median values. A higher HV value indicates better quality of the non-dominated frontier of the initial population. Furthermore, the range between the maximum and minimum HV values for populations generated by PIPGS is considerably smaller than that for CRGS. This can be attributed to the use of a carefully designed heuristic rule base in PIPGS, which ensures the generation of high-quality individuals that serve as key components of the non-dominated frontier and significantly enhance population stability. Similarly, Fig. 13 demonstrates that the IGD values of initial populations generated by PIPGS are consistently lower than those produced by CRGS in terms of maximum, average, minimum, and median values across all three scenarios. A lower IGD value indicates that the non-dominated frontier of the initial population is closer to the true non-dominated frontier. These findings underscore the effectiveness of the PIPGS developed in this study.

[See PDF for image]

Fig. 12

HV values of initial populations generated by the two strategies at different time points

[See PDF for image]

Fig. 13

IGD values of initial populations generated by the two strategies at different time points

Verification of the optimization capability of the proposed IICA

To evaluate the optimization performance of the proposed IICA, this study compares it with classical algorithms (e.g., ADE, TICA, and MOPSO) and recently developed algorithms for solving similar problems (e.g., NSGA-II and LSPM-WC). The six algorithms and their parameter settings are as follows:

• Improved Imperial Competition Algorithm (IICA): The population size is set to 100, with $Q_{\text{imp}}=20$, the number of iterations is 19, the influence factor is 0.1, the revolution probability is 1, and the selection coefficient is 0.9.

• Traditional Imperial Competition Algorithm (TICA): The parameters for TICA are the same as those for IICA.

• Adaptive Differential Evolution (ADE) [66]: The population size and number of iterations are the same as those for IICA. The mutation scaling factor ranges from a maximum of 0.9 to a minimum of 0.1, and the crossover probability ranges from a maximum of 0.5 to a minimum of 0.1.

• Non-dominated Sorting Genetic Algorithm II (NSGA-II) [33, 34]: The population size and number of iterations are the same as those for IICA. The crossover probability is 0.9, and the mutation probability is 0.1.

• Multi-Objective Particle Swarm Optimization (MOPSO): The population size and number of iterations are the same as those for IICA. The inertia weight is 1.5, the cognitive coefficient is 2, and the social coefficient is 2.

• Local Search Probability Meme Water Cycle (LSPM-WC) Algorithm [30]: The algorithm parameters are configured as follows: the population size is set to 100, the number of rivers is 20, the number of tributaries is 80. The local search probability is 0.9, the crossover probability for meme local search is 0.9, and the mutation probability is 0.1. Additionally, the evaporation rate is 0.3, the rainfall intensity ranges from 0.1 to 0.5, the flow factor is set to 1, and the number of iterations is 20.

For the experimental setup, three scheduling cycles are examined, with the number of AGVs in the system set to 45, 50, and 55. The simulation platform records the populations obtained by six algorithms every 0.25 s. Both the IGD and HV indicators are used to evaluate the populations searched by each algorithm. Each algorithm is executed 10 times for each scheduling cycle, and the comprehensive non-dominated frontier obtained from 10 simulations of all algorithms is used as the true non-dominated frontier for calculating the IGD value. Figures 14 and 15 illustrate the variations in HV and IGD values over time for the populations generated by the six algorithms.

[See PDF for image]

Fig. 14

HV values of populations generated by six different algorithms at various time points

[See PDF for image]

Fig. 15

IGD values of populations generated by six different algorithms at various time points

As shown in Figs. 14 and 15, at the 0.0-s mark, the population generation strategy implemented by IICA results in higher HV values and lower IGD values compared to the other five algorithms, accompanied by a much smaller standard deviation. This indicates that the population generation strategy designed in this study is effective in generating high-quality solutions. As optimization time progresses, the IGD values for all six algorithms decrease significantly, while HV values increase, with standard deviations also decreasing noticeably. This demonstrates that all algorithms progressively converge toward the non-dominated frontier.

Comparing the six algorithms, it is evident that MOPSO converges too quickly because the solutions in the population are overly influenced by the global optimum, often resulting in entrapment within local optima. Furthermore, the fixed inertia weight method complicates the balance between solution diversity and algorithm convergence. Consequently, MOPSO consistently exhibits the highest IGD values and lowest HV values across all evaluations. Unlike MOPSO, TICA maintains population diversity through the evolution of multiple populations, resulting in IGD and HV values that are superior to those of MOPSO, as shown in Figs. 14 and 15. ADE further improves performance by adaptively adjusting its search capability and speed during the early and late stages of iteration using a variable scale factor and cross probability. As a result, its IGD and HV values are slightly better than those of TICA. The LSPM-WC algorithm integrates the water cycle algorithm with a meme algorithm based on local search probability, effectively enhancing the global search efficiency and the quality of local search solutions. As a result, LSPM-WC outperforms ADE, TICA, and MOPSO. NSGA-II demonstrates even better performance by ensuring that dominant genes from the parent population are reliably passed on to offspring through crossover operations. Its mutation operators prevent local optima, while elite retention and domain search strategies ensure high solution quality. Therefore, NSGA-II achieves significantly better IGD and HV values compared to LSPM-WC, ADE, and the other four algorithms. The IICA proposed in this study incorporates ADE in the assimilation process, significantly enhancing the convergence speed of the traditional imperialist competition algorithm. Furthermore, it integrates revolution and exchange strategies to expand the algorithm’s search space. The introduction of a disturbance mechanism prevents rural population from falling into local optimal state, thereby optimizing both solution quality and convergence speed. As demonstrated in Figs. 14 and 15, the IGD and HV values of IICA consistently outperform those of all other algorithms, proving its effectiveness.

Validation of deadlock avoidance strategy

In Section "Heuristic decoding strategy", the number of fully loaded trailers delivered to the workstation is calculated based on (24). This strategy can prevent blockages in the AGV system, thereby avoiding system deadlocks. To verify the effectiveness of this strategy, the simulation platform was used to compare the actual scheduling effects of the following two types of methods.

Type I: IICA, TICA, ADE, NSGA-II, MOPSO, and LSPM-WCA, with deadlock avoidance strategies. The number of full-load trailers $L_{i,m}^X$ for workstation distribution in the scheduling decision of full-load trailer delivery tasks is calculated using (24).

Type II: IICA-N, TICA-N, ADE-N, NSGA-II-N, MOPSO-N, and LSPM-WCA-N, without deadlock avoidance strategies. In the scheduling decision of full-load trailer delivery tasks, it is always ensured that the number of full-load trailers at each workstation is equal to the maximum number of trailers each workstation can accommodate. The number of full-load trailers $L_{i,m}^X$ delivered by AGV $G_m$ to workstation $W_i$ is determined as follows:

38

$$L_{i,m}^X=min⌊\left(C_i,-,I_i^t,-,\sum _{1\le m\le N_G},L_{i,m}^X\right),,,\left(C^G,-,\sum _{1\le m\le N_G},L_{i,m}^X\right)⌋$$

Each algorithm was simulated 10 times, running for 120 h each time, and simulation data were extracted from the 50-th to 120-th hours. In order to comprehensively evaluate the performance of the algorithm, the selected indicators are as follows:

• The average hourly production $\overline{{\theta }_1}$: The number of car bodies assembled per hour on the chassis production line. The higher the value of this indicator, the higher the efficiency of material distribution AGVS operation, and the more sufficient the material guarantee for chassis assembly.

• the number of deadlocks $\overline{\delta }$: The number of deadlocks that occur in multiple simulations. This indicator is mainly used to verify the effectiveness of deadlock avoidance strategies.

• The average execution time of a single fully loaded trailer delivery task $\overline{t_1}$: The lower the indicator, the better the order in which AGV delivers fully loaded trailers to each workstation, and the better the performance of the scheduling method.

• The average execution time of a single empty trailer return task $\overline{t_2}$: The lower the indicator, the better the order in which AGVs transport empty trailers back from each workstation, and the better the performance of the scheduling method.

The corresponding results of ten simulations for scheduling methods with and without the deadlock avoidance strategy are shown in Figs. 16, 17, 18 and 19 respectively.

[See PDF for image]

Fig. 16

Average hourly production $\overline{{\theta }_1}$

[See PDF for image]

Fig. 17

Number of deadlocks $\overline{\delta }$

[See PDF for image]

Fig. 18

Average execution time of a single fully loaded trailer delivery task $\overline{t_1}$

[See PDF for image]

Fig. 19

Average execution time of a single empty trailer return task $\overline{t_2}$

As shown in Fig. 16, the actual productivity is relatively low for algorithms such as IICA-N, NSGA-II-N, and LSPM-WCA-N, due to the lack of deadlock avoidance strategies. Although increasing the number of AGVs can enhance the productivity of the transportation system, even with 65 AGVs, the hourly output remains significantly below the design requirement of 60 vehicles per hour. In contrast, algorithms such as IICA, NSGA-II, and LSPM-WCA, which incorporate the designed deadlock avoidance strategy, achieve higher productivity with fewer AGVs. For instance, with 45 AGVs, the productivity of the six algorithms using the deadlock avoidance strategy improves by more than 383.8% per hour compared to their counterparts without the strategy. This indicates that the designed deadlock avoidance strategy not only prevents system inefficiency but also improves productivity. While NSGA-II and LSPM-WCA demonstrate superiority in terms of productivity, their results consistently fall slightly short of those achieved by the proposed IICA algorithm. Therefore, the IICA algorithm, combined with the deadlock avoidance strategy, exhibits a clear advantage and effectively enhances the productivity of the assembly line.

As shown in Fig. 17, algorithms such as IICA-N, NSGA-II-N, and LSPM-WCA-N experience frequent deadlocks due to the lack of a deadlock avoidance strategy. Although increasing the number of AGVs can improve transportation capacity and reduce the occurrence of deadlocks, even with 65 AGVs, the system still encounters deadlocks, and hourly output remains below the target of 60 vehicles per hour. While theoretically, increasing the number of AGVs indefinitely might meet design requirements by eliminating deadlocks and achieving desired productivity, this approach is neither economically nor practically feasible, particularly in space-constrained workshop environments. In contrast, the six algorithms employing the designed deadlock avoidance strategy successfully prevent deadlocks, demonstrating the effectiveness of the proposed strategy. Therefore, the deadlock avoidance strategy proposed in this article is effective.

Figures 18a and 19a illustrate that as the number of AGVs increases, the average task execution time for all algorithms gradually rises due to the constrained workshop environment. The road network becomes increasingly congested, leading to inevitable waiting times when multiple AGVs pass through the same intersection or road segment simultaneously. Figures 18b and 19b show that the average task execution time for all algorithms without the deadlock avoidance strategy is consistently higher than for those with the strategy, regardless of the number of AGVs. This disparity arises because the absence of a deadlock avoidance strategy causes AGVs performing fully loaded trailer delivery tasks to become blocked when they cannot access trailer unloading space, thereby increasing task execution times. These findings highlight that the proposed deadlock avoidance strategy effectively reduces task execution times and enhances the transportation efficiency of AGVs.

Validation of actual scheduling effectiveness

To further verify the effectiveness of the proposed IICA, we conducted a comparison and analysis of the actual scheduling effects of IICA, ICA, ADE, NSGA-II, MOPSO, and LSPM-WCA methods. Each algorithm was simulated 10 times, running for 120 h each time, and simulation data were extracted from the 50-th to the 120-th hour. The selected indicators are as follows:

• The average execution time of each AGV task $\overline{t_s}$: The lower the indicator, the better the order in which AGV accesses each workstation, and the better the performance of the scheduling method.

• The average task punctuality rate $\overline{\mu }$: The proportion of timely delivery of materials at each workstation, the higher the indicator, the better the performance of the scheduling algorithm

• The average hourly production $\overline{\theta }$: The number of car bodies assembled per hour on the chassis production line.

• The average production line start-up rate $\overline{\eta }$. The proportion of normal production time for the chassis production lines. The higher the indicator, the less downtime the production line experiences due to material shortages.

Among the above four indicators, the first two indicators can directly reflect the operational efficiency of AGVS, while the last two indicators reflect the production efficiency of the chassis assembly line. In this way, the performance of scheduling methods can be reflected from different perspectives. The simulation results of the four indicators corresponding to each method are shown in Figs. 20, 21, 22 and 23, respectively.

[See PDF for image]

Fig. 20

Average execution time for a single task for all AGVs $\overline{t}$

[See PDF for image]

Fig. 21

Average on-time rate of tasks $\overline{\mu }$

[See PDF for image]

Fig. 22

Average hourly productivity $\overline{\theta }$

[See PDF for image]

Fig. 23

Average production line start-up rate $\overline{\eta }$

As shown in Fig. 20, when the system operates with 60 and 65 AGVs, the average task execution time per AGV experiences a sharp increase. Specifically, the task execution times for IICA, NSGA-II, LSPM-WCA, ADE, TICA, and LSPM-WCA increase by 14.5%, 15.39%, 17.33%, 15.4%, 15.2%, 16.13%, and 19.1%, respectively. Similar trends are observed in Figs. 18a and 19a. This phenomenon can be attributed to two main reasons. First, as the number of AGVs in the system increases, the road network becomes more congested, resulting in path conflicts between AGVs and increased traffic delays. Second, although the increased number of AGVs enhances material transportation capacity, and ensures timely trailer delivery to each station, the number of trailers transported per delivery at the same station decreases. This, in turn, increases the number of workstations that each AGV must visit per delivery, leading to longer task distance and execution times of individual AGVs. Therefore, in practical production settings, the number of AGVs should be optimized to balance production pace and minimize task execution times.

Secondly, as shown in Fig. 21, when the system operates with 40 AGVs, the average task timeliness rates across the six algorithms are relatively high. MOPSO performs the worst but still achieves a timeliness rate of 40%, while IICA performs the best, exceeding 65%. The high task timeliness rates can be attributed to two key factors. First, the algorithms are either well-established multi-objective optimization methods or recently developed hybrid algorithms tailored for solving similar scheduling problems, enabling good overall performance. Second, as illustrated in Figs. 16 and 17, significant differences in transportation capacity and deadlock frequency are observed among the six algorithms with and without the designed deadlock prevention strategy, indicating that the designed deadlock prevention strategy indirectly improves task timeliness. As shown in Fig. 23, when the system operates with 40 AGVs, the average production line start-up rate is less than 70%. This is primarily due to an insufficient number of AGVs, which results in frequent material shortages at some assembly stations, hindering the full utilization of the production line. As the number of AGVs increases, both the average task timeliness rate and production line start-up rate improve significantly. Notably, the IICA algorithm is the first to achieve 100% average task timeliness rate and production line start-up rates with 55 AGVs. These results demonstrate that the IICA algorithm designed in this study significantly improves task timeliness and production line efficiency, consistently outperforming the other five algorithms.

As shown in Fig. 22, when the number of AGVs is less than 55, the productivity of the chassis assembly line increases with the addition of AGVs but still fails to meet the designed production capacity of 60 vehicles per hour. The limited number of AGVs restricts transportation capacity, leading to low task punctuality rates (Fig. 21) and insufficient line start-up rates (Fig. 23). As the number of AGVs increases, the system’s transport capacity gradually improves, resulting in higher throughput across all six algorithms. When the number of AGVs reaches 55, IICA is the first to achieve the designed throughput of 60 vehicles per hour, with the highest average task punctuality rate of 99.569% and the highest average line activation rate of 99.828%. IICA consistently outperforms the other five algorithms, demonstrating its superiority over both classic and emerging approaches for multi-load AGVS task scheduling problems. As shown in Fig. 22, significant differences are observed in the standard deviations of throughput values and the average task execution times of AGVs. Notably, IICA exhibits the smallest standard deviation, indicating greater stability in production capacity, lower fluctuations in average task execution times, and higher overall operational consistency in the transport system.

To thoroughly validate the performance of the proposed method, we expanded the analysis through a three-tier experimental system: First, in foundational algorithm performance validation, HV and IGD metrics compared initial population strategies (PIPGS vs. CRGS). Figures 12, 13 box plots demonstrate that heuristic rules substantially enhanced HV values while reducing IGD volatility in initial populations, with multi-scenario statistical tests confirming significant differences. Regarding optimization capability, Figs. 14, 15 dynamic convergence curves establish IICA's superiority in HV/IGD metrics as its adaptive differential evolution mechanism accelerates Pareto frontier convergence and improves solution distribution quality compared to NSGA-II. Finally, deadlock avoidance validation and scheduling effectiveness analysis demonstrated that the buffer-remaining-capacity-based constraint strategy eliminated system deadlocks while scheduling with 55 AGVs achieved 99.569% on-time task rate, 14.5% task execution time reduction, and 99.828% production line startup rate. All visualizations were generated through Plant Simulation experiments, with figures rigorously aligned to analytical discussions to form a closed-loop evidence chain of “data-visualization-conclusions.”

The proposed methodology demonstrates robust performance in controlled environments though certain aspects warrant further refinement including computational efficiency during peak operational density scenarios environmental adaptability under volatile buffer conditions and scalability within dynamically reconfigured production layouts. These considerations present valuable pathways for advancing industrial applicability in future research streams.

Conclusion

This paper focuses on the trailer-type multi-load AGVS for comprehensive material delivery in assembly lines. First, a mathematical model for multi-load AGVS task scheduling was established, aiming at minimizing task delivery distance, and maximizing the remaining time before the production line faces a shutdown due to material shortages. Additionally, by analyzing the deadlock phenomenon of multi-load AGVS, a corresponding deadlock avoidance strategy was designed.

Based on the characteristics of the multi-objective optimization task scheduling mathematical model for multi-load AGVS, a new multi-load AGV deadlock prevention task scheduling method was designed by combining heuristic scheduling rules with the improved IICA. Furthermore, the deadlock prevention strategy and forward-looking prediction mechanism are integrated for individual decoding. To enhance the quality of the initial population, multiple heuristic rules were designed to generate high-quality individuals forming part of the initial population. Finally, a multi-load AGVS simulation platform for automotive chassis material distribution was constructed using Siemens Plant Simulation software, and extensive experiments were conducted using this platform. The results show that the quality of the initial population can be effectively improved by generating part of the individuals through heuristic scheduling rules. The deadlock avoidance strategy designed in this paper not only prevents deadlock phenomena, but also reduces task execution time, thereby improving system productivity. Compared with five other algorithms, the proposed IICA achieves higher chassis assembly line productivity in shorter task execution times.

This article did not consider the impact of AGV charging characteristics and equipment failures on the scheduling performance of multi-load AGVs. In actual AGVS operation, these factors can cause dynamic fluctuations in the number of available AGVs in the system, increasing the complexity of multi-load AGVS scheduling problems. Therefore, addressing the multi-load AGV scheduling problem considering AGV charging characteristics and equipment failure rate will be the future research direction of our research group [31, 58].

In this paper, dynamic uncertain factors such as equipment failure and production plan change are not considered in the algorithm design. In the future, based on these studies [67, 68, 69, 70, 71–72], the AGVS scheduling algorithm with the ability to deal with equipment failure and production plan change will be further developed.

Author contributions

Haining Xiao: Investigation, Methodology, Formal analysis, Data curation, Writing—review & editing, Supervision, Funding acquisition. Bin Zhao: Methodology, Software, Data curation, Visualization, Formal analysis, Writing—original draft, Writing—review & editing, Funding acquisition. Biao Zhang: Investigation, Resources. Min Wang: Investigation, Formal analysis, Methodology.

Funding

This work was supported by the National Natural Science Foundation of China (Grant Nos. 52005427), the Jiangsu Industry University Cooperation Project (Grant Nos. BY20221007), the Qinglan Project Funding for Universities in Jiangsu Province of China (Grant Nos. 2022), the Postgraduate Research & Practice Innovation Program of Jiangsu Province (Grant Nos. SJCX23_1862), the Postgraduate Research & Practice Innovation Program of Yancheng Institute of Technology (Grant Nos. SJCX23_XY049 and SJCX23_XZ021).

Data availability

Data will be made available on request.

Declarations

Conflict of Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

1. Zhou, B; Zhao, Z. A hybrid fuzzy-neural-based dynamic scheduling method for part feeding of mixed-model assembly lines. Comput Ind Eng; 2022; 163, [DOI: https://dx.doi.org/10.1016/j.cie.2021.107794] 107794.

2. Liu, W; Zhu, X; Wang, L; Wang, S. Multiple equipment scheduling and AGV trajectory generation in U-shaped sea-rail intermodal automated container terminal. Measurement; 2023; 206, [DOI: https://dx.doi.org/10.1016/j.measurement.2022.112262] 112262.

3. Lu, J; Ren, C; Shao, Y; Zhu, J; Lu, X. An automated guided vehicle conflict-free scheduling approach considering assignment rules in a robotic mobile fulfillment system. Comput Ind Eng; 2023; 176, [DOI: https://dx.doi.org/10.1016/j.cie.2022.108932] 108932.

4. Xiao, H; Wu, X; Zeng, Y; Zhai, J. A cega-based optimization approach for integrated designing of a unidirectional guide-path network and scheduling of agvs. Math Probl Eng; 2020; 2020, [DOI: https://dx.doi.org/10.1155/2020/3961409] 3961409.

5. Hellmann, W; Marino, D; Megahed, M; Suggs, M; Borowski, J; Negahban, A. Human, AGV or AIV? An integrated framework for material handling system selection with real-world application in an injection molding facility. Int J Adv Manuf Technol; 2019; 101, 1–4 pp. 815-824. [DOI: https://dx.doi.org/10.1007/s00170-018-2958-x]

6. Li, C; Zhang, L; Zhang, L. A route and speed optimization model to find conflict-free routes for automated guided vehicles in large warehouses based on quick response code technology. Adv Eng Inform; 2022; 52, [DOI: https://dx.doi.org/10.1016/j.aei.2022.101604] 101604.

7. Xiao, H; Wu, X; Qin, D; Zhai, J. A collision and deadlock prevention method with traffic sequence optimization strategy for ugn-based agvs. IEEE Access; 2020; 8, pp. 209452-209470. [DOI: https://dx.doi.org/10.1109/access.2020.3039515]

8. Kumbhar, SG; Thombare, RB; Salunkhe, AB. Automated guided vehicles for small manufacturing enterprises: a review. SAE Int J Mater Manuf; 2018; 11, 3 pp. 253-258. [DOI: https://dx.doi.org/10.4271/05-11-03-0024]

9. Chawla, VK; Chanda, AK; Angra, S. Multi-load agvs scheduling by application of modified memetic particle swarm optimization algorithm. J Braz Soc Mech Sci Eng; 2018; 40, 9 436. [DOI: https://dx.doi.org/10.1007/s40430-018-1357-4]

10. Du, L; Ke, S; Wang, Z; Tao, J; Yu, L; Li, H. Research on multi-load AGV path planning of weaving workshop based on time priority. Math Biosci Eng; 2019; 16, 4 pp. 2277-2292.4030686 [DOI: https://dx.doi.org/10.3934/mbe.2019113]

11. Yan, R; Jackson, L; Dunnett, S. A study for further exploring the advantages of using multi-load automated guided vehicles. J Manuf Syst; 2020; 57, pp. 19-30. [DOI: https://dx.doi.org/10.1016/j.jmsy.2020.08.005]

12. Ma, X; Bian, Y; Gao, F. An improved shuffled frog leaping algorithm for multiload agv dispatching in automated container terminals. Math Probl Eng; 2020; 2020, 4062207 [DOI: https://dx.doi.org/10.1155/2020/1260196] 1544.90110 1260196.

13. Rahimikelarijani, B; Fazlollahtabar, H; Nayeri, S. Multi-objective multi-load tandem autonomous guided vehicle for robust workload balance and material handling optimization. SN Appl Sci; 2020; 2, 7 1200. [DOI: https://dx.doi.org/10.1007/s42452-020-3002-y]

14. Rahimikelarijani, B; Saidi-Mehrabad, M; Barzinpour, F. A mathematical model for multiple-load agvs in tandem layout. J Optim Ind Eng; 2020; 13, 1 pp. 67-80. [DOI: https://dx.doi.org/10.22094/JOIE.2018.537.37]

15. Chol, J; Gun, CR. Multi-agent based scheduling method for tandem automated guided vehicle systems. Eng Appl Artif Intell; 2023; 123, [DOI: https://dx.doi.org/10.1016/j.engappai.2023.106229] 106229.

16. Dang, Q; Singh, N; Adan, I; Martagan, T; van de Sande, D. Scheduling heterogeneous multi-load agvs with battery constraints. Comput Oper Res; 2021; 136, 4304205 [DOI: https://dx.doi.org/10.1016/j.cor.2021.105517] 1511.90031 105517.

17. Wang, Z; Wu, Y. An ant colony optimization-simulated annealing algorithm for solving a multiload AGVs workshop scheduling problem with limited buffer capacity. Processes; 2023; 11, 3 861. [DOI: https://dx.doi.org/10.3390/pr11030861]

18. Yan, R; Dunnett, SJ; Jackson, LM. Model-based research for aiding decision-making during the design and operation of multi-load automated guided vehicle systems. Reliab Eng Syst Saf; 2022; [DOI: https://dx.doi.org/10.1016/j.ress.2021.108264]

19. Li G, Li X, Gao L, H C (2019) Tasks assigning and sequencing of multiple agvs based on an improved harmony search algorithm. 10(11): 4533–4546. https://doi.org/10.1007/s12652-018-1137-0

20. Ho, Y; Liu, H. The performance of load-selection rules and pickup-dispatching rules for multiple-load agvs. J Manuf Syst; 2009; 28, 1 pp. 1-10. [DOI: https://dx.doi.org/10.1016/j.jmsy.2009.06.001]

21. Ho, Y; Liu, H; Yih, Y. A multiple-attribute method for concurrently solving the pickup-dispatching problem and the load-selection problem of multiple-load agvs. J Manuf Syst; 2012; 31, 3 pp. 288-300. [DOI: https://dx.doi.org/10.1016/j.jmsy.2012.03.002]

22. Chawla, VK; Chanda, AK; Angra, S. Simultaneous dispatching and scheduling of multi-load agvs in fms-a simulation study. Mater Today Proc; 2018; 5, 11 pp. 25358-25367. [DOI: https://dx.doi.org/10.1016/j.matpr.2018.10.339]

23. Angra, S; Chanda, A; Chawla, VJ. Comparison and evaluation of job selection dispatching rules for integrated scheduling of multi-load automatic guided vehicles serving in variable sized flexible manufacturing system layouts: a simulation study. Glob Sci; 2018; 8, 4 pp. 187-200. [DOI: https://dx.doi.org/10.5267/j.msl.2018.3.002]

24. Ramanaiah, DV; Ashok, B. Performance of multi-load agv systems under different guide path configurations. Int J Technol Eng Sci; 2013; 1, pp. 22-31.

25. Azimi, P; Alidoost, M. A heuristic approach for optimizing a multiple-load automated guided vehicle system in an integrated flexible manufacturing system. Econ Comput Econ Cybern Stud Res; 2011; 45, 2 pp. 169-187.

26. Azimi, P; Haleh, H; Alidoost, MJ. The selection of the best control rule for a multiple-load agv system using simulation and fuzzy madm in a flexible manufacturing system. Model Simul Eng; 2010; 2010, pp. 131-134. [DOI: https://dx.doi.org/10.1155/2010/821701]

27. Isik, M; Sahin, C; Hamidy, SM. Novel dispatching rules for multiple-load automated guided vehicles. Int J Simul Model; 2023; [DOI: https://dx.doi.org/10.2507/ijsimm22-1-632]

28. Azimi P, Ghanbari MR, Yarmohammadi S (2012) Optimization a multi-objective and multiple-load agv system using optimization via simulation approach. Int Bull Bus Adm 2012(13):97–108. https://www.researchgate.net/publication/280598116

29. Hu, Y; Yang, H; Huang, Y. Conflict-free scheduling of large-scale multi-load AGVs in material transportation network. Transp Res Part E Logist Transp Rev; 2022; 158, [DOI: https://dx.doi.org/10.1016/j.tre.2022.102623] 102623.

30. Krishnamoorthy, P; Satheesh, N; Sudha, D; Sengan, S; Alharbi, M; Pustokhin, DA; Setiawan, R. Effective scheduling of multi-load automated guided vehicle in spinning mill: a case study. IEEE Access; 2023; 11, pp. 9389-9402. [DOI: https://dx.doi.org/10.1109/access.2023.3236843]

31. Yu N, Li T, Wang B (2021) Multi-load agvs scheduling algorithm in automated sorting warehouse. In: Paper Presented at the 2021 14th International Symposium on Computational Intelligence and Design (ISCID), 126–129. https://doi.org/10.1109/ISCID52796.2021.00037

32. Zou, W; Pan, Q; Tasgetiren, MF. An effective iterated greedy algorithm for solving a multi-compartment agv scheduling problem in a matrix manufacturing workshop. Appl Soft Comput; 2021; 99, [DOI: https://dx.doi.org/10.1016/j.asoc.2020.106945] 106945.

33. Huo, X; He, X; Xiong, Z; Wu, X. Multi-objective optimization for scheduling multi-load automated guided vehicles with consideration of energy consumption. Transp Res Part C-Emerg Technol; 2024; 161, [DOI: https://dx.doi.org/10.1016/j.trc.2024.104548] 104548.

34. Lin, Y; Xu, Y; Zhu, J; Wang, X; Wang, L; Hu, G. Mlatso: a method for task scheduling optimization in multi-load agvs-based systems. Robot Comput Integr Manuf; 2023; [DOI: https://dx.doi.org/10.1016/j.rcim.2022.102397]

35. Haining, X; Xing, W; Ting, Z; Jingjing, Z. A deadlock-avoidance dispatching method for multiple-load agvs based transportation system. Trans Nanjing Univ Aeronaut Astronaut; 2021; 38, 1 pp. 181-192. [DOI: https://dx.doi.org/10.16356/j.1005-1120.2021.01.018]

36. Dong, J; Zhang, L; Xiao, T; Li, H. A dynamic delivery strategy for material handling in mixed-model assembly lines using decentralized supermarkets. Int J Model Simul Sci Comput; 2015; 6, 04 1550038. [DOI: https://dx.doi.org/10.1142/S179396231550038]

37. Chen, C; Xi, L; Zhou, B; Zhou, S. A multiple-criteria real-time scheduling approach for multiple-load carriers subject to lifo loading constraints. Int J Prod Res; 2011; 49, 16 pp. 4787-4806. [DOI: https://dx.doi.org/10.1080/00207543.2010.510486]

38. Zhou, B; Xu, J. An adaptive svm-based real-time scheduling mechanism and simulation for multiple-load carriers in automobile assembly lines. Int J Model Simul Sci Comput; 2017; 8, 04 [DOI: https://dx.doi.org/10.1142/S1793962317500489] 1750048.1750041-1750048.1750024.

39. Chen, C; Xia, B; Zhou, B; Xi, L. A reinforcement learning based approach for a multiple-load carrier scheduling problem. J Intell Manuf; 2015; 26, 6 pp. 1233-1245. [DOI: https://dx.doi.org/10.1007/s10845-013-0852-9]

40. Zhou, B; Zhao, L. A quantum-inspired archimedes optimization algorithm for hybrid-load autonomous guided vehicle scheduling problem. Appl Intell; 2023; 53, 22 pp. 27725-27778. [DOI: https://dx.doi.org/10.1007/s10489-023-04962-1]

41. Xia, B; Zhang, M; Gao, Y; Yang, J; Peng, Y. Design for optimally routing and scheduling a tow train for just-in-time material supply of mixed-model assembly lines. Sustainability; 2023; 15, 19 14567. [DOI: https://dx.doi.org/10.3390/su151914567]

42. Cheng, W; Meng, W. An efficient genetic algorithm for multi agv scheduling problem about intelligent warehouse. Robot Intell Autom; 2023; 43, 4 pp. 382-393.4669265 [DOI: https://dx.doi.org/10.1108/ria-10-2022-0258]

43. Zhang, L; Hu, Y; Guan, Y. Research on hybrid-load agv dispatching problem for mixed-model automobile assembly line. Proc CIRP; 2019; 81, pp. 1059-1064. [DOI: https://dx.doi.org/10.1016/j.procir.2019.03.251]

44. Lin, S; Liu, A; Wang, J; Kong, X. An improved fault-tolerant cultural-PSO with probability for multi-AGV path planning. Expert Syst Appl; 2024; 237, [DOI: https://dx.doi.org/10.1016/j.eswa.2023.121510] 121510.

45. Zou, W; Pan, Q; Wang, L. An effective multi-objective evolutionary algorithm for solving the agv scheduling problem with pickup and delivery. Knowl-Based Syst; 2021; 218, [DOI: https://dx.doi.org/10.1016/j.knosys.2021.106881] 106881.

46. Tang, Y; Zhou, F. An improved imperialist competition algorithm with adaptive differential mutation assimilation strategy for function optimization. Expert Syst Appl; 2023; 211, [DOI: https://dx.doi.org/10.1016/j.eswa.2022.118686] 118686.

47. Zajac, J; Malopolski, W. Structural on-line control policy for collision and deadlock resolution in multi-agv systems. J Manuf Syst; 2021; 60, pp. 80-92. [DOI: https://dx.doi.org/10.1016/j.jmsy.2021.05.002]

48. Guan, X; Dai, X. Deadlock-free multi-attribute dispatching method for agv systems. Int J Adv Manuf Technol; 2009; 45, 5–6 pp. 603-615. [DOI: https://dx.doi.org/10.1007/s00170-009-1996-9]

49. Chen, X; Xing, Z; Feng, L; Zhang, T; Wu, W; Hu, R. An etcen-based motion coordination strategy avoiding active and passive deadlocks for multi-agv system. IEEE Trans Autom Sci Eng; 2023; 20, 2 pp. 1364-1377. [DOI: https://dx.doi.org/10.1109/tase.2022.3175909]

50. Chung, CH; Jang, YJ. Deadlock prevention and multi agent path finding algorithm considering physical constraint for a massive fleet AGV system. Appl Soft Comput; 2024; 161, [DOI: https://dx.doi.org/10.1016/j.asoc.2024.111725] 111725.

51. Pratissoli, F; Brugioni, R; Battilani, N; Sabattini, L. Hierarchical traffic management of multi-agv systems with deadlock prevention applied to industrial environments. IEEE Trans Autom Sci Eng; 2023; [DOI: https://dx.doi.org/10.1109/tase.2023.3276233]

52. Wu, W; Xing, Z; Yue, H; Su, H; Pang, S. Petri-net-based deadlock detection and recovery for control of interacting equipment in automated container terminals. IET Intell Transp Syst; 2022; 16, 6 pp. 739-753. [DOI: https://dx.doi.org/10.1049/itr2.12168]

53. Yu, Y; Gong, H; Liu, H; Mou, X. Knowledge representation and reasoning using fuzzy petri nets: a literature review and bibliometric analysis. Artif Intell Rev; 2023; 56, 7 pp. 6241-6265. [DOI: https://dx.doi.org/10.1007/s10462-022-10312-3]

54. Park, J; Kim, J. Multi-agv scheduling under limited buffer capacity and battery charging using simulation techniques. Appl Sci; 2024; 14, 3 [DOI: https://dx.doi.org/10.3390/app14031197] 1197.

55. Murakami, K. Time-space network model and MILP formulation of the conflict-free routing problem of a capacitated AGV system. Comput Ind Eng; 2020; 141, [DOI: https://dx.doi.org/10.1016/j.cie.2020.106270] 106270.

56. Atashpaz-Gargari E, Lucas C (2007) Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition. In: Paper Presented at the 2007 IEEE Congress on evolutionary computation, pp 4661–4667. https://doi.org/10.1109/CEC.2007.4425083

57. Li, Y; Yang, Z; Wang, L; Tang, H; Sun, L; Guo, S. A hybrid imperialist competitive algorithm for energy-efficient flexible job shop scheduling problem with variable-size sublots. Comput Ind Eng; 2022; 172, [DOI: https://dx.doi.org/10.1016/j.cie.2022.108641] 108641.

58. Kaveh, A; Rahmani, P; Eslamlou, AD. An efficient hybrid approach based on harris hawks optimization and imperialist competitive algorithm for structural optimization. Eng Comput; 2022; 38, Suppl 2 pp. 1555-1583. [DOI: https://dx.doi.org/10.1007/s00366-020-01258-7]

59. Tao, X; Li, J; Huang, T; Duan, P. Discrete imperialist competitive algorithm for the resource-constrained hybrid flowshop problem with energy consumption. Complex Intell Syst; 2021; 7, 1 pp. 311-326. [DOI: https://dx.doi.org/10.1007/s40747-020-00193-w]

60. Gao, Y; Chang, D; Chen, C; Sha, M. A digital twin-based decision support approach for agv scheduling. Eng Appl Artif Intell; 2024; 130, [DOI: https://dx.doi.org/10.1016/j.engappai.2023.107687] 107687.

61. Kouka, N; BenSaid, F; Fdhila, R; Fourati, R; Hussain, A; Alimi, AM. A novel approach of many-objective particle swarm optimization with cooperative agents based on an inverted generational distance indicator. Inf Sci; 2023; 623, pp. 220-241. [DOI: https://dx.doi.org/10.1016/j.ins.2022.12.021]

62. Zhang, Y; Hu, X; Wu, C. Improved imperialist competitive algorithms for rebalancing multi-objective two-sided assembly lines with space and resource constraints. Int J Prod Res; 2020; 58, 12 pp. 3589-3617. [DOI: https://dx.doi.org/10.1080/00207543.2019.1633023]

63. Zitzler, E; Thiele, L; Laumanns, M; Fonseca, CM. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput; 2003; 7, 2 pp. 117-132. [DOI: https://dx.doi.org/10.1109/tevc.2003.810758]

64. Guerreiro, AP; Fonseca, CM; Paquete, L. The hypervolume indicator: Computational problems and algorithms. ACM Comput Surv; 2021; 54, 6 pp. 1-42. [DOI: https://dx.doi.org/10.48550/arXiv.2005.00515]

65. Shang, K; Ishibuchi, H; He, L; Pang, LM. A survey on the hypervolume indicator in evolutionary multiobjective optimization. IEEE Trans Evol Comput; 2020; 25, 1 pp. 1-20. [DOI: https://dx.doi.org/10.1109/tevc.2020.3013290]

66. Liang, J; Wang, P; Guo, L; Qu, B; Yue, C; Yu, K; Wang, Y. Multi-objective flow shop scheduling with limited buffers using hybrid self-adaptive differential evolution. Memet Comput; 2019; 11, 4 pp. 407-422. [DOI: https://dx.doi.org/10.1007/s12293-019-00290-5]

67. Song, X; Wu, C; Song, S; Stojanovic, V; Tejado, I. Fuzzy wavelet neural adaptive finite-time self-triggered fault-tolerant control for a quadrotor unmanned aerial vehicle with scheduled performance. Eng Appl Artif Intell; 2024; 131, [DOI: https://dx.doi.org/10.1016/j.engappai.2023.107832] 107832.

68. Du, Z; Xie, X; Qu, Z; Hu, Y; Stojanovic, V. Dynamic event-triggered consensus control for interval type-2 fuzzy multi-agent systems. IEEE Trans Circuits Syst I Regul Pap; 2024; 71, 8 pp. 3857-3866. [DOI: https://dx.doi.org/10.1109/TCSI.2024.3385671]

69. Kim, H; Park, C; Govindan, V; Vasudevan, S; Kumar, G. Systematic Reliability Optimization (ASRO). Babylon J Math; 2023; 2023, pp. 50-53. [DOI: https://dx.doi.org/10.58496/bjm/2023/010]

70. Hussein, N; Khalaf, S; Shah, K. Advanced composite materials for sustainable construction: innovations in civil engineering applications. KHWARIZMIA; 2024; 2024, [DOI: https://dx.doi.org/10.70470/KHWARIZMIA/2024/003] 8–16.

71. Sutikno, T. Fuzzy optimization and metaheuristic algorithms. Babylon J Math; 2023; 2023, pp. 59-65. [DOI: https://dx.doi.org/10.58496/BJM/2023/012]

72. Al-Ibraheemi, F; Tally, M; Nadweh, S; Al Sayed, I; Tawfeq, J; Gheni, H; Shah, P; Sekhar, R. A cognitive energy-driven routing strategy for ultra-efficient data transfer in wireless sensor networks. Appl Data Sci Anal; 2025; 2025, pp. 131-143. [DOI: https://dx.doi.org/10.58496/ADSA/2025/011]