CN118966681B - Optimization method for early-stage workpiece number in single machine scheduling in consideration of constraint of release and deadline - Google Patents

Abstract

The invention discloses an optimization method for the number of delayed workpieces in single-machine scheduling with release and deadline constraints, which particularly considers a special pseudo-symmetrical breaking method based on a substitution group theory so as to reduce the calculated amount of a proposed algorithm. Based on the symmetric group replacement parity of the original search space, the problem-specific pseudo-symmetric property is introduced, and the search space of the algorithm is halved. The algorithm explores promising areas in the reduced search space, generates sub-solution sequences with position-based crossover, relies on simulated annealing based on pseudo-symmetric destruction to check in depth for neighborhood solutions, and relies on distance and quality-based population update mechanisms to ensure healthy populations. Compared with the current most advanced algorithm in the examples of multiple scales, the method provided by the invention has excellent performance on each index, can obtain better solutions in a shorter time, can provide higher-quality solutions for decision makers in a short time, and provides important management guidance for actual production scheduling of enterprises.

Description

Optimization method for early-stage workpiece number in single machine scheduling in consideration of constraint of release and deadline

Technical Field

The invention relates to the technical field of intelligent optimization and production scheduling optimization, in particular to an optimization method for a delayed workpiece number in single machine scheduling with release and deadline constraint.

Background

In modern manufacturing, production scheduling problems are an important class of optimization problems, the core goal of which is to reasonably allocate production resources to accomplish production tasks in an optimal manner. The single machine scheduling problem is widely focused as one of the basic problems of production scheduling. Particularly in practical production, the release time and the cut-off time of the workpiece are important constraints that cannot be ignored. The technical scheme aims at solving the single machine scheduling problem with release and deadline constraint, optimizing the number of the delayed work pieces and has important theoretical and practical values. In a single machine scheduling problem with release and deadline constraints, each workpiece has not only processing time, but also release time and deadline. The release time specifies when the workpiece can begin processing, and the expiration time specifies when the workpiece should complete processing before. If the work piece fails to complete before the expiration time, a pull-out period will occur, which may lead to bad consequences in actual production, such as fines, customer complaints, etc.

In the existing scheduling methods, many researches focus on the use of accurate algorithms to process simplified small-scale problem examples, the solving methods of the problems are relatively mature, mainly branch delimitation and only can process problems of at most 300 workpieces, but the problems of long solving time, high requirement on computer performance, incapability of processing larger-scale problems and the like exist in the methods, and the problems are difficult to apply in practical industry. Furthermore, when considering the release time and deadline constraints, the complexity of the problem increases significantly, making it more difficult for existing scheduling algorithms to be applied directly. The existing scheduling method mainly focuses on minimizing the total deadline or the maximum deadline, and ignores the problem of optimizing the deadline work piece. In actual production, reducing the number of work pieces in the pull-out period is often of more direct economic and management significance than minimizing the pull-out period. Therefore, the invention provides improvement for the problems of long solving time, high computer performance requirement, small scale of the processable problem and the like of the existing algorithm.

Disclosure of Invention

Aiming at the defects of the prior art, the invention provides the optimization method and the system for the number of the delayed workpieces in the single machine scheduling with release and deadline constraint, which have the advantages of reduced search space, high solving efficiency, good solving quality and the like, and solve the technical problems.

In order to achieve the above purpose, the invention provides a method for considering the number of the delayed workpieces in the single machine scheduling with release and deadline constraint, comprising the following steps:

S1, constructing a mathematical model considering a single machine scheduling problem with release and deadline constraints, and setting constraints on the model, wherein the specific expression is as follows:

s.t.

Where N represents the number of workpieces to be processed, pi represents the sequence of workpieces to be processed, pi_N represents the set of all possible sequences of workpieces, i e N,Respectively represents the release time, the processing time and the cut-off time of the workpiece pi_i,Indicating the finishing time of the workpiece pi_i,Indicating the completion time of the workpiece pi_i-1,Indicating whether the workpiece pi_i is in a pulling period, wherein the pulling period is 1, and the normal delivery is 0;

S2, constructing a modular factor replacement group algorithm based on a replacement group theory, and solving the scheduling problem in the step S1;

S2.1, reading the optimal sequence of the model in the step S1 as a sub-solution sequence;

