Multi-flexible integrated scheduling algorithm for multi-flexible integrated scheduling problem with setup times

1.   Introduction

Scheduling is a critical factor for the efficiency of production manufacturing systems. The main studies of scheduling basically include two important stages: part processing and product assembly. The traditional scheduling approaches usually regard them as independent of each other, such as the flow shop scheduling for mass product production, the job shop scheduling (JSS) for various of types of small-batch parts or components and the assembly sequence planning (ASP) for final assembly or subassemblies. With the pursuit of the individuation and customization of complex products, make-to-order production has become one of the essential production modes in enterprises. Especially for some complex, large and heavy products such as the heavy machine tool, medical equipment and large military equipment, they are generally customized with single or minimal orders, and JSS and ASP are essential to use to shorten the makespan, reduce the manufacturing cost and improve the production efficiency.

JSS is a scheduling method to generate an optimal and reasonable processing plan for components or parts, according to which the equipment resources are allocated to the processing operations for the efficient production of the enterprise. After the JSS is completed, all parts or components that need to be assembled are scheduled according to the optimal assembly plan generated by the ASP to achieve the final assembly of the product efficiently. As the critical optimization scheduling technologies, the approaches for JSS and ASP are widely studied and applied in production manufacturing.

Since the JSS problem (JSSP) has been proven to be an NP-hard combinatorial optimization problem, it has become one of the critical research subjects in the field of production manufacturing in recent decades, and plenty of approaches have been designed to solve it. Valenzuela-Alcaraz et al. ^[1] studied the JSS with no-wait operations and defined a timetabling rule by using binary chains to make it automatically optimized during the evolution of the proposed coevolutionary algorithm. Salido et al. ^[2] proposed a model to analyze the relationship among energy efficiency, robustness and makespan, and they used CPLex to solve the JSSP with machines with different working speeds. Dai et al. ^[3] proposed an enhanced EDA to solve the JSSP in consideration of transportation constraints, with the aim of reducing energy consumption. Hao et al. ^[4] proposed multi-objective EDA for the bi-criteria stochastic JSSP. Wang and Wang ^[5] studied the two-objective JSS model with a hybrid genetic algorithm. Nguyen et al. ^[6] adopted cooperative coevolution genetic programming to solve the dynamic multi-objective JSSP. Meanwhile, the approaches for ASP (ASPP) have been studied and applied. Wang et al. ^[7] proposed a dual Q-learning-based algorithm to solve the ASPP with uncertain assembly times. Ying et al. ^[8] studied ASP in consideration of the physical characteristics of robotic arms in a cyber-physical assembly system. De Giorgio et al. ^[9] proposed online reinforced learning for ASP with interactive guidance systems.

With the improvement of manufacturing technology and manufacturing environments, such as the flexible machining center and the CNC, flexible manufacturing is becoming more and more common, and the research on flexible product scheduling is becoming more critical. As respective extensions of JSS and ASP, flexible JSS (FJSS) and flexible ASP (FASP) are applied to flexible manufacturing, in which an operation has at least one available machine for processing and is allowed to choose any machine among them. The approaches for solving the FASP problems and the FJSS problems are also widely investigated.

Baykasoglu and Madenoglu ^[10] proposed a greedy randomized adaptive search for dynamic FJSS. Furthermore, Baykasoglu et al. ^[11] applied the greedy randomized adaptive search procedure for the dynamic FJSS problem by considering preventive maintenance activities. Vital-Soto et al. ^[12] built a mathematical model and proposed a hybridized bacterial foraging optimization algorithm for the FJSS problem with sequencing flexibility. Gong et al. ^[13] proposed a hybrid artificial bee colony (ABC) algorithm for the FJSS problem with worker flexibility. Li et al. ^[14,15] proposed a reinforcement learning-based RMOEA/D and a self-adaptive multi-objective evolutionary algorithm for the FJSS problem with fuzzy processing time. Liu et al. ^[16] proposed a hierarchical and distributed architecture to achieve real-time control of the dynamic FJSS and solve the problem by using a double deep Q-network algorithm-based approach. Lei et al. ^[17] proposed an end-to-end deep reinforcement framework to automatically learn a policy for solving FJSS problems and embedded the local state encountered by using a graph neural network. Du et al. ^[18] proposed a hybrid multi-objective optimization algorithm for the estimation of distribution and a deep Q-network to solve the FJSS problem; it considers both the maximum completion time and total electricity price. For FASP, Hottenrott et al. ^[19] studied the flexible assembly layouts in smart manufacturing and provided a framework based on analytical insight and chance-constrained problem formulation. Li et al. ^[20] proposed an iterative widen heuristic beam search algorithm to minimize the makespan. Finetto et al. ^[21] proposed a mixed-model sequencing optimization algorithm for fully FASP.

The above studies on FJSS and FASP problems only focus on pure processing and pure assembly, which may lead to a large gap generated by inventory time between the processing stage and the assembly stage during the entire production process. To avoid this problem, flexible assembly JSS (FAJSS) has been put forward and studied to consider the processing operations with some assembly operations simultaneously in flexible manufacturing to further eliminate the gap and shorten the makespan.

Ren et al. ^[22] proposed an energy-aware hybrid algorithm based on particle swarm optimization (PSO) and a genetic algorithm (GA) to address the multi-objective FAJSS problem and improve production efficiency and minimize energy consumption. Lin et al. ^[23] studied the FAJSS problem in consideration of tight job constraints and designed a GA-based algorithm to minimize the makespan. Fattahi et al. ^[24] established a mathematical model and proposed a hybrid algorithm based on PSO and a parallel variable neighborhood search algorithm for the FAJSS problem with the purpose of minimizing the makespan. Wu et al. ^[25] improved the differential evolution algorithm and applied it to solve the FAJSS problem in a distributed environment. Zhang and Wang ^[26] designed a constraint programming model and solved the FAJSS problem considering both sequence-dependent setup times and part sharing in a dynamic environment, with the objective of minimizing the maximum completion time of all jobs. Li et al. ^[27] improved the ABC algorithm and applied it to solve the FAJSS problem with batch-scheduling to reduce switching costs in the job processing stage.

Although the above investigations tend to study assembly operations during the processing stage, the processing operations and the assembly operations of these studies are usually assigned to different machines. Meanwhile, current research rarely considers all assembly operations and never takes the reprocessing operations of subassembly into account. Therefore, to further make up for the above deficiencies, integrated scheduling (IS) has been proposed and studied; the interaction between assembly operations and processing operations is fully considered simultaneously.

