CN110909787A

CN110909787A - Method and system for multi-objective batch scheduling optimization based on clustering evolutionary algorithm

Info

Publication number: CN110909787A
Application number: CN201911133581.5A
Authority: CN
Inventors: 贾兆红; 钱思源; 唐俊
Original assignee: Anhui University
Current assignee: Anhui University
Priority date: 2019-11-18
Filing date: 2019-11-18
Publication date: 2020-03-24
Anticipated expiration: 2039-11-18
Also published as: CN110909787B

Abstract

本发明提供了基于聚类的进化算法进行多目标批调度优化的方法，S1：初始化种群规模N、最大迭代次数MaxIteration和重组配对概率S，以及种群P、帕累托解集A，迭代次数t＝1；S2：利用解码规则和局部优化计算种群目标值；S3：对目标值进行聚类；S4：基于聚类结果对种群P执行交叉变异生成子代种群Q，计算子代种群Q的目标值；S5：更新集合A，执行选择操作更新种群P，基于更新后的种群P更新重组配对概率S；S6：如果t＜MaxIteration，t＝t+1，跳转至S2，否则输出集合A。本发明还提供了用于多目标批调度的系统，本发明提供的基于聚类的进化算法进行多目标批调度优化的方法和系统的优点在于：为生产过程中的批调度问题提供了可靠的解决方案。The present invention provides a method for multi-objective batch scheduling optimization based on a clustering evolutionary algorithm, S1: initialized population size N, maximum iteration times MaxIteration and recombination pairing probability S, population P, Pareto solution set A, iteration times t =1; S2: Calculate the population target value using decoding rules and local optimization; S3: Cluster the target value; S4: Perform cross-mutation on the population P based on the clustering results to generate the offspring population Q, and calculate the target of the offspring population Q value; S5: Update the set A, perform the selection operation to update the population P, and update the recombination pairing probability S based on the updated population P; S6: If t<MaxIteration, t=t+1, jump to S2, otherwise output the set A. The present invention also provides a system for multi-objective batch scheduling. The advantages of the method and system for multi-objective batch scheduling optimization provided by the clustering-based evolutionary algorithm are: it provides a reliable solution for batch scheduling problems in the production process. solution.

Description

Method and system for multi-objective batch scheduling optimization based on clustering evolutionary algorithm

Technical Field

The invention relates to the technical field of batch scheduling optimization, in particular to a method and a system for multi-objective batch scheduling optimization based on a clustering evolutionary algorithm.

Background

Scheduling plays an important role in actual production manufacturing, and all that involves the allocation of resources is not separated from scheduling because reasonable scheduling can meet our demand targets. At present, the method has practical scheduling application in the aspects of steel production, integrated production, cloud computing, medical industry, textile industry and the like. One type of scheduling problem, referred to as the batch processor scheduling problem, was originally derived from the last production run of semiconductor chips, and is different from the classical scheduling problem, in which a plurality of workpieces can be processed simultaneously on one machine, and the workpieces are also subject to batch decision, and the processing sequence of the batches is sometimes studied. The existing batch scheduling problem is basically a combined optimization problem difficult to perform NP (network processor), a meta-heuristic algorithm is usually adopted to solve the problem, and the solving method is closely related to the specific problem.

With the proposal of the concept of "green manufacturing", environmental protection and energy consumption become two issues that must be considered in the manufacturing process, and the batch scheduling problem is closely related to the actual manufacturing process, so that in the research process of the batch scheduling problem, besides the traditional target value research, the energy consumption naturally becomes a new research target value and becomes a hot content of research. For manufacturing enterprises, the reduction of energy consumption not only protects the environment, but also reduces the manufacturing cost of the enterprises to a certain extent, so that the win-win situation is realized. It is then of great practical significance to study the conventional standards and to consider the reduction in energy consumption. At present, the most direct energy consumption is the power consumption of the machine, and as the unit electricity prices are changed in different time periods and the processing and idle power of the machine are different, the energy consumption can be reduced by reasonably arranging the processing sequence of the batch on the machine.

At present, the batch scheduling research considering the electricity price cost is less than the research of the traditional target value, and under the batch scheduling problems that the machine speed is different and the workpiece has the size attribute, the work for researching the reduction of the electricity price cost is less, and the situation is definitely existed in the actual production process, so that the batch scheduling research is worth further research.

Disclosure of Invention

The technical problem to be solved by the invention is to provide a batch scheduling optimization method comprising a self-adaptive clustering and evolutionary algorithm, so that the working time and the electricity price cost of a batch scheduling scheme are considered; and realizing multi-objective optimization.

The invention solves the technical problems through the following technical scheme:

a method for carrying out multi-objective batch scheduling optimization based on a clustering evolutionary algorithm,

s1: initializing a population size N, a maximum iteration number MaxIteraction and a recombination pairing probability S; initializing a population P and a pareto solution set A based on a machined workpiece, wherein individuals of the population P and the set A represent workpiece sequences, and the initialization iteration number t is 1;

s2: executing a decoding rule on the population P to obtain scheduling schemes of all individuals, adjusting each scheduling scheme through local optimization and calculating a target value of each scheduling scheme;

s3: clustering the target value of the population P by using self-adaptive clustering;

s4: selecting a cross-variant object for individuals in the population P based on the clustering result to generate a child population Q, and calculating a target value of the child population Q by using a decoding rule and local optimization;

s5: utilizing pareto individual updating sets A of the parent population P and the child population Q, performing selection operation on the parent population P and the child population Q to update the population P, and updating the recombination pairing probability S based on the updated population P;

s6: if t < maxitration, t ═ t +1, jump to S2, otherwise output set a.

Preferably, the method for initializing the population P in S1 is: and respectively arranging according to the ascending sequence, the descending sequence and the ascending sequence of the arrival time of the processing time to obtain three individual workpiece sequences, and randomly generating the remaining individual workpiece sequences.

Preferably, the decoding rules described in S2 and S4 are used to set any group X ═ X_n|n∈[1,N]Of individuals X_nConversion of corresponding work sequence to Dispatch plan X'_nThe specific method comprises the following steps:

step i: first stageWith 1 as the initialization n, the set of scheduling schemes

Step ii: sequentially reacting X_nPutting the workpieces in the lot into a lot which can contain the workpieces and has the minimum residual capacity, and if no lot meeting the conditions exists, creating a new lot to put the current workpieces until all the workpieces are completely distributed;

step iii: arranging all batches in ascending order according to the arrival time of the batches;

step iv: distributing the current batch to a machine with the earliest completion time, and if a plurality of machines meet the conditions, selecting the machine with the highest processing speed;

