CN108446814A - With the tree searching method and device of sequential pipeline Job-Shop problem - Google Patents

Abstract

The invention belongs to the field of assembly line workshop scheduling, and in particular relates to a tree search method and device for same-sequence assembly line workshop scheduling. It aims to solve the optimal scheduling problem of the same sequence assembly line workshop. First, the NEH algorithm is used to obtain the initial solution, and then combined with the tree search method, the forward search and reverse search are used as two branches of a parent node, and are optimized separately, and compared with the parent node, the forward optimal solution and the reverse optimal solution are obtained. The optimal solution is the two generated sub-nodes. Through the above method to build a tree structure, the optimal scheduling of the same sequence flow workshop is realized. Compared with the prior art, the invention shortens the maximum completion time, and the algorithm is a deterministic algorithm, and the solution result is a definite stable solution.

Description

Tree search method and device for the same-sequence assembly line shop scheduling problem

technical field

The invention belongs to the field of assembly line workshop scheduling, and in particular relates to a tree search method and device for the same-sequence assembly line workshop scheduling problem.

Background technique

The problem of assembly line shop scheduling is a cross-cutting research field, involving operations research, management, automation, computer and other fields. The research on assembly line workshop scheduling can help enterprises improve production efficiency, enhance the flexibility and reliability of production, and has important research significance for advanced manufacturing and intelligent manufacturing.

The assembly line shop scheduling problem is generally an NP-complete problem, and the search for the target solution involves the combinatorial explosion of the solution space. The current solution methods mainly include tabu search algorithm, simulated annealing algorithm, ant colony algorithm, particle swarm algorithm and so on. The above algorithm mainly adopts meta-heuristic algorithm. The algorithm itself has randomness, sometimes the results cannot be reproduced, it is unstable, and it takes a long time to calculate on the computer.

Contents of the invention

In order to solve the above-mentioned problems in the prior art, that is, in order to solve the optimal scheduling problem of the same-sequence assembly line workshop, one aspect of the present invention proposes a tree search method for the same-sequence assembly line workshop scheduling problem, including the following steps:

Step S1: Use a heuristic algorithm to solve the initial solution of the same-order assembly line shop scheduling, as the current node of the first search;

Step S2: Obtain the forward sub-nodes of the current node based on the forward search method, obtain the reverse sub-nodes of the current node based on the reverse search method, and construct a binary search tree;

Step S3: Determine whether the current child node has an ancestor node, if the current child node has an ancestor node, then execute step S4, otherwise execute with the newly generated forward child node and reverse child node as the current node Step S2;

Step S4: If the forward child node, reverse child node, and ancestor node of the current node are not equal, return to step S2, otherwise, the optimal solution is the value of the three, and the tree search ends;

The ancestor node is the upper two-level node of the current child node.

Preferably, the step S1 is specifically: according to the number n of workpieces in the same-sequence assembly line workshop scheduling, the number m of machines required to process workpieces, and the time p _i,j ,i= 1,2,...,m,j=1,2,...,n, use the heuristic algorithm to solve the initial solution of the same-sequence assembly line shop scheduling workpiece, and use it as the current node of the first search.

Preferably, the heuristic algorithm is the NEH algorithm.

Preferably, the initial solution is the minimum and maximum completion time of the same-sequence assembly line shop scheduling.

Preferably, the forward search method specifically includes: moving each workpiece in the current node from front to back to all possible positions in order to obtain (n ^- 1)! Permutations and combinations, calculate the maximum completion time in all permutations and combinations, and select the minimum value as the forward optimal solution;

Compare the forward optimal solution with its parent node, if the forward optimal solution is less than or equal to the value of its parent node, then use the forward optimal solution as the forward child node of this search point, otherwise the parent node of the forward better solution is the forward child node of this search.

Preferably, the reverse search method specifically includes: moving each workpiece in the current node from back to front to all possible positions sequentially, to obtain (n ^- 1)! Permutations and combinations, calculate the maximum completion time in all permutations and combinations, and select the minimum value as the reverse optimal solution;

Compare the reverse optimal solution with its parent node, if the reverse optimal solution is less than or equal to the value of its parent node, then use the reverse optimal solution as the reverse child node of this search, otherwise use The parent node of the reverse optimal solution is the reverse child node of this search.

Another aspect of the present invention also proposes a tree search device for the same-sequence assembly line shop scheduling problem,