Xie et al. ^[28] investigated an IS problem with no-wait operations and solved it with their proposed hybrid algorithm. Xie et al. ^[29] proposed a dispatching rule-based algorithm to address the IS problem in consideration of the maintenance of machines. Xie et al. ^[30] investigated an IS problem in two-workshop and designed an IS algorithm by considering the prescheduling of the root-subtree processes. Xie et al. ^[31] studied an IS problem with a pre-start device and proposed an idle machine-driven-based algorithm with the objective of minimizing the completion time of products. Zhan et al. ^[32] proposed an IS algorithm based on the end time driven and processing area priority to solve a two-workshop collaboration IS problem. Gao et al. ^[33] fully considered the characters of the tree structure and proposed a GA-based hybrid algorithm to solve the IS problem. Wang et al. ^[34] applied a non-dominated sorting genetic algorithm-Ⅱ with a hybrid chromosome coding mechanism to solve the IS problem, aiming to minimize the total production completion time and the total inventory time.

Besides the above investigations, the flexible IS problem (FISP) has been investigated to optimize the scheduling sequence of all operations simultaneously in flexible manufacturing, regardless of whether the operation belongs to the part processing operations, the assembly operations or the assembly reprocessing operations. Some approaches for FISPs are as follows.

Gao et al. ^[35] presented a GA-based algorithm with remaining work probability selection coding to solve the FISP. Xie et al. ^[36] proposed a device-driven and essential path-based integrated algorithm to solve the FISP. Xie et al. ^[37] proposed a device-driven based conflict mediation algorithm to solve the FISP. Lu et al. ^[38] investigated the order review/release and dispatching rules to solve the FISP by using a simulation approach. Xie et al. ^[39] proposed a shorten-time-based algorithm to simplify the FISP into an IS problem and solved it with the allied critical path method. Xie et al. ^[40] adopted the layer priority-based integrated algorithm to solve the FISP in the reverse order.

Actually, the high flexibility characteristic of flexible manufacturing is not only specific to the equipment. There can be more than 15 flexibility types in a flexible manufacturing system ^[41], such as a flexible variable disturbance ^[42], a flexible sequence ^[12], flexible workers ^[13] and so on. Furthermore, flexible manufacturing with multiple types of concurrent flexibility is called multi-flexible manufacturing. However, most of the current research on FISPs only focuses on machine flexibility. For some complex products, especially those with a treelike structure, due to the complex product structure, the complex constraint relationship between operations and the processing characteristics of materials, alternative planning routes can be chosen to achieve the same processing effect; consequently, the tightness between some processes is enhanced. To take advantage of the flexibility of complex products and reduce the inventory time resulting from separate part processing and assembly, it is necessary to further investigate multi-flexible features for the FISP, which is much closer to the actual enterprise production activities.

Therefore, it is necessary to propose an effective algorithm to optimize the scheduling sequence for the multi-flexible integrated problem (MFISP), to further improve the efficiency and reduce the cost. Thus, we investigate the multi-flexible IS problem with setup times (MFISP), which considers flexible machines, flexible sequential operations, flexible planning paths and operation-dependent setup times. To reduce the complexity of the problem and facilitate the dynamic scheduling of the machines and operations, the machine idle time is treated as the driven time to schedule the processing operation tree in the reverse order.

The remainder of this paper is as follows. In Section 2, the problem description and mathematical model for the MFISP are presented. In Section 3, the design and implementation of four scheduling strategies are given. In Section 4, the implementation of the multi-flexible integrated scheduling algorithm (MFISA) is given, and the complexity analysis of the algorithm is in Section 5. In Section 6, experiments are carried out to test the performance and the efficiency of the proposed algorithm for the MFISP and FISP. Finally, the conclusions and future research work are given.

2.   Problem description and mathematical models

2.1.   Problem description

To make IS problems more general, the assembly machines and the machining machines are not distinguished according to their functions, but are uniformly called machines. By default, each machine can have capacities of both assembly and machining. The machining operations and the assembly operations are collectively known as operations. To better describe the MFISP, we introduce the following concepts.

Definition 1. (Flexible planning path group) If different planning paths can be selected from one operation to another, then the set of all of these paths is called the flexible planning path group. The paths are called the flexible planning paths.

Definition 2. (Flexible sequential operation group) If there are non-strict precedence constraints between the operations involved in a path from one operation to another, then the set of the involved operations is called the flexible sequential operation group. The involved operations are called the flexible sequential operations.

Definition 3. (Flexible operation) The operations that belong to the flexible planning path group or the flexible sequential operation group are collectively referred to as the flexible operations. The first operation of a flexible planning path is called the first-position flexible operation.

Definition 4. (Setup time) The waiting time required for the machine on which different types of operations are processed successively is called the setup time.

In the multi-flexible IS system, at least one machine is available for each operation and the processing time required is not necessarily the same for each machine. Each operation can only choose one machine to be processed. The waiting time between different types of operations on the same machine should not be less than the corresponding setup times. And, the flexible planning path groups and the flexible sequential operation groups can be expressed by the OR sub-graphs and the AND sub-graphs on a processing operation tree, respectively, as shown in Figure 1. The node information of a special-type operation becomes four components (i.e., operation number/machine number/processing time/operation type). The operations in the flexible sequential operation groups are for the same workpiece, so there is no overlapping processing time. As different planning paths in a flexible planning path group can achieve the same processing effect, only one planning path can be selected from the same flexible planning path group.

2.2.   Mathematical model

Based on the description of the MFISP, the assumptions are as follows.

1) The information on the machines, the processing time, the operations types, the setup times and the precedence constraints between operations is all given.

2) The processing of each operation cannot be interrupted. If it is interrupted, the operation must be reprocessed.

3) The breakdown of machines will not happen, and the migration time of each workpiece between different machines is negligible.

Then, the constraints of the MFISP are as follows.

1) The starting time of each operation must be no earlier than the ending time of its predecessors.

2) The starting time of each operation cannot be earlier than the maximum completion time of the previous operations on the same machine.

3) In each flexible planning path group, only one flexible planning path can be chosen.

4) There must be no overlapping processing times between operations in each flexible sequential operation group.

According to the assumptions and constraints, the established mathematical model and symbols of the MFISP are described as follows, where the symbols and indices are shown in Table 1.

Constraint conditions:

Equation (1) ensures that all non-flexible operations will inevitably be performed on one machine. Equation (2) further illustrates that some operations may not be performed. Equations (1) and (2) reflect the characteristics of route flexibility in the MFISP. Equations (3) and (4) ensure that the processing time and the starting time of each operation are only related to the selected machine. They reflect the characteristics of machine flexibility. Equation (5) illustrates the relationship between the processing time, the starting time and the completion time of each operation. It reflects the time characteristics of operations. Equation (6) ensures that the operations on any flexible planning path are either all or not processed. Equation (7) ensures that only one flexible planning path can be selected in each flexible planning path group. Equations (6) and (7) reflect the constraint (3). Equations (8) and (9) ensure that each operation must comply with the precedence constraint between operations, that is, each operation can only start after the completion of its immediate predecessor operations. They reflect the constraint (1). Equation (10) prevents the overlapping of operations on each machine with consideration of setup times. It reflects the characteristics of setup times and the constraint (2). Equation (11) ensures that the processing times of the operations in the same flexible sequential operation group cannot overlap, that is, the operations are serial processing. It reflects the constraint (4). Equations (12) and (13) ensure that the completion time and the starting time have practical significance.

This work was aimed to reduce the makespan of the product as the ultimate goal to solve the MFISP. The objective function is shown in Eq (14).

where C indicates the completion time of the product, which is equal to the maximum completion time of all operations.

3.   Design and analysis of scheduling strategies

In order to keep the makespans of the complex products in the MFISP as short as possible, it is necessary to select the appropriate machine for each operation on the premise of satisfying the precedence constraints. It is also necessary to consider the choice of the flexible planning paths and the serial processing relationship between the operations in each flexible sequential operation group. Therefore, the algorithm proposed in this paper should consider four requirements: a. Uncouple the flexible operations from the flexible sequential operation groups and the flexible planning paths; b. Reduce the backsliding and the stacking of serial operations on the critical paths; c. Reasonable arrangement of the parallel operations; d. Preemption of busy machines by certain operations. Hence, the algorithm in this paper reduces the complexity of the problem and makes the scheduling procedure dynamic by adopting reverse-order scheduling of the processing operation tree and driving scheduling events at each machine's idle time. The idle moment for a machine is known as the driven time, at which a new scheduling event occurs. Meanwhile, four corresponding scheduling strategies have been designed and adopted: a. Flexible operation determination strategy (FODS); b. Operation optimization allocation strategy (OOAS); c. Parallel optimization strategy (POS); d. Potential operation preemptive strategy (POPS). Among these strategies, the FODS is a supplementary strategy to the dispatching strategies OOAS and POS. Since flexible operations are involved in each round of dispatching, it is necessary to determine the category of the flexible operation so as to determine whether the operation can be set as a planned operation for an optimal planning path or an optimal order. In addition, for the flexible operation of the flexible planning path group, the optimal path and the optimal machine are dynamic, so it is necessary to use the FODS to dynamically judge the operation to match the corresponding machine in order to achieve the current optimal scheduling effect.

3.1.   Relevant concepts and definitions

Definition 5. (Competitive operation) At a driven time, there is a schedulable operation for an idle machine. If the earliest completion time of the operation on this machine is earlier than the earliest completion time on any other available machine, then the operation is known as a competitive operation for the idle machine.

Definition 6. (Planned operation) At a driven time, an operation that the idle machine plans to process is known as the planned operation of the idle machine.

Definition 7. (Quasi-schedulable operation) At a driven time, an operation whose immediate predecessors are being processed or starting to be processed is called the quasi-schedulable operation.

Definition 8. (Potential operation) For a planned operation, if the static starting time of a quasi-schedulable operation on the same machine is less than its completion time, then the quasi-schedulable operation is known as the potential operation for the planned operation. The static starting time of an operation is equal to the maximum completion time of its immediate predecessors.

Definition 9. (Relative subsequent path) The path with the longest average length involved from all immediate successors of operation i to the leaf nodes is called the relative subsequent path (RSP) of operation i. The length formula of the relative subsequent path is shown in Eq (15).

where l_i indicates the length of the relative subsequent path of operation i; O_{i, g, h} indicates the set of operations on the g^th path from an immediate successor of operation i to the h^th reachable leaf node; OF_i is the set of successors of operation i; G_{i, h} indicates the total number of paths from the immediate successor of operation i to the h^th reachable leaf node; M_i' is the set of the available machines of operation i'; | M_i'| is the number of available machines of operation i'.

Definition 10. (Competition indicator of potential operation) The indicator to measure the competitiveness of potential operations i' compared to the corresponding planned operation i is called the competition indicator of potential operation i'. It can be computed by using Eq (16).

${c_i}_{, {k_0}}$ is the completion time of planned operation i on machine k₀ at a driven time; l_i indicates the length of the relative subsequent path of operation i; $\mathop {\min }\limits_{k' \in {M_{i'}}} ({c_{i', k'}})$ indicates the earliest completion time of operation i' among all of its available machines; l_i' indicates the length of the relative subsequent path of operation i'; ${c_{i'}}_{, {k_0}}$ is the completion time of operation i' on machine k₀ if planned operation i will not be processed on machine k₀ at the driven time; $\mathop {\min }\limits_{k \in {M_{i'}}} ({c_{i, k}})$ indicates the earliest completion time of operation i among all of its available machines.

If 0 < ${\theta _{i', i, {k_0}}}$ < $\alpha$ ($\alpha$ is suggested to be close to 1), then it indicates that, for machine k₀, potential operation i' is more competitive than planned operation i, and it has the advantage of preempting it on machine k₀; operation i is known as the interrupted operation for machine k₀ at the driven time. If ${\theta _{i', i, {k_0}}}$ > $\alpha$, then it means that planned operation i is more competitive and will not be preempted.

3.2.   Flexible operation determination strategy

3.2.1.   Design ideas

At a driven time, when an operation selected by an idle machine is a flexible operation, there are two situations: 1) If it is the first-position flexible operation, then it indicates that the planning path in the flexible planning path group is not determined. One should look for other flexible planning paths in the flexible planning path group and calculate the earliest completion time for each flexible planning path. If the flexible planning path with the earliest completion time is the path to which the operation belongs and the idle machine is the selected machine, then the operation is determined to be the planned operation for the idle machine. Otherwise, the operation will not be selected by the idle machine. 2) If the operation is a flexible sequential operation, then one should calculate the sum of the completion time of the operation and the length of its relative subsequent path. One should look for other flexible operations in the flexible sequential operation group that have no precedence constraint with it. If there is at least one of the above operations, for which the sum of the earliest completion time and the length of the subsequent path is less than its own, then it will not be selected by the idle machine. Otherwise, it is determined as the planned operation for the idle machine. This strategy realizes the purpose of determining whether the flexible operation selected at the moment is the optimal solution and shortening the completion time by dynamically selecting the flexible operation with the least serial processing at each driven time.

3.2.2.   Implementation of the strategy

The specific implementation steps of the FODS are as follows, and its flowchart is shown in Figure 2.

1) Schedule initialization and input the information on the operations and machines, the flexible sequential operation groups and the flexible planning path groups.

2) At the driven time, flexible operation i is selected by the idle machine k.

