MILP Modeling and Optimization of Three-Stage Flexible Job Shop Scheduling Problem with Assembly and AGV Transportation

Abstract

The flexible job shop scheduling problem (FJSP) is commonly encountered in practical manufacturing environments. A product is typically built by assembling multiple jobs during actual manufacturing. AGVs are normally used to transport the jobs from the processing shop to the assembly shop, where they are assembled. Therefore, studying the integrated scheduling problem with its processing, transportation, and assembly stages is extremely beneficial and significant. This research studies the three-stage flexible job shop scheduling problem with assembly and AGV transportation (FJSP-T-A), which includes processing jobs, transporting them via AGVs, and assembling them. A mixed integer linear programming (MILP) model is established to obtain optimal solutions. As the MILP model is challenging for solving large-scale problems, a novel co-evolutionary algorithm (NCEA) with two different decoding methods is proposed. In NCEA, a restart operation is developed to improve the diversity of the population, and a multiple crossover strategy is designed to improve the quality of individuals. The validity of the MILP model is proven by analyzing its complexity. The effectiveness of the restart operator, multiple crossovers, and the proposed algorithm is demonstrated by calculating and analyzing the RPI values of each algorithm's results within the time limit and performing a paired t-test on the average values of each algorithm at the 95% confidence level. This paper studies FJSP-T-A by minimizing the makespan for the first time, and presents a MILP model and an NCEA with two different decoding methods.

Introduction

Flexible production needs are becoming increasingly difficult for the conventional assembly line method to meet due to the diversification of market demand and the rise in product changes. The flexible job shop has become increasingly popular in modern manufacturing shops as a more adaptable and diverse style of production. Flexible job shops can handle many different types of products and operations in parallel, allowing each operation to be machined on any machine. Furthermore, it has been established that the flexible job shop problem (FJSP) is an NP-hard problem [1]. In actual production, the finished job often needs to be transported to another factory. A job is an integral part of the product and takes part in its assembly. The processing shop and assembly shop are separated by a specific amount of distance. From the processing shop to the assembly shop, the jobs need to be moved by AGVs. The quantity of AGVs is restricted because of their expensive price. Every task needs to be transported, which takes time as well.

This paper studies a three-stage assembly problem (FJSP-T-A).

• 1st Stage: the first stage is the processing of FJSP.

• 2nd Stage: the transportation of a multi-AGV and multi-load AGV transportation problem.

• 3rd Stage: the assembly stage of a parallel machine assembly problem.

FJSP-T-A needs to solve several sub-problems in three stages, namely, the processing machine selection sub-problem and operation sequencing sub-problem in the processing stage, the AGV selection sub-problem in the transportation stage, and the assembly machine selection sub-problem and operation sequencing sub-problem in the assembly stage. As a result, FJSP-T-A is a more intricate NP-hard problem than FJSP, the AGV scheduling problem, and the parallel machine scheduling problem.

This paper solves FJSP-T-A from both exact and approximation methods. The exact method is to resolve the problem by establishing a mixed integer linear programming (MILP) model specifically designed for FJSP-T-A. The MILP model serves as the foundation for research on the workshop scheduling problem, particularly when taking into account new goals or restrictions. The MILP model is crucial and capable of finding the best answer. We can extract the neighborhood structural characteristics, neighborhood relationships, neighborhood quick assessment technique, and fitness landform of the scheduling problem by analyzing the optimal solution produced by the MILP model [2]. Therefore, this thesis provides a MILP model of FJSP-T-A to solve the optimal solution. The MILP model is unable to resolve large-scale examples' optimal solutions in an acceptable amount of time. To resolve these large-scale cases, a new co-evolutionary algorithm (NCEA) is therefore suggested. In nature, species coexist in large numbers, exchange information, and work together to further the general evolution through mutual competition and cooperation. The application of the co-evolutionary techniques to evolutionary algorithms has been motivated by these phenomena.

Moreover, co-evolutionary algorithm (CEA) shows good effectiveness for solving FJSP [3]. Compared to previous studies, this work offers three key contributions:

1. FJSP-T-A with minimizing makespan is studied for the first time.

2. To minimize makespan, this paper designed a novel MILP model for the first time.

3. This paper proposed a novel NCEA with two different decoding methods.

The structure of this thesis is as follows: Section 2 reviews the literature on FJSP and CEA, Section 3 details the proposed MILP model, Section 4 describes NCEA in seven aspects, Section 5 offers the experimental results, and Section 6 introduces conclusions and future works.

Literature Review

Literature Review of FJSP

Scholars started to take an interest in the FJSP when it was first presented in 1990. First, mathematical approaches were used to study the FJSP. These approaches had a number of serious shortcomings, including the inability to handle large-scale problems quickly and a high learning curve. A hierarchical approach based on taboo search (TS) meta-heuristics was proposed in Ref. [4] to solve the FJSP. This signaled the start of the FJSP solution process employing intelligent optimization techniques. Intelligent optimization techniques overcome the constraints of mathematical methods in solving the FJSP by providing faster solution speeds than mathematical methods and by approximating solutions to large-scale issues.

Later, the FJSP was extensively researched by academics as a scheduling problem, which led to the creation of more advanced optimization methods to resolve the FJSP [5, 6–7]. Exact methods and approximate methods are the two types of approaches used to resolve the FJSP. For small-scale problems, exact methods primarily use MILP approaches, which can effectively determine the optimal solution. Approximate methods mainly rely on metaheuristic algorithms, which can obtain near-optimal solutions within a reasonable timeframe. In particular, for large-scale problems, approximate methods can provide near-optimal solutions when the MILP model is unable to find a viable solution. Generally, the FJSP can be separated into single-stage FJSP and multi-stage FJSP based on the research stage.

Literature Review of Single-stage FJSP

In single-stage FJSP, every operation is finished in the same stage. It usually concentrates on reducing work waiting and completion times, and optimizing resource utilization within the same stage.

(1) Solving the single-stage FJSP by models

To minimize the makespan of FJSP, Ozguven et al. [8] presented a MILP model based on the precedence relationships of operations for the first time, Elazeem et al. [9] presented a mathematical model, and Huang et al. [10] presented an auto MILP model. To minimize the total energy consumption, Meng et al. [5] designed six novel MILP models. To minimize the makespan of FJSP with work centers, Hansmann et al. [11] developed a MILP model and subsequently introduced a branch-and-bound method. To minimize the makespan and the total machining time, Gran et al. [12] formulated a mixed-integer goal programming (MIGP) model. For small instances, exact methods can produce optimal solutions. However, they are highly time-intensive and may not find any feasible solution for large instances.

(2) Solving the single-stage FJSP by metaheuristic algorithms

To minimize the makespan of FJSP, Nouiri et al. [13] presented a particle swarm optimization (PSO) algorithm, Yazdani et al. [14] presented a parallel variable neighborhood search (PVNS) algorithm, Ho et al. [15] presented a learnable genetic architecture (LEGA), Li et al. [16] presented a hybrid algorithm (HA) that combines genetic algorithm (GA) with TS algorithm, Zhang et al. [17] developed an improved GA, Wang et al. [3] developed a multiple swarm collaborative GA (MSCGA) that utilizes multiple swarm structures for solving the two sub-problems of FJSP independently, Shen et al. [18] presented a TS algorithm, and Fan et al. [19] presented a HA and put forth three strategies to address various critical paths during the local search phase.

To minimize the total workload of machines, the workload of the critical machine and the makespan, Zhang et al. [20] developed a HA, Shao et al. [21] presented a HA, Kato et al. [22] presented a hybrid solution approach, and Gu et al. [23] designed a novel discrete PSO algorithm. To minimize energy consumption and production cycle of FJSP with transportation constraints, Dai et al. [24] presented an enhanced GA. To minimize the mean of earliness and tardiness and the makespan, Gao et al. [25] developed a Pareto-based grouping discrete harmony search algorithm (PGDHS).

Literature Review of Multi-stage FJSP

Multi-stage FJSP involves the production of jobs or products through multiple stages. One scenario is that after a job is accomplished, the job is transported the next processing machine and further processed. Additionally, only one job is transported by the AGV in parallel. Another scenario is that after the job is processed, it is either assembled into a product or transported first and then assembled.

(1) Solving the multi-stage FJSP by models

