CN108446814B - Tree search method and device for shop scheduling problem of same-sequence assembly line - Google Patents

Abstract

The invention belongs to the field of assembly line shop scheduling, in particular to a tree search method and device for the same sequence assembly line shop 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 the reverse search are regarded as two branches of a parent node. The optimal solution is the generated two sub-nodes. The tree structure is constructed by the above method to realize the optimal scheduling of the flow workshop in the same sequence. Compared with the prior art, the present invention shortens the maximum completion time, and the algorithm is a deterministic algorithm, and the solution result is a determined stable solution.

Description

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

technical field

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

Background technique

The assembly line shop scheduling problem is an interdisciplinary research field, involving operations research, management, automation, computer and other fields. The study of the assembly line workshop scheduling problem 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 generally belongs to the 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 algorithms mainly use meta-heuristic algorithms. The algorithm itself is random, and sometimes the results are not reproducible and unstable, and the computing time on the computer is long.

SUMMARY OF THE INVENTION

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

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

Step S2: obtain the forward child node of the current node based on the forward search method, obtain the reverse child node 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 use the newly generated forward child node and reverse child node as the current node to execute step S2;

Step S4: If the forward child node, reverse child node, and ancestor node of the current node are not equal, then return to step S2, otherwise the value of the three is the optimal solution, 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 of workpieces n, the number of machines m required to process the workpieces, and the required processing time of all workpieces on each machine p _i,j ,i= 1,2,...,m,j=1,2,...,n, the heuristic algorithm is used to solve the initial solution of the scheduling workpiece of the same sequence assembly line, as the current node of the first search.

Preferably, the heuristic algorithm is the NEH algorithm.

Preferably, the initial solution is the minimum maximum makepan of the same sequence of assembly line shop scheduling.

Preferably, the forward search method is specifically: moving each workpiece in the current node to all possible positions from front to back in turn, to obtain (n ^- 1)! For each permutation and combination, calculate the maximum completion time of 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, take the forward optimal solution as the forward child node of this search. point, otherwise, the parent node of the forward optimal solution is the forward child node of this search.

Preferably, the reverse search method is specifically: move each workpiece in the current node to all possible positions sequentially from back to front, and obtain (n ^- 1)! For each permutation and combination, 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 the value of its parent node, then take 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 solution module: It is used to solve the initial solution of the same-sequence assembly line shop scheduling by using the heuristic algorithm, 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 node of the current node based on the reverse search method;

Ancestor node judgment module: used to determine whether the current child node has an ancestor node; if the current child node has no ancestor node, the forward child node and the reverse child node are converted to the current node Move to the forward search module and the reverse search module; if the current child node has an ancestor node, then move the forward child node and the reverse child node to the data comparison module;

Data comparison module: used to compare the forward child node, the reverse child node, and its ancestor nodes, and if at least one pair is not equal, compare the forward child node, The reverse child node is transferred to the current node and transferred to the forward search module and the reverse search module, otherwise the tree search is ended by taking the value of the three as the optimal solution.

Preferably, the heuristic algorithm solving module is specifically used for the number of workpieces n, the number of machines required to process the workpieces m and the required processing time p _i,j of all workpieces on each machine in the same-sequence assembly line shop scheduling, i=1,2,...,m,j=1,2,...,n, using the heuristic algorithm to solve the initial solution of the scheduling workpiece in the same sequence assembly line, 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 line shop scheduling, the number m of machines required to process the workpieces, and the time p _i,j , i=1,2 for all workpieces to be processed on each machine. ,...,m,j=1,2,...,n.

Preferably, the heuristic algorithm solving module further comprises a heuristic algorithm storage unit, which is used for storing a pre-programmed heuristic algorithm.

Preferably, the forward search module is specifically used for:

Move each workpiece in the current node to all possible positions in turn from front to back, obtain all permutations, calculate the maximum completion time of 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 its parent node, then take the forward optimal solution as the forward child node of this search, Otherwise, the parent node of the forward optimal solution is the forward child node of this search.

Preferably, the reverse search module is specifically used for:

Move each workpiece in the current node to all possible positions from back to front 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, take 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 the tree search method and device for the same-sequence assembly line shop scheduling problem proposed by the present invention have 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 the flow chart of the tree search method realization of the same-sequence assembly line shop scheduling problem;

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

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. It should be understood by those skilled in the art that these embodiments are only used to explain the technical principle 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 the same time, and each workpiece can only be processed on one machine at the same time. The processing of workpieces is not allowed. Interrupted, the problem is to determine the processing sequence and time of the workpieces on the machine, so that the objective function is optimized. Shop scheduling problems widely exist in manufacturing and logistics systems. The main solutions 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 not reproducible, have instability, and the computing time on the computer is long. The invention provides a tree search method and device for the same-sequence assembly line shop scheduling problem, which shortens the maximum completion time, and the algorithm is deterministic. The solution result is to determine the stable solution, which can better solve the scheduling problem of the same-sequence flow shop.

