Integrated scheduling algorithm of reversed device network based on operation genealogy table

Abstract

In response to the issue where previous complex product device network scheduling algorithms did not separately consider the migration time of the device, resulting in errors in the actual scheduling results, this paper proposes a reverse device network integrated scheduling algorithm based on the operation genealogy table within the framework of a genetic algorithm. Firstly, the processing operation tree of the product is mapped into an operation genealogy table, and an encoding method based on multi-child probability selection is proposed. Then, crossover methods based on descendant nodes, parent nodes, and positions are respectively introduced to ensure the legality of the generated offspring individuals. Additionally, two mutation methods, namely the single point mutation method based on movable range and the recoding mutation method based on a single node, are proposed to enhance population diversity. Lastly, a pre-decoding method driven by migration time and a forward-to-reverse scheduling scheme conversion strategy based on completion time reversal is resented. This paper conducts two sets of comparative experiments based on rules and based on metaheuristics, comparative experimental results demonstrate that the proposed algorithm outperforms other comparative algorithms in terms of solution quality.

Keywords

Operation genealogy table integrated scheduling algorithm tree-structured products device network

1 Introduction

Production scheduling [1 –3] refers to the process of effectively configuring shared resources within a specific period to meet specific production target requirements. Integrated scheduling, as a third type of production scheduling problem distinct from traditional job-shop [4, 5] and flow-shop [6, 7] scheduling problems, aims to simultaneously consider the processing and assembly processes of operations. In the face of complex manufacturing environments with multiple varieties and small batch production, especially for products with complex tree-like process structures, it exhibits better effects. The application of integrated scheduling can significantly improve production efficiency, reduce enterprise production costs, and optimize resource utilization, thus attracting extensive attention in the modern manufacturing field from both academia and industry.

In recent years, there have been certain research advancements in integrated scheduling [8]. Current research on integrated scheduling problems is divided into three stages: general integrated scheduling problems, distributed multi-workshop integrated scheduling problems, and device network integrated scheduling problems. For the general integrated scheduling problem of a single workshop with complex products, Zhou et al. [9] proposed a resource collaborative integrated scheduling algorithm considering the weights of multi-operation devices, optimizing the density of vertical continuous processing and the degree of parallel optimization of horizontal processes by defining the weights of operations and devices and adjusting scheduling time strategies. Teng et al. [10] proposed a flexible integrated scheduling method considering vertical and horizontal pre-scheduling of root subtrees, dynamically determining processing devices by grouping processes according to the device, optimizing scheduling efficiency, and outperforming algorithms based on uniform rules. However, the above-mentioned algorithms rely more on product processing structures and are difficult to adapt to differences between different instances, with scheduling schemes lacking diversity. Gao et al. [11] proposed an integrated scheduling algorithm based on priority constraint tables to address the shortcomings of intelligent optimization algorithms in handling tree-like complex products, such as deficiencies in encoding method design and the generation of infeasible offspring by evolution operators during the iteration process. Zhou et al. [12] proposed a heuristic integrated scheduling algorithm combining the improved Dijkstra algorithm, effectively addressing the problem of neglecting process structure and attribute characteristics in integrated scheduling of multi-variety, small-batch complex products, reducing device idle time, and having better practicality for different instances of integrated scheduling problems. With the continuous growth in demand for personalized products, a single workshop has become inadequate to meet a wide range of processing technology requirements, necessitating collaborative production among multiple workshops. For the distributed workshop scheduling problem where an enterprise has multiple workshops or multiple enterprises share the same workshop, Zhang et al. [13] proposed a two-workshop integrated scheduling algorithm based on timing selection, which determines the scheduling order and start processing time of operations by virtualizing operations with simultaneous ending constraints into an operation group and combining the pseudo-critical path method and first-fit scheduling algorithm as well as the anticipated late finish priority strategy and simultaneous finish strategy. Xie et al. [14] proposed a batch-wise balanced non-symmetric three-workshop integrated scheduling algorithm, which divides devices into different types based on device attributes, determines workshops using operation correlation strategies and balanced arrangement adjustment strategies, and determines scheduling sequences using long-path strategies, thus improving the utilization of non-symmetric devices. However, with the development of cloud computing and emerging new manufacturing models like cloud manufacturing [15], device resources are no longer confined within the enterprise but form a network shared by multiple enterprises. This decentralized nature poses new challenges to integrated scheduling, such as the transportation time of workpieces between devices in different geographic areas. Therefore, addressing these challenges and achieving good collaboration between devices is crucial for enhancing the overall efficiency and competitiveness of the manufacturing industry. Currently, the solutions to the previously mentioned issues are relatively limited. Wang et al. [16] proposed a reverse device network integrated scheduling algorithm based on dynamic root node operation sets to solve the problem of prolonged product completion time caused by previous flexible device network integrated scheduling algorithms only considering forward scheduling. Xie et al. [17] proposed an algorithm for the equipment selection problem in flexible equipment network integrated scheduling algorithms, presenting a new algorithm (SP-FENIS) considering subsequent operations on the same layer, effectively shortening product completion time through reverse-layer priority, meaning reverse tight-later path and earliest finish time strategies. However, the algorithm has certain flaws, such as including migration time in the processing time of operations and not separately considering migration time, resulting in biased actual scheduling results, which are unfavorable for the parallel efficiency of operations in distributed device networks on differentdevices.

Given this, this paper proposes a reverse device network integrated scheduling algorithm based on the operation genealogy table, introduces a reverse encoding method based on the operation genealogy table, designs genetic operators that satisfy reverse constraints for complex product integrated scheduling and assembly, and the pre-decoding process separately analyzes the migration time between devices. Furthermore, it ensures the generation of feasible solutions to the original problem through a forward conversion strategy. Finally, the algorithm proposed in this paper undergoes comparison with multiple instance experiments to verify its feasibility and practical advantages.

