Abstract

Translate

This study addresses the joint scheduling problem of flexible job shop scheduling and automated guided vehicles with the objective of minimizing the makespan. We propose an efficient optimization approach based on a critical-path-driven variable neighborhood descent. The core contribution lies in the development of a critical path detection mechanism that incorporates transportation processes, along with the design of tailored neighborhood structures. Building on this foundation, a problem-specific variable neighborhood descent search strategy is implemented. Unlike traditional variable neighborhood descent approaches, the proposed critical path analysis accurately identifies bottleneck operations in both processing and transportation stages. The designed neighborhood structures effectively coordinate machine scheduling and automated guided vehicles transportation, enabling synergistic optimization. To enhance overall performance, auxiliary strategies such as an external memory archive and population diversity maintenance are integrated. Experimental results on multiple benchmark datasets demonstrate that the proposed method achieves significant improvements in solution quality compared to existing algorithms. Ablation experiments further confirm the critical role of the critical-path-driven variable neighborhood descent mechanism in enhancing algorithmic performance.

Full text

Turn on search term navigation

Translate

1. Introduction

Driven by diversified and personalized customer demands, the manufacturing industry is undergoing a transformation towards multi-variety, small-batch, and intelligent production modes. The Flexible Job Shop Scheduling Problem (FJSP), which accounts for the flexibility in machine selection for operations, represents a prevalent and critical scheduling challenge in modern manufacturing [1].

Current research largely addresses production scheduling and logistics scheduling as separate domains. Production scheduling primarily focuses on the sequencing of operations and allocation of machines, typically either incorporating transportation time into processing time or assuming unlimited transportation resources. In contrast, logistics scheduling emphasizes route planning and the allocation of transportation resources. The key to achieving workshop automation and intelligence lies in the coordinated operation of production and transportation equipment. Automated Guided Vehicles (AGVs), characterized by their energy efficiency, automation, and high flexibility, serve as crucial tools for material handling in smart workshops [2]. The classical FJSP does not consider the transportation of workpieces between the load/unload area and machines, or between different machines. However, in practical workshop environments, AGV transportation constitutes a non-negligible portion of time and is subject to constraints such as limited guide paths. Neglecting AGV transportation would directly and adversely impact material distribution, production processing efficiency, and on-time delivery capability across the entire manufacturing process. Therefore, integrated scheduling of FJSP and AGVs not only better aligns with real-world production conditions and market requirements but also holds significant theoretical value.

The job shop scheduling problem represents a long-standing challenge in the field of combinatorial optimization and continues to attract sustained research interest. Extensive efforts have been devoted to developing a variety of solution methodologies, which can be broadly categorized into exact methods, heuristic rules, and metaheuristic algorithms. For instance, Liu et al. [3] investigated a dynamic flexible job shop scheduling problem with transportation resources and proposed a multi-objective adaptive large neighborhood search algorithm. In a similar vein, Ren et al. [4] studied a dynamic flexible job shop scheduling problem subject to transportation resource and time constraints; they developed a dynamic decision-making flowchart for the scheduling system and introduced a particle swarm optimization algorithm enhanced with genetic operators. On the methodological front, Fuladi et al. [5] integrated genetic algorithms, simulated annealing, and variable neighborhood search to construct an efficient hybrid metaheuristic framework, while Fatemi-Anaraki et al. [6] systematically compared the performance of mixed-integer linear programming and constraint programming in complex scheduling environments. These high-performance algorithms, which represent significant advances in general scheduling research, provide a solid methodological foundation for addressing more complex integrated scheduling problems.

Under this backdrop, research focusing on shop scheduling with integrated material transportation has continued to evolve. Early studies on integrated shop floor and AGV scheduling were primarily conducted within rigid job shop settings where machine flexibility was not considered. During this phase, scholars focused on establishing effective mathematical models and solution frameworks for this complex problem. For instance, Bilge et al. [7] established a nonlinear mixed-integer programming model and developed an iterative procedure to solve it; Lacomme et al. [8] proposed a new framework based on disjunctive graphs to model the job shop scheduling-AGV(JSP-AGV) problem and adopted a memetic algorithm for solution; Yao et al. [9] designed a new mixed-integer linear programming model based on the idea of sequence modeling, which achieved better solutions than other models.Such research has laid a foundation for the JSP-AGVs problem, yet its core limitation lies in the failure to consider machine flexibility, leading to a gap between the research and the flexibility requirements in real-world manufacturing environments.

With the advancement of research, the joint scheduling problem of flexible job shops and AGVs, which can more accurately describe actual production systems, has become the mainstream. The core challenge of this problem lies in the need to make collaborative decisions on operation sequencing, machine selection, and AGVs allocation simultaneously and its complexity increases sharply as the scale expands. For example, Ham [10] proposed two different planning models to solve the flexible job shop scheduling-AGV (FJSP-AGV). Lim et al. [11] presented a two-stage iterative heuristic based on mathematical programming, along with a decomposition scheme centered on machine allocation, to optimize the makespan. Yao et al. [12] decomposed the flexible job shop scheduling problem with limited AGVs into four sub-problems and proposed a mixed-integer linear programming model.

To address large-scale complex problems, the research focus has swiftly shifted to various metaheuristic algorithms. In metaheuristic-based solution frameworks, the design of encoding strategies plays a crucial role, thereby leading to distinct methodological approaches: Homayoni et al. [13] encoded only the operation sequence, designed greedy heuristic rules for machine and AGVs allocation, and proposed a multi-start biased random-key genetic algorithm for solution; Hu Xiaoyang et al. [14] adopted a two-layer encoding for the operation and machine parts, put forward a “first-come, first-served” heuristic rule for AGVs allocation, and designed an improved iterative local search algorithm for solving the problem; Homayouni et al. [15] used three-layer encoding for operation sequencing, machine selection, and AGVs allocation, and combined it with a late acceptance hill-climbing method to achieve the solution.

To solve the FJSP-AGV problem, researchers have proposed various strategies.Liu Erhui et al. [16] proposed a mutation operator based on principal component analysis and introduced operations such as the crossover operator to improve the flower pollination algorithm, aiming to solve the joint scheduling problem of job shops and AGVs; Chaudhry et al. [17] optimized the allocation of machine and AGVs resources using Excel and Evolver based on genetic algorithms; Chen Kui et al. [18] proposed a hybrid discrete particle swarm optimization algorithm integrating competitive learning and random restart mechanisms for solution; Li et al. [19] proposed a multi-strategy-driven genetic algorithm (GA), and designed three targeted strategies for the sub-problems of operation sequencing and machine assignment; Berterottière et al. [20] extended the classical disjunctive graph model and proposed a move evaluation process that runs in constant time, which was then applied within a tabu search framework to improve the optimization efficiency of the algorithm; Yao et al. [21] specifically designed a new neighborhood structure for the unique characteristics of the job shop scheduling problem integrated with limited transportation resources, and combined this new neighborhood structure with tabu search.

Despite the abundant research achievements, there is still potential for further improvement. Firstly, many studies based on GA have insufficient attention to key mechanisms such as population initialization and diversity maintenance, which impairs the global exploration capability. Secondly, in the local search phase, many designed neighborhood structures are relatively general and lack the use of structural information inherent in scheduling problems to guide in-depth and efficient optimization, resulting in limited local exploitation capability.In summary, targeting the FJSP-AGV problem, this paper proposes an improved genetic algorithm integrated with variable neighborhood descent (IVNDGA). The main contributions of this paper are as follows:

(1). A comprehensive model capturing the coupling relationships among operation sequencing, machine selection, and AGV transportation was developed. This model fully characterizes both the machine processing stages and the AGV activities, including loaded and unloaded transportation.

(2). Incorporating a backward-tracking concept, a critical path identification method was proposed to accurately pinpoint mixed bottleneck operations involving both transportation and processing that directly impact the makespan. Corresponding neighborhood structures were generated by adjusting operations on this critical path, which significantly reduced ineffective search efforts.

(3). The algorithm was further enhanced by integrating the Variable Neighborhood Descent with auxiliary strategies, namely an external memory archive and population diversity maintenance. Experimental results on datasets of various scales demonstrate that the proposed algorithm is both feasible and effective for solving the integrated FJSP and AGV scheduling problem.

The rest of the paper is structured as follows: Section 2 formulates the integrated scheduling problem of FJSP and AGVs and develops the corresponding mathematical model. Section 3 presents the encoding and decoding mechanisms along with the improved genetic algorithm. Section 4 introduces the proposed critical path identification method that incorporates transport processes and the adaptive variable neighborhood descent (VND) algorithm. Experimental results based on multiple benchmark instances are provided and discussed in Section 5. Finally, Section 6 concludes the paper and outlines potential directions for future research.

