Sage Journals: Discover world-class research

Abstract

The distributed assembly permutation flowshop scheduling problem (DAPFSP) has become a significant research topic in recent years. However, most existing studies rely on approximation search algorithms, such as metaheuristic algorithms, to address the high complexity of DAPFSP. To overcome the limitations of instability and poor search capability in these algorithms, this study proposes a hybrid biogeography-based optimization (HBBO) algorithm to solve DAPFSP with the objective of minimizing makespan. Two factory allocation methods are employed to generate initial solutions, reducing the possibility of redundant solutions. A crossover operator is utilized to improve the quality of partial solutions during the global search phase of HBBO. Additionally, four migration rate models are comprehensively tested as alternatives to commonly used models. Two neighborhood search methods are incorporated as the local search strategy for HBBO. The Metropolis acceptance criterion is employed to retain some inferior solutions, thereby enhancing solution diversity and preventing the algorithm from getting trapped in local optima. A series of experiments are conducted, and the computational results demonstrate that HBBO delivers promising results for DAPFSP.

Keywords

Distributed assembly permutation flowshop scheduling problem hybrid biogeography-based optimization factory allocation methods migration rate models metropolis acceptance criterion

1. Introduction

With the continuous development of economic globalization, applications such as the Internet of everything, 5G and e-commerce are constantly being explored. This development is expected to increase daily demand for the product. In response, enterprises are actively seeking the most efficient production methods to save time, costs, and space, ultimately maximizing profits. The advent of distributed manufacturing systems (DMS) offers a comprehensive solution to this challenge. The application of DMS effectively manages intricate production decisions within the supply chain system, aiming to reduce production costs, shorten response times, increase production flexibility, improve product quality, and minimize management risks (Renna, 2012; Jia, 2002). Efficiently production planning necessitates the integration of production schedules from each member of the supply chain to optimize the performance of the DMS (Rossit et al., 2019). The distributed scheduling problem (DSP) focuses on the collaboration between multiple production plants in manufacturing and processing operations (Garey et al., 1976). The introduction of DSP contributes significantly to enhancing the production efficiency of factories, attracting growing attention from researchers (Cheng et al., 2019; Lin & Ying, 2013; Pourhejazy et al., 2021; Ying & Lin, 2017).

Distributed assembly permutation flowshop scheduling problem (DAPFSP) is an important branch of DSP. DAPFSP is widely used in gear processing (Gokhale & Mathirajan, 2011), bearing processing (Wang et al., 2024), and semiconductor wafer production (Wenyou Jia & Li, 2015). Taking the wafer manufacturing process as an example, Figure 1 is the flowchart of the wafer production process. This is a typical DAPFSP production mode. Each factory has a complete production chain. Each production chain consists of four different machines, which perform the following processes: cleaning to remove wafer surface contamination, applying the photoresist layer for subsequent wafer exposure, exposing the photoresist with ultraviolet light to define the circuit pattern, and removing the unexposed photoresist from the wafer to form the pattern. Wafers of different specifications can be processed simultaneously. Once the wafers have completed all the processes, they can be loaded onto the assembly line for assembly and inspection. The emergence of multi-factories has made the product manufacturing process more flexible, significantly reducing time costs and energy consumption.

Figure 1.

Flowchart of the Wafer Production Process.

DAPFSP serves as an extension of the permutation flow shop scheduling problem (PFSP). PFSP is proven to be an NP-Complete problem when involving more than three machines (Garey et al., 1976). Consequently, DAPFSP inherits this complexity and is also established as an NP-Complete problem. It becomes unrealistic to pursue the optimal solution by exhaustive permutation search. Therefore, low-cost metaheuristic algorithms are used to solve highly complex discrete combinatorial optimization problems, such as those related to production scheduling (Gao et al., 2024a, 2024b; Kilic et al., 2023; Liang et al., 2022; Torralba et al., 2018; Zamfirache et al., 2024). Commonly used algorithms include genetic algorithms (GA), ant colony optimization (ACO), and simulated annealing(SA), among others. These algorithms often have drawbacks, such as getting trapped in local optima. However, the biogeography-based optimization (BBO) algorithm can effectively overcome this limitation. The migration and mutation processes in BBO enhance the diversity of solutions and can perfectly escape local optima. At the same time, in order to retain the advantages of other algorithms, the crossover operator from GA and the acceptance criterion from SA are combined with BBO to enhance BBO’s global search performance and deep search capability (Precup et al., 2021; Torralba et al., 2018). Given the specificity of the problem, the conventional migration rate model of BBO is replaced in an attempt to find the most suitable model for solving the DAPFSP. In conclusion, this paper designs a hybrid biogeography-based optimization (HBBO) algorithm to solve the DAPFSP with the objective of minimizing makespan.

This paper is organized as follows. Section 2 reviews the relevant literature of the DAPFSP. Section 3 describes DAPFSP and provides the problem model. Section 4 introduces the basic framework of BBO. Section 5 provides a detailed introduction to the framework of HBBO and the related search methods. Sections 6 is the simulation experiment. Section 7 summarizes the conclusions and provides suggestions for future work.

2. Literature Review

DAPFSP was first proposed by Hatami et al. (2015), and a mixed integer linear programming (MILP) model was developed for it. Three constructive heuristic algorithms and a variable neighborhood search (VNS) algorithm were also designed, resulting in 12 algorithms to solve the DAPFSP. Two factory allocation methods were used, and a comprehensive summary of the problem’s characteristics was provided. In subsequent years, the problem was extended to DAPFSP with sequence dependent setup times (DAPFSP-SDST) by Hatami et al. (2013). A MILP model was proposed for this extension, and two constructive heuristic algorithms along with two neighborhood search methods were applied to VNS and iterative greedy (IG) algorithm. Parameter experiments were conducted, and the performance of these algorithms in solving DAPFSP-SDST was compared.

The DAPFSP with total flowtime (DAPFSP-TF) was addressed by Sang et al. (2019), who introduced three algorithms based on hybrid discrete invasive weed optimization (HDIWO). Local search procedures based on product permutations and job sequences were developed, and the algorithms demonstrated strong performance when compared with BBO, estimation of distribution algorithm (EDA).

DAPFSP with setup times (DAPFSP-ST) was addressed by Zhang and Xing (2018), who extended the regular two-stage assembly flow shop problem to a distributed manufacturing environment. The social spider optimization-based memetic algorithm was the first to be applied to combinatorial optimization. Wang and Wang (2015) proposed a memetic algorithm combined with EDA (EDAMA) to solve DAPFSP. EDAMA demonstrated better performance in small-sized instances compared to HBBO, while HBBO performed better in large-sized instances due to its stronger search ability.

A hybrid biogeography-based optimization algorithm was proposed by Lin and Zhang (2016), incorporating path relinking heuristics during the migration phase to exchange product job sequences. A global search for job insertion was also designed. The algorithm significantly improved upon basic instances of DAPFSP. Similarly, a backtracking search hyper-heuristic (BS-HH) algorithm was introduced by Lin et al. (2017), where ten heuristic rules were used to form a set of low-level heuristics. The backtracking search algorithm operated on these low-level heuristics. BS-HH was found to be significantly superior to EDAMA and HBBO in large instances of DAPFSP.