To minimize the makespan of FJSP with AGV, Yuan et al. [26] developed an optimization model, Han et al. [27] proposed a novel MILP model, and Yao et al. [28] presented a MILP model with a more streamlined model structure. To minimize the flow time, tardiness and energy consumption of flexible assembly job shop scheduling problems (FAJSP), Hu et al. [29] developed a MILP model. To minimize the makespan and the total energy consumption of FJSP-T-A, Yang et al. [30] developed a novel MILP model.

(2) Solving the multi-stage FJSP by metaheuristic algorithms

To minimize the makespan of FJSP with AGV, Xin et al. [31] designed a hybrid algorithm based on multi-perspective modeling, Luo et al. [32] designed a collaborative hybrid evolutionary algorithm, Zhang et al. [33] developed a deep reinforcement learning method, and Pan et al. [34] presented a learning-based multi-population evolutionary optimization method. To minimize the total machine load, the total AGV operation time and the makespan, Wen et al. [35] developed an effective HA. To minimize the makespan and the total energy consumption, Zhang et al. [36] developed a memory-based algorithm. For the FAJSP with job constraints, to minimize the makespan, Lin et al. [37] proposed a job constraint GA. To minimize the makespan of FJSP with sequence-dependent setup times and assembly operations, Fattahi et al. [38] designed a PSO algorithm and two HAs based on PSO. To minimize the makespan and the energy consumption of FJSP with assembly operations, Ren et al. [39] presented a novel heuristic algorithm that integrates PSO and GA. For the distributed FJSP considering transportation and assembly, to minimize the energy consumption and the makespan, Pan et al. [40] designed a knowledge-based bi-level optimization algorithm.

Literature Review of CEA

Co-evolution was initially defined by Janzen [41] in 1980. In 1991, the parasitic co-evolution model was introduced [42]. In 1994, Potter et al. [43] presented a general model. In 1995, a competitive co-evolutionary model was presented [44]. Later, researchers proved the significant effectiveness of CEA in solving scheduling problems. Algorithms integrating CEA with other approaches have been developed and applied across various domains. Imrani et al. [45] presented a co-evolutionary inspired method. Filipiak et al. [46] employed evolutionary algorithms and CEAs in conjunction with local search algorithms to help network operators make decisions about connection behavior in monitored power systems. A new cooperative coevolving PSO (CCPSO) algorithm was developed [47]. To resolve the minimax problem, Fabris et al. [48] designed a co-evolutionary differential evolution (DE) algorithm. Pan [49] designed an innovative cooperative co-evolutionary ABC (CCABC) algorithm to resolve the steelmaking-continuous casting scheduling problem. To resolve constrained optimization problems, Ghasemishabankareh et al. [50] developed a cooperative algorithm. Hiew et al. [51] presented a competitive CEA to train artificial neural networks.

An extensive examination of the literature shows that the integration of three-stage problems is quite difficult, and that the majority of the works that have been done so far have concentrated on one- or two-stage integration schedules. The invention of the FJSP-T-A utilizing MILP and a novel co-evolutionary algorithm NCEA with two distinct decoding techniques is the main goal of the current study.

Problem Description

Parameters Definition

In Table 1, the symbols are defined. In Table 2, the decision variables are described.

Table 1. Symbols definition

Symbol	Definition
$i,i^{\prime }$	Job indices
$j,j^{\prime }$	Operation indices
$p,p^{\prime }$	Product indices
$k,k^{\prime }$	Processing machine indices
$t$	AGV shipment index
$a$	Assembly machine index
$v$	AGV index
$n$	Job number
$m$	Processing machine number
$\mathit{np}$	Product number
$n_i$	Operation number of job $i$
$\mathit{nA}$	AGV number
$\mathit{na}$	Assembly machine number
$I$	Job set and $I=\left\{\text{1,2},,,·,·,·,,,n\right\}$
$J_i$	Operation set of job $i$ and $J_i=\left\{\text{1,2},,,·,·,·,,,n_i\right\}$
$J_i^{\prime }$	Operation set of job $i$ and $J_i^{\prime }=\left\{\text{1,2},,,·,·,·,,,n_i,-,1\right\}$
$P$	Product set and $P=\left\{\text{1,2},,,·,·,·,,,n,p\right\}$
$P{I}_p$	Job set of product $p$
$K$	Processing machine set and $K=\left\{1,,,·,·,·,,,m\right\}$
$K_{i,j}$	Processing machine set of operation $O_{i,j}$
$A$	Assembly machine set and $A=\left\{1,,,·,·,·,,,n,a\right\}$
$V$	AGV set and $V=\left\{\text{1,2},,,\cdots ,,,n,A\right\}$
$T$	AGV shipment set and $T=\left\{1,,,·,·,·,,,n\right\}$
$T^{\prime }$	AGV shipment set and $T^{\prime }=\left\{1,,,·,·,·,,,n,-,1\right\}$
$\mathit{Cap}$	AGV capacity
$O_{i,j}$	$j$-th operation of job $i$
$t_{i,j,k}$	Processing time of operation $O_{i,j}$ on processing machine $k$
$t{a}_p$	Assembly time of product $p$
$\mathit{Tr}$	Transportation time
$\mathit{bigM}$	An extremely large positive value.

Table 2. Decision variables definition

Variable categories	Processing stages	Decision variables	Definition
Binary decision variables	Processing	$X_{i,j,k}$	It equals to 1 when processing machine $k$ is chosen for operation $O_{i,j}$; otherwise, it equals to 0.
		$Y_{i,j,i^{\prime },j^{\prime }}$	It equals to 1 when operation $O_{i,j}$ is processed before operation $O_{i^{\prime },j^{\prime }};$ otherwise, it equals to 0.
	Transportation	$X{T}_{i,v,t}$	It equals to 1 when job $i$ is transported by AGV $v$ in the $t$-th time; otherwise, it equals to 0.
	Assembly	$X{A}_{p,a}$	It equals to 1 when assembly machine $a$ is selected for product $p$; otherwise, it equals to 0.
	Assembly	$Y{A}_{p,p^{\prime }}$	It equals to 1 when product $p$ is assembled before product $p^{\prime }$; otherwise, it equals to 0.
Continuous decision variables	Processing	$S_{i,j}$	It denotes the starting processing time of operation $O_{i,j}$.
	Transportation	$S{T}_{v,t}$	It denotes the starting transportation time of AGV $v$'s $t$-th transport.
	Assembly	$S{A}_p$	It denotes the starting assembly time of product $p$.
	Assembly	$C_{\mathit{max}}$	It denotes the makespan.

FJSP-T-A Definition

The FJSP-T-A studied in this paper is divided into three main stages: processing stage, transportation stage and assembly stage. The schematic diagram is provided in Figure 1. The scheduling objective of FJSP-T-A is to minimize the makespan for the entire production process.

[See PDF for image]

Figure 1

The schematic diagram of FJSP-T-A

Processing Stage

During the processing stage, the main objective of FJSP-T-A is to allocate a processing machine to each operation and establish the processing sequence of operations. There is a set of $n$ jobs $I=\left\{\text{1,2},,,·,·,·,,,n\right\}$ and a set of $m$ processing machines $K=\left\{1,,,·,·,·,,,m\right\}$. Each job $J_i$ is composed of a series of operations $\left\{O_{i1},,,O_{i2},,,·,·,·,,,O_{i{n}_i}\right\}$. The jobs are machined on $m$ processing machines. Each operation is allocated to a processing machine chosen from a designated set of available machines. The operations within the same job must be performed following their specified sequence.

Transportation Stage

In the transportation stage, the main objective of the FJSP-T-A is to select an AGV for each job and establish the order of transport of jobs. There is a set $V=\left\{\text{1,2},,,\cdots ,,,n,A\right\}$ of AGVs. The processing shop and the assembly shop have a certain distance. The jobs must be transported from the processing shop to the assembly shop using AGVs, and this transportation requires a specific amount of time. The travel modes of AGVs include loaded travel and unloaded travel. The loaded travel indicates that AGVs take jobs from the processing shop to the assembly shop. The unloaded travel indicates that AGVs return from the assembly shop to the processing shop.

Assembly Stage

