CN105809344A - Hyper-heuristic algorithm based ZDT flow shop job scheduling method - Google Patents

Abstract

The invention discloses a job scheduling method for a zero-idle flow shop based on a hyperheuristic algorithm. The method first sets the objective function of the job scheduling problem of a zero-idle flow shop, and establishes a corresponding scheduling optimization model. On this basis, combined with a super The heuristic algorithm framework uses the widely used harmony search algorithm as the HLH strategy of the super-heuristic algorithm, and designs simple heuristic rules for the characteristics of the job scheduling problem in the zero-idle flow shop to build the LLH method set, so as to realize the Optimal solution to job scheduling problem in zero-idle flow shop. This method not only retains the good global optimization performance of the meta-heuristic algorithm, but also avoids the uncertainty caused by adjusting the algorithm parameters based on manual experience in the meta-heuristic algorithm, which can effectively improve the efficiency of algorithm design. The improvement is also significant.

Description

A Job Scheduling Method for Zero Idle Flow Shop Based on Hyperheuristic Algorithm

technical field

The invention belongs to the technical field of workshop job scheduling, and in particular relates to a zero-idle flow workshop job scheduling method based on a super-heuristic algorithm.

Background technique

As an important branch of production scheduling, Flow-shop Scheduling Problem (FSP) is an NP-hard complex combinatorial optimization problem in essence. The zero-idle flow shop job scheduling problem is a further extension of FSP, which requires that the machine does not idle during the production process, that is, no idle time is allowed between adjacent workpieces processed on the machine. For example, in the manufacturing process of glass fiber, the heating furnace needs to maintain a constant high temperature of 2800℉ in a production cycle. Due to the large amount of thermal inertia in the furnace, it takes several days to stop and start, and it takes a lot of time to use the equipment. Therefore, once it is running, it is not expected to have idle time; and for example, in the integrated circuit production process using photolithography, the stepper used is an expensive device, and it is hoped that there will be zero idle time during operation. The zero-idle flow shop scheduling problem generally exists in the production process of textile, chemical, metallurgical and other process industries, and has a wide range of engineering application backgrounds. At present, the research on the solution method of the zero-idle flow shop scheduling problem is mainly divided into three categories:

(1) Accurate algorithms, such as branch and bound method, mixed integer programming, etc. When such algorithms are used to solve NFSP, they are mainly used to solve small-scale problem instances;

(2) Heuristic algorithms, such as NEH method, Johnson heuristic rules, KK method, etc. The implementation of this type of algorithm is relatively simple, but the quality of the scheduling solution obtained is not high, and it is often difficult to obtain the optimal solution;

(3) Meta-heuristic algorithms, such as discrete particle swarm optimization algorithm, harmony search algorithm, differential evolution algorithm, artificial bee colony algorithm, firefly algorithm, and distribution estimation algorithm. Due to its good global optimization performance, meta-heuristic algorithms are widely used in It has been widely used in production scheduling optimization.

Among the above three types of algorithms, the metaheuristic algorithm is the most widely used, but this type of algorithm requires the designer to have sufficient professional background knowledge, design a specific algorithm for a specific problem (instance), and evaluate it through a set of test examples . In fact, this approach has shortcomings. Due to the large differences in problem definitions, constraints and optimization objectives under different scheduling indicators, a single meta-heuristic algorithm cannot guarantee that it is always optimal on all problems (instances). in other algorithms.

Hyperheuristic algorithm is a newly emerged conceptual model for solving complex and diverse optimization problems, and has become one of the research hotspots in the field of computational intelligence technology. Hyper-heuristic algorithms manage and manipulate a series of low-level heuristics (Low Level Heuristics, LLH) methods through a high-level heuristic (HighLevelHeuristic, HLH) strategy to generate optimal heuristic algorithms for solving different problems (instances). The HLH strategy searches the solution space of the problem domain indirectly through the LLH method. Since the domain shielding is realized between the heuristic domain and the problem domain, by modifying the LLH method, objective function and other information of the problem domain, the hyperheuristic algorithm can be easily Transplant to a different problem model. Therefore, the present invention uses the hyperheuristic algorithm to solve the zero-idle flow shop job scheduling problem.

