Background
In the distributed manufacturing mode, the efficient scheduling optimization scheme not only can effectively improve comprehensive production benefits of enterprises, but also can integrate distributed production resources, so that production cost is reduced. The distributed workshop scheduling problem is to study the distribution scheme of workpieces among factories by taking cooperative production among different enterprises as a background, and ensure the optimization of the processing sequence of the workpieces in each factory to a certain index. The solution of the distributed shop scheduling problem is more complex than the single shop scheduling problem, and the problems of interrelationships among factories, processing sequences of workpieces distributed to the interior of the workshops, how machines are distributed and the like need to be considered. Distributed flow shop scheduling is one of the important problems of distributed shop scheduling, and plays an important role in a plurality of industries such as steel, food processing, chemical engineering, operation and research. The problem is characterized in that the solving difficulty is increased geometrically along with the increase of the problem scale. When this type of problem is solved using conventional methods, it is often intolerable in terms of complexity and space for medium and large scale problems. Therefore, the adoption of a novel intelligent optimization algorithm to solve the problems has important practical significance. In addition, a collaborative group intelligent optimization algorithm based on knowledge driving is a key for solving the distributed scheduling problem. Refining a knowledge type search strategy through deep understanding and analysis of the problems; through the elicitation of the calculation intelligent mechanism, the intelligent searching operation of the diversified groups is designed; furthermore, the satisfactory optimization performance is expected to be further obtained through group cooperation, operation cooperation, parameter cooperation, strategy cooperation, target cooperation and algorithm cooperation.
The differential evolution algorithm is a population-based meta-heuristic that exhibits excellent performance in solving a number of field and many practical application problems. However, since different problems all have unique characteristics, if it is desired to show better optimal solving performance on a certain problem, a corresponding algorithm needs to be built for a model of a specific problem. Therefore, the invention constructs a reasonable optimization method aiming at the distributed replacement flow shop scheduling common in the manufacturing distributed production scheduling field. The algorithm has remarkable effect in solving a series of optimization problems through an inherent unique search mechanism.
Disclosure of Invention
The invention provides a knowledge-driven discrete differential evolution algorithm (KDDE) which is applied to the scheduling problem of a distributed replacement flow shop, and can optimize the operation efficiency and performance of the scheduling system of the distributed replacement flow shop. The technical scheme adopted is as follows:
the invention relates to a knowledge-driven discrete differential evolution algorithm distributed scheduling optimization solving method, which comprises the following steps:
Step 1: initializing a population using DNEH method;
Step 2: using a variation and crossover operator based on the workpiece sequence;
Step 3: a neighborhood structure based switching mechanism and a local search strategy are used, together with knowledge driven collaboration mechanisms.
Preferably, in step 1, a good initialization population is obtained using the new initialization method, so that KDDE can search in a better area early in the evolution process, providing potential candidate solutions.
Preferably, in step2, a new discrete mutation operator is used, so that the new discrete mutation operator can adapt to the characteristic of the scheduling problem, and the searching efficiency of the algorithm is improved.
Preferably, in step 3, four neighborhood search mechanisms are adaptively selected by using a knowledge-driven optimization strategy, so as to ensure that the candidate solution escapes from the local optimum in the search process, and the convergence accuracy of KDDE is improved.
The invention has the following beneficial effects:
(1) A high quality initialization population sequence is constructed using the new heuristic method, enabling the algorithm to quickly search for better regions.
(2) The invention uses a collaborative search mechanism based on knowledge driving, so that the optimizer adapts to the problem characteristics, and the exploration and development capabilities of the optimizer are balanced.
(3) The invention has simple logic, easy realization and easy expansion, and can expand the optimization method to meet the solving requirement of most scheduling problems in the current intelligent manufacturing production field.
Detailed Description
The present invention will be described in further detail with reference to the accompanying drawings and examples. It should be understood that the specific examples described herein are for purposes of illustration only and are not intended to limit the scope of the invention.
As shown in FIG. 1, FIG. 1 is a flow chart of a distributed replacement flow shop scheduling optimization solution method based on a knowledge-driven discrete differential evolution algorithm of the present invention.
The application of KDDE algorithm to distributed replacement flow shop scheduling problems will be further described below with reference to the accompanying drawings:
A distributed replacement flow shop scheduling method based on a knowledge-driven discrete differential evolution algorithm specifically comprises the following steps:
step 1: initializing parameters, setting the population number num, and ending the algorithm.
Step 2: the population is initialized, and call NEH generates ps (population size) candidate solutions to form a population N. Assuming that after inserting one workpiece, the current factory already contains k workpieces, each workpiece of the factory is taken out, inserted into the other k-1 positions, and the best sequence is selected as the current sequence. An example of a specific application rule for NEH is shown in fig. 2. In fig. 2, the detailed process of workpiece insertion is shown in a dashed box. NEH is shown in algorithm 5.1.
Step 3: mutation operators and crossover operators, a mutation strategy is one of the important operators in DE, which helps to avoid the algorithm from falling into local optimization. The mutation strategy formula is as follows:
Where x pb, G is the optimal vector for the current G generation. r1 and r2 are two random integers in the range of [1, N ]. The "-" and three operators in the formula are defined as follows:
wherein Δ1 and Δ2 are temporary vectors; "Mod" represents the mathematical operation of Mod; pseudo code for the mutation operator is given in algorithm 2.
The mutated sequence may be illegal because a single workpiece may be repeated or deleted. Thus, the legitimate target individual is obtained by the following crossover operator. Variant individual v i, g and target individual x i, g-1 are combined by crossover operators to generate test individual u i, g. From j e [1: n ] starting, if rand (). Gtoreq.CR or the workpiece is already in v i, g, then delete the workpiece v i, j, where v i, j ε v i, g. Let u i, g= x i, g-1, and delete the work pieces contained in V i from u i, g. All positions of u i, g were evaluated and V i was inserted into the best position of u i, g. This step is repeated until V i is empty. A detailed example of the crossover operator is shown in fig. 4, assuming V i = (5,0,2,3,5,4) is a variant sequence.
Step 4: variable neighborhood searching and local searching; the main ideas of neighborhood search are divided into the following aspects: first, the local optimum of one neighborhood structure is not necessarily the optimum of another neighborhood. Second, the globally optimal solution contains locally optimal solutions for all possible neighborhood structures. Finally, for different problems, the local optima of multiple or one neighborhood are relatively close to each other. The design of the neighborhood allows for solving the finishing time of other plants without reducing the total finishing time if the plant (denoted as critical plant f c) that is the maximum finishing time is not changed. A detailed neighborhood example is given in fig. 5. In each iteration, a current neighborhood solution is generated by using the neighborhood structure, and local search is performed according to the neighborhood solution. As shown in fig. 6, four local search methods are used to search for candidate solutions. In addition, the selection of the neighborhood is also one of the important factors that improves the search capability of the algorithm. In KDDE, a knowledge-based optimization strategy is proposed to adaptively select the currently most appropriate neighborhood search mechanism. The algorithm firstly enters one of the neighborhoods, and local search small-range disturbance is carried out according to the current neighborhood solution. Based on the fed-back information, when there are still potential candidate solutions in the neighborhood, then a local search is continued in the neighborhood. If there are no potential candidate solutions in the neighborhood, the algorithm switches to the next neighborhood to continue searching. That is, instead of blindly altering the neighborhood search mechanism, the algorithm determines whether to switch to the next neighborhood based on the feedback results of the local search. This closed loop control system with feedback information allows the algorithm to find more potential candidate solutions. Historical information in the algorithm evolution process is extracted to be used as guiding knowledge for switching neighborhood search, and the exploration and development capability of the algorithm are balanced.
Step 5: if the running time does not reach the set termination condition, returning to the step3, otherwise outputting the optimal individuals in the current population and the corresponding makespan.
To test KDDE for performance, four advanced algorithms were chosen for comparison, HDDE(WANG L,PAN Q-K,SUGANTHAN P N,et al.A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems[J].Computers and Operations Research,2010,37(3):509-20)、DDE(ZHANG G,XING K,CAO F.Discrete differential evolution algorithm for distributed blocking flowshop scheduling with makespan criterion[J].Engineering Applications of Artificial Intelligence,2018,76,96-107)、CDE(ZHANG G,XING K.Differential evolution metaheuristics for distributed limited-buffer flowshop scheduling with makespan criterion[J].Computers&Operations Research,2019,108,33-43)、 two-stage IG algorithm (RUIZ R,PAN Q-K,NADERI B.Iterated Greedy methods for the distributed permutation flowshop scheduling problem[J].Omega,2019,83,213-222)., which were each tested in simulation on a standard test set, and ARPD (AVERAGE RELATIVE PERCENTAGE device) was used to characterize the performance of the algorithm. The smaller ARPD, the better the algorithm performance. Table 1 gives the Wilcoxon rank sum test results for five algorithms on a standard test set (Ta problem). The Wilcoxon signed rank test is a test method for data pairwise comparison. As shown in table 1, R+ represents the functional rank sum of the first algorithm over the second algorithm in the row, and R- represents the functional rank sum of the second algorithm over the first algorithm. "Yes" means that at the significance level α, the results of the pairwise comparisons differ significantly. The results show that for the DPFSP problem with α=0.05, α=0.01, KDDE is significantly better than the other four comparisons.
Table 1KDDE et al Wilcoxon rank sum test results of algorithm
The foregoing has shown and described the basic principles and main features of the present invention and the advantages of the present invention. It will be understood by those skilled in the art that the present invention is not limited to the embodiments described above, and that the above embodiments and descriptions are merely illustrative of the principles of the present invention, and various changes and modifications may be made without departing from the spirit and scope of the invention, which is defined in the appended claims. The scope of the invention is defined by the appended claims and equivalents thereof.