A biased-randomized iterated local search (BR-ILS) algorithm was proposed by Ferone et al. (2020) for solving DAPFSP. It was found to provide better stability in small-sized instances when compared to EDAMA and HBBO. In large-sized instances, BR-ILS was able to refresh better solutions, demonstrating its effectiveness across different problem sizes. DAPFSP with no-idle (DANIFSP) was introduced by Shao et al. (2018), with the objective of minimizing the makespan at the assembly stage. Gonzalez-Neira et al. (2017) focused on DAPFSP with stochastic processing times and proposed a hybrid algorithm combining biased randomization, simulation techniques, and metaheuristics.

Zhang et al. (2018) addressed DAPFSP and developed a constructive heuristic alongside two hybrid algorithms based on VNS and PSO. The DAPFSP was modified by Pan et al. (2019b), who reallocated assembly machines and introduced acceleration methods. Three heuristic algorithms and three VNS and IG neighborhood structures were designed, all of which performed well in solving the DAPFSP.

Yang and Xu (2021) introduced flexible assembly and batch delivery constraints to the DAPFSP (DAPFSP-FABD) based on Zhang’s research, designing four heuristic algorithms, VNS, and IG to solve the problem.

From Table 1, it can be seen that adding hybrid algorithm is an increasingly popular research direction in studying distributed scheduling problems, and optimal acceptance criteria is also gradually applied in distributed scheduling problems.

Table 1.
Literature Comparison.

Authors Algorithm Problem Hybrid Algorithm Optimal Acceptance Criteria

Yang and Xu (2021) VNS DAPFSP ✓

Hatami et al. (2013) HA, VNS, IG DAPFSP-SDST ✓ ✓

Sang et al. (2019) HDIWO DAPFSP-TF ✓

Lin and Zhang (2016) HBBO DAPFSP ✓ ✓

Lin et al. (2017) BS-HH DAPFSP ✓

Zhang and Xing (2018) MSSO DAPFSP-ST ✓

Wang and Wang (2015) EDAMA DAPFSP

Ferone et al. (2020) BR-ILS DAPFSP ✓ ✓

Shao et al. (2018) ILS VNS DANIFSP

Gonzalez-Neira et al. (2017) BR-Sim GRASP SDAPFSP ✓

Zhang et al. (2018) HVNS HPSO DAPFSP-FA ✓ ✓

Pan et al. (2019b) IG, HVNS DAPFSP ✓

Yang and Xu (2021) IG DAPFSP-FABD ✓ ✓

Authors	Algorithm	Problem	Hybrid Algorithm	Optimal Acceptance Criteria
Yang and Xu (2021)	VNS	DAPFSP		✓
Hatami et al. (2013)	HA, VNS, IG	DAPFSP-SDST	✓	✓
Sang et al. (2019)	HDIWO	DAPFSP-TF	✓
Lin and Zhang (2016)	HBBO	DAPFSP	✓	✓
Lin et al. (2017)	BS-HH	DAPFSP	✓
Zhang and Xing (2018)	MSSO	DAPFSP-ST	✓
Wang and Wang (2015)	EDAMA	DAPFSP
Ferone et al. (2020)	BR-ILS	DAPFSP	✓	✓
Shao et al. (2018)	ILS VNS	DANIFSP
Gonzalez-Neira et al. (2017)	BR-Sim GRASP	SDAPFSP	✓
Zhang et al. (2018)	HVNS HPSO	DAPFSP-FA	✓	✓
Pan et al. (2019b)	IG, HVNS	DAPFSP	✓
Yang and Xu (2021)	IG	DAPFSP-FABD	✓	✓

3. Distributed Assembly Permutation Flowshop Scheduling Problem

Figure 2 is the illustration of DAPFSP. DAPFSP can be described as follows. In production stage, job $J_{j}$ ( $j = 1, \dots, n$ ) needs to be assigned to factory $g$ ( $g = 1, \dots, f$ ) for processing. Each job can only be assigned to one factory. All factories have the same number and type of machines $M_{i}$ ( $i = 1, \dots, m$ ). Each job has $m$ processes. Each process must be processed on machine $i$ ( $i = 1, \dots, m$ ). All jobs are processed along the same route, specifically: first on machine 1, then on machine 2, and so on until reaching machine $i$ . This type of processing is called flowshop processing. The processing time required for job $j$ on machine $i$ is $p_{i j} (p_{i j} > 0)$ . Once the job is processed, it cannot be interrupted. In the assembly stage, jobs that have completed all processes need to be assembled into a product. Each job belongs to only one product $P_{l}$ ( $l = 1, \dots, k$ ), each product contains at least one job. The number of jobs belonging to product $l$ is $Ψ_{l}$ , $n = \sum_{l = 1}^{t} Ψ_{l}$ . The assembly of a product cannot begin until all its jobs are finished. The assembly time of the product $l$ is $p p_{l} (p p_{l} > 0)$ . Once the product is assembled on the assembly line ( $A L$ ), it cannot be interrupted. In the job production stage, $n$ jobs ( $J_{1}, J_{2}, \dots, J_{n}$ ) distributed to factory $g$ ( $F_{1}, F_{2}, \dots, F_{f}$ ), each factory is identical and contains $m$ processing machines ( $M_{1}, M_{2}, \dots, M_{m}$ ).

\begin{matrix} C_{i, j} = p_{i j}, j = 1, i = 1 \end{matrix}

(1)

\begin{matrix} C_{i, j} = C_{i - 1, j} + p_{i j}, j = 1, i = 2, \dots, m \end{matrix}

(2)

\begin{matrix} C_{i, j} = C_{i, j - 1} + p_{i j}, j = 2, \dots, n, i = 1 \end{matrix}

(3)

\begin{matrix} C_{i, j} = C_{i - 1, j} + p_{i j}, C_{i - 1, j} > C_{i, j - 1}, j = 2, \dots, n, i = 2, \dots, m \end{matrix}

(4)

\begin{matrix} C_{i, j} = C_{i, j - 1} + p_{i j}, C_{i - 1, j} \leq C_{i, j - 1}, j = 2, \dots, n, i = 2, \dots, m \end{matrix}

(5)

Equation (1) indicates the completion time of the first job on machine 1. Equation (2) indicates the completion time of first job on machine

M_{m}

. Equation (3) indicates the completion time of job

J_{j}

on machine1. Equations (4) and (5) represent the completion time of job

J_{j}

on machine

M_{m}

C_{i j}

is the completion time of job

J_{j}

on machine

M_{i}

\begin{matrix} C_{l} = max {x_{j l} C_{m, j}} + p p_{l}, l = 1, j = 1, 2, \dots, n \end{matrix}

(6)