s2.2, initializing an algorithm search area flag S_flag and letting S_flag =0 or 1, i.e. deciding that the algorithm searches on either the odd side or the even side in the parity search space, searching on the even side when S_flag =0, searching on the odd side when S_flag =1;

The permutation group theory specifically comprises a given symmetry group, wherein the symmetry group consists of two sets, all elements which are possibly permuted in the symmetry group can be divided into an odd part and an even part, each set consists of the order multiplication of each element on one side of the symmetry group, and the one-to-one mapping from one set to the other set is called the permutation group theory;

Based on the theory, the search space of the algorithm can be divided into two sequences with the same number;

S2.3, optimizing data generated by S1 in each population by using a local search algorithm according to the population on the same side obtained in the step S2.2, wherein the local search algorithm is an algorithm for solving the optimization problem;

s2.4, generating a new sub-subsequence by using a position-based crossing method for the data after the optimization of S2.3;

S2.5, restoring the child subsequence positioned at the odd side of the search space in the new child subsequence generated in the S2.4 to the search space at the even side, and if the child subsequence positioned at the odd side is not available, skipping the step, wherein the specific steps are as follows:

S2.5.1 setting beta_N＝interchange(π_new, k, j) (k, j epsilon N, k not equal to j), wherein beta_N is to exchange the kth workpiece and the jth workpiece of pi_new, pi_new is a new sub-subsequence, and N represents the number of workpieces to be processed;

S2.5.2, β_N set according to S2.5.1 and the permutation parity result pi_new and β_N satisfy the following equation:

Then

In the formula,Is the set of all even permutations in pi_N,Is a set of all odd permutations, i.e. if the child subsequence falls into the search space on the odd side of the search mark, the parity of pi_new can be repaired to the even side of the search area mark by only exchanging the positions of any two workpieces in pi_new;

s2.6, checking the neighbor solution of the individual obtained by substituting the S1 model with the S2.5 child solution sequence by using a simulated annealing program based on a pseudo-symmetrical breaking method, wherein the specific expression based on the pseudo-symmetrical breaking method is as follows:

η_N＝Insert(π_new,k,j)(k,j∈N,k≠j)

Where η_N is pi_new, where the kth workpiece is inserted into the jth workpiece, the relationship between k and j only needs to satisfy the following formula to ensure that the insertion operation does not affect the parity of the solution, where the specific expression is as follows:

η_N＝Insert(π_new,k,j),(k,j∈N,k≠j)∧(|k-j|mod2≠0)

Where mod represents the remainder of the remainder.

S2.7, updating the population according to a population updating mechanism based on distance and quality, so that the number of the pull-period work pieces of the solution generated in S2.6 is smaller than one solution with the largest number of the work pieces of the original pull-period work pieces in S1, adding the generated new solution into the population, otherwise, discarding the generated new solution, and skipping the step, wherein the specific steps are as follows:

S2.7.1, judging whether the target value of the child solution sequence of the population to be inserted is better than the worst solution in S1, namely, whether the situation of the stall in S1 occurs or not, if so, executing a step S2.7.2, otherwise, jumping to a step S2.7.4;

s2.7.2, judging whether the sequence of the child solution sequence to be inserted into the population is the same as any sequence in the population, wherein the calculation mode is as follows:

In the formula,Is the relative position of the ith workpiece of pi¹ in pi², if simi (pi¹,π²) noteq0, then executing step S2.7.3, otherwise jumping to step S2.7.4, pi¹ representing the sub-subsequence de-sequence after S2.6 is checked, pi² representing either sequence;

S2.7.3, replacing the child subsequence with the worst target value in the population with a child subsequence of S2.7.2;

s2.7.4, discarding the worst child solution sequence;

S2.8, judging whether a termination condition of the algorithm is reached, wherein the termination condition is that the algorithm runs for one hour, if so, executing the step S2.9, and if not, jumping to execute the step S2.4;

s2.9, outputting a solution found in the algorithm searching process, substituting the solution into the S1 model, and obtaining the solution with the best minimum effect;

s3, verifying the effectiveness of the method, wherein the method comprises the following steps:

In order to verify the effectiveness of the modular factor substitution group algorithm based on the substitution group theory, the algorithm is compared with three currently mainstream advanced algorithms VBIH, HDHHO and IGwS and a general mixed integer programming solver CPLEX aiming at different scale calculation examples;