2. Problem Description and Mathematical Model

2.1. Model Parameters

We developed a mathematical model to describe FJSP-AGV using the notation of Table 1.

2.2. Problem Description

There are n independent jobs to be processed on m multifunctional machines $M = {M_{1}, M_{2}, \dots, M_{m}}$ , and the intermediate transportation process needs to be carried out by v AGVs (Automated Guided Vehicles) of the same type $V = {V_{1}, V_{2}, \dots, V_{v}}$ . Among them, job $J_{i} \in J$ consists of $n_{i}$ operations $O_{i} = {O_{i 1}, O_{i 2}, \dots, O_{i n_{i}}}$ . For operation $O_{i j}$ , it can be processed by one machine from the optional machine set $M_{i j}$ , and the corresponding processing time is generally different when different machines are selected.

For the same job, if two consecutive adjacent operations are assigned to different machines, one available AGV must be selected to complete the transportation tasks between machines and between machines and loading/unloading areas. The transportation process specifically includes: the empty transportation where the AGV moves from its current position to the target position to pick up the job, and the loaded transportation where the AGV delivers the job to the selected processing machine after picking it up.

The number of AGVs, the transportation time between machines and between machines and loading/unloading areas are known, and the optional machine set for each operation and the corresponding processing time are also known. The scheduling objective is as follows: select an appropriate processing machine for each operation, determine the processing sequence on each machine, and assign the transportation operations between machines to an available AGV, so as to minimize the makespan.

Problem Assumptions

(1). Initial state constraint: All machines and AGVs are available at time 0, and all jobs can start processing at time 0.

(2). Machine occupancy constraint: Each machine can process at most one operation at any given time.

(3). AGV occupancy constraint: Each AGV can transport at most one operation at any given time.

(4). Operation processing constraints: Different operations of the same job are processed in a given sequence, while operations of different jobs are independent.

(5). Sufficient space is available at each machine to allow jobs to wait for the machine or for AGV.

(6). Traffic congestion is not considered; all AGVs move at the same speed regardless of whether they are loaded or empty.

(7). Machine failure, AGV failure and AGV power consumption are not considered.

2.3. Mathematical Model

Objective function: Minimize the makespan

(1) $min C_{max}$

Constraints:

(2) $E T_{i j w}^{s} \geq S_{i (j - 1) h}$

(3) $E T_{i j w}^{s} \geq L T_{i j w}^{c} - (1 - Y A_{i j p q w}) \times L$

(4) $E T_{i j w}^{c} = E T_{i j w}^{s} + T_{l_{w}}^{h}$

(5) $L T_{i j w}^{s} \geq E T_{i j w}^{c}$

(6) $L T_{i j w}^{s} \geq C_{i (j - 1) h}$

(7) $L T_{i j w}^{c} = L T_{i j w}^{s} + T_{h}^{k}$

(8) $S_{i j k} \geq S_{i (j - 1) h} + P_{i (j - 1) h}$

(9) $S_{p q k} \geq S_{i j k} + P_{i j k} - (1 - Y M_{i j p q k}) \times L$

(10) $S_{i j k} \geq E T_{i j w}^{c}$

(11) $C_{i j k} = S_{i j k} + P_{i j k}$

(12) $\sum_{k = 1}^{M_{i j}} \sum_{w = 1}^{v} X_{i j k w} = 1$

Equation (2) indicates that the start time of empty transportation must be greater than or equal to the processing start time of the previous operation; Equation (3) indicates that the start time of empty transportation must be greater than or equal to the end time of the last transportation task of the selected AGV; Equation (4) indicates that the completion time of empty transportation is equal to the start time of empty transportation plus the pickup time from the current workstation to the target workstation; Equation (5) indicates that the start time of loaded transportation must be greater than or equal to the completion time of empty transportation; Equation (6) indicates that the start time of loaded transportation must be greater than or equal to the completion time of the previous operation; Equation (7) indicates that the completion time of loaded transportation is equal to the start time of loaded transportation plus the transportation time from picking up the workpiece at the predecessor machine to delivering it to the target workstation; Equation (8) indicates that for the same job, the processing of a subsequent operation can only start after the completion of the previous operation; Equation (9) indicates that there is a sequential processing order on the same machine; Equation (10) indicates that the processing start time of an operation must be greater than or equal to the completion time of loaded transportation; Equation (11) indicates that the processing completion time of an operation is equal to its processing start time plus the processing time on the selected machine; Equation (12) indicates that each operation can only be transported by one AGV and processed on one machine.

3. Improved Genetic Algorithm

3.1. Encoding and Decoding

Since the integrated scheduling problem of FJSP and AGV involves three sub-problems, namely operation sequencing, machine selection, and AGV allocation, this paper adopts a two-layer encoding structure consisting of an operation sequence (OS) layer and a machine selection (MS) layer. For the AGV allocation problem, a heuristic rule that minimizes the idle waiting time of AGVs is applied during decoding for allocation.

If the operation is the first process of a job, select the AGV that arrives earliest at the material station:

$w = arg min_{w \in V} {t_{w} + T_{l_{w}}^{M_{0}}}$

Otherwise, select the AGV with the minimum relative idle time for transportation:

$w = arg min_{w \in V} {| t_{w} + T_{l_{w}}^{m_{i (j - 1)}} - C_{i (j - 1)} |}$

This decision reflects a core efficiency trade-off. On one hand, adopting a three-layer encoding scheme for AGV assignment would significantly expand the solution space and raise computational complexity, making it difficult to ensure algorithm feasibility and convergence speed. On the other hand, although this heuristic rule only performs local optimization and may not guarantee globally optimal AGV workload distribution, its objective aligns closely with the primary optimization goal. It directly contributes to reducing total makespan by minimizing transportation wait times.

For the integrated scheduling instance where 3 jobs are transported by 2 AGVs and processed on 2 machines, the corresponding processing times and transportation times are shown in Table 2 and Table 3, respectively.

Figure 1 shows a feasible encoding scheme for this instance.

Based on the two-layer encoding shown in Figure 1, the obtained processing sequence is $[O_{21}, O_{31}, O_{11}, O_{32}, O_{12}, O_{22}]$ , with the corresponding selected machines as $[2, 1, 1, 1, 2, 1]$ . For $O_{21}$ , initially both AGVs are available, and one AGV, for example A1, can be randomly selected. A1 directly transports the load from the material station to $M_{1}$ , followed by the machining process. While $O_{21}$ is being transported, A2 remains available at the material station and can directly perform load transportation for $O_{31}$ , which is then processed on $M_{2}$ . For $O_{11}$ , according to the defined allocation rule, the AGV that arrives at the material station earliest is selected. The arrival times of A1 and A2 at $M_{0}$ are ${1.5, 3}$ respectively, so A1 is chosen for transportation. $O_{11}$ requires A1 to first return empty to $M_{0}$ and then transport the load to $M_{1}$ . However, since $O_{31}$ is currently being processed on $M_{1}$ , $O_{11}$ must wait for $O_{31}$ to complete before it can be processed. As both $O_{31}$ and $O_{32}$ are on $M_{1}$ , no transportation is needed; they simply wait for $O_{11}$ to finish before beginning their processing. before it can proceed with processing. For transporting $O_{12}$ , the relative idle times of A1 and A2 are calculated as ${1.5, 3}$ respectively, so A1 is selected. Similarly, when transporting $O_{22}$ , the relative idle times are ${2.5, 1.5}$ respectively, so A2 is chosen to transport $O_{22}$ .

Finally, the decoded scheduling diagram shown in Figure 2 is obtained. The color coding in the figure is explained as follows: red, green, and blue indicate the processing times of Jobs $J_{1}$ , $J_{2}$ , and $J_{3}$ , respectively. White and gray blocks represent the AGV’s unloaded and loaded travel times.

The detailed decoding procedure is outlined in Algorithm 1.