3) If the flexible operation i is the first-position flexible operation, then go to Step 5. Otherwise, go to Step 14.

4) If the flexible operation i is a flexible sequential operation, then go to Step 9. Otherwise, go to Step 14.

5) Find the flexible planning path group to which operation i belongs; calculate the earliest completion time ${C_u}$ of each flexible planning path in the group.

The specific methods to compute ${C_u}$ are as follows. At the driven time, according to the completion time of the determined operations on machines, and without considering the other operations, if the u^th flexible planning path is scheduled in the group, then the earliest completion time ${C_u} = \mathop {{ma} }\limits_{i' \in {O_u}} x(\mathop {\min }\limits_{k' \in {M_{i'}}} ({s_{i'}}_{, k'} + {p_{i', k'}}))$.

6) Select the flexible planning path with the earliest completion time.

7) If the flexible operation i is the first-position operation of the selected flexible planning path, then go to Step 8. Otherwise, go to Step 15.

8) If the idle machine k is selected by operation i on the selected flexible planning path, then go to Step 14. Otherwise, go to Step 15.

9) Calculate the sum of the completion time of operation i on machine k and the length of its relative subsequent path: (c_{i, k} + l_i).

10) Find the flexible sequential operation group j to which the flexible operation i belongs.

11) If there are other flexible operations without a precedence constraint relationship with operation i in group j, then go to Step 14. Otherwise, go to Step 12.

12) Calculate the sum of the earliest completion time for each operation on its available machines and the length of its relative subsequent path: $\mathop {\min }\limits_{k' \in {M_{i'}}} ({c_{i'}}_{, k'}) + {l_{i'}}$, where $i' \in {O_j}\& \forall (i, i'), (i', i) \notin R$.

13) If there is an operation i' that satisfies the condition $\mathop {\min }\limits_{k' \in {M_{i'}}} ({c_{i'}}_{, k'}) + {l_{i'}} \lt {c_{i, k}} + {l_k}$, then go to Step 15. Otherwise, go to Step 14.

14) If the idle machine k still chooses the flexible operation i, go to Step 16.

15) If the idle machine k no longer selects the flexible operation i, go to Step 16.

16) End.

3.3.   Operation optimization allocation strategy

3.3.1.   Design ideas

At a driven time, for an idle machine, create a set of its competitive operations if they exist in the schedulable operation set. According to the definition of competitive operations, all operations have the characteristics that the completion time on the idle machine is better than that on the other available machines. Therefore, choosing an appropriate competitive operation can reduce the workload of the machine. Meanwhile, to complete the operations on the critical path as early as possible and avoid the accumulation of a large number of schedulable operations with priority constraints due to deferred processing, the principle of the relative long subsequent path (RLSP) has been designed and adopted in the OOAS. Select the operation with the longest relative subsequent path from the competitive operation set; if the operation is not unique, then select the operation with the earliest completion time. If the operation is still not unique, then the operation with a short setup time is preferred. If the selected operation is a flexible operation, then the FODS is adopted to determine whether the operation is still selected by the idle machine. If the operation is abandoned, then select another operation for the machine according to the principle of the RLSP. If all of the idle machines are executed in the above procedure once, the first round of allocation is over. If unassigned idle machines still exist after the first round of allocation, then the second round of operation allocation continues and the operations of the first-round allocation are processed on their selected machines by default. Repeat the above implementation until all of the idle machines have assigned operations or the remaining idle machines do not have any competitive operations.

3.3.2.   Implementation of the strategy

The specific implementation steps of the OOAS are as follows, and its flowchart is shown in Figure 3.

1) Schedule initialization and input the information on the operations and machines, the idle machine set M_I and the schedulable operation set O_S. And, create two empty sets: the planned operation set O_P and the planned machine set M_P.

2) Set the initial values of the parameters: m = | M_I |, r = 1. | M_I | indicates the number of idle machines.

3) Select the r^th machine from M_I and generate its competitive operation set O_C according to the definition of the competitive operation.

4) If O_C is empty, then m- -, and go to Step 10. Otherwise, go to Step 5.

5) Select an operation from O_C based on the principle of the RLSP.

● The principle of the RLSP: Select the operation with the longest relative subsequent path from the competitive operation set. If the operation is not unique, then select the operation with the earliest completion time. If the operation is still not unique, then the operation with a short setup time is preferred.

6) If the selected operation is a flexible operation, then go to Step 7. Otherwise, go to Step 9.

7) Adopt the FODS, and if the machine still selects the operation, then go to Step 9. Otherwise, go to Step 8.

8) Remove the operation from O_C, update O_C and go to Step 4.

9) If the selected operation is determined to be the planned operation of the machine, then add the operation and the machine to O_P and M_P respectively, and remove the operation from O_S.

10) r++.

11) If r < | M_I |, then go to Step 12. Otherwise, go to Step 3.

12) If m = 0 or m = | M_I |, then go to Step 14. Otherwise, go to Step 13.

13) Update the information on the machines and operations in O_P and M_P respectively; then, remove them from M_I and go to Step 2.

14) End.

3.4.   Parallel optimization strategy

3.4.1.   Design ideas

At a driven time, for an idle machine k with no competitive operation, if it is an available machine for some planned operations, then select operation i which can be finished earliest on machine k from these operations, and mark its planned machine k'. Assign operation i to machine k temporarily. If the competitive operation set of machine k' is not empty, then select the competitive operation with the earliest completion time on machine k'. If the selected operation i' is a flexible operation, then use the FODS to determine whether the machine k' will still select it. If the selection continues, then operation i' is determined to be the new planned operation for machine k', while operation i is finally determined to be the planned operation for machine k. Otherwise, select the other competitive operation with the earlier completion time to machine k', and use the FODS to repeat the above steps. Finally, if there is no competitive operation that meets the requirements, then cancel the movement of operation i to machine k. This strategy maximizes the avoidance of the empty load of idle machines at the driven time by adjusting the scheduling of the planned operations, so as to improve the parallelism between parallel processing operations.

