CN108681818A - A kind of Optimization Scheduling of gear mechanism process - Google Patents

Abstract

The invention relates to an optimal scheduling method of a gear machining process. The method is as follows: by determining the scheduling model and optimization target of a batch of gear blanks to be processed and formed during the machining process, and using the optimal scheduling method based on a hybrid discrete harmonic search algorithm The method optimizes the objective; among them, the scheduling model is established according to the processing time of each gear on each processing machine during the machining process of the gear, and the optimization objective is to minimize the maximum completion time. The invention proposes a scheduling model and an optimization target of the gear machining process, which can obtain an excellent solution to the scheduling problem of the gear machining process in a short time, thereby ensuring that the gears can have a high pass rate when they leave the factory, and at the same time make the gear machining The expression of the process is more clear and accurate.

Description

An Optimal Scheduling Method for Gear Machining Process

technical field

The invention relates to an optimal scheduling method of a gear machining process, which belongs to the field of intelligent optimal scheduling of production workshops.

Background technique

A gear is a mechanical element with gears on the rim that continuously mesh to transmit motion and power. The application of gears in transmission has appeared very early. At the end of the nineteenth century, the principle of the generative gear cutting method and the special machine tools and tools for gear cutting using this principle appeared one after another. Gears are widely used in the machinery industry, especially in the fields of automobiles and heavy machinery, where continuous meshing of gears can transmit motion and power. As an important part of the mechanical basic industry, the gear industry will have very broad prospects both in terms of scale and processing technology. In view of the limited production capacity of enterprise equipment and other resources, reasonable scheduling can have a great impact on equipment utilization, delivery time, inventory, etc.

The general gear processing process has the following steps: blank manufacturing, gear blank heat treatment, gear blank processing, tooth surface processing, gear tooth heat treatment, tooth surface finishing and gear tooth finishing. Different processing operations need to be completed on different machines. During the entire gear machining process, the gears to be processed need to be operated on different machines in turn to complete the gear forming. Specifically, to process and produce n gears, the gear blank needs to pass through different m machines in the same order to complete the gear processing. Therefore, the characteristic of the gear processing process is that each gear blank is processed according to the machine sequence M1, M ₂ ,..., M _m in each processing process, and the processing sequence of each gear blank on each machine is the same, The academic community defines this type of pipeline as Permutation Flow-shop (PFS), and it has also been proven that the PFS scheduling problem with more than two machines is an NP-hard problem, that is, its exact solution cannot be obtained in polynomial time. Obviously, for the pipeline scheduling problem of the researched gear processing process, the processing machines are obviously larger than two, which also belongs to the category of NP-hard problems. Reasonable scheduling of this problem can significantly improve the production efficiency of the gear production process.

From the description of the above gear processing process, it can be seen that the pipeline scheduling problem of the gear processing process is NP-hard. The traditional mathematical programming method can only solve small-scale problems, and the heuristic constructive method has poor optimization quality. Therefore, the present invention starts from From the perspective of intelligent algorithm, an optimal scheduling method based on Hybrid Discrete Harmony Search Algorithm (HDHSA) is designed, which can obtain an excellent solution to the scheduling problem of gear machining process in a short time.

Contents of the invention

The invention provides an optimal scheduling method of the gear machining process, which is used to obtain an excellent solution to the optimal scheduling problem of the gear machining and manufacturing process in a relatively short period of time.

The technical solution of the present invention is: an optimal scheduling method of the gear machining process, by determining the scheduling model and optimization target of a batch of gear blanks to be processed and formed in the machining process, and using the optimization method based on the hybrid discrete harmonic search algorithm The scheduling method optimizes the objective; the scheduling model is established according to the processing time of each gear on each processing machine during the machining process of the gear, and the optimization objective is to minimize the maximum completion time C _max (π):

C _max (π)＝C(π _n ,m)

In the formula, n × m represents the scale of the problem, n represents the total number of gears to be processed, m represents the number of machines used in the gear processing process, Indicates a set of positive integers; π=[π ₁ ,π ₂ ,…,π _i ] indicates the process of the gear to be processed, π _k indicates the gear at the kth position in π, Indicates the processing time of the π _i -th gear on the j machine, C(π _i ,j) is the completion time of the π _i -th gear on the j machine; the optimization objective of the model is Find an optimal sorting π ^* in the sorting set Π of gears, so that the maximum completion time C _max (π) is the smallest.