Heuristic algorithm solving module: used to use heuristic algorithm to solve the initial solution of the same-order assembly line shop scheduling, as the current node of the first search;

Forward search module: used to search forward child nodes of the current node based on the forward search method;

Reverse search module: used to search the reverse child nodes of the current node based on the reverse search method;

Ancestor node judging module: used to judge whether the current child node has an ancestor node; if the current child node has no ancestor node, then convert the forward child node and the reverse child node into the current node Move to forward search module and reverse search module; If current child node has ancestor node, then described forward child node, described reverse child node are moved to data comparison module;

Data comparison module: used to compare the forward child node, the reverse child node, and its ancestor node in pairs, and if at least one pair is not equal, compare the forward child node, The reverse child node is converted into the current node and sent to the forward search module and the reverse search module, otherwise, the tree search ends with the values of the three as the optimal solution.

Preferably, the heuristic algorithm solving module is specifically configured to base on the number n of workpieces in the same-sequence assembly line workshop scheduling, the number m of machines required to process workpieces, and the required processing time p _i,j of all workpieces on each machine, i=1,2,...,m,j=1,2,...,n, use a heuristic algorithm to solve the initial solution of the same-sequence assembly line workshop scheduling workpiece, and use it as the current node of the first search.

Preferably, the input end of the heuristic algorithm solving module is a data extraction unit;

The data extraction unit is used to extract the number n of workpieces in the same-sequence assembly line workshop scheduling, the number m of machines required to process workpieces, and the time p _i,j required to process all workpieces on each machine, i=1,2 ,...,m,j=1,2,...,n.

Preferably, the heuristic algorithm solution module further includes a heuristic algorithm storage unit for storing pre-programmed heuristic algorithms.

Preferably, the forward search module is specifically used for:

For each workpiece in the current node, move from front to back to all possible positions in turn, get all permutations and combinations, calculate the maximum completion time of all permutations and combinations, and select the minimum value as the forward optimal solution;

Comparing the forward optimal solution with its parent node, if the forward optimal solution is less than or equal to its parent node, then use the forward optimal solution as the forward child node of this search, Otherwise, the parent node of the forward optimal solution is used as the forward child node of this search.

Preferably, the reverse search module is specifically used for:

Move each workpiece in the current node from back to front to all possible positions in turn, get all permutations and combinations, calculate the maximum completion time of all permutations and combinations, and select the minimum value as the reverse optimal solution;

Compare the reverse optimal solution with its parent node, if the reverse optimal solution is less than or equal to its parent node, then use the reverse optimal solution as the reverse child node of this search, otherwise the reverse optimal solution The parent node of the better solution is the reverse child node of this search.

Those skilled in the art should be able to realize that a tree search method and device for the same-sequence assembly line workshop scheduling problem proposed by the present invention has the following advantages:

(1) Compared with the existing algorithm, this algorithm shortens the maximum completion time;

(2) The algorithm is a deterministic algorithm, and the solution result is a definite stable solution;

(3) It can help enterprises improve production efficiency and enhance the flexibility and reliability of production.

Description of drawings

Fig. 1 is a schematic flow chart of the implementation of the tree search method for the same-sequence assembly line shop scheduling problem;

Fig. 2 is a kind of Gantt diagram of the workshop scheduling of the same sequence assembly line;

Fig. 3 is a schematic diagram of the tree structure of the tree search method.

Detailed ways

Preferred embodiments of the present invention are described below with reference to the accompanying drawings. Those skilled in the art should understand that these embodiments are only used to explain the technical principles of the present invention, and are not intended to limit the protection scope of the present invention.

The workshop scheduling problem means that the scheduled workpieces need to be processed on different machines. Each machine can only process one workpiece at most at the same time, and each workpiece can only be processed on one machine at most at the same time. The processing of workpieces is not allowed. Interruption, the problem is to determine the processing sequence and timing of workpieces on the machine so that the objective function is optimized. Workshop scheduling problems widely exist in manufacturing and logistics systems. The solving methods mainly include tabu search algorithm, simulated annealing algorithm, ant colony algorithm, particle swarm algorithm, etc. The above algorithms mainly use meta-heuristic algorithm, and the algorithm itself has randomness. Sometimes the results are irreproducible and unstable, and the calculation time on the computer is long. The present invention provides a tree search method and device for the same-sequence assembly line workshop scheduling problem, which shortens the maximum completion time, and the algorithm is deterministic The result of the solution is a stable solution, which can better solve the scheduling problem of the same sequence flow workshop.

