An improved memetic algorithm for distributed hybrid flow shop scheduling problem with operation inspection and reprocessing

Abstract

The classical distributed hybrid flow shop scheduling problem (DHFSP) only considers static production settings while ignores operation inspection and reprocessing. However, in the actual production, the manufacturing environment is usually dynamic; and the operation inspection and reprocessing are very necessary to avoid unqualified jobs from being transported to other production units and to make reasonable arrangements for unqualified and unprocessed jobs. In this paper, we propose a DHFSP with operation inspection and reprocessing (DHFSPR) for the first time, in which the operation inspection and reprocessing as well as the processing time and energy consumption are considered simultaneously. An improved memetic algorithm (IMA) is then designed to solve the DHFSPR, where some effective crossover and mutation operators, a new dynamic rescheduling method (DRM) and local search operator (LSO) are integrated. A total 60 DHFSPR benchmark instances are constructed to verify the performance of our IMA. Extensive experiments carried out demonstrate that the DRM and LSO can effectively improve the performance of IMA, and the IMA has obvious superiority to solve the DHFSPR problem compared with other three well-known algorithms. Our proposed model and algorithm here will be beneficial for the production managers who work with distributed hybrid shop systems in scheduling their production activities by considering operation inspection and reprocessing.

Introduction

Most recently, the distributed hybrid flow shop scheduling problem (DHFSP) has attracted an increasing number of researchers and production managers due to the economic globalization and increase of personal and diversity requirements of customers. The DHFSP entails arranging jobs, factories, workshops, machines appropriately to generate feasible solutions,^1–5 which includes four sub-problems: (1) assigning each job to a factory selected from the optional factory set; (2) assigning each job to a workshop selected from the optional workshop set from a corresponding factory; (3) assigning each job to a machine selected from the optional machine set from a corresponding workshop of factory; and (4) sequencing the operations satisfying the constraints among factories, machines and operations simultaneously. Obviously, the DHFSP is a more difficult NP-hard problem than the traditional flow shop scheduling problem (FSP) with only one factory.^6–8

In the recent decade, a various dynamic events have been studied in the production scheduling in recent years: such as new jobs arrival,^9–12 uncertain processing times,^13–15 machine breakdowns,^16–19 operator unavailability,^20,21 job cancellation,^22–25 etc. However, to the best of our knowledge, in the field of DHFSP, all existing researchers ignored the dynamic events of operation inspection and reprocessing, that is, they assumed that the production process is deterministic and unchanged; but in the real production systems, operation inspection and reprocessing are inevitable. For example, when an operation is finished processing, it is need to be inspected to detect the production defects timely and avoid unqualify products flowing to the next production stage. If the inspection result of the operation is qualified, it can be transported to the next stage for further processing; else if the result is unqualified, the process may be repaired, reprocessed, or directly scrapped, and other unprocessed processes need to be rescheduled.

Facing the above discussed practical production scheduling problem, the production managers must have to face the following situations when making scheduling decisions in the DHFSP:

• (1) In actual production, the operation quality may be affected by many uncertain events, such as the uncertainty of material quality, processing methods, and measurement tools. Without inspection, the defective jobs will be transported to the next production stage, which not only delays the completion time, but also adds additional processing, transportation and energy consumption costs. Therefore, how to arrange the operation inspection in each production stage and how to arrange the defective jobs to be reprocessed in the DHFSP is a thorny problem for the production decision makers, considering the operation inspection and job transportation simultaneously.

• (2) If the inspection result of an operation of a job is unqualified, it needs to be reprocessed or scrapped, which will make the original scheduling scheme infeasible. Hence, how to arrange the defective jobs to generate a feasible rescheduling scheme is another tough problem for the production decision makers, considering different inspection results of the jobs.

• (3) The DHFSP is a more NP-hard problem compared with the traditional FSP, which means that the traditional linear integer programing methods are difficult or even impossible to obtain accurate solutions in finite time. Hence, how to construct an effective optimization algorithm to solve the DHFSP is another important problem for the production decision makers, considering the optimization objectives of maximal completion time and total energy consumption simultaneously.

In addition, memetic algorithm (MA) as one of the most effective multi-objective algorithms, has been extensively applied to solve various scheduling problems in recent years. For instance, Yuan and Xu ²⁶ proposed some new memetic algorithms (MAs) for the multi-objective flexible job shop scheduling problem (FJSP) with the objectives to minimize the makespan, total workload, and critical workload. Gong et al. ²⁷ proposed a novel MA to solvethe classical distributed production scheduling problem, aiming to minimize the makespan and total energy consumption. Luo et al. ²⁸ proposed an efficient MA to solve the distributed flexible job shop scheduling problem with transfers with the objectives of minimizing the makespan, maximum workload, and total energy consumption of factories. To addresses the multi-objective energy-efficient FJSP with type-2 processing time, Li et al. ²⁹ proposed a mixed-integer linear programing model and designed a learning-based reference vector memetic algorithm to solve it. In order to determine the appropriate speed of the machine and the location of maintenance activities, Abedi et al. ³⁰ proposed a multi-population and multi-objective MA, in which the solutions are distributed into sub-populations.

Inspired by the above findings, in this paper, to solve the practical DHFSP with operation inspection, operation reprocessing and operation transportation among different factories, workshops and machines, the following researches were conducted. Firstly, a new model of the DHFSP considering operation inspection and reprocessing (DHFSPR) is proposed to achieve a better production performance. In addition, an improved memetic algorithm (IMA) is proposed to solve the DHFSPR aiming at minimizing the makespan and total energy consumption. In the IMA, a four-layer coding method and a new load balancing initialization method are designed to obtain high quality initial population; some effective crossover and mutation operators and a local search operator (LSO) are presented to obtain a larger solution space and accelerate the IMA’s convergence speed; a new mathematical model of DHFSP with operation inspection and reprocessing (DHFSPR) is proposed to realize a better production scheduling and a comprehensive dynamic rescheduling method (DRM) including three rescheduling strategies is designed to generate rescheduling schemes according to the inspection results of operations. Finally, in the experimental phase, a total of 60 DHFSPR benchmark instances are constructed to test the proposed algorithm, and four sets of experiments are designed to evaluate the effectiveness of the proposed operators and IMA. More specifically, the first experiment is conducted to obtain the optimal parameter combinations of the proposed IMA and other three compared algorithms based on the Taguchi experimental method ³¹ ; the second and third experiments are used to verify the effectiveness of the LSO and DRM respectively. The fourth set of experiment is carried out to evaluate the effectiveness of the proposed IMA by comparing it with other three well-known multi-objective algorithms.

The contributions of this paper can be summarized as follows:

• (1) We proposed a DHFSP model for the first time, which considers both operation and reprocessing. Compared with the traditional HFSP, this model has stronger flexibility and is more suitable for practical production.

• (2) An IMA was designed to solve the proposed DHFSP, in which a new well-designed four-layer chromosome coding method, a new load balancing initialization method, some effective crossover and mutation operators, and an LSO were integrated to obtain a high quality initial population, expand the solution space and accelerate the IMA’s convergence speed.

• (3) A comprehensive dynamic scheduling strategy that includes three rescheduling methods is provided to minimize the makespan and arrange the reprocessing operations to the idle machines as much as possible based on the event-driven rescheduling strategy and the full rescheduling method in predictive response scheduling.

The rest of this paper is organized as follows. In Section 2, the mathematical model and DRM are introduced in detail. Section 3 introduces the specific structure and content of the IMA. The experimental result and analysis are presented in Section 4. In the end, Section 5 summarizes paper and looks forward to the future research.

Literature review

Related work on DHFSP

Since the DHFSP was first proposed by Ying and Lin, ³² an increasing number of researchers have expanded and studied the problem from multiple aspects. Lu et al. ³³ designed a Pareto-based multi-objective hybrid iterated greedy algorithm by integrating the merits of genetic operator and iterated greedy heuristic to consider green goals in a distributed production environment. To minimize the adjustment and energy consumption simultaneously, Mou et al. ³⁴ proposed the energy-efficient distributed permutation flow-shop inverse scheduling problem. Dong and Ye ³⁵ established a distributed two-stage reentrant hybrid flow shop bi-level scheduling model, which takes makespan, total carbon emissions and total energy consumption costs as the optimization objectives. With increasing environmental awareness and energy requirement, Wang and Wang ³⁶ addressed the energy-aware DHFSP with the objectives of minimizing the makespan and energy consumption simultaneously. Yu et al. ³⁷ proposed a mixed integer linear programing (MILP) model and a knowledge-based iterative greedy algorithm considering the production of constrained resources (such as worker resources) in DHFSP. Considering the production of spare parts and the limited number of workers, a collaborative optimization problem of spare parts production and worker arrangement driven by operation and maintenance is proposed by Wang et al., ³⁸ and an improved Non-dominated Sorting Genetic Algorithm-II is proposed to solve it. Shao et al. ³⁹ investigated a distributed heterogeneous hybrid assembly line workshop scheduling problem with energy and labor perception (ELDHHFSP), and proposed MILP model for ELDHHFSP with the goal of minimizing total delay, total production cost, and total carbon emissions. Starting from the solution and strategy space, a network MA for the ELDHHFSP is proposed.

Considering some factors exiting in real production settings, some extend versions of DHFSP were studied by many researchers. To improve the operational efficiency and competitive advantage of supply chains, Qin et al. ⁴⁰ proposed three fast heuristics (CR-based heuristic, SLACK-based heuristic, and EDD-based heuristic) and an adaptive human-learning-based genetic algorithm to minimize the sum of earliness, tardiness and delivery costs. Cai et al. ⁴¹ considered DHFSP with sequence-dependent setup times in which factory assignment and machine assignment of first stage are integrated together. A new shuffled frog-leaping algorithm with memeplex quality is proposed to minimize the total tardiness and makespan simultaneously. Li et al. ⁴² proposed a hybrid artificial bee colony algorithm to solve a parallel batching DHFSP with deteriorating jobs. More and more enterprises are facing rapidly changing market demands and small yet frequent orders, Shao et al. ⁴³ studied a distributed heterogeneous hybrid flow shop lot-streaming scheduling problem with the minimization objective of makespan.