The scale of the examples is 50, 300 and 700 respectively, each scale has 16 different examples, 48 examples are total, due to the limitation of memory and time, the solver CPLEX can only calculate a feasible solution (two examples can obtain an optimal solution) in 16 examples under 50 scales, and to ensure the fairness of comparison, all algorithms are independently and repeatedly operated for 20 times on each example, and the operation time 3600 seconds is used as the termination condition of all algorithms including the solver;

all algorithms adopt Intel E3-1220 v5 processor (3.0 GHz), 8GB memory, linux operating system and C++ programming environment, and different random number seeds are used for each iteration;

in order to verify the comprehensive quality of the approximate optimal solution finally obtained by the algorithm so as to evaluate the performance of the algorithm, three evaluation indexes are adopted, wherein the three evaluation indexes are respectively as follows:

1. Each algorithm was run with 20 independent iterations of the found historical BEST solution (BEST)

2. Average Value (AVG) of the found optimal solution was run in 20 independent iterations of each algorithm

3. Each algorithm was run in 20 independent iterations with Standard Deviation (SD) of the found optimal solution.

The beneficial effects of the invention are that

1. The invention discloses a method for optimizing the number of delayed workpieces in single-machine scheduling with release and deadline constraint by using a modular-cause substitution group algorithm, which particularly considers a special pseudo-symmetrical breaking method based on the substitution group theory so as to reduce the search space and the calculation workload of the proposed algorithm. Based on the symmetric group permutation parity of the original search space, a problem-specific pseudo-symmetric property in terms of target value is introduced. The algorithm then explores promising search areas within a reduced search space, relies on location-based crossover to generate meaningful child solutions, simulated annealing based on pseudo-symmetry breaking to check in depth for neighborhood solutions, and distance and quality based population update mechanisms to ensure healthy populations. Through experimental comparison, the method provided by the invention is excellent in all the examples with different scales, can provide higher-quality solutions for a decision maker in a shorter time, and provides important management guidance for actual production scheduling of enterprises.

2. Compared with the prior art, the method can obtain better solutions in reasonable time for practical industrial application, has stable algorithm performance, can treat large-scale problems, and has very remarkable help for practical application.

Drawings

FIG. 1 is an overall flow chart of an algorithm of the present invention;

FIG. 2 is a schematic view of the present invention based on position crossing;

FIG. 3 is a schematic diagram of the parity interchange scheme of the present invention;

FIG. 4 is a schematic diagram of an insertion operation of the present invention to ensure parity invariance.

Detailed Description

The following description of the embodiments of the present invention will be made clearly and completely with reference to the accompanying drawings, in which it is apparent that the embodiments described are only some embodiments of the present invention, but not all embodiments. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.

The invention provides a method for considering the number of the delayed workpieces in single machine scheduling with release and deadline constraint, which is shown in figure 1 and comprises the following steps:

S1, constructing a mathematical model considering a single machine scheduling problem with release and deadline constraints, and setting constraints on the model, wherein the specific expression is as follows:

s.t.

Where N represents the number of workpieces to be processed, pi represents the sequence of workpieces to be processed, pi_N represents the set of all possible sequences of workpieces, i e N,Respectively represents the release time, the processing time and the cut-off time of the workpiece pi_i,Indicating the finishing time of the workpiece pi_i,Indicating the completion time of the workpiece pi_i-1,Indicating whether the workpiece pi_i is in a pulling period, wherein the pulling period is 1, and the normal delivery is 0;

S2, constructing a modular factor replacement group algorithm based on a replacement group theory, and solving the scheduling problem in the step S1;

S2.1, reading the optimal sequence of the model in the step S1 as a sub-solution sequence;

s2.2, initializing an algorithm search area flag S_flag and letting S_flag =0 or 1, i.e. deciding that the algorithm searches on either the odd side or the even side in the parity search space, searching on the even side when S_flag =0, searching on the odd side when S_flag =1;

The permutation group theory specifically comprises a given symmetry group, wherein the symmetry group consists of two sets, all elements which are possibly permuted in the symmetry group can be divided into an odd part and an even part, each set consists of the order multiplication of each element on one side of the symmetry group, and the one-to-one mapping from one set to the other set is called the permutation group theory;

Based on the theory, the search space of the algorithm can be divided into two sequences with the same number;