The optimal scheduling method based on the hybrid discrete harmony search algorithm is specifically:

Step1. The design of the encoding method: the encoding is carried out in the gear machining sequence in the gear machining process, and the order is π=[π ₁ ,π ₂ ,…,π _i ], i=1,2,…,n, where i is Number of gears to be processed;

Step2. Parameter initialization: the size of the harmony memory HMS is the population size NP, the value probability HMCR of the harmony memory, the pitch fine-tuning probability PAR, and set the algorithm start time;

Step3. Population initialization: use the NEH method to generate an initial population individual, and use the random method to generate the remaining NP-1 individuals, and record the objective function value f of each individual until the number of initial solutions reaches the population size requirements; harmony memory The specific form is as follows:

Among them, X ¹ , X ² ,...,X ^HMS are the generated HMS harmony, f(X ¹ ), f(X ² ),...,f(X ^HMS ) are their corresponding objective function values;

Step4. Generate new harmony: New harmony is mainly generated through the following three mechanisms: learning harmony memory, fine-tuning tone and random selection of tone. The specific description is as follows:

①. Randomly generate a random number rand from 0 to 1. If rand<HMCR, then apply the learning harmony memory mechanism and randomly select a harmony variable from the existing harmony memory HM as the new harmony X ^new ; Otherwise, a new harmony variable is randomly generated from the solution space as a new harmony X ^new by applying the mechanism of randomly selecting the tone;

②. A harmony variable X ^new can be obtained from ①. If this harmony variable is generated by learning the harmony memory, it is necessary to fine-tune this harmony variable: If a random number rand1 between 0 and 1 is randomly generated <PAR, then it is necessary to perform pitch fine-tuning operations based on the forward_insert neighborhood for the new harmony X ^new to generate new individuals; if rand1≥PAR, it is necessary to perform a pitch fine-tuning operation based on the swap neighborhood for the new harmony X ^new , Generate a new individual, the specific formula is as follows:

Step5. Update the harmony memory: According to Step4, a new harmony memory HM ^new composed of new harmony can be obtained, and each individual in the new harmony memory can be evaluated to obtain its corresponding objective function value f , compare the individuals in the new harmony memory bank with the individuals in the initial harmony memory bank HM generated in Step3, if the individual X ^new in HM ^new is better than the individual X ^old in HM, that is, f( X ^new )<f(X ^old ), then replace individual X ^new in HM ^new with individual Xo ^ld in HM; otherwise, do not modify;

Step6. Problem-based local search: regard one-fifth of the individuals in the new population as "selected individuals", and carry out the exploration stage and the disturbance stage for each "selected individual" in turn. If the individual obtained by the local search is better than the "selected individual", individual", replace it and use the current population as the new generation population;

Step7. Termination condition: set the termination condition to be the running time of the algorithm T=100×n, if it is satisfied, then output the "optimal individual"; otherwise, go to step Step4 and iterate repeatedly until the termination condition is satisfied.

The exploration stage uses the "backward_insert" neighborhood operation, and the number of explorations is set to the total number of gears to be processed n; the neighborhood operation based on "interchange" is used to realize the disturbance stage, and the number of disturbances is 3 times. Detailed exploration.

The beneficial effect of the present invention is that: the present invention proposes a scheduling model and an optimization target of the gear machining process, and can obtain an excellent solution to the scheduling problem of the gear machining process in a short time, thereby ensuring that the gear can have a higher efficiency when it leaves the factory. At the same time, the expression of the gear processing process is clearer and more accurate; the "high-quality individuals" of the current generation population obtained according to the steps of the discrete harmony search algorithm are used to update the next generation of individuals, which can better guide the algorithm to perform a global search; In the process of updating the population, by repeatedly adjusting the tone (adaptation value) of each harmony (individual) in the band (population), a wonderful harmony state is finally achieved, which not only makes full use of the historical information of the dominant individual, but also It can ensure that the global search of the algorithm has a certain width; using the "interchange" operation to perturb in the local search is conducive to the algorithm jumping out of the local optimum, thereby making the search field of the algorithm wider, combined with the "backward_insert" neighborhood search mechanism. The local development ability of the algorithm is significantly improved, and the quality of the solution is significantly improved.