step v: returning to step iv until all batches have been allocated to the machine, the current individual X is assigned_nCorresponding scheduling scheme X'_nAdding a set X';

step vi: if N is less than N, making N equal to N +1, returning to the step ii, otherwise, outputting a set X';

where the capacity of the new lot is equal to the machine capacity MC.

Preferably, the method for adjusting the scheduling scheme and calculating the target value by local optimization described in S2 and S4 is:

step I: inputting a scheduling scheme set X', obtaining a total number m of machines and an electricity price EP (t) in a time period t, and initializing n to 1 and i to 1;

step II: obtaining current scheduling scheme X'_nUpper machine M_iNumber of batches | M_iInitialization of k ═ M_i|；

Step III: when k is equal to | M_iAnd satisfy

PW_i×EP(CT_ki+1)+SW_i×EP(ST_ki+1)-PW_i×EP(ST_ki+1) less than or equal to 0 or CT_ki＜ST_(k+1)iWhen, make ST_ki＝ST_ki+1，CT_ki＝CT_ki+1；

When k ≠ M_iAnd satisfy

PW_i×EP(CT_ki+1)+SW_i×EP(ST_ki+1)-PW_i×EP(ST_ki+1)-SW_ki×EP(CT_ki+1) less than or equal to 0 or CT_ki＜ST_(k+1)iWhen, make ST_ki＝ST_ki+1，CT_ki＝CT_ki+1；

Wherein, PW_iFor the working power of machine i, SW_iFor idle power of machine i, CT_kiFor the completion time of the k-th lot on machine i, ST_kiThe starting processing time of the kth batch on the machine i;

CT_ki＝ST_ki+PT_ki

ST_ki＝max{RT_ki,CT_(k-1)i}

wherein PT_kiThe processing time of the k-th batch on the machine i is equal to the ratio of the maximum processing time of all the workpieces in the batch to the processing speed of the machine, i.e. the processing time of the k-th batch on the machine i is equal to the processing speed of the machine

r_jAs the machining time of the workpiece j, B_kiFor the k-th batch on machine i, v_iIs the processing speed of machine i;

RT_kiis the arrival time of the k-th batch on machine i, which is equal to the maximum arrival time of all workpieces in the batch, i.e.

RT_ki＝max{p_j|j∈B_ki}

p_jIs the arrival time of workpiece j;

step IV: when k is more than 1, making k equal to k-1, and returning to the step III;

step V: if i is less than m, making i equal to i +1, returning to the step II, otherwise calculating the current scheduling scheme X'_nTarget value of (C), i.e. maximum completion time C_maxAnd total electricity price cost TEC;

C_max＝max{CT_ki|i∈[1,m]}

will current scheduling scheme X'_nCorresponding target value x_nAdding the target value set x;

step VI: and if N is less than N, making N equal to N +1, returning to the step II, otherwise, outputting the target value set x.

Preferably, the method for adaptively clustering the target values in S3 is as follows:

step A: acquiring a current iteration time t and a target value set x;

and B: if T is 1ormod (T, T) is 0, jumping to the step C for coarse clustering, otherwise jumping to the step D for updating the clustering result;

and C: inputting the target value set into a canty algorithm to obtain the cluster number K and each class C_k,k∈[1,K]Centroid point m_k；

Step D: performing single clustering by using K-means algorithm based on current centroid point, and updating class C_kCentroid point m_k；

Where mod (T, T) represents the remainder of T/T, and the coarse clustering period T is the global variable set in S1.

Preferably, the method for identifying subjects for cross-variant individuals described in S4 is:

step a: acquiring a set P ═ { P) of a population P_n|n∈[1,N]And a clustering result C ═ C of a target value set P of the population P_k|k∈[1,K]}; applying a clustering result C of the target value set P to the population P, and enabling n to be 1;

step b: if rand () ≦ S, go to step c, otherwise jump to step d, where rand () represents a random number;

step c: from the current individual P_nClass C of which_kIn which another individual P is randomly selected_n′Performing cross mutation operation to obtain the filial generation sequence Q_nAdding the mixture into a population Q;

step d: never including the current individual P_nOf arbitrary class C_kIn which another individual P is randomly selected_n′Performing cross mutation operation to obtain the filial generation sequence Q_nAdding the mixture into a population Q;

step e: and if N is less than N, making N equal to N +1, returning to the step b, otherwise, outputting the population Q.

Preferably, the specific method of cross mutation described in S4 includes: generating a progeny sequence by two-point crossing and performing a mutation operation on the progeny sequence by two-point crossing;

the specific method for generating the filial generation sequence by two-point crossing comprises the following steps:

step ①, get parent P_nAnd P_n′The progeny of which are defined as Q, respectively_nAnd Q_n′The sequence length is M;

step ②, if rand () > is not less than pc, Q_n＝P_n,Q_n′＝P_n′Otherwise, go to step ③;

step ③ randomly generating two crossing points m₁,m₂And 1 < m₁＜m₂< M for Q_nRetention of P_nSequence of workpieces at both ends of a cross point, the workpieces between the cross points being in P according to the respective workpieces_n′For Q_n′Retention of P_n′Sequence of workpieces between intersections, the workpieces at both ends of an intersection being in P relation to the corresponding workpieces_nThe sequence of (1);

the method for performing variation operation on the progeny sequence comprises the following steps:

step (1): extracting the current filial generation individual Q_n；

Step (2): if rand () is greater than or equal to pm, Q_nOtherwise, two variation points are randomly generated to exchange Q_nWorkpieces corresponding to the two middle variation points;

wherein pc is the crossover probability, pm is the variation probability, and both are global variables preset in S1.

Preferably, the method for updating the set a in S5 is as follows: sequentially extracting pareto individuals of the parent population P and the child population Q,

when in use

When the current pareto individual is added to the set A;

when in use

If the current pareto individual dominates partial solutions in the set A, removing the solution dominated in the set A, and storing the solution dominated in the set A into the current pareto individual; if the current pareto individual is not dominated by the solutions in the set A, the current pareto individual is stored in the set A, and if the current pareto individual is dominated by all the solutions in the set A, no operation is performed; repeating the operation until the pareto individuals in the parent population P and the offspring population Q are extracted;

the criterion for evaluating whether an individual is dominated is to use a pareto dominance relationship, defined as follows:

F(w)＝(f₁(w),f₂(w),...,f_r(w)), if and only if

And is

When we call w dominate u, where C_maxAnd TEC is equivalent to f₁(w) and f₂(w) that is

F(w)＝(C_max,TEC)

Pareto individuals are one or more solutions that are not dominated by other individuals throughout the population.

Preferably, the method for updating the population P in S5 is to select individuals of the updated population P from the current population P and the offspring population Q by using a selection operation of a classical NSGA-II algorithm;

