Two-stage iterated greedy algorithm for distributed flexible assembly permutation flowshop scheduling problems with sequence-dependent setup times

1.   Introduction

With the continuous development of the economic globalization and the gradual globalization of the manufacturing industry, manufacturing enterprises are encountering unprecedented competition ^[1,2]. To improve their competitiveness, the traditional single-factory production mode must be transformed into a multi-factory production mode ^[3,4]. Enterprises can coordinate and control factories in different places to improve production efficiency and stability, reduce costs, and enhance competitiveness ^[5]. Scheduling is an important component of the manufacturing system and directly affects the efficiency and competitiveness of enterprises ^[6,7]. An efficient scheduling method can achieve efficiency improvement, energy savings, consumption reduction, emission reduction, and cost reduction in the enterprise's production and manufacturing process ^[8,9].

Distributed manufacturing system scheduling has received considerable attention ^[10,11,12]. The first study ^[13] on the distributed permutation flowshop scheduling problem (DPFSP) was conducted in 2010. In 2013, a DPFSP with a single assembly machine was observed; it is called the distributed assembly permutation flowshop scheduling problem (DAPFSP) ^[14]. However, the production efficiency of a single assembly machine is not high, and this has become a bottleneck in the production system in some cases. In our previous work ^[15], production efficiency was improved by using an effective scheduling scheme. In this study, another scheme for adding more assembly machines is studied. To solve the aforementioned bottleneck, companies typically use multiple identical assembly machines. In this study, a distributed flexible assembly permutation flowshop scheduling problem (DFAPFSP) is considered, in which multiple assembly machines replace the single machine assembly in the DAPFSP. Compared with the DPFSP and DAPFSP, the DFAPFSP is more complex because it must generate a plan composed of a production sub-schedule for jobs and assembly sub-schedule for products. Our contributions are summarized as follows: (1)we establish a mathematical model for the DFAPFSP with sequence-dependent setup times, (2) a two-stage iterated greedy (TSIG) algorithm for solving DFAPFP is proposed, in which the first stage adjusts the job sequence and the second stage optimizes the product sequence, (3)we redesign the destruction, reconstruction, and local search algorithms based on problem characteristics in two stages, and (4) we verify the performance by using experimental statistics and analysis.

The remainder of this paper is organized as follows. Section 2 presents a review of related studies on the DPFSP, DAPFSP, and DFAPFSP. Section 3 introduces the DFAPFSP with makespan criterion and provides an illustrative example. Section 4 presents the proposed TSIG algorithm with its detailed design. Section 5 describes the experimental calibration of the TSIG and verifies the new mathematical model presented in Section 3. Section 6 details the computational results and comparisons with state-of-the-art algorithms. Finally, Section 7 provides concluding remarks and suggestions for future work.

2.   Literature review

Recently, the DPFSP has been receiving more research attention ^[13]. The DPFSP is a complex scheduling problem that aims to determine which factory each job is assigned to and the order of jobs in each factory. Various metaheuristics have been proposed to solve the DPFSP, including the hybrid immune algorithm ^[16], tabu algorithm ^[17], iterated greedy (IG) ^{[18,19,20,21]}, scatter search ^[22], chemical reaction optimization ^[23], discrete artificial bee colony ^[24,25], and discrete fruit fly optimization ^[26]. In addition, numerous variants of the DPFSP have been proposed, such as distributed blocking flowshop scheduling ^[27], distributed no-wait flowshops ^[28,29], distributed flexible job shop scheduling ^[30,31], green scheduling for the DPFSP ^[5], inverse scheduling for the DPFSP ^[32], the bi-objective DPFSP ^[33], and the DPFSP with sequence-dependent setup times ^[26]. Several review papers have systematically summarized the DPFSP ^[10,11].