3.4.2.   Implementation of the strategy

The specific implementation steps of the POS are as follows, and its flowchart is shown in Figure 4.

1) Schedule initialization and input the information on the operations and machines, the idle machine set M_I, the schedulable operation set O_S, the planned operation set O_P and the planned machine set M_P.

2) Set the initial value of the parameter: r = 1.

3) Select the r^th machine k from M_I.

4) If there are operations of O_P that can be processed on machine k, then go to Step 5. Otherwise, go to Step 14.

5) Select the planned operation i that can be finished earliest on machine k and mark its original planned machine k'.

6) Generate the competitive operation set O_C for machine k'.

7) If O_C is empty, then operation i remains to be the planned operation for machine k'; go to Step 14. Otherwise, go to Step 8.

8) Select the earliest completed operation i' on machine k' from O_C.

9) If operation i' is a flexible operation, then go to Step 10. Otherwise, go to Step 12.

10) Adopt the FODS, and if machine k' still selects operation i', then go to Step 12. Otherwise, go to Step 11.

11) Remove the operation from O_C and update it; then, go to Step 7.

12) Determine operation i' as the new planned operation for machine k' and assign the planned scheduling process i to the machine k; then, update O_P and M_P.

13) Remove operation i' from O_S and update it.

14) r ++.

15) If r > | M_I |, then go to Step 16. Otherwise, go to Step 3. | M_I | is the number of machines in M_I.

16) End.

3.5.   Potential operation preemption strategy

3.5.1.   Design ideas

At a driven time, create an empty interrupted operation set. For a planned operation on its planned machine, if its potential operations exist, then compute the competition indicators of these operations in the descending order by the relative subsequent path length. If there is a potential operation for which the competition indicator is less than $\alpha$, then the planned operation on the planned machine can be interrupted by it. Otherwise, the planned operation will not be interrupted. Repeat the above procedure and add all of the interrupted operations into the interrupted operation set. This strategy makes up for the shortage of neglecting the preemption of the new schedulable operations which are generated at other driven times.

3.5.2.   Implementation of the strategy

The specific implementation steps of the POPS are as follows, and its flowchart is shown in Figure 5.

1) Schedule initialization and input the quasi-scheduling operation set O_Q, the planned operation set O_P and the planned machine set M_P; then, create an empty interrupted operations set O_I.

2) Set the initial value of the parameter: r = 1.

3) Select the r^th planned operation from O_P and generate the corresponding potential operation set O_Po according to the definition of the potential operation.

4) If O_Po is empty, then go to Step 9. Otherwise, go to Step 5.

5) Arrange the operations in O_Po in descending order according to the length of their relative subsequent paths.

6) Calculate the competition indicator for each potential operation in turn.

7) If there is an operation for which the competition indicator is less than $\alpha$, then the planned operation can be interrupted; go to Step 8. Otherwise, the planned operation will not be interrupted; go to Step 9.

8) Add the planned operation into O_I.

9) r++.

10) If r > | O_P |, then go to Step 11. Otherwise, go to Step 3. | O_P | indicates the scale of O_P.

11) End.

4.   Algorithm design and complexity

4.1.   Algorithm design and implementation

According to the above analysis of the main strategies, the implementation steps of the proposed algorithm, named MFISA, have been designed as follows.

1) Schedule initialization and input the information on the operations and machines and setup times; then, initialize the data.

2) Generate the idle machine set M_I, the schedulable operation set O_S and quasi-schedulable operation set O_Q at the drive time T_d.

● Machine status mark: There are two marks for machine status. If the machine is idle, then its status mark is 1; if the machine is occupied, then its status mark is 0. At the initial time T_d = 0, the status mark of all machines is 1.

● Operation status mark: There are three marks for operation status. If the operation is unprocessed, then the operation status is marked as 0; if the operation is completed, then the operation status is marked as 1; if the operation is under processing, then the operation status is marked as 0.5. At the initial time T_d = 0, the status mark of all operations is 1.

● Mark conversion: At driven time T_d, when an operation is assigned to a machine, the machine status mark is converted from 1 to 0 and the operation status mark is converted from 1 to 0.5. When the next driven time T_{d + 1} is confirmed, the status mark of the machine, for which the ending time is equal to T_{d + 1}, is converted from 0 to 1; and, the status mark of the corresponding operation is converted from 0.5 to 0.

● Generation of M_I: Traverse the status marks of all machines, and then add the machines with status marks of 1 to M_I.

● Generation of O_S: Traverse the status marks of all operations, and then add to O_S the operations for which the status marks are 1 and the status marks of their predecessors are 0. In particular, at the initial moment, in the processing tree, all node operations with zero-entry degree are schedulable operations. Since the MFISA adopts the reverse-order scheduling mode, only the root node operation is schedulable at the initial time.

● Generation of O_Q: Traverse the status marks of all operations and add to O_Q the operations for which the status marks are 1 and the status marks of their immediate predecessors are 0.5.

● Driven time: The moment that the status mark of a machine is converted to 1 is known as a driven time, and the scheduling system is driven to have a scheduling event, that is, a schedulable operation is decided to be assigned for the idle machines.

3) Adopt the OOAS to assign the planned operations for idle machines and generate the planned operation set O_P and the planned machine set M_P.

4) If all idle machines have been assigned planned operations, then go to Step 6. Otherwise, go to Step 5.

5) Adopt the POS to deal with the unassigned idle machines and update O_P and M_P.

6) The POPS is used to determine whether the current planned operation can be preempted by the other operations, and to generate the interrupted operation set O_I.

7) If O_I is empty, then go to Step 9. Otherwise, go to Step 8.

8) The planned machines of the operations in O_I are locked for them at T_d, that is, each operation cannot be selected by its planned machine until the next driven time. Then, update O_S, retreat all machine statuses and all operation statuses back to the driven time T_d and go to Step 3.

● The locked machine for the operation is recorded as "operation number L (machine number)". For example, the corresponding machine 3 of operation 26 is locked and recorded as 26L (3).

9) Calculate the next driven time T_{d + 1} and update the driven time T_d = T_{d + 1}. Then, update M_I, O_S and O_Q.