As mentioned above, the existing researches about DHFSP typically consider the factors in the actual manufacturing systems, such as energy efficiency, worker flexibility, heterogeneous factories, workshops, and transportation. However, to the best of our knowledge, no research about DHFSP considers the operation inspection and reprocessing, while which widely exist in the actual production environments. This may lead to resource waste and make the original plan infeasible. Therefore, to make the DHFSP model more in line with actual production, it is of great significance to study the DHFSP that considers the operation inspection and reprocessing.

Related work on dynamic scheduling

In terms of dynamic FSP (DFSP), Lee and Kim ⁴⁴ addressed a robotic FSP with processing time variations where two-part types are processed on each given set of dedicated machines and use a reinforcement learning (RL) approach to obtain efficient robot task sequences to minimize the makespan. Marichelvam and Geetha ⁴⁵ proposed an improved MA to tackle energy-efficient FSPs with uncertainties such as cancelled and new orders to minimize the total energy cost. Considering the dynamic events endanger baseline schedules, which may require a cost intensive re-scheduling, Grumbach et al. ⁴⁶ provided a novel method for robust-stable scheduling in dynamic flow shops based on deep reinforcement learning (DRL) implemented with OpenAI frameworks. The method is demonstrated using different flow shop instances with uncertain processing times, stochastic machine failures and uncertain repair times.

Regarding to the dynamic job shop scheduling problem (DJSP), Zhang et al. ⁴⁷ presented a multi-agent manufacturing system based on DRL to solve the DJSP, which integrates the self-organization mechanism and self-learning strategy. Zhang et al. ⁴⁸ introduced Digital Twin into the DJSP, which can provide more information for predicting machine availability, and help to detect interference by comparing physical machines with constantly updated digital counterparts in real-time, and triggers rearrangements in a timely manner when needed. Since traditional methods cannot dynamically generate effective scheduling strategies in face of the disturbance of environments, Zeng et al. ⁴⁹ proposed a flexible hybrid framework that takes disjunctive graphs as states and a set of general dispatching rules as the action space with minimum prior domain knowledge. Li et al. ⁵⁰ presented a modeling and solution approach for a robust DJSP under deterministic and stochastic machine unavailability caused, respectively, by planned preventive maintenance and unplanned corrective maintenance following random breakdowns. Shady et al. ⁵¹ proposed a genetic programing approach to generate dispatching rules automatically for multi-objective DJSP considering machine breakdowns. Considering the dynamics and the uncertainties such as machine breakdown and job rework of the job-shop environment, Wang et al. ⁵² proposed a dynamic scheduling method based on DRL and adopting proximal strategy optimization to find the optimal scheduling strategy to cope with the curse of state.

For the dynamic FJSP (DFJSP), Chang et al. ⁵³ proposed a DRL to solve the DFJSP with random job arrival, with the goal of minimizing penalties for earliness and tardiness. Zhang et al. ⁵⁴ proposed an effective two-stage algorithm based on convolutional neural network to solve the DFJSP with machine breakdown. Luo et al. ⁵⁵ proposed a knowledge-driven two-stage MA and used a rescheduling strategy is implemented in the scheduling process to mitigate the impact of machine breakdowns. An et al. ⁵⁶ studied the DFJSP with new job insertion and machine preventive maintenance (PM), established an imperfect PM (IPM) model, determined the optimal maintenance plan for each machine, and proposed an improved adaptive reference vector non dominated sorting inheritance algorithm III to solve the problem. Zhang et al. ⁵⁷ proposed a novel multifidelity-based surrogate-assisted genetic programing and proposed an effective collaboration mechanism with knowledge transfer for utilizing the advantages of multifidelity-based surrogate models to solve the desired problems. Due to the real manufacturing system is prone to various disturbance events, which increase the complexity and uncertainty of shop floor, Li et al. ⁵⁸ adopted deep reinforcement learning to solve the dynamic FJSP with insufficient transportation resources. In the production process of flexible job shop, there are dynamic events such as machine breakdowns or new job arrivals, Duan and Wang ⁵⁹ proposed a new robust optimization method that considers dynamic events and designs two indicators for evaluating the robustness of the system, namely the reusability of the system and the reproducibility of processing tasks. Wang et al. ⁶⁰ designed a novel dynamic multi-objective scheduling algorithm based on DRL. The algorithm uses two deep Q-learning networks and a real-time processing framework to process each dynamic event and generate complete scheduling scheme.

From the above, it can be seen that the dynamic scheduling has received an increasing attention from researchers. However, they normally ignore the dynamic events of operation inspection and reprocessing, while which are actually one of the most common dynamic events in real production environments. For example, if the inspection result of a finished operation is unqualified, how will we handle this operation? Reprocessing or scrapping the unqualified operations will result in the original scheduling plan being infeasible, increasing costs, and effect other unprocessed operations. Therefore, it is very necessary to propose intelligent optimization algorithms with high performance and robustness to address the impact of operation reprocessing and scrapping on the production system.

The mathematic model of the DHFSPR

Problem description

The DHFSPR studied in this paper consists of n jobs (J₁, J₂, …, J_n), f factories (F ₁ , F₂, …, F_f), each factory contains w workshops (W ₁ , W₂, …, W_w), each workshop contains m machines (M ₁ , M₂, …, M_m); and has l production stages {G ₁ , G₂, …, G_l}. In each stage, the factories, workshops and machines can be randomly selected for the corresponding operations. Each job is processed in the same sequence from G ₁ to G _l . Depending on the factory, workshop, and machine set, there are multiple parallel machines (M _k  ≥ 2) in each stage. The DHFSPR model proposed in this paper considers the jobs transportation among different factories, workshops and machines, including two optimization objectives: (1) maximum completion time; and (2) total energy consumption.

The DHFSPR model must meet the following constraints:

• All jobs must be processed according to the sequence of stages.

• A machine can process only one operation of a job at any time.

• Each operation can only be processed on a machine located in a workshop of a factory at the same time.

• The operation must be carried out continuously without interruption.

• The operations of different jobs have the same priority.

• Any operation of a job cannot be processed until its previous operations are finished.

• Each operation must be inspected before it can be transported to the next stage for processing.

• Inspection time of each operation is predefined.

• The processing time of operations of all jobs are predefined.

• The unit energy consumption of all machines is set in advance.

• Transportation times and energy consumption between different factories, workshops and machines are predetermined.

Parameters and variables

All parameters and symbols in the model of the DHFSPR are shown in Table 1.

Table 1.

Parameters, symbols, and variables of the DHFSPR.