In the assembly stage, the main objective of FJSP-T-A is to allocate an assembly machine for each product and determine the assembly sequence of products. There is a set of $\mathit{na}$ assembly machines $A=\left\{1,,,·,·,·,,,n,a\right\}$ and a set of $\mathit{np}$ products $P=\left\{\text{1,2},,,·,·,·,,,n,p\right\}$. Each product needs to be assembled on one of $\mathit{na}$ assembly machines.

Assumptions

1. In the processing stage, all jobs are independent. All processing machines are working at time 0. No sequencing constraints exist between the operations of different jobs. Each operation is processed only once. Operation preemption is prohibited. Each processing machine is processed only one job in parallel. Transportation times between different processing machines are negligible.

2. In the transportation stage, all AGVs are working at time 0. All AGVs are the same. The maximum number of jobs transported by the AGV at each time cannot exceed the capacity of the AGV. Each job is transported only by a single AGV. An AGV can transport a job only after it has been completed. Each AGV moves at a constant speed and the path interference of the AGV is not considered. The time to load and unload jobs is negligible.

3. In the assembly stage, all assembly machines are ready for use at time zero. All assembly machines are the same. Each job belongs to only one product. Only when the jobs of the product all arrive at the assembly shop, they can be delivered to the assembly machines for assembly. There are no processing order constraints between products. Only one machine can be selected for the assembly of a product. Each product can only be assembled once. Non-preemptive scheduling is enforced, with each machine restricted to handling a single product simultaneously. The conversion time between different products on the same assembly machines is assumed to be neglected.

FJSP-T-A Example

To show FJSP-T-A more clearly, an example is provided in Figure 2. Specifically, the example presented in Figure 2 has five jobs, two products, two processing machines, two AGVs and two assembly machines. The Product $P_1$ consists of Jobs $J_1$ and $J_2$. The Product $P_2$ consists of Jobs $J_3$, $J_4$ and $J_5$. The Null in the figure indicates that the AGVs return without load. The completion times of Jobs 1-5 are 181, 110, 192, 121 and 170 respectively. After the processing of Jobs $J_2$ and $J_4$, the AGV $V_1$ transports Jobs $J_2$ and $J_4$ to the assembly shop. Then, Jobs $J_5$ and $J_1$ are processed successively. The AGV $V_2$ transports Jobs $J_5$ and $J_1$ to the assembly shop. Finally, the AGV $V_1$ return to the processing shop to transport the last processed Job $J_3$. The jobs of the Product $P_1$ all arrive at the assembly shop earlier than Product $P_2$. Therefore, the Product $P_1$ first selects the machine for assembly. After the Job $J_3$ arrives at the assembly shop, the Product $P_2$ begins to be assembled. The completion times of Products 1-2 are 252 and 258 respectively. Thus, the makespan is 258.

[See PDF for image]

Figure 2

Example of the FJSP-T-A

Mathematical Model

This section provides a comprehensive introduction to the MILP model, with the model flow described in Figure 3.

[See PDF for image]

Figure 3

The MILP flow chart

The objective function is provided as follows:

1

$$\begin{array}{c}minf=C_{\mathit{max}}\end{array}$$

The constraints are provided as follows:

(1) Constraint Sets of Processing Stage

2

$$\sum _{k\in K_{i,j}}{X}_{i,j,k}=1,\forall i\in I,j\in J_i,$$

3

$$\begin{array}{c}{S}_{i,j}+t_{i,j,k}\le S_{i^{\prime },j^{\prime }}+\\ bigM\left(3,-,Y_{i,j,i^{\prime },j^{\prime }},-,X_{i,j,k},-,X_{i^{\prime },j^{\prime },k}\right),\\ \forall i\in I,i^{\prime }\in I,i<i^{\prime },\\ j\in J_i,j^{\prime }\in J_{i^{\prime }},k\in K_{i,j}\cap K_{i^{\prime },j^{\prime }},\end{array}$$

4

$$\begin{array}{c}{S}_{i^{\prime },j^{\prime }}+t_{i^{\prime },j^{\prime },k}\le S_{i,j}+\\ bigM\left(2,+,Y_{i,j,i^{\prime },j^{\prime }},-,X_{i,j,k},-,X_{i^{\prime },j^{\prime },k}\right),\\ \forall i\in I,i^{\prime }\in I,i<i^{\prime },\\ j\in J_i,j^{\prime }\in J_{i^{\prime }},k\in K_{i,j}\cap K_{i^{\prime },j^{\prime }},\end{array}$$

5

$$\begin{array}{c}{S}_{i,j+1}\ge S_{i,j}+{\sum }_{k\in K_{i,j}}{t}_{i,j,k}{X}_{i,j,k},\\ \forall i\in I,j\in J_i^{\prime },\end{array}$$

6

$$\begin{array}{c}{S}_{i,j}\ge 0,\forall i\in I,j\in J_i,\end{array}$$where, Eq. (2) guarantees that each operation $O_{i,j}$ is machined on only one processing machine in the processing stage. Eqs. (3) and (4) define the processing sequencing restrictions for operations allocated to the same processing machine. Eq. (5) guarantees that operation $O_{i,j+1}$ can only be begin once operation $O_{i,j}$ is completed. Eq. (6) restricts the value range of the decision variable $S_{i,j}$, ensuring that all jobs begin at time zero.

(2) Constraint Sets of Transportation Stage

7

$$\begin{array}{c}S{T}_{v,t}+bigM\left(1-X{T}_{i,v,t}\right)\ge S_{i,n_i}+\\ \sum _{k\in K_{i,n_i}}{t}_{i,n_i,k}{X}_{i,n_i,k},\forall j\in J,v\in V,t\in T,\end{array}$$

8

$$\begin{array}{c}{\sum }_{v\in V}{\sum }_{t\in T}X{T}_{i,v,t}=1,\forall i\in I,\end{array}$$

9

$$\begin{array}{c}{\sum }_{i\in I}X{T}_{i,v,t}\ge {\sum }_{i\in I}X{T}_{i,v,t+1},\forall v\in V,t\in T^{\prime },\end{array}$$

10

$$\begin{array}{c}{\sum }_{i\in I}X{T}_{i,v,t}\le Cap,\forall v\in V,t\in T,\end{array}$$

11

$$\begin{array}{c}S{T}_{v,t+1}\ge S{T}_{v,t}+2Tr,\forall v\in V,t\in T^{\prime },\end{array}$$

12

$$\begin{array}{c}S{T}_{v,t}\ge 0,\forall v\in V,t\in T,\end{array}$$where, Eq. (7) guarantees that jobs are transported only after they have been completed in the processing stage. Specifically, if AGV $v$ transports the job $i$ at the $t_{\mathit{th}}$ time, that is, $X{T}_{i,v,t}=1$, then Eq. (7) enforces that $S{T}_{v,t}$ is at least the finishing time of the final operation of job $i$, given by $S_{i,n_i}+{\sum }_{k\in K_{i,n_i}}{t}_{i,n_i,k}{X}_{i,n_i,k}$. Eq. (8) ensures that each job is transported only once by a single AGV during the transportation stage. Eq. (9) mandates that AGVs transport jobs sequentially, preventing idle travel between the processing and assembly stages. Eq. (10) ensures that at any given time, the number of jobs transported by an AGV does not surpass its capacity. Eq. (11) defines the relationship between the start times of consecutive AGV transports, ensuring that the starting time $S{T}_{v,t+1}$ is no less than the combined value of the starting time $S{T}_{v,t}$ and the round-trip time. Eq. (12) defines the valid range for the decision variable $S{T}_{v,t}$, ensuring that all AGVs are available from time zero.

(3) Constraint Sets of Assembly Stage

13

$$\begin{array}{c}S{A}_p+bigM\left(1-X{T}_{i,v,t}\right)\ge S{T}_{v,t}+Tr,\\ \forall v\in V,t\in T,p\in P,i\in P{I}_p,\end{array}$$

14

$$\begin{array}{c}{\sum }_{a\in A}X{A}_{p,a}=1,\forall p\in P,\end{array}$$

15

$$\begin{array}{c}S{A}_p+t{a}_p\le S{A}_{p^{\prime }}\\ +bigM\left(3,-,Y,A_{p,p^{\prime }},-,X,A_{p,a},-,X,A_{p^{\prime },a}\right),\\ \forall p\in P,p^{\prime }\in P,p<p^{\prime },a\in A,\end{array}$$