● The driven time ${T_{d + 1}} = \mathop {\min }\limits_{i \in {O_P}} ({c_i})$, where i is the operation in O_P; that is, the next driven time ${T_{d + 1}}$ is equal to the earliest completion time of the planned operations.

● Convert the status marks of all planned operations to 0.5 and convert the status marks of the operations for which the completion time equals to ${T_{d + 1}}$ to 0.

● Convert the status marks of all planned machines to 0 and convert the status marks of the machines for which the completion time equals to ${T_{d + 1}}$ to 1.

10) If all operations have been processed, that is, if the status mark of each operation is 0, then go to Step 11. Otherwise, go to Step 2.

11) Output the scheduling information and the Gantt chart.

12) End.

The flowchart for the MFISA is shown in Figure 6.

4.2.   Complexity analysis

The total number of operations of a complex product is set to be n, where the total number of the flexible operations is n₁, and the total number of the involved machines is m. Then, the complexities of the FODS, the POS, the POAS and the POPS involved in the MFISA are as follows:

1) In the FODS, the calculation of the earliest completion time of the flexible planning path requires n₁ times, or the calculation of the sum of the earliest completion time of the flexible sequential operation and its relative subsequent path length requires n₁ times. The comparison with the sum of the completion time of the planned operation and the relative subsequent path length requires (n₁ - 1) times. Because ${n_1} \leqslant n$, if and only if ${n_1} = n$, the complexity will be O(n).

2) There are at most m idle machines involved in the OOAS, and the calculation of the competitive operations for each machine needs nm times. Each operation needs to be sorted once to find the available machine with the shortest completion time, so nm²log₂(m) times are required in total. When adopting the principle of the RLSP, the length of the relative subsequent path needs to be calculated at most n times and be sorted once, so it requires nlog₂(n) times executions. During the execution of the OOAS, the FODS is adopted at most n₁ times. Therefore, the OOAS involves (nm²log₂(m) + nlog₂(n) + n₁ (n₁ - 1)) times executions, so the maximum complexity is O(n²) if and only if ${n_1} = n$.

3) There are at most (m - 1) idle machines involved in the POS, so, to generate the competitive process set for each planned machine, it needs to calculate the completion times at most (n - 1)m times, and each operation should be sorted once to find the machine with the shortest completion time. Thus, it requires (n-1)m²log₂(m) times executions. Then, all competitive operations need to be sorted with (n-1)log₂(n-1) times executions. During the execution of the POS, the FODS is adopted at most n₁ times. Therefore, the POS involves ((n-1)m²log₂(m) + (n-1)log₂(n-1) + n₁ (n₁-1)) times executions, so the maximum complexity is O(n²) if and only if ${n_1} = n$.

4) There are at most m planned operations that need to have the preemptive judgment in the POPS. It needs to calculate the earliest starting times for at most (n-m) operations to generate the potential operations for each planned operation. Then, it needs at most m(n-m) times for comparison with the completion times of the planned operations. In order to judge the preemption of the potential operations, the competition indicators need to be calculated (n-m) times for each planned machine, so m(n-m) times executions are required in total, and m operations are added into the interrupted operation set. Therefore, the POPS involves at most (m(n-m) + m(n-m) + m) times executions, so the complexity is O(n).

5) When a preemption event occurs at the driven time, it is necessary to lock m operations and the corresponding machines, and to reassign the operations to the idle machines at the driven time. Thus, ((n-1) + (n-2) +…+1) = n (n-1) / 2 times executions are needed in total for all driven times.

In conclusion, the complexity of the MFISA in this paper is max{n(n-1)/2 O(n), n(n-1)/2 O(n²), n(n-1)/2 O(n²), n(n-1)/2 O(n)}. Therefore, the complexity is O(n⁴) if ${n_1} = n$, or O(n³) if ${n_1} \ll n$.

5.   Experimental analysis

5.1.   Numerical example for MFISP

The above analysis and design of the MFISA are not based on a particular example, so the algorithm and strategies in this paper have more general applicability and application significance. In order to further explain the execution processing and the final effect of this algorithm, this paper will explain it through an example and highlight the scheduling procedure that involves the scheduling strategies.

The processing operation tree of a complex product A is shown in Figure 7. Each node represents an operation with three common attributes: the operation number, the available machine numbers and the processing time of each machine. In addition, the special operation contains its operation type information. Except for the ordinary operations, there are four special operation types; information on the setup times is shown in Table 2. The flexible planning path groups and the flexible sequential operation groups are represented by the AND sub-graphs and the OR sub-graphs in the processing operation tree, respectively.

Now, the MFISA with α = 0.94 is applied to solve the scheduling problem of Product A. The scheduling procedure of each driven time is shown in Table 3. To make the strategies easier to understand, a few driven times are described in detail.

First, we need to reverse the processing operation tree, that is, to perform priority scheduling of the root node and reverse scheduling along the arrow direction. At the initial time, t = 0, the schedulable operation set O_S = {1} and the idle machine set M_I = {1, 2, 3, 4}. Only Machine 2 has the competitive operation set O_C = {1}, so, according to the OOAS, Machine 2 selects Operation 1 as its planned operation. At this time, the planned operation set O_P = {1} and planned machine set M_P = {2}. Since there is no potential operation of Machine 2, the final scheduling scheme is as follows: O_P = {1} and M_P = {2}.

At t = 5, the schedulable operation set O_S = {2, 3, 4} and the idle machine set M_I = {1, 2, 3, 4}. Then, the OOAS is adopted, in the first round of allocation, the competitive operation set of Machine 1 is O_C = {2, 4}, l₂ = 122.7, l₄ = 60.7. According to the principle of the RLSP, Machine 1 selects Operation 2, and Machine 4 selects Operation 3. By updating the earliest ending time of each machine after the first round of allocation, the idle machine set M_I = {2, 3} and there is no competitive operation for them; so, the second round of allocation is not required. At this time, the planned operation set O_P = {2, 3} and planned machine set M_P = {1, 4}. Then, the POS is adopted, the planned operation 3 on the planned machine 4 is an available operation for the idle machine 2. Operation 2 is temporarily assigned to Machine 3. Meanwhile, the competition operation set of Machine 4 is {4}, so Machine 2 selects Operation 3 as the planned operation, and Machine 4 selects Operation 4 as its new planned operation. At this time, the planned operation set O_P = {2, 3, 4} and planned machine set M_P = {1, 2, 4}.