Contents of the invention

The purpose of the present invention is to address the deficiencies in the prior art, and propose a zero-idle assembly line job scheduling method based on a hyperheuristic algorithm. The method first sets the objective function of the zero-idle assembly line job scheduling problem, and establishes a corresponding Scheduling optimization model, on this basis, combined with the framework of the hyper-heuristic algorithm, a widely used meta-heuristic algorithm—Harmony Search (HS) algorithm is used as the HLH strategy of the hyper-heuristic algorithm, and for zero idle Based on the characteristics of the job scheduling problem of the flow shop, a simple heuristic rule is designed to construct the LLH method set, so as to realize the optimal solution to the job scheduling problem of the zero-idle flow shop.

The method that the present invention solves the problems of the technologies described above takes, and the steps are as follows:

(1) Set the objective function fit(·) of the job scheduling optimization problem in the zero-idle flow shop;

(2) Initialize the HS algorithm parameters, the HS algorithm parameters include: harmony memory capacity (HMS), memory value probability (HMCR), pitch adjustment probability (PAR), pitch adjustment range (bw), individual length ( L) and the number of iterations (T);

(3) Design heuristic rules by using job exchange, insertion and flipping operations, construct a set of LLH methods for job scheduling problems in a zero-idle flow shop, and number the LLH methods;

(4) Initialize the group and generate a harmony memory bank, each individual in the harmony memory bank corresponds to the numbering sequence of the LLH method k∈[1,HMS], x ^k ∈ R ^L , R ^L is the L-dimensional real number space;

(5) Randomly generate the scheduling candidate solution π ^k =Permuting(J) corresponding to each individual in the harmony memory bank, where J={J ₁ ,J ₂ ,...,J _n }, which is the set of jobs to be performed, Permuting(· ) is a random random order operation;

(6) Calculate the fitness value fit(x ^k ) of all individuals in the harmony memory bank, the specific method is as follows:

(a) For an individual x ^k in the harmony memory bank, set i=1;

(b) will A LLH method is applied to the corresponding scheduling candidate solution π ^k to obtain a new scheduling candidate solution

(c) Calculate π ^k and The fitness value fit(π ^k ) and like but Otherwise, keep the scheduling candidate solution π ^k unchanged;

(d) Make i=i+1, judge whether i≤L is established, if established, go to (b) to continue execution, otherwise go to (e) execution;

(e) will The scheduling candidate solution π ^k and its fitness value fit(π ^k ) obtained by the LLH method are used as the final fitness value of the individual x ^k , that is, fit(x ^k )=fit(π ^k );

(7) Generate a new individual x′={x′ ₁ ,x′ ₂ ,…,x′ _L }, the specific steps are as follows:

(a) First generate two random numbers, namely random numbers r ₁ and r ₂ uniformly distributed on [0,1];

(b) Randomly select an individual x ^j from the harmony memory bank;

(c) Obtain the value x′ _i of the i-th dimension of a new individual, i=1,2,…,L, the calculation rule is: if r ₁ <HMCR and r ₂ ≥PAR, then If r ₁ <HMCR and r ₂ <PAR, then If r ₁ ≥ HMCR, then x′ _i =Rnd(Lb(x′ _i ),Ub(x′ _i )), where Rnd(a,b) means generating a random number in the range from a to b, and Lb(x′ _i ) and Ub(x′ _i ) respectively represent the minimum and maximum values on the i-th dimension in the harmony memory;

(d) Regularization processing, because the value x′ _i of the new individual x′={x′ ₁ ,x′ ₂ ,…,x′ _L } obtained in (c) may exceed the feasible solution Therefore, the following formula is used for normalization, where [·] is the rounding operation:

${\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>& {\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; L</span>}<span\; class="notranslate">\; ,</span>& {\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; ></span>\mathrm{<span\; class="notranslate">\; L</span>}\\ <span\; class="notranslate">\; \&lsqb;</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; e</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}\mathrm{<span\; class="notranslate">\; e</span>}\end{array}\right.<span\; class="notranslate">\; ;</span>$

(8) Update the harmony memory bank. If the fitness value fit(x′) of the new individual obtained in step (7) is better than the fitness value fit(x ^j ) of the individual x ^j in the harmony memory, then use the new individual x′ and its corresponding scheduling The candidate solution replaces the individual with the worst fitness in the library and its scheduling candidate solution;

(9) Check whether the current number of iterations has reached T times. If not, go back to step (7), otherwise sort the better candidate solutions in the current harmony memory according to the fitness value, and save the individual x _best with the best fitness and its corresponding scheduling candidate solution π _best ;

(10) Output the Gantt chart corresponding to the scheduling candidate solution π _best , so as to complete the optimal solution to the zero-idle flow shop job scheduling problem.

Compared with the prior art, the present invention has the following advantages:

In the zero-idle pipeline job scheduling problem, there are large differences in the parameters of the solution individual expression, constraint conditions, and optimization objectives under different scheduling indicators, which makes it difficult for the meta-heuristic algorithm to maintain high performance in various scheduling optimization problems. The present invention adopts the super-heuristic algorithm to realize the job scheduling optimization of the zero-idle flow shop, and uses the widely used HS algorithm as the HLH strategy under the super-heuristic framework to manipulate a series of simple LLH methods to indirectly realize the target problem. The solution not only retains the good global optimization performance of the meta-heuristic algorithm, but also avoids the uncertainty caused by adjusting the algorithm parameters based on manual experience in the meta-heuristic algorithm. Once the algorithm parameters of the HLH strategy in the present invention are determined and do not need to be adjusted, the corresponding LLH method and objective function only need to be simply modified according to different scheduling optimization objectives, so it can also be easily transplanted to other problem instances containing different scheduling objectives, and can Effectively improve the efficiency of algorithm design. In addition, the core idea of the super-heuristic algorithm proposed by the present invention is to effectively organize the LLH method set to generate the optimal heuristic method for solving the zero-idle flow shop job scheduling problem, and these LLH method sets are all determined by simple heuristic rules. Composition, the algorithm complexity is low, so it is also of great significance to improve the efficiency of pipeline job scheduling.

Description of drawings

Figure 1 is a description of the processing time in the zero-idle flow shop operation;

Figure 2 is the overall flow chart of job scheduling in zero-idle flow shop based on hyperheuristic algorithm;

Fig. 3 is a schematic diagram of LLH method operation;

Fig. 4 is a schematic diagram of the harmony memory bank and its corresponding scheduling candidate solutions in the harmony search algorithm.

detailed description

In order to better understand the technical solutions and features of the present invention, the implementation of the present invention will be further described below in conjunction with the accompanying drawings.

First, it is necessary to set the objective function fit( ) of the job scheduling optimization problem in a zero-idle flow shop. Since the optimization objectives under different scheduling indicators are different, this embodiment takes the common minimum completion time (Makespan) as an example to illustrate . Given scheduling solution π={J ₁ ,J ₂ ,…,J _n }, where J ₁ ,J ₂ ,…,J _n are n workpieces to be operated, which need to pass through m machines in the zero-idle pipeline operation in turn , that is, no idle time is allowed between adjacent workpieces processed on the machine. Set the processing time, start time and completion time of workpiece J _i (i=1,2,…,n) on machine j (j=1,2,…,m) as P _i,j , S _{i, j} and C _i,j . Figure 1 shows a schematic diagram of the possible processing flow of workpiece J _i on machine j. The completion time of the zero-idle flow shop job scheduling problem can be calculated as follows:

In Fig. 1(a), the processing start time S _{i ,j} of workpiece Ji is its completion time C _i,j-1 on the previous machine, while the machine under the zero-idle constraint requires two adjacent The workpiece operation time interval Γ _j =0, in this case, it will affect the subsequent processing time. In Fig. 1(b), S _i,j is the completion time C _i-1,j of the previous job J _i-1 on the current machine, and Γ _j =0 always exists. For the first machine in assembly line production, since it does not have the influence of the previous machine, Γ ₁ =0, we can get:

C _1,1 = S _1,1 +P _1,1 (1)

C _i,1 ＝C _i-1,1 +P _i,1 (2)

where S _1,1 =0. In addition, the start time S _1,1 of the first job J ₁ on each machine is the completion time C _1,j-1 of the job on the previous machine, so S _1,j = C _{1 ,j-1} , at the same time, it can also be calculated that the completion time of J ₁ processed by each machine is:

C _1,j =S _1,j +P _1,j (3)

It can be seen from Figure 1(a) that if there is a zero-idle constraint on the current machine, the processing start time of J _i-1 on machine j needs to be delayed by Γ _j to meet the constraint condition. Therefore, considering the situation in Figure 1, when the processing flow encounters machine j, the delayed time Γ _j = max{C _i,j-1 -C _i-1,j ,0} will cause all subsequent processes to All processing operations are delayed, and the total delay time can be calculated by formula (4).

Γ _j ＝Γ _j-1 +max{C _i,j-1 -(C _i-1,j +Γ _j-1 ),0}(4)

Thus, the start time and completion time of each machine j can be obtained as shown in equations (5) and (6) respectively.

S _i,j ＝max{C _i-1,j +Γ _j ,C _i,j-1 }(5)

C _i,j =S _i,j +P _i,j (6)

Therefore, the completion time corresponding to the scheduling solution π can be obtained as:

C _max (π) = C _n,m (7)

The objective function of the zero-idle flow shop scheduling problem can be expressed as follows:

fit(π)＝ _Cmax (π)(8)

The overall process of solving the above objective function zero-idle assembly line job scheduling problem is shown in Figure 2. The specific implementation steps are:

Step (1) Initialize the HS algorithm parameters. Initialize harmony memory capacity (HMS), memory value probability (HMCR), pitch adjustment probability (PAR), pitch adjustment range (bw), individual length (L) and number of iterations (T);

Step (2) Design the LLH method set by swapping, inserting and flipping operations, as shown in Figure 3, the specific method is as follows:

(a) Job exchange: randomly select two jobs J _a and J _b of scheduling candidate solutions, and exchange corresponding positions;

(b) Job insertion 1: Randomly select two jobs J _a and J _b of scheduling candidate solutions, and insert J _b after J _a ;

(c) Job insertion 2: randomly select two jobs J _a and J _b of scheduling candidate solutions, and insert J _a after J _b ;

(d) Job flipping: flip all jobs {J ₁ ,J ₂ ,…,J _n } to get {J _n ,…,J ₂ ,J ₁ };

The above method is used to construct the LLH method set for the job scheduling problem of the zero-idle flow shop, and the numbers are sequentially numbered in the above order, that is, 1: job exchange, 2: job insertion 1, 3: job insertion 2, 4: job reversal;

Step (3) Initialize the group, that is, generate a harmony memory bank. Each individual in the harmony memory library corresponds to the numbering sequence of the LLH method k∈[1,HMS], x ^k ∈ R ^L , its generation method is as follows:

${\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; R</span>}\mathrm{<span\; class="notranslate">\; no</span>}\mathrm{<span\; class="notranslate">\; d</span>}\mathrm{<span\; class="notranslate">\; no</span>}\mathrm{<span\; class="notranslate">\; \%</span>}\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&Element;</span><span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; L</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 9</span>}<span\; class="notranslate">\; )</span>$