Among the many variants of the DPFSP, the DAPFSP is the most important and can be considered as a combination of the DPFSP and assembly scheduling problem. The DAPFSP has also received considerable attention. Hatami et al. published the first paper on the DAPFSP ^[14]. Wang et al. ^[34] proposed a memetic algorithm for solving the DAPFSP by combining the estimation of distribution algorithm and local search. Deng et al. ^[35] proposed a mixed-integer linear programming (MILP) model for the DAPFSP. Subsequently, a competitive memetic algorithm was proposed to solve the DAPFSP. Researchers have proposed many metaheuristics to solve the DAPFSP, including the backtracking search hyperheuristic algorithm ^[36] that designs ten simple and effective heuristic rules to construct a set of low-level heuristic (LLH) rules, and uses the backtracking search algorithm as a high-level strategy to manipulate the LLH rules to operate on the solution space, the hybrid biogeography-based optimization algorithm ^[37] that simulates the migration, mutation, and selection processes of species in different habitats to achieve global optimal solution search for complex problems, three-dimensional matrix-cube-based estimation of distribution algorithm ^[38] that describes the distribution pattern of excellent solutions by establishing a probability model, and generates a new population based on the model sampling to replace the crossover and mutation operations of traditional genetic algorithms, and biased-randomized iterated local search ^[39] which is a metaheuristic framework that iteratively applies local search, perturbation, and evaluation of the solution against the acceptance criterion.

In these previous studies, the DAPFSP was explored by minimizing the makespan criterion, whereas in following studies, other optimization objectives were investigated. Sang et al. ^[40] presented three variants of the discrete invasive weed optimization for the DAPFSP with total flowtime criterion. Huang et al. ^[41] also studied the DAPFSP with total flowtime criterion based on an IG algorithm. Li et al. ^[15] focused on the DAPFSP with total tardiness criterion. Based on the DAPFSP research, some researchers have added conditions depending on the production reality, such as blocking ^[42,43], no-idle ^[44], sequence-dependent setup times ^[45], no-wait ^[46], hybrid flowshop ^[47], fuzzy processing time ^[48], and three stages (the production, transportation, and assembly stages) ^[49]. Some researchers have focused on the multi-objective optimization of the DAPFSP. Zhao et al. ^[50] proposed a brainstorm optimization approach for solving the multi-objective energy-efficient distributed assembly no-wait flowshop scheduling problem. Zhang et al. ^[51] studied a dual-objective energy-efficient DFAPFSP with minimum makespan and energy consumption. Huang et al. ^[52] presented a two-phase evolutionary algorithm for the DAPFSP with the total flowtime and total tardiness criteria.

Limited research has been conducted on the DFAPFSP. Zhang et al. ^[53] studied the DFAPFSP with a sequence-independent setup time which means that the preparation time required to switch between different jobs does not depend on the order of the jobs. They proposed a constructive heuristic (two-phase heuristic search, TPHS) and two hybrid metaheuristics (hybrid variable neighborhood search, HVNS, and hybrid particle swarm optimization, HPSO). Numerical experiments showed that both the TPHS and metaheuristics can obtain a reliable solution that matches the running time. Ying et al. ^[54] also addressed the DFAPFSP with a sequence-independent setup time to minimize the completion time. A MILP model of the DFAPFSP was proposed for the first time. Subsequently, constructive heuristics and customized metaheuristics IG_PD (iterated greedy with product destruction mechanism) were proposed to solve the DFAPFSP. Extensive computational experiments showed that the proposed IG_PD has been the best approach to date.

Zhang et al. ^[55] proposed a memetic algorithm with meta-Lamarckian learning and simplex search for the DFAPFSP. Statistical results showed that the proposed algorithm was significantly better than the existing algorithms. Yang and Xu ^[56] studied the DFAPFSP with batch delivery, which is more complicated because of transportation costs. This analysis and summary of previous studies indicate that many studies have been conducted on the DPFSP and DAPFSP, but limited attention has been paid to the DFAPFSP.