\begin{matrix} C_{l} = C_{l - 1} + p p_{l}, C_{l - 1} > max {x_{j l} C_{m, j}}, l = 2, \dots, k, j = 1, 2, \dots, n \end{matrix}

(7)

\begin{matrix} C_{l} = max {x_{j l} C_{m, j}} + p p_{l}, C_{l - 1} \leq max {x_{j l} C_{m, j}}, l = 2, \dots, k, j = 1, 2, \dots, n \end{matrix}

(8)

\begin{matrix} C_{\max} = max {C_{l}}, l = 1, 2, \dots, k \end{matrix}

(9)

\begin{matrix} min C_{max} \end{matrix}

(10)

Figure 2.

Illustration of DAPFSP.

In the product assembly stage, the product $P_{l}$ ( $l = 1, 2, \dots, k$ ) allocate to an assembly line for assembly. The maximum assembly time is the research objective of the DAPFSP.

Equation (6) represents the time required for the completion of the first product assembly. Equations (7) and (8) represent the completion time of product $P_{l}$ . Equation (9) is the maximum assembly time. Equation (10) is the objective function of DAPFSP. $x_{j l}$ is a binary variable, where it is 1 if job $J_{j}$ belongs to product $P_{l}$ , and 0 otherwise. $C_{l}$ is the completion time of product $P_{l}$ . $C_{\max}$ is the maximum completion time.

4. Biogeography-Based Optimization Algorithm

BBO (Lin, 2015; Wang & Duan, 2014) is a metaheuristic algorithm inspired by the migration of species in biogeography. The primary mechanism for driving BBO involves modifying the habitat suitability index (HSI) for each habitat through the migration of species between habitats and habitat mutation. The HSI serves as a reflection of habitat fitness, influenced by various factors known as habitat suitability index variables (SIVs), including surface temperature, humidity, and rainfall. These SIVs collectively contribute to the determination of HSI, where a higher HSI value signifies a habitat of better quality, and conversely, a lower value indicates a lower-quality habitat. BBO relies on two key operators, migration, and mutation, to bring about changes in the HSI values. Migration involves the movement of species between habitats, influencing the HSI of both the source and destination habitats. This simulates the natural process of species moving in different environments. On the other hand, mutation introduces variability in the HSI values by altering the SIVs within a habitat. This operation simulates the occurrence of changes in environmental conditions within a habitat. In summary, BBO dynamically optimizes the quality of habitats by leveraging migration and mutation operations, with HSI and SIVs playing crucial roles in evaluating and shaping the fitness of each habitat in the population. BBO works based on two main operators named migration and mutation, which are described as follows:

\begin{matrix} λ_{r} = I (1 - \frac{N (r)}{N_{max}}) \end{matrix}

(11)

\begin{matrix} μ_{r} = E \frac{N (r)}{N_{max}} \end{matrix}

(12)

$λ_{r}$ represents the immigration rate of habitat r $H (r)$ , and $μ_{r}$ represents the emigration rate of $H (r)$ . $I (I \in (0, 1])$ and $E (E \in (0, 1])$ are the maximum immigration rate and maximum emigration rate, and they are usually set as constants. $N (r)$ represents the number of species at the instant of time contained in $H (r)$ and $N_{max}$ is the maximum number of species present in all habitats. Equations (10) and (11) represent the commonly used linear migration rate models in BBO. In addition, there are quadratic migration rate models, exponential migration rate models, and cosine migration rate models. These models will be provided in detail in Section 5.3.

The habitat mutation operation is a local search strategy to conduct a deeper search for the current solution. In BBO, as species migrate between habitats, all habitats will ultimately achieve a dynamic balance process, which is the desired outcome for species but not for algorithm. Algorithms need to continuously improve the optimal solution. Therefore, when designing the migration operator for BBO, algorithms also set up a mutation operator, as shown in Equations (12) and (13). $P_{r}$ is the probability of the number of species in $H (r)$ , $m_{max}$ is the maximum mutation rate, and $m_{r}$ is the probability of mutation.