A tree search method for the same-sequence assembly line shop scheduling problem according to an embodiment of the present invention, as shown in FIG. 1 , includes the following steps:

Step S101: use a heuristic algorithm to solve the initial solution of the same-sequence assembly line shop scheduling as the current node of the first search;

Step S102: obtain the forward child node of the current node based on the forward search method, obtain the reverse child node of the current node based on the reverse search method, and use the obtained forward child node, Reverse the child node to insert a new node of 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 use the newly generated forward child node and reverse child node as the current node to execute 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 first search forward child node is l21, and the reverse child node is l22, the second search takes l21 and l22 as the current nodes, respectively, to obtain the forward child node l31 of l21, the reverse child node l32, and obtain the forward child node l33 of l22, the reverse child node l34, the third The second search takes l31, l32, l33, and l34 as the current nodes, respectively, and the obtained child nodes l41, l42, l43, l44, l45, l46, l47, l48, and the binary search tree is expanded. Among them, when the second layer l21 is 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 Node l11, the comparison mechanism of the tree search method for the same sequential assembly line shop scheduling problem is the comparison between the forward sub-node l31, the reverse sub-node l32, and l11. Similarly, the third layer l34 is 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 forward child node l47 and the reverse child node is the upper two-level node l22 of l48, then the same order The comparison mechanism of the tree search method for the assembly 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 applied in the present invention can be NEH algorithm, tabu search algorithm, simulated annealing algorithm, ant colony algorithm, genetic algorithm, particle swarm algorithm, etc. The preferred solution is NEH algorithm, and the initial solution to be solved is the same-sequence assembly line shop scheduling. Minimum Maximum Completion Time.

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

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

Step S202: Perform a forward search on the current node, that is, (n-1) obtained by moving each workpiece in the current node backwards to all possible positions in turn! Perform optimization in these arrangements to obtain forward child nodes; perform reverse search on the current node, that is, each workpiece in the current node moves forward to all possible positions in turn (n-1) ! According to the structure of the binary search tree, use the obtained forward child nodes and reverse child 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 use the newly generated forward child node and reverse child node as the current node to execute Step S202.

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

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 to the permutation and combination of all possible positions sequentially from front to back. 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, which can be searched ^n-2 sorts; in this way, when j=n-1, the workpiece has one position backward, and one sort can be searched; when j=n, the workpiece has no position backwards, and there is no new sorting. This forward search can search for (n-1)! an arrangement. Calculate the minimum maximum make-time among all permutations, and get a forward optimal solution.

The forward optimal solution is compared with its parent node. If the forward optimal solution is less than or equal to the value of its parent node, the forward optimal solution is used as the positive child node of this search; 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 from back to front to the permutation and combination 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 ahead, and ⁿ -2 sorts can be searched ; So, when j=2, the workpiece has 1 position forward, and can search for 1 sorting; when j=1, the first workpiece has no position forward, and there is no new sorting. This reverse search can search for (n-1)! an arrangement. Calculate the minimum and maximum processing time among all arrangements, and obtain the inverse 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 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 of 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.

In this embodiment, the binary tree search termination condition is that the forward child node, reverse child node, and 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, if the three solutions are equal, the loop will be jumped out, the obtained solution is the optimal solution, and the tree search is over.

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, an embodiment of the present invention provides a tree search device for the same-sequence assembly line shop scheduling problem, and the device includes the following modules:

Heuristic algorithm solution module: It is used to solve the initial solution of the same-sequence assembly line shop scheduling by using the heuristic algorithm, 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 node of the current node based on the reverse search method;

Ancestor node judgment module: used to determine 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 Forward search module and reverse search module; if the current node has an ancestor node, then move the forward child node and the reverse child node to the data comparison module;

Data comparison module: used to compare the forward child node, the reverse child node, and its ancestor nodes, and if at least one pair is not equal, compare the forward child node, The reverse child node is transferred to the current node and transferred to the forward search module and the reverse search module, otherwise the tree search is ended by taking the value of the three as the optimal solution.

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

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

The data extraction unit is used to extract the number of workpieces n, the number of machines required to process the workpieces, and the processing time p _i,j , i=1,2,. ..,m ^, j=1,2,...,n.

The above-mentioned heuristic algorithm solving module also includes a heuristic algorithm storage unit, which is used to store the heuristic algorithm prepared in advance. The technical personnel 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 tree search device for the above-mentioned same-sequence assembly line shop scheduling problem is specifically used for:

Move each workpiece in the current node to all possible positions in turn from front to back, obtain all permutations, calculate the maximum completion time of 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 its parent node, then take the forward optimal solution as the forward child node of this search, Otherwise, the parent node of the forward optimal solution is the forward child node of this search.

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