Description of drawings

Fig. 1 is the technological process schematic diagram of gear machining process among the present invention;

Fig. 2 is the overall algorithm flowchart of the present invention;

Fig. 3 is the representation schematic diagram of problem solution among the present invention;

Fig. 4 is the schematic diagram of the pitch fine-tuning operation change based on "forward insertion" (forward_insert) neighborhood of the present invention;

Fig. 5 is a schematic diagram of the change of pitch fine-tuning operation based on "exchange" (swap) neighborhood of the present invention;

Fig. 6 is a schematic diagram of the change of the collar operation based on "interchange" in the present invention;

Fig. 7 is a schematic diagram of the variation of the neighborhood operation based on "backward_insert" in the present invention.

Detailed ways

Example 1: As shown in Figures 1-7, an optimal scheduling method for a gear machining process, by determining the scheduling model and optimization objectives of a batch of gear blanks to be processed and formed in the machining process, and using a method based on hybrid discrete and The optimal scheduling method of the acoustic search algorithm optimizes the target; among them, the scheduling model is established according to the processing time of each gear on each processing machine during the machining process of the gear, and the optimization objective is to minimize the maximum completion time C _max ( π):

C _max (π)＝C(π _n ,m)

In the formula, n × m represents the scale of the problem, n represents the total number of gears to be processed, m represents the number of machines used in the gear processing process, Indicates a set of positive integers; π=[π ₁ ,π ₂ ,…,π _i ] indicates the process of the gear to be processed, π _k indicates the gear at the kth position in π, Indicates the processing time of the π _i -th gear on the j machine, C(π _i ,j) is the completion time of the π _i -th gear on the j machine; the optimization objective of the model is Find an optimal sorting π ^* in the sorting set Π of gears, so that the maximum completion time C _max (π) is the smallest.

Further, the optimal scheduling method based on the hybrid discrete harmony search algorithm can be set as:

Step1. The design of the encoding method: the encoding is carried out in the gear machining sequence in the gear machining process, and the order is π=[π ₁ ,π ₂ ,…,π _i ], i=1,2,…,n, where i is Number of gears to be processed;

For example: sort and code the gear blanks to be processed. For example, there are 5 processing gears and 3 processing machines. After random coding, a gear processing sequence is [5, 3, 1, 2, 4], and each machine The processing sequence is the sequence. In the sequence [5,3,1,2,4], the 5 in the first position means that the first gear to be processed is gear No. 5, the 3 in the second position means that the second gear to be processed is gear No. 3, and the number three The position of 1 means that the third gear to be processed is the No. 1 gear, and so on.

Step2. Parameter initialization: the size of the harmony memory HMS is the population size NP (the population size is NP, that is, the number of initial solutions NP), the value probability HMCR of the harmony memory, the pitch fine-tuning probability PAR, and set the algorithm to start time;

Step3. Population initialization: use the NEH method to generate an initial population individual, and use the random method to generate the remaining NP-1 individuals, and record the objective function value f of each individual until the number of initial solutions reaches the population size requirements; harmony memory The specific form is as follows:

Among them, X ¹ , X ² ,...,X ^HMS are the generated HMS harmony, f(X ¹ ), f(X ² ),...,f(X ^HMS ) are their corresponding objective function values; Indicates the 1st, 2nd,...,n gears to be processed in the HMS population;

Step4. Generate new harmony (individual): New harmony is mainly generated through the following three mechanisms: learning harmony memory, fine-tuning the tone and randomly selecting the tone. The specific description is as follows:

①. Randomly generate a random number rand from 0 to 1. If rand<HMCR, apply the learning harmony memory mechanism and randomly select a harmony variable from the existing harmony memory HM as a new harmony (individual) X ^new ; otherwise, apply the mechanism of randomly selecting the tone, and randomly generate a new harmony variable from the solution space as the new harmony (individual) X ^new ;

②. From ①, a harmony variable X ^new can be obtained. If this harmony variable is generated by learning the harmony memory (that is, randomly selected from the harmony library HM), it is necessary to fine-tune the harmony variable. The present invention designs two pitch fine-tuning operations, that is, the pitch fine-tuning operation based on the "forward_insert" neighborhood and the pitch fine-tuning operation based on the "swap" neighborhood. The selection of the two fine-tuning operations is determined by the pitch fine-tuning frequency PAR. The specific method is:

It can be seen from the above formula that firstly, a random number rand1 between 0 and 1 is randomly generated, and if rand1<PAR, the neighborhood operation based on the "forward_insert" (forward_insert) neighborhood needs to be performed on the new harmony X ^new to realize pitch fine-tuning Generate a new individual, and its specific implementation is shown in Figure 4; if rand1≥PAR, then it is necessary to perform a tone fine-tuning operation based on the "swap" (swap) neighborhood of the new harmony X ^new to generate a new individual, and its specific implementation is shown in Figure 4 5.

Step5. Update the harmony memory. According to Step4, we can obtain a new harmony memory (new population) HM ^new composed of new harmony (new individuals), and evaluate each individual in the new harmony memory to obtain its corresponding objective function value f. Compare the individuals in the new harmony memory with the individuals in the initial harmony memory HM generated in Step3, if the individual X ^new in HM ^new is better than the individual X ^old in HM, that is, f(X ^new )<f(X ^old ), then replace individual X ^new in HM ^new with individual X ^old in HM; otherwise, do not modify.

Step6. Problem-based local search. In order to balance the global search and local search of the algorithm, improve the exploration efficiency of the algorithm for high-quality areas. The present invention designs a local search based on two kinds of neighborhood operations "interchange" and "backward_insert" for one-fifth of individuals in the updated new population. The local search is divided into a disturbance stage and an exploration stage. The “interchange”-based neighborhood operation is used to realize the disturbance stage. The number of disturbances is 3 times, and the individual after the disturbance is explored in more detail. In the exploration stage, the “backward_insert” neighborhood is used. Operation, the number of explorations is set to the total number n of gears to be processed. One-fifth of the individuals in the new population are regarded as "selected individuals", and each "selected individual" is explored and disturbed in turn. If the individual obtained by local search is better than the "selected individual", it will be replaced, and Treat the current population as a new generation population;

Step7. Termination condition: set the termination condition to be the running time of the algorithm T=100×n, if it is satisfied, then output the "optimal individual"; otherwise, go to step Step4 and iterate repeatedly until the termination condition is satisfied.

In order to verify the validity and robustness of the Hybrid Discrete Harmony Search Algorithm (HDHSA) proposed by the present invention, the HDHSA is compared with the standard Harmony Search Algorithm (HSA). The specific comparison test is as follows:

In the present invention, the Rec class problem in the commonly used Flow shop test problem set is selected as the test problem, and under the same conditions, the standard harmony search algorithm (HSA) and the discrete harmony search algorithm (HDHSA) proposed by the present invention are compared. Comparison of objective function value results. The running time of the algorithm for problems of different scales is T=100×n (unit: ms). Each algorithm and its test program are programmed by Delphi 2010, the operating system is Win10, the main frequency of the CPU is 2.2GHz, and the memory is 4GB. The parameters of the proposed Hybrid Discrete Harmony Search Algorithm (HDHSA) are set as follows: population size popsize=2×n, value probability of harmony memory bank HMCR=0.9, pitch fine-tuning probability PAR=0.3. Each algorithm was repeated 20 times independently, where AVG represents the mean of the optimal value and SD represents the standard deviation. Table 1 shows the comparison of the objective function value results between the standard harmony search algorithm (HSA) and the discrete harmony search algorithm (HDHSA) proposed by the present invention under the same test environment. As can be seen from Table 1, the AVG and SD obtained by the proposed algorithm of the present invention are better than the standard harmony search algorithm on most of the test problems, which shows the effectiveness of the proposed algorithm of the present invention, and also proves that the discrete and Acoustic search algorithm is an effective algorithm for solving the optimal scheduling problem of gear machining process.

Table 1 Obtained objective function values under different problem scales

The specific implementation of the present invention has been described in detail above in conjunction with the accompanying drawings, but the present invention is not limited to the above-mentioned implementation, within the knowledge of those of ordinary skill in the art, it can also be made without departing from the gist of the present invention. Variations.

Claims (3)