The IG algorithm has achieved excellent performance in job shop scheduling ^[57]. In our recent three studies ^[15,18], we used the IG algorithm to solve distributed flowshop scheduling problems and compared it with state-of-the-art algorithms. The algorithms compared included the modified IG, cloud-theory-based IG, scatter search, bounded-search IG, evolutionary, discrete artificial bee colony, iterated local search, hybrid discrete invasive weed optimization, biogeography-based optimization, and competitive memetic algorithms. The results showed that the IG algorithm outperformed the others. Therefore, in this study, we use the IG algorithm to solve the DFAPFSP with makespan criterion and sequence-dependent setup times which means preparation time required to switch between different jobs depends on the order of the jobs, which is expected to yield better results.

3.   Problem description

The mathematical model of the DFAPFSP is described as follows. Two stages are considered: production and assembly; n jobs are processed in the first stage and assembled into t products in the second stage. The first stage involves F production factories. All production factories are identical. Each production factory is a flowshop composed of m machines (M₁, M₂, M₃, …, M_m). The processing time of job j on machine i is the same for all production factories. All jobs are available at initialization.

After all jobs for a product are completed, they can be assembled into a product on the assembly machine (AM) in the second stage. The second stage involves q assembly factories. Each assembly factory has only one assembly machine. Therefore, in the following, the assembly factory and assembly machine are equivalent. The performances of all assembly machines are the same. Assembly can be conducted in any assembly factory. n, m, F, q, and t are known in advance.

Equipment failures, maintenance, and other interruptions are not considered. Operations cannot be transferred to other machines or factories during the processing. A production (assembly) machine can process only one job (product) at a time, and a job (product) can be processed on only one production (assembly) machine at a time. The job (product) operation of each production (assembly) machine cannot be interrupted until it is completed. Each machine has a sequence-dependent setup time to prepare for the processing of each job. Table 1 lists the indices, parameters, and decision variables used.

The key parameters and variables are emphasized as follows. If job j is a part of product s, then g_js = 1. The processing time for job j on machine i and the processing time for product s on the assembly machine are represented as p_ji and pp_s, respectively. The setup time between jobs k and j on machine i and the setup time between products l and s on the assembly machine are S_kji and SA_ls, respectively. There are four binary variables, namely X_{k, j}, Y_{j, f}, XA_{l, s}, and YA_{l, a}. If job j is processed after job k, then X_{k, j} = 1; if job j is processed in factory f, then Y_{j, f} = 1; if product l is processed after product s, then XA_{l, s} = 1; if product l is processed in assembly factory a, then YA_{l, a} = 1. Otherwise, these four binary variables are 0. The completion time of job j on machine i and the completion time of product s on the assembly machine are denoted as C_ji and CA_s.

3.1.   MILP models

The MILP model for the DFAPFSP is extended from the models proposed by Hatami et al. ^[14] and Naderi et al. ^[13]. Equation (1) is our optimization function.

Subject to

Note that machine 0 is a dummy and that C_j0 = 0, ∀ j. Constraint set implies that each job is processed in only one factory. Constraint set indicates that a job cannot be processed on two machines simultaneously and the relationship between the completion time of a job on two adjacent machines. Constraint sets and are dichotomous pairs of constraints related to each possible job pair. If job k is processed after job j in factory f, constraint (4) provides the relationship between the completion times of jobs k and j. On the contrary, if job k is processed before job j in factory f, constraint (5) describes the relationship between the completion times of jobs k and j. Similarly, constraint sets and are dichotomous pairs of constraints related to each possible product pair. Constraint implies that each product can be assembled only after all its components are completed in the first stage. Constraint set defines the makespan, and constraints – define the value range of the variables.

3.2.   Illustrative example

We consider an example in which n = 6, F = 3, m = 2, q = 2, and t = 3. Jobs 1 and 6, 2 and 3, and 4 and 5 are assembled into products 1, 2, and 3, respectively. Other parameters, such as the processing and setup times, are listed in Tables 2–5. We consider a scheduling scheme as follows: Jobs 1 and 3, 4 and 6, and 5 and 2 are processed sequentially in factories 1, 2, and 3, respectively. In the assembly stage, product 3 is processed on assembly machine 1, and products 1 and 2 are processed on assembly machine 2. Figure 1 shows a Gantt chart. As shown in Figure 1, the completion time of this scheduling scheme is 163 time units.