Algorithm 1 Decoding
Input: OS, MS, per-job operation counts $n_{i}$ , total operations N, processing-time table, transportation-time table.
Output: Start/end times of each transportation and processing, and the makespan.
Initially, all jobs and all AGVs are in the warehouse; all machines and AGVs are available.
1:	for $k = 1$ to N do
2:	set $O_{i j} = OS (k)$ ; $m_{i j} = MS (n_{i - 1} + j)$	% decode the k-th operation
3:	if $j = 1$ then	% first operation of the job
4:	$w = arg {min}_{w \in V} {t_{w} + T_{l_{w}}^{M_{0}}}$	% AGV arriving LU earliest
5:	if $l_{w} = M_{0}$ then	% AGV already in LU area
6:	$L T_{i 1 w}^{s} = t_{w}$ , $L T_{i 1 w}^{c} = L T_{i 1 w}^{s} + T_{M_{0}}^{m_{i 1}}$ ; $t_{w} = L T_{i 1 w}^{c}$ ; $l_{w} = m_{i 1}$	% loaded transportation
7:	$S_{i 1} = max (t_{w}, C_{m_{i 1} - 1})$ ; $C_{i 1} = S_{i 1} + P_{i 1 m_{i 1}}$	% processing
8:	else	% AGV not in LU area
9:	$E T_{i 1 w}^{s} = t_{w}$ , $E T_{i 1 w}^{c} = E T_{i 1 w}^{s} + T_{l_{w}}^{M_{0}}$ ; $t_{w} = E T_{i 1 w}^{c}$ ; $l_{w} = M_{0}$	% empty transportation
10:	$L T_{i 1 w}^{s} = t_{w}$ , $L T_{i 1 w}^{c} = L T_{i 1 w}^{s} + T_{M_{0}}^{m_{i 1}}$ ; $t_{w} = L T_{i 1 w}^{c}$ ; $l_{w} = m_{i 1}$	% loaded transportation
11:	$S_{i 1} = max (t_{w}, C_{m_{i 1} - 1})$ ; $C_{i 1} = S_{i 1} + P_{i 1 m_{i 1}}$	% processing
12:	end if
13:	else	% non-first operation
14:	$w = arg {min}_{w \in V} \|t_{w} + T_{l_{w}}^{m_{i (j - 1)}} - C_{i (j - 1)}\|$	% reduce idle waiting
15:	if $m_{i (j - 1)} = m_{i j}$ then	% same machine
16:	$S_{i j} = max (C_{i (j - 1)}, C_{m_{i j} - 1})$ ; $C_{i j} = S_{i j} + P_{i j m_{i j}}$	% processing
17:	else	% different machines
18:	if $l_{w} = m_{i (j - 1)}$ then	% AGV at predecessor
19:	$L T_{i j w}^{s} = max (t_{w}, C_{i (j - 1)})$ , $L T_{i j w}^{c} = L T_{i j w}^{s} + T_{m_{i (j - 1)}}^{m_{i j}}$ ; $t_{w} = L T_{i j w}^{c}$ ; $l_{w} = m_{i j}$	% loaded transportation
20:	$S_{i j} = max (t_{w}, C_{m_{i j} - 1})$ ; $C_{i j} = S_{i j} + P_{i j m_{i j}}$	% processing
21:	else	% AGV not at predecessor
22:	$E T_{i j w}^{s} = max (t_{w}, C_{m_{i j} - 1})$ , $E T_{i j w}^{c} = E T_{i j w}^{s} + T_{l_{w}}^{m_{i (j - 1)}}$ ; $t_{w} = E T_{i j w}^{c}$ ; $l_{w} = m_{i (j - 1)}$	% empty transportation
23:	$L T_{i j w}^{s} = max (t_{w}, C_{i (j - 1)})$ , $L T_{i j w}^{c} = L T_{i j w}^{s} + T_{m_{i (j - 1)}}^{m_{i j}}$ ; $t_{w} = L T_{i j w}^{c}$ ; $l_{w} = m_{i j}$	% loaded transportation
24:	$S_{i j} = max (t_{w}, C_{m_{i j} - 1})$ ; $C_{i j} = S_{i j} + P_{i j m_{i j}}$	% processing
25:	end if
26:	end if
27:	end if
28:	end for

3.2. Population Initialization

The quality of initial solutions in the population significantly influences both the optimization capability and computational efficiency of evolutionary algorithms. Therefore, considering both the quality and diversity of initial solutions, this paper adopts multiple rules to generate the initial population.

OS section is initialized using a random generation approach.

MS, three distinct rules are designed considering machine workload, transportation time, and diversity aspects. The rules are allocated in proportions of 20%, 20%, and 60%, respectively:

Rule 1: Records the current workload of each available machine and assigns the current operation to the machine that can complete processing at the earliest time.

Rule 2: If the current operation is the first operation of a job, randomly selects an available machine. Otherwise, selects the machine that minimizes the additional transportation time.

Rule 3: Randomly selects a machine from the available machine set for processing the current operation.

3.3. Selection Operations

This paper employs two selection strategies:

Elite Preservation: The two best individuals in the current population are directly preserved for the next generation.

Binary Tournament: Two individuals are randomly selected from the parent population, and the one with better fitness value is chosen as offspring. To maintain constant population size, binary tournament selection is repeated until the selected individuals reach the required population size.

3.4. Hybrid Crossover Operation

When the crossover probability condition is met, a random probability value p within the range [0, 1] is generated. The specific crossover method is then determined by comparing a random number p with a predefined variable $P_{v}$ , which is defined as follows:

(13) $P_{v} = \frac{G e n - 1}{M a x G e n - 1}$

When $p > P_{v}$ , crossover is performed between offspring individuals and individuals in the external memory archive. For the OS part, path relinking [22] is adopted, and for the MS part, two-point crossover is used. The specific process of two-point crossover is as follows: randomly select two different positions, and then swap all elements between these two positions of the two parents. When $p \leq P_{v}$ , crossover is performed between offspring individuals. For the OS part, IPOX crossover [23] is adopted, and for the MS part, uniform crossover [23] is used.

3.5. Hybrid Mutation Operation

For the OS part, two mutation methods are adopted. OS Mutation 1: Randomly select two different positions from the OS and swap the elements at these two positions. OS Mutation 2: Randomly select two different positions $K 1$ and $K 2$ in the OS; if $K 1 > K 2$ , insert $K 1$ before $K 2$ ; if $K 1 < K 2$ , insert $K 2$ before $K 1$ . For the MS part, two mutation methods are also adopted. MS Mutation 1: Randomly select two positions with multiple optional machines and replace their currently selected machines. MS Mutation 2: Randomly select one position and replace the machine at this position with the machine with the shortest processing time.

3.6. External Memory Archive Strategy

To address the uniformity of parent sources and ensure the timely inheritance of genes from superior individuals in the population, this paper introduces an external memory archive strategy. This strategy selectively retains high-quality individuals from each iteration to participate in crossover operations in subsequent iterations.

The individuals with the optimal and worst fitness values in the memory archive are denoted as $Y_{best}$ and $Y_{worst}$ , respectively. The individual with the highest fitness in the population after the current iteration is defined as $X_{best}$ , and the suboptimal solution is denoted as $\tilde{X}$ .

To ensure a uniform distribution of excellent individuals in the external memory archive, this paper proposes a method to judge the similarity between two individuals by combining the concept of Hamming Distance [24]:

(14) $H D (X_{1}, X_{2}) = \frac{\sum_{i = 1}^{N} (|X_{1} [M S (i)] - X_{2} [M S (i)]|)}{N}$

where

|X_{1} [M S (i)] - X_{2} [M S (i)]| = 0

if the elements at the i-th position in the MS segments of

X_{1}

and

X_{2}

are identical; otherwise, it equals 1.

The detailed update process of the external memory archive is presented in Algorithm 2, where $\mod (a, b)$ denotes the remainder of a divided by b.

Algorithm 2 External memory archive Strategy
Input: Current external ${Y_{h}}_{h = 1}^{H}$ , iteration number $Gen$ , current iteration’s best individual $X_{best}$ , suboptimal individual $X^{\sim}$ .
Output: Updated external memory archive.
1: . Directly store the top H individuals with the best fitness in the population into the external memory archive. 2: . if $fit (X_{best}) \leq fit (Y_{best})$ and $H D (X_{best}, Y_{best}) \neq 0$ then 3: . $Y_{worst} \leftarrow X_{best}$ ; $fit (Y_{worst}) \leftarrow fit (X_{best})$ 4: . $Y_{best} \leftarrow Y_{worst}$ 5: . else 6: . if $fit (X^{\sim}) < fit (Y_{\mod (Gen, H)})$ and $H D (X^{\sim}, Y_{\mod (Gen, H)}) < 0.8$ then 7: . $Y_{\mod (Gen, H)} \leftarrow X^{\sim}$ ; $fit (Y_{\mod (Gen, H)}) \leftarrow fit (X^{\sim})$ 8: . end if 9: . end if