S2.3, optimizing data generated by S1 in each population by using a local search algorithm according to the population on the same side obtained in the step S2.2, wherein the local search algorithm is an algorithm for solving the optimization problem;

S2.4, generating new offspring solutions by using a position-based crossing method, wherein as shown in FIG. 2, a plurality of genes are randomly selected in one parent solution with independent probability, the positions can be discontinuous, the genes at the positions of the parent 1 are copied to the same positions of the offspring 1, then the genes which are absent in the offspring 1 are filled in the blank positions of the offspring 1 according to the sequence of the parent 2 to obtain offspring 1, and the other offspring is obtained in the same manner after exchanging the parent identities;

s2.5, repairing the child solution sequence on the odd side of the search space in the new child solution sequence generated in S2.4 to the search space on the even side, wherein as shown in FIG. 3, two different genes are randomly selected in the child solution, the replacement parity of the solution can be changed after the positions of the two different genes are exchanged, and if the child solution sequence on the odd side is not found, the step is skipped, and the specific steps are as follows:

S2.5.1 setting beta_N＝interchange(π_new, k, j) (k, j epsilon N, k not equal to j), wherein beta_N is to exchange the kth workpiece and the jth workpiece of pi_new, pi_new is a new sub-subsequence, and N represents the number of workpieces to be processed;

S2.5.2, β_N set according to S2.5.1 and the permutation parity result pi_new and β_N satisfy the following equation:

Then

In the formula,Is the set of all even permutations in pi_N,Is a set of all odd permutations, i.e. if the child subsequence falls into the search space on the odd side of the search mark, the parity of pi_new can be repaired to the even side of the search area mark by only exchanging the positions of any two workpieces in pi_new;

S2.6, checking the neighbor solution of the individual obtained by substituting the S1 model with the S2.5 child solution sequence by using a simulated annealing program based on a pseudo-symmetrical fracture method, wherein the inserting operation is shown in the figure 4, selecting two genes with odd number of positions apart from each other from the child solution, inserting one gene into the other position, and not changing the replacement parity of the solution, wherein the specific expression based on the pseudo-symmetrical fracture method is as follows:

η_N＝Insert(π_new,k,j)(k,j∈N,k≠j)

Where η_N is pi_new, where the kth workpiece is inserted into the jth workpiece, the relationship between k and j only needs to satisfy the following formula to ensure that the insertion operation does not affect the parity of the solution, where the specific expression is as follows:

η_N＝Insert(π_new,k,j),(k,j∈N,k≠j)∧(k-j|mod2≠0)

Where mod represents the remainder of the remainder.

S2.7, updating the population according to a population updating mechanism based on distance and quality, so that the number of the pull-period work pieces of the solution generated in S2.6 is smaller than one solution with the largest number of the work pieces of the original pull-period work pieces in S1, adding the generated new solution into the population, otherwise, discarding the generated new solution, and skipping the step, wherein the specific steps are as follows:

S2.7.1, judging whether the target value of the child solution sequence of the population to be inserted is better than the worst solution in S1, namely, whether the situation of the stall in S1 occurs or not, if so, executing a step S2.7.2, otherwise, jumping to a step S2.7.4;

s2.7.2, judging whether the sequence of the child solution sequence to be inserted into the population is the same as any sequence in the population, wherein the calculation mode is as follows:

In the formula,Is the relative position of the ith workpiece of pi¹ in pi², if simi (pi¹,π²) noteq0, then executing step S2.7.3, otherwise jumping to step S2.7.4, pi¹ representing the sub-subsequence de-sequence after S2.6 is checked, pi² representing either sequence;

S2.7.3, replacing the child subsequence with the worst target value in the population with a child subsequence of S2.7.2;

S2.7.4, discard the worst child solution sequence.

S2.8, judging whether a termination condition of the algorithm is reached, wherein the termination condition is that the algorithm runs for one hour, if so, executing the step S2.9, and if not, jumping to execute the step S2.4;

s2.9, outputting a solution found in the algorithm searching process, substituting the solution into the S1 model, and obtaining the solution with the best minimum effect;

s3, verifying the effectiveness of the method, wherein the method comprises the following steps:

In order to verify the effectiveness of the modular factor substitution group algorithm based on the substitution group theory, the algorithm is compared with three currently mainstream advanced algorithms VBIH, HDHHO and IGwS and a general mixed integer programming solver CPLEX aiming at different scale calculation examples;