4.   TSIG algorithm for the DFAPFSP

The IG algorithm is a fast and effective intelligent optimization algorithm with a simple structure and few parameters. The IG algorithm destroys and reconstructs the current solution through iterations to produce a series of solutions. The new solution is updated by using an acceptance criterion. The IG algorithm has been applied in many fields, particularly for the flowshop scheduling problem, which shows good performance.

4.1.   Solution representation and TSIG framework

The representation of the solutions is important. A reasonable representation of the solutions can help the algorithms obtain better results. The solutions of recent studies ^[53,54], which are similar to this study, are divided into two parts. The first part represents the production factory allocation of jobs in the production stage and processing sequence in each factory, and the second part represents the assembly factory allocation of products and processing sequence of products in the assembly stage. However, the second part can be obtained from the first part using a greedy algorithm ^[53,54]. Only the first part is decisive. We studied this representation and determined that it leads to local optimization for the DFAPFSP with sequence-dependent setup times. As shown in Figure 2(a), products 1 and 2 are arranged for processing in the assembly factories. Figure 2(b) shows the solution obtained according to the method in ^[53,54]. That is, a better solution exists when the positions of P₁ and P₂ change, as shown in Figure 2(c). The reason for this result is that the setup time of the concerned problem is sequence-dependent.

The solution representation is the same as in the literature ^[53,54]. The difference is that the second and first halves are independent of one another. A solution can be expressed as

indicates the job allocation in the production stage and

indicates the product allocation in the assembly stage. The job sequence of factory f is

where ${n}_{f}$ is the number of jobs in factory f. Similarly, the product sequence of assembly factory a is

Therefore, the scheduling scheme of the example in Section 3.2 is

The DFAPFSP is complex and cannot be handled by using a one-stage method. The first stage outputs products with release times. When multiple jobs in the production stage are extracted, they cannot be reinserted because the intermediate solution generated in the first stage cannot be evaluated. If the job production plan in the first stage is determined, the problem becomes a multi-parallel machine processing problem with release time, which is equivalent to the multi-traveling salesman problem and is NP hard. The approaches used in the original studies ^[53,54] can obtain better solutions under the condition of sequence-independent setup times. This problem requires further study in the context of sequence-dependent setup times. Based on the problem characteristics, we designed the TSIG algorithm. Figure 3 shows the TSIG algorithm framework.

4.2.   Initial solution

A good initial solution significantly impacts the performance of the algorithm. Heuristic H₁₁ was proposed in the first study on the DAPFSP ^[14]. The latest studies ^[15,40] also show that the H₁₁ algorithm has a good performance. Therefore, we designed a new heuristic based on H₁₁ and called it Improved H₁₁ (IH₁₁), as shown in Algorithm 1. First, a temporary sequence of products is obtained (Line 1). Then, a sequence of jobs for each product is obtained (Lines 2.1 and 2.2). The sequence (${\pi }_{T}$) of all jobs is obtained by combining the sequences of each product (Line 3). Each job in ${\pi }_{T}$ is inserted into the optimal position in the product factories in sequence to minimize the makespan (Lines 4–6). Line 7 calculates the release time for each product. The product sequence (Line 8) is obtained in ascending order of the release time. Finally, the products are successively inserted into the assembly factory to obtain the best makespan. In Algorithm 1, the complexity of the code in Lines 1–3 is $\mathrm{O}\left({t}^{2}\right)$, $\mathrm{O}\left({n}^{2}\right)$, and $\mathrm{O}\left(1\right)$, respectively. The complexity of the code in Lines 4–6 is

The complexity of the code in Lines 7–9 is $\mathrm{O}\left(t\right)$, $\mathrm{O}\left({t}^{2}\right)$, and $\mathrm{O}\left({t}^{2}\right)$, respectively. Finally, the complexity of Algorithm 1 is

4.3.   Destruction procedure for the first stage