Move each workpiece in the current node to all possible positions from back to front 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, take 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 that studies the scheduling optimization problem in which 5 workpieces are processed on 4 machines in the same order and the minimum maximum makepan (makespan) is solved. Among them, pi, j, i = 1, 2, 3, 4j, = 1, 2, .

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. The result of the heuristic algorithm is used as the root node. Through the judgment and comparison mechanism of the present invention, the forward search method is used to grow positive To the child node, the reverse child node is grown in the reverse search method until the end condition of the tree search loop occurs. In order to verify the validity and reliability of the present invention, the present invention is simulated by computer software to realize the scheduling of workpieces, the number of workpieces 5 and the number of machines in the same sequence assembly line workshop scheduling, all workpieces are processed on each machine. time, as shown in Table 1.

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

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

Those skilled in the art should be aware that the method steps and apparatuses of the various examples described in conjunction with the embodiments disclosed herein can be implemented in electronic hardware, computer software, or a combination of the two, in order to clearly illustrate the 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 in electronic hardware or software depends on the specific application and design constraints of the technical solution. Skilled artisans may use different methods of implementing the described functionality for each particular application, but such implementations should not be considered beyond the scope of the present invention.

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

Claims (6)

1. a tree search method of the same sequence assembly line shop scheduling problem, is characterized in that, comprises the following steps: Step S1: use a heuristic algorithm to solve the initial solution of the same-sequence assembly line shop scheduling as the current node of the first search; Step S2: obtain the forward child node of the current node based on the forward search method, obtain the reverse child node 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 use the newly generated forward child node and reverse child node as the current node to execute step S2; Step S4: If the forward child node, reverse child node, and ancestor node of the current node are not equal, then return to step S2, otherwise the value of the three is the optimal solution, and the tree search ends; The ancestor node is the upper two-level node of the current child node; The step S1 is specifically: according to the number of workpieces n, the number of machines m required to process the workpieces, and the required processing time p _i,j , i=1,2 ,...,m,j=1,2,...,n, the heuristic algorithm is used to solve the initial solution of the scheduling workpiece in the same sequence assembly line, as the current node of the first search; The forward search method is specifically: move each workpiece in the current node to all possible positions sequentially from front to back, and obtain (n-1)! For each permutation and combination, calculate the maximum completion time of 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, take the forward optimal solution as the forward child node of this search. point, otherwise the parent node of the forward optimal solution is the forward child node of this search; The reverse search method is specifically: move each workpiece in the current node to all possible positions sequentially from back to front, and obtain (n-1)! For each permutation and combination, 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 the value of its parent node, then take 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. 2 . The tree search method for the same-sequence assembly line shop scheduling problem according to claim 1 , wherein the heuristic algorithm is the NEH algorithm. 3 . 3 . The tree search method for the same-sequence assembly line shop scheduling problem according to claim 1 , wherein the initial solution is the minimum maximum completion time of the same-sequence assembly line shop scheduling. 4 . 4. a tree search device of the same sequence assembly line shop scheduling problem, is characterized in that, Heuristic algorithm solution module: It is used to solve the initial solution of the same-sequence assembly line shop scheduling by using the heuristic algorithm, 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 node of the current node based on the reverse search method; Ancestor node judgment module: used to determine whether the current child node has an ancestor node; if the current child node has no ancestor node, the forward child node and the reverse child node are converted to the current node. The point is moved to the forward search module and the reverse search module; if the current child node has an ancestor node, the forward child node and the reverse child node are moved to the data comparison module; Data comparison module: used to compare the forward child node, the reverse child node, and its ancestor nodes, and if at least one pair is not equal, compare the forward child node, The reverse child node is transferred to the current node and transferred to the forward search module and the reverse search module, otherwise the tree search is terminated with the value of the three as the optimal solution; The heuristic algorithm solving module is specifically used for the number of workpieces n, the number of machines m required to process the workpieces, and the required processing time p _i,j , i=1 of all workpieces on each machine in the same-order assembly line shop scheduling ,2,...,m,j=1,2,..n.,, the heuristic algorithm is used to solve the initial solution of the scheduling workpiece of the same sequence assembly line, as the current node of the first search; The forward search module is specifically used for: Move each workpiece in the current node to all possible positions in turn from front to back, obtain all permutations, calculate the maximum completion time of 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 its parent node, then take the forward optimal solution as the forward child node of this search, Otherwise, the parent node of the forward optimal solution is the forward child node of this search; Move each workpiece in the current node to all possible positions from the back to the front in turn, get all the permutations, calculate the maximum completion time of all the permutations, 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, take 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. 5. the tree search device of the same sequence assembly line shop scheduling problem according to claim 4, is characterized in that, the input end of described heuristic algorithm solving module is data extraction unit; The data extraction unit is used to extract the number n of workpieces in the same-sequence line shop scheduling, the number m of machines required to process the workpieces, and the time p _i,j , i=1,2 for all workpieces to be processed on each machine. ,...,m,j=1,2,...,n. 6 . The tree search device for the same-sequence assembly line shop scheduling problem according to claim 4 , wherein the heuristic algorithm solving module further comprises a heuristic algorithm storage unit, which is used for storing pre-compiled heuristic algorithms. 7 .

Images