3.7. Population Diversity Maintenance Strategy

In traditional genetic algorithms, the diversity of the population decreases as iterations proceed, and many individuals with the same fitness value will appear, causing the algorithm to fall into premature convergence. Therefore, the entire population is checked every $N_{t}$ generations to maintain the diversity of the population. The specific operations are as follows:

If the fitness values of two individuals are the same and their MS (Machine Selection) parts are also completely the same, the MS part of one of them must be randomly regenerated. Otherwise, a reverse operation is performed on their OS (Operation Sequence) parts.

4. Variable Neighborhood Descent Search

VND can systematically search in multiple different neighborhoods and is an effective local search algorithm [25]. Due to its flexibility and efficiency, VND has become an important tool for complex combinatorial optimization problems such as logistics scheduling [26], shop scheduling [27], and vehicle routing problems [28].

The neighborhood structure generated by adjusting the operations on the critical path can avoid certain blind searches and improve the efficiency of finding better solutions [29]. Neighborhood search based on the critical path has been widely applied to job shop scheduling [30] and flexible job shop scheduling [31]. However, there are relatively few studies on critical paths considering the AGV transportation process.To address this issue, this paper designs a critical path identification method that incorporates a backward-search strategy. The core procedure is as follows:

Endpoint Identification: The operation with the latest completion time in the scheduling solution is selected as the critical path endpoint. When multiple operations share the identical latest completion time, one is randomly selected as the path endpoint.

Backward Tracing: Starting from the identified endpoint, a systematic backward recursion is performed to identify three types of predecessor dependencies:

–. Job Predecessor: The immediately preceding operation within the same workpiece.

–. Machine Predecessor: The immediately preceding operation processed on the same machine.

–. AGV Transport Predecessor: If the current operation’s initiation depends on AGV delivery, the previous operation transported by the same AGV (i.e., the transport task release point).

Path Construction: At each backward tracing step, the predecessor that enables the latest possible start time for the current operation is selected and incorporated into the critical path. This recursive process continues until reaching an operation with a load start time of zero (i.e., the scheduling origin), thereby completely constructing a hybrid “processing–transport” critical path from start to end.

To facilitate the search for the critical path, the following symbols are defined:

Job predecessor: $P J (h)$ ; Machine predecessor: $P M (h)$ ; AGV transportation predecessor: $P A (h)$ . $Flag = 1$ : continuous based on machine predecessors; $Flag = 2$ : continuous based on job predecessors; $Flag = 3$ : continuous based on AGV transportation.

4.1. Backward Search Method for Critical Path Involving Transportation Processes

The specific steps for identifying the critical path are detailed in Algorithm 3.

To better illustrate the reverse critical path identification process, we present a step-by-step demonstration using the Figure 3. Since operations $O_{12}$ and $O_{13}$ shared identical latest completion times, $O_{12}$ was randomly selected as the current critical operation. Upon updating its start time to 6, forward analysis showed neither its machine predecessor $O_{21}$ (completion time: 3.5) nor job predecessor $O_{11}$ (completion time: 5) matched this value. However, the AGV load start time for $O_{12}$ equaled 6, prompting the inclusion of this transport operation as the new critical node. With the start time now set to 5, the job predecessor $O_{11}$ exhibited matching completion time and was consequently added to the critical set. Subsequent analysis of $O_{11}$ (start time: 3) revealed alignment with its machine predecessor $O_{31}$ ’s completion time, leading to its inclusion. As $O_{31}$ constituted both the initial job and machine operation, its AGV load completion time of 1 matched the updated start time, qualifying this transport operation as critical. The process terminated at start time 0, yielding the final critical path—including transport phases—along the yellow arrows: $O_{12}$ , $O_{11}$ , and $O_{31}$ .

Algorithm 3 Calculate Critical Path

Input: Scheduling solution.

Output: Critical path (set of critical operations).

1: . Randomly select an operation $O_{h}$ whose completion time equals the makespan as the current critical operation; set $Flag = 1$ . % init

2: . while $L T_{h}^{s} > 0$ do % backtrack from the end

3: . if $Flag = 1$ then % check machine predecessor

4: . if $C (P M (h)) = S (h)$ then add $P M (h)$ to the set and set it as current; else % tie not on machine

5: . if $L T_{h}^{c} = S (h)$ then add $O_{h}$ to the set, set as current; $Flag = 3$ ; else $Flag = 2$ ;

end if

6: . end if

7: . else if $Flag = 2$ then % check job predecessor

8: . if $C (P J (h)) = S (h)$ then add $P J (h)$ to the set and set it as current else if $S (P J (h)) = S (h)$ then add $P J (h)$ to the set and set it as current

else % not predecessor

9: . if $L T_{h}^{c} = S (h)$ then add $O_{h}$ to the set, set as current; $Flag = 3$ ; else $Flag = 1$ ;

end if

10: . end if

11: . else % $Flag = 3$ , transportation-related

12: . if $L T_{h}^{c} = S (h)$ then add $O_{h}$ and set as current else if $E T_{h}^{c} = S (h)$ then add $O_{h}$ and set as current else if $L T_{P A (h)}^{c} = S (h)$ then add $P A (h)$ and set as current else $Flag = 2$

end if

13: . end if

14: . end while

4.2. Neighborhood Structure Based on Critical Path

The variable neighborhood search algorithm improves the current solution by utilizing different neighborhood structures, so the design of neighborhood structures is crucial for the algorithm’s optimization ability. Therefore, this paper combines the defined critical operations to make targeted adjustments to OS and MS, and designs 5 different neighborhood structures. The details are as follows:

N1:. Randomly select a critical operation, then randomly select another operation in the entire sequence, and swap their positions.

N2:. Randomly select a critical operation and randomly insert it into the entire sequence.

N3:. Randomly select a critical operation and replace its currently selected machine.

N4:. Randomly select a critical operation. If it is the first operation of a job, replace its current optional machine; if there is a job predecessor, replace the currently selected machine of the job predecessor.

N5:. Randomly select two critical operations and swap their positions.

VND algorithm incorporates multiple distinct neighborhood structures. During its execution, a candidate solution is selected as the incumbent. The search process initiates within the first neighborhood structure. If an improved solution is identified, it replaces the incumbent, and the search reverts to the first neighborhood. Otherwise, the algorithm proceeds to explore the subsequent neighborhood structure. This iterative procedure continues until no further improvement is achievable across all neighborhood structures. A schematic representation of the application of one such neighborhood structure is illustrated in Figure 4.

4.3. Adaptive Variable Neighborhood Descent Search

The standard variable neighborhood descent algorithm only searches the individual with the best fitness in each generation of the population, while other individuals in the population also have the potential to be searched. Therefore, this section adopts an adaptive strategy. The number of individuals performing variable neighborhood descent search in the current generation is:

(15) $n p = ⌊N p \times sin (\frac{G e n}{M a x G e n} \times \frac{π}{2})⌋$

where

G e n

is the current iteration number, and

M a x G e n

represents the maximum number of iterations of the algorithm,

N p

is the population size, and

⌊ \cdot ⌋

denotes rounding down the value inside.

In the early stage of evolution, GA cannot provide high-quality individuals for VND, so the probability of finding good solutions through VND is low. At this time, the number of individuals searched by VND ( $n p$ ) is small, which can save the time of the entire algorithm. In the later stage of the algorithm, there are a large number of optimal solutions in GA; increasing the number of individuals searched by VND at this time is conducive to finding better solutions. Therefore, during the evolution process of GA, the number of searches by VND is adaptively adjusted with the current number of iterations, which helps balance the exploitation and exploration capabilities of the algorithm.

The specific search process is shown in Algorithm 4.

Algorithm 4 Adaptive Variable Neighborhood Descent (AVND)
Input: Current iteration solution set S, number of solutions $n p$ to explore, max neighborhood index $K_{max}$ .
Output: Improved solution set $S^{*}$ .
1:	for $i = 1$ to $n p$ do	% iterate over selected solutions
2:	$X = S (i)$ ; $k = 1$ ; compute the critical operations of X.	% init
3:	while $k < K_{max}$ do	% neighborhood loop
4:	apply neighborhood structure $N_{k}$ on X to obtain a feasible $X^{*}$ .	% move
5:	if $f (X) < f (X^{})$ then* $X \leftarrow X^{}$ ; $f (X) \leftarrow f (X^{})$ ; $k \leftarrow 1$ else $k \leftarrow k + 1$ ; end if
6:	end while
7:	$S (i) \leftarrow X$ .	% write back
8:	end for