The scale of the examples is 50, 300 and 700 respectively, each scale has 16 different examples, 48 examples are total, due to the limitation of memory and time, the solver CPLEX can only calculate a feasible solution (two examples can obtain an optimal solution) in 16 examples under 50 scales, and to ensure the fairness of comparison, all algorithms are independently and repeatedly operated for 20 times on each example, and the operation time 3600 seconds is used as the termination condition of all algorithms including the solver;

all algorithms adopt Intel E3-1220 v5 processor (3.0 GHz), 8GB memory, linux operating system and C++ programming environment, and different random number seeds are used for each iteration;

in order to verify the comprehensive quality of the approximate optimal solution finally obtained by the algorithm so as to evaluate the performance of the algorithm, three evaluation indexes are adopted, wherein the three evaluation indexes are respectively as follows:

1. Each algorithm was run with 20 independent iterations of the found historical BEST solution (BEST)

2. Average Value (AVG) of the found optimal solution was run in 20 independent iterations of each algorithm

3. Each algorithm was run in 20 independent iterations with Standard Deviation (SD) of the found optimal solution;

Shown in table 1 are comparison results of CPLEX, VBIH, HDHHO, IGwS and MPGA (algorithm proposed by the present invention) at a scale of 50 workpieces, with the bold representing the optimum value for each example. It can be seen from table 1 that for all examples at this scale, the algorithm of the invention is better than the comparison algorithm at BEST, AVG and SD, and that for two examples where CPLEX obtained the optimal solution, the algorithm of the invention also obtained the optimal solution, and for examples where CPLEX obtained only the feasible solution, the algorithm of the invention reached even better than the feasible solution obtained by CPLEX.

Table 1CPLEX, VBIH, HDHHO, IGwS and MPGA results of the comparison of examples at 50 scale

In the table, the optimal solution is the rest of the solutions.

Table 2 shows the comparison results of the algorithm of the present invention and the comparison algorithm at the 300 scale, and from the results, it is apparent that the algorithm of the present invention has better stability than the comparison algorithm in that the best solution of 15 examples among the 16 examples at the scale is obtained by the algorithm of the present invention, and the difference between the result obtained by the algorithm of the present invention and the best solution obtained by the comparison algorithm is very small for the example where only one best solution is not obtained by the algorithm of the present invention.

Table 2VBIH, HDHHO, IGwS and MPGA results of example comparisons at 300 scale

Table 3 shows the comparison results of the algorithm of the present invention and the comparison algorithm at the 700 scale, from which it is apparent that all the best solutions of the 16 examples at the scale are obtained by the algorithm of the present invention, and the best solutions obtained by the present invention are significantly better than the best solutions obtained by the comparison algorithm from the best solution gaps obtained by the respective algorithms, and furthermore, from AVG and SD indexes, the algorithm of the present invention has very good stability compared to the comparison algorithm. This also demonstrates that the proposed algorithm has significant advantages in handling larger scale problems, which can significantly increase the efficiency of the scheduling decision maker in practical use and can provide a better solution in a shorter time.

Table 3VBIH, HDHHO, IGwS and MPGA results of example comparisons at 700 Scale

Although embodiments of the present invention have been shown and described, it will be understood by those skilled in the art that various changes, modifications, substitutions and alterations can be made therein without departing from the principles and spirit of the invention, the scope of which is defined in the appended claims and their equivalents.

Claims (4)

Translated fromChinese