16

$$\begin{array}{c}S{A}_{p^{\prime }}+t{a}_{p^{\prime }}\le S{A}_p+\\ bigM\left(2,+,Y,A_{p,p^{\prime }},-,X,A_{p,a},-,X,A_{p^{\prime },a}\right),\\ \forall p\in P,p^{\prime }\in P,p<p^{\prime },a\in A,\end{array}$$

17

$$\begin{array}{c}S{A}_p+t{a}_p\le C_{\mathit{max}},\forall p\in P,\end{array}$$where, Eq. (13) ensures that the assembly of a product cannot begin until all jobs contained within the product have been transported to the assembly stage. Eq. (14) guarantees that each product is chosen for one assembly machine only during the assembly stage. Eqs. (15) and (16) define assembly sequencing restrictions for products allocated to the same assembly machine. Eq. (17) restricts that the makespan is no less than the assembly time to complete all products.

The Proposed NCEA for Solving FJSP-T-A

The CEA adopts a divide-and-conquer approach to address complex optimization problems [52]. The fundamental concept involves breaking down a system into several smaller systems, each of which develops on its own. Then, in order to accomplish overall evolution, the subsystems are integrated to form a new system [53]. In this study, chromosomes and populations are subjected to CEA. Considering that the issues in the solution's representation are independent of one another. As a result, the examined problem is ideally suited for the CEA to solve.

Encoding and Decoding

Only the operations sequencing (OS) string and processing machine selection (PMS) string in the processing stage of the encoding need to be taken into consideration, as the AGV selection in the transportation stage and the process sequencing and assembly machine selection in the assembly stage are decided by particular rules in the decoding. Additionally, in the processing step, distinct coding techniques are employed for the processing machine selection and operation sequence. One PMS swarm is present in each job, and it is this swarm that determines which machine is used for each action. An OS individual and N PMS individuals chosen one at a time from the PMS swarms comprise a solution [3]. In the processing stage, the subproblem of processing machine selection is determined by PMS, while the subproblem of operation sequence is determined by OS. The lengths of the OS and PMS are the same and correspond to the total number of processes for all workloads.

Specifically, in the encoding, each operation of a job is defined by the OS as the job number. The order of the job number determines the sequence of operations which is established by the sequence in which integer values appear while performing a left-to-right scan of the OS string. The frequency with which the same integer value appears indicates the operation number for the job. For instance, in the OS string, the first occurrence of the same integer value can be regarded as the first operation of the job. The second occurrence can be interpreted as the second operation of the job, and so on. Similarly, the processing machine selection for each corresponding operation of the jobs is represented by the PMS string. However, the integer values do not represent processing machine identifiers, but rather indices of the candidate machine set. Figure 4 illustrates an example of the encoding method. The processing machine index for operation $O_{\text{3,1}}$ is 3, which corresponds to the actual processing machine number 2.

[See PDF for image]

Figure 4

The encoding chromosome

The decoding process of NCEA is as follows:

Step 1: According to the PMS string, assign processing machines for each operation.

Step 2: Identify the operations allocated to each processing machine.

Step 3: Identify the set of processing machines selected for each job.

Step 4: Calculate start and completion times for each operation.

Step 5: Adjust for idle time and insert the next operation if possible.

Step 6: Generate start and completion times for all jobs.

Step 7: Assign jobs to AGVs for transportation.

Step 8: Assign jobs to assembly machines.

Step 9: Generate start and completion times during assembly.

Two decoding methods, namely D-J and D-P, are designed. In both decoding methods, if there are at least two idle AGVs, the one with a smaller index is selected. The same principle is applied to the selection of assembly machines. The first decoding method D-J involves sorting the finishing times of jobs in ascending order and prioritizing the transportation of the job located at the front of the sequence. Additionally, the product can be assembled only when all its components arrive at the assembly shop. The product is first assembled when its components first arrive. As shown in Figure 5, the five jobs are transported to the assembly shop by AGVs in the order of their finishing times. The completion times of Jobs 1-5 are 91, 55, 99, 72 and 85 respectively. After Jobs $J_2$ and $J_4$ are processed, the AGV $V_1$ transports them to the assembly shop. Following that, Jobs $J_1$ and $J_5$ are processed and then transported by AGV $V_2$. Finally, Job $J_3$ is processed and transported by $V_1$. According to the arrival times at the assembly shop, Jobs $J_1$ and $J_2$ of product $P_1$ are assembled first, followed by product $P_2$.

[See PDF for image]

Figure 5

D-J example

The second decoding method D-P involves arranging the products in increasing order of their earliest assembly time without considering transportation time. Priority is given to transporting the product containing jobs located at the front of the sequence. The product can be assembled only when all its components arrive at the assembly workshop, and the product is first assembled when its components first arrive. As shown in Figure 6, the five jobs are processed in the processing shop. The completion times of Jobs 1-5 are 102, 54, 85, 72 and 82 respectively. The jobs with the maximum makespan from products are selected, and sort them in ascending order. The order is Jobs $J_3$ and $J_1$. Because Job $J_3$ belongs to product $P_2$ and Job $J_1$ belongs to product $P_1$, so the earliest assembly time for product $P_2$ is earlier than that of product $P_1$, the jobs from product $P_2$ are transported first. According to the completion times of the jobs, Jobs $J_4$ and $J_5$ are transported by AGV $V_1$, followed by Job $J_3$ and the earlier completed Job $J_2$ from product $P_1$, which are transported by AGV $V_2$. At this point, all the jobs from product $P_2$ have arrived at the assembly shop, and product $P_2$ is assembled first. Finally, AGV $V_1$ returns to the processing shop, transports Job $J_1$ to the assembly shop, and product $P_1$ begins its assembly. The “Null” in Figures 5 and 6 represents AGVs returning empty.

[See PDF for image]

Figure 6

D-P example

Initialization

The population's quality significantly influences the solving speed and effectiveness of population-based intelligent algorithms. Therefore, the population is initialized using the steps described below.

Step 1: Randomly generate N job sequences. Set t=0.

Step 2: For each job sequence, N processing machine selection sequences are generated, and N individuals are created.

Step 3: Update t to t+1.

Step 4: To determine if the termination condition is met, if it is not satisfied, go back to step 2; if it is satisfied, proceed to step 5.

Step 5: $N^2$ individuals are generated and their fitness values are computed separately.

Step 6: Sort by fitness value from smallest to largest.

Step 7: Take the first N individuals as the initial population.

Selection Operator

The binary tournament selection operator is employed to enhance the evolutionary process. The method involves randomly selecting two individuals from the population and advancing the one with superior fitness to the next generation. This process continues until the newly formed population attains the same size as the original population.

Population Division

The co-evolution method is applied to chromosomes and populations. According to the encoding method, it is divided into two sub-problems: OS and PMS. These two sub-problems evolve independently. The nature of the problem is very suitable for co-evolutionary methods. Therefore, the population can be divided into the OS population and the PMS population. It should be noted that there is a one-to-one correspondence between OS and MS, with each OS string corresponding to an MS string.

Crossover Operator

In this study, precedence operation crossovers (POX) for the job sequence population and uniform crossovers (UC) for the processing machine selection population are applied [27].

For POX, the following steps are performed: First, the job set is randomly partitioned into two subsets, referred to as Set1 and Set2. Next, the components derived from parent P1 belonging to Set1 are inserted into the same positions of offspring O1, and the components derived from parent P2 belonging to Set1 are inserted into the same positions of offspring O2. Finally, the components derived from parent P2 belonging to Set2 are sequentially inserted into offspring O1, and the components derived from parent P1 belonging to Set2 are sequentially inserted into offspring O2. Figure 7(a) provides an example of POX applied to job sequence string.

[See PDF for image]

Figure 7

Example of POX and UC

The steps for the UC operation on the machine selection strings are as follows: Initially, a specified quantity of binary numbers is generated randomly. Next, if the binary numbers generated equal 1, the genes from parents P1 and P2 are exchanged. Ultimately, offspring O1 and O2 are produced. Figure 7(b) provides an example of UC applied to machine selection strings.