The tree search method for the same-sequence assembly line shop scheduling problem of an embodiment of the present invention, as shown in Figure 1, includes the following steps:

Step S101: use a heuristic algorithm to solve the initial solution for the same-order assembly line shop scheduling, and use it as the current node for the first search;

Step S102: Obtain the forward sub-nodes of the current node based on the forward search method, obtain the reverse sub-nodes of the current node based on the reverse search method, and use the obtained forward sub-nodes, Reverse the child node to insert a new node in the binary search tree;

Step S103: Determine whether the current child node has an ancestor node, if the current child node has an ancestor node, then execute step S104, otherwise execute with the newly generated forward child node and reverse child node as the current node Step S102;

Step S104: If the forward child node, reverse child node, and ancestor node of the current node are not equal, return to step S102; otherwise, take the value of the three as the optimal solution, and the tree search ends.

The ancestor node is defined as the upper two-level node of the current child node. Taking Figure 3 as an example, the root node of the binary search tree is l11, the forward child node of the first search is l21, and the reverse child node is l22, the second search takes l21 and l22 as the current node respectively, and obtains the forward child node l31 of l21, the reverse child node l32, obtains the forward child node l33 of l22, the reverse child node l34, and the third The second search takes l31, l32, l33, and l34 as the current node, and obtains the child nodes l41, l42, l43, l44, l45, l46, l47, and l48, so that the binary search tree is expanded. Among them, when the second layer l21 is taken as the current node, the forward child node l31 of l21, and the reverse child node l32, the ancestor node is the forward child node l31, and the upper two levels of the reverse child node l32 For node l11, the tree search method comparison mechanism for the sequential assembly line workshop scheduling problem is the forward sub-node l31, the reverse sub-node l32, and the pairwise comparison of l11. Similarly, the third layer l34 is used as the current node At this time, the forward child node of l34 is l47, and the reverse child node is l48. At this time, the ancestor node is the upper two-level node l22 with the forward child node l47 and the reverse child node l48, and the order is the same The comparison mechanism of the tree search method for the assembly line shop scheduling problem is that the forward child node is l47, the reverse child node is l48, and the three are compared with l22.

The heuristic algorithm used in the present invention can be NEH algorithm, tabu search algorithm, simulated annealing algorithm, ant colony algorithm, genetic algorithm, particle swarm algorithm, etc., and its preferred scheme is NEH algorithm, and the initial solution for solving is the same sequence assembly line workshop scheduling Minimum and maximum completion time.

In order to facilitate the understanding of this embodiment, the tree search method for the same-sequence assembly line shop scheduling problem disclosed in the embodiment of the present invention is described in detail below.

Step S201: According to the number of workpieces n, the number of machines m and the processing time p _i,j required for processing all workpieces on each machine in the same-order assembly line workshop scheduling, i=1,2,...,m ^, j =1,2,...,n, using the NEH algorithm to solve the minimum and maximum completion time of the same-sequence assembly line shop scheduling, as the current node of the first search.

Step S202: Carry out a forward search on the current node, that is, each workpiece in the current node moves backwards to all possible positions one by one (n-1)! permutations, optimize in these permutations, and obtain forward sub-nodes; perform a reverse search on the current node, that is, move each workpiece in the current node forward to all possible positions in sequence (n-1) ! permutations, optimize in these permutations, and obtain reverse sub-nodes; based on the structure of the binary search tree, use the obtained forward sub-nodes and reverse sub-nodes to insert new nodes of the binary search tree.

Step S203: Determine whether the current child node has an ancestor node, if the current child node has an ancestor node, then execute step S204, otherwise execute with the newly generated forward child node and reverse child node as the current node Step S202.

Step S204: Compare the forward child node, reverse child node and ancestor node in pairs, if at least one pair is unequal, return to step S202. If the three solutions are equal, then jump out of the loop, the value of the three is the optimal solution, and the tree search ends.

In this embodiment, the generation method of the forward child node in step S202 is:

For each workpiece j=1,2,...,n in the current node, move from front to back to the permutations and combinations of all possible positions. When j=1, the workpiece has n-1 possible moving positions backward, and n-1 sorting can be searched; when j=2, the workpiece has n ^- 2 possible moving positions backward, and can be searched ^n-2 sorting; thus, when j=n-1, the workpiece has 1 position backward, and 1 sorting can be searched; when j=n, the workpiece has no backward position, and there is no new sorting. This forward search can search to (n-1)! permutations. Calculate the minimum and maximum completion time among all permutations, and obtain a forward optimal solution.