the method for updating the recombination pairing probability S comprises the following steps:

defining a new solution contribution value (t) generated by performing the cross mutation operation described in S4 in the t-th iteration process as follows:

wherein, g₁(t) means crossing the updated population P using the method of step cNumber of individuals derived from fork variation, g₂(t) representing the number of individuals in the updated population P which are cross-mutated by using the method in the step d;

the recombination pairing probability S is updated every L generations by

Wherein t is the current iteration number, and the probability updating accumulated algebra L is a global variable preset in S1.

The invention also provides a system for carrying out multi-target batch scheduling optimization based on the evolutionary algorithm of clustering, which comprises

An initialization module: initializing a population scale N, a maximum iteration number MaxIteraction and a recombination pairing probability S, initializing a population P and an initialization pareto solution set A based on a processing workpiece, wherein individuals of the population P and the set A represent workpiece sequences, and the initialization iteration number t is 1;

a scheduling optimization module: executing a decoding rule on the population P to obtain scheduling schemes of all individuals, adjusting each scheduling scheme through local optimization and calculating a target value;

a clustering module: clustering the target value of the population P by using self-adaptive clustering;

a progeny evolution module: selecting a cross-variant object for individuals in the population P based on the clustering result to generate a child population Q, and calculating a target value of the child population Q by using a decoding rule and local optimization;

a data updating module: utilizing pareto individual updating sets A of the parent population P and the child population Q, performing selection operation on the parent population P and the child population Q to update the population P, and updating the recombination pairing probability S based on the updated population P;

an iteration output module: if t is less than MaxIteraction, t is t +1, returning to the scheduling optimization module, otherwise, outputting the set A.

The method and the system for carrying out multi-target batch scheduling optimization based on the clustering evolutionary algorithm have the advantages that: the distribution information of the population is extracted through self-adaptive clustering, recombination of the population is guided based on the information and the recombination mating probability, the recombination mating probability can be dynamically adjusted according to historical information, the diversity of population evolution is increased, various batch scheduling schemes can be provided for evaluation and selection, the size information of machines and workpieces is considered, and a reliable solution is provided for batch scheduling problems in the production process.

Drawings

FIG. 1 is a distribution diagram of solutions of the CBEA algorithm and the comparison algorithm provided by an embodiment of the present invention over examples 300-3-1-8;

FIG. 2 is a distribution diagram of solutions of the CBEA algorithm and the comparison algorithm provided by the embodiment of the present invention on an example 200-5-1-3;

FIG. 3 is a distribution diagram of solutions of the CBEA algorithm and the comparison algorithm on the example 100-5-s-9 according to the present invention.

Detailed Description

In order that the objects, technical solutions and advantages of the present invention will become more apparent, the present invention will be further described in detail with reference to the accompanying drawings in conjunction with the following specific embodiments.

When the scheme is explained in the embodiment, partial local variables with the same form exist, and when the variables with the same form conflict at different positions, the definition of the local algorithm where the variables are located is used as the standard; to distinguish between particular steps in a different manner, it should be understood that the different expressions are used merely to distinguish between different steps, whether in the context of an entire algorithm or a partial algorithm, and are not intended to limit the order of steps.

The problem to be solved by the application is that the batch scheduling problem of double targets is to minimize the maximum completion time and the total electricity price cost, the multi-target batch scheduling problem is substantially equivalent to a discrete multi-target optimization problem, a solution method on a continuous problem cannot be directly applied, an evolutionary algorithm is commonly used for solving the multi-target optimization problem, the effect is ideal and popular with people, meanwhile, a lot of solutions are generated in the iterative process of the evolutionary algorithm, and the solutions hide certain information related to the problem, so that people hope to mine the hidden information and apply the hidden information to the algorithm through a certain strategy. Therefore, the evolutionary algorithm is adopted and combined with the self-adaptive clustering strategy to obtain a new evolutionary algorithm based on clustering, which is called CBEA algorithm to solve the batch scheduling problem of double targets, before explaining the algorithm, firstly, a problem model aimed at by the algorithm is simplified, and basic rules of the batch scheduling problem are described as follows:

(1) each workpiece j has three attributes: time of arrival p_jMachining time r_jAnd size s_jEach machine i has four attributes: machine capacity MC, machine speed v_iPW of machining power_iAnd idle power SW_i。

(2) Defining the set of batches as B, wherein the B-th batch processed on machine i is marked as B_bi(ii) a Batch B_biMachining time PT_biEqual to the ratio of the maximum processing time of all the workpieces in the batch to the processing speed of the machine in which it is located, i.e.

Time of arrival RT_biEqual to the maximum arrival time of all workpieces in the batch, i.e. RT_bi＝max{r_j|j∈B_bi}; the maximum capacity of the batch is the capacity MC of the machine, while the sum of all workpiece sizes in the batch must not exceed the capacity of the machine, i.e.

(3) Starting time ST of a batch when it is distributed to the machines_biEqual to the maximum of the arrival time of the batch and the completion time of the previous batch, ST_bi＝max{RT_bi,CT_(b-1)i}; time-of-flight CT_biEqual to the sum of the starting processing time and the processing time, i.e. CT_bi＝ST_bi+PT_bi；

(4) Each workpiece can be placed in only one batch and can be placed in only one machine; the batch is not allowed to have any operation performed on it during processing;

(5) the optimization objective is to minimize the maximum completion time C_maxAnd aElectricity price cost TEC.

The embodiment provides a method for performing multi-target batch scheduling optimization based on a clustering evolutionary algorithm, which comprises the following steps:

s1: initializing a population P based on experience initialization population scale N, maximum iteration number MaxIteraction and recombination pairing probability S, and initializing the population P based on a processing workpiece, wherein individuals of the population P represent workpiece sequences, and the method for initializing the population P comprises the steps of generating the workpiece sequences by a special heuristic rule, and at least comprises three individuals which are arranged according to an ascending order and a descending order of processing time and an ascending order of arrival time; the remaining individuals are generated using a second initialization method, namely random ordering.

And initializing the pareto solution set A, namely setting A as an empty set, wherein the number of initialization iterations t is 1.

S2: executing a decoding rule on the population P to obtain scheduling schemes of all individuals, adjusting each scheduling scheme through local optimization, and then calculating a target value of the adjusted scheduling scheme;

decoding rules: the decoding rule is to set any group X as X_n|n∈[1,N]Of individuals X_nThe corresponding workpiece sequence is converted into a batch scheme, and the batches are distributed to different machines, so that a scheduling scheme X is obtained_n' the concrete method is as follows:

step i: initializing n-1, scheduling scheme set