Parameters
$i,a$	Index for jobs
$j,b$	Index for operations
$k$	Index for stages
$f$	Index for factories
$w$	Index for workshops
$m$	Index for machines
$l$	Total number of stages
$n$	Total number of jobs
ri	Total number of operations of job i
$n_f$	Total number of factories
$n_w$	Total number of workshops
$m_{\mathrm{wf}}$	Total number of machines in workshop w of factory f
$O_{\mathrm{ij}}$	The j-th operation of job i
G	Set of stages, G = {1, 2, …, l}
$M_{\mathrm{ij}}$	Set of operable machines for $O_{\mathrm{ij}}$
$I$	Set for jobs, I={1,2,…,n}
$Q_i$	Set for the operations of job i, $Q_i=\{1,2,\dots ,q_i\}$
$Q{Q}_i$	Set for the top $r_i-1$ operations of job i, $Q{Q}_i=\{1,2,\dots ,q_i-1\}$
$F_f$	Set for factories, $F_f=\{1,2,\dots ,n_f\}$
$W_w$	Set for workshop in factory f, $W_w=\{1,2,\dots ,n_w\}$
$M_{\mathrm{ijwf}}$	Set for machine in workshop w of factory f that are eligible to process $O_{\mathrm{ij}}$
$T_{\mathrm{ijfwm}}$	Processing time of operation $O_{\mathrm{ij}}$ processed by machine m in workshop w of factory f
$p$	Index for positions
$p_{\mathrm{fwm}}$	Total number of positions of machine m in workshop w of factory f
$P_{\mathrm{fwm}}$	Set for the positions of machine m in workshop w of factory f, $P_{\mathrm{fwm}}=\{1,2,\dots ,p_{\mathrm{fwm}}\}$
$P{P}_{\mathrm{fwm}}$	Set for the top $p_{\mathrm{fwm}}-1$ positions of machine m in workshop w of factory f, $P{P}_{\mathrm{fwm}}=\{1,2,\dots ,p_{\mathrm{fwm}}-1\}$
$T{I}_{\mathrm{ij}}$	The inspection time of $O_{\mathrm{ij}}$
$T_m$	The transportation time between two machines
$T_w$	The transportation time between two workshops
$T_f$	The transportation time between two factories
$P{E}_{\mathrm{fwm}}$	The processing power of machine m in workshop w of factory f
$\mathrm{EU}$	The transportation power
$C$	A large positive integer
Variables
$X_{\mathrm{if}}$	$X_{\mathrm{if}}$ = $\{\begin{array}{c}1,\mathrm{if}\mathrm{job}i\mathrm{is}\mathrm{processed}\mathrm{in}\mathrm{factory}f\hfill \\ \multicolumn{1}{c}{0,\mathrm{otherwise}}\end{array}$
$X_{\mathrm{ijfwmp}}$	$X_{\mathrm{ijfwmp}}$ = $\{\begin{array}{c}1,\mathrm{if}\mathrm{operation}{O}_{\mathrm{ij}}\mathrm{is}\mathrm{processed}\mathrm{at}\mathrm{position}p\mathrm{of}\mathrm{machine}m\mathrm{in}\mathrm{workshop}w\mathrm{of}\mathrm{factory}f\hfill \\ \multicolumn{1}{c}{0,\mathrm{otherwise}}\end{array}$
$T{M}_{\mathrm{ij}}$	$T{M}_{\mathrm{ij}}$ = $\{\begin{array}{c}1,\mathrm{if}\mathrm{operation}{O}_{\mathrm{ij}}\mathrm{is}\mathrm{transported}\mathrm{between}\mathrm{two}\mathrm{machines}\hfill \\ \multicolumn{1}{c}{0,\mathrm{otherwise}}\end{array}$
$T{W}_{\mathrm{ij}}$	$T{W}_{\mathrm{ij}}$ = $\{\begin{array}{c}1,\mathrm{if}\mathrm{operation}{O}_{\mathrm{ij}}\mathrm{is}\mathrm{transported}\mathrm{between}\mathrm{two}\mathrm{workshops}\hfill \\ \multicolumn{1}{c}{0,\mathrm{otherwise}}\end{array}$
$T{F}_{\mathrm{ij}}$	$T{F}_{\mathrm{ij}}$ = $\{\begin{array}{c}1,\mathrm{if}\mathrm{operation}{O}_{\mathrm{ij}}\mathrm{is}\mathrm{transported}\mathrm{between}\mathrm{two}\mathrm{factories}\hfill \\ \multicolumn{1}{c}{0,\mathrm{otherwise}}\end{array}$
$X_{\mathrm{ijkm}}$	$X_{\mathrm{ijk}}$ = $\{\begin{array}{c}1,\mathrm{if}\mathrm{operation}{O}_{\mathrm{ij}}\mathrm{is}\mathrm{processed}\mathrm{on}\mathrm{machine}m\mathrm{at}\mathrm{stage}k\hfill \\ \multicolumn{1}{c}{0,\mathrm{otherwise}}\end{array}$
$Z_{\mathrm{ijk}}$	$Z_{\mathrm{ilk}}$ = $\{\begin{array}{c}1,\mathrm{if}\mathrm{operation}{O}_{\mathrm{ij}}\mathrm{is}\mathrm{precedes}\mathrm{operation}{O}_{i{r}_i}\mathrm{at}\mathrm{stage}k\hfill \\ \multicolumn{1}{c}{0,\mathrm{otherwise}}\end{array}$
$W_{\mathrm{ilk}}$	$W_{\mathrm{ilk}}$ = $\{\begin{array}{c}1,\mathrm{if}\mathrm{operation}{O}_{\mathrm{ij}}\mathrm{is}\mathrm{to}\mathrm{be}\mathrm{processed}\mathrm{at}\mathrm{stage}k\mathrm{immediately}\mathrm{after}\mathrm{its}\mathrm{completion}\mathrm{at}\mathrm{stage}l\hfill \\ \multicolumn{1}{c}{0,\mathrm{otherwise}}\end{array}$
$I{P}_{\mathrm{ij}}$	$I{P}_{\mathrm{ij}}=\{\begin{array}{c}1,\mathrm{if}\mathrm{operation}{O}_{\mathrm{ij}}\mathrm{is}\mathrm{reprocessed}\mathrm{after}\mathrm{inspection}\hfill \\ \multicolumn{1}{c}{0,\mathrm{otherwise}}\end{array}$
$\mathrm{EM}$	Total transportation energy consumption between two machines
$\mathrm{EW}$	Total transportation energy consumption between two workshops
$\mathrm{EF}$	Total transportation energy consumption between two factories
$\mathrm{EP}$	Total processing energy consumption of all operations
$\mathrm{ET}$	Total transportation energy consumption
$T_{\mathrm{ijk}}^s$	The start time of $O_{\mathrm{ij}}$ in $G_k$
$T_{\mathrm{ijk}}^c$	The completion time of $O_{\mathrm{ij}}$ in $G_k$
$S_{\mathrm{fwmp}}$	The start time of position p of machine m in workshop w of factory f
$C_{\max }$	Makespan
$E$	Total energy consumption

Energy consumption model

The total energy consumption (E) includes the total energy consumption of machine processing (EC) and total energy consumption of transportation (ET), which are defined as follows:

• (1) EC is the total energy consumption of all machines during processing and can be calculated by using equation (1).

$$\begin{array}{l}EC=\\ \sum _{i\in I}\sum _{j\in Q_i}\sum _{f\in F_a}\sum _{w\in W_f}\sum _{m\in M_{ij}}\sum _{p\in P_{fwm}}{T}_{ijfwm}\ast X_{ijfwmp}\ast P{E}_{fwm}\ast (1+I{P}_{ij})\end{array}$$

(1)

• (2) ET is the total energy consumption of all jobs transported among different factories, workshops and machines, and can be calculated by using equation (2).

$$\begin{array}{c}\mathrm{ET}=\mathrm{EF}+\mathrm{EW}+\mathrm{EM}=\sum _{i\in I}\sum _{j\in Q_i}{T}_f*T{F}_{\mathrm{ij}}*\mathrm{EU}*(1+I{P}_{\mathrm{ij}})\hfill \\ +\sum _{i\in I}\sum _{j\in Q_i}{T}_w*T{W}_{\mathrm{ij}}*\mathrm{EU}*(1+I{P}_{\mathrm{ij}})\hfill \\ +\sum _{i\in I}\sum _{j\in Q_i}{T}_m*T{M}_{\mathrm{ij}}*\mathrm{EU}*(1+I{P}_{\mathrm{ij}})\hfill \end{array}$$

(2)

Mathematical model of DHFSPR

Based on the model in literature ⁶¹ and the above parameters and energy consumption model, the mathematical model of DHFJSP is as follows: the above parameters and energy consumption model, the mathematical model of DHFJSP is as follows:

• Objectives:

• (1) Minimizing the makespan (ob1)

$$\begin{array}{c}\mathrm{ob}1=\min C_{\max }\hfill \end{array}$$

(3)

• (2) Minimizing the total energy consumption (ob2)

$$\begin{array}{c}\mathrm{ob}2=\mathrm{minE}=min(\mathrm{EP}+\mathrm{ET})\hfill \end{array}$$

(4)

• Subject to:

$$\begin{array}{c}{T}_{\mathrm{ijk}}^s\ge 0,\forall i\in I,j\in Q_i,k\in G\hfill \end{array}$$

(5)

$$\begin{array}{c}\sum _{\begin{array}{c}k\in G\hfill \\ \multicolumn{1}{c}{m\in m_{\mathrm{fw}}}\end{array}}{X}_{\mathrm{ijkm}}=X_{\mathrm{if}}\forall i\in I,j\in Q_i\hfill \end{array}$$

(6)

$$\begin{array}{l}\sum _{i\in I}\sum _{j\in Q_i}\sum _{f\in F_f}\sum _{w\in W_w}{X}_{ijfwmp}\ge \sum _{a\in I}\sum _{b\in Q_i}\sum _{f\in F_f}\sum _{w\in W_w}{X}_{abfwm\left(p+1\right)},\\ \forall m\in M_{ijfw},p\in P{P}_{fwm}\end{array}$$

(7)

$$\begin{array}{c}{T}_{i(j+1)k}^S-T_{\mathrm{ijk}}^S\ge \sum _{f\in F_i}\sum _{w\in W_f}\sum _{m\in M_{\mathrm{ijfw}}}\sum _{p\in P_{\mathrm{fwm}}}\hfill \\ (T_{\mathrm{ijfwmk}}+T{I}_{\mathrm{ij}*}I{P}_{\mathrm{ij}}+T_f*T{F}_{\mathrm{ij}}+T_w*T{W}_{\mathrm{ij}}+T_m*T{M}_{\mathrm{ij}})*\hfill \\ X_{\mathrm{ijfwmp}},\begin{array}{c}\forall i\in I,j\in Q_i,k\in G,f\in F_f,w\in W_w,m\in M_{\mathrm{ijfw}},p\in P_{\mathrm{fwm}}\hfill \end{array}\hfill \end{array}$$

(8)

$$\begin{array}{c}\sum _{i\in I}\sum _{j\in Q_i}\sum _{f\in F_f}\sum _{w\in W_w}{X}_{\mathrm{ijfwmp}}\le 1,\forall w\in W_f,\forall m\in M_{\mathrm{ijfw}},p\in P{P}_{\mathrm{fwm}}\hfill \end{array}$$

(9)

$$\begin{array}{c}{S}_{\mathrm{fwmp}}\le T_{\mathrm{ijk}}^s+\sum _{f\in F_i}\sum _{w\in W_f}\sum _{m\in M_{\mathrm{ijfw}}}\sum _{p\in P_{\mathrm{fwm}}}\hfill \\ (T_{\mathrm{ijfwmk}}+T{I}_{\mathrm{ij}*}I{P}_{\mathrm{ij}}+T_f*T{F}_{\mathrm{ij}}+T_w*T{W}_{\mathrm{ij}}+T_m*T{M}_{\mathrm{ij}})*\hfill \\ X_{\mathrm{ijfwmp}},\forall i\in I,j\in Q,f\in F_f,w\in W_w,m\in M_{\mathrm{ijfw},}p\in P_{\mathrm{fwm}}\hfill \end{array}$$

(10)

$$\begin{array}{c}{T}_{\mathrm{ijk}}^c\ge T_{\mathrm{ijk}}^s+\sum _{f\in F_a}\sum _{w\in W_f}\sum _{m\in M_{\mathrm{ijfw}}}\sum _{p\in P_{\mathrm{fwm}}}\hfill \\ (T_{\mathrm{ijfwmk}}+T{I}_{\mathrm{ij}*}I{P}_{\mathrm{ij}}+T_f*T{F}_{\mathrm{ij}}+T_w*T{W}_{\mathrm{ij}}+T_m*T{M}_{\mathrm{ij}}\hfill \\ +T{I}_{\mathrm{ij}}*I{P}_{\mathrm{ij}})*X_{\mathrm{ijfwmp}},\begin{array}{c}\forall i\in I,j\in Q_i,f\in F_a,w\in W_f\hfill \end{array}\hfill \end{array}$$

(11)

$$\begin{array}{c}{T}_{i(j+1)}^s\ge T_{\mathrm{ij}}^c,\forall i\in I,j\in Q{Q}_i\hfill \end{array}$$

(12)

$$\begin{array}{c}{C}_{\max }\ge T_{i{r}_{i}k}^s+\sum _{f\in F_a}\sum _{w\in W_f}\sum _{m\in M_{\mathrm{ijfw}}}\sum _{p\in P_{\mathrm{fwm}}}\hfill \\ (T_{i{r}_i\mathrm{fwmk}}+T_f*T{F}_{i{r}_i}+T_w*T{W}_{i{r}_i}+T_m*T{M}_{i{r}_i}+T{I}_{\mathrm{ij}}*I{P}_{\mathrm{ij}})*\hfill \\ X_{i{r}_i\mathrm{fwmp}},\begin{array}{c}\forall i\in I,j\in Q_i,f\in F_f,w\in W_w,m\in M_{\mathrm{ijfw},}p\in P_{\mathrm{fwm}}\hfill \end{array}\hfill \end{array}$$

(13)

$$\begin{array}{c}0\le (T{F}_{\mathrm{ij}}+T{W}_{\mathrm{ij}}+T{M}_{\mathrm{ij}})\le 1,\forall i\in I,j\in Q_i\hfill \end{array}$$

(14)

$$\begin{array}{c}{T}_{\mathrm{ijk}}^s\ge 0,\forall i\in I,j\in Q_{i}k\in G\hfill \end{array}$$

(15)

$$\begin{array}{c}{T}_{\mathrm{ijk}}^c\ge 0,\forall i\in I,j\in Q_{i}k\in G\hfill \end{array}$$

(16)

$$\begin{array}{c}{S}_{\mathrm{fwmp}}\ge 0,\forall f\in F_f,w\in W_w,m\in M_{\mathrm{ijfw},}p\in P_{\mathrm{fwm}}\hfill \end{array}$$

(17)

In the above mathematical model, equations (3) and (4) represent the objectives of minimizing the makespan and total energy consumption. Constraint (5) requires that the starting time of a job on the first stage is later than or equal to time zero. Constraint (6) ensures that each job must be processed by any one machine at each stage. Constraint (7) guarantees that the machining position on each machine is determined and must be assigned to the operation sequentially. Constraint (8) specifies the processing sequence between operations of all jobs. Constraints (9)-(10) make sure that at most one operation is scheduled at each position of each machine at the same time, and no overlapping processing is allowed. Constraints (11) defines the completion time of each operation. Constraints (12) ensures that an operation of a job can be started only when the operation at previous stage is finished. Constraint (13) defines the target value of makespan. Constraint (14) guarantees at most one transportation is allowed for each operation among factories, workshops and machines at the same time. Constraints (15)–(17) ensure that the start and finish times of all operations, as well as the start times of all positions, have no variables less than 0.

Model example

Table 2 shows a simple example of the DHFJSP model, which includes three stages (G1, G2 and G3), seven jobs (J ₁ , J₂, …, J₇) processed in sequence according to the stage sequence, and two factories (F ₁ and F ₂ ). Taking G1 for example, in which F1 and F2 each have two workshops (W ₁₁ and W ₁₂ ) and one workshop (W ₂₁ ); and W ₁₁ , W ₁₂ and W ₂₁ have two machines (M ₁₁₁ and M ₁₁₂ ), two machines (M ₁₂₁ and M ₁₂₂ ), two machines (M ₂₁₁ and M ₂₁₂ ), respectively. G2 and G3 can be described as G1. The numbers in the brackets indicate the unit processing energy consumption (P _Efwm ) of the corresponding machines. The data to the left and right of the comma represent the processing time (T _ijfwm ) and inspection time (T _Iij ) respectively for the corresponding operations. If we want to get the T _ijfwm , T _ij and P _Efwm of J ₁ on M ₁₂₁ in W ₁₂ of F ₁ in G2, we just need to set i = 1, j = 2, k = 2, f = 1, w = 2, m = 2, then T _ijfwm  = 50, T _iij  = 18, P _Efwm  = 6. The dashes in Table 2 (“-”) indicate that their corresponding operations cannot be performed on the corresponding machines. For example, M ₁₁₁ in W ₁₁ of F ₁ cannot process J ₁ in G1.

Table 2.

An example of DHFSPR.

Job	G1						G2						G3
	F 1				F 2		F 1					F 2	F 1		F 2
	W 11		W 12		W 21		W 11		W 12			W 21	W 11	W 12	W 21
	M 111 (7)	M 112 (6)	M 121 (8)	M 122 (4)	M 211 (10)	M 212 (5)	M 113 (7)	M 114 (6)	M 123 (8)	M 124 (6)	M 213 (9)	M 214 (5)	M 115 (10)	M 125 (8)	M 215 (7)
J 1	5,2	6,2	-	11,3	13,2	-	13,2	-	6,2	-	-	13,2	8,2	6,2	7,2
J 2	-	6,1	8,2	-	-	8,2	6,2	6,2	-	7,2	7,1	6,2	5,2	-	7,1
J 3	-	11,2	6,1	-	8,2	-	7,2	7,1	-	7,1	-	7,2	6,2	-	6,1
J 4	13,2	-	10,2	8,2	-	9,2	-	13,2	-	8,2	10,2	-	6,2	7,2	7,2
J 5	13,2	-	10,2	9,1	-	-	8,2	-	10,1	8,1	-	8,2	5,2	8,2	8,2
J 6	7,2	-	8,2	-	6,2	-	-	6,2	8,2	-	6,2	-	8,2	-	8,2
J 7	-	16,3	-	10,2	8,2	7,2	6,2	7,1	8,2	-	-	6,2	5,2	7,2	10,2

Rescheduling method

In this paper, a dynamic rescheduling method (DRM) is proposed to minimize the makespan and to arrange the reprocessing operations to the idle machines as much as possible based on the event-driven rescheduling strategy and the full rescheduling method in predictive response scheduling. The DRM includes three strategies which are described as follows, where T _ijfwmk and L _fwmk represent the reprocessing time of the rescheduled O _ij on machine m of workshop w of factory f in stage k and the interval length between two adjacent operations on machine m of workshop w of factory f in the stage k, respectively.

• Strategy 1: If L _fwmk > T _ijfwmk , O _ij is inserted directly into the earliest interval of all the optional machines.

• Strategy 2: If 0 < L _fwmk < T _ijfwmk , O _ij is inserted into the biggest interval of all the optional machines, and other operations affected by the inserting are moved to the right as less as possible obeying their processing constraints.

• Strategy 3: If L _fwmk  = 0, O _ij is arranged to the position behind the last operation of optional machine with the smallest cumulative processing time for reprocessing.

To illustrate the rescheduling process clearly, Figure 1 shows a Gantt chart of a rescheduling scheme for operation reprocessing, in which the green and red squares adjacent to operations indicate that the inspection results are qualified and unqualified respectively, that is, the operations with red color need to be reprocessed.

Figure 1.

An example of the DRM: (a) strategy 1: assuming O ₃₂ needs to be reprocessed, (b) strategy 2: assuming O ₂₃ needs to be reprocessed, and (c) strategy 3: assuming O ₆₃ needs to be reprocessed.

From Figure 1(a), we can see that O ₃₂ on M4 in workshop 11 of factory 1 needs to be reprocessed (because the color of the square adjacent to O ₃₂ is red), the processing time of O ₃₂ is 7, and the interval time between O ₄₂ and O ₇₂ is 9. Hence, O ₃₂ is inserted into the interval between O ₄₂ and O ₇₂ based on Strategy 1 (satisfying L _fwmk  = L ₂₁₄₂  = 9 > T _ijfwmk  = T ₃₂₁₂₄  = 7), and the reprocessed O ₃₂ is marked as O_32′.

From Figure 1(b), we can see that O ₂₃ on M5 in workshop 11 of factory 1 needs to be reprocessed (because the color of the square adjacent to O ₂₃ is red), the processing time of O ₂₃ is 6, and the interval time between O ₁₃ and O ₄₃ is 5. Hence, O ₂₃ is inserted into the interval between O ₁₃ and O ₄₃ by moving O ₄₃ to the right based on Strategy 2 (satisfying 0 < L _fwmk  =L ₁₁₅₃  = 5 < T _ijfwmk  = T ₁₂₅₃  = 6), and the reprocessed O ₂₃ is marked as O_23′.

From Figure 1(c), we can see that O ₆₃ on M5 in workshop 11 of factory 1 needs to be reprocessed (because the color of the square adjacent to O ₆₃ is red), the processing time of O ₆₃ is 6, and the interval time between each adjacent operation equals to 0. Hence, O ₆₃ is arranged to M5 in workshop 11 of factory 1 (with the smallest cumulative processing time) for reprocessing based on Strategy 3 (satisfying L _fwmk  = L ₁₁₅₃  = 0), and the reprocessed O ₆₃ is marked as O_63′.

The proposed IMA

As we all know, the NSGA-II is one of the most popular evolutionary algorithms to solve the production scheduling problems (Deb et al. ⁶⁸ ), in which a selection strategy is used to choose the excellent individuals for the population, and the non-dominant sorting and crowding distance operators are designed to deal with the optimization objectives. In recent decades, the MA has also been widely used to solve the scheduling problems based on the framework of NSGA-II, in which an efficient local search operator (LSO) is integrated.^36,62,63 Here, we propose an IMA to solve the DHFSPR, in which an efficient LSO is combined to expend the solution space and increase the convergence speed while retaining the advantages of both NSGA-II and MA. The framework of the proposed IMA is shown in Figure 2. From Figure 3, we can see that the IMA includes two stages: the initial scheduling stage (marked as “First stage”) and the rescheduling stage (marked as “Second stage”). In the initial scheduling stage, all operations are processed according to the initial scheduling scheme; and in the rescheduling stage, the reprocessing operations and the unfinished operations will be processed according to the rescheduling scheme. The details of the rescheduling method are described in Section 2.6.

Figure 2.

The framework of the proposed IMA.

Figure 3.

An example of the four-layer encoding method.

Chromosome encoding

A four-layer encoding method is designed to represent the processing and reprocessing information, which includes the operation sequence vector (OS), inspection result vector (IS), factory sequence vector (FS), workshop sequence vector (WS) and machine sequence vector (MS).

Figure 3 shows an example of this encoding method. Each integer in the OS vector represents the job number, and the number of occurrences of each integer represents the total number of operations for the corresponding job. For example, the second number “2” in stage 2 indicates the second operation of job 2 (O ₂₂ ), which occurs three times, meaning that job 2 has three operations in total. Each integer in the IS vector represents the inspection result of each operation: “0” and “1” mean that the inspection results of the corresponding operations are qualified and unqualified, respectively. Integers in FS, WS, and MS vectors represent the factory, workshop and machine that are assigned to the corresponding operations, respectively. For example, the value [IS, FS, WS, MS] of O ₁₁ is [0, 2, 1, 1], which means that O ₁₁ is processed on machine 1 of workshop 1 in factory 2 and its inspection result is qualified.

Population initialization

Based on the proposed four-layer encoding operator, a new load balancing initialization method (LBM) for is designed for the IMA to obtain an initial population, aiming at to decrease the transportations among machines, workshops and factories. More specifically, if an operation can be processed on the same machine as its previous operation, it is arranged to be processed at this machine; else if an operation can be processed on another optional machine in the same workshop as its previous operation, it is arranged to be processed at another optional machine in the same workshop; else if an operation can be processed on another optional machine in another workshop of the same factory as its previous operation, it is arranged to be processed at this optional machine in this optional workshop of the same factory; else, the factory, workshop and machine with minimum accumulation processing time are selected. The core pseudocode for initialization is Algorithm 1. The core pseudo code of LBM is shown in Algorithm 1.

Algorithm 1: rule_init (job_num, pop_size, all_oper, oper_set, stage_num)

% pop_size: Population size

% job_num: The total number of jobs

% all_oper: The sum of operation for all jobs

% oper_set: The set of the number of operations for each job % stage_num: Total number of stages

1: Pop_st ← cell (1: pop_size, 1);

2: For j=1 to pop_size Do

3: num ← 0; Chrom ← zeros (8, all_oer);

4:  num ← 0; 5:  For ii=1 to stag _num Do 6:    in ← randperm(job_num); 7:    partoper1(1, num +1: job_num*ii) ←in;

8:    num ←ii*job_num; 9:  End For 10:  Chrom (1,1: all_oper) ← partoper1(1,1: all_oper);

11:  For z=1 to all_oper Do

12:  Read genes in Chrom one by one from left to right;

13:   If the current operation is the first operation of a job Then

14:   The factory fa_rank with the shortest cumulative processing time is randomly selected from the available factory     set avai_fa_set to process the current operation;

15:   The workshop wo_rank with the shortest cumulative processing time is randomly selected from the available workshop set avai_wo_set to process the current operation;

16:   The machine ma_rank with the shortest cumulative processing time is randomly selected from the available machine set avai_ma_set to process the current operation;

17:   Chrom (2:4, z) ← [fa_rank, wo_rank, ma_rank];

18:   Else

19:   [Pre_fa, Pre_wo, Pre_ma] ← [Chrom(3, z-1), Chrom(4, z-1), Chrom(5, z-1)];

20:    If Pre_fa== avai_fa_set Then

21:     If Pre_wo== avai_wo_set Then

22:      If Pre_ma== avai_ma_set Then

23:      ma_fank ← Pre_ma; wo_rank ← Pre_wo; fa_rank ← Pre_fa;

24:      Else

25:      Select an available machine ma1_rank from avai_ma at random;

26:      ma_rank ← ma1_rank; wo_rank ← Pre_wo; fa_rank ← Pre_fa;

27:      End If

28:     Else

29:     Select an available workshop wo1_rank from avai_wo_set at random;

30:     Select an available machine ma1_rank from avai_ma_set at random;

31:     ma_rank ← ma1_rank; wo_rank ← wo1_rank; fa_rank ← Pre_fa;

32:     End If

33:    Else

34:    Select an available factory fa1_rank from avai_fa_set at random;

35:    Select an available workshop wo1_rank from avai_wo_set at random;

36:    Select an available machine ma1_rank from avai_ma_set at random;

37:    ma_rank ← ma1_rank; wo_rank ← wo1_rank; fa_rank ← fa1_rank;

38:    End If

39:   Chrom (2:4, z) ← [fa_rank, wo_rank, ma_rank];

40:   End If

41:  End For

42:  Pop_st(j) ← Chrom;

43:  End For

44:  Return (Pop_st)

Chromosome decoding

In order to process each operation as early as possible and take full use of the advantages of machinable machines, an effective decoding method is employed until all chromosomes are decoded. The specific steps are as follows:

• Step 1: Determine the current decoding operation O _ij from the OS vector.

• Step 2: Identify the processing machine in workshop of factory that handle the O _ij from FW, WS, and MS vectors, separately; and determine the processing time, inspection time, and transportation time of O _ij .

• Step 3: Find one processing interval ([TS, TE]) from all processing intervals on the processing machine, where TS and TE denote the start time and end time of the processing interval, respectively. The earliest processing time T _a of O _ij is obtained by equation (18), where represents the completion time of O_i(j−1), and if j≤1, then T _a  = 0.

$$\begin{array}{c}{T}_a=\max \{T_{i(j-1)k}^c+T_f,\mathrm{TS}\}\hfill \end{array}$$

(18)

• Step 4: Using equation (19) to determine that whether O _ij can be inserted into intervals: if so, set the start time of O _ij to T _a ; else, set as T _b according to equation (20), where T _lm represents the completion time of the last operation on the selected machine. The examples of the two cases are shown in Figure 4.

$$\begin{array}{c}{T}_a+T_{\mathrm{ijfwmk}}+T{I}_{\mathrm{ij}}\le \mathrm{TE}\hfill \end{array}$$

(19)

$$\begin{array}{c}{T}_b=\max \{T_{i(j-1)k}^c+T_f,T_{\mathrm{lm}}\}\hfill \end{array}$$

(20)

• Step 5: Cyclic the above steps until all chromosomes have been decoded.

Figure 4.

Insert decoding method of the DHFSP: (a) T_a + T_ijfwmk + TI_ij≤ TE and (b) T_a + T_ijfwmk + TI_ij≥ TE.

Crossover operator

In the DHFSPR model, in order to avoid infeasible solutions and ensure the diversity of population, a stage crossing method (SCM) is designed in OS vector layer. Figure 5 shows an example of SCM, where P1 and P2 represent the parents and C1 and C2 represent the children. The specific steps of the SCM are as follows:

• Step 1: Randomly select a stage (Stage 2 in the example) from all stages of P1 to be crossed; and randomly select two positions (Position 1 = 2 and Position 2 = 4 in the example) from this selected stage.

• Step 2: The gene segment between Position 1 and Position 2 in P1 is [4, 1, 3], and the corresponding operations are O₄₂, O₁₂, O₃₂.

• Step 3: Randomly select a stage (Stage 1 in the example) from all stages of P2; select the same genes as [4, 1, 3] in the selected stage of P2 from the left to right, which is [3, 4, 1].

• Step 4: Replace the genes of [4, 1, 3] in P1 by the genes of [3, 4, 1] in P2 from the left to right in succession, and keep other genes in P1 unchanged to generate C1.

• Step 5: Replace the genes of [3, 4, 1] in P2 by the genes of [4, 1, 3] in P1 from the left to right in succession, and keep other genes in P2 unchanged to generate C2.

Figure 5.

An illustration of the SCM.

Mutation operators

A two-stage mutation operator (TMO) is proposed for the OS and a random-gene mutation operator (RGM) was designed for FS, WS and MS to expand the solution space while maintaining the diversity of solutions. The specific steps of TMO and RGM are as follows, where P1, P2 represent two parents, and C1, C2 represent two children.

An example of TMO for C1 is shown in Figure 6 as follows:

• Step 1: Randomly select a stage (Stage 2) from P1 in OS.

• Step 2: Randomly select two genes in P1 and obtain their positions. In the example, Position 1 = 2 and Position 2 = 4.

• Step 3: Find the gene segment between Position 1 and Position 2 in P1, which is [4,1,3]; and disrupt the sequence of the gene segment [4,1,3] in P1 and keep other genes in P1 unchanged to generate C1.

Figure 6.

An illustration of the TMO.

An example of RGM for C2 is shown in Figure 7 as follows:

• Step 1: Randomly select the same two positions from FS, WS and MS in P2. In the example, the 5th and 11th positions are selected.

• Step 2: Select an optional factory, workshop and machine for the operations in the selected two positions (5th and 11th) to replace the ones in these two positions in P2 and keep other genes in P2 unchanged to generate C2.

Figure 7.

An illustration of the TPM.

The proposed LSO

The LSO have been widely integrated into the evolutionary algorithms to expand the solution space as well as maintain the diversity of the solutions (Asadzadeh, 2015; G. Gong, Chiong, Deng, Han, et al., 2020; G. Gong, Chiong, Deng, & Luo, 2020; X. Gong, Deng, Gong, Liu, & Ren, 2018). Hence, an effective LSO is designed to reduce the maximum completion time by moving critical blocks on the critical path. The proposed LSO includes a position exchange method (PEM) and a machine exchange method (MEM) in the same stage. The probability of PEM and MEM used in the LSO is set to 50%. As shown in Figure 8(a), the critical path is [O ₄₁ ←O ₄₂ ←O ₂₂ ←O ₂₃ ], which contains three critical blocks on different machines.

Figure 8.

An example of the proposed LSO: (a) an example of the initial critical path, (b) the result of PEM, and (c) the result of MEM.

An example of PEM is shown in Figure 8(b) as follows:

• Step 1: Randomly find two adjacent operations next to each other on the critical blocks located on the critical path at the same stage. In the example, [O₂₂, O₄₂] is the selected critical block.

• Step 2: Swap operations on the key blocks to reduce the makespan. In the example, the makespan of the scheduling scheme is reduced from 64 (see Figure 8(a)) to 54 (see Figure 8(b)) by swapping operations O₂₂ and O₄₂.

An example of MEM is shown in Figure 8(c) as follows:

• Step 1: Find the critical path and the critical blocks.

• Step 2: Randomly find an operation from the critical blocks, and change its processing machine to another optional machine with minimum cumulative workload. In the example, O₂₂ is randomly selected, and the makespan of the scheduling scheme is reduced from 64 (see Figure 10(a)) to 60 (see Figure 10(c)) by changing the processing machine of O₂₂ from M4 to M3 (with minimum cumulative workload) in Stage 2 in workshop 11 of factory 1.

• Step 3: Loop through the above steps until a possible better solution is found or all the critical blocks are traversed.

Experiments and analysis

The proposed IMA for the DHFSPR was executed in MATLAB R2018a and run on a computer with an Intel Core i5 2.9 GHz and 16 GB RAM. To test the performance of IMA, a three-part experiment is carried out. Firstly, the key parameters of IMA are determined and compared with other four algorithms. Then, verify the validity of the operators proposed in this paper. Finally, the superior performance of IMA algorithm is proved by comparing with other algorithms. Each benchmark instance was run 10 times to reduce randomness in the experimental results.

Constructing the DHFSPR benchmarks

To test the effectiveness of the proposed IMA in addressing the DHFSP model, 60 new DHFSP benchmark instances (named QHs 01-60) based on some authoritative examples of traditional HFSP standards ⁶¹ were built, which can be divided into three sizes: small benchmark instances (QHs 01-20), medium benchmark instances (QHs 21-40), and large benchmark instances (QHs 41-60). In these proposed instances, the number of jobs n = {20,50,100} and the number of stages l = {5,10} constitute an n × l problem scale. Each combination of n and l generates 10 instances, and the processing time is given as a discrete uniform distribution in the interval [1,99]. Randomly generate the same number of factories and workshops for each test problem from [2, 3]. The same number of parallel machines in each stage is uniformly generated within the interval [1, 5], as shown in literature [55], in which at least one stage has two or more parallel machines. In addition, the inspection results of each operation include two types: qualified and unqualified. The operation with qualified inspection result can be directly transported to the next stage for processing, and the operation with unqualified inspection result will be reprocessed by one of its optional machines with shortest processing time. The unqualified rate of each operation is set at 3%.

For all built instances, the processing power of each machine is set to a random number of 10–20; the unit inspection time of each operation is set as a random number between 10 and 18; unit transportation time between two different factories, workshops and machines is set at 80, 40 and 20, respectively; and the operation transportation and processing power are set to 10. The constructed instances QHs 01-60 can be downloaded from: https://github.com/QiYanzu/DHFSP.

Performance metrics

To test the performance of different algorithms, there are three widely used and effective performance evaluation methods, including: the Set Coverage indicator (C-metric), ⁶⁴ Inverted Generational Distance (IGD), ⁶⁵ and Hypervolume indicator (HV). ⁶⁶ For the SC, the larger the value of C (A, B), the better the solution set of A, and vice versa; for the IGD, the lower the IGD value, the better the algorithm performance, and vice versa; and for the HV, the higher the HV value, the better the algorithm performance, and vice versa. More specific descriptions can be seen from the corresponding references.

Parameter settings

Different parameters will affect the overall performance of the algorithm, so we need to adjust the key parameters of the compared algorithms. In this paper, the Taguchi experimental design method ³¹ was used to determine the optimal parameter values of each algorithm (IMA, NNIA, NSGA-II, NSGA-III). Four levels setting of each key parameter are shown in Table 3. There are four key parameters: the population size (PS), crossover probability (CP), mutation probability (MP) and LSO probability (LP). Three instances are selected for the experiment including small-scale (QH 07), medium-scale (QH 27) and large-scale (QH 47), and the IGD is selected as the evaluation index for the experimental results.

Table 3.

Key parameter settings.

Algorithm		IMA				NNIA			NSGA-II			NSGA-III
Parameter		PS	CP	MP	LP	PS	CP	MP	PS	CP	MP	PS	CP	MP
Level	1	60	0.4	0.1	0.2	60	0.4	0.1	60	0.4	0.1	60	0.4	0.1
	2	90	0.5	0.2	0.3	90	0.5	0.2	90	0.5	0.2	90	0.5	0.2
	3	120	0.6	0.3	0.4	120	0.6	0.3	120	0.6	0.3	120	0.6	0.3
	4	150	0.7	0.4	0.5	150	0.7	0.4	150	0.7	0.4	150	0.7	0.4

Parameters calibration of IMA

According to the Taguchi experimental method, an orthogonal table is used to set the parameter combinations of the experiments (the details can refer to the Montgomery ³¹ ). In short, in the orthogonal table, the total number of occurrences of each level in each column (representing each factor) is equal; and the level combination of different rows in any two columns is different. Hence, based on the parameter settings in Table 3, we can obtain an orthogonal table with 16 degrees of freedom. As shown in Table 4, a total of 16 parameter combinations are shown in columns 2–5 and the IGD value of parameter combinations are shown in columns 6–8.

Table 4.

Orthogonal allay and results.

No.	Parameters				IGD
	PS	CP	MP	LP	QH07	QH27	QH47
1	60	0.4	0.1	0.2	0.4603	0.4603	0.4603
2	60	0.5	0.2	0.3	0.2986	0.2986	0.2986
3	60	0.6	0.3	0.4	0.3684	0.3684	0.3684
4	60	0.7	0.4	0.5	0.0798	0.0798	0.0798
5	90	0.4	0.2	0.4	0.1805	0.1805	0.1805
6	90	0.5	0.1	0.5	0.1211	0.1211	0.1211
7	90	0.6	0.4	0.2	0.3322	0.3322	0.3322
8	90	0.7	0.3	0.3	0.2074	0.2074	0.2074
9	120	0.4	0.3	0.5	0.1838	0.1838	0.1838
10	120	0.5	0.4	0.4	0.0810	0.0810	0.0810
11	120	0.6	0.1	0.3	0.3285	0.3285	0.3285
12	120	0.7	0.2	0.2	0.2719	0.2719	0.2719
13	150	0.4	0.4	0.3	0.1867	0.1867	0.1867
14	150	0.5	0.3	0.2	0.2550	0.2550	0.2550
15	150	0.6	0.2	0.5	0.1664	0.1664	0.1664
16	150	0.7	0.1	0.4	0.0276	0.0276	0.0276

Based on the results in Table 4, the rank changes of IMA parameters are shown in Figure 9. For the PS, the minimum value of IGD is found at the first level for QH 01, QH 27, and QH 47; hence, the PS is set as 150. For the CP, the minimum value of IGD is found at the fourth level for QH 27 and QH 47, and the minimum value of IGD is found at the first level for QH 07, hence, the CP is set as 0.7. For the MP, the minimum value of IGD is found at the third, first and fourth levels respectively, for QH 01, QH 27, and QH 47, but the first level of Q27 is the lowest, hence, the MP is set as 0.1. For the LP, the minimum value of IGD is found at the fourth level for QH 27 and QH 47 and at the second level for QH 07, hence, the LP is set as 0.5.

Figure 9.

Main effect of key parameter of IMA.

Based on the above result analysis, the optimal key parameters of the IMA are set as follows: PS = 150, CP = 0.7, MP = 0.1, and LP = 0.5 (see Table 5).

Table 5.

Tuning results of key parameters for comparative algorithms.

Algorithm parameter	IMA				NNIA			NSGA-II			NSGA-III
	PS	CP	MP	LP	PS	CP	MP	PS	CP	MP	PS	CP	MP
Level	4	4	1	4	4	4	4	4	4	4	4	3	4
Value	150	0.7	0.1	0.5	150	0.7	0.4	150	0.7	0.4	150	0.6	0.4

Parameters calibration of the comparison algorithms

In this paper, NNIA, ⁶⁷ NSGA-II, ⁶⁸ and NSGA-III ⁶⁹ are selected as comparison algorithms. The main reasons for choosing these three comparison algorithms are as follows: (1) all of the NNIA, NSGA-II, NSGA-III, and IMA are based on traditional genetic algorithms, so they have similar frameworks; (2) all these algorithms use the non-dominated sorting method to deal with multi-objective problems; and (3) all these algorithms are classical algorithms are usually used as the baseline algorithms to verify the effectiveness of the newly proposed multi-objective algorithms.

To ensure the fairness of the experiment, the Taguchi experiment is also used to calibrate the key parameters of the NNIA, NSGA-II and NSGA-III based on three instances (QH 07, QH 27, and QH 47). The key parameters and level settings of each algorithm are shown in Table 3. The variation trend of each parameter level of the three comparison algorithms is plotted in Figure A1. As shown in Table 5, the key parameter combinations of NNIA, NSGA-II, and NSGA-III were obtained using the same analytical method as IMA.

Evaluate the effectiveness of the proposed LSO

In order to verify the effectiveness of the LSO in the algorithm IMA, we compared the results of IMA with LSO and IMA without LSO (IMA1). A total of 40 instances (including large, medium, and small size) were solved by IMA and IMA1, and evaluated their performance against C-metric, IGD and HV. Each experiment is performed independently 10 times.

The experimental results of IMA and IMA1 are shown in Table A1 of the Appendix. It can be seen from the experimental results that the performance of IMA is obviously better than that of IMA1. Therefore, it is proved that LSO expands the solution space in the search process, improves the convergence speed of the algorithm, and enables the algorithm to obtain better solutions.

Comparison of rescheduling methods

According to the survey, there is no literature on the dynamic scheduling of operational reprocessing, so there is no suitable strategy for comparison. However, right-shift rescheduled strategy is often used to deal with dynamic scheduling problems in other scheduling problems.^70–75 Hence, in order to verify the effectiveness of the DRM to handle the remaining operations after operations reprocessing, the results obtained by using IMA with the DRM(IMA2) will be compared with those by using IMA with the right-shift rescheduled method (RRS) (IMA3). The RRS method is described as follows: after the results of the operation inspection are confirmed, each rescheduling operation is immediately scheduled to the original machine for reprocessing, and the affected operations are moved to the right accordingly.

In the experiment, a total of 40 instances (QHs 01-05, QHs 11-15, QHs 21-25, QHs 31-45, QHs 51-60) are selected, and each instance is run independently 10 times (the termination criterion was set to 100 iterations).

Based on C-metric, IGD, and HV, the final evaluation results of the IMA2 and IMA3 are shown in Table A2 of the Appendix. From the table, it can be clearly seen from the C-metric value that IMA2 is better than IMA3 in all instances; from the IGD value, it is clear that IMA2 has an overwhelming advantage over IMA3 in all instances, except for QH 11; and from the HV value, it is clear that IMA2 is better than IMA3 in all instances. Hence, based on the above results and analysis, the solution obtained by IMA2 is significantly better than that obtained by IMA3, which proves that the proposed DRM has superior performance in handling operation reprocessing.

Comparison with other algorithms

To further verify the performance of the proposed IMA algorithm, it is compared with three well-known multi-objective algorithms, namely NNIA, NSGA-II, and NSGA-III. For the fairness of the experiment, NNIA, NSGA-II, and NSGA-III used the same initialization method, crossover and mutation operators as our proposed IMA in 60 benchmark instances. The key parameters of all comparison algorithms were calibrated in Section 4.3, and the operating conditions and stopping criteria of the comparison algorithms were consistent with IMA.

To ensure the fairness and rationality of the experiment, we divided the experimental process into two parts. The first part takes 100 iterations as the stopping criterion, and each algorithm runs independently 10 times; and the second part takes the minimum average running time form the first stage for each instance, and each algorithm also runs independently 10 times.

In the first part, the comparison results based on C-metric, HV and IGD are recorded in Tables A3 and A4 of the Appendix. As can be seen from Table A3, based on C-metric, it can be seen that the proposed IMA outperforms the NNIA on most of the instances except QH 10, QH 12, and QH 31; outperforms the NSGA-II and NSGA-III on all instances. As can be seen from Table A4, based on IGD, 89%, 98%, and 98% of the instances solved by IMA are better than NNIA, NSGA-II, and NSGA-III, respectively; and based on HV, 92%, 98%, and 98% of the instances solved by IMA are better than NNIA, NSGA-II, and NSGA-III, respectively.

In the second part, the rescheduling scheme comparison results generated by four comparison algorithms based on C-metric, IGD and HV are shown in Tables 6 and 7. As can be seen from Table 6, based on the C-metric, 83%, 100%, and 100% of the instances solved by IMA were better than NNIA, NSGA-II, and NSGA-III, respectively. It can be seen from Table 7, 87%, 98%, and 100% of the instances solved by IMA based on HV are better than NNIA, NSGA-II, and NSGA-III, respectively; and based on IGD, IMA solved 89%, 90%, and 100% of the instances better than NNIA, NSGA-II, and NSGA-III, respectively.

Table 6.

C-metric of the compared algorithms under the stopping standard of the same time.

Benchmarks	Size	D:IMA	D1:NNIA	D:IMA	D2:NSGA-II	D:IMA	D3:NSGA-III
	n × l × F × W	C(D,D1)	C(D1,D)	C(D,D2)	C(D2,D)	C(D,D3)	C(D3,D)
QH 01	20 × 5 × 2 × 2	0.0000	0.6000	0.7778	0.0000	0.6667	0.0000
QH 02	20 × 5 × 2 × 2	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 03	20 × 5 × 2 × 2	0.6000	0.1250	0.9000	0.0000	1.0000	0.0000
QH 04	20 × 5 × 2 × 2	1.0000	0.0000	0.7500	0.0000	1.0000	0.0000
QH 05	20 × 5 × 2 × 2	0.5000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 06	20 × 5 × 2 × 2	0.7500	0.2000	0.8462	0.0000	1.0000	0.0000
QH 07	20 × 5 × 2 × 2	0.6667	0.0000	1.0000	0.0000	0.8889	0.0000
QH 08	20 × 5 × 2 × 2	0.7143	0.1429	1.0000	0.0000	1.0000	0.0000
QH 09	20 × 5 × 2 × 2	0.6667	0.0000	1.0000	0.0000	0.9000	0.0000
QH 10	20 × 5 × 2 × 2	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 11	20 × 10 × 2 × 2	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 12	20 × 10 × 2 × 2	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 13	20 × 10 × 2 × 2	0.3333	0.3333	1.0000	0.1667	0.8571	0.1667
QH 14	20 × 10 × 2 × 2	0.6667	0.0000	0.9167	0.0000	1.0000	0.0000
QH 15	20 × 10 × 2 × 2	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 16	20 × 10 × 2 × 2	0.0000	0.6000	1.0000	0.0000	0.8889	0.0000
QH 17	20 × 10 × 2 × 2	1.0000	0.0000	1.0000	0.0000	0.9333	0.0000
QH 18	20 × 10 × 2 × 2	1.0000	0.0000	0.9286	0.0000	1.0000	0.0000
QH 19	20 × 10 × 2 × 2	0.8333	0.0833	1.0000	0.0000	1.0000	0.0000
QH 20	20 × 10 × 2 × 2	1.0000	0.0000	1.0000	0.0000	0.7500	0.0000
QH 21	50 × 5 × 3 × 3	0.5000	0.0000	0.9333	0.0000	1.0000	0.0000
QH 22	50 × 5 × 3 × 3	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 23	50 × 5 × 3 × 3	0.6667	0.0000	1.0000	0.0000	1.0000	0.0000
QH 24	50 × 5 × 3 × 3	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 25	50 × 5 × 3 × 3	0.5714	0.5000	0.9286	0.0000	1.0000	0.0000
QH 26	50 × 5 × 3 × 3	1.0000	0.1333	1.0000	0.0000	1.0000	0.0000
QH 27	50 × 5 × 3 × 3	0.5000	0.2000	1.0000	0.0000	1.0000	0.0000
QH 28	50 × 5 × 3 × 3	0.6000	0.5000	0.6000	0.2500	1.0000	0.0000
QH 29	50 × 5 × 3 × 3	1.0000	0.0769	1.0000	0.0000	1.0000	0.0000
QH 30	50 × 5 × 3 × 3	0.8571	0.0000	1.0000	0.0000	0.9333	0.0000
QH 31	50 × 10 × 3 × 3	0.7500	0.3750	0.9500	0.1250	1.0000	0.0000
QH 32	50 × 10 × 3 × 3	0.2000	0.5000	1.0000	0.0000	1.0000	0.0000
QH 33	50 × 10 × 3 × 3	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 34	50 × 10 × 3 × 3	1.0000	0.0000	0.9000	0.0000	0.8571	0.0000
QH 35	50 × 10 × 3 × 3	0.0000	0.7000	1.0000	0.0000	1.0000	0.0000
QH 36	50 × 10 × 3 × 3	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 37	50 × 10 × 3 × 3	1.0000	0.0000	0.9565	0.0000	1.0000	0.0000
QH 38	50 × 10 × 3 × 3	1.0000	0.0909	1.0000	0.0000	1.0000	0.0000
QH 39	50 × 10 × 3 × 3	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 40	50 × 10 × 3 × 3	0.6667	0.0000	1.0000	0.0000	1.0000	0.0000
QH 41	100 × 5 × 4 × 4	0.3333	0.0667	1.0000	0.0000	1.0000	0.0667
QH 42	100 × 5 × 4 × 4	0.8333	0.0625	1.0000	0.0000	1.0000	0.0000
QH 43	100 × 5 × 4 × 4	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 44	100 × 5 × 4 × 4	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 45	100 × 5 × 4 × 4	1.0000	0.0000	0.9231	0.0000	1.0000	0.0000
QH 46	100 × 5 × 4 × 4	0.8571	0.0000	1.0000	0.0000	1.0000	0.0000
QH 47	100 × 5 × 4 × 4	0.8571	0.1250	1.0000	0.0000	1.0000	0.0000
QH 48	100 × 5 × 4 × 4	0.2857	0.3750	1.0000	0.0000	1.0000	0.0000
QH 49	100 × 5 × 4 × 4	0.6667	0.2000	1.0000	0.0000	1.0000	0.0000
QH 50	100 × 5 × 4 × 4	0.7500	0.0000	1.0000	0.0000	1.0000	0.0000
QH 51	100 × 10 × 4 × 4	0.7500	0.3750	0.9500	0.0000	1.0000	0.0000
QH 52	100 × 10 × 4 × 4	0.3333	0.3636	0.8750	0.0000	0.7000	0.0000
QH 53	100 × 10 × 4 × 4	0.7500	0.3000	1.0000	0.0000	0.9000	0.0000
QH 54	100 × 10 × 4 × 4	0.0000	0.8000	1.0000	0.0667	1.0000	0.0000
QH 55	100 × 10 × 4 × 4	0.0000	0.5385	0.9091	0.0000	0.6250	0.0769
QH 56	100 × 10 × 4 × 4	1.0000	0.1429	1.0000	0.0000	0.8000	0.0000
QH 57	100 × 10 × 4 × 4	0.2000	0.5000	0.5455	0.1000	1.0000	0.0000
QH 58	100 × 10 × 4 × 4	1.0000	0.0000	1.0000	0.0000	1.0000	0.0000
QH 59	100 × 10 × 4 × 4	0.0000	0.0000	0.9444	0.0000	0.8000	0.0000
QH 60	100 × 10 × 4 × 4	1.0000	0.0000	0.9000	0.0000	1.0000	0.0000
Win numbers (Rate)		50 (83%)	10 (17%)	60 (100%)	0 (0%)	60 (100%)	0 (0%)

Note. The bold font represents superior individual data and the underlined entries represent data with the same results.

Table 7.

HV and IGD value of the compared algorithms under the stopping standard of the same time.

Benchmarks	HV				IGD
	IMA	NNIA	NSGA-II	NSGA-III	IMA	NNIA	NSGA-II	NSGA-III
QH 01	0.1383	0.1248	0.0829	0.1055	0.0572	0.0929	0.1853	0.1053
QH 02	0.0312	0.0183	0.0066	0.0160	0.0000	0.3538	0.7721	0.4157
QH 03	0.0242	0.0420	0.0201	0.0112	0.2015	0.0261	0.3772	0.4376
QH 04	0.0248	0.0167	0.0205	0.0101	0.1551	0.3208	0.1035	0.4678
QH 05	0.1597	0.1688	0.0780	0.1004	0.0295	0.0295	0.5037	0.3750
QH 06	0.1212	0.1094	0.0695	0.0410	0.0380	0.1288	0.2504	0.4254
QH 07	0.0200	0.0107	0.0059	0.0069	0.0000	0.3933	0.6974	0.5916
QH 08	0.0231	0.0260	0.0059	0.0091	0.0536	0.0446	0.6666	0.5279
QH 09	0.0188	0.0378	0.0028	0.0077	0.3357	0.0000	0.7859	0.6375
QH 10	0.0240	0.0195	0.0183	0.0081	0.0000	0.1401	0.1816	0.5234
QH 11	0.0405	0.0248	0.0180	0.0152	0.0000	0.2274	0.3629	0.3809
QH 12	0.0498	0.0071	0.0245	0.0169	0.0000	0.4067	0.2902	0.2710
QH 13	0.1226	0.1395	0.0955	0.1084	0.0620	0.0401	0.2499	0.1617
QH 14	0.0179	0.0158	0.0123	0.0090	0.1413	0.2139	0.3466	0.3944
QH 15	0.0226	0.0138	0.0066	0.0079	0.0000	0.3129	0.5722	0.4989
QH 16	0.0356	0.0349	0.0170	0.0210	0.1124	0.1900	0.3044	0.2276
QH 17	0.0453	0.0320	0.0247	0.0189	0.1183	0.2268	0.3508	0.4008
QH 18	0.0352	0.0171	0.0198	0.0075	0.0000	0.2524	0.3134	0.5077
QH 19	0.0296	0.0438	0.0082	0.0112	0.1046	0.1962	0.4275	0.4044
QH 20	0.1132	0.0653	0.0854	0.0535	0.1538	0.5040	0.3427	0.5010
QH 21	0.0225	0.0137	0.0228	0.0075	0.3434	0.3378	0.2085	0.5014
QH 22	0.1772	0.1346	0.1005	0.0946	0.0000	0.0847	0.2521	0.2852
QH 23	0.0823	0.0533	0.0178	0.0130	0.0276	0.1623	0.5394	0.5105
QH 24	0.0293	0.0191	0.0158	0.0067	0.0000	0.3099	0.3894	0.6791
QH 25	0.0131	0.0128	0.0084	0.0067	0.0395	0.1176	0.2803	0.4042
QH 26	0.0294	0.0254	0.0127	0.0079	0.0000	0.1302	0.5229	0.6884
QH 27	0.0278	0.0253	0.0122	0.0169	0.0000	0.0623	0.4387	0.3785
QH 28	0.0129	0.0088	0.0074	0.0063	0.0122	0.1815	0.1885	0.2381
QH 29	0.0169	0.0133	0.0040	0.0094	0.0000	0.1222	0.6236	0.2608
QH 30	0.0167	0.0280	0.0034	0.0083	0.2487	0.0918	0.7268	0.5727
QH 31	0.0150	0.0127	0.0091	0.0028	0.1225	0.2200	0.2854	0.6565
QH 32	0.0172	0.0172	0.0077	0.0084	0.0618	0.1384	0.5221	0.3507
QH 33	0.0088	0.0068	0.0045	0.0046	0.0000	0.2521	0.4184	0.3589
QH 34	0.0229	0.0119	0.0082	0.0152	0.4044	0.4941	0.2161	0.4098
QH 35	0.0229	0.0228	0.0150	0.0117	0.0222	0.0393	0.2223	0.4228
QH 36	0.0121	0.0076	0.0035	0.0046	0.0000	0.3218	0.6290	0.4947
QH 37	0.0536	0.0427	0.0599	0.0417	0.2983	0.4175	0.0613	0.3456
QH 38	0.0290	0.0222	0.0041	0.0035	0.0000	0.1609	0.8262	0.8750
QH 39	0.0375	0.0289	0.0070	0.0135	0.0000	0.1837	0.8116	0.5460
QH 40	0.0353	0.0338	0.0253	0.0257	0.0178	0.0451	0.2107	0.1647
QH 41	0.0062	0.0037	0.0026	0.0034	0.0124	0.1552	0.3586	0.1977
QH 42	0.0310	0.0275	0.0134	0.0064	0.0491	0.1423	0.4200	0.6163
QH 43	0.0172	0.0066	0.0046	0.0043	0.0000	0.5025	0.6667	0.5417
QH 44	0.1192	0.0807	0.0685	0.0816	0.0000	0.2072	0.2761	0.1943
QH 45	0.1626	0.0983	0.1027	0.0751	0.2807	0.3313	0.1883	0.3124
QH 46	0.0256	0.0396	0.0035	0.0109	0.1455	0.1040	0.7211	0.4313
QH 47	0.0153	0.0117	0.0071	0.0019	0.0000	0.1048	0.3860	0.8023
QH 48	0.0160	0.0152	0.0066	0.0056	0.0068	0.0425	0.5165	0.5987
QH 49	0.0218	0.0184	0.0083	0.0059	0.0389	0.1139	0.5137	0.5966
QH 50	0.0182	0.0136	0.0105	0.0118	0.0000	0.1275	0.2291	0.1898
QH 51	0.0241	0.0238	0.0240	0.0026	0.0559	0.0978	0.1853	0.7435
QH 52	0.0115	0.0149	0.0123	0.0100	0.1226	0.0710	0.1309	0.1740
QH 53	0.0135	0.0100	0.0079	0.0093	0.1425	0.2267	0.3009	0.1548
QH 54	0.0105	0.0102	0.0078	0.0078	0.0326	0.0732	0.1837	0.2073
QH 55	0.0099	0.0095	0.0062	0.0069	0.0104	0.1280	0.2787	0.1833
QH 56	0.1336	0.0958	0.0787	0.0884	0.1218	0.2411	0.2253	0.1519
QH 57	0.0113	0.0105	0.0100	0.0084	0.0252	0.0736	0.0664	0.1955
QH 58	0.0653	0.0196	0.0101	0.0032	0.0000	0.5589	0.6769	0.8301
QH 59	0.0505	0.0311	0.0249	0.0164	0.4177	0.5810	0.2212	0.3580
QH 60	0.0213	0.0155	0.0169	0.0015	0.2472	0.3287	0.2538	0.6373
Win numbers (Rate)	51 (85%)	8 (13%)	1 (2%)	0 (0%)	47 (78%)	7 (11%)	6 (10%)	0 (0%)

Note. The bold font represents superior individual data and the underlined entries represent data with the same results.

Therefore, based on the experimental results of the above two parts, it can be concluded that the IMA proposed in this paper is significantly better than the comparison algorithm in terms of convergence, distribution, and quality of non-dominated solutions under the same number of iterations and the same running time, which confirms the high performance of IMA algorithm in solving DHFSP.

To better demonstrate the performance of IMA, Figure 10 display the mean plots of SC, IGD, and HV for four algorithms with 95% CI (confidence interval, CI), from which we can observe that the significant difference among the four algorithms. Based on the figure, the C-metric interval range of IMA is closer to 1 than that of NNIA, NSGA-III, and NSGA-II, hence IMA is superior to NNIA, NSGA-III, and NSGA-II. The overall performance order of the four algorithms for solving the scheduling scheme is as follows: IMA > NNIA > NSGA-II > NSGA-III. At the same time, Table 8 records the non-parametric statistical test of Wilcoxon’s signed rank test at 95% confidence level, indicating significant differences between IMA and the comparison algorithms, because the p-values are far less than 0.05.

Figure 10.

Mean plots with 95% CI in terms of C-metric, HV and IGD results of four algorithms.

Table 8.

Wilcoxon signed-rank test.

	p-Value (C-metric)	p-Value (HV)	p-Value (IGD)
p-Value (IMA, NNIA)	1.60E-08	2.80E-05	5.49E-08
p-Value (IMA, NSGA-II)	3.09E-12	5.15E-11	9.08E-10
p-Value (IMA, NSGA-III)	1.15E-12	1.63E-11	2.44E-11

In order to visually display the distribution of non-dominated solutions of the algorithm, nine instances (QH 07, QH 12, QH 22, QH 26, QH 30, QH 35, QH 41, QH 47, QH 58) are randomly selected and their Pareto front (PF) distributions were drawn in Figure 11. It can be seen from Figure 11(a) to (i) that the PFs distribution of IMA is closer to the bottom of the graph, indicating that the solution obtained by IMA has a higher probability to dominate the solutions obtained by other three algorithms.

Figure 11.

PF results of selected instances: (a) QH 07, (b) QH 12, (c) QH 22, (d) QH 26, (e) QH 30, (f) QH 35, (g) QH 41, (h) QH 47, and (i) QH 58.

Figures 12 and 13 show two Gantt charts of the initial scheduling scheme and rescheduling scheme generated by IMA for QH01. It can be seen from Figure 13 that all operations are inspected after processing, and O ₃₁ , O ₄₂ , and O ₁₂₂ are required to be reprocessed according to the inspection results. The inspection results and rescheduling process are as follows:

• The first operation O ₃₁ of job 3 and the second operation O ₄₂ of job 4 need to be reprocessed (the inspection results of O ₃₁ and O ₄₂ in Figure 13 are marked in red). According to Strategy 1 in Section 2.6, machinable machines should be found at the same stage and arranged on the earliest machinable machines. As shown in Figure 13, O ₃₁ is inserted into O ₁₂₁ on M1 of Workshop12 for processing and is marked as O₃₁′, O ₄₂ is inserted into O ₅₂ on M4 of Workshop21 for processing and is marked as O₄₂′; and the subsequent affected operations of jobs 3 and 4 are shifted to the right accordingly.

• The second operation O ₁₂₂ of job 12 also need to be reprocessed. According to Strategy 3 in Section 2.6, O₁₂₂ should be operated after the inspection and reprocessing immediately. The subsequent affected operations of job 12 should be shifted to the right accordingly.

Figure 12.

An initial scheduling scheme of QH 01 with IMA before rescheduling.

Figure 13.

A rescheduling scheme of QH 01 with IMA after rescheduling.

The check results of all other job operations are qualified (the test results are marked in green in Figure 13), that is, keep the latest scheduling scheme unchanged and continue to process the unprocessed operations of other jobs.

Conclusions

In this paper, we have presented a new model of DHFSPR – distributed hybrid flow shop scheduling with operation inspection and reprocessing. This model is the first to consider operation inspection and reprocessing in the context of distributed hybrid flow shop scheduling. We proposed an IMA algorithm to solve the DHFSPR aiming at minimizing the makespan and total energy consumption simultaneously. In the IMA, a four-layer encoding method and a new load balanced initialization method were proposed to expand the solution space while maintaining the diversity of the population; a random stage crossover operator and a two-stage mutation operator were designed to expand the search space of the solutions; an LSO containing two methods was proposed to improve the local search ability and convergence speed of the IMA; and a DRM was designed to deal with the unqualified operations.

In the experimental part, we first constructed 60 benchmark instances based on some HFSP classic benchmark instance to test the performance of the algorithm. To be fair, the key parameters of IMA and other three compared algorithms (NNIA, NSGA-II and NSGA-III) were calibrated by using the Taguchi method. In addition, 40 large, medium and small cases were selected to verify the effectiveness of the proposed LSO and DRM. Furthermore, extensive comparisons were carried out between our proposed IMA and three well-known algorithms based on the 60 constructed benchmark instances. From these experimental results, we can see that the IMA is significantly better than other three compared algorithms based on the C-metric, IGD and HV evaluation indexes.

Our work has both theoretical and practical contributions. In theory, we have pioneered a new research direction of the DHFSP, which considers the real production factors of operational inspection and reprocessing for the first time. From the perspective of practical application, the DHFSPR model can help production managers to deal with unqualified operations, avoiding unreasonable material distribution and unnecessary waste of production resources, so that to improve productivity and resource utilization.

In the future, we will study the DHFSPR in more detail. For example, the changes of delivery times and inventory capacity, and the shortages of raw materials may be taken into consideration.