The forward better solution is compared with its parent node, if the forward better solution is less than or equal to the value of its parent node, the forward better solution is used as the forward child node of this search, otherwise the forward better solution is used The parent node of the better solution is the forward child node of this search.

In this embodiment, the generation method of the reverse child node in step S202 is:

For each workpiece j=1 ^, 2,...,n in the current node, move sequentially from back to front to the permutations and combinations of all possible positions. When j=n, the workpiece has n- ¹ positions forward, and n-1 sorts can be searched; when j=n-1, the workpiece has n-2 positions forward, and ^n- 2 sorts can be searched ; In this way, when j=2, the workpiece has 1 position forward, and a sorting can be searched; when j=1, the first workpiece has no position forward, and there is no new sorting. This reverse search can search to (n-1)! permutations. Calculate the minimum and maximum processing time among all permutations, and obtain the reverse optimal solution.

The reverse optimal solution is compared with the parent node, if the reverse optimal solution is less than or equal to the value of its parent node, the reverse optimal solution is used as the reverse child node of this search, otherwise the parent node of the reverse optimal solution is used The node is the reverse child node of this search.

To sum up, step S202 calculates the minimum and maximum completion time in all arrangements through forward search and reverse search, and then obtains the forward child node and reverse child node through comparison, that is, the two child nodes of the parent node , and so on, the binary tree search structure is generated continuously.

In this embodiment, the binary tree search termination condition is that the forward child node, the reverse child node, and the ancestor node of the current node are equal, specifically: comparing the reverse child node, the forward child node, and the ancestor node, The three are compared in pairs, and if the three solutions are equal, the loop will be jumped out, and the obtained solution is the optimal solution, and the tree search ends.

In order to facilitate the understanding of the tree search method for the same-sequence assembly line shop scheduling problem provided by the above embodiments, the embodiment of the present invention provides a tree search device for the same-sequence assembly line shop scheduling problem, which includes the following modules:

Heuristic algorithm solving module: used to use heuristic algorithm to solve the initial solution of the same-order assembly line shop scheduling, as the current node of the first search;

Forward search module: used to search forward child nodes of the current node based on the forward search method;

Reverse search module: used to search the reverse child nodes of the current node based on the reverse search method;

Ancestor node judging module: used to judge whether the current node has an ancestor node; if the current node has no ancestor node, the forward child node and the reverse child node are converted to the current node and transferred to A forward search module and a reverse search module; if the current node has an ancestor node, the forward child node and the reverse child node are transferred to the data comparison module;

Data comparison module: used to compare the forward child node, the reverse child node, and its ancestor node in pairs, and if at least one pair is not equal, compare the forward child node, The reverse child node is converted into the current node and sent to the forward search module and the reverse search module, otherwise, the tree search ends with the values of the three as the optimal solution.

In specific implementation, the above-mentioned heuristic algorithm solving module is specifically used to base on the number of workpieces n in the same-order assembly line workshop scheduling, the number of machines m required to process workpieces, and the time p _i,j required to process all workpieces on each machine, i=1,2,...,m,j=1,2,...,n, use the heuristic algorithm to solve the minimum and maximum completion time of the same sequence assembly line shop scheduling workpiece, as the current result of the first search point.

The input end of the heuristic algorithm solving module is a data extraction unit.

The data extraction unit is used to extract the number n of workpieces in the same-order assembly line workshop scheduling, the number m of machines required to process workpieces, and the time p _i,j required to process all workpieces on each machine, i=1,2,. ..,m ^, j=1,2,...,n.

The above-mentioned heuristic algorithm solving module also includes a heuristic algorithm storage unit for storing pre-programmed heuristic algorithms. The technician can select the heuristic algorithm program to be used according to the actual use situation, and store the program in the heuristic algorithm storage unit. unit, the algorithm program can be used directly when using the tree search device for the same-sequence assembly line shop scheduling problem.

Further, the forward search module of the above-mentioned tree search device for the same-sequence assembly line shop scheduling problem is specifically used for:

For each workpiece in the current node, move from front to back to all possible positions in turn, get all permutations and combinations, calculate the maximum completion time of all permutations and combinations, and select the minimum value as the forward optimal solution;

Comparing the forward optimal solution with its parent node, if the forward optimal solution is less than or equal to its parent node, then use the forward optimal solution as the forward child node of this search, Otherwise, the parent node of the forward optimal solution is used as the forward child node of this search.