step v: return to step iv until all batches are allocated to machinesOn the device, the current individual X_nCorresponding scheduling scheme X'_nAdding a set X';

step vi: if N is less than N, making N equal to N +1, returning to the step ii, otherwise, outputting a scheduling scheme set X';

where the capacity of the new lot is equal to the machine capacity MC.

Local optimization: the method for adjusting the scheduling scheme through local optimization and calculating the target value of the scheduling scheme comprises the following steps:

step I: inputting a scheduling scheme set X', obtaining the number m of machines and the electricity price EP (t) in a time period t, and initializing n to 1 and i to 1;

step II: obtaining current scheduling scheme X'_nMachine M_iNumber of lots | M_iI, initialization k ═ M_i|；

Step III: due to the difference of unit electricity prices in different time periods, the maximum completion time C is within a reasonable time range_maxUnder the condition of no change, the aim of reducing the TEC can be achieved by adjusting the processing sequence of the upper batch of the machine. The specific operation is that the current batch is moved backwards in sequence according to unit time in the period of finishing the current batch and starting processing the next batch until the electricity price cost can be reduced, and the specific method comprises the following steps:

when k is equal to | M_iAnd satisfy

When k ≠ M_iAnd satisfy

Wherein, PW_iFor working of machine iPower, SW_iFor idle power of machine i, CT_kiFor the completion time of the k-th lot on machine i, ST_kiThe starting processing time of the kth batch on the machine i;

CT_ki＝ST_ki+PT_ki

ST_ki＝max{RT_ki,CT_(k-1)i}

RT_ki＝max{p_j|j∈B_ki}

p_jIs the arrival time of workpiece j;

C_max＝max{CT_ki|i∈[1,m]}

Specifically, in step S2, when the group P is operated, the group P needs to be assigned to the set X, that is, X ═ P, and after decoding and local optimization form a scheduling scheme, the scheduling scheme X ' and the target value X of the set X are assigned to the group P, that is, P ' ═ X ', P ═ X.

S3: clustering the target value of the population P by using self-adaptive clustering; the following is a general set of target values x ═ x_n|n∈[1,N]Explaining a self-adaptive clustering method;

step A: obtaining the current iteration times t and a target value set x ═ x_n|n∈[1,N]}；

wherein mod (T, T) represents the remainder of T/T; that is, coarse clustering is performed once every T iterations, and in the rest of the cases, clustering is performed only by using a K-means algorithm, where a coarse clustering period T is an empirical value, and in S1, T is initialized to 10 in the preferred embodiment;

and C: inputting the target value set into a Canopy algorithm to obtain the clustering number K and each class C_k,k∈[1,K]Centroid point m_k；

This step is to call the Canopy algorithm, which is known in the prior art, and for the sake of understanding, a specific procedure is given here:

a) the method comprises the following steps Set of target values x ═ x_n|n∈[1,N]Storing the data into a List, and initializing K to be 0;

b) the method comprises the following steps Randomly choosing a point x from the List_iAnd calculating other points x in the List_nTo point x_iThe euclidean distance d of;

c) the method comprises the following steps All d < T₁Generates a new canty_k＝{x_n|dis(x_n,x_i) < T1}, dis (a, b) represents the Euclidean distance between a and b, let K be K +1, and d < T in List is removed₂A point of (a);

d) the method comprises the following steps Judging whether the List is empty or not, and determining that the List is idle e); otherwise, turning to b);

e) the method comprises the following steps For each canty_k(K ═ 1, 2.. times., K), its centroid point is calculated

In the embodiment, only the parameter T is calculated₁And T₂The values of (a) are defined, and the rest are default values; wherein T is₁＝2T₂，T₂Is the average of the euclidean distances between all individuals in the target value set x.

Similarly, the K-means algorithm in the prior art is called, and the specific method is as follows:

a) the method comprises the following steps X is to be_n(N ═ 1, 2.. times.n) to class C_kWherein

argmin denotes the position corresponding to the minimum value, dis (x)_n,m_j) Is x_nAnd m_jThe euclidean distance between;

b) the method comprises the following steps For each class C_kUpdate its centroid point

When clustering a target value set P of a population P, it is necessary to assign the set P to a set x, that is, x is P.

Usually, most clustering algorithms need to assign corresponding classification numbers in advance, and the clustering result has a certain relationship with the assigned classification numbers in advance, but sometimes the classification number is not determined in advance too well, which obviously affects the performance of the clustering algorithms. Therefore, it is desirable that the cluster classification number can be dynamically adjusted according to the current population, and it is also desirable that the dynamic adjustment is as accurate as possible and the process is not overly complicated. Therefore, the method adopts the Canopy + K-means algorithm to cluster the target value of the population, firstly, the K-means algorithm is a classic clustering algorithm based on division, but the method has some defects: 1. the selection of the initial centroid point has blindness and randomness; 2. the number of clusters needs to be determined in advance, and the Canopy algorithm is a coarse clustering algorithm, namely, the optimal number of clusters can be simply and quickly given, but an accurate clustering result cannot be given, so that the two can be mutually combined, and the advantages and the disadvantages can be made up. In addition, each clustering process needs a large amount of iteration operations and then can be converged, so that time consumption is increased inevitably, and in order to reduce time consumption, the iterative process of the clustering algorithm is integrated into the evolutionary process, namely, the clustering algorithm can gradually mine distribution information while the evolutionary algorithm searches. In a word, the Canopy algorithm can firstly provide a more reasonable initial centroid point, eliminate the dependence of the K-means algorithm on the prior knowledge, and then cluster the target values of the population by using the K-means algorithm based on the initial centroid point according to the current iteration condition, thereby obtaining an accurate clustering result.

It should be noted that, as iterative evolution progresses, the whole population may be allocated to one class by the Canopy algorithm, which may affect the execution of heterogeneous crossing in subsequent cross variation, and for this problem, a person skilled in the art may appropriately modify the algorithm, increase the judgment condition for the number of clusters, and when Canopy only obtains one cluster set, the population is forcibly divided into at least two classes, and since the whole population may be allocated to one cluster, the criteria for forced classification may not be required at this time, and may be divided randomly or according to a specific rule, and only care needs to be taken to ensure that the number of individuals between different classes is not very different.

the method for determining the cross variation object comprises the following steps:

step e: and if N is less than N, making N equal to N +1, returning to the step b, otherwise, outputting the population Q, namely the child population of the current population P.

The embodiment strengthens the local development capacity of the population through mating among the same species, promotes the global exploration capacity of the population through mating among the different species, and alternately uses two mating modes through dynamically adjusted recombination pairing probability, thereby ensuring the balance between development and exploration as much as possible and improving the diversity of the population.