Wherein Rndn is a generated random positive integer, and % represents a modulo operation;

Step (4) Randomly generate the scheduling candidate solution π ^k =Permuting(J) corresponding to each individual in the harmony memory bank, where J={J ₁ ,J ₂ ,...,J _n }, and Permuting(·) is the random Random order operations, the final generated initialization harmony memory and corresponding scheduling candidate solutions are shown in Figure 4;

Step (5) Calculate the fitness value fit(x ^k ) of all individuals in the harmony memory bank, the specific method is as follows:

(a) For an individual x ^k in the harmony memory bank, set i=1;

(b) will A LLH method is applied to the corresponding scheduling candidate solution π ^k to obtain a new scheduling candidate solution

(c) Use formula (6) to calculate π ^k and The fitness value fit(π ^k ) and like but Otherwise, keep the scheduling candidate solution π ^k unchanged;

(d) Make i=i+1, judge whether i≤L is established, if established, go to (b) to continue execution, otherwise go to (e) execution;

(e) will The scheduling candidate solution π ^k and its fitness value fit(π ^k ) obtained by the LLH method are used as the final fitness value of the individual x ^k , that is, fit(x ^k )=fit(π ^k );

Step (6) Generate a new individual x′={x′ ₁ ,x′ ₂ ,…,x′ _L }, the specific steps are as follows:

(a) First generate two random numbers, namely random numbers r ₁ and r ₂ uniformly distributed on [0,1];

(b) Randomly select an individual x ^j from the harmony memory bank;

(c) Obtain the value x′ _i of the i-th dimension of a new individual, i=1,2,…,L, the calculation rule is: if r ₁ <HMCR and r ₂ ≥PAR, then If r ₁ <HMCR and r ₂ <PAR, then If r ₁ ≥ HMCR, then x′ _i =Rnd(Lb(x′ _i ),Ub(x′ _i )), where Rnd(a,b) means generating a random number in the range from a to b, and Lb(x′ _i ) and Ub(x′ _i ) respectively represent the minimum and maximum values on the i-th dimension in the harmony memory;

(d) Regularization processing, because the value x′ _i of the new individual x′={x′ ₁ ,x′ ₂ ,…,x′ _L } obtained in (c) may exceed the feasible solution range, so formula (10) is used for regularization processing, where [ ] is rounding operation;

${\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>& {\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; L</span>}<span\; class="notranslate">\; ,</span>& {\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; ></span>\mathrm{<span\; class="notranslate">\; L</span>}\\ <span\; class="notranslate">\; \&lsqb;</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; e</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}\mathrm{<span\; class="notranslate">\; e</span>}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 10</span>}<span\; class="notranslate">\; )</span>$

Step (7) updating the harmony memory. If the fitness value fit(x′) of the new individual obtained in step (7) is better than the fitness value fit(x ^j ) of the individual x ^j in the harmony library, then use the new individual x′ and its corresponding scheduling candidate The individual with the worst fitness in the solution substitution library and its scheduling candidate solution;

Step (8) Check whether the current number of iterations has reached T times. If not, go back to step (7), otherwise sort the better candidate solutions in the current harmony memory according to the fitness value, and save the individual x _best with the best fitness and its corresponding scheduling candidate solution π _best ;

Step (9) outputs the Gantt chart corresponding to the scheduling candidate solution π _best . In this way, the solution to the job scheduling problem of the zero-idle flow shop is completed.

Claims (2)

