CN111652412A - A kind of neighborhood search scheduling method and device applied to replacement flow workshop - Google Patents

Abstract

The invention discloses a neighborhood search scheduling method and device applied to a replacement flow shop. The method includes: acquiring a time matrix about a machine tool, a workpiece and the processing time of the workpiece, generating an initial processing sequence of the workpiece, and forming a Gantt chart ; Determine the critical path under the initial processing sequence, and the critical path is the process path with the longest total processing time; Based on the target workpiece and its adjacent workpieces, determine the neighborhood feature blocks and key points, and the target workpiece is the head and tail The workpiece and the first workpiece on the critical path of each machine tool, the neighborhood feature block is the area where the Gantt chart structure changes after the adjacent workpiece is exchanged, and the key point is the critical path and the adjacent workpiece. The intersection of the domain feature block; after exchanging the target workpiece and its adjacent workpieces, if the key point moves forward, the exchange is performed; if the key point moves backward, the exchange is not performed; in this way, the calculation accuracy is ensured and the calculation is greatly reduced. frequency.

Description

A kind of neighborhood search scheduling method and device applied to replacement flow workshop

technical field

The invention belongs to the field of workshop scheduling, and more particularly, relates to a method and device for neighborhood search and scheduling applied to a replacement flow workshop.

Background technique

Production scheduling is to reasonably determine the processing path, processing time and operation of each processing object under the constraints of certain production conditions to achieve certain production goals, which can be defined as "allocating limited resources to several tasks in time. , to meet one or more objectives". A large number of production scheduling problems exist in the manufacturing industry. Under the trend of intelligent manufacturing, more and more production enterprises focus on production scheduling problems, develop better scheduling algorithms, and strive to pursue better solutions. In order to achieve the goal of reducing costs and improving production efficiency. Among them, the Permutation Flowshop Scheduling Problem (PFSP) belongs to the classical NP-hard problem, which has complexities such as exponential explosion and process correlation.

The traditional "model + algorithm" workshop scheduling is very mature, and people have achieved very rich results in related fields. However, with the development of intelligent and flexible workshops, the amount of workshop data becomes larger and larger, and the solution space of the corresponding heuristic algorithms and meta-heuristic algorithms becomes more and more complex, which puts forward more challenges for the performance of the algorithm itself. high challenge.

However, the current algorithms are generalized algorithms, which do not analyze and improve the structure and characteristics of the manufacturing system problem itself, and are not enough to solve the increasingly complex actual production problems. Therefore, it is urgent to analyze the problem structure itself, find the rules, and combine with meta-heuristic algorithms to realize intelligent scheduling in the new era.

SUMMARY OF THE INVENTION

Aiming at the defects and improvement requirements of the prior art, the present invention provides a neighborhood search scheduling method and device applied to a replacement flow shop to solve the technical problem that the existing shop scheduling method cannot be applied to huge workshop data.

In order to achieve the above object, the present invention provides a neighborhood search and scheduling method applied to a replacement flow shop, comprising the following steps:

S1: Obtain the time matrix about the machine tool, the workpiece and the processing time of the workpiece, generate the initial processing sequence of the workpiece, and form a Gantt chart;

S2: Determine the critical path under the initial processing sequence, the critical path is the process path with the longest total processing time; based on the target workpiece and its adjacent workpieces, determine the neighborhood feature blocks and key points, and the target workpiece is The first and last workpieces and the first workpiece on the critical path of each machine tool, the neighborhood feature block is the area where the Gantt chart structure changes after the adjacent workpieces are exchanged, and the key point is the relationship between the critical path and the The intersection of neighborhood feature blocks;

S3: After exchanging the target workpiece and its adjacent workpieces, if the key point moves forward, the exchange is performed; if the key point moves backward, the exchange is not performed;

S4: Repeat the operations of steps S2 and S3 for the new machining sequence obtained, until the total machining time cannot be shortened by exchanging all adjacent workpieces, then output the optimal machining sequence.

Further, before the step S2, a multi-neighbor search operation is performed on the initial processing sequence;

The multi-neighbor search operation includes:

randomly select two workpieces in said new machining sequence, reversing the order of all workpieces between the two workpieces; or

randomly select three workpieces in the new machining sequence, and swap the positions of the two sequences between the three workpieces; or

Two workpieces are randomly selected in the new machining sequence, and the positions of the two workpieces are swapped.