The embodiment also provides a system for carrying out multi-target batch scheduling optimization based on the evolutionary algorithm of clustering, which comprises

The specific working method and principle of the above modules are the same as those of the batch scheduling optimization method.

Cross mutation: because the algorithm solves the problem of combined optimization and adopts a coding mode based on a workpiece sequence, the cross variation mode on the common continuous optimization problem can not be directly applied to the current problem.

The method for producing progeny sequences by cross-mutation provided in this example comprises: generating a progeny sequence by two-point crossing and performing a mutation operation on the progeny sequence by two-point crossing;

where pc is the crossover probability, and pc is preset in S1 so that pc is not changed in the whole iteration process, that is, the crossover probability pc is a global variable.

table 1: cross operation schematic table

Taking two sequences of 10 workpieces shown in table 1 as an example, the two sequences are parent1(2,3,5,6,8,1,9,7,4,10) and parent2(7,8,1,3,5,2,10,4,9,6), the randomly generated cross-point positions are 4 and 8, respectively, for child1, the workpiece sequences at both ends of the parent1 cross-point are reserved, and the workpiece sequences between child1 cross-points are arranged in the order of the remaining workpieces in parent 2; similarly for child2, the sequences of workpieces between parent2 intersections are retained, and the sequences of workpieces at both ends of the child2 intersection are arranged in the order of the remaining workpieces in parent 1.

step (1): extracting the current filial generation individual Q_n；

Step (2): if rand () is greater than or equal to pm, Q_nOtherwise, two variation points are randomly generated to exchange Q_nAnd (5) workpieces corresponding to the two variation points, wherein pm is a variation probability and is also a global variable preset in S1.

Table 2: schematic representation of mutation operation

As shown in table 2, for the child1 sequences obtained in table 1, the randomly generated crossover work positions are 3 and 8, a new child1 sequence shown at the bottom in the table is obtained, the sequence is saved in the offspring population, and then the cross mutation operation is continued on the next parent individual until all individuals in the population P generate offspring individuals subjected to the cross mutation operation.

After the filial generation population Q is generated through cross variation, decoding rules and local optimization are required to be executed on the filial generation population Q to obtain a target value of the filial generation population, the specific method is introduced, only Q needs to be given to X before starting, and after the specific method is finished, a result corresponding to the set X is given to the set Q; reference may be made to the assignment processing method of the population P.

S5: updating a pareto solution set A by using pareto individuals of a parent population P and a child population Q, performing selection operation on the parent population P and the child population Q to update the population P, and updating a recombination pairing probability S based on the updated population P;

the method for updating the set A comprises the following steps: sequentially extracting pareto individuals of the parent population P and the child population Q,

when in use

When the current pareto individual is added to the set A;

when in use

F(w)＝(f₁(w),f₂(w),...,f_r(w)), if and only if

And is

When we call w dominate u. In the present example, f (w) ═ C_max,TEC)，C_maxAnd TEC is equivalent to f₁(w) and f₂(w), r is 2, w is the individual solution in the population. In addition, there are generally many pareto individuals in the overall population that are not dominated by other solutions.

Based on the above method for updating the set a, if the individuals in the set a are dominated by any pareto individual, all the dominated individuals are deleted, so that some known better individuals or individuals corresponding to the currently used scheduling scheme may be placed in the initialization of the set a, and in order to reduce the complexity of data processing, the set a is preset as an empty set in step S1.

Selecting an individual of the updated population P from the current population P and the offspring population Q by adopting the selection operation of a classical NSGA-II algorithm; the selection operation comprises non-dominated sorting and congestion distance calculation;

wherein, g₁(t) the number of individuals of the updated population P that were cross-mutated using the method of step c, g₂(t) representing the number of individuals in the updated population P which are cross-mutated by using the method in the step d;

the recombination pairing probability S is updated every L generations by

Wherein t is the current iteration number, and the probability updating accumulated algebra L is a global variable preset in S1; in order to prevent the search of the algorithm from being totally biased to exploration or development, the introduced constraint conditions force the recombination pair probability to be defined, namely, when the contribution degree of the accumulated new solution of the L generation is not more than 0.2L, the recombination pair probability is set to be 0.8, and when the contribution degree of the accumulated new solution of the L generation is not less than 0.8L, the recombination pair probability is set to be 0.2.

S6: if t < maxitration, t ═ t +1, jump to S2, otherwise output set a.

And in the iteration period, after a new population P is obtained, returning to S2 for the next iteration again until the preset iteration times MaxIteraction is reached, and obtaining a pareto solution set A, namely a set of optimal individuals.

Simulation experiment

The performance of the CBEA Algorithm provided in the present example will be tested by comparison with related art algorithms, NSGA-II (see K Deb, A Pratap, S Agrarwal, et al. A Fast and Elitist Multi object Genetic Algorithm: NSGA-II [ J ]. IEEE Transactions on evolution calculation, 2002,6(2): 182) and MODED (see S C Zhou, L X Lin, NDu, et al. A Multi-object differential evaluation for processing of a processing architecture connected Computing environment [ J ]. Computers, Research, 96-96 processing Algorithm, J. (see ZJ. correction, J. conversion, S20155. J.), the decoding modes of the workpiece sequences of all algorithms are consistent with the method provided by the embodiment, all test examples are generated randomly, different test examples mainly have differences between the workpiece and the machine information, and the information of the test examples is shown in table 3.

Factors of the fact	Value range	Number of values
			Size of work h	100、200、300	3
Size of work piece s_j	U[1,15]、U[15,35]	2
			Arrival time r of workpiece_j	U[1,LB]	1
Time p for machining workpiece_j	U[8,48]	1
			Number of machines m	3、5	2
Machine capacity MC	40	1
			Machining power PW	2vv	5
Machine idle power SW	1	1
			Machine speed v	1、1.5、2、2.5、3	5

Table 3: testing example information

The LB in the range of values of the arrival time of the workpiece in table 3 is calculated as follows:

LB＝ρZ

where ρ is a coefficient, ρ is set to 0.1 in the experiment provided in this embodiment, and Z represents the sum of all the workpiece processing times in the current calculation example; reference may be made in particular to the document P Damodaran, M C Velez-Gallego.Heuritics for makespan min immunization on parallel boards processing machines with indirect joint times [ J ]. Int J Adv Manual Technol,2010,49: 1119-.

In addition, different machines have speed differences, and when the number of the machines is 3, the speeds of 3 machines are 1,2 and 3 respectively; for a majority of machine numbers of 5, the machine speeds are 1, 1.5, 2, 2.5, 3, respectively.

Based on the workpiece size and workpiece dimensions given in table 3, 6 test examples were randomly generated, each containing 10 test examples, and then tested in an environment of different number of machines, that is, 12 sets of test examples in total. The total electricity price cost relates to an electricity price standard, a Beijing area time-of-use electricity price function is selected as a standard after partial documents are referred, and a specific function formula is as follows:

all four algorithms for comparison need to define part of parameters, and the parameters possibly influence the performance of the algorithms, so that the fairness of comparison experiments can be influenced, in order to reduce the influence of the parameters on the performance of the algorithms as much as possible, the experiment parameters in the documents are adopted for both the MODED E algorithm and the APMO algorithm, the NSGA-II algorithm parameters are consistent with the CBEA algorithm parameters provided by the application, and the specific parameters refer to Table 4.

CBEA	MODDE	NSGA-II	APMO
				Population size N:100	Population size N:100	Population size N:100	Population size N:100
Iteration number MaxIteration 500	Iteration number maxIteration 500	Iteration number maxIteration 500	Iteration number maxIteration 500
				Cross probability pc 0.9	Cross probability pc 0.9	Cross probability pc 0.9	DE control parameter CF 0.5
The variation probability pm is 0.2	The variation probability pm is 0.1	The variation probability pm is 0.2	DE control parameter CR:1
				Initial recombination pairing probability S:0.3			Initial mating probability β:0.5
Probability updating cumulative algebra L10			History length HL:15
				Coarse clustering period T10			Maximum iteration number of clustering 50
			5 clustering result keeping unchanged times
							Damping coefficient of 0.5

Table 4: algorithm parameters

In addition, all algorithms are realized by C + + under a windows10 system and run under a visual studio 2017 integrated development environment, hardware is a Corei53.40GHz processor, memory is 16GB, and test examples under each type run for 10 times.

In order to measure the quality of the algorithm, the embodiment adopts three different indexes to evaluate the performance of the algorithm, namely the scale, the coverage rate and the over-volume index of the pareto solution set;

1) the scale of pareto solution set a; for the multi-objective optimization algorithm, more than one solution is obtained, and the more pareto solutions are obtained, which means that more choices can be provided for a decision maker, and the better the diversity of the algorithm is;