2 Problem description

The objective of device network integrated scheduling is to fully exploit the parallel potential of workpiece processing to optimize production efficiency. In the production environment of device networks, the integrated scheduling problem of tree-shaped complex products can be understood as follows: facing a tree-shaped complex product containing n executable operations, cooperative operations need to be achieved through multiple interconnected processing device. In this process, the specific layout of device networks, sequence arrangement of operations, and key information such as processing device and required time for each operation are all known conditions. At the same time, the constraint relationships between operations have strict immutability and must be strictly followed. Device network integrated scheduling must meet the following constraints:

There are no identical devices in the device network, and the processing device is in a discrete distribution state.

Once a device in the device network starts processing an operation, it cannot be interrupted midway.

Each operation can only start processing after its reverse tight predecessor operation has been fulfilled and device migration has been concluded, or when there is no reverse tight predecessor operation.

When different device is needed for processing adjacent operations, migration time needs to be considered.

At time zero, all devices are available.

The completion time of the last operation is the total processing time of the product, which is the completion time.

Assuming a complex single product consists of n operations {O_i } _1⩽i⩽n, processed on m machines {M_k } _1⩽k⩽m. S_i represents the reverse start time of O_i on device M_k, and C_i represents the reverse completion time of operation O_i. t_ik represents the processing time on device M_k, and T_{m_i,m_l} is the migration time between devices m_i and m_l. X_ik = 1 indicates that operation O_i is processed on machine M_k; Y_li = 1indicates that operation O_l is the reverse predecessor of operation O_i. The problem is described as: $min C_{max} = min {\max (C_{i})}$ (1) $s . t . \min {S_{i}}$ (2) $s_{i} ⩾ max {c_{l} + T_{m_{i}, m_{l}}}, Y_{li} = 1$ (3) $c_{i} = s_{i} + t_{i}$ (4)

The objective of the optimization in Equation (1) is to minimize the maximum completion time of operations (i.e., minimize the product completion time). Equation (2) indicates that subject to the constraints of inequality Equation (3), the goal is to process the operations as early as possible on the processing device. Equation (3) signifies that process O_i, before starting processing, requires waiting for all operations with precedence constraints to complete processing, and these related operations must be migrated to the currently selected processing device first. Equation (4) represents the actual completion time of the operation O_i.

The complex processing operations in the device network integrated scheduling form a tree-like structure known as the processing operation tree of the product. The directed edges between operations represent the partial order relation of product processing. In the example of the processing operation tree of product A shown in Fig. 1 [23], each node in the rectangular box sequentially indicates the operation name, the corresponding processing device, and the processing time. The root node in the processing tree is A1, and when the root node is processed, it indicates the completion of product processing assembly [18]. The objective of scheduling is to minimize the completion time of operation A1. The inter-operation migration times between devices in Fig. 1 are shown in Table 1. The weighted directed graph in Fig. 2 illustrates the device network for processing Product A, where nodes represent different processing devices and the weights between nodes represent the migration time of operations between devices.

Table 1

The migration time between different processing device for product A.

	M ₁	M ₂	M ₃	M ₄
M ₁	0	10	15	10
M ₂	10	0	25	20
M ₃	15	25	0	10
M ₄	10	20	10	0

Fig. 1

Processing operation tree of product A.

Fig. 2

Device network of product A.

As shown in Fig. 1, in the case of operations 16 and 10, according to traditional integrated scheduling algorithms, when operation16 completes processing on M3, operation10 will immediately begin processing. However, in device network integrated scheduling algorithms, according to Table 1, operation 10 needs to wait for 15 minutes before being scheduled to start.

3 Algorithm design

Based on a comprehensive analysis of the characteristics and challenges of the device network integrated scheduling problem, this paper employs a genetic algorithm to solve the problem and explores algorithm implementation techniques that satisfy migration time conditions. Simultaneously, an in-depth study is conducted on the processing operation tree of product A structure, establishing an OGT based on the constraint relationships between them. Using OGT as a foundation, a reverse encoding method based on multi-child probability selection is designed to meet the requirements of the algorithm’s crossover and mutation operators. Additionally, strategies for pre-decoding and forward transformation are proposed to achieve effective solutions for this type of problem.

3.1 Establishment of operation genealogy table

The OGT designed in this paper facilitates the acquisition of precedence constraint information between operations. For instance, by identifying the diagonal elements of the OGT with a value of –1, corresponding operations in the row or column can be obtained, thus obtaining the root node operation. By identifying the i-th row elements of OGT, operations corresponding to columns with an element value of 1 can be obtained, thereby obtaining the child operations of operation O_i. By identifying the j-th column elements of OGT, operations corresponding to rows with an element value of 1 can be obtained, thereby obtaining the parent operations of operation O_j. Based on the OGT designed in this paper, new encoding methods and evolutionary operators are constructed to solve the tree-like structured complex product scheduling problem considering migration time. Table 2

Table 2
The operation genealogy table of product A shown in Fig. 1

A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 A17 A18

A1 –1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

A2 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0

A3 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0

A4 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0

A5 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

A6 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0

A7 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0

A8 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0

A9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

A10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

A11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

A12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

A13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

A14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

A15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

A16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

A17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

A18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

	A1	A2	A3	A4	A5	A6	A7	A8	A9	A10	A11	A12	A13	A14	A15	A16	A17	A18
A1	–1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
A2	0	0	0	0	1	1	1	0	0	0	0	0	0	0	0	0	0	0
A3	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0	0
A4	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
A5	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
A6	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
A7	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
A8	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	0	0
A9	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
A10	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
A11	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
A12	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
A13	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
A14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
A15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
A16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
A17	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
A18	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