1. A zero-idle flow shop job scheduling method based on super-heuristic algorithm, is characterized in that, comprises the following steps: Step (1) Set the objective function fit(·) of the job scheduling optimization problem in the zero-idle flow shop; Step (2) Initialize the HS algorithm parameters; the parameters include: harmony memory capacity HMS, memory value probability HMCR, pitch adjustment probability PAR, pitch adjustment range bw, individual length L and iteration number T; Step (3) Design heuristic rules by using job exchange, insertion and flipping operations to construct a set of LLH methods for job scheduling problems in a zero-idle flow shop, and number the LLH methods; Step (4) initialize the population and generate harmony Memory bank; each individual in the harmony memory bank corresponds to the numbering sequence of the LLH method k ∈ [1, HMS], x ^k ∈ R ^L ; Step (5) Randomly generate the scheduling candidate solution π ^k =Permuting(J) corresponding to each individual in the harmony memory bank, where J={J ₁ ,J ₂ ,...,J _n } is the set of jobs to be performed, and Permuting( ) is a random random operation; Step (6) Calculate the fitness value fit(x ^k ) of all individuals in the harmony memory bank, the specific method is as follows: (a) For an individual x ^k in the harmony memory bank, set i=1; (b) will A LLH method is applied to the corresponding scheduling candidate solution π ^k to obtain a new scheduling candidate solution (c) Calculate π ^k and The fitness value fit(π ^k ) and like but Otherwise, keep the scheduling candidate solution π ^k unchanged; (d) Make i=i+1, judge whether i≤L is established, if established, go to (b) to continue execution, otherwise go to (e) execution; (e) will The scheduling candidate solution π ^k and its fitness value fit(π ^k ) obtained by the LLH method are used as the final fitness value of the individual x ^k , that is, fit(x ^k )=fit(π ^k ); Step (7) Generate a new individual x′={x′ ₁ ,x′ ₂ ,…,x′ _L }, the specific steps are as follows: (a) First generate two random numbers, namely random numbers r ₁ and r ₂ uniformly distributed on [0,1]; (b) Randomly select an individual x ^j from the harmony memory bank; (c) Obtain the value x′ _i of a new individual on the i-th dimension, i=1,2,…,L, and its calculation rule is: if r ₁ <HMCR and r ₂ ≥PAR, then If r ₁ <HMCR and r ₂ <PAR, then If r ₁ ≥ HMCR, then x′ _i =Rnd(Lb(x' _i ),Ub(x' _i )), where Rnd(a,b) means generating a random number in the range from a to b, and Lb(x' _i ) and Ub(x′ _i ) respectively represent the minimum and maximum values on the i-th dimension in the harmony memory; (d) Regularization processing, because the value x′ _i of the new individual x′={x ₁ ′,x′ ₂ ,…,x′ _L } obtained in (c) may exceed the feasible solution Therefore, the following formula is used for normalization processing, where [·] is the rounding operation. ${\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>& {\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 1</span>}\\ \mathrm{<span\; class="notranslate">\; L</span>}<span\; class="notranslate">\; ,</span>& {\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; ></span>\mathrm{<span\; class="notranslate">\; L</span>}\\ <span\; class="notranslate">\; \&lsqb;</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; e</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}\mathrm{<span\; class="notranslate">\; e</span>}\end{array}\right.$ Step (8) update the harmony memory; if the new individual fitness value fit(x′) obtained in step (7) is better than the fitness value fit(x ^j ) of the individual x ^j in the harmony memory, then Replace the individual with the worst fitness and its scheduling candidate solution in the library with the new individual x' and its corresponding scheduling candidate solution; Step (9) Check whether the current number of iterations has reached T times; if not, return to step (7), otherwise, sort the better candidate solutions in the current harmony memory according to the fitness value, and save the best fitness The optimal individual x _best and its corresponding scheduling candidate solution π _best ; Step (10) outputs the Gantt chart corresponding to the scheduling candidate solution π _best , thereby completing the optimal solution to the zero-idle assembly line job scheduling problem. 2. the zero-idle assembly line job scheduling method based on super-heuristic algorithm according to claim 1, is characterized in that, described step (3) adopts job exchange, insertion and flip operation design heuristic rule, in order to construct A collection of LLH methods for the job scheduling problem of zero-idle flow shop, the specific methods are as follows: (a) Job exchange: randomly select two jobs J _a and J _b of scheduling candidate solutions, and exchange corresponding positions; (b) Job insertion 1: Randomly select two jobs J _a and J _b of scheduling candidate solutions, and insert J _b after J _a ; (c) Job insertion 2: randomly select two jobs J _a and J _b of scheduling candidate solutions, and insert J _a after J _b ; (d) Job flipping: flip all jobs {J ₁ ,J ₂ ,…,J _n } to get {J _n ,…,J ₂ ,J ₁ }; The above method is used to construct the LLH method set for the job scheduling problem of the zero-idle flow shop, and numbered in sequence according to the above order, that is, 1: job exchange, 2: job insertion 1, 3: job insertion 2, 4: job reversal.