2) coverage rate; it was first proposed by E Zitzler, L Thile, Multi objective Evolution Algorithms, A C orthogonal Case Study and the Strength partner Approach [ J ]. IEEETransmission on Evolution Approach calculation, 1999,3(4):257-271, to compare the degree of superiority between two algorithm solutions, with the formula:

c (E, F) indicates how much of the solution in solution set F is dominated by the solutions in solution set E. A larger value of C (E, F) indicates that more solutions in the solution set F are dominated by the solutions of the solution set E, that is, the algorithm for obtaining the solution set E is superior to the algorithm for obtaining the solution set F, wherein C (E, F) belongs to [0,1 ]. In addition, this index is asymmetric, i.e., C (E, F) ≠ C (F, E).

3) An ultra volume index; the evaluation index is a commonly used evaluation index of a multi-target evolutionary algorithm, is used for evaluating the approximation degree of a pareto solution set obtained by the algorithm to approach a real pareto front, and actually measures the convergence of the algorithm, the larger the super volume value of the pareto solution set of the algorithm is, the better the convergence of the algorithm is, the closer the super volume value is to the real pareto front, but a reference point is also needed for calculating the super volume value, the dimensionality of the reference point is equal to the number of targets solved by the problem, and the reference point is set as

Wherein

Represents the maximum C in all pareto solutions obtained by all algorithms on all examples_maxValue, Z_TECRepresents the maximum TEC value among all pareto solutions.

Tables 5-8 show the results of the simulation tests, wherein the test example types are composed of workpiece number-machine number-workpiece size, wherein the total number of workpieces is 100, 200, 300, the machine number is 3 or 5, and the workpiece size is divided into two types of large and small, for example, 100-3-l represents 100 workpieces, 3 machines, large-sized workpieces, and the same can be understood for other example representations.

Types of examples	CBEA	MODDE	NSGA-II	APMO
					100-3-s	2.428E+07	2.412E+07	2.375E+07	2.310E+07
100-5-s	2.400E+07	2.387E+07	2.356E+07	2.309E+07
					200-3-s	1.549E+07	1.501E+07	1.419E+07	1.317E+07
200-5-s	1.505E+07	1.471E+07	1.406E+07	1.351E+07
					300-3-s	8.434E+06	7.970E+06	6.894E+06	5.906E+06
300-5-s	8.045E+06	7.761E+06	7.033E+06	6.576E+06
					100-3-l	1.679E+07	1.680E+07	1.666E+07	1.643E+07
100-5-l	1.915E+07	1.910E+07	1.877E+07	1.859E+07
					200-3-l	5.501E+06	5.407E+06	5.272E+06	4.855E+06
200-5-l	8.239E+06	8.005E+06	7.612E+06	7.234E+06
					300-3-l	4.627E+05	4.082E+05	3.380E+05	1.832E+05
300-5-l	1.892E+06	1.622E+06	1.281E+06	9.576E+05
					avg	1.229E+07	1.206E+07	1.162E+07	1.113E+07

Table 5: hyper-volume index value

As can be seen from Table 5, the CBEA algorithm provided by the present embodiment is superior to the other three algorithms except for the 100-3-1 example; the CBEA algorithm is also optimal from the point of view of the average hypervolecity index, NSGA-II, MODDE, APMO are in turn. Further analysis can find that the difference between the over-volume index value obtained by the CBEA algorithm and the over-volume index value obtained by other algorithms is larger and larger as the number of workpieces is increased, and the phenomenon exists in both large workpieces and small workpieces, so that the convergence of the CBEA algorithm is better than that of a comparison algorithm. The effect of the example 100-3-l is not optimal, possibly due to the large size of the workpiece, the small number of machines and workpieces, which results in at most one or two workpieces in the batch, so that each algorithm actually yields a batch of almost identical results, and, in addition to the small number of machines, the sequence of machining on the machines may vary greatly, which ultimately results in a less than optimal effect on the example.

Types of examples	CBEA	MODDE	NSGA-II	APMO
					100-3-s	8.4	7.2	10	10.6
100-5-s	8	6.2	8.3	8.2
					200-3-s	7.7	11.2	11	10.2
200-5-s	7.4	6.5	6.9	9.2
					300-3-s	8.4	16.2	11.7	11
300-5-s	6.5	8.7	8.2	9.7
					100-3-l	13.9	13.9	12.9	6.9
100-5-l	9.8	9.8	7.7	9.2
					200-3-l	17.6	13.3	13.2	6.2
200-5-l	10.6	9.2	10.2	8.8
					300-3-l	16.9	9.5	11.3	5.3