In this paper, for each solution, POX and UC are conducted T times instead of one time. For example, cross parents P1 and P2 one time, and one offspring O1 and one offspring O2 are obtained. If cross parents P1 and P2 T times, T offsprings O1s and T offsprings O2s are obtained. Then, the best offsprings O1 and O2 are selected from the T offsprings O1s and O2s.

Restart Operation

As the algorithm iterates, individuals tend to converge to the same solution, resulting in a lack of diversity within the population. This can lead to algorithm stagnation and premature convergence. To increase population diversity, a restart operation is designed for FJSP-T-A, which ensures that the algorithm explores a broader solution space and increases the chances of finding the global optimum. Performing a restart operation in each generation consumes a significant amount of time and can decrease the algorithm's performance. Therefore, we have set a rule to execute the restart operation every Nt iteration. Specifically, the individuals within the population are ranked according to their fitness values in descending order, and the top 50% are retained while the remaining 50% are randomly generated.

The Steps of the Proposed NCEA

The steps of NCEA are as follows:

Step 1: Initialization: Set NCEA parameters and generate the initial population using a brute-force search strategy. Set the iteration count to t=0.

Step 2: Evaluation: Evaluate the fitness value of each chromosome in the population.

Step 3: Selection: Employ the selection method as described in Section 4.3.

Step 4: Multiple crossovers: Perform POX T times on the OS population and select the best solutions, and perform UC T times on the PMS population to select the best solutions.

Step 5: Restart operation: Perform the restart operation using the method provided in section 4.6.

Step 6: Termination: If the termination condition is met, proceed to Step 7. Otherwise, increment t by 1 and repeat from Step 2.

Step 7: Return the best-found solution.

Figure 8 illustrates the flow of the proposed NCEA.

[See PDF for image]

Figure 8

The flow chart of NCEA

Experimental Results

The MILP model and all the algorithms in this paper were run on a 12th Gen Intel(R) Core(TM) i7-12700 CPU @ 2.10 GHz with 16GB of RAM. The MILP model uses OPL modeling language, and the solver method used is a branch and cut[54, 55]. The branch-and-cut method integrates the cutting plane and branch-and-bound techniques. It works by applying a branch-and-bound algorithm while utilizing cutting planes to improve the linear programming relaxations. Two sets of instances, namely MFJSPTA01-10 and MKTA01-10 are used. All algorithms are separately run 20 times for each test, with a stopping time of 2 $N_{\mathit{oper}}$ seconds. The stopping criterion for the MILP model is configured to be 600 s for all instances.

Parameter Settings

The NCEA with decoding methods D-J and D-P are named NCEA -J and NCEA -P respectively. In NCEA -J and NCEA -P, the key parameters are mainly the population size N, the number of iterations Nt required for the restart operation and the number of multicrossover operations T. To assess the effect of parameter settings on the performance of NCEA, the design of experiments (DOE) approach is applied to examine the impact of parameters on algorithm efficiency. The levels of the three parameters involved in the test are provided in Table 3.

Table 3. Main parameters and levels

Parameters	Horizontal setting
	1	2	3
N	200	300	400
Nt	50	100	150
T	2	4	6

According to the levels of each parameter, an orthogonal array $L_9{(3}^3)$ is used for the experiments, which consists of 9 different combinations of parameters at different levels. The NCEA-J and NCEA-P are separately run 20 times for each different parameter combination using the MFJSTA10 and a stopping time of 2 $N_{\mathit{oper}}$ seconds. In Tables 4 and 5, “Response values” denote the average makespan obtained after running the MFJSTA10 20 times under the given parameter combination. The smaller the response values are, the better the set of parameters is. The orthogonal arrays for parameter settings of NCEA-J and NCEA-P are provided in Tables 4 and 5 respectively.

Table 4. Table of orthogonal parameter settings for NCEA-J

Number	Level			Response values
	N	Nt	T
1	1	1	1	1306.2
2	1	2	2	1305.3
3	1	3	3	1307.2
4	2	1	2	1307
5	2	2	3	1299.8
6	2	3	1	1304.5
7	3	1	3	1303.6
8	3	2	1	1301.9
9	3	3	2	1302.6

Table 5. Table of orthogonal parameter settings for NCEA-P

Number	Level			Response values
	N	Nt	T
1	1	1	1	1305.8
2	1	2	2	1307.3
3	1	3	3	1304.7
4	2	1	2	1297.3
5	2	2	3	1306
6	2	3	1	1307
7	3	1	3	1304
8	3	2	1	1307.7
9	3	3	2	1307

According to the above experiments, the response values and influence levels of the three main parameters are provided in Tables 6 and 7. In the "Level" column, the smaller the value is, the greater the level of influence of the parameter is.

Table 6. Mean response values and levels for each parameter of NCEA-J

Levels	N	Nt	T
1	1306.2	1305.6	1304.2
2	1303.8	1302.3	1305
3	1302.7	1304.8	1303.5
Extreme difference	3.5	3.3	1.5
Level	1	2	3

Table 7. Mean response values and levels for each parameter of NCEA-P

Levels	N	Nt	T
1	1305.9	1302.4	1306.8
2	1303.4	1307	1303.9
3	1306.2	1306.2	1304.9
Extreme difference	2.8	4.6	2.9
Level	3	1	2

Based on Table 6 and Figure 9, the optimal parameters for NCEA-J are determined as follows: N = 400, Nt = 100, T = 6. Based on Table 7 and Figure 10, the optimal parameters for NCEA-P are determined as follows: N = 300, Nt = 50 and T = 4.

[See PDF for image]

Figure 9

Trend of influence of each parameter of NCEA-J

[See PDF for image]

Figure 10

Trend of influence of each parameter of NCEA-P

Evaluation of MILP Model

Table 8 presents the comprehensive results derived from the MILP model. In Table 8, the abbreviations NB, NCV, and NC are used to denote specific components of the model. Specifically, NB refers to the count of 0-1 decision variables, NCV indicates the count of continuous decision variables, and NC signifies the count of constraints in the model. The term "Value" in the table represents the solutions that are successfully obtained within the stipulated timelimit. Additionally, the term "Gap" is used to convey the average optimality gap associated with the solutions that are obtained within this same time constraint. The "Gap" is defined as (CS-BS)/BS×100%, where "CS" represents the best solution obtained by the model within the given time limit, and "BS" represents the lower bound achieved within the same duration. It should be emphasized that a solution with a gap value of 0 is considered to be optimal, indicating that it meets the best possible solution criteria. Lastly, the term "Time" refers to the duration taken to arrive at the solution, providing insight into the efficiency of the solving process.

Table 8. Results of MILP model

Instances	NB	NCV	NC	Value	Gap(%)	Time
MFJSTA01	139	28	329	494	0	1.5
MFJSTA02	155	28	367	477	0	3.6
MFJSTA03	220	33	534	494	0	15.1
MFJSTA04	287	38	707	579	0	504.7
MFJSTA05	291	38	695	549	0	37.4
MFJSTA06	371	44	896	665	3.2	600
MFJSTA07	501	52	1224	904	12.2	600
MFJSTA08	586	58	1384	914	13.1	600
MFJSTA09	845	70	2014	1112	28.6	600
MFJSTA10	1008	76	2404	1275	23.6	600
MKTA01	1214	79	2987	63	0	8.9
MKTA02	1841	82	9182	62	0	32.0
MKTA03	8475	185	25620	286	67.5	600
MKTA04	2357	125	5424	89	1.1	600
MKTA05	3987	141	9158	214	77.5	600
MKTA06	8574	174	25694	-	-	-
MKTA07	5040	145	17334	192	88.5	600
MKTA08	6852	270	14847	553	92.4	600
MKTA09	15464	285	40184	507	95.5	600
MKTA10	19226	285	52816	-	-	600

Table 8 shows that the MILP model successfully solves instances MFJSTA01-05 and MKTA01-02 optimally within 600 seconds. However, for instances MFJSTA06-10, MKTA03-05, and MKTA07-09, it only finds feasible solutions, while it fails to find any feasible solutions for MKTA06 and MKTA10 within the timelimit. This limitation arises from the increased size of the instances, which leads to a significant rise in the solution space, the count of 0-1 decision variables, continuous decision variables, and constraints, complicating the branching process, the establishment of lower bounds, and cuts. These challenges indicate that the MILP model is inefficient for larger instances. Nonetheless, it effectively solves smaller instances optimally, which is crucial for scheduling problems, especially new ones. Optimal solutions serve as benchmarks for developing approximate methods, including heuristic and meta-heuristic algorithms.