There is a potential operation set O_Po = {5, 6} for Machine 4. According to the POPS, the competition indicator for Operation 4 is ${\theta _{5, 4, 4}} = 0.907 \lt 0.94$, which means that Operation 4 may be preempted by Operation 5 on Machine 4. Then, lock Operation 4 up from being selected by Machine 4 until the next driven time. Trace all of the scheduled information back to t = 5 and reschedule the idle machines and operations at t = 5.

Backtracking to t = 5, the schedulable operation set O_S = {2, 3, 4} and the interrupted operations set O_I = {4L(4)}. According to the OOAS, the planned operation set O_P = {2, 3} and planned machine set M_P = {1, 4} are obtained. The planned operation 2 on the planned machine 1 is an available operation for the idle machine 3. According to the POS, Operation 2 is temporarily assigned to Machine 3. Meanwhile, the competition operation set of Machine 1 is {4}, so Machine 2 selects Operation 3 as the planned operation and Machine 1 selects Operation 4 as its new planned operation. Thus, the planned operation set O_P = {2, 3, 4} and planned machine set M_P = {3, 4, 1}. Since there is no potential operation set for M_P, the final scheduling scheme at t = 5 is as follows: O_P = {2, 3, 4} and M_P = {3, 4, 1}.

At t = 30, the schedulable operation set is {16/17, 26, 32/35, 41}, the idle machine set M_I = {2, 3} and the interrupted operations set O_I = {26L(4)}. Operations 16 and 17 are flexible operations in the same flexible sequential operation group, and Operations 32 and 35 are the first-position flexible operations on two flexible planning paths of the same flexible planning path group. The competitive operation set of Machine 3 is {16/17, 35, 41}, and the competitive operation set of Machine 4 is {32}. According to the OOAS, the planned operations of Machines 3 and 4 are Operations 16 and 32, respectively. Then, according to the FODS, Operation 16 is better than Operation 17, and the planning path of Operation 32 is better than that of Operation 35; so, Machines 3 and 4 still keep their selection. At this time, the planned operation set O_P = {16, 32} and planned machine set M_P = {3, 4}. Finally, according to the POPS, it is known that neither Machine 3 nor Machine 4 will be preempted, so the final scheduling scheme at t = 30 is as follows: O_P = {16, 32} and M_P = {3, 4}.

The Gantt chart is shown in Figure 8, where a gray square indicates the setup time. The final completion time of Product A is 141 hours; the selected orders for the two flexible sequential operation groups are {16$\succ$17$\succ$18} and {12$\succ$11$\succ$14$\succ$13}, and the selected planning paths of the two flexible planning path groups are {32$\succ$33$\succ$34} and {22}. The final positive scheduling order of operation and the corresponding machines for Product A are {42, 15, 31, 28, 25, 39, 21, 13, 30, 40, 22, 20, 38, 29, 19, 34, 11, 10, 41, 18, 14, 27, 12, 17, 33, 9, 26, 32, 16, 8, 7, 5, 6, 2, 3, 4, 1} and {4, 1, 1, 3, 1, 1, 2, 4, 2, 3, 3, 1, 2, 1, 1, 2, 2, 4, 4, 4, 3, 3, 3, 3, 4, 4, 3, 2, 1, 3, 1, 4, 2, 1, 4, 3, 2}.

To visualize the effects of POS and POPS, Figures 9 and 10 show the Gantt charts obtained without the POS and POPS, respectively. The makespans of Product A are 156 hours and 161 hours, respectively. Obviously, their makespans are much longer than that obtained via the MFISA. The reasons are as follows.

Without using the POS, many operations cannot be processed in parallel with optional machines. For example, in Figure 9, without using the POS, Operation 4 is not assigned to any machine at t = 5, which delays all of the starting times of the successor operations, and Machine 3 remains idle until time 28.

Without using the POPS, the processing states at some driven times will not backtrack to a better scheme to consider the competition of some potential operations, which can preempt the machine. For example, in Figure 10, without using the POPS, the processing state is not backtracked to driven time 5 by because Operation 6 can preempt Machine 4 from Operation 4 at time 11. Operation 6 will be processing on Machine 4 at time 23, which is 12 hours later than it in Figure 8.

5.2.   Experiments for MFISP

In order to research the effectiveness of the proposed MFISA for the MFISP, we use the hypothesis test cases. Because there is no published integrated algorithm for the MFISP, we chose three typical dispatching rules: earliest completion time (ECT), job with most remaining work (JMRW) and machine with least workload (MLW); these were used to enable comparison with the MFISA. Because the MFISA does not describe the operations by jobs due to the reprocessing of some subassemblies, in this study, the dispatching rule JMRW was modified to give priority to the operation with the longest relative subsequence path. The number of actual scheduling operations of a complex product in the MFISP cannot be fixed, so 30 complex products with different scales and quantities of operation and equipment were selected. The process parameters of these products and the results of the above four algorithms are shown in Table 4. We chose $\alpha \in [0.9, 1]$ with the step length of 0.01 for the proposed algorithm, where a total of 11 groups of experiments were carried out. Table 4 shows the best results and average values of these 11 groups of experiments. The results of these 11 groups of experiments are shown in Figure 11. For further intuitive illustration, the confidence intervals of the optimal solutions and CPU time are shown in Figure 12.

In Figure 11, it is obvious that the optimal result of each product obtained by the MFISA may differ with different α. This is because these products are structured differently and the MFISP is NP-hard. Also, the differences between the results were not huge. Thus, we randomly chose the case with α = 0.94 as an example. In Figure 12(a), it is clear that the average results of the MFISA are better than those of the other three algorithms, and all of the optimal results (best-known) were obtained by the MFISA. Also, the MFISA with α = 0.94 performed better than the other three algorithms. Most of the results of the other three algorithms were far from the optimal solutions, among which the MLW performed the worst. However, in Figure 12(b), we can see that the CPU times of the MFISA are much slower than those of the other algorithms. If there is a dynamic disturbance, the MLW is the fastest algorithm to respond, but it also sacrifices the makespans of the complex products.

The results show that the scheduling results of the proposed algorithm are the most favorable. As the operation scale increases, this advantage becomes more obvious. In fact, all of the optimal solutions were obtained by it with a suitable $\alpha \in [0.9, 1]$. Among all of the comparisons, the MFISA had the best performance.

5.3.   Numerical example for FISP