Algorithm 2 presents the pseudocode for the destruction procedure for the first stage. It randomly selects a product and extracts all jobs belonging to the product.

4.4.   Construction procedure for the first stage

The construction procedure for the first stage returns all jobs in $J$ to $\lambda$, as shown in Algorithm 3. The operations are as follows: Randomly select a job in $J$ and place it in the best position in $\lambda$. In the second stage, an important parameter is the release time of the products. After all jobs belonging to a product are processed, the product can be processed in the second stage; the shorter the release time of a product, the better. However, the release times of many products are difficult to evaluate. In the TSIG algorithm, a greedy method (Lines 5–8) is used to obtain $\xi$ for the second stage. The final completion time is then obtained and used to measure the fitness of each position.

4.5.   Local search for the first stage

The basic operation of the local search for the first stage (LocalSearch1 in Algorithm 4) is as follows: Randomly select a job, extract the job from the current position, insert the extracted job into a new random position, and calculate the makespan using the same greedy method (Lines 5–7 in Algorithm 4) as described in Subsection 4.4. If a better solution is obtained, then the original solution is replaced. The basic operation is performed $ite{r}_{L}S$ times, and $\mathrm{C}\left(\mathrm{\lambda }, \mathrm{\xi }\right)$ is the makespan of a solution $< \lambda, \xi >$.

4.6.   Destruction procedure for the second stage

Note that the problem considered in the second stage is the parallel machine problem with release time. The release time is determined by the production scheduling of the first stage. The destruction procedure for the second stage (Destruction2 in Algorithm 5) involves randomly selecting d products and extracting them from ξ.

4.7.   Construction procedure for the second stage

In the second stage, the construction procedure inserts the extracted product at the optimal position of the assembly sequence. Algorithm 6 presents the pseudocode.

4.8.   Local search for the second stage

In the second stage, a local search attempts to extract a product and insert it into other positions to improve the performance of the solution. To balance efficiency and performance, when half of all products have been tested and have not been improved, the local search stops. Algorithm 7 presents the pseudocode of the local search for the second stage.

4.9.   Acceptance criterion