300-5-l	12.3	9.3	10.8	9.1
					avg	10.6	10.1	10.2	8.7

Table 6: pareto solution scale

According to table 6, it can be found that for the index of pareto solution set size, the CBEA algorithm provided in this embodiment has no significant effect over the volume index value, especially on small-sized workpieces, the algorithm provided in this embodiment does not dominate, and the 3 algorithms compared with each other dominate over several sets of test examples. But its effect is shown on large-sized workpieces, the average pareto solution obtained on 6 sets of test examples of which is the most. The average pareto solution solved by the CBEA algorithm is the most in the whole test calculation, the diversity of the algorithm is guaranteed to a certain extent, and the algorithm has room for improvement on small-size workpieces.

Table 7: coverage index value of CEBA algorithm and comparison algorithm

Table 8: comparing coverage index values between algorithms

Referring to Table 7, it can be found that the C value of CBEA for NSGA-II is substantially above 0.98, the C values of the APMO algorithm are all 1, and the MODDE algorithm is above 0.9 except for 100-3-1, which shows that the CBEA algorithm provided by the embodiment can cover most solutions of the comparison algorithm, while the three algorithms NSGA-II, APMO and MODDE compared in the reverse calculation are mostly 0 or close to 0 for the C value of CBEA, therefore, the solution in the pareto solution set a obtained by the CBEA algorithm provided by this embodiment is significantly better than the comparison algorithm, in addition, on the basis of the 100-3-l test example, no matter C (CBEA, MODDE) or C (MODDE, CBEA) is too good, and the solution obtained by the CBEA at 100-3-l has no advantage per se, so the index value calculated by the 100-3-l test example is not too good; the specific reasons are analyzed in detail previously. Further observation of the coverage relationship between the comparison algorithm in Table 8 shows that for the problems faced by this example, the MODDE algorithm is better than NSGA-II and APMO, wherein NSGA-II is better than APMO, and APMO is the worst.

FIGS. 1-3 show partial pareto frontograms of CBEA and a comparative algorithm, and it can also be seen that the CBEA algorithm provided in this example is significantly better than the comparative algorithm, as exemplified by FIG. 1, whose example 300-3-l-8, represents the result of the 8 th test example under the 300-3-1 example.

Claims

1. The method for multi-objective batch scheduling optimization based on the evolutionary algorithm of clustering is characterized in that:

S1: Initialize the population size N, the maximum number of iterations MaxIteration, and the recombination pairing probability S; initialize the population P based on the machining workpiece, and initialize the Pareto solution set A, the individuals of the population P and the set A represent the workpiece sequence, and the initialization iteration number t=1;

S2: Execute the decoding rule on the population P to obtain the scheduling schemes of all individuals, adjust each scheduling scheme through local optimization, and calculate the target value of the adjusted scheduling scheme;

S3: Use adaptive clustering to cluster the target value of the population P;

S4: Based on the clustering results, select the cross-mutated objects for the individuals in the population P to generate the offspring population Q, and use the decoding rules and local optimization to calculate the target value of the offspring population Q;

S5: Use the Pareto individuals of the parent population P and the child population Q to update the set A, perform a selection operation on the parent population P and the child population Q to update the population P, and update the recombination pairing probability S based on the updated population P;

S6: If t<MaxIteration, t=t+1, jump to S2, otherwise output set A.

2. The method for multi-objective batch scheduling optimization by cluster-based evolutionary algorithm according to claim 1, is characterized in that: the method for initializing population P described in S1 is: according to processing time ascending order, descending order and arrival time respectively The workpiece sequences of three individuals are obtained by ascending order, and the workpiece sequences of the remaining individuals are randomly generated.

3. The method for multi-objective batch scheduling optimization by clustering-based evolutionary algorithm according to claim 2, characterized in that: in S2 and S4, any population X={X _n |n∈[ 1,N]} The workpiece sequence corresponding to the individual X _n is transformed into the scheduling plan X' _n , the specific method is as follows:

Step i: Initialize n=1, scheduling scheme set

Step ii: Put the workpieces in X _n in turn into the batch that can accommodate the workpiece and have the smallest remaining capacity. If there is no batch that meets the conditions, create a new batch and put it into the current workpiece until all the workpieces are allocated;

Step iii: Arrange all batches in ascending order of batch arrival time;

Step iv: Allocate the current batch to the machine with the earliest completion time. If there are multiple machines that meet the conditions, select the machine with the fastest processing speed;

Step v: Return to step iv, until all batches are allocated to the machine, and add the scheduling plan _X'n corresponding to the current individual _Xn to the set X';

Step vi: if n<N, let n=n+1, return to step ii, otherwise output the set X';

Among them, the capacity of the new batch is equal to the machine capacity MC.

4. the method that the evolutionary algorithm based on clustering according to claim 3 carries out the method for multi-objective batch scheduling optimization, it is characterized in that: the method for local optimization adjustment scheduling scheme described in S2 and S4 and calculating the target value of the scheduling scheme after optimization for:

Step I: Input the set of scheduling plans X', obtain the total number of machines m and the electricity price EP(t) in the time period t, initialize n=1, i=1;

Step II: Obtain the batch quantity |M _i | on the machine Mi of the current scheduling scheme X′ _n , and initialize k _{=|M i} _| ;

Step III: When k=|M _i |, and satisfy

When PW _i ×EP(CT _ki +1)+SW _i ×EP(ST _ki +1)-PW _i ×EP(ST _ki +1)≤0 or CT _ki <ST _(k+1)i , let ST _ki =ST _ki +1, CT _ki =CT _ki +1;

When k≠|M _i |, and satisfy

PW _i ×EP(CT _ki +1)+SW _i ×EP(ST _ki +1)-PW _i ×EP(ST _ki +1)-SW _ki ×EP(CT _ki +1)≤0

or CT _ki <ST _(k+1)i ,

Let ST _ki =ST _ki +1, CT _ki =CT _ki +1;

Among them, PW _i is the processing power of machine i, SW _i is the idle power of machine i, CT _ki is the completion time of the k-th batch on machine i, and ST _ki is the starting processing time of the k-th batch on machine i;

CT _ki =ST _ki +PT _ki

ST _ki =max{RT _ki ,CT _(k-1)i }

Among them, PT _ki is the processing time of the kth batch on machine i, which is equal to the ratio of the maximum processing time of all workpieces in the batch to the processing speed of the machine where it is located, namely

r _j is the processing time of workpiece j, B _ki is the kth batch on machine i, and v _i is the processing speed of machine i;

RT _ki is the arrival time of the kth batch on machine i, which is equal to the maximum arrival time of all workpieces in the batch, i.e.

RT _ki =max{p _j |j∈B _ki }