1.一种考虑带释放和截止时间约束的单机调度中拖期工件数的优化方法，其特征在于：包括以下步骤：1. A method for optimizing the number of delayed workpieces in single-machine scheduling with release and deadline constraints, characterized in that it includes the following steps:S1、构建考虑带释放和截止时间约束的单机调度问题的数学模型，并对模型设置约束；S1. Construct a mathematical model for the single-machine scheduling problem with release and deadline constraints, and set constraints on the model;步骤S1所述的数学模型及对模型设置的约束的具体表达式如下所示：The specific expressions of the mathematical model and the constraints set on the model described in step S1 are as follows:s.t.s.t.式中，N表示待加工工件数量，π表示待加工的工件序列，*表示最优解，Π_N表示所有可能的工件序列集合，i∈N，分别表示工件π_i的释放时间，加工时间和截止时间，表示工件π_i的完工时间，表示工件π_i-1的完成时间，表示工件π_i是否拖期，拖期为1，正常交付为0；Where N represents the number of workpieces to be processed, π represents the sequence of workpieces to be processed, * represents the optimal solution, Π_N represents the set of all possible workpiece sequences, i∈N, They represent the release time, processing time and cut-off time of workpiece π_i, respectively. represents the completion time of workpiece π_i , represents the completion time of workpiece π_i-1 , Indicates whether the workpiece π_i is delayed, delayed is 1, and normal delivery is 0;S2、构建基于置换群理论的模因置换群算法对步骤S1中调度问题进行求解；S2, constructing a memetic permutation group algorithm based on permutation group theory to solve the scheduling problem in step S1;步骤S2具体包括以下步骤：Step S2 specifically includes the following steps:S2.1、读取步骤S1模型最优序列作为子代解序列；S2.1, read the optimal sequence of the model in step S1 as the descendant solution sequence;S2.2、初始化算法搜索区域标记S_flag并使S_flag＝0或1，即决定算法在奇偶搜索空间中的奇数侧或偶数侧任意一侧进行搜索，S_flag＝0时算法在偶数侧搜索，S_flag＝1时算法在奇数侧搜索；S2.2, initialize the algorithm search area mark S_flag and set S_flag = 0 or 1, that is, decide whether the algorithm searches on the odd side or the even side in the odd-even search space. When S_flag = 0, the algorithm searches on the even side, and when S_flag = 1, the algorithm searches on the odd side;S2.3、根据S2.2的得到的位于同一侧的种群，使用局部搜索算法对每个种群中S1生成的数据进行优化；S2.3, based on the populations on the same side obtained in S2.2, use the local search algorithm to optimize the data generated by S1 in each population;S2.4、对S2.3优化后的数据使用基于位置的交叉的方法，产生新的子代解序列；S2.4, using the position-based crossover method on the data optimized in S2.3 to generate a new offspring solution sequence;S2.5、将S2.4生成的新的子代解序列中位于搜索空间奇数侧的子代解序列修复至偶数侧的搜索空间，如没有位于奇数侧的子代解序列，则跳过该步骤；S2.5. Repair the sub-generation solution sequence on the odd side of the search space in the new sub-generation solution sequence generated in S2.4 to the search space on the even side. If there is no sub-generation solution sequence on the odd side, skip this step.S2.6、使用基于伪对称破缺方法的模拟退火程序，检查S2.5子代解序列代入S1模型求得的个体的邻域解；S2.6, using a simulated annealing procedure based on the pseudo-symmetry breaking method, check the neighborhood solutions of the individuals obtained by substituting the offspring solution sequence of S2.5 into the S1 model;S2.7、根据基于距离和质量的种群更新机制来更新种群，使得S2.6生成的解的拖期工件数少于S1中原始拖期工件数最多的一个解，则将生成的新解加入种群，否则丢弃生成的新解，跳过该步骤；S2.7, update the population according to the population update mechanism based on distance and quality, so that the number of delayed workpieces of the solution generated by S2.6 is less than the solution with the largest number of delayed workpieces in S1, then add the generated new solution to the population, otherwise discard the generated new solution and skip this step;S2.8、判断是否达到算法的终止条件，所述终止条件即算法运行时间一小时，若达到则执行步骤S2.9，若未达到则跳转执行步骤S2.4；S2.8, determine whether the termination condition of the algorithm is met, the termination condition is that the algorithm runs for one hour, if it is met, execute step S2.9, if not, jump to step S2.4;S2.9、输出算法搜索过程中找到的解，将解代入S1模型，得到的解最小效果最好；S2.9, output the solution found during the algorithm search process, substitute the solution into the S1 model, and the solution obtained is the smallest and has the best effect;S3、验证方法的有效性。S3. Verify the effectiveness of the method.2.根据权利要求1所述的一种考虑带释放和截止时间约束的单机调度中拖期工件数的优化方法，其特征在于：所述步骤S2.5具体步骤如下：2. According to the method for optimizing the number of delayed workpieces in single-machine scheduling with release and deadline constraints in claim 1, it is characterized in that: the specific steps of step S2.5 are as follows:S2.5.1、设置β_N＝interchange(π_new,k,j)(k,j∈N,k≠j)，所述β_N是将π_new的第k个工件和第j个工件进行互换操作，π_new是新的子代解序列，N表示待加工工件数量；S2.5.1. Set β_N =interchange(π_new ,k,j)(k,j∈N,k≠j), where β_N is the operation of interchanging the k-th workpiece and the j-th workpiece of π_new , π_new is the new sub-generation solution sequence, and N represents the number of workpieces to be processed;S2.5.2、根据S2.5.1设置的β_N和置换奇偶性得到π_new和β_N之间的关系满足下式：S2.5.2. According to the β_N and permutation parity set in S2.5.1, the relationship between π_new and β_N satisfies the following equation:式中，是Π_N中所有偶数置换的集合，是所有奇数置换的集合，即如果子代解序列落到了搜索标记奇数侧的搜索空间，只需将π_new中任意两个工件的位置进行互换，即可将π_new的奇偶性修复至搜索区域标记的偶数侧。In the formula, is the set of all even permutations in Π_N , is the set of all odd permutations, that is, if the descendant solution sequence falls into the search space on the odd side of the search mark, the parity of π_new can be repaired to the even side of the search area mark by simply swapping the positions of any two artifacts in π_new .3.根据权利要求1所述的一种考虑带释放和截止时间约束的单机调度中拖期工件数的优化方法，其特征在于：步骤S2.6中，所述基于伪对称破缺方法的具体表达式如下：3. The optimization method for the number of delayed workpieces in single-machine scheduling with release and deadline constraints according to claim 1 is characterized in that: in step S2.6, the specific expression based on the pseudo-symmetry breaking method is as follows:η_N＝Insert(π_new,k,j)(k,j∈N,k≠j)η_N =Insert(π_new ,k,j)(k,j∈N,k≠j)式中，η_N是π_new将第k个工件插入第j个工件的位置得到，则k和j的关系仅需满足下式即可保证插入操作不会影响解的奇偶性，具体表达式如下所示：Where η_N is π_new , which is obtained by inserting the kth workpiece into the position of the jth workpiece. The relationship between k and j only needs to satisfy the following equation to ensure that the insertion operation does not affect the parity of the solution. The specific expression is as follows:η_N＝Insert(π_new,k,j),(k,j∈N,k≠j)∧(|k-j|mod2≠0)η_N =Insert(π_new ,k,j),(k,j∈N,k≠j)∧(|kj|mod2≠0)式中，mod表示取余数。In the formula, mod means the remainder.4.根据权利要求1所述的一种考虑带释放和截止时间约束的单机调度中拖期工件数的优化方法，其特征在于：步骤S2.7中所述基于距离和质量的种群更新机制规则具体如下：4. According to the method for optimizing the number of delayed workpieces in single-machine scheduling with release and deadline constraints in claim 1, it is characterized in that: the population update mechanism rules based on distance and quality in step S2.7 are specifically as follows:S2.7.1、判断即将插入种群的子代解序列的目标值是否优于S1中的最差解，也就是S1中是否出现拖期的情况，如果优于，则执行步骤S2.7.2，否则跳转步骤S2.7.4；S2.7.1. Determine whether the target value of the offspring solution sequence to be inserted into the population is better than the worst solution in S1, that is, whether there is a delay in S1. If so, execute step S2.7.2; otherwise, jump to step S2.7.4.S2.7.2、判断即将插入种群的子代解序列的序列是否与种群中任一序列相同，计算方式为：S2.7.2. Determine whether the sequence of the offspring solution sequence to be inserted into the population is the same as any sequence in the population. The calculation method is:式中，是π¹的第i个工件在π²中的相对位置，如果simi(π¹,π²)≠0,则执行步骤S2.7.3，否则跳转步骤S2.7.4，π¹表示S2.6经过检查后的子代解序列序列，π²表示任一序列；In the formula, is the relative position of the ith workpiece of π¹ in π^2. If simi(π¹ ,π² )≠0, execute step S2.7.3, otherwise jump to step S2.7.4. π¹ represents the sequence of child solutions after checking in S2.6, and π² represents any sequence;S2.7.3、将种群中目标值最差的子代解序列替换为S2.7.2的子代解序列；S2.7.3, replace the offspring solution sequence with the worst target value in the population with the offspring solution sequence of S2.7.2;S2.7.4、舍弃最差的子代解序列。S2.7.4. Discard the worst descendant solution sequence.