\begin{matrix} {\dot{P}}_{r} = {\begin{array}{cc} - (λ_{r} + μ_{r}) P_{r} + μ_{r + 1} P_{r + 1} \\ - (λ_{r} + μ_{r}) P_{r} + λ_{r - 1} P_{r - 1} + μ_{r + 1} P_{r + 1} \\ - (λ_{r} + μ_{r}) P_{r} + λ_{r - 1} P_{r - 1} \end{array} \begin{matrix} r = 0 \\ 1 \leq r \leq N - 1 \\ r = N \end{matrix} \end{matrix}

(13)

\begin{matrix} m_{r} = m_{max} (1 - \frac{P_{r}}{P_{max}}) \end{matrix}

(14)

5. HBBO For DAPFSP

5.1. Coding and Encoding Method

Considering the complexity of the DAPFSP, a one-dimensional encoding method based on the sequence of job is designed, addressing the characteristics of the problem. Figure 3 is an encoding example, and this one-dimensional encoding can be represented by $Π$ . Job $J_{1}$ , $J_{3}$ , and $J_{5}$ belong to product 1. Job $J_{2}$ , $J_{7}$ , $J_{8}$ and $J_{9}$ belong to product 2. Job $J_{4}$ and $J_{6}$ belong to product 3. $Π$ ensures that all jobs of the same product are consecutively encoded in $Π$ . Each job belonging to product $P_{l}$ in $Π$ is referred to as $Π_{l}$ . The order in which each $Π_{l}$ appears from left to right in $Π$ is called the product priority $Π_{p p}$ . In Figure 3, $Π$ = $[1, 3, 5, 2, 7, 8, 4, 6]$ , $Π_{1}$ = $[1, 3, 5]$ , $Π_{2}$ = $[2, 7, 8, 9]$ , $Π_{3}$ = $[4, 6]$ , $Π_{p p}$ = $[1, 2, 3]$ .

Figure 3.

An Example of the Encoding and Decoding Process for DAPFSP.

Two factory allocation methods ( $N R 1$ and $N R 2$ ) are used in the decoding process of the DAPFSP (Naderi & Ruiz, 2010).

(1) $N R 1$ : Assign job $J_{j}$ to the factory with the lowest current $C_{m a x}$ , not including job $J$ .

(2) $N R 2$ : Assign job $J_{j}$ to the factory which completes it at the earliest time, that is, the factory with the lowest $C_{\max}$ , after including job $J$ .

HBBO generates $Π_{l}$ and $Π_{p p}$ randomly each time an initial individual is created. By combining $Π_{l}$ and $Π_{p p}$ , an initial encoding $Π$ can be obtained. Next, the job $J_{j}$ in $Π$ are selected from left to right, and $J_{j}$ is randomly assigned to a factory using either $N R 1$ or $N R 2$ . Once all the jobs have been assigned, the job processing sequence diagram, such as the one in Figure 3, can be obtained. The Makespan can be obtained by using the formula for the objective function provided in Section 3. In HBBO, $H S I$ of each habitat can be considered as the inverse of the objective function.

5.2. Acceptance Criteria

SA uses the Metropolis algorithm to generate the sequence of solutions of the combinatorial optimization problem, and the corresponding transition probability is shown in equation (15):

M_{P} = {\begin{array}{cc} 1, \\ \exp (- (\frac{HSI (H_{pre}) - HSI (H_{opt})}{t})), \end{array} \begin{matrix} HSI (H_{pre}) \leq HSI (H_{opt}) \\ otherwise \end{matrix}

(15)

If the $HSI$ of the optimized habitat $H_{opt}$ is bigger than the $H S I$ of the pre-optimized habitat $H_{pre}$ , $H_{opt}$ is directly accepted as $H_{pre}$ ; otherwise, the new solution is accepted according to the $\exp (- (HSI (H_{pre}) - HSI (H_{opt}) / t))$ and the random number. This method can retain a certain probability that there may be better coding segments of the poor solution, but also increase the diversity of understanding and improve the local search ability of the algorithm.

5.3. Migration Method

The crossover operator in GA can effectively retain the excellent encoding segments of parent individuals, while BBO is prone to losing some of the excellent encodings during the migration process. Therefore, HBBO incorporates the crossover operator from GA during the migration phase to improve the quality of the migrated habitats as a prerequisite. In addition, the conventional linear migration rate model may not be suitable for solving DAPFSP. Therefore, three other migration rate models were tested in the experiments.

Exponential migration model:

\begin{matrix} λ_{r} = I e^{- \frac{N (r)}{N_{max}}} \end{matrix}

(16)

\begin{matrix} μ_{r} = E e^{\frac{N (r)}{N_{max}} - 1} \end{matrix}

(17)

Secondary migration model:

\begin{matrix} λ_{r} = I {(1 - \frac{N (r)}{N_{max}})}^{2} \end{matrix}

(18)

\begin{matrix} μ_{r} = E {(\frac{N (r)}{N_{max}})}^{2} \end{matrix}

(19)

Cosine migration model:

\begin{matrix} λ_{r} = \frac{I}{2} (1 + \cos (\frac{N (r) π}{N_{max}})) \end{matrix}

(20)

\begin{matrix} λ_{r} = \frac{E}{2} (1 - \cos (\frac{N (r) π}{N_{max}})) \end{matrix}

(21)

Figure 4 is an example of the crossover process in HBBO. Using the data from Section 5.1 as an example, suppose there are two habitats, namely Father and Mother. Randomly exchange any number of job combinations of product $P_{l}$ , assuming the exchange is between product 2 and product 3. By keeping the processing priority of each product in the factory unchanged and only swapping the processing sequence of the jobs, two offspring individuals, offspring1 and offspring2, can be obtained. The migration rate is calculated to select the habitats for migration. The encoding information from the immigration habitat is replaced by the encoding information from the emigration habitat. Figure 5 illustrates an example of the migration process in HBBO.

Figure 4.

An Example of the Crossover Process.

Figure 5.

An Example of the Migration Process in HBBO.

5.4. Mutation Method

The mutation stage of HBBO is a critical step for the algorithm to escape local optima. Therefore, the solution space domain of the mutation strategy needs to be as large as possible, and the search method should be simple. Based on this, two mutation operators, local search job (LSJ) and local search product (LSP), are designed. Before executing LSJ, the $C_{\max}$ of each factory needs to be calculated. Any factory, except the one with the maximum $C_{\max}$ , is selected as the mutation target for LSJ. Randomly select two jobs of the same product in the chosen factory and swap their positions. The LSP mutation strategy does not require the calculation of $C_{m a x}$ for each factory. LSP only needs to randomly select two products and swap the processing sequence of the workpieces belonging to these two products to complete the mutation. Using the case in Section 5.1 as an example, the LSJ and LSP operation is as follows:

(1) LSJ: By calculation, it is found that the $C_{\max}$ of factory 1 is 45, and the $C_{\max}$ of factory 2 is 55. Therefore, factory 2 is selected as the mutation target for LSJ. Assume that product 1 is randomly selected. Randomly select two jobs of product 1 in factory 2, job 5 and job 1, and swap their positions. The habitat after the LSJ mutation is shown in Figure 6.

Figure 6.

LSJ Search.

(2) LSP: Randomly select two products, product 1 and product 2. Swap the processing sequence of the jobs belonging to the two products in the entire job sequence. The job 1 of product 1 in factory 1 swaps positions with the jobs 2, 7, and 8 of product 2 in factory 1. The job 3 and job 5 of product 1 in factory 1 swap positions with job 9 of product 2 in factory 2. The habitat after the LSP mutation is shown in Figure 7.

Figure 7.

LSP Search.

After performing the LSJ and LSP operations, use the acceptance criteria from Section 5.2 to determine whether the habitat should be retained.

5.5. Framework of HBBO

During the initialization phase, HBBO generates $N$ one-dimensional encodings and uses two factory allocation methods to obtain a batch of habitats with high HSI. The immigration and emigration rates of each habitat are calculated, based on which two habitats are selected: the habitat for immigration and the habitat for emigration. The offspring individuals generated by the crossover operation between these two habitats are taken as the new immigration and emigration habitats. The mutation probability for each habitat is calculated, and it is then determined whether the probability $m_{r}$ is greater than the random probability $R a n d o m P$ . If $m_{r}$ is greater than $R a n d o m P$ , the LSP and LSJ mutation operations are executed, and the mutated results are evaluated using the Metropolis function to determine whether they should be retained. Otherwise, it is determined whether the algorithm has reached the termination condition. If the condition is met, the optimal habitat is output; otherwise, the migration strategy is executed Figure 8.

Figure 8.

Flowchart of HBBO.

6. Computational Evaluation

6.1. Test Instances and Metrics

To evaluate the performance of the proposed methods for DAPFSP, the small-scale and large-scale DAPFSP instances presented in reference Hatami et al. (2013) are used as the experimental data set. All algorithms are coded in Microsoft Visual C++ and implemented on the laptop with i9-13980HX CPU @2.20 GHz and 16.0 GB RAM.

The processing data and optimal solutions of the DAPFSP instances used in the experiment can be found on soa.iti.es. In a small-scale DAPFSP instance, the number of jobs $n \in {8, 12, 16, 20, 24}$ , the number of machines $m \in {2, 3, 4, 5}$ , the number of factories $f \in {2, 3, 4}$ , the number of products $p \in {2, 3, 4}$ , each combination has 5 different instances, for a total of 900 instances. In a large-scale DAPFSP instance, the number of jobs $n \in {100, 200, 500}$ , the number of machines $m \in {5, 10, 20}$ , the number of factories $f \in {4, 6, 8}$ , the number of products $p \in {30, 40, 50}$ , each combination has 10 different instances, for a total of 810 instances. Each instance can be represented by $n_m_f_p$ . The termination condition of HBBO is CPU running time, The termination time is $n \times f \times 0.1$ seconds.

The average relative percentage deviation ( $RP D_{avg}$ ) is used to represent the result of the MBBO to solve DAPFSP. The percentage of optimal relative deviation ( $RP D_{best}$ ) is used to represent the optimal operating result in the MBBO process. $RP D_{best}$ and $RP D_{best}$ are defined as follows:

\begin{matrix} RP D_{avg} = \sum_{T = 1}^{R} (\frac{C_{T} - C_{best}}{C_{best}} \times 100) \times \frac{1}{R} (%) \end{matrix}

(22)

\begin{matrix} RP D_{best} = min_{T = 1, \dots R} (\frac{C_{T} - C_{best}}{C_{best}} \times 100) (%) \end{matrix}

(23)

$R$ represents the number of times the algorithm needs to run, $T$ is the number of times the algorithm is currently run. $C_{T}$ represents the result of the $T$ run of the algorithm, $C_{best}$ represents the known optimal result, $C_{B}$ represents the optimal result in $R$ times of running the algorithm. $R P D_{best}$ is negative if the MBBO updates a known optimal solution.

6.2. Parameter Setting

In order to maximize the performance of HBBO, Taguchi experimental method was used to find the optimal parameter combination for MBBO. MBBO has 5 parameters, which are habitat number $N$ , maximum iterations $I t e r_{max}$ , maximum mutation rate $m_{max}$ , the temperature $t$ and the crossover probability $α$ . Each parameter has four different accuracies. There are 16 parameter combinations. small-scale instance is selected for testing; each parameter combination was independently run 5 times and $R P D_{a v g}$ was used as the experimental result. Table 2 shows the values of five parameters of HBBO with four accuracies. Table 3 shows the operation results of orthogonal array $L_{16}$ ( $4^{3}$ ) obtained by Taguchi experiment under different parameter combinations.

Table 2.
Parameters and Their Levels.

Factor Level

Parameter 1 2 3 4

$N$ 50 100 150 200

$M_{max}$ 0.05 0.1 0.15 0.2

$I t e r_{max}$ 50 100 150 200

$t$ 100 200 300 400

$α$ 0.2 0.3 0.4 0.5

	Factor Level
$N$	50	100	150	200
$M_{max}$	0.05	0.1	0.15	0.2
$I t e r_{max}$	50	100	150	200
$t$	100	200	300	400
$α$	0.2	0.3	0.4	0.5

Table 3.

The Orthogonal $L_{16} (4^{5})$ .

No.	$N$	$M_{max}$	$I t e r_{max}$	$t$	$α$	$RP D_{avg}$
1	1	1	1	1	1	3.44
2	1	2	2	2	2	1.55
3	1	3	3	3	3	1.50
4	1	4	4	4	4	1.16
5	2	1	2	3	4	2.29
6	2	2	1	4	3	2.83
7	2	3	4	1	2	1.04
8	2	4	3	2	1	0.75
9	3	1	3	4	2	1.83
10	3	2	4	3	1	1.13
11	3	3	1	2	4	2.12
12	3	4	2	1	3	1.18
13	4	1	4	2	3	5.43
14	4	2	3	1	4	6.51
15	4	3	2	4	1	6.13
16	4	4	1	3	2	6.71

As shown in Figure 9, HBBO with $N = 150$ , $M_{max} = 0.20$ , $Ite r_{max} = 200$ , $t = 200$ and $α = 0.40$ performs better than HBBO with other parameter combinations, so the above settings are adopted.

Figure 9.

Main Effects Plot for Means and S/N Ratio.

6.3. Effectiveness Evaluation of the Proposed Methods

In Section 5.3, four new migration rate models are proposed: the linear migration rate model, exponential migration rate model, quadratic migration rate model, and cosine migration rate model. These models are used to replace the original migration rate model in MBBO for comparative experiments. The design of these models aims to improve the algorithm’s performance in solving DAPFSP, particularly in optimizing resource scheduling for cases of varying scales. To evaluate the effectiveness of these four migration rate models, small-scale DAPFSP test cases are selected for the experiments.

Figure 10 shows the 95% confidence intervals of the algorithm’s performance optimized by different migration rate models in DAPFSP small-scale case. The confidence intervals are calculated based on multiple experimental results and provide an intuitive reflection of the stability and reliability of each model in solving the problem. From the figure, it can be observed that there are significant differences in solution quality among the models. The cosine migration rate model maintains stability while ensuring solution quality, whereas the other models exhibit greater variability and poorer solution quality, potentially requiring more iterations to achieve better results.

Figure 10.

95% Confidence Intervals of Four Migration Model.

Additionally, to further analyze the convergence of the algorithm, the 24_5_3_2_4 case is selected for the experiment. Figure 11 presents the convergence analysis results of the four algorithms on the same test case. By showing the variation in the objective function values of each algorithm during the iteration process, Figure 11 provides a clear reflection of the convergence characteristics of different migration rate models. Based on the trends in the figure, the cosine migration rate model quickly approaches the optimal solution in the early iteration stages, while the other models may exhibit significant fluctuations during the convergence process and require a longer time to stabilize. Through convergence analysis, the search efficiency and stability of the solutions for each model can be assessed, providing a theoretical basis for optimizing scheduling problems.

Figure 11.

Convergence Analysis Chart of Instance 24_5_3_2_4.

Ultimately, through these experimental results, this paper aims to offer a more competitive solution for DAPFSP, particularly in complex production scheduling environments. It demonstrates how improvements in the migration rate models can enhance the algorithm’s global search capability and local optimization ability, thereby more effectively balancing the various demands in optimization problems.

6.4. Ablation Test

In order to evaluate the effectiveness of crossover proposed in Section 5.3 and acceptance criteria in Section 5.2, ablation experiments were conducted in this section. Ablation experiment is an experimental method commonly used in the field of algorithm research to evaluate the impact of certain features on the overall performance of an algorithm by removing or disabling them. Table 4 lists the algorithm labels for four different mechanisms. Each algorithm independently tested 900 instances of small-sized DAPFSP 5 times and compared $R P D_{best}$ as the result.

Table 4.
Algorithms That Include/Do Not Include Various Structures.

Algorithm Mechanism

None Not included crossover and acceptance criteria

HBBO ( $ω 1$ ) Include crossover

HBBO ( $ω 2$ ) Include acceptance criteria

HBBO Include crossover and acceptance criteria

Algorithm	Mechanism
None	Not included crossover and acceptance criteria
HBBO ( $ω 1$ )	Include crossover
HBBO ( $ω 2$ )	Include acceptance criteria
HBBO	Include crossover and acceptance criteria

Figure 12 records the running results of each algorithm. It can be observed that no matter what kind of structure can effectively improve the search ability of the algorithm. And the mean $RP D_{best}$ of HBBO ( $ω 1$ ) and HBBO ( $ω 2$ ) is 0.713 and 0.868, compared to None, $ARPD$ improved by 68.8 $%$ and 61.9 $%$ , at the same time, the interval is also reduced, which indicates that the stability of the algorithm is also improved. The HBBO contains all structures. The algorithm can further improve its search capability by 105.26 $%$ when all structures are added.

Figure 12.

$RP D_{best}$ Interval Plot of 95 $%$ Confidence Level of Different Algorithms.

6.5. Comparisons with Other Algorithms

To comprehensively evaluate the algorithm’s performance, both small-scale and large-scale DAPFSP cases were used for testing. A comparison was made between the algorithm proposed in reference Hatami et al. (2013), HBBO, and BBO. Tables 5 and 6 present the ${RPD}_{avg}$ values of each algorithm for different-scale DAPFSP cases, with the bolded values indicating the optimal solution for the current scale.

Table 5.
Comparison of RPD Values of Small-Sized Instances.

$f \times n$ $H_{11}$ $H_{12}$ $H_{21}$ $H_{22}$ $H_{31}$ $H_{32}$ $V N D_{_{H 11}}$ $V N D_{_{H 12}}$ $V N D_{_{H 21}}$ $V N D_{_{H 22}}$ $V N D_{_{H 31}}$ $V N D_{_{H 32}}$ $B B O$ $H B B O$

2 $\times$ 8 14.62 13.61 6.91 5.99 13.55 12.17 1 0.76 1 0.76 1.02 0.78 0.39 0.17

2 $\times$ 12 13.70 12.78 5.74 5.17 11.58 11.05 0.93 0.87 0.93 0.87 0.93 0.87 0.52 0.21

2 $\times$ 16 12.52 11.40 5.77 5.10 10.00 9.16 0.73 0.55 0.72 0.53 1.09 0.53 0.31 0.06

2 $\times$ 20 10.23 9.59 4.55 3.78 8.96 8.46 0.53 0.36 0.51 0.37 0.57 0.37 0.18 −0.21

2 $\times$ 24 8.71 8.34 5.00 4.74 7.54 7.15 0.54 0.21 0.54 0.21 0.54 0.21 $- 0.19$ −0.31

3 $\times$ 8 11.35 9.96 4.57 3.15 8.92 7.79 1.09 0.70 1.15 0.76 1.15 0.76 1.21 0.77

3 $\times$ 12 9.96 9.13 3.03 2.55 8.72 7.50 0.44 0.28 0.44 0.28 0.44 0.28 0.28 0.15

3 $\times$ 16 10.10 9.16 3.77 3.14 9.59 8.73 0.86 0.56 0.91 0.56 0.91 0.56 0.21 0.13

3 $\times$ 20 9.86 8.93 2.72 2.19 8.53 7.84 0.43 0.43 0.43 0.43 0.43 0.43 0.17 0.05

3 $\times$ 24 7.77 6.48 3.11 2.52 7.24 6.32 0.64 0.33 0.64 0.33 0.64 0.33 0.00 −0.15

4 $\times$ 8 9.03 8.01 2.16 1.25 6.41 5.25 1.08 0.63 0.99 0.63 0.99 0.63 2.02 1.23

4 $\times$ 12 5.63 4.53 1.82 1.38 4.58 3.58 0.74 0.47 0.74 0.47 0.74 0.56 0.60 0.12

4 $\times$ 16 7.21 6.34 2.86 2.27 6.14 5.18 0.59 0.28 0.59 0.28 0.59 0.28 0.29 0.18

4 $\times$ 20 6.80 6.00 2.96 2.61 5.66 5.04 1.10 0.63 1.10 0.63 1.10 0.63 0.28 0.07

4 $\times$ 24 5.14 4.43 2.02 1.60 4.87 4.19 0.57 0.26 0.57 0.26 0.57 0.26 0.03 −0.05

Average 9.51 8.58 3.80 3.16 8.15 7.29 0.75 0.49 0.75 0.49 0.78 0.50 0.42 0.16

$f \times n$	$H_{11}$	$H_{12}$	$H_{21}$	$H_{22}$	$H_{31}$	$H_{32}$	$V N D_{_{H 11}}$	$V N D_{_{H 12}}$	$V N D_{_{H 21}}$	$V N D_{_{H 22}}$	$V N D_{_{H 31}}$	$V N D_{_{H 32}}$	$B B O$	$H B B O$
2 $\times$ 8	14.62	13.61	6.91	5.99	13.55	12.17	1	0.76	1	0.76	1.02	0.78	0.39	0.17
2 $\times$ 12	13.70	12.78	5.74	5.17	11.58	11.05	0.93	0.87	0.93	0.87	0.93	0.87	0.52	0.21
2 $\times$ 16	12.52	11.40	5.77	5.10	10.00	9.16	0.73	0.55	0.72	0.53	1.09	0.53	0.31	0.06
2 $\times$ 20	10.23	9.59	4.55	3.78	8.96	8.46	0.53	0.36	0.51	0.37	0.57	0.37	0.18	−0.21
2 $\times$ 24	8.71	8.34	5.00	4.74	7.54	7.15	0.54	0.21	0.54	0.21	0.54	0.21	$- 0.19$	−0.31
3 $\times$ 8	11.35	9.96	4.57	3.15	8.92	7.79	1.09	0.70	1.15	0.76	1.15	0.76	1.21	0.77
3 $\times$ 12	9.96	9.13	3.03	2.55	8.72	7.50	0.44	0.28	0.44	0.28	0.44	0.28	0.28	0.15
3 $\times$ 16	10.10	9.16	3.77	3.14	9.59	8.73	0.86	0.56	0.91	0.56	0.91	0.56	0.21	0.13
3 $\times$ 20	9.86	8.93	2.72	2.19	8.53	7.84	0.43	0.43	0.43	0.43	0.43	0.43	0.17	0.05
3 $\times$ 24	7.77	6.48	3.11	2.52	7.24	6.32	0.64	0.33	0.64	0.33	0.64	0.33	0.00	−0.15
4 $\times$ 8	9.03	8.01	2.16	1.25	6.41	5.25	1.08	0.63	0.99	0.63	0.99	0.63	2.02	1.23
4 $\times$ 12	5.63	4.53	1.82	1.38	4.58	3.58	0.74	0.47	0.74	0.47	0.74	0.56	0.60	0.12
4 $\times$ 16	7.21	6.34	2.86	2.27	6.14	5.18	0.59	0.28	0.59	0.28	0.59	0.28	0.29	0.18
4 $\times$ 20	6.80	6.00	2.96	2.61	5.66	5.04	1.10	0.63	1.10	0.63	1.10	0.63	0.28	0.07
4 $\times$ 24	5.14	4.43	2.02	1.60	4.87	4.19	0.57	0.26	0.57	0.26	0.57	0.26	0.03	−0.05
Average	9.51	8.58	3.80	3.16	8.15	7.29	0.75	0.49	0.75	0.49	0.78	0.50	0.42	0.16

Table 6.

Comparison of RPD Values of Large-Sized Instances.

	$H_{11}$	$H_{12}$	$H_{21}$	$H_{22}$	$H_{31}$	$H_{32}$	$V N D_{_{H 11}}$	$V N D_{_{H 12}}$	$V N D_{_{H 21}}$	$V N D_{_{H 22}}$	$V N D_{_{H 31}}$	$V N D_{_{H 32}}$	$B B O$	$H B B O$
4	5.57	5.09	0.32	0.19	2.96	2.56	0.06	0.03	0.05	0.01	0.05	0.01	0.13	0.04
6	3.77	3.29	0.11	0.06	1.64	1.31	0.03	0.01	0.02	0	0.02	0	0.47	0.19
8	3.09	2.66	0.04	0.02	1.21	0.93	0.02	0	0.01	0	0.01	0	0.65	0.36
30	3.78	3.34	0.21	0.11	2.23	1.86	0.03	0.01	0.04	0.01	0.04	0.01	0.21	0.11
40	4.3	3.85	0.15	0.1	1.94	1.62	0.04	0.02	0.02	0.01	0.02	0.01	0.37	0.26
50	4.36	3.85	0.11	0.05	1.65	1.32	0.04	0.01	0.02	0	0.02	0	0.52	0.23
100	6.3	5.61	0.17	0.08	2.02	1.58	0.05	0.02	0.03	0.01	0.03	0.01	0.77	0.45
200	3.76	3.28	0.15	0.07	1.92	1.55	0.03	0.01	0.02	0	0.02	0	0.13	0.07
500	2.37	2.16	0.14	0.1	1.87	1.67	0.03	0.01	0.03	0.01	0.03	0.01	$- 0.08$	−0.12

From the results, it can be observed that in the small-scale DAPFSP cases, HBBO demonstrates a clear advantage, outperforming other algorithms in nearly all scales, except for the $4 \times 8$ scale, where it is slightly outperformed by ${VND}_{H 22}$ . However, in large-scale cases, HBBO’s performance is relatively weaker. It is worth noting, though, that in the high-complexity case of $n = 500$ , HBBO achieved multiple optimal solutions, indicating its significant advantage in handling complex problems and showcasing greater robustness.

7. Conclusions and Future Work

This paper introduces a hybrid biogeography-based optimization algorithm for solving DAPFSP. In order to improve the HSI of the initial habitat, a method of initializing random product sequence and factory allocation method was proposed. The core of this initialization is initialization by random product sequence and factory allocation method. This approach aims to accelerate the transportation of post-production products to the assembly shop and reduce the maximum completion time of the assembly shop, ultimately minimize the completion time of the assembly shop.

The contributions of this paper are as follows. (a) In the case of DAPFSP, four different migration models were experimentally compared to select the most suitable migration mode for the algorithm. (b) The crossover operator of the GA algorithm was incorporated into the migration operation of the BBO, employing the POX operator as the crossover method. (c) The Metropolis function in SA is used as an acceptance criterion for HBBO. (d) five sets of primary parameters for the HBBO were proposed, and 16 sets of Taguchi experiments were performed to determine the most suitable parameters for both small and large instances of DAPFSP. The experimental results were compared with the 12 search strategies proposed by Hatami et al. (2013) to demonstrate the significant impact of HBBO.

For our future work, we will add additional constraints to DAPFSP and attempt to integrate different types of swarm intelligence algorithms into the BBO algorithm (Pan et al., 2019a), such as the frog jumping algorithm (Li et al., 2018), gray wolf algorithm (Besharatnia et al., 2022), and krill swarm algorithm (Wang et al., 2014a, 2014b). The algorithm model will be improved to reduce the running time and iterations, and different search methods will be explored to enhance the speed of reaching optimal solutions and escaping local optima. Furthermore, efforts will be made to find the algorithm with the highest adaptability to the BBO and fuse it to achieve better scheduling results for DAPFSP.

Footnotes

Acknowledgments

This study was funded by Key Natural Science Research Projects of Colleges and Universities in Anhui Province (2022AH050978, 2023AH050935, 2023AH052915), Anhui Province University Excellent Top Talent Training Project (gxbjZD2022023), Wuhu science and technology project (2022jc26), the Open Research Fund of Anhui Province Key Laboratory of Detection Technology and Energy Saving Devices, Anhui Polytechnic University (JCKJ2021A06), Anhui Polytechnic University-Jiujiang District Industrial Collaborative Innovation Special Fund Project (2022cyxtb6), Research Fund Project of Anhui Polytechnic University (2022YQQ002, Xjky2022002), Anhui Province Key Laboratory of Machine Vision Detection and Perception (KLMVI-2024-HIT-15).

Funding

The authors received no financial support for the research, authorship, and/or publication of this article.

Declaration of Conflicting Interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

ORCID iD

Long Cheng

References

Besharatnia

Talebpour

Aliakbary

(2022). An improved grey wolves optimization algorithm for dynamic community detection and data clustering. Applied Artificial Intelligence, 36(1), 2012000.

Cheng

C.-Y.

Ying

K.-C.

Chen

H.-H.

H.-S.

(2019). Minimising makespan in distributed mixed no-idle flowshops. International Journal of Production Research, 57(1), 48–60.

Ferone

Hatami

González-Neira

E. M.

Juan

A. A.

Festa

(2020). A biased-randomized iterated local search for the distributed assembly permutation flow-shop problem. International Transactions in Operational Research, 27(3), 1368–1391.

Gao

Wang

(2024a). A modified competitive swarm optimizer guided by space sampling for large-scale multi-objective optimization. Swarm and Evolutionary Computation, 86, 101499. https://doi.org/10.1016/j.swevo.2024.101499

Gao

Zhang

Luo

Fan

(2024b). A fast nondominated sorting-based moea with convergence and diversity adjusted adaptively. The Journal of Supercomputing, 80(2), 1426–1463. https://doi.org/10.1007/s11227-023-05516-5

Garey

M. R.

Johnson

D. S.

Sethi

(1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117–129.

Gokhale

Mathirajan

(2011). Heuristic algorithms for scheduling of a batch processor in automobile gear manufacturing. International Journal of Production Research, 49(10), 2705–2728. https://doi.org/10.1080/00207541003720368

Gonzalez-Neira

E. M.

Ferone

Hatami

Juan

A. A.

(2017). A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times. Simulation Modelling Practice and Theory, 79, 23–36.

Hatami

Ruiz

Andres-Romano

(2013). The distributed assembly permutation flowshop scheduling problem. International Journal of Production Research, 51(17), 5292–5308.

10.

Hatami

Ruiz

Andrés-Romano

(2015). Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times. International Journal of Production Economics, 169, 76–88.

11.

Jia

Fuh

J. Y.

Nee

A. Y.

Zhang

(2002). Web-based multi-functional scheduling system for a distributed manufacturing environment. Concurrent Engineering, 10(1), 27–39.

12.

Kilic

Essiz

E. S.

Keles

M. K.

(2023). Binary anarchic society optimization for feature selection. Romanian Journal of Information Science and Technology, 26, 351–364. https://api.semanticscholar.org/CorpusID:264075101

13.

Jiang

(2018). An improved shuffled frog leaping algorithm and its application in the optimization of cascade reservoir operation. Hydrological Sciences Journal, 63(15-16), 2020–2034.

14.

Liang

Zeng

Luo

(2022). An improved loop subdivision to coordinate the smoothness and the number of faces via multi-objective optimization. Integrated Computer-Aided Engineering, 29(1), 23–41. https://doi.org/10.3233/ICA-210661

15.

Lin

(2015). A hybrid biogeography-based optimization for the fuzzy flexible job-shop scheduling problem. Knowledge-Based Systems, 78, 59–74.

16.

Lin

Wang

Z.-J.

(2017). A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem. Swarm and Evolutionary Computation, 36, 124–135.

17.

Lin

S.-W.

Ying

K.-C.

(2013). Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm. Computers & Operations Research, 40(6), 1625–1647.

18.

Lin

Zhang

(2016). An effective hybrid biogeography-based optimization algorithm for the distributed assembly permutation flow-shop scheduling problem. Computers & Industrial Engineering, 97, 128–136.

19.

Naderi

Ruiz

(2010). The distributed permutation flowshop scheduling problem. Computers & Operations Research, 37(4), 754–768.

20.

Pan

Q.-K.

Gao

Wang

(2019a). A multi-objective hot-rolling scheduling problem in the compact strip production. Applied Mathematical Modelling, 73, 327–348.

21.

Pan

Q.-K.

Gao

Xin-Yu

Jose

F. M.

(2019b). Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem. Applied Soft Computing, 81, 105492.

22.

Pourhejazy

Cheng

C.-Y.

Ying

K.-C.

Lin

S.-Y

(2021). Supply chain-oriented two-stage assembly flowshops with sequence-dependent setup times. Journal of Manufacturing Systems, 61, 139–154.

23.

Precup

R.-E.

Hedrea

E.-L.

Roman

R.-C.

Petriu

E. M.

Szedlak-Stinean

A.-I.

Bojan-Dragos

C.-A.

(2021). Experiment-based approach to teach optimization techniques. IEEE Transactions on Education, 64(2), 88–94. https://doi.org/10.1109/TE.2020.3008878

24.

Renna

(2012). Production and manufacturing system management: Coordination approaches and multi-site planning.

25.

Rossit

D. A.

Tohme

Frutos

(2019). Industry 4.0: Smart scheduling. International Journal of Production Research, 57(12), 3802–3813.

26.

Sang

H.-Y.

Pan

Q.-K.

J.-Q.

Wang

Han

Y.-Y.

Gao

K.-Z.

Duan

(2019). Effective invasive weed optimization algorithms for distributed assembly permutation flowshop problem with total flowtime criterion. Swarm and Evolutionary Computation, 44, 64–73.

27.

Shao

(2018). Local search methods for a distributed assembly no-idle flow shop scheduling problem. IEEE Systems Journal, 13(2), 1945–1956.

28.

Torralba

Á.

López

C. L.

Borrajo

(2018). Symbolic perimeter abstraction heuristics for cost-optimal planning. Artificial Intelligence, 259, 1–31. https://doi.org/10.1016/j.artint.2018.02.002

29.

Wang

Duan

(2014). A hybrid biogeography-based optimization algorithm for job shop scheduling problem. Computers & Industrial Engineering, 73, 96–114.

30.

Wang

G.-G.

Gandomi

A. H.

Alavi

A. H.

(2014a). An effective krill herd algorithm with migration operator in biogeography-based optimization. Applied Mathematical Modelling, 38(9-10), 2454–2462.

31.

Wang

G.-G.

Guo

Gandomi

A. H.

Hao

G.-S.

Wang

(2014b). Chaotic krill herd algorithm. Information Sciences, 274, 17–34.

32.

Wang

Shi

Wang

(2024). Re-entrant green scheduling problem of bearing production shops considering job reworking. Machines, 12(4) 281. https://doi.org/10.3390/machines12040281

33.

Wang

S.-Y.

Wang

(2015). An estimation of distribution algorithm-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 46(1), 139–149.

34.

Wenyou Jia

Z. J.

(2015). Combined scheduling algorithm for re-entrant batch-processing machines in semiconductor wafer manufacturing. International Journal of Production Research, 53(6), 1866–1879. https://doi.org/10.1080/00207543.2014.965355

35.

Yang

(2021). The distributed assembly permutation flowshop scheduling problem with flexible assembly and batch delivery. International Journal of Production Research, 59(13), 4053–4071.

36.

Ying

K.-C.

Lin

S.-W.

(2017). Minimizing makespan in distributed blocking flowshops using hybrid iterated greedy algorithms. IEEE Access, 5, 15694–15705.

37.

Zamfirache

I. A.

Precup

R. -E.

Petriu

E. M.

(2024). Adaptive reinforcement learning-based control using proximal policy optimization and slime mould algorithm with experimental tower crane system validation. Applied Soft Computing, 160, 111687. https://doi.org/10.1016/j.asoc.2024.111687

38.

Zhang

Xing

(2018). Memetic social spider optimization algorithm for scheduling two-stage assembly flowshop in a distributed environment. Computers & Industrial Engineering, 125, 423–433.

39.

Zhang

Xing

Cao

(2018). Scheduling distributed flowshops with flexible assembly and set-up time to minimise makespan. International Journal of Production Research, 56(9), 3226–3244.

	Factor Level
Parameter	1	2	3	4
$N$	50	100	150	200
$M_{max}$	0.05	0.1	0.15	0.2
$I t e r_{max}$	50	100	150	200
$t$	100	200	300	400
$α$	0.2	0.3	0.4	0.5

A Hybrid Biogeography-Based Optimization Algorithm for Distributed Assembly Permutation Flowshop Scheduling Problem

Abstract

Keywords

1. Introduction

5.1. Coding and Encoding Method

6.1. Test Instances and Metrics

Table 2. Parameters and Their Levels. Factor Level Parameter 1 2 3 4 N 50 100 150 200 M max 0.05 0.1 0.15 0.2 I t e r max 50 100 150 200 t 100 200 300 400 α 0.2 0.3 0.4 0.5

Table 4. Algorithms That Include/Do Not Include Various Structures. Algorithm Mechanism None Not included crossover and acceptance criteria HBBO ( ω 1 ) Include crossover HBBO ( ω 2 ) Include acceptance criteria HBBO Include crossover and acceptance criteria

Footnotes

Acknowledgments

Funding

Declaration of Conflicting Interests

ORCID iD

References

Table 2.
Parameters and Their Levels.

Factor Level

Parameter 1 2 3 4

$N$ 50 100 150 200

$M_{max}$ 0.05 0.1 0.15 0.2

$I t e r_{max}$ 50 100 150 200

$t$ 100 200 300 400

$α$ 0.2 0.3 0.4 0.5

Table 4.
Algorithms That Include/Do Not Include Various Structures.

Algorithm Mechanism

None Not included crossover and acceptance criteria

HBBO ( $ω 1$ ) Include crossover

HBBO ( $ω 2$ ) Include acceptance criteria

HBBO Include crossover and acceptance criteria