After the destruction, construction, and local search procedures in the two stages, a new solution is obtained. This new solution may worsen or improve. Generally, an acceptance criterion allows the worse solution to be accepted with a certain probability, which can help the IG algorithm exit the local optima to ensure a continuous evolution of the IG algorithm. Researchers have designed various acceptance criteria ^[58]. However, in our recent study ^[15], we concluded that rejecting a worse solution can achieve a better final result in some cases. We designed a new acceptance criterion, as shown in Algorithm 8, based on the acceptance criteria in ^[54] and ^[15]. If the new solution is better than the current solution, it replaces the current solution. If it is also better than the current optimal solution (${sol}^{*}$), it replaces the current optimal solution. Parameter β is used in the new acceptance criterion. If β equals zero, then the worse solution is not accepted. If β is larger than 0, the worse solution is accepted with a probability of ${e}^{-RPD}$, where $RPD = \left(C\left(so{l}^{{'}}\right)-C\left(sol\right)\right)/C\left(sol\right)\times 100$.

4.10.   Procedure of the proposed TSIG

Algorithm 9 presents the complete implementation of the TSIG algorithm. First, heuristic ${IH}_{11}$ is used to obtain an initial solution, which is temporarily considered the optimal solution. The TSIG then enters the loop operation and exits the loop when the termination conditions are satisfied. In the loop, the following operations are performed on the temporary solution ($so{l}^{\mathrm{{'}}}$): Destruction1, Construction1, LocalSearch1, Destruction2, Construction2, LocalSearch2, and AcceptanceCriterion. Finally, the results are returned.

5.   Experimental calibration and mathematical model verification

The parameters of the proposed TSIG algorithm were adjusted to enable the TSIG algorithm to show its optimal performance. The TSIG algorithm has four parameters: d, iter_ LS, iter_S2, and β. For these four parameters, different possible values were determined based on the relevant literature. In the literature ^[53,54], the optimal settings of parameters may differ for different problem scales. For small-scale instances, the possible values of d are 1, 3, and 5; that of iter_LS, 0, 10, and 30; iter_S2, 1, 3, and 5; and β, 0, and 1. These factors lead to a total of 3×3×3×2 = 54 different configurations for the TSIG algorithm (small-scale). For large-scale instances, the only difference is the possible values of iter_S2, which are 0, 1, and 3. Similarly, the TSIG algorithm has 54 different configurations for large-scale instances.

The method in ^[53,54] was used to generate test instances. The calibration experiments involved two types of test instances: large- and small-scale. Table 6 lists their parameters. The processing times for each job and product are a random number between 1 and 99. The setup time for all machines is uniformly generated from ^[1,20]. Small-scale data involve 3×2×2×2×3 = 72 combinations, and large-scale data involve 2×2×2×2×2 = 32 combinations. Each combination produces an instance. Thus, 104 numerical instances are obtained.

All algorithms were coded using C++, and the IDE was MS VS 2017. We ran configurations on an Intel (R) Core (TM) i7-4790 CPU@3.60 GHz with 16.00 GB of RAM on a Windows 10 operating system and stopped them when the termination criterion of the maximum elapsed CPU time of 6×n×m ms was met, where n and m are the number of jobs and machines, respectively. The algorithm under each configuration was run independently five times. Thus, 72×54×5 = 19,440 small- and 32×54×5 = 8640 large-scale numerical results were generated.

We measured the relative percentage increase (RPI) from the results as follows:

where C is the makespan obtained in each configuration and instance, and C* is the best makespan obtained for that instance among the 54×5 = 270 results. Considering all instances, we obtained 270×104 = 28,080 RPI results for the calibration of the TSIG algorithm.

The mean plots with 95% Tukey honest significant difference (HSD) confidence intervals (shown in Figures 4 and 5) were used to analyze the best values of the parameters. From the results of the experimental analysis shown in Figure 4, we can easily obtain the following parameter settings for the small-scale instances: d = 3, iter_LS = 10, iter_S2 = 3, and β = 0. Figure 5 shows the best parameter configuration for large-scale datasets: d = 3, iter_LS = 10, iter_S2 = 1, and β = 0.

The mathematical model in Section 3.1 is implemented using CPLEX to solve small-scale instances. For the most complex instance in which n, m, F, t, and q are 30, 3, 3, 8, and 4, respectively, the solver does not end running for 2 hours. Then, we use CPLEX to solve 72 small-scale instances and get results in 600 s. A solution for each instance is obtained at the set termination time. For the briefest purposes, detailed results are not listed, which can be obtained through our email. The mathematical model in Section 3.1 is verified to be correct, but time-consuming.

6.   Computational evaluation

The TSIG algorithm was compared with state-of-the-art algorithms, namely, HVSN ^[53], HPSO ^[53], and IG_PD ^[54], which are similar to our research topic. Table 7 lists the parameters of the compared algorithms, which are sourced from their original papers. The programming and running environments of all algorithms were the same as those mentioned in Section 5. To show the performance of all algorithms panoramically, we set three algorithm termination criteria:

where v was tested at three values: 20, 40, and 60. In addition, the experimental dataset was the same as that described in Section 5. The only difference was that each combination produced five numerical instances. Thus, we obtained

instances (including 360 small- and 160 large-scale instances). Each algorithm was run independently 10 times for each instance.

Tables 8–13 list the average RPI (ARPI) values grouped by factory, production machine, job, assembly machine, and product. Tables 8 and 9 present the ARPI values of all competitive algorithms when the termination time was 20mn ms. The TSIG algorithm is the best for small-scale instances, followed by IGPD, HPSO, and HVNS. For large-scale instances, for m = 6, the performance of TSIG ranks second but is similar to that of IG_PD. In other large-scale instances, TSIG is optimal. Therefore, in large-scale instances, TSIG is the best, followed by IG_PD, HPSO, and finally HVNS.

A multifactor analysis of variance (ANOVA) was conducted to determine whether the differences observed in Tables 8 and 9 were significant. The types of algorithms, number of jobs, number of production machines, number of factories, number of assembly machines, and number of products are considered factors.

Figure 6 shows the mean plots of the types of algorithms, interactions of the algorithms and number of factories, interactions of the algorithms and number of jobs, interactions of the algorithms and number of production machines, interactions of the algorithms and number of assembly machines, and interactions of the algorithms and number of products. We employed a 95% confidence level and the Tukey HSD confidence interval.

Figure 6 shows that the total ARPI values generated by the four algorithms are statistically different. From best to worst, the algorithms are as follows: TSIG, IG_PD, HPSO, and HVNS. When the scale of the DFAPFSP is small (f = 2, 3; n = 20, 24, 30; m = 2, 3; q = 2, 3, 4; t = 6, 8), each algorithm can obtain a better solution. However, the TSIG algorithm is the best. When the scale of the DFAPFSP is large (f = 5, 10; n = 100,200; m = 6, 8; q = 6, 8; t = 30, 40), the performance differences of the four algorithms improve. However, the proposed TSIG algorithm yields the best results.

Tables 10–13 show the ARPI values of all competitive algorithms at 40mn and 60mn ms, respectively. Figures 7 and 8 show the mean plots, interactions, and 95.0% Tukey HSD intervals at t = 40mn ms and those at t = 60mn ms, respectively. When the scale of the DFAPFSP is small, the difference between all algorithms is large. When the scale of the DFAPFSP becomes larger, the problem becomes more difficult, as well as obtaining the optimal solution. The TSIG algorithm is the best except for n = 100 or m = 6; and when n = 100 or m = 6, it is second-best and performs almost as well as the best. The ranking of the competitive algorithms is the same as that of 20mn ms, which can be concluded from these tables and figures.

The experimental results show that TSIG performs better than HVNS, HPSO, and IG_PD. This should be due to the following reasons. On the one hand, as mentioned earlier, the IG algorithm has shown excellent performance in solving combinatorial optimization problems, especially in job shop scheduling problems. On the other hand, the IG algorithm has been improved based on the characteristics of the problem to be solved. For example, two parts are used in the representation of the solution, representing the scheduling scheme for the production stage and the assembly stage, respectively; the destruction, reconstruction, and local search algorithms are redesigned based on the characteristics of the production stage and the assembly stage.

7.   Conclusions

This study addressed the DFAPFSP, which involves multiple assembly machines. An efficient scheduling algorithm is crucial for the DFAPFSP. However, few studies have been conducted on this topic. First, we established a new mathematical model for the DFAPFSP with sequence-dependent setup times and makespan criterion. The TSIG algorithm was proposed to solve the DFAPFSP based on problem-specific knowledge. All IG algorithm components were redesigned. Several experiments were conducted to verify that the TSIG algorithm is superior to existing algorithms.

The DFAPFSP is a new research topic, with only a few studies being conducted. In fact, the DFAPFSP may face more complex situations in actual production, such as dynamic order changes and uncertainties of machine failures. This study does not account for these dynamic uncertainties, constituting a primary limitation of the current work. Significant research efforts remain necessary to address these gaps. Future investigations could explore alternative optimization objectives, such as minimizing total flow time or reducing total tardiness. The energy-efficient DFAPFSP should also be investigated for optimizing multiple objectives simultaneously. Finally, the DFAPFSP can be integrated with the transportation process for research purposes.

Author contributions

Yuanzhen Li: Software, Investigation, Validation, Conceptualization, Methodology, Writing-original draft preparation; Leilei Meng: Writing-review & editing, Validation, Formal analysis; Biao Zhang: Data Curation, Investigation, Visualization. All authors have read and approved the final version of the manuscript for publication.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This research is partially supported by the National Natural Science Foundation of China 52205529, and the Natural Science Foundation of Shandong Province (ZR2021QE195).

Conflict of interest

The authors declare that there is no conflict of interest.