p _j is the arrival time of workpiece j;

Step IV: when k>1, set k=k-1, and return to step III;

Step V: if i<m, set i=i+1, return to step II, otherwise calculate the target value of the current scheduling plan _X'n , that is, the maximum completion time _Cmax and the total electricity price cost TEC;

C _max =max{CT _ki |i∈[1,m]}

Add the target value x _n corresponding to the current scheduling scheme X' _n into the target value set x;

Step VI: If n<N, let n=n+1, return to step II, otherwise output the target value set x.

5. the method that the evolutionary algorithm based on clustering according to claim 4 carries out the method for multi-objective batch scheduling optimization, it is characterized in that: the described method of S3 is carried out adaptive clustering to target value:

Step A: Obtain the current iteration number t and the target value set x;

Step B: if t=1 or mod(t, T)=0, then jump to step C for rough clustering, otherwise jump to step D to update the clustering result;

Step C: Input the target value set into the Canopy algorithm to obtain the number of clusters K and the centroid point m _k of each class C _k ,k∈[1,K];

Step D: using the K-means algorithm to perform a single clustering based on the current centroid point, and update the centroid point m _{k of the class C k} _;

Among them, mod(t, T) represents the remainder of t/T, and the coarse clustering period T is a global variable set in S1.

6. the method that the evolutionary algorithm based on clustering according to claim 5 carries out the method for multi-objective batch scheduling optimization, it is characterized in that: described in S4 is that the method for determining the object for the cross-mutation individual is:

Step a: Obtain the set P={P _n |n∈[1,N]} of the population P, and the clustering result C={C _k |k∈[1,K]} of the target value set p of the population P; Apply the clustering result C of the target value set p to the population P, let n=1;

Step b: If rand()≤S, go to step c, otherwise go to step d, where rand() represents a random number;

Step c: randomly select another individual P _n′ from the class C _k to which the current individual P _n belongs to perform a crossover mutation operation, and add the offspring sequence Q _n to the population Q;

Step d: randomly select another individual P _n′ from any class C _k that does not include the current individual P _n to perform a crossover mutation operation, and add the offspring sequence Q _n to the population Q;

Step e: If n<N, let n=n+1, return to step b, otherwise output the population Q.

7. The method for multi-objective batch scheduling optimization by clustering-based evolutionary algorithm according to claim 6, is characterized in that: the concrete method of crossover variation described in S4 comprises: generate offspring sequence by two-point crossover and pass Two-point exchange performs the mutation operation on the descendant sequence;

The specific method for generating a progeny sequence through two-point crossover is:

Step 1: Obtain the sequence of the parent P _n and P _n′ , the children are defined as Q _n and Q _n′ respectively, and the sequence length is M;

Step ②: if rand()≥pc, then Q _n =P _n , Q _n′ =P _n′ ; otherwise, step ③ is performed;

Step ③: randomly generate two intersection points m ₁ , m ₂ and 1<m ₁ <m ₂ <M, for Q _n , keep the workpiece sequence at both ends of the intersection point of P _n , and the workpieces between the intersection points are at P according to the corresponding workpieces. The order in _n' is arranged, for Q _n' , the sequence of workpieces between the intersections of P _n' is reserved, and the workpieces at both ends of the intersection are arranged in the order of the corresponding workpieces in P _n ;

The method for performing mutation operation on the progeny sequence is:

Step (1): extract the current offspring individual Q _n ;

Step (2): If rand()≥pm, then Q _n is unchanged, otherwise two mutation points are randomly generated, and the workpieces corresponding to the two mutation points in Q _n are exchanged;

Among them, pc is the crossover probability, and pm is the mutation probability, both of which are preset global variables in S1.

8. The method for multi-objective batch scheduling optimization by cluster-based evolutionary algorithm according to claim 7, is characterized in that: the method for updating set A described in S5 is: successively extract parent population P and child population Q the Pareto individual,

when

When , add the current Pareto individual to set A;

when

When , if the current Pareto individual dominates some solutions in set A, remove the dominated solutions in A and store them in the current Pareto individual; if the current Pareto individual and the solutions in set A do not dominate each other, Then save the current Pareto individual into set A. If the current Pareto individual is dominated by all solutions in set A, no operation is performed; the above operations are repeated until the parent population P and child population Q are extracted. Pareto individual;

The criterion for evaluating whether an individual is dominated is to use the Pareto dominance relationship, which is defined as follows:

F(w)=(f ₁ (w),f ₂ (w),...,f _r (w)) if and only if

f _l (w)≤f _l (u), and

When f _q (w)≤f _q (u), we say that w dominates u, where C _max and TEC are equivalent to f ₁ (w) and f ₂ (w), respectively, namely

F(w)=(C _max ,TEC)

A Pareto individual is one or more solutions that are not dominated by other individuals in the entire population.

9. the method that the evolutionary algorithm based on clustering according to claim 8 carries out multi-objective batch scheduling optimization, it is characterized in that: the method for updating population P described in S5 is to adopt the selection operation of classical NSGA-II algorithm from current Select the individuals of the updated population P from the population P and the offspring population Q;

The method for updating the recombination pairing probability S is:

The new solution contribution value (t) generated by the cross-mutation operation described in S4 during the t-th iteration is defined as:

Among them, g ₁ (t) represents the number of individuals in the updated population P obtained by cross-mutation using the method of step c, and g ₂ (t) represents the number of individuals in the updated population P obtained by using the method of step d cross-mutation;

The recombination pairing probability S is updated every L generation, the method is

Among them, t is the current number of iterations, and the probability update cumulative algebra L is a global variable preset in S1.

10. A system for multi-objective batch scheduling optimization based on a clustering evolutionary algorithm, characterized in that: comprising:

Initialization module: initialize the population size N, the maximum iteration number MaxIteration and the recombination pairing probability S, initialize the population P based on the processing workpiece, initialize the Pareto solution set A, the individuals of the population P and the set A represent the workpiece sequence, and the number of initialization iterations t=1 ;

Scheduling optimization module: execute decoding rules on population P to obtain scheduling schemes of all individuals, adjust each scheduling scheme through local optimization and calculate the target value;

Clustering module: Use adaptive clustering to cluster the target value of population P;

The offspring evolution module: based on the clustering results, select the cross-mutated objects for the individuals in the population P to generate the offspring population Q, and use the decoding rules and local optimization to calculate the target value of the offspring population Q;

Data update module: use the Pareto individuals of the parent population P and the child population Q to update the set A, perform a selection operation on the parent population P and the child population Q to update the population P, and update the recombination pairing probability S based on the updated population P;

Iterative output module: if t<MaxIteration, t=t+1, return to the scheduling optimization module, otherwise output set A.