The reverse search module of the above-mentioned tree search device for the same-order assembly line shop scheduling problem is specifically used for:

Move each workpiece in the current node from back to front to all possible positions in turn, get all permutations and combinations, calculate the maximum completion time of all permutations and combinations, and select the minimum value as the reverse optimal solution;

Compare the reverse optimal solution with its parent node, if the reverse optimal solution is less than or equal to its parent node, then use the reverse optimal solution as the reverse child node of this search, otherwise the reverse optimal solution The parent node of the better solution is the reverse child node of this search.

The same-sequence assembly line shop scheduling problem, as shown in Figure 2, is a Gantt chart of the scheduling optimization problem that studies the processing of 5 workpieces on 4 machines in the same order and solves the minimum and maximum completion time (makespan). Among them, pi, j, i=1, 2, 3, 4j, = 1, 2,..., Table 5 shows the processing time required for all workpieces on each machine.

The scheduling optimization algorithm of the present invention is a tree search method, and its basic binary tree search structure is shown in Figure 3, with the result of the heuristic algorithm solution as the root node, through the judgment and comparison mechanism of the present invention, the forward search method grows positive To the child node, the reverse child node is grown by the reverse search method until the end condition of the tree search loop occurs. In order to verify the effectiveness and reliability of the present invention, the present invention is simulated by computer software to realize the scheduling of workpieces, with the number of workpieces 5 and the number of machines 4 in the sequential assembly line workshop scheduling, and all workpieces are processed on each machine. time, as shown in Table 1.

Table 1. Machining schedule required for all workpieces to be processed on each machine

The tree search method of the present invention runs on a computer to obtain a result of 24 for the same sequence assembly line workshop scheduling problem. Compared with the existing method of 25, the minimum and maximum completion time is reduced by 4%, and the result is stable, which can improve production efficiency for enterprises. , the larger the calculation scale, the more obvious the effect advantage will be.

Those skilled in the art should be able to realize that the method steps and devices described in conjunction with the embodiments disclosed herein can be implemented by electronic hardware, computer software, or a combination of the two. In order to clearly illustrate electronic hardware and software In the above description, the components and steps of each example have been generally described according to their functions. Whether these functions are performed by electronic hardware or software depends on the specific application and design constraints of the technical solution. Those skilled in the art may implement the described functionality using different methods for each particular application, but such implementation should not be considered as exceeding the scope of the present invention.

So far, the technical solutions of the present invention have been described in conjunction with the preferred embodiments shown in the accompanying drawings, but those skilled in the art will easily understand that the protection scope of the present invention is obviously not limited to these specific embodiments. Without departing from the principles of the present invention, those skilled in the art can make equivalent changes or substitutions to related technical features, and the technical solutions after these changes or substitutions will all fall within the protection scope of the present invention.

Claims (12)

1. a kind of tree searching method of same sequential pipeline Job-Shop problem, which is characterized in that include the following steps：

Step S1：Initial solution with sequential pipeline Job-Shop is solved using heuritic approach, as working as first time search Preceding node；

Step S2：The positive child node of current node is obtained based on forward lookup method, is obtained currently based on reverse search method The reverse child node of node builds binary search tree；

Step S3：Judging current child node, whether there is or not ancestral's nodes, if current child node has ancestral's node, then follow the steps S4, otherwise divide Step S2 is not executed as current node using newly-generated positive child node, reverse child node；

Step S4：If the positive child node of current node, reverse child node, ancestral's node are unequal, return to step S2, otherwise with The value of three is optimal solution, and tree search terminates；

Ancestral's node is the upper two-stage node of current child node.

2. the tree searching method of same sequential pipeline Job-Shop problem according to claim 1, which is characterized in that described Step S1, specially：According to needed for workpiece number n in sequential pipeline Job-Shop, workpieces processing number of machines m and all works The time p of part required processing on each machine_i,j, i=1,2 ..., m, j=1,2 ..., n, it is asked using heuritic approach Solution is with the initial solution of sequential pipeline Job-Shop workpiece, the current node as first time search.

3. the tree searching method of same sequential pipeline Job-Shop problem according to claim 2, which is characterized in that described Heuritic approach is NEH algorithms.

4. the tree searching method of same sequential pipeline Job-Shop problem according to claim 2, which is characterized in that described Initial solution is the minimum Maximal Makespan with sequential pipeline Job-Shop.