4.4. Algorithm Flowchart

The specific flow of the proposed algorithm is shown in Figure 5 below.

4.5. Complexity Analysis of the IVNDGA

In this section, we analyze the overall time complexity of the IVNDGA. Let $N_{p}$ denote the population size, H the size of the external memory archive, N the total number of operations, M the total number of machines, G the maximum number of iterations, $N_{t}$ the interval iteration count, and T the average number of iterations for the variable neighborhood descent search. According to the algorithmic framework, IVNDGA incorporates population initialization, fitness evaluation, improved genetic operations, and adaptive variable neighborhood descent search. The time complexity of population initialization is $O (N_{p} \cdot N) + O (N_{p} \cdot N \cdot M)$ , while fitness evaluation requires $O (3 N_{p} \cdot N)$ operations. Within the genetic algorithm component, the selection operation has complexity $O (N_{p})$ , hybrid crossover requires $O (2 N_{p} \cdot N)$ , hybrid mutation costs $O (N_{p} \cdot (1 + \frac{1 + M}{2}))$ , the external memory archive strategy demands $O (2 H \cdot N)$ , and population diversity maintenance requires $O (N_{p}^{2} \cdot N)$ . The variable neighborhood descent search, which includes critical path computation, neighborhood structure exploration, and fitness re-evaluation, exhibits complexity of $O (N_{p} \cdot T \cdot (N + N + 3 N))$ . The overall time complexity of IVNDGA can be expressed as:

$O (N_{p} \cdot N (1 + M + 3) + G \cdot (N_{p} \cdot (1 + 2 N + 1 + \frac{1 + M}{2} + 5 T \cdot N) + 2 H \cdot N) + \frac{G \cdot N_{p}^{2} \cdot N}{N_{t}})$

When the number of iterations is sufficiently large, the time complexity of the algorithm approximately equals $O (G \cdot N_{p} \cdot T \cdot N)$ . The space complexity is primarily determined by population storage requirements. The algorithm maintains a population of size $N_{p}$ , with each individual having an encoding length proportional to N, resulting in a space complexity of $O (N_{p} \cdot N)$ . The additional space required by other components, including the external memory archive and neighborhood structures, is negligible compared to the population storage and does not affect the overall complexity order.

5. Simulation Experiment Analysis

5.1. Operating Environment and Parameter Setting

The algorithm in this paper is programmed using Matlab R2020b, and the operating environment is Intel(R) Xeon(R) Silver 4210 CPU @ 2.20 GHz 2.19 GHz, with 32.0 GB of RAM.

Since the parameter settings have a significant impact on the algorithm’s running time and computational accuracy, to enable the algorithm to run in a relatively optimal state, this paper selects some parameters through orthogonal experiments. These parameters include: population size $N_{p}$ , interval iteration number $N_{t}$ , crossover probability $P_{c}$ , and mutation probability $P_{m}$ .

The selected parameter values are $N_{p} \in {100, 200, 300}$ , $N_{t} \in {50, 100, 150}$ , $P_{c} \in {0.7, 0.8, 0.9}$ , and $P_{m} \in {0.1, 0.15, 0.2}$ . Taking MKT01 as an example, this paper takes the average value of 10 repeated runs.

It can be seen from Figure 6 that when the population size $N_{p}$ is 200, relatively good solutions can be obtained; thus, $N_{p} = 200$ is set. When the interval iteration number is 100, solutions of relatively good quality are obtained; thus, $N_{t} = 100$ is set. As the mutation probability increases, the solution quality improves accordingly; thus, $P_{c} = 0.9$ is set. When the mutation probability is 0.15, solutions of good quality can be obtained; thus, $P_{m} = 0.15$ is set. Additionally, the maximum number of iterations maxGen is set to $10 \times N$ (where N is the total number of operations), the maximum capacity H of the external memory archive is set to 20, and the number of available AGVs is 2. All data used in the experimental simulations of this paper are sourced from Reference [15], where Instance 1 and Instance 2 are small-scale, Instance 3 is medium-scale, and Instance 4 is large-scale data.

Furthermore, to comprehensively assess the algorithm’s robustness and average performance, all experimental runs were conducted without fixing a random seed. Each independent run was initialized with a random state based on the system clock. This approach ensures that our results reflect the algorithm’s stability across a variety of random scenarios and is a common practice in evolutionary algorithm research to demonstrate generalizability.

The complete parameter settings of the IVNDGA algorithm are summarized in Table 4.

5.2. Comparison of Different Algorithms

In order to more intuitively measure the performance of the improved algorithm, this paper introduces the relative percentage increase as a comparison index, and the specific formula is:

(16) $R P I = \frac{|C_{\max}^{low} - C_{\max}|}{C_{\max}} \times 100 %$

where

C_{\max}

represents the optimal value obtained by GA, and

C_{\max}^{low}

is the optimal value obtained in other improved algorithms.

For the small-scale Instance 1, we compared the proposed IVNDGA against several state-of-the-art algorithms. These algorithms include: algorithm from study [10] (CP2), the Multistart Biased Random Key Genetic Algorithm [13] (BRKGA), the Iterative Improved Local Search methods [14] (IILS-I and IILS-II), Late Acceptance Hill Climbing [15] (LAHC), a Mixed-Integer Linear Programming approach [15] (MILP), and Hybrid Discrete Particle Swarm Optimization [16] (HDPSO). This selection encompasses a diverse range of metaheuristic, exact, and hybrid methodologies, ensuring comprehensive benchmarking.

As shown in Table 5, both IVNDGA and the CP2 achieved optimal solutions across all 10 test cases. To rigorously evaluate statistical performance, we conducted Wilcoxon signed-rank tests ( $α = 0.05$ ). The results demonstrate that IVNDGA achieved identical solutions to the exact method CP2, confirming equivalent solution quality. Significant superiority was observed against BPKGA ( $p = 0.039$ ) and highly significant advantage over HDPSO ( $p = 0.008$ ). Although no significant differences were detected when compared with ILS-I, ILS-II, and LAHC (H = 1000) ( $p = 0.083$ , $0.102$ , and $0.317$ , respectively), the collective evidence confirms IVNDGA’s statistically verified competitive edge in small-scale optimization.

Table 6 summarizes the performance comparison on Instances 2-1 between our IVNDGA and other algorithms: BRKGA [13], MILP [15], LAHC (H = 1000) [15], and the algorithm from study [17] (PGA). The results show that IVNDGA attained optimal solutions in all 28 instances and even found new best-known solutions for EX81, EX72, and EX84. Wilcoxon tests further substantiate these findings: IVNDGA exhibits highly significant improvements over BRKGA ( $p < 0.001$ ) and PGA ( $p < 0.01$ ), while maintaining significant advantage against LAHC ( $p < 0.05$ ). Notably, performance equivalent to MILP was observed with no statistical significance. These results statistically validate IVNDGA’s robust performance in medium-scale instances.

Table 7 compares the performance of IVNDGA with BRKGA [13], MILP [15], LAHC (H = 1000) [15], and PGA [17] on Instance 2-2. The results indicate that our algorithm achieves marginally better average PRI values and secures new optimal solutions for instances EX730, EX741, and EX840. Additional Wilcoxon tests conducted on independent instances reinforce these conclusions: significant advantages are maintained against PGA ( $p < 0.01$ ), LAHC ( $p < 0.01$ ), and BRKGA ( $p < 0.05$ ), while equivalent performance to MILP persists ( $p = 0.317$ ). Such consistent outcomes across diverse problem instances underscore IVNDGA’s remarkable robustness.

Table 8 compares IVNDGA with MILP [15], LAHC (H = 1000) [15], and Tabu Search [20] (Tabu) on the more complex Instance 3. IVNDGA obtains superior solutions for cases MFJST09 and MFJST10, while yielding comparable average PRI values. Statistical analysis reveals identical performance to MILP across all valid instances, while no significant differences are observed against LAHC (H $= 1000$ ) ( $p = 0.180$ ) or Tabu Search ( $p = 0.066$ ). These findings indicate that IVNDGA maintains performance parity with established metaheuristics in this challenging test environment.

The performance of IVNDGA on large-scale Instance 4 is evaluated against IILS-I [14], IILS-II [14], LAHC (H = 1000) [15], and Tabu [20] in Table 9. The proposed algorithm secures new superior solutions across all instances except MKT04. Final Wilcoxon tests confirm these advantages: highly significant improvements are demonstrated against ILS-I, ILS-II, and Tabu (all $p < 0.01$ ), while significant superiority over LAHC (H $= 1000$ ) is maintained ( $p < 0.01$ ). This comprehensive statistical evidence establishes IVNDGA’s consistently superior optimization capability across problems of varying complexity and scale.