Further, after the step S4, combined with the meta-heuristic algorithm, the multi-neighbor search operation is performed on the optimal processing sequence, and steps S2-S4 are repeated to obtain a global optimal solution.

Further, the meta-heuristic algorithm includes one of the following:

Simulated annealing algorithm, tabu search algorithm, genetic algorithm, ant colony optimization algorithm, particle swarm optimization algorithm, artificial fish swarm algorithm, artificial bee colony algorithm, artificial neural network algorithm.

Another aspect of the present invention provides a neighborhood search and scheduling device applied to a replacement flow shop, comprising:

The initialization module is used to obtain the time matrix about the machine tool, the workpiece and the processing time of the workpiece, generate the initial processing sequence of the workpiece, and form a Gantt chart;

The calculation module is used to determine the critical path under the initial processing sequence, the critical path is the process path with the longest total processing time; based on the target workpiece and its adjacent workpieces, determine the neighborhood feature blocks and key points, the The target workpiece is the first workpiece on the first and last workpieces on the critical path of each machine tool, the neighborhood feature block is the area where the Gantt chart structure changes after the adjacent workpieces are exchanged, and the key point is the critical path the intersection with the neighborhood feature block;

The exchange module is used to exchange the target workpiece and its adjacent workpieces, if the key point moves forward, the exchange is performed; if the key point moves backward, the exchange is not performed;

The output module is configured to re-input the obtained new processing sequence into the calculation module and the exchange module, and output the optimal processing sequence until the total processing time cannot be shortened by exchanging all adjacent workpieces.

Further, the device also includes:

a multi-neighborhood search operation module for performing a multi-neighborhood search operation on the initial processing sequence;

The multi-neighbor search operation includes:

randomly select two workpieces in said new machining sequence, reversing the order of all workpieces between the two workpieces; or

randomly select three workpieces in the new machining sequence, and swap the positions of the two sequences between the three workpieces; or

Two workpieces are randomly selected in the new machining sequence, and the positions of the two workpieces are swapped.

Further, the multi-neighborhood search operation module is further configured to perform the multi-neighborhood search operation on the optimal processing sequence in combination with a meta-heuristic algorithm to obtain a global optimal solution.

Further, the meta-heuristic algorithm includes one of the following:

Simulated annealing algorithm, tabu search algorithm, genetic algorithm, ant colony optimization algorithm, particle swarm optimization algorithm, artificial fish swarm algorithm, artificial bee colony algorithm, artificial neural network algorithm.

In general, through the above technical solutions conceived by the present invention, the following beneficial effects can be achieved:

(1) By defining a new neighborhood structure, the present invention determines key paths, neighborhood feature blocks and key points, and excavates their related laws, and applies them to the scheduling problem of the replacement assembly shop, thereby shortening the calculation of the optimal solution. time, and improve the calculation accuracy, thereby improving the production stability and product quality, and reducing the product manufacturing cycle.

(2) The simplified operation of calculating the total processing time and the operation of eliminating invalid calculation in the present invention can greatly increase the efficiency of the algorithm, eliminate the problem of combined explosion caused by the increase in the number of workpieces, reduce the requirements for computer performance, and expand the application. range, higher universality.

(3) The present invention avoids the problem that a single search method is easy to fall into a local optimal solution by adopting a multi-neighbor search operation, thereby reducing the quality of the solution.

Description of drawings

1 is a flowchart of a neighborhood search and scheduling method applied to a replacement flow shop provided by the present invention;

2 is a schematic diagram of the neighborhood structure of a replacement flow workshop provided by an embodiment of the present invention;

3 is a schematic diagram of a critical path of a replacement flow workshop provided by an embodiment of the present invention;

4 is a schematic diagram of a neighborhood feature block of a replacement flow shop provided by an embodiment of the present invention;

5 is a schematic diagram of key points of a displacement flow workshop provided by an embodiment of the present invention;

6 is a schematic diagram of a method for simplifying key points of a replacement flow workshop provided by an embodiment of the present invention;

FIG. 7 is a flowchart of the combination of simulated annealing algorithm and neighborhood search provided by an embodiment of the present invention.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention. In addition, the technical features involved in the various embodiments of the present invention described below can be combined with each other as long as they do not conflict with each other.

As shown in Figure 1, it is a flowchart of a neighborhood search and scheduling method applied to a replacement flow shop provided by the present invention, comprising the following steps:

S1: Obtain the time matrix about the machine tool, the workpiece and the processing time of the workpiece, generate the initial processing sequence of the workpiece, and form a Gantt chart;