5. the tree searching method of same sequential pipeline Job-Shop problem according to claim 1 or 2, which is characterized in that The forward lookup method, specially：All possible position is moved to from front to back successively to each workpiece in current node It sets, obtains (n-1)！A permutation and combination calculates the Maximal Makespan in all permutation and combination, select minimum value as it is positive compared with Excellent solution；

By the more excellent solution of the forward direction compared with its father node, if the more excellent solution of the forward direction is less than or equal to the value of its father node, It is the positive child node of this search with the more excellent solution of the forward direction, is otherwise searched for for this with the father node of the more excellent solution of forward direction Positive child node.

6. the tree searching method of same sequential pipeline Job-Shop problem according to claim 1 or 2, which is characterized in that The reverse search method, specially：All possible position is moved to from back to front successively to each workpiece in current node It sets, obtains (n-1)！A permutation and combination calculates the Maximal Makespan in all permutation and combination, select minimum value as inversely compared with Excellent solution；

By the reverse more excellent solution compared with its father node, if the reverse more excellent solution is less than or equal to the value of its father node, It is the reverse child node of this search with the reverse more excellent solution, is otherwise searched for for this with the father node of the reverse more excellent solution Reverse child node.

7. a kind of tree searcher of same sequential pipeline Job-Shop problem, which is characterized in that

Heuritic approach solves module：For solving the initial solution with sequential pipeline Job-Shop using heuritic approach, make For the current node of first time search；

Forward lookup module：Positive child node for searching for current node based on forward lookup method；

Reverse search module：Reverse child node for searching for current node based on reverse search method；

Ancestral's node judgment module：For node before judging group, whether there is or not ancestral's nodes；If current child node, will be described without ancestral's node Positive child node, the reverse child node switch to current node and are transplanted on forward lookup module and reverse search module；If current Child node has ancestral's node that the positive child node, the reverse child node are then transplanted on data comparison module；

Data comparison module：For the positive child node, the reverse child node and its ancestral's node, three to be compared two-by-two, If at least a pair of unequal, the positive child node, the reverse child node are switched to current node and be transplanted on forward direction Search module and reverse search module terminate tree search otherwise using the value of three as optimal solution.

8. the tree searcher of same sequential pipeline Job-Shop problem according to claim 7, which is characterized in that described Heuritic approach solves module and is specifically used for according to the machine needed for workpiece number n in sequential pipeline Job-Shop, workpieces processing The time p of device number m and all workpiece required processing on each machine_i,j, i=1,2 ..., m, j=1,2 ..., n, it uses Heuritic approach solves the initial solution with sequential pipeline Job-Shop workpiece, the current node as first time search.

9. the tree searcher of same sequential pipeline Job-Shop problem according to claim 8, which is characterized in that described The input terminal that heuritic approach solves module is data extracting unit；

The data extracting unit is for extracting with the workpiece number n in sequential pipeline Job-Shop, the machine needed for workpieces processing The time p of device number m and all workpiece required processing on each machine_i,j, i=1,2 ..., m, j=1,2 ..., n.

10. the tree searcher of same sequential pipeline Job-Shop problem according to claim 8, which is characterized in that institute It further includes heuritic approach storage unit to state heuritic approach and solve module, for storing heuritic approach prepared in advance.

11. the tree searcher of same sequential pipeline Job-Shop problem according to claim 7, which is characterized in that institute Forward lookup module is stated to be specifically used for：

All possible position is moved to from front to back successively to each workpiece in current node, obtains all arrangement groups It closes, calculates the Maximal Makespan of all permutation and combination, select minimum value as positive more excellent solution；

By the more excellent solution of the forward direction compared with its father node, if the more excellent solution of the forward direction is less than or equal to its father node, with institute The more excellent solution of forward direction is stated as the positive child node of this search, is otherwise that this is searched for just with the father node of the more excellent solution of forward direction To child node.

12. the tree searcher of same sequential pipeline Job-Shop problem according to claim 7, which is characterized in that institute Reverse search module is stated to be specifically used for：

All possible position is moved to from back to front successively to each workpiece in current node, obtains all arrangement groups It closes, calculates the Maximal Makespan of all permutation and combination, select minimum value as reverse more excellent solution；

By the reverse more excellent solution compared with its father node, if the reverse more excellent solution is less than or equal to its father node, with institute Reverse more excellent solution is stated as the reverse child node of this search, otherwise the father node of the reverse more excellent solution is the reverse of this search Child node.