In summary, the proposed IVNDGA algorithm demonstrates consistently superior optimization performance across all four benchmark sets of varying scales. It either matches the solution quality of state-of-the-art methods or achieves statistically significant improvements, particularly over population-based algorithms. Supported by comprehensive Wilcoxon signed-rank tests, these results confirm that IVNDGA possesses enhanced search capability and robust performance, establishing it as a highly competitive approach for solving complex optimization problems.

5.3. Ablation Experiment Analysis

To further verify the effectiveness of the proposed strategies, ablation experiments were conducted on Instance 4. Each case was run independently 10 times, and the optimal values obtained by the algorithm were adopted. Herein, GA refers to the genetic algorithm without any additional operations; IGA1 denotes the genetic algorithm integrated with the external memory archive strategy; IGA2 represents the genetic algorithm combined with population diversity maintenance; and VNDGA indicates the genetic algorithm incorporated with variable neighborhood descent search.

As can be seen from Table 10, both algorithms incorporating the external memory archive strategy and the population diversity management strategy can improve the genetic algorithm to a certain extent. IGA1 outperforms IGA2 in terms of improvement effect when the instance scale is small, while IGA2 shows better improvement as the instance scale increases. The VNDGA algorithm achieves the best optimization performance, indicating that the variable neighborhood descent search based on the critical path is effective. In summary, combining multiple strategies with local search is feasible, and it achieves better results especially in large-scale instances.

6. Conclusions

This paper proposes a heuristic allocation strategy based on the shortest AGV idle time and employs multiple initialization rules to enhance initial population quality. To better balance the global exploration and local exploitation capabilities of the genetic algorithm, we introduce three key strategies: an external memory archive, a population diversity maintenance mechanism, and a critical-path-based VND search. Simulation experiments confirm the feasibility and superiority of the proposed IVNDGA algorithm for solving the FJSP-AGV problem. For future research, we plan to extend this algorithm to multi-objective and dynamic scheduling scenarios in FJSP-AGV, aiming to further enhance manufacturing production efficiency.

Author Contributions

Conceptualization, H.J. and D.P.; methodology, Y.C.; software, H.J. and Q.T.; validation, Y.C.; formal analysis, Y.C.; investigation, Q.T. and Y.Y.; resources, Y.Y.; data curation, H.J. and Q.T.; writing—original draft preparation, H.J.; writing—review and editing, Y.C., D.P. and Y.Y.; visualization, H.J. and Q.T.; supervision, D.P.; project administration, D.P.; funding acquisition, H.J. and D.P. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

The original data presented in the study are openly available in reference [15].

Conflicts of Interest

Author Han Jia was employed by the company China National Petroleum Company. The remaining authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1 Schematic diagram of the FJSP-AGV encoding strategy.

Figure 2 FJSP-AGV decoding and scheduling map.

Figure 3 Schematic Diagram of Reverse Search.

Figure 4 Implementation of a VND Neighborhood Structure.

Figure 5 Flowchart of IVNDGA to solve FJSP-AGV.

Figure 6 Trends in the impact of parameters.

Table 1

Model Parameters.

Notations	Definitions
n	Total number of jobs
m	Total number of machines
v	Total number of AGVs
$n_{i}$	Total number of operations for job i
N	Total number of operations for all jobs
J	Job set $J = {J_{1}, J_{2}, \dots, J_{n}}$
M	Machine set $M = {M_{0}, M_{1}, M_{2}, \dots, M_{m}}$ , where $M_{0}$ represents the loading and unloading area
V	AGV set $V = {V_{1}, V_{2}, \dots, V_{v}}$
$O_{i}$	All operations set of job i: $O_{i} = {O_{i 1}, O_{i 2}, \dots, O_{i n_{i}}}$
w	AGV index
$t_{w}$	Current available time of AGV w
$l_{w}$	Current location of AGV w
$k, h$	Machine index
$i, p$	Job index
$j, q$	Operation index
$O_{i j}$	The j-th operation of job i
$P_{i j k}$	Processing time of operation $O_{i j}$ on machine k
$T_{k}^{h}$	Transportation time from machine k to machine h
$S_{i j k}$	Start time of operation $O_{i j}$ on machine k
$C_{i j k}$	Completion time of operation $O_{i j}$ on machine k
$C_{i}$	Completion time of the i-th job
$C_{\max}$	Maximum completion time
$E T_{i j w}^{s}$	Start time of empty transportation of operation $O_{i j}$ by AGV w
$E T_{i j w}^{c}$	Completion time of empty transportation of operation $O_{i j}$ by AGV w
$L T_{i j w}^{s}$	Start time of loaded transportation of operation $O_{i j}$ by AGV w
$L T_{i j w}^{c}$	Completion time of loaded transportation of operation $O_{i j}$ by AGV w
$X_{i j k w}$	0–1 decision variable: takes 1 if operation $O_{i j}$ is processed on machine k and by AGV w, otherwise 0
$Y M_{i j p q k}$	0–1 decision variable: takes 1 if $O_{i j}$ is processed on machine k before $O_{p q}$ , otherwise 0
$Y A_{i j p q w}$	0–1 decision variable: takes 1 if $O_{i j}$ is transported by AGV w before $O_{p q}$ , otherwise 0
L	Represents a sufficiently large integer

Table 2

Processing Time Instance for FJSP-AGV.

Job	Operation	$M_{1}$	$M_{2}$
$J_{1}$	$O_{11}$	2	3
$J_{1}$	$O_{12}$	3	2
$J_{2}$	$O_{21}$	4	3
$J_{2}$	$O_{22}$	2	3
$J_{3}$	$O_{31}$	2	2
$J_{3}$	$O_{32}$	1	–

Note: ‘–’ represents that processing of operation $O_{32}$ is not supported by machine $M_{2}$ .

Table 3

Transportation Time Instance for FJSP-AGV.

	$M_{0}$	$M_{1}$	$M_{2}$
$M_{0}$	0	1	0.5
$M_{1}$	2	0	1
$M_{2}$	1	1	0

Table 4

The parameter settings of the IVNDGA algorithm.

Parameters	Description	Value
$N_{p}$	Population size	200
$N_{t}$	Interval iteration number	100
$P_{c}$	Crossover probability	0.9
$P_{m}$	Mutation probability	0.15
maxGen	Maximum number of iterations	$10 \times N$
H	Maximum capacity of external archive	20
AGV	Number of available AGVs	2

Table 5

Comparison of different algorithms.

Instances	M-J-N	CP2 [10]	BPKGA [13]	IILS-I [14]	IILS-II [14]	MILP [15]	LAHC [15]	HDPSO [16]	IVNDGA
fjsp1	8-7-19	134	138	136	136	134	134	148	134
fjsp2	8-6-15	114	118	114	114	114	114	118	114
fjsp3	8-6-16	120	120	120	120	120	120	130	120
fjsp4	8-5-19	114	120	114	114	114	114	126	114
fjsp5	8-5-13	94	96	94	94	94	94	94	94
fjsp6	8-6-18	138	138	140	138	138	138	150	138
fjsp7	8-8-19	108	112	110	112	110	112	126	108
fjsp8	8-6-20	178	178	178	178	178	178	186	178
fjsp9	8-5-17	144	144	144	144	144	144	152	144
fjsp10	8-6-21	174	174	174	176	174	174	190	174
#best		10	5	7	8	9	9	1	10
mean PRI		0	1.77	0.48	0.52	0.19	0.37	7.74	0

Note: ‘#’ represents the count of optimal values.

Table 6

Comparison of different algorithms on Instance 2-1.