Evaluation of NCEA

To verify the effectiveness of NCEA, the relative percentage increase (RPI) is used as a comparison metric, and it is reckoned as follows:

18

$$\begin{array}{c}RPI=\frac{MC-{\mathit{MC}}_{\mathit{best}}}{{\mathit{MC}}_{\mathit{best}}}\times 100,\end{array}$$where, $\mathit{MC}$ refers the best result of a test instance of an algorithm obtained through multiple repetitions, and ${\mathit{MC}}_{\mathit{best}}$ denotes the best $\mathit{MC}$ among all the compared algorithms. It should be noted that a smaller RPI value indicates better performance. In Tables 9 and 10, Best denotes the optimal value obtained by repeating an instance for 20 times, and Average refers the average value obtained by repeating an instance for 20 times. Mean RPI denotes the average value of the RPI of all the instances.

Table 9. Comparison results of NCEA-J and NCEA-P

Instances	Best		Average
	NCEA-P	NCEA-J	NCEA-P	NCEA-J
MFJSTA01	494	494	494	494
MFJSTA02	480	477	491.7	486.2
MFJSTA03	503	494	507	505.4
MFJSTA04	579	579	584.5	589
MFJSTA05	568	568	578.1	579
MFJSTA06	677	675	677	677.2
MFJSTA07	904	904	916.4	916.7
MFJSTA08	914	914	917.5	919.2
MFJSTA09	1141	1159	1163.6	1161.1
MFJSTA10	1234	1296	1294.1	1305.7
MKTA01	69	66	70	66.8
MKTA02	65	62	65.5	63.2
MKTA03	227	227	227	227
MKTA04	100	91	101.7	91.9
MKTA05	197	197	199.8	197.5
MKTA06	95	93	97.3	95.7
MKTA07	169	162	170.4	165.8
MKTA08	539	539	539.2	539
MKTA09	345	327	346.6	331.1
MKTA10	247	245	252.4	247.7
Mean RPI	1.74	0.33	1.5	0.1

The values in bold are the best

Table 10. Comparison results of MFJSTA and MKTA

Instances	Best			Average
	CEA-M	CEA-R	NCEA	CEA-M	CEA-R	NCEA
MFJSTA01	494	494	494	494	494	494
MFJSTA02	477	477	477	489.8	488.4	486.2
MFJSTA03	494	504	494	508	513.4	505.4
MFJSTA04	579	579	579	603.5	603.5	589
MFJSTA05	568	568	568	583.1	583.1	579
MFJSTA06	677	677	675	683.1	683.1	677.2
MFJSTA07	904	908	904	920.7	918.1	916.7
MFJSTA08	914	914	914	921	929.6	919.2
MFJSTA09	1138	1138	1159	1166.4	1166.4	1161.1
MFJSTA10	1299	1299	1296	1310.5	1310.5	1305.7
MKTA01	65	67	66	66.8	67.4	66.8
MKTA02	63	63	62	63.7	64	63.2
MKTA03	227	227	227	227	227	227
MKTA04	92	92	91	92.1	93.4	91.9
MKTA05	196	197	197	197.5	198.4	197.5
MKTA06	95	96	93	96.5	97.5	95.7
MKTA07	164	165	162	165.6	167	165.8
MKTA08	539	539	539	539	539	539
MKTA09	327	327	327	331.7	331.7	331.1
MKTA10	243	250	245	245.3	252.6	247.7
Mean RPI	0.33	0.86	0.24	0.44	0.92	0.05

The values in bold are the best

Comparison of Two Different Decoding Methods

In this section, the NCEA-J and NCEA-P are compared and evaluated. In Table 9, the comparison results are provided.

From Table 9, it can be noted that regarding the best value, except for instances MFJSTA09 and MFJSTA10, the performance of NCEA-J is better than or equal to NCEA-P. Regarding the average values, in most small-scale instances, NCEA-P outperforms NCEA-J, while in large-scale instances, except for MKTA03, NCEA-J demonstrates better performance than NCEA-P. Regarding both best values and average values, the Mean RPI values of NCEA-J are smaller than those of NCEA-P, indicating that the performance of NCEA-J is superior to that of NCEA-P. Therefore, NCEA-J is used for subsequent validation and comparison experiments.

Validation of the Restart Operation and Multiple Crossovers

To verify the validity of the restart operation, the NCEA is compared with the NCEA without the restart operation added. The NCEA without the restart operation added is named CEA-M. To assess the efficacy of multiple crossovers, the performance of NCEA will be compared with single crossover NCEA. The single crossover NCEA is named as CEA-R. In Table 10, the results of the comparison are provided.

According to Table 10, NCEA outperforms CEA-M in most instances, with Mean RPI values for both best and average values being less than CEA-M. This indicates that the restart operation is effective. Except for MFJSTA09, NCEA outperforms CEA-R in both best and average values. Furthermore, with the increase in problem scale, NCEA demonstrates superior performance. Additionally, regarding both best values and average values, the Mean RPI values of NCEA-J are smaller than those of NCEA-P, indicating the effectiveness of multiple crossovers.

Table 11 presents the paired t-test results at a 95% confidence level for the average values. All p-values are below 0.05, with CEA-M vs. NCEA at 0.011 and CEA-R vs. NCEA at 0.001. Thus, NCEA is statistically superior to both CEA-M and CEA-R, reinforcing the effectiveness of the restart operation and multiple crossovers.

Table 11. Paired t-test for the average values

Comparison	P-value	Remark
CEA-M vs. NCEA	0.011	<0.05
CEA-R vs. NCEA	0.001	<0.05

Comparison of NCEA and MILP Model

To assess the efficacy of NCEA, a comparison is made between the best solution obtained from the NCEA and the MILP model. In Table 12, the comparison results are provided.

Table 12. Comparison results of NCEA-J and MILP

Instances	MILP	NCEA
MFJSTA01	494*	494
MFJSTA02	477*	477
MFJSTA03	494*	494
MFJSTA04	579*	579
MFJSTA05	549*	568
MFJSTA06	665	675
MFJSTA07	904	904
MFJSTA08	914	914
MFJSTA09	1112	1159
MFJSTA10	1275	1296
MKTA 01	63*	66
MKTA 02	62*	62
MKTA 03	286	227
MKTA 04	89	91
MKTA 05	214	197
MKTA 06	-	93
MKTA 07	192	162
MKTA 08	553	539
MKTA 09	507	327
MKTA 10	-	245

Solution with * are proved to optimal by MILP model

The values in bold are the best

According to Table 12, for the small-scale instances MFJSTA01-10, NCEA performs worse than the MILP model in solving MFJSTA05, MFJSTA06, MFJSTA09 and MFJSTA10. For the other instances, the results of NCEA are comparable to the MILP model. For the large-scale instances MKTA01-10, except for MKTA01 and MKTA04, NCEA performs better than or equal to the MILP model. More importantly, for the instances MKTA06 and MKTA10, the MILP model fails to obtain any feasible solution within a reasonable time, while NCEA is able to obtain very good approximate solutions. Therefore, NCEA has a good performance in solving large-scale problems.

Comparison of NCEA and Other Algorithms

The NCEA is compared with other algorithms, including GA [56], VNS [57], ABC [58] and MBO [59]. The parameters of all algorithms are determined by DOE. Specifically, the parameters of IGA and VNS are the same as those in the respective literature. In ABC, the sizes of employed bees, the sizes of onlooker bees, the sizes of scout bees and the iteration of local search are 50, 100, 10 and 500 respectively. In MBO, the population size is set to 51, with 3 neighboring solutions, 1 shared neighboring solution, and 10 tours. In Table 13, the experimental results are provided.

Table 13. Comparison results of NCEA and other Algorithms

Instances	GA		VNS		ABC		MBO		NCEA
	Best	Average	Best	Average	Best	Average	Best	Average	Best	Average