When the number of flexible operations is zero and there are no special types of operations, the MFISP will degenerate into the normal FISP, which only considers the flexibility of machines. The MFISA can also be applied to solve the scheduling for the normal FISP.

Now, we take the processing operation tree of Product B in Figure 13 as an example. The other three flexible integrated algorithms, i.e., the DPFISA ^[36] and CMFISA ^[37], which have better scheduling effects on the FISP, and the RLFISA ^[40], which is the latest algorithm, were compared with the MFISA. The Gantt chart for each is shown in Figure 14. The completion time of the scheduling scheme obtained by the MFISA was 120 hours, which is the same as that of the DPFISA and much less than the 155 hours obtained by the CMFISA. The result shows that the MFISA can also better solve the FISP.

5.4.   Experiments for FISP

To further illustrate the effectiveness of the MFISA for solving the normal FISP, we randomly generated 13 groups of test instances with the operation and equipment combination of [50,100,200] × [5,10,15] and [400,600] × [15,20]. Each group contained 10 test instances of the same scale, for a total of 130 instances. In this study, 13 groups of test instances were divided into low density, medium density and high density based on the average number of operations per machine. Low density refers to the instances in which the average number of operations per machine is less than 20. High density refers to the instances in which the average number of operations per machine is more than 30, and the remaining instances are at medium density. The scales of all instances are shown in Table 5.

The final results of the MFISA with α = 0.94, the DPFISA, the CMFISA and the RLFISA are shown in Figures 15 and 16. In order to make the results more intuitive, the confidence intervals of the optimal solutions and the CPU times for the four algorithms under different production densities are shown in Figures 17–19.

As shown in Figure 15, when the production scale is low-density, the average result of the MFISA with different values of α is the best. Compared with the average result, the solution with α = 0.94 was not the best among all α values, but it was still better than the other three algorithms. It indicates that, regardless of the α value, overall, the MFISA outperforms the other algorithms. Among the other algorithms, the RLFISA is the most recently published algorithm, but its performance is worse than the DPFISA. However, the RLFISA had the best running time of the four algorithms, while the MFISA was the slowest.

As shown in Figure 16, when the production scale is medium-density, the average results of the MFISA are still the best, but the effect is weaker than that of low density. When α is 0.94, the performance of the MFISA is still better than that of the other three algorithms. On the whole, most of the results of the MFISA are better than those of the other algorithms. The optimization effect of the RLFISA was better than that of the other two algorithms. However, the CMFISA had the best running time of the four algorithms, while the MFISA was the slowest.

As shown in Figure 19, the average results of the MFISA are still the best when the production scale is high-density. When α is 0.94, the performance of the MFISA is still better than the other three algorithms, but the running time is much longer than those of the other algorithms. Overall, the MFISA outperformed the other algorithms for the most instances. Among the other three algorithms, the DPFISA had a better optimization effect.

Based on Figures 17–19, it can be found that the optimization effect of the MFISA always keeps a high level no matter the value of α. The optimization effects of the RLFISA and the CMFISA obviously decrease with the increase of the production density. The optimization effect of the DPFISA improves with the increase of the production density. The running times of the four algorithms increase greatly with the increase of production density.

6.   Discussion

In summary, the complementarity of all strategies has great influence on the performance of the proposed strategies when applied to solve both the MFISP and FISP.

For the FISP, the previous approaches involved studying the characteristics of the processing tree by focusing on the shortest processing time of each operation to simplify the flexible problem, such as using the DPFISA and CMFISA. This ignores the influence of other processing times on all processing, artificially reducing the effect of optimization. The proposed algorithm makes up for this shortcoming and uses the average processing time to define the remaining workload of the processing tree, that is, the RSP. The OOAS was designed based on the RSP; it reduces the workload of the machines by selecting the proper competitive operations, and it avoids the accumulation of serial operations by making the operations on the critical path complete earlier.

Previous event-driven-based approaches only dispatch operations per driven time according to one certain principle, such as CMFISA. This may cause device load imbalance, resulting in longer processing times for concurrent operations. Besides, some algorithms only focus the schedulable operations at a current driven time or current layer priority in the processing tree, such as the DPFISA, RLFISA and CMFISA. This may cause new schedulable processes generated at other driven times or layers to lose potentially idle devices. To avoid the above shortages, the proposed algorithm uses the POS to supplement the results of employing the OOAS in parallel, and it uses the POPS to backtrack the driven times. The POS maximizes the avoidance of the empty load of idle machines at the driven time by adjusting the scheduling of the planned operations, so as to improve the parallelism between parallel processing operations. The POPS achieves the preemption of the new schedulable operations, providing a better solution to previous driven times.

The experimental results in Figures 17–19 show that the MFISA performs better than the comparison algorithms without considering the production scale density. And, a suitable α can control it to find a more optimal solution. Since the change of α is controlled in a small range (0.9~1) and there is no obvious rule between the results, α can be randomly selected within this range. Also, since the running time of the proposed algorithm is short, it can also be run several times with different α to get a more optimized result.

For the MFISP, in addition to the above advantages, the FODS is very helpful for the proposed algorithm when dynamically determining whether the current flexible operation is optimal. However, typical dispatching rules have no special strategy to deal with the flexible planning path group, so flexible operations cannot be optimally scheduled. The experimental results in Table 4 show that the MFISA is better than the comparison algorithms even when the operation scale is increased.

7.   Conclusions and future research

In this paper, we address the MFISP for complex products. We establish the relevant mathematical model and build the extension processing operation tree by mapping the flexible sequential operation groups and the flexible planning path groups to the AND sub-graphs and OR sub-graphs. Then, we put forward the MFISA to solve the scheduling of the MFISP. Therefore, the conclusions are as follows.

1) The FODS ensures the compact serial processing between flexible operations and shortens the completion time of products as much as possible.

2) The OOAS reduces the workload of the machines by selecting the proper competitive operations and avoids the accumulation of serial operations by making the operations on the critical path complete earlier.

3) The POS avoids the empty load of the machines at the driven time by readjusting the scheduling scheme.

4) The POPS achieves the preemption of the new schedulable operations.

5) The MFISA can not only effectively solve the MFISP, but it can also better solve the FISP.

Based on the MFISA proposed in this paper, it can also be mixed with strategies for multi-workshops or other constrains to solve an extension of the MFISP, and it can be further extended to dynamic environments.

Acknowledgments

We would like to acknowledge the support of the National Natural Science Foundation of China (Grant no. 61772160).

Conflict of interest

The authors declare that there is no conflict of interest.