Instance	M-J-N	BRKGA [13]	MILP [15]	LAHC [15]	PGA [17]	IVNDGA
EX11	4-5-13	70	70	70	70	70
EX21	4-6-15	76	-	74	74	74
EX41	4-5-19	72	-	72	72	72
EX51	4-5-13	61	59	59	59	59
EX71	4-8-19	81	-	81	82	81
EX81	4-6-20	93	-	94	-	91 *
EX91	4-5-17	82	-	82	82	82
EX12	4-5-13	59	56	56	56	56
EX22	4-6-15	62	61	62	62	61
EX42	4-5-19	58	-	56	59	56
EX52	4-5-13	49	47	48	47	47
EX72	4-8-19	62	-	62	63	61 *
EX82	4-6-20	80	-	82	-	80
EX92	4-5-17	69	69	69	69	69
EX13	4-5-13	62	62	62	62	62
EX23	4-6-15	67	-	67	67	67
EX43	4-5-19	63	-	61	62	61
EX53	4-5-13	53	52	52	52	52
EX73	4-8-19	67	-	66	67	66
EX83	4-6-20	84	-	85	-	84
EX93	4-5-17	74	-	73	74	73
EX14	4-5-13	78	78	78	78	78
EX24	4-6-15	87	-	84	84	84
EX44	4-5-19	82	-	80	80	80
EX54	4-5-13	68	64	64	64	64
EX74	4-8-19	97	-	94	95	94
EX84	4-6-20	102	-	102	-	101 *
EX94	4-5-17	89	-	87	87	87
#best		10	10	21	16	28
mean PRI		1.67	0	0.30	0.34	−0.17

Note: ‘#’ represents the count of optimal values. ‘-’ represents that the algorithm cannot produce a valid solution. ‘*’ denotes results that are superior to those of other algorithms.

Table 7

Comparison of different algorithms on Instance 2-2.

Instance	M-J-N	BRKGA [13]	MILP [15]	LAHC [15]	PGA [17]	IVNDGA
EX110	4-5-13	94	94	94	94	94
EX210	4-6-15	104	104	104	106	104
EX410	4-5-19	92	-	92	93	92
EX510	4-5-13	77	77	77	77	77
EX710	4-8-19	102	-	103	102	102
EX810	4-6-20	141	-	141	-	141
EX910	4-5-17	119	118	118	118	118
EX120	4-5-13	91	91	91	91	91
EX220	4-6-15	102	102	102	103	102
EX420	4-5-19	90	88	88	88	88
EX520	4-5-13	76	76	76	76	76
EX720	4-8-19	98	-	99	99	98
EX820	4-6-20	138	-	138	-	138
EX920	4-5-17	118	116	116	116	116
EX130	4-5-13	95	92	92	92	92
EX230	4-6-15	102	102	102	102	102
EX430	4-5-19	90	89	89	89	89
EX530	4-5-13	78	77	77	77	77
EX730	4-8-19	100	-	101	102	99 *
EX830	4-6-20	139	-	139	-	139
EX930	4-5-17	118	118	118	118	117 *
EX140	4-5-13	99	97	97	99	97
EX241	4-6-15	153	153	154	154	153
EX441	4-5-19	133	131	134	134	131
EX541	4-5-13	113	113	113	113	113
EX740	4-8-19	104	-	105	104	104
EX741	4-8-19	150	-	150	151	149 *
EX840	4-6-20	144	-	144	-	143 *
EX940	4-5-17	121	119	121	120	119
#best		16	18	19	14	29
mean PRI		0.46	0.04	0.30	0.59	−0.80

Note: ‘#’ represents the count of optimal values. ‘-’ represents that the algorithm cannot produce a valid solution. ‘*’ denotes results that are superior to those of other algorithms.

Table 8

Comparison of different algorithms on Instance 3.

Instance	M-J-N	MILP [15]	LAHC [15]	Tabu [20]	IVNDGA
MFJST01	6-5-15	485	485	485	485
MFJST02	7-5-15	463	463	463	463
MFJST03	7-6-18	482	482	482	482
MFJST04	7-7-21	576	576	579	576
MFJST05	7-7-21	532	532	532	532
MFJST06	7-8-24	652	652	652	652
MFJST07	7-8-32	-	898	901	898
MFJST08	8-9-36	-	900	900	900
MFJST09	8-11-44	-	1120	1133	1100 *
MFJST10	8-12-48	-	1238	1270	1227 *
#best		6	8	8	10
mean PRI		0	0	0.37	−0.27

Note: ‘#’ represents the count of optimal values. ‘-’ represents that the algorithm cannot produce a valid solution. ‘*’ denotes results that are superior to those of other algorithms.

Table 9

Comparison of different algorithms on Instance 4.

Instance	M-J-N	IILS-I [14]	IILS-II [14]	LAHCR [15]	Tabu [20]	IVNDGA
MKT01	6-10-55	184	187	187	187	175 *
MKT02	6-10-58	148	142	148	134	124 *
MKT03	8-15-150	368	357	371	342	333 *
MKT04	8-15-90	258	256	225	254	244
MKT05	4-15-106	329	318	312	310	295 *
MKT06	15-10-150	367.5	347.5	389.5	336.5	311 *
MKT07	5-20-100	291	285	291	289	263 *
MKT08	10-20-225	829.5	820.5	846	770.5	760 *
MKT09	10-20-240	768.5	756.5	794	709	696.5 *
MKT10	15-20-240	684.5	670	712.5	616.5	600.5 *
#best		0	0	1	0	9
mean PRI		7.73	5.35	7.64	1.59	−5.06

Note: ‘#’ represents the count of optimal values. ‘*’ denotes results that are superior to those of other algorithms.

Table 10

Comparison of improvements in the proposed algorithm.

Instance	GA	IGA1	IGA2	VNDGA	IVNDGA
MKT01	191	184	187	177	175
MKT02	139	130	133	126	124
MKT03	381	368	370	353	333
MKT04	265	252	253	248	244
MKT05	328	314	315	305	295
MKT06	379.5	359	355	332.5	311
MKT07	305	293	291	276	263
MKT08	895.5	853	827.5	793	760
MKT09	790.5	766	758	721	696.5
MKT10	693	675.5	660.5	627	600.5
#best	0	0	0	0	10
mean PRI	14.02	9.07	8.82	3.69	0

Note: ‘#’ represents the count of optimal values.

References