MFJSTA01	494	494.9	494	495.8	494	515.4	494	512	494	494
MFJSTA02	490	492.3	490	492.6	493	493.3	477	492	477	486.2
MFJSTA03	504	513.7	494	515.7	532	545	513	531.2	494	505.4
MFJSTA04	601	607.4	605	615.4	626	642.3	610	622.2	579	589
MFJSTA05	549	570.7	549	580.4	582	605.5	581	601.9	568	579
MFJSTA06	667	679.4	672	699.8	736	749.3	687	714.6	675	677.2
MFJSTA07	935	967.6	940	981	1025	1052.9	972	1011.2	904	916.7
MFJSTA08	914	952.1	966	991.3	1008	1040.5	965	1012.8	914	919.2
MFJSTA09	1138	1163.9	1159	1213.8	1256	1302.9	1220	1239.6	1159	1161.1
MFJSTA10	1302	1319.8	1334	1356.9	1439	1479.5	1335	1403.6	1296	1305.7
MKTA01	65	65.3	65	66.5	69	70.2	65	66.6	66	66.8
MKTA02	62	64.1	64	65.5	66	68.8	64	65	62	63.2
MKTA03	227	227	227	227	227	227.9	227	227	227	227
MKTA04	93	94.3	96	98.3	104	105.8	97	98.4	91	91.9
MKTA05	197	198.4	199	202.8	216	221.2	210	211.4	197	197.5
MKTA06	92	92.9	97	99.9	109	110.6	99	102.2	93	95.7
MKTA07	166	167.3	167	175.1	194	195.9	183	185.1	162	165.8
MKTA08	539	539	539	539	541	543.8	539	539	539	539
MKTA09	328	330.1	337	342	360	366	353	358.9	327	331.1
MKTA10	248	252.1	265	272	292	296.3	287	292.7	245	247.7
Mean RPI	0.9	1.2	2.59	3.91	9.25	10.27	5.17	6.44	0.46	0.35

The values in bold are the best

From Table 13, it can be observed that NCEA outperforms or is comparable to the other four algorithms in most instances. Regarding both best values and average values, the Mean RPI values of NCEA-J are smaller than those of the other four algorithms, indicating the NCEA is an effective algorithm for resolving FJSP-T-A.

Table 14 provides the paired-t test results at a 95% confidence level for average values of Table 13. According to Table 14, the p-values of the paired t-test of GA vs. NCEA, VNS vs. NCEA, ABC vs. NCEA and MBO vs. NCEA are all less than 0.05. Therefore, it can be concluded that the NCEA statistically outperforms the GA, VNS, ABC and MBO.

Table 14. Paired t-test of different algorithms for the average values

Comparison	P-value	Remark
GA vs. NCEA	0.042	<0.05
VNS vs. NCEA	0.002	<0.05
ABC vs. NCEA	0.001	<0.05
MBO vs. NCEA	0.000	<0.05

Conclusions and Future Works

This thesis investigates the three-stage FJSP-T-A problem and designs a MILP model and NCEA with two decoding methods to minimize makespan. According to experimental findings, decoding method D-J performs better than D-P. Additionally, a comparison and evaluation of the NCEA and MILP models' efficacy are made. By the MILP model, small-scale instances can be optimally resolved, and effective solutions can be obtained using the NCEA. Specifically, the MILP model can find optimal solutions for 7 out of 20 instances within the timelimit. For small-scale instances, such as MFJSTA05 and MKTA01, the NCEA cannot obtain the optimal solutions. However, NCEA can obtain very good feasible solutions for large-scale instances, such as MKT05-10, for which the MILP model can only obtain very bad solutions or cannot obtain feasible solutions. Moreover, compared with the existing algorithms, namely GA, VNS, ABC and MBO, the proposed NCEA outperforms them for the FJSP-T-A problem in this paper.

Future research will take into account the FJSP-T-A customer demands and production process risks. Additionally, we'll look into production and transportation process uncertainties including machine malfunctions and AGV obstacles. We'll also take into account how much energy machinery uses during the manufacturing and shipping procedures. To find the best answers and provide a more effective algorithm for optimizing multi-stage scheduling problems, more research and optimization of the MILP model will be done.

Acknowledgements

Not applicable.

Author contributions

Shiming Yang wrote the manuscript; Leilei Meng was in charge of the whole trial; Ullah Saif, Chaoyong Zhang, Hongyan Song and Biao Zhang assisted with sampling and laboratory analyses. All authors read and approved the final manuscript.

Funding

Supported by National Natural Science Foundation of China (Grant Nos. 52205529 and 62303204), the Youth Innovation Team Program of Shandong Higher Education Institution (Grant No. 2023KJ206) and the Guangyue Youth Scholar Innovation Talent Program support received from Liaocheng University (Grant No. LCUGYTD2022-03).

Data availability

Not applicable.

Declarations

Competing Interests

The authors declare no competing financial interests.

References

[1] Meng, LL; Zhang, CY; Ren, YP et al. Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem. Computers & Industrial Engineering; 2020; 142, 106347.

[2] Meng, LL; Gao, KZ; Ren, YP et al. Novel MILP and CP models for distributed hybrid flowshop scheduling problem with sequence-dependent setup times. Swarm and Evolutionary Computation; 2022; 71, 101058.

[3] Wang, CY; Li, Y; Li, XY. Solving flexible job shop scheduling problem by a multi-swarm collaborative genetic algorithm. Journal of Systems Engineering and Electronics; 2021; 32, 2 pp. 261-271.

[4] Brandimarte, P. Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research; 1993; 41, 3 pp. 157-183.

[5] Meng, LL; Zhang, CY; Shao, XY et al. MILP models for energy-aware flexible job shop scheduling problem. Journal of Cleaner Production; 2019; 210, pp. 710-723.

[6] Zhang, GH; Zhang, LJ; Song, XH et al. A variable neighborhood search based genetic algorithm for flexible job shop scheduling problem. Cluster Computing; 2019; 22, 5 pp. 11561-11572.

[7] Tutumlu, B; Saraç, T. A MIP model and a hybrid genetic algorithm for flexible job-shop scheduling problem with job-splitting. Computers & Operations Research; 2023; 155, 4568087 106222.

[8] C özgüven, L özbakır, Y Yavuz. Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Applied Mathematical Modelling, 2010, 34(6): 1539-1548.

[9] A E Abd Elazeem, A E Mohamed, M Sayed, et al. Optimality of the flexible job shop scheduling problem. African Journal of Mathematics and Computer Science Research, 2011, 4: 321-328.

[10] Huang, LP; Su, R. An auto-MILP model for flexible job shop scheduling problem. IFAC-PapersOnLine; 2022; 55, 3 pp. 137-142.4626778

[11] Hansmann, RS; Rieger, T; Zimmermann, UT. Flexible job shop scheduling with blockages. Mathematical Methods of Operations Research; 2014; 79, 2 pp. 135-161.3191209

[12] S S Gran, I Ismail, T A Ajol, et al. Mixed integer programming model for flexible job-shop scheduling problem (FJSP) to minimize makespan and total machining time. 2015 International Conference on Computer, Communications, and Control Technology (I4CT), 2015: 413-417.

[13] Nouiri, M; Bekrar, A; Jemai, A et al. An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem. Journal of Intelligent Manufacturing; 2018; 29, pp. 603-615.

[14] Yazdani, M; Amiri, M; Zandieh, M. Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Systems with Applications; 2010; 37, 1 pp. 678-687.

[15] Ho, NB; Tay, JC; Lai, EMK. An effective architecture for learning and evolving flexible job-shop schedules. European Journal of Operational Research; 2007; 179, 2 pp. 316-333.

[16] Li, XY; Gao, L. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics; 2016; 174, pp. 93-110.

[17] Zhang, GH; Gao, L; Shi, Y. An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications; 2011; 38, 4 pp. 3563-3573.

[18] Shen, LJ; Dauzère-Pérès, S; Neufeld, JS. Solving the flexible job shop scheduling problem with sequence-dependent setup times. European Journal of Operational Research; 2018; 265, 2 pp. 503-516.3719385

[19] Fan, JX; Shen, WM; Gao, L et al. A hybrid jaya algorithm for solving flexible job shop scheduling problem considering multiple critical paths. Journal of Manufacturing Systems; 2021; 60, pp. 298-311.

[20] Zhang, GH; Shao, XY; Li, PG et al. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering; 2009; 56, 4 pp. 1309-1318.