1. An optimal scheduling method of a gear machining process, characterized in that: by determining a scheduling model and an optimization target of a batch of gear blanks to be processed and formed in the machining process, and using an optimal scheduling method based on a hybrid discrete harmonic search algorithm The method optimizes the objective; among them, the scheduling model is established according to the processing time of each gear on each processing machine during the machining process of the gear, and the optimization objective is to minimize the maximum completion time C _max (π): C _max (π)＝C(π _n ,m) In the formula, n × m represents the scale of the problem, n represents the total number of gears to be processed, m represents the number of machines used in the gear processing process, Indicates a set of positive integers; π=[π ₁ ,π ₂ ,…,π _i ] indicates the process of the gear to be processed, π _k indicates the gear at the kth position in π, Indicates the processing time of the π _i -th gear on the j machine, C(π _i ,j) is the completion time of the π _i -th gear on the j machine; the optimization objective of the model is Find an optimal sorting π ^* in the sorting set Π of gears, so that the maximum completion time C _max (π) is the smallest. 2. The optimal scheduling method of the gear machining process according to claim 1, characterized in that: the optimal scheduling method based on the hybrid discrete harmony search algorithm is specifically: Step1. The design of the encoding method: the encoding is carried out in the gear machining sequence in the gear machining process, and the order is π=[π ₁ ,π ₂ ,…,π _i ], i=1,2,…,n, where i is Number of gears to be processed; Step2. Parameter initialization: the size of the harmony memory HMS is the population size NP, the value probability HMCR of the harmony memory, the pitch fine-tuning probability PAR, and set the algorithm start time; Step3. Population initialization: use the NEH method to generate an initial population individual, and use the random method to generate the remaining NP-1 individuals, and record the objective function value f of each individual until the number of initial solutions reaches the population size requirements; harmony memory The specific form is as follows: Among them, X ¹ , X ² ,...,X ^HMS are the generated HMS harmony, f(X ¹ ), f(X ² ),...,f(X ^HMS ) are their corresponding objective function values; Step4. Generate new harmony: New harmony is mainly generated through the following three mechanisms: learning harmony memory, fine-tuning tone and random selection of tone. The specific description is as follows: ①. Randomly generate a random number rand from 0 to 1. If rand<HMCR, then apply the learning harmony memory mechanism and randomly select a harmony variable from the existing harmony memory HM as the new harmony X ^new ; Otherwise, a new harmony variable is randomly generated from the solution space as a new harmony X ^new by applying the mechanism of randomly selecting the tone; ②. A harmony variable X ^new can be obtained from ①. If this harmony variable is generated by learning the harmony memory, it is necessary to fine-tune this harmony variable: If a random number rand1 between 0 and 1 is randomly generated <PAR, then it is necessary to perform pitch fine-tuning operations based on the forward_insert neighborhood for the new harmony X ^new to generate new individuals; if rand1≥PAR, it is necessary to perform a pitch fine-tuning operation based on the swap neighborhood for the new harmony X ^new , Generate a new individual, the specific formula is as follows: Step5. Update the harmony memory: According to Step4, a new harmony memory HM ^new composed of new harmony can be obtained, and each individual in the new harmony memory can be evaluated to obtain its corresponding objective function value f , compare the individuals in the new harmony memory bank with the individuals in the initial harmony memory bank HM generated in Step3, if the individual X ^new in HM ^new is better than the individual X ^old in HM, that is, f( X ^new )<f(X ^old ), then replace individual X ^new in HM ^new with individual X ^old in HM; otherwise, do not modify; Step6. Problem-based local search: regard one-fifth of the individuals in the new population as "selected individuals", and carry out the exploration stage and the disturbance stage for each "selected individual" in turn. If the individual obtained by the local search is better than the "selected individual", individual", replace it and use the current population as the new generation population; Step7. Termination condition: set the termination condition to be the running time of the algorithm T=100×n, if it is satisfied, then output the "optimal individual"; otherwise, go to step Step4 and iterate repeatedly until the termination condition is met. 3. The optimal scheduling method of the gear machining process according to claim 2, characterized in that: the exploration stage utilizes the "backward_insert" neighborhood operation, and the number of explorations is set to the total number n of gears to be processed; The neighborhood operation realizes the disturbance stage, and the number of disturbances is 3 times, and a more detailed exploration is carried out on the disturbed individuals.