1. Meng, L.; Duan, P.; Gao, K.; Zhang, B.; Zou, W.; Han, Y.; Zhang, C. MIP Modeling of Energy-Conscious FJSP and Its Extended Problems: From Simplicity to Complexity. Expert Syst. Appl.; 2024; 241, 122594. [DOI: https://dx.doi.org/10.1016/j.eswa.2023.122594]

2. Wu, B.; Ding, Y.C.; Abla, B. Research Status of AGV and Machine Integrated Scheduling. Comput. Eng. Appl.; 2023; 59, pp. 1-12. (In Chinese)

3. Liu, J.; Sun, B.; Li, G.; Chen, Y. Multi-Objective Adaptive Large Neighbourhood Search Algorithm for Dynamic Flexible Job Shop Schedule Problem with Transportation Resource. Eng. Appl. Artif. Intell.; 2024; 132, 107917. [DOI: https://dx.doi.org/10.1016/j.engappai.2024.107917]

4. Ren, W.; Yan, Y.; Hu, Y.; Guan, Y. Joint Optimisation for Dynamic Flexible Job-Shop Scheduling Problem with Transportation Time and Resource Constraints. Int. J. Prod. Res.; 2022; 60, pp. 5675-5696. [DOI: https://dx.doi.org/10.1080/00207543.2021.1968526]

5. Fuladi, S.K.; Kim, C.S. Dynamic Events in the Flexible Job-Shop Scheduling Problem: Rescheduling with a Hybrid Metaheuristic Algorithm. Algorithms; 2024; 17, 142. [DOI: https://dx.doi.org/10.3390/a17040142]

6. Fatemi-Anaraki, S.; Tavakkoli-Moghaddam, R.; Foumani, M.; Vahedi-Nouri, B. Scheduling of Multi-Robot Job Shop Systems in Dynamic Environments: Mixed-Integer Linear Programming and Constraint Programming Approaches. Omega; 2023; 115, 102770. [DOI: https://dx.doi.org/10.1016/j.omega.2022.102770]

7. Bilge, U.; Ulusoy, G. A Time Window Approach to Simultaneous Scheduling of Machines and Material Handling System in an FMS. Oper. Res.; 1995; 43, pp. 1058-1070. [DOI: https://dx.doi.org/10.1287/opre.43.6.1058]

8. Lacomme, P.; Larabi, M.; Tchernev, N. Job-Shop Based Framework for Simultaneous Scheduling of Machines and Automated Guided Vehicles. Int. J. Prod. Econ.; 2013; 143, pp. 24-34. [DOI: https://dx.doi.org/10.1016/j.ijpe.2010.07.012]

9. Yao, Y.J.; Liu, Q.H.; Li, X.Y.; Gao, L. A Novel MILP Model for Job Shop Scheduling Problem with Mobile Robots. Robot. Comput. Integr. Manuf.; 2023; 81, 102506. [DOI: https://dx.doi.org/10.1016/j.rcim.2022.102506]

10. Ham, A. Transfer-Robot Task Scheduling in Flexible Job Shop. J. Intell. Manuf.; 2020; 31, pp. 1783-1793. [DOI: https://dx.doi.org/10.1007/s10845-020-01537-6]

11. Lim, C.H.; Moon, S.K. A Two-Phase Iterative Mathematical Programming-Based Heuristic for a Flexible Job Shop Scheduling Problem with Transportation. Appl. Sci.; 2023; 13, 5215. [DOI: https://dx.doi.org/10.3390/app13085215]

12. Yao, Y.; Liu, Q.; Fu, L.; Li, X.; Yu, Y.; Gao, L. A Novel Mathematical Model for the Flexible Job-Shop Scheduling Problem with Limited Automated Guided Vehicles. IEEE Trans. Autom. Sci. Eng.; 2024; 22, pp. 7449-7462. [DOI: https://dx.doi.org/10.1109/TASE.2024.3356255]

13. Homayouni, S.M.; Fontes, D.B.M.M.; Gonçalves, J.F. A Multistart Biased Random Key Genetic Algorithm for the Flexible Job Shop Scheduling Problem with Transportation. Int. Trans. Oper. Res.; 2023; 30, pp. 688-716. [DOI: https://dx.doi.org/10.1111/itor.12878]

14. Hu, X.Y.; Yao, X.F.; Hung, P.; Zeng, Z.R. Improved Iterative Local Search Algorithm for Solving Multi-AGV Flexible Job Shop Scheduling Problem. Comput. Integr. Manuf. Syst.; 2022; 28, pp. 2198-2212. (In Chinese)

15. Homayouni, S.M.; Fontes, D.B.M.M. Production and Transport Scheduling in Flexible Job Shop Manufacturing Systems. J. Glob. Optim.; 2021; 79, pp. 463-502. [DOI: https://dx.doi.org/10.1007/s10898-021-00992-6]

16. Liu, E.; Yao, X.; Tao, T.; Jin, H. Improved Flower Pollination Algorithm for Job Shop Scheduling Problems Integrated with AGVs. Comput. Integr. Manuf. Syst.; 2019; 25, pp. 2219-2236.

17. Chaudhry, I.; Rafique, A.; Elbadawi, I.; Aichouni, M.; Usman, M.; Boujelbene, M.; Boudjemline, A. Integrated Scheduling of Machines and Automated Guided Vehicles (AGVs) in Flexible Job Shop Environment Using Genetic Algorithms. Int. J. Ind. Eng. Comput.; 2022; 13, pp. 343-362. [DOI: https://dx.doi.org/10.5267/j.ijiec.2022.2.002]

18. Chen, K.; Bi, L.; Wang, W.Y. Research on Integrated Scheduling of AGV and Machine in Flexible Job Shop. J. Syst. Simul.; 2022; 34, pp. 461-469.

19. Li, W.L.; Li, H.; Wang, Y.; Han, Y. Optimizing Flexible Job Shop Scheduling with Automated Guided Vehicles Using a Multi-Strategy-Driven Genetic Algorithm. Egypt. Inform. J.; 2024; 25, 100437. [DOI: https://dx.doi.org/10.1016/j.eij.2023.100437]

20. Berterottiere, L.; Dauzère-Pérès, S.; Yugma, C. Flexible Job-Shop Scheduling with Transportation Resources. Eur. J. Oper. Res.; 2024; 312, pp. 890-909. [DOI: https://dx.doi.org/10.1016/j.ejor.2023.07.036]

21. Yao, Y.; Gui, L.; Li, X.; Gao, L. Tabu Search Based on Novel Neighborhood Structures for Solving Job Shop Scheduling Problem Integrating Finite Transportation Resources. Robot. Comput.-Integr. Manuf.; 2024; 89, 102782. [DOI: https://dx.doi.org/10.1016/j.rcim.2024.102782]

22. Serna, N.J.E.; Seck-Tuoh-Mora, J.C.; Medina-Marin, J.; Hernandez-Romero, N.; Barragan-Vite, I.; Armenta, J.R.C. A Global-Local Neighborhood Search Algorithm and Tabu Search for Flexible Job Shop Scheduling Problem. PeerJ Comput. Sci.; 2021; 7, e574. [DOI: https://dx.doi.org/10.7717/peerj-cs.574] [PubMed: https://www.ncbi.nlm.nih.gov/pubmed/34141895]

23. Sun, K.; Zheng, D.; Song, H.; Cheng, Z.; Lang, X.; Yuan, W.; Wang, J. Hybrid Genetic Algorithm with Variable Neighborhood Search for Flexible Job Shop Scheduling Problem in a Machining System. Expert Syst. Appl.; 2023; 215, 119359. [DOI: https://dx.doi.org/10.1016/j.eswa.2022.119359]

24. Zhang, Q.; Guan, X.; Wang, H.; Pardalos, P.M. Maximum Shortest Path Interdiction Problem by Upgrading Edges on Trees Under Hamming Distance. Optim. Lett.; 2021; 15, pp. 2661-2680. [DOI: https://dx.doi.org/10.1007/s11590-020-01687-9]

25. Duarte, A.; Mladenović, N.; Sánchez-Oro, J.; Todosijević, R. Variable Neighborhood Descent. Handbook of Heuristics; Martí, R.; Pardalos, P.M.; Resende, M.G.C. Springer: Berlin/Heidelberg, Germany, 2018; pp. 341-367.

26. Lan, Y.L.; Liu, F.; Ng, W.W.Y.; Zhang, J.; Gui, M. Decomposition Based Multi-Objective Variable Neighborhood Descent Algorithm for Logistics Dispatching. IEEE Trans. Emerg. Top. Comput. Intell.; 2020; 5, pp. 826-839. [DOI: https://dx.doi.org/10.1109/TETCI.2020.3002228]

27. Zhang, B.; Pan, Q.K.; Meng, L.L.; Zhang, X.; Ren, Y.; Li, J.; Jiang, X. A Collaborative Variable Neighborhood Descent Algorithm for the Hybrid Flow Shop Scheduling Problem with Consistent Sublots. Appl. Soft Comput.; 2021; 106, 107305. [DOI: https://dx.doi.org/10.1016/j.asoc.2021.107305]

28. Kyriakakis, N.A.; Sevastopoulos, I.; Marinaki, M.; Marinakis, Y. A Hybrid Tabu Search–Variable Neighborhood Descent Algorithm for the Cumulative Capacitated Vehicle Routing Problem with Time Windows in Humanitarian Applications. Comput. Ind. Eng.; 2022; 164, 107868. [DOI: https://dx.doi.org/10.1016/j.cie.2021.107868]

29. Liu, G.; Wang, Y.; Zhang, F. Convergence Analysis of Job Shop Scheduling Problem Based on Critical Path. Comput. Integr. Manuf. Syst.; 2014; 20, pp. 1078-1087. (In Chinese)

30. Xue, L.L. Block Structure Neighborhood Search Genetic Algorithm for Job-Shop Scheduling. Comput. Integr. Manuf. Syst.; 2021; 27, pp. 2848-2857. (In Chinese)

31. Zheng, J.; Pan, D.Z. An Improved Firefly Algorithm for Multi-Objective Flexible Job Shop Scheduling. Control Eng. China; 2024; 31, pp. 272-280. (In Chinese)

© 2025 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

Critical-Path-Based Variable Neighborhood Descent for the Joint Scheduling of FJSP and AGVs

Content area

Abstract

Full text

1. Introduction

2. Problem Description and Mathematical Model

2.1. Model Parameters

2.2. Problem Description

2.3. Mathematical Model

3. Improved Genetic Algorithm

3.1. Encoding and Decoding

3.2. Population Initialization

3.3. Selection Operations

3.4. Hybrid Crossover Operation

3.5. Hybrid Mutation Operation

3.6. External Memory Archive Strategy

3.7. Population Diversity Maintenance Strategy

4. Variable Neighborhood Descent Search

4.1. Backward Search Method for Critical Path Involving Transportation Processes

4.2. Neighborhood Structure Based on Critical Path

4.3. Adaptive Variable Neighborhood Descent Search

4.4. Algorithm Flowchart

4.5. Complexity Analysis of the IVNDGA

5. Simulation Experiment Analysis

5.1. Operating Environment and Parameter Setting

5.2. Comparison of Different Algorithms

5.3. Ablation Experiment Analysis

6. Conclusions