S2: Determine the critical path under the initial processing sequence, the critical path is the process path with the longest total processing time; based on the target workpiece and its adjacent workpieces, determine the neighborhood feature blocks and key points, and the target workpiece is The first and last workpieces and the first workpiece on the critical path of each machine tool, the neighborhood feature block is the area where the Gantt chart structure changes after the adjacent workpieces are exchanged, and the key point is the relationship between the critical path and the The intersection of neighborhood feature blocks;

S3: After exchanging the target workpiece and its adjacent workpieces, if the key point moves forward, the exchange is performed; if the key point moves backward, the exchange is not performed;

S4: Repeat the operations of steps S2 and S3 for the new machining sequence obtained, until the total machining time cannot be shortened by exchanging all adjacent workpieces, then output the optimal machining sequence.

The related terms are specifically introduced below to facilitate a better understanding of the present invention.

1. Definition of neighborhood and critical path of replacement flow workshop

In the current model of the replacement flow shop, the associated neighborhood search and critical path definitions do not appear. In the present invention, the neighborhood and critical path of the replacement flow shop are defined as follows:

(1) Definition of neighborhood search for replacement flow shop

Swap the processing order of all two adjacent workpieces in turn. If the quality of the solution becomes better, update it, otherwise continue to exchange the next set of workpieces until any two adjacent workpieces in the sequence exchange positions, and the result cannot be improved, the default Obtain the local optimal solution in the current neighborhood.

As shown in Figure 2, under the current neighborhood search, the positions of workpiece 9 and workpiece 8 are exchanged. If the exchange makes the final completion time smaller, the exchange is performed, otherwise, continue to judge whether workpiece 8 and workpiece 5 can make the completion time become smaller. After several iterations, if any exchange of adjacent workpieces in the graph cannot make the completion time smaller, it is judged that the local optimal solution in the current neighborhood is reached, and the neighborhood search is completed.

(2) Definition of critical path of replacement flow workshop

The concept of the critical path first appeared in the job shop scheduling problem. The machining process of the workpiece on the critical path satisfies the property: the process path with the longest processing time or the process moves on the non-critical path, and the processing time will not change. If the process satisfies the above properties, it is judged to be on the critical path. Following this definition, the critical path in the permutation flow shop problem is shown in Figure 3. Since the sequence of operations cannot be changed, it means that all workpieces are on the critical path.

2. Simplified calculation of neighborhood search for replacement flow workshop

According to the neighborhood search method defined in the present invention, the problem can already be calculated, but as with the traditional method, when the scale of the problem increases, the calculation amount will explode exponentially due to the need to repeatedly calculate the completion time of the entire processing process. , the calculation time and accuracy will also drop sharply, which cannot meet the current scheduling needs. Therefore, the present invention simplifies the neighborhood search method in combination with the definition of the critical path. The specific operations are as follows:

1. Neighborhood feature block simplification

As shown in Figure 4, assuming that the currently exchanged workpieces are 8 and 5, then the changed part of the original Gantt chart is only the area shown by the step shape in the figure, and the structure of the rest will not change. Therefore, in the calculation process, it is only necessary to calculate the change of the stepped area, and then the overall processing time change can be known. By applying this method, a certain amount of calculation can be reduced.

2. Simplification of key points

Combining the above step-shaped neighborhood feature block with the critical path, an intersection can be found and set as a key point. As shown in Figure 5.

The value of the keypoint is equal to the start time of the operation where the critical path is adjacent to the selected feature block area. Combined with the critical path, it can be obtained: when the key point is moved backward, the final result will not be better; when the key point is moved forward, the final result will not be worse.

Therefore, it is only necessary to calculate the movement of key points to determine the final change, which can greatly reduce the amount of calculation and the influence of the number of machine tools on the final result.

3. The number of key point calculations is simplified

When the number of workpieces to be processed is large, the critical paths and key points need to be calculated frequently, which will also affect the overall calculation efficiency. Therefore, the present invention finds the corresponding Gantt chart rule through analysis, which can greatly reduce the number of calculations.

As shown in Figure 6, the neighborhood satisfies the following rules: (1) When there are 4 or more consecutive key workpieces on the same machine tool, the intermediate process is exchanged, and the final result will not be better; (2) Only the beginning and end and The workpiece adjacent to the first workpiece on the critical path of each machine tool.

Swap sequences that might make the results better in this Gantt are only 1 and 15, 5 and 11, 11 and 7, 7 and 14, 14 and 1, 6 and 13, 13 and 10, 2 and 3. Therefore, the optimal solution only needs to be calculated 8 times according to the calculation method of the above key points.

After screening according to the above two rules, no matter how large the problem is, it only needs to calculate 2m+2 times at most to get the optimal solution in the current neighborhood, where m is the number of machine tools; if this rule is not used, it is necessary to calculate n (n-1)/2 times, where n is the number of workpieces.

Taking the simulated annealing algorithm as an example, the new neighborhood search method is nested in the meta-heuristic algorithm. The overall flow chart is shown in Figure 7. Specific steps are as follows:

1. Collect the number of machine tools in the replacement flow workshop, the number of workpieces, and the processing time of each workpiece on each machine tool, so as to form multiple time matrices about the machining time of machine tools, workpieces and workpieces, and establish the replacement flow workshop The scheduling model with the shortest processing time.

2. The initial solution state S of the SA algorithm is the 1-n sequence generated by the NEH algorithm. When selecting the initial value of the control parameter, it is generally required that the value of the initial value T ₀ should be sufficiently large, it is in a high temperature state at the beginning, and the acceptance rate of Metropolis is about 1.

The initial temperature of the conventional SA algorithm is randomly set, but it often affects the final convergence performance of the algorithm. Therefore, this paper randomly generates a set of states, determines the maximum target value difference |Δ _max | between the two states, and then uses the initial acceptance probability to determine the initial temperature according to the difference. The relevant expression is T ₀ =-|Δ _max | /p ₀ , where p ₀ is the initial acceptance probability.

3. Under large-scale problems, a single search method is easy to fall into the local optimal solution, which reduces the quality of the solution. In order to improve the ubiquity of the algorithm under large-scale problems, the present invention generates a new solution in a coordinated manner of multi-neighbor search operations based on probability selection. The three neighborhood search operations are as follows:

(1) Two exchange: randomly select two points in the coding sequence, and reverse the order of all workpieces between the two points.

(2) Three exchanges: randomly select three points in the coding sequence, and exchange two sequence positions between the three points.

(3) Point exchange: randomly select two points in the coding sequence, and exchange the workpiece positions of these two points.

In order to improve the operation speed of the algorithm, when the optimal fitness of the new solution generated according to the above method does not change within a certain number of iterations, the algorithm is determined to end and the search at the current temperature is completed.

4. After completing the search, enter the new neighborhood search stage, first find the key path and key points under the current processing order. The changes of the adjacent workpiece key points of the first workpiece on the critical path of each machine tool are judged in turn. If the key point is moved forward, the current machining sequence exchange is retained. If it is moved backward, the current processing sequence exchange will be abandoned. Perform a new neighborhood search operation on the obtained new processing sequence until all adjacent processes are exchanged and cannot be optimized, then this step ends.

5. Judge whether to accept the new solution through the Metropolis criterion. After the judgment, the variable E_best is additionally set to save the global optimal solution, which is not affected by the Metropolis criterion judgment, so as not to be replaced in subsequent iterations.

6. Different from the standard SA algorithm, this paper uses the "Doppler" attenuation function instead of the original exponential function. This new decay function can improve the convergence speed of the solution in large-scale environments. The Doppler effect type temperature decreasing curve is expressed as:

Among them, k is the number of iterations, K is the total cooling times, and a is a custom iteration coefficient. This function is used to continuously attenuate the temperature T, and the iteration is terminated when the end temperature is reached. After the temperature decay is completed, the optimal objective function value is returned to obtain the processing sequence of the current replacement flow shop.

On the basis of the above-mentioned model and solving algorithm, in order to prove the practical application effect of the present invention, the present invention selects a large-scale TA type problem in the standard test example for simulation testing (the number of workpieces is greater than 100), and compares it with other existing existing The algorithm effects are compared, wherein KP+SA is the result of the neighborhood search nested in the SA algorithm in the present invention.

Table 1 Example parameters and example results

As shown in Table 1, the numerical values in the table represent the relative error between the optimal solution obtained by the corresponding algorithm and the known optimal solution. It can be seen that the method proposed by the present invention is far superior to the same type of algorithm. In solving the problem, great advantages have been achieved, and the calculation results are quite stable and efficient, and can be used to guide actual production.

Those skilled in the art can easily understand that the above are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention, etc., All should be included within the protection scope of the present invention.

Claims (8)

1. A neighborhood search scheduling method applied to a replacement flow shop is characterized by comprising the following steps:

s1: acquiring a time matrix related to a machine tool, a workpiece and workpiece processing time, generating an initial processing sequence of the workpiece, and forming a Gantt chart;

s2: determining a critical path under the initial processing sequence, wherein the critical path is a process path with the longest total processing time; determining neighborhood feature blocks and key points based on a target workpiece and adjacent workpieces thereof, wherein the target workpiece is a head workpiece and a tail workpiece and a first workpiece on a key path of each machine tool, the neighborhood feature blocks are regions in which the Gantt chart structure is changed after the adjacent workpieces are exchanged, and the key points are intersection points of the key paths and the neighborhood feature blocks;

s3: after exchanging the target workpiece and the adjacent workpieces, if the key point moves forward, exchanging; if the key point moves backwards, no exchange is carried out;

s4: repeating the operations of steps S2 and S3 on the obtained new machining sequence until the total machining time cannot be shortened by exchanging all the adjacent workpieces, and outputting the optimal machining sequence.

2. The neighborhood search scheduling method applied to a replacement flow plant according to claim 1, wherein, before said step S2, a multi-neighborhood search operation is performed on said initial machining sequence;

the multi-neighborhood search operation comprises:

randomly selecting two workpieces in the new processing sequence, and reversing the sequence of all the workpieces between the two workpieces; or

Randomly selecting three workpieces in the new processing sequence, and exchanging the positions of two sequences among the three workpieces; or

And randomly selecting two workpieces in the new processing sequence, and exchanging the positions of the two workpieces.

3. The neighborhood search scheduling method applied to the replacement flow shop of claim 2, wherein after the step S4, the multi-neighborhood search operation is performed on the optimal processing sequence in combination with a meta-heuristic algorithm, and the steps S2-S4 are repeated to obtain a global optimal solution.

4. The neighborhood search scheduling method applied to a permuting water plant according to claim 3, wherein said meta-heuristic algorithm comprises one of:

the method comprises the following steps of simulated annealing algorithm, tabu search algorithm, genetic algorithm, ant colony optimization algorithm, particle swarm optimization algorithm, artificial fish colony algorithm, artificial bee colony algorithm and artificial neural network algorithm.

5. A neighborhood searching and scheduling device applied to a replacement flow shop is characterized by comprising:

the initialization module is used for acquiring a time matrix related to the machine tool, the workpiece and the workpiece processing time, generating an initial processing sequence of the workpiece and forming a Gantt chart;

the calculation module is used for determining a critical path under the initial processing sequence, wherein the critical path is a process path with the longest total processing time; determining neighborhood feature blocks and key points based on a target workpiece and adjacent workpieces thereof, wherein the target workpiece is a head workpiece and a tail workpiece and a first workpiece on a key path of each machine tool, the neighborhood feature blocks are regions in which the Gantt chart structure is changed after the adjacent workpieces are exchanged, and the key points are intersection points of the key paths and the neighborhood feature blocks;

the exchange module is used for exchanging the target workpiece and the adjacent workpiece and then exchanging if the key point moves forwards; if the key point moves backwards, no exchange is carried out;

and the output module is used for inputting the obtained new machining sequence into the calculation module and the exchange module again until the total machining time cannot be shortened by exchanging all adjacent workpieces, and outputting the optimal machining sequence.

6. The neighborhood search scheduling apparatus for replacing a plant as claimed in claim 5, further comprising:

the multi-neighborhood search operation module is used for performing multi-neighborhood search operation on the initial processing sequence;

the multi-neighborhood search operation comprises:

randomly selecting two workpieces in the new processing sequence, and reversing the sequence of all the workpieces between the two workpieces; or

Randomly selecting three workpieces in the new processing sequence, and exchanging the positions of two sequences among the three workpieces; or

And randomly selecting two workpieces in the new processing sequence, and exchanging the positions of the two workpieces.

7. The neighborhood search scheduling apparatus of claim 6, wherein said multi-neighborhood search operation module is further configured to perform said multi-neighborhood search operation on said optimal processing sequence in combination with a meta-heuristic algorithm to obtain a global optimal solution.

8. The neighborhood search scheduling apparatus for replacing a plant as claimed in claim 7, wherein said meta-heuristic algorithm comprises one of:

the method comprises the following steps of simulated annealing algorithm, tabu search algorithm, genetic algorithm, ant colony optimization algorithm, particle swarm optimization algorithm, artificial fish colony algorithm, artificial bee colony algorithm and artificial neural network algorithm.

Images