$OGT (i, j) = {\begin{matrix} 1, i \neq j and Operation O_{j} is the child node of O_{i} \\ - 1, i = j and Operation O_{i} is the root node \\ 0, Otherwise \end{matrix}, 1 ⩽ i ⩽ n, 1 ⩽ j ⩽ n$ (5)

3.2 Encoding method based on multi-child probability selection

This paper adopts an operation-based encoding strategy, where the numbers on the encoded gene positions represent the IDs of operations. To ensure the legality of population individuals and improve the quality of individuals in the initial population, an encoding method based on multi-child probability selection is proposed. This method aims to achieve the transition of operations in the operation tree between encodable and non-encodable states by continuously updating the values in the OGT until all operations complete individual encoding. The specific steps are as follows:

Step 1: Establish OGT according to the processing operation tree of the product.

Step 2: Add the operations O_i in OGT whose values in corresponding columns are all 0 or –1 to the encodable operation set C.

Step 3: For each operation in the encodable operation set C, calculate the number of times it corresponds to a value of 1 in the i-th row of OGT. Select operations through a roulette wheel selection strategy and update the value of the i-th row corresponding to the operation in OGT to 0. At the same time, set all values in the i-th column to 1, so that the operation becomes non-encodable, while its child operations become encodable.

Step 4: Repeat steps 2 and 3 until the encodable operation set C is empty, at which point the method terminates. With the above-mentioned OGT-based multi-child probability selection encoding method, an individual that fully satisfies the priority sequence constraints of various operations in the product can be obtained. Figure 3 illustrates an individual obtained by applying the above encoding method to the product described in Fig. 1.

Fig. 3

Illustration of the chromosome coding of product A.

Fig. 3 illustrates a schematic diagram of an individual obtained by applying the above encoding method to the product described in Figure 1.

3.3 Selection method

In this paper, the tournament selection algorithm is employed as the main selection strategy, supplemented by the elite preservation strategy. The tournament selection algorithm randomly selects two individuals from the parent population for comparison and then chooses the individual with superior fitness as a member of the next-generation population. The elite preservation strategy preserves the individual with the best fitness in each generation, ensuring the ability to consistently pass on excellent genes to the next generation.

3.4 Crossover method

Based on OGT and individual representation method designed in this paper, this section presents crossover methods based on descendant nodes, based on parent nodes, and based on position. During the algorithm execution, these three crossover methods are randomly executed.

(1) Crossover Method Based on Descendant Nodes

To facilitate the inheritance of a favorable arrangement of a certain operation’s descendant nodes in the parent individuals by the offspring individuals, this section proposes a crossover method based on descendant nodes. The main idea is to randomly select an operation from the parent individual V₁ as the current crossover parent node, identify the OGT, iteratively obtain all its descendant nodes, and add them to the recombination operation set. Another paired parent individual V₂ specifies the order of operations in the recombination operation set. Finally, the sorted recombination operations are backfilled to obtain offspring individual $V_{1}^{'}$ . The same method can be applied to obtain offspring individual $V_{2}^{'}$ . The crossover process for the two paired parent individuals V₁ and V₂ of product A is illustrated in Fig. 4:

Fig. 4

Crossover method based on descendant nodes.

Figure 4 shows the offspring individuals generated using the above steps for two randomly generated parent individuals. In Fig. 4, V₁ and V₂ are the selected parent individuals, where the operation 3 from parent individual V₁ was randomly chosen as the parent node. For the offspring individual $V_{1}^{'}$ , its recombination operation set is [8, 15, 9, 18, 14]. The order in which it appears in the paired parent individual V₂ is [8, 15, 18, 9, 14]. Therefore, the order in which the recombination operation appear in the offspring individual is [8, 15, 18, 9, 14], resulting in the final offspring individual $V_{1}^{'}$ . Similarly, the offspring individual $V_{2}^{'}$ can be obtained.

(2) Crossover Method Based on Parent Nodes

To facilitate the inheritance of a favorable arrangement of certain operation parent nodes in the parent individuals by the offspring individuals, this section proposes a crossover method based on parent nodes. The main idea is to randomly select some operations from parent individual V₁ as the current crossover parent nodes, ensuring that the selected number of operations is greater than 1. Identify the OGT and iteratively obtain their parent nodes up to the root node (if multiple parent nodes are chosen, take the union). The order in which each operation in the recombination operation set appears in the current paired parent individual is specified by another paired parent individual (move all non-consecutive operations backward to ensure that the constraints between operations are satisfied). Finally, the offspring individual $V_{1}^{'}$ is obtained. The same method can be applied to obtain the offspring individual $V_{2}^{'}$ . The crossover process for the two paired parent individuals V₁ and V₂ of product A is illustratedin Fig. 5.

Fig. 5

Crossover method based on parent nodes.

Figure 5 shows the offspring individuals generated for two randomly generated parent individuals using the above steps. In Fig. 5, V₁ and V₂ are the selected parent individuals, where operations 11 and 14 from parent individual V₁ were randomly chosen as parent nodes. First, iteratively obtain the parent operation set [1, 2, 5] for operation 11. Then, iteratively obtain the parent operation set [8, 3, 1] for operation 14. Next, take the union of these two parent operation sets to obtain [1, 3, 2, 5, 8]. For offspring individual $V_{1}^{'}$ , the order of the recombination operation set should match the order in the paired parent individual V₂. Therefore, arrange the operations in the recombination operation set in the order of V₂, resulting in [1, 2, 3, 8, 5]. Finally, move the non-consecutive nodes in the recombination operation set backward to obtain offspring individual $V_{1}^{'}$ . Similarly, offspring individual $V_{2}^{'}$ can be obtained.

(3) Position-Based Crossover Method

In “flat” tree-structured complex products, there are many descendant operation genes, and their arrangement significantly affects the product completion time. Therefore, to facilitate the acquisition of favorable arrangements for descendant genes in offspring individuals, this section proposes a position-based crossover method. The main idea is to randomly select a crossover position for parent individual $V_{1}^{'}$ , and the arrangement of all operations after this position is specified by another parent individual V₂. Finally, the offspring individual $V_{1}^{'}$ is obtained by backfilling. The crossover process for the paired parent individuals V₁ and V₂ for product A is illustrated in Fig. 6.

Fig. 6

Location-based crossover method.

Figure 6 depicts the two offspring individuals generated using the aforementioned steps for two randomly generated parent individuals. In Fig. 6, V₁ and V₂ are the selected parent individuals participating in the recombination. Based on the described crossover method, the randomly selected position in the parent individual V₁ is 7, and the corresponding recombined operation set after this position is [6, 15, 12, 9, 16, 11, 17, 13, 18, 14]. For the offspring individual V₁, the first 7 positions inherit the operations from the corresponding position of V₁, and the order of operations in the recombined operation set after that, as they appear in the parent individual V₂, is [6, 12, 15, 13, 18, 9, 17, 14, 11, 16]. Therefore, by rearranging the order of operations in the recombined operation set according to this sequence and filling in the vacant positions, the offspring individual $V_{1}^{'}$ can be obtained. Similarly, the offspring individual $V_{2}^{'}$ can be obtained.

(4) Crossover Method Analysis

Based on the above description, all three crossover methods are based on the parent individual V₁, replacing the gene sequence with that of another parent individual V₂ to generate offspring V′, inheriting the favorable arrangement of the parents. Since the selected parent individuals do not contain infeasible solutions, and the crossover process considers the constraints between operations, the individuals generated by the above-mentioned crossover algorithms can satisfy the constraints between operations and will not produce infeasible solutions.

3.5 Mutation method

Based on the OGT and the individual representation method designed in this paper, this section proposes the single-point mutation method based on the movable range and the re-encoding mutation method based on a single node, with both mutation methods being randomly executed during the algorithm’s execution.

(1) Single point mutation method based on movable range

To ensure the diversity of the population after mutation, this section proposes a single-point mutation method based on a movable range. The main idea is to randomly select an operation of the mutated individual V as the current mutated child node, identify OGT, obtain the parent and child nodes of this operation, and determine its position in the current mutated individual. If there are multiple child nodes, select the leftmost position of the child operation in the individual. Insert the current mutated child node randomly into any position between its parent and child nodes. Finally, generate the mutated offspring V′. The mutation process for product A’s individual V is illustrated in Fig. 7.

Fig. 7

Single point mutation method based on movable range.

Randomly selecting operation 3 as the mutation child node in the mutated individual, by identifying the OGT, determining its parent node 1, and child nodes 8 and 9. Within the mutation range, following the mutation rules, select child node 8 as the rightmost boundary of the mutation range and simultaneously select parent node 1 as the leftmost boundary of the mutation range. Then, randomly inserting the mutation node into position 5 within the range, ultimately generating the mutated offspring individual V′.

(2) Recoding mutation method based on single node

To increase the diversity of the population, this section proposes a single-node recoding mutation method. The main idea is to randomly select an operation in the mutated individual V as the current mutation root, identify the OGT, obtain all its descendants, add the currently schedulable nodes to the schedulable operation set, use the encoding method described in this paper to select schedulable operations, and finally re-generate the arrangement of the mutation root and its descendants, and fill them back into the mutated individual in order. The final mutated offspring V′ is generated. The mutation process for product A’s individual V is shown in Fig. 8.

Fig. 8

Recoding mutation method based on a single node.

The randomly selected mutation root node in the mutated individual V is operation 3. By identifying the OGT, its set of descendant operations is obtained as [8, 15, 9, 18, 14]. Subsequently, using the encoding method proposed in this paper, the set of descendant operations is recoded, resulting in a schedulable operation set of [8, 9]. Then, according to the multiple probability selection method, operation 8 is chosen. At this point, the schedulable operation set is updated to [14, 15, 9]. Continuing to select operation 9, the operation set becomes [14, 15]. Then, operation 14 is chosen, and now only operation 15 remains in the operation set, which is updated to [18]. Finally, operation 18 is selected, and now the schedulable operation set is empty, and the operation is concluded.

(3) Analysis of Mutation Methods

The mutation method based on single-node re-encoding focuses more on the exchange and insertion of nodes, which can introduce a larger mutation range, aiding in increasing the diversity of the search space. On the other hand, the single-point mutation method based on the movable range is designed based on the encoding principles in this paper, ensuring the generation of an individual different from the local optimal solution. Both methods ensure the absence of infeasible individuals. Additionally, even if the same operation is chosen, the resulting mutated individuals may not be unique.

3.6 Pre-decoding strategy

Based on the individual representation method described in this paper, this section proposes a pre-decoding method driven by migration completion time to decode the individual into a reverse scheduling scheme. Its main idea is to sequentially retrieve the current operation to be scheduled from left to right, place the operation on the corresponding device, and process it at the migration completion time. After decoding the individual, the reverse start time and completion time on each machine can be obtained. Based on these data, the corresponding scheduling Gantt chart can be generated. Figure 9 shows the specific scheduling scheme obtained after decoding the individual described in Fig. 3. The completion time of the critical path in the operation set is the objective function value, which is the maximum completion time of a leaf node or the last operation on each machine.

Fig. 9

Pre-decoding scheduling scheme.

3.7 Forward transformation strategy

Since the encoding method adopted in this paper is reverse encoding, the decoding of the specific scheduling scheme is also in reverse order. To convert the reverse scheduling scheme into a forward scheduling scheme, i.e., scheduling the product from the leaf node, this paper provides a scheduling scheme conversion strategy based on completion time reversal [19]. Assuming that the completion time of the product for the to-be-converted scheme is known, along with the reverse start and completion times of each operation, the specific method of the conversion strategy described in this paper is:

First, subtract the start and completion times of each operation in reverse scheduling from the product completion time of the current scheme; then, take the negation of the results corresponding to each operation, i.e., turn each start and completion time value into a non-negative number; finally, swap the start and completion time corresponding to each operation to obtain the scheduled timetable for each operation in forward scheduling. Note that after transforming into a forward scheduling scheme, if all predecessors of an operation have been completed and there is an idle time before the current operation starts processing, the operation can be moved forward. However, whether in a forward or reverse scheduling scheme, the completion time of the product remains unchanged.

Therefore, the movement of operations was not considered in this paper. Figure 10 presents the forward scheduling scheme obtained by applying the forward conversion strategy to the reverse scheduling result shown in Fig. 9. Since, during the algorithm iteration process, it is only necessary to know the completion time of the product associated with the current individual, rather than the forward scheduling times of each operation. Therefore, at the end of the algorithm execution, the transformation strategy described in this paper can be applied to the obtained optimal reverse scheduling solution.

Fig. 10

Converted forward scheduling scheme.

3.8 Overall algorithm flowchart

The overall process of the proposed reverse device network integrated scheduling algorithm based on the OGT is illustrated in Fig. 11. During the execution of the algorithm, it first generates an initial population and then performs the designed crossover and mutation operations randomly in the subsequent iterative process to achieve population iteration. After G consecutive rounds of iterations, if there is no improvement in the fitness of the best individual in the population, the algorithm will stop running.

Fig. 11

The overall flow chart of the designed algorithm.

3.9 Computational complexity

Set the number of individuals in the population to N, the number of operations to n, and the number of processing devices to m. Each iteration of the algorithm involves population initialization, selection process, crossover process, mutation process, pre-decoding process, and decoding process. During the algorithm iteration process, population initialization involves encoding each individual. This article uses the multi-child probability selection strategy based on OGT to encode individuals. Encoding each individual requires traversing the constraint relationships of each operation in OGT, so its time complexity is proportional to the square of the number of nodes in the process tree, i.e., O(n²). For population initialization containing N individuals, the time complexity of completing all encoding is O(n²*N). This article uses tournament selection and elite preservation strategies to select individuals in the population. During the selection process, the population needs to be sorted from small to large according to the fitness of individuals, with a time complexity of O(nlog(n)*N). The algorithm randomly performs three crossover operations, each requiring two visits to the parent chromosomes, hence, the time complexity of crossover operations is O(n*N). In the two mutation operations proposed in this article, the first one needs to obtain the parent node and child node of the mutation node, thus its time complexity is O(n*N); the second one needs to obtain all descendant nodes of the mutation node and reorder them according to the priority constraint relationship, hence, its time complexity is also O(n*N). During the pre-decoding process, each operation needs to sequentially obtain the idle time periods between the same processing devices, with a time complexity of O(n*N). In the decoding phase, only the processing and ending times of each operation in the best individual completed by the iteration need to be reversed, thus, its time complexity is O(n). In summary, the time complexity of one iteration of the algorithm in this article is O(n²*N).

4 Numerical experiments

To validate the performance of the proposed algorithm ISA_RDNOGT, two sets of comparative experiments were conducted in this chapter. In the first set of experiments, specific product scheduling instances described in previous literature were used as test cases. This experiment aims to compare the performance of the proposed algorithm in terms of solution quality and solution diversity with conventional mainstream heuristic rule-based algorithms. In the second set of experiments, the solution quality (based on the completion time of obtained scheduling solutions) and solution speed (algorithm running time) of the proposed algorithm were compared with existing metaheuristic integrated scheduling algorithms.

All algorithms were implemented in Python and run on a computer with a 64-bit Windows 10 operating system, an Intel(R) Core(TM) i7-9750 CPU @ 2.60 GHz processor, and 16GB of memory. For each test case in the dataset, the algorithms were independently run 30 times to obtain the solutions.

4.1 Parameters setting

The impact of each parameter on the algorithm’s performance is analyzed using the Taguchi experimental design method [20] in this section, and the values of each parameter during algorithm runtime are determined. Test case I_77_4_1 is selected as the experimental case, where 77_4 indicates the size of the selected case (n = 77, m = 4), and 1 indicates that it is the first case in the case set. The algorithm proposed in this chapter involves four related parameters: population size (Ps), crossover probability (Pc), mutation probability (Pm), and termination condition-related parameter G (if the current optimal solution does not improve within consecutive G generations, the algorithm terminates). Four levels of impact factors are set in this section, and the specific combinations are shown in Table 3. The orthogonal array L16(44) is selected for experimentation, and for each parameter combination, the average completion time obtained from running independently 30 times is taken as the experimental indicator. The orthogonal array L16 and various experimental indicators are shown in Table 3. The impact of each parameter on the algorithm’s performance is shown in Fig. 12.

Table 3
Algorithm parameters corresponding to different levels of impact factors

Parameters Factor Level

1 2 3 4

Ps n1 n2 n3 n4

G 50 100 150 200

Pc 0.6 0.7 0.8 0.9

Pm 0.1 0.2 0.3 0.4

Parameters	Factor Level
Ps	n*1	n*2	n*3	n*4
G	50	100	150	200
Pc	0.6	0.7	0.8	0.9
Pm	0.1	0.2	0.3	0.4

Fig. 12

The impact of four key parameters on the ISA_RDNOGT algorithm.

Table 4 and Fig. 12 reveal that, firstly, parameter Ps has the greatest impact on the algorithm’s performance. As Ps changes from n*1 to n*4, the average value of the experimental indicator varies from 181.79 to 180.61, with a range of 1.18. As Ps gradually increases during the experiment, the experimental indicator improves, and the minimum product completion time corresponds to Ps = n*4. Therefore, in this section of the experiment, Ps is set to n*4. Secondly, parameter Pm has a significant impact on the algorithm’s performance. As Pm changes from 0.1 to 0.4, the average value of the experimental indicator varies from 181.67 to 180.71, with a range of 0.96. The minimum product completion time corresponds to Pm = 0.4. Thus, in this experiment, Pm is set to 0.4. Next, the parameter G has a notable impact on the algorithm’s performance. As G changes from 50 to 200, the average value of the experimental indicator varies from 181.585 to 180.84, with a range of 0.74. The experimental indicator first decreases, then increases, and then decreases again as G gradually increases. The smallest average completion time is obtained when G is set to 200. Therefore, in this experiment, G is set to 200. Lastly, parameter Pc has the least impact on the algorithm’s performance. As Pc changes from 0.6 to 0.9, the average product completion time varies from 181.44 to 180.98, with a range of 0.46. The experimental indicator initially decreases and then increases as Pc gradually increases. The smallest product completion time is obtained when Pc is set to 0.7. Therefore, in this experiment, Pc is set to 0.7. In summary, the four key parameters of the proposed algorithm, ISA_RDNOGT, are set as follows: Ps = n*4, G = 200, Pc = 0.7, and Pm = 0.4. The comparative experiments with heuristic rule algorithms and meta-heuristic algorithms conducted in this chapter all used this parameter to iterate the algorithm.

Table 4

The orthogonal results of different factor levels

Experiment Number	Factor Level				Index Makespan Average
	Ps	G	Pc	Pm
1	1	1	1	1	183.67
2	1	2	2	2	181.3
3	1	3	3	3	181.2
4	1	4	4	4	181.0
5	2	1	2	3	181.0
6	2	2	1	4	180.87
7	2	3	4	1	181.13
8	2	4	3	2	181.07
9	3	1	3	4	180.73
10	3	2	4	3	180.9
11	3	3	1	2	180.83
12	3	4	2	1	180.93
13	4	1	4	2	180.9
14	4	2	3	1	180.93
15	4	3	2	4	180.23
16	4	4	1	3	180.37
K1	727.17	726.3	725.74	726.66	–
K2	724.07	724	723.46	724.1	–
K3	723.39	723.39	723.93	723.47	–
K4	722.43	723.37	723.93	722.83	–
k1 = K1/4	181.79	181.58	181.44	181.67	–
k2 = K2/4	181.02	181	180.87	181.03	–
k3 = K3/4	180.85	180.85	180.98	180.88	–
k4 = K4/4	180.61	180.84	180.98	180.71	–
Range	1.18	0.74	0.46	0.96	–
Rank	1	3	4	2	–

4.2 Compare with heuristic rule-based algorithms

In this group of experiments, the processing operation tree of product A in Fig. 1 of this paper is selected as the test case, and the selected comparative algorithms are as follows: ISA_STD [21], a resource cooperative integrated scheduling algorithm based on sub-tree cycle decomposition of the process tree, ISA_CMPEW [9], a resource collaborative integrated scheduling algorithm considering multi-operation device weight, and DJSSA_DSOHP [22], a dynamic job-shop scheduling algorithm that can dynamically generate priority process sets, are compared with the device network integrated scheduling algorithm ISA_RDNOGT proposed in this paper, which considers the migration time between devices. The scheduling results obtained are shown in Fig. 13.

Fig. 13

Comparison between the scheduling schemes obtained by the ISA-RDNOGT algorithm in this article and previous heuristic rule algorithms. (a) ISA_STD scheduling scheme. (b) ISA_CMPEW scheduling scheme. (c) DJSSA_DSOHP scheduling scheme. (d) ISA_RDNOGT scheduling scheme.

Due to the limited applicability of heuristic rule algorithms, it can be observed from Fig. 13 that, under the consideration of migration time, the algorithm proposed in this paper significantly outperforms the other three algorithms in terms of scheduling results. In the process of 30 solving iterations, the calculation results of the algorithm ISA_RDNOGT in this paper show an average makespan value of 228.0, and it is capable of generating multiple different scheduling solutions, not only obtaining superior solutions but also ensuring solution diversity. Figure 13(d) represents one of the optimal scheduling solutions for the product shown in Fig. 1.

4.3 Comparative metaheuristic algorithm

There are plenty of benchmark datasets available for traditional production scheduling problems. However, there are currently no available benchmark test cases for device network integrated scheduling problems. Most of the comparative examples mentioned in the literature on integrated scheduling problems are for single-product instances. In order to better test the performance of the algorithm proposed in this paper, this chapter randomly generated 100 test cases, following the experimental methods of previous integrated scheduling solutions based on meta-heuristic optimization algorithms. Each test instance is randomly generated by the following parameters [16]: the number of operations is [50, 100], the number of devices is [4, 8], the migration time of the process between devices [1, 10], and the processing time of the operation is [1, 20]. In addition, to remove the special case of the test set instance, the number of processing operation tree of the product levels is set to [2, n/2], where n is the number of operations corresponding to the current processing operation tree of the product. In this section, the following mainstream integrated scheduling algorithms were selected as comparative algorithms: CSA_VCLDC [23], an integrated scheduling algorithm based on virtual component-level partitioning coding, ISA_ORMT [24], an integrated scheduling algorithm based on step relationship matrix table coding, and ISA_DROS [19], an integrated scheduling algorithm based on dynamic root node operation set. The values of parameters in each algorithm were the optimal values validated in their respective literature: G = 50, PC = 0.8, PM = 0.05, PS = 100 for CSA_VCLDC and ISA_ORMT. For algorithm ISA_DROS, G = 30, PC = 0.9, PM = 0.3, PS = n*4.

Each algorithm independently ran 30 times to solve each test case. The minimum completion time and average completion time of each test case during the solving process are shown in Figs. 14 and 15, respectively. From Figs. 14 and 15, it can be observed that the curves of the minimum completion time and average completion time of the algorithm proposed in this paper, ISA_RDNOGT, are mostly below the curves of the solution curves of other algorithms, indicating that for the test cases, the solutions obtained by algorithm ISA_RDNOGT are mostly superior to those obtained by other comparative algorithms.

Fig. 14

For 100 randomly generated instances, the minimum makespan obtained by each algorithm after running independently for 30 times for each instance.

Fig. 15

For 100 randomly generated instances, the average makespan obtained by each algorithm after running independently 30 times for each instance.

To further clarify the solving capability of the algorithm proposed in this paper on the test dataset, Fig. 16 presents the statistical data of the results shown in Figs. 14 and 15. In Fig. 16, the first set of data counts the total number of times the minimum completion time obtained by each algorithm in Fig. 14 is the smallest among the results obtained by the four algorithms mentioned above. Specifically, in the first set of data shown in Fig. 14, for the 100 instances described in Fig. 14, algorithm ISA_RDNOGT obtained the optimal solution for 78 instances, algorithm ISA_ORMT obtained the optimal solution for 33 instances, algorithm CSA_VCLDC obtained the optimal solution for only 28 instances, and algorithm CPFS_CJ obtained the optimal solution for 12 instances. The second set of data describes the statistical situation of the average completion time results shown in Fig. 15, showing the average solving capability of each algorithm for the test cases. Among the 100 instances described in Fig. 15, algorithm ISA_DROS obtained the optimal solution for 73 instances, algorithm ISA_ORMT obtained the optimal solution for 15 instances, algorithm PCSA_VCLDC obtained the optimal solution for 16 instances, and algorithm ISA-DROS obtained the optimal solution for only 3 instances. It can be seen from Fig. 17 that under the conditions where the parameters of each algorithm are optimal, although the running time increases, the algorithm proposed in this paper exhibits significantly superior solving capability compared to the other three algorithms.

Fig. 16

For 100 randomly generated instances, the number of times each algorithm obtains the minimum makespan and the minimum average makespan.

Fig. 17

For 100 randomly generated instances, the average running time of each algorithm running independently 30 times.

For a certain randomly instance, algorithms ISA_DROS, ISA_ORMT, CSA_VCLDC, and the proposed algorithm ISA_RDNOGT were independently run 30 times, and the resulting completion times of the products are shown in Fig. 18. Figure 19 represents the runtime consumed during the algorithm-solving process. It can be observed from Figs. 18 and 19 that the algorithm proposed in this paper, ISA_RDNOGT, exhibits superior solving capability compared to the other three algorithms, with only a slight increase in running time.

Fig. 18

For a certain random instance, the minimum makespan obtained by running each algorithm independently 30 times.

Fig. 19

For a certain random instance, the minimum makespan obtained by running each algorithm independently 30 times.

5 Conclusion and outlook

To address the integrated scheduling problem in device networks considering device migration time, this study proposes a novel reverse integrated scheduling algorithm based on the operation genealogy table. Firstly, to simplify the algorithm design, an encoding method utilizing an operation genealogy table for the probabilistic selection of multiple children is proposed based on the concept of reverse scheduling, ensuring the effectiveness and superiority of initial population individuals. Secondly, corresponding crossover and mutation methods are designed based on the parent-child relationships of operations and their positions within individuals, which not only guarantees that the population does not generate infeasible solutions during the evolution process but also avoids unnecessary detection and repair processes for infeasible solutions. Furthermore, a pre-decoding strategy based on migration completion time is designed for reverse-encoded individuals, and a forward conversion strategy is provided to obtain the optimal scheduling solution. Finally, compared with other algorithms, the proposed algorithm in this paper achieves solutions to the integrated scheduling problem in device networks and demonstrates higher performance in obtaining feasible solutions, making it more suitable for practical applications.

However, there are some limitations to this study. Firstly, in addressing device network integrated scheduling algorithms based on migration time, the methods explored so far are relatively limited. Future research could consider adopting more advanced methods such as artificial intelligence algorithms [25] to address this issue. Secondly, the scheduling method proposed in this paper is only applicable to specific contexts of the problem. Future research should focus on addressing a wider range of scheduling problems, such as large-scale scheduling challenges in transportation, freight, and other domains [28]. Such extensions will bring more profound impacts to the scheduling field and provide more comprehensive solutions for practical applications.

Conflict of interest

All authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Funding

This work is supported by the Natural Science Foundation of Shandong Province, fund number ZR2020MF029, and the Natural Science Foundation of Shandong Province, fund number ZR2023MF090.

References

, et al., Optimization approaches for solving production scheduling problem: A brief overview and a case study for hybrid flow shop using genetic algorithms, Advances in Production Engineering & Management 17(1) (2022), 45–56.

Waubert de Puiseau, Constantin, Richard Meyes and Tobias Meisen, On reliability of reinforcement learning based production scheduling systems: a comparative survey, Journal of Intelligent Manufacturing 33(4) (2022), 911–927.

Liang Tang, et al., Centralized collaborative production scheduling with evaluation of a practical order-merging strategy, International Journal of Production Research 61(1) (2023), 282–301.

Zhang

, et al., A cooperative evolutionary algorithm with simulated annealing for integrated scheduling of distributed flexible job shops and distribution, Swarm and Evolutionary Computation 85 (2024), 101467.

Andreas Kuhnle, et al., Explainable reinforcement learning in production control of job shop manufacturing system, International Journal of Production Research 60(19) (2022), 5812–5834.

Shao

, Shao

and Pi

, Modelling and optimization of distributed heterogeneous hybrid flow shop lot-streaming scheduling problem, Expert Systems with Applications 214 (2023), 119151.

Hao-Xiang Qin, et al., An improved iterated greedy algorithm for the energy-efficient blocking hybrid flow shop scheduling problem, Swarm and Evolutionary Computation 69 (2022), 100992.

Xie

, et al., A new algorithm for complex product flexible scheduling with constraint between jobs, Computers & Industrial Engineering 57(3) (2009), 766–772.

Zhou

and Xie

, Resource collaborative integrated scheduling algorithm considering multi-process equipment weight, Journal of Electronics & Information Technology 44(5) (2022), 1625–1635.

10.

Teng

, et al., A flexible integrated scheduling algorithm for dynamic determination processing equipment considering the root-subtree vertical and horizontal pre-scheduling, IEEE Access 10 (2022), 132298–132314.

11.

Gao

, et al., Integrated scheduling algorithm based on the priority constraint table for complex products with tree structure, Advances in Mechanical Engineering 12(12) (2020), 1687814020985206.

12.

Zhou

, et al., A heuristic integrated scheduling algorithm based on improved dijkstra algorithm, Electronics 12(20) (2023), 4189.

13.

Zhang

, et al., A comprehensive scheduling algorithm for two workshops based on timing, Computer Integrated Manufacturing System 23(9) (2017), 1938.

14.

Xie

, Zheng

and Xia

, Asymmetric three workshop comprehensive scheduling algorithm for batch balanced processing, Journal of Beijing Institute of Technology 37(3) (2017), 274–280.

15.

, Fang

and Yin

, A machine tool matching method in cloud manufacturing using Markov Decision Process and cross-entropy, Robotics and Computer-Integrated Manufacturing 65 (2020), 101968.

16.

Wang

, Xie

and Gao

, Flexible networked machine integrated scheduling algorithm based on the dynamic root node operation set considering reverse scheduling, Electronics 12(3) (2023), 526.

17.

Xie

and Liu

, A comprehensive scheduling algorithm for flexible equipment networks considering same layer subsequent processes, Journal of Electronics and Information Technology 46 (2024), 1–9.

18.

Xie

, Liu

and Yang

, A batch comprehensive scheduling algorithm considering subsequent processes with 2 batch processing processes, Journal of Shanghai Jiao Tong University 46(11) (2012), 1746–1752.

19.

Wang

, et al., Integrated Scheduling Algorithm for Complex Products Based on the Dynamic Subtree Operation Set Inverse Coding, (2022).

20.

Angela Dean and Daniel Voss, eds. Design and analysis of experiments, New York, NY: Springer New York, 1999.

21.

Xie

, Zhou

and Yang

, A resource collaborative comprehensive scheduling algorithm for process tree subtree recurrent decomposition, Journal of Mechanical Engineering 58(13) (2022), 228–239.

22.

Xie

, et al., A job shop scheduling algorithm that can dynamically generate a set of priority operations, Journal of Computer Science 31(3) (2008).

23.

Zhao

, Hang

and Wang

, A product comprehensive scheduling algorithm based on virtual component level partition coding, Computer Integrated Manufacturing System 21(9) (2015), 2435.

24.

, Guo

and Song

, Integrated scheduling algorithm based on an operation relationship matrix table for tree-structured products, International Journal of Production Research 56(16) (2018), 5437–5456.

25.

Xiao

, et al., CapMatch: Semi-supervised contrastive transformer capsule with feature-based knowledge distillation for human activity recognition, IEEE Transactions on Neural Networks and Learning Systems (2023).

26.

Xiao

, et al., Deep contrastive representation learning with self-distillation, IEEE Transactions on Emerging Topics in Computational Intelligence (2023).

27.

Xiao

, et al., Densely knowledge-aware network for multivariate time series classification, IEEE Transactions on Systems, Man, and Cybernetics: Systems (2024).

28.

Chen

and Ying

, SF-FWA: A self-adaptive fast fireworks algorithm for effective large-scale optimization, Swarm and Evolutionary Computation 80 (2023), 101314.

29.

Maxim A. Dulebenets, An Adaptive Polyploid Memetic Algorithm for scheduling trucks at a cross-docking terminal, Information Sciences 565 (2021), 390–421.

30.

Prashant Singh, et al., Development of exact and heuristic optimization methods for safety improvement projects at level crossings under conflicting objectives, Reliability Engineering & System Safety 220 (2022), 108296.

31.

Maxim A. Dulebenets, A diffused memetic optimizer for reactive berth allocation and scheduling at marine container terminals in response to disruptions, Swarm and Evolutionary Computation 80 (2023), 101334.

32.

Emilio Singh and Nelishia Pillay, A study of ant-based pheromone spaces for generation constructive hyper-heuristics, Swarm and Evolutionary Computation 72 (2022), 101095.

Integrated scheduling algorithm of reversed device network based on operation genealogy table

Abstract

Keywords

1 Introduction

2 Problem description

3.1 Establishment of operation genealogy table

3.4 Crossover method

4 Numerical experiments

4.1 Parameters setting

Table 3 Algorithm parameters corresponding to different levels of impact factors Parameters Factor Level 1 2 3 4 Ps n*1 n*2 n*3 n*4 G 50 100 150 200 Pc 0.6 0.7 0.8 0.9 Pm 0.1 0.2 0.3 0.4

Conflict of interest

Funding

References

Table 3
Algorithm parameters corresponding to different levels of impact factors

Parameters Factor Level

1 2 3 4

Ps n1 n2 n3 n4

G 50 100 150 200

Pc 0.6 0.7 0.8 0.9

Pm 0.1 0.2 0.3 0.4