[21] Shao, XY; Liu, WQ; Liu, Q et al. Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem. The International Journal of Advanced Manufacturing Technology; 2013; 67, 9 pp. 2885-2901.

[22] Kato, ERR; Aranha, GDDA; Tsunaki, RH. A new approach to solve the flexible job shop problem based on a hybrid particle swarm optimization and random-restart hill climbing. Computers & Industrial Engineering; 2018; 125, pp. 178-189.

[23] Gu, XL; Huang, M; Liang, X. A discrete particle swarm optimization algorithm with adaptive inertia weight for solving multiobjective flexible job-shop scheduling problem. IEEE Access; 2020; 8, pp. 33125-33136.

[24] Dai, M; Tang, DB; Giret, A et al. Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints. Robotics and Computer-Integrated Manufacturing; 2019; 59, pp. 143-157.

[25] Gao, KZ; Suganthan, PN; Pan, QK et al. Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling. Information Sciences; 2014; 289, pp. 76-90.3258460

[26] Yuan, M; Zheng, L; Huang, H et al. Research on flexible job shop scheduling problem with AGV using double DQN. Journal of Intelligent Manufacturing; 2025; 36, 1 pp. 509-535.

[27] Han, XQ; Cheng, WY; Meng, LL et al. A dual population collaborative genetic algorithm for solving flexible job shop scheduling problem with AGV. Swarm and Evolutionary Computation; 2024; 86, 101538.

[28] Y J Yao, Q H Liu, L Fu, et al. A novel mathematical model for the flexible job-shop scheduling problem with limited automated guided vehicles. IEEE Transactions on Automation Science and Engineering, 2024: 1-14.

[29] Hu, YF; Zhang, LP; Wang, Q et al. A matheuristic-based multi-objective evolutionary algorithm for flexible assembly jobs shop scheduling problem in cellular manufacture. Swarm and Evolutionary Computation; 2024; 87, 101549.

[30] Yang, SM; Meng, LL; Ullah, S et al. MILP modeling and optimization of multi-objective three-stage flexible job shop scheduling problem with assembly and AGV transportation. IEEE Access; 2025; 13, pp. 25369-25386.

[31] Xin, B; Lu, S; Wang, Q et al. Simultaneous scheduling of processing machines and automated guided vehicles via a multi-view modeling-based hybrid algorithm. IEEE Transactions on Automation Science and Engineering; 2024; 21, 3 pp. 4753-4767.

[32] Y M Luo, Q Zhang, L Lin. A cooprative hybrid evolutionary algorithm for flexible scheduling with AGVs. 2023 International Conference on Sensing, Measurement & Data Analytics in the era of Artificial Intelligence (ICSMD), 2023: 1-7.

[33] Zhang, M; Wang, L; Qiu, FS et al. Dynamic scheduling for flexible job shop with insufficient transportation resources via graph neural network and deep reinforcement learning. Computers & Industrial Engineering; 2023; 186, 109718.

[34] Pan, ZX; Wang, L; Zheng, J et al. A learning-based multipopulation evolutionary optimization for flexible job shop scheduling problem with finite transportation resources. IEEE Transactions on Evolutionary Computation; 2023; 27, 6 pp. 1590-1603.

[35] Wen, XY; Fu, YZ; Yang, WC et al. An effective hybrid algorithm for joint scheduling of machines and AGVs in flexible job shop. Measurement and Control; 2023; 56, 9–10 pp. 1582-1598.

[36] Zhang, FY; Li, R; Gong, WY. Deep reinforcement learning-based memetic algorithm for energy-aware flexible job shop scheduling with multi-AGV. Computers & Industrial Engineering; 2024; 189, 109917.

[37] Lin, WH; Deng, QW; Han, WW et al. An effective algorithm for flexible assembly job-shop scheduling with tight job constraints. International Transactions in Operational Research; 2022; 29, 1 pp. 496-525.4305086

[38] Fattahi, P; Bagheri, RN; Daneshamooz, F. Solving flexible job shop scheduling problem with an assembly stage and sequence dependent setup time. Industrial Engineering & Management Sharif; 2019; 34, 1 pp. 119-131.

[39] Ren, WB; Wen, JQ; Yan, Y et al. Multi-objective optimisation for energy-aware flexible job-shop scheduling problem with assembly operations. International Journal of Production Research; 2021; 59, 23 pp. 7216-7231.

[40] Z X Pan, L Wang, J J Wang, et al. Distributed energy-efficient flexible manufacturing with assembly and transportation: a knowledge-based bi-hierarchical optimization approach. IEEE Transactions on Automation Science and Engineering, 2024: 1-17.

[41] Janzen, DH. When is it coevolution. Evolution; 1980; 34, 3 pp. 611-612.

[42] Hillis, WD. Co-evolving parasites improve simulated evolution as an optimization procedure. Physica D: Nonlinear Phenomena; 1990; 42, 1 pp. 228-234.

[43] Potter, MA; De Jong, KA. A cooperative coevolutionary approach to function optimization. Lecture Notes in Computer Science; 1994; 866, 7 pp. 249-257.

[44] C D Rosin, R K Belew. Methods for competitive co-evolution: finding opponents worth beating. Proceedings of International Conference on Genetic Algortihms, 1995: 373-381.

[45] El Imrani, A; Bouroumi, A; Limouri, M et al. A coevolutionary genetic algorithm using fuzzy clustering. Intelligent Data Analysis; 2000; 4, pp. 183-193.

[46] Filipiak, S. Classifier system and co-evolutionary hybrid approach to restoration service of electric power distribution networks. Journal of Electrical Engineering and Technology; 2012; 7, 3 pp. 288-296.

[47] Li, XD; Yao, X. Cooperatively coevolving particle swarms for large scale optimization. IEEE Transactions on Evolutionary Computation; 2012; 16, 2 pp. 210-224.

[48] Fabris, F; Krohling, RA. A co-evolutionary differential evolution algorithm for solving min–max optimization problems implemented on GPU using c-CUDA. Expert Systems with Applications; 2012; 39, 12 pp. 10324-10333.

[49] Pan, QK. An effective co-evolutionary artificial bee colony algorithm for steelmaking-continuous casting scheduling. European Journal of Operational Research; 2016; 250, 3 pp. 702-714.3436507

[50] Ghasemishabankareh, B; Li, X; Ozlen, M. Cooperative coevolutionary differential evolution with improved augmented lagrangian to solve constrained optimisation problems. Information Sciences; 2016; 369, pp. 441-456.3539445

[51] Hiew, BY; Tan, SC; Lim, WS. A double-elimination-tournament-based competitive co-evolutionary artificial neural network classifier. Neurocomputing; 2017; 249, pp. 345-356.

[52] Sang, H; Duan, P; Li, J. An effective invasive weed optimization algorithm for scheduling semiconductor final testing problem. Swarm and Evolutionary Computation; 2018; 38, pp. 42-53.

[53] Lei, D. Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling. Applied Soft Computing; 2012; 12, 8 pp. 2237-2245.

[54] Meng, LL; Zhang, CY; Zhang, B et al. MILP modeling and optimization of multi-objective flexible job shop scheduling problem with controllable processing times. Swarm and Evolutionary Computation; 2023; 82, 101374.

[55] Meng, LL; Duan, P; Gao, KZ et al. MIP modeling of energy-conscious FJSP and its extended problems:from simplicity to complexity. Expert Systems with Applications; 2024; 241, 122594.

[56] Meng, LL; Cheng, WY; Zhang, B et al. An improved genetic algorithm for solving the multi-AGV flexible job shop scheduling problem. Sensors; 2023; 23, 8 3815.

[57] Meng, LL; Zhang, CY; Zhang, B et al. Mathematical modeling and optimization of energy-conscious flexible job shop scheduling problem with worker flexibility. IEEE Access; 2019; 7, pp. 68043-68059.

[58] Gao, KZ; Suganthan, PN; Chua, TJ et al. A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion. Expert Systems with Applications; 2015; 42, 21 pp. 7652-7663.

[59] Li, HC; Cao, BQ; Zhu, HD. A variable neighborhood migrating birds optimization algorithm for flexible job shop scheduling. International Journal of Performability Engineering; 2017; 13, 7 pp. 1020-1029.