FLEXIBLE JOB-SHOP SCHEDULING METHOD BASED ON LIMITED STABLE MATCHING STRATEGY

Abstract

The present invention provides a flexible job-shop scheduling method based on a limited stable matching strategy, and belongs to the field of job-shop scheduling. The method adopts the following design solution: a. generating an initial chromosome population through integer coding and initializing relevant parameters; b. conducting crossover and mutation operations on parent chromosomes to obtain progeny chromosomes; c. combining the progeny chromosomes and the parent chromosomes into a set of to-be-selected chromosomes, and selecting a next generation of chromosomes from the set through limited stable matching operation; and d. stopping the algorithm if meeting cut-off conditions; otherwise turning to step b. The present invention introduces a limited stable matching strategy into the selection process of the progeny chromosomes to solve a multi-target flexible job-shop scheduling problem, so as to overcome the defects of insufficient population distribution and insufficient convergence in the existing method for solving the multi-target flexible job-shop scheduling problem when solving such problem, thereby obtaining excellent scheduling solution with good timeliness and high reliability.

Claims

1. A flexible job-shop scheduling method based on a limited stable matching strategy, comprising the following steps: (a) initializing related parameters: obtaining an initial chromosome population meeting constraint conditions through integer coding according to specific contents of a production order; determining a neighborhood of each subproblem; and calculating a fitness value; (b) selecting a parent chromosome from the neighborhood of each subproblem; generating progeny chromosomes through simulated binary crossover and polynomial mutation; and calculating a fitness value; (c) selecting progeny populations: (c1) combining a set of generated progeny chromosomes and a set of original parent chromosomes into a set S={s.sub.1, s.sub.2, . . . , s.sub.2N} of to-be-selected chromosomes, and mapping the set to a target space to obtain a set X={x.sub.1, x.sub.2, . . . , x.sub.2N} of to-be-selected solutions, a subproblem set P={p.sub.1, . . . , p.sub.t, . . . , p.sub.N} and a weight vector set w={.sub.1, . . . , .sub.t, . . . , .sub.N}, wherein N is the number of the chromosomes; (c2) selecting the angle of the solution relative to the subproblem as position information ; (c3) constructing an adaptive transfer function, and using the position information to obtain limit information; (c4) obtaining preference values through a preference value calculation formula of the subproblem with limit information for the solutions; arranging the preference values in an ascending order to obtain a preference sequence of the subproblem for all solutions; and conducting the same operation for all the subproblems to obtain a preference matrix .sub.p; (c5) obtaining the preference values through the preference value calculation formula of the solutions for the subproblems; arranging the preference values in an ascending order to obtain a preference sequence of the solutions for all the subproblems; and conducting the same operation for all the subproblems to obtain a preference matrix .sub.x; (c6) using the information of the preference matrices .sub.p and .sub.x as input, and delaying an acceptance procedure to obtain a stable matching relationship of the subproblems and the solutions, thereby selecting progeny solutions and also selecting chromosomes corresponding to the progeny solutions; and (d) outputting a population Pareto solution set when meeting cut-off conditions; selecting a chromosome by a decision maker from the Pareto solution set according to practical needs; decoding the chromosome to form a feasible scheduling solution; otherwise, returning to step (b).

2. The flexible job-shop scheduling method according to claim 1, wherein the acquisition process of the position information in the step (c2) is as follows: firstly, converting an m-dimensional target space F(x)=[f.sub.1(x), . . . f.sub.l(x), . . . f.sub.m(x)]R.sup.m into C.sub.m.sup.2 two-dimensional spaces F.sub.c(x)=[f.sub.u(x), f.sub.v(x)], wherein c is a number of the two-dimensional spaces, c=1, 2, . . . C.sub.m.sup.2; u and v are numbers of space dimensionality, u, v [1, 2, . . . , m]; f.sub.u(x) and f.sub.v(x) respectively indicate target values of the solution x X in the two-dimensional spaces; then determining a component .sub.uv=(.sub.u, .sub.v) of the weight vector w corresponding to the subproblem p P; and finally, calculating an angle component .sub.uv(x, p) of the position information : .sub.uv(x, p)=arc tan(|f.sub.u(x).sub.u|/|f.sub.v(x).sub.v|), wherein .sub.uv(x, p)[0, /2], is an algebraic sum of C.sub.m.sup.2 angle components of the solutions and the subproblems.

3. The flexible job-shop scheduling method according to claim 1, wherein the limit information in the step (c3) is obtained through the position information and the transfer function, and the transfer function is shown in formula (1): $\begin{array}{cc}{T}_L\left(\right)=\frac{1}{1+e^{-9.Math.\left(/-1\right)/L}};& \left(1\right)\end{array}$ wherein L is a control parameter, and the larger the L is, the more uniform the transfer function is; in order to solve the problem of overconvergence in the early stage of iteration and ensure the balance of convergence and diversity in the later stage of iteration, with the iteration of the algorithm, L setting is gradually increased from 1 to 20.

4. The flexible job-shop scheduling method based on the limited stable matching strategy according to claim 1, wherein in the step (c4), calculation steps of the preference matrix .sub.p of the subproblems for the solutions comprise: calculating the preference value p of the subproblem p for the solution x through formula (2) to obtain preference values of the subproblem p for 2N solutions; arranging the preference values in an ascending order to obtain a preference sequence of one subproblem for the solutions; using the preference sequence as a row of the preference matrix .sub.p; and calculating the preference sequences of all the subproblems for the solutions through the same method to obtain a preference matrix .sub.p of the subproblems with the limit information for the solutions, and thus .sub.p being N2N matrix, $\begin{array}{cc}.Math..Math.p\left(p,x,\right)=g^{\mathrm{tch}}\left(x,z^{*}\right).Math.T_L\left(\right)=\frac{\underset{1lm}{\max }.Math.\left\{.Math.f_l\left(x\right)-z_l^{*}.Math./{}_l\right\}}{1+e^{-9.Math.\left(/-1\right)/L}}& \left(2\right)\end{array}$ wherein is a weight vector of the subproblem p and z* is a reference point, wherein $z_l^{*}=\underset{xX}{\min }.Math.f_l\left(x\right),l=1,2,\mathrm{.Math.}.Math.,m.$

5. The flexible job-shop scheduling method according to claim 3, wherein in the step (c4), calculation steps of the preference matrix .sub.p of the subproblems for the solutions comprise: calculating the preference value p of the subproblem p for the solution x through formula (2) to obtain preference values of the subproblem p for 2N solutions; arranging the preference values in an ascending order to obtain a preference sequence of one subproblem for the solutions; using the preference sequence as a row of the preference matrix .sub.p; and calculating the preference sequences of all the subproblems for the solutions through the same method to obtain a preference matrix .sub.p; $\begin{array}{cc}.Math..Math.p\left(p,x,\right)=g^{\mathrm{tch}}\left(x,z^{*}\right).Math.T_L\left(\right)=\frac{\underset{1lm}{\max }.Math.\left\{.Math.f_l\left(x\right)-z_l^{*}.Math./{}_l\right\}}{1+e^{-9.Math.\left(/-1\right)/L}};& \left(2\right)\end{array}$ wherein is a weight vector of the subproblem p and z* is a reference point, wherein $z_l^{*}=\underset{xX}{\min }.Math.f_l\left(x\right),l=1,2,\mathrm{.Math.}.Math.,m.$

6. The flexible job-shop scheduling method according to claim 1, wherein in the step (c5), calculation steps of the preference matrix .sub.x of the solutions for the subproblems comprise: calculating the preference value of the solution x for the subproblem p through formula (3) to obtain preference values of the solution x for N subproblems; arranging the preference values in an ascending order to obtain a preference sequence of one solution for the subproblems; and using the preference sequence as a row of the preference matrix .sub.x, and thus .sub.x being 2NN matrix; $\begin{array}{cc}.Math..Math.x\left(x,p\right)=.Math.\stackrel{\_}{F}\left(x\right)-\frac{{}^T.Math.\stackrel{\_}{F}\left(x\right)}{{}^T.Math.}.Math..Math.& \left(3\right)\end{array}$ wherein F(x) is a target vector for standardization of the solution x and .Math. is Euclidean distance.

7. The flexible job-shop scheduling method according to claim 3, wherein in the step (c5), calculation steps of the preference matrix .sub.x of the solutions for the subproblems comprise: calculating the preference value of the solution x for the subproblem p through formula (3) to obtain preference values of the solution x for N subproblems; arranging the preference values in an ascending order to obtain a preference sequence of one solution for the subproblems; and using the preference sequence as a row of the preference matrix .sub.x, and thus .sub.x being 2NN matrix; $\begin{array}{cc}.Math..Math.x\left(x,p\right)=.Math.\stackrel{\_}{F}\left(x\right)-\frac{{}^T.Math.\stackrel{\_}{F}\left(x\right)}{{}^T.Math.}.Math..Math.& \left(3\right)\end{array}$ wherein F(x) is a target vector for standardization of the solution x and .Math. is Euclidean distance.

8. The flexible job-shop scheduling method according to claim 4, wherein in the step (c5), calculation steps of the preference matrix .sub.x of the solutions for the subproblems comprise: calculating the preference value of the solution x for the subproblem p through formula (3) to obtain preference values of the solution x for N subproblems; arranging the preference values in an ascending order to obtain a preference sequence of one solution for the subproblems; and using the preference sequence as a row of the preference matrix .sub.x, and thus .sub.x being 2NN matrix; $\begin{array}{cc}.Math..Math.x\left(x,p\right)=.Math.\stackrel{\_}{F}\left(x\right)-\frac{{}^T.Math.\stackrel{\_}{F}\left(x\right)}{{}^T.Math.}.Math..Math.& \left(3\right)\end{array}$ wherein F(x) is a target vector for standardization of the solution x and .Math. is Euclidean distance.

Description

DESCRIPTION OF DRAWINGS

[0022] FIG. 1 is a flow chart of an algorithm.

[0023] FIG. 2 is a functional diagram of a limit operator.

[0024] FIG. 3 is a Pareto frontier of an actual production order solved by different solving strategies.

[0025] Reference numbers in the embodiments of the present invention are as follows by combining with the drawings:

[0026] 1distribution of solutions selected without limit information; 2distribution of solutions selected with limit information; 3Pareto frontier obtained by solving FJSP using the solving strategy proposed in the present invention; 4Pareto frontier obtained by solving FJSP using a genetic algorithm solving strategy of non-dominated sorting with an elitist strategy; and 5Pareto frontier obtained by solving FJSP using a multi-target evolution algorithm solving strategy based on a stable matching selection strategy.

DETAILED DESCRIPTION

[0027] The present invention is further described below in combination with specific drawings and embodiments.

[0028] As shown in FIG. 1, to obtain a production process scheduling solution that is more conformable to the actual production, the method for obtaining a multi-target FJSP by a limited stable matching strategy in the present invention comprises the following steps:

[0029] a. initializing relevant parameters and populations

[0030] a1. initializing relevant parameters, comprising populations and target space dimensionality m=2, chromosome number N=40, crossover probability P.sub.c=0.8, mutation probability P.sub.m=0.6, iterations K=400, neighborhood parameter T=5 and limit operator control parameter L=1;

[0031] a2. setting a group of uniformly distributed weight vector w={.sub.1, . . . , .sub.t, . . . , .sub.N}, wherein one vector .sub.t=(.sub.t,1, . . . , .sub.t,l, . . . , .sub.t,m)R.sup.m, .sub.t,l0, simultaneously obtaining a subproblem set P={p.sub.1, . . . , p.sub.t, . . . , p.sub.N}, calculating the Euclidean distance from each weight vector to another weight vector, for the weight vector .sub.t, t=1, 2, . . . , N, setting a set B(t)={t.sub.1, t.sub.2, . . . , t.sub.T}, and then .sup.1, .sup.2, . . . , .sup.T being T vectors which are closest to .sub.t;

[0032] a3. randomly producing a population S={s.sub.1, s.sub.2, . . . , s.sub.N} of N integer coding chromosomes, calculating fitness values to obtain a solution set X={x.sub.1, x.sub.2, . . . , x.sub.N} in the target space, setting g=1; initializing a reference point z*=(z*.sub.1, z*.sub.2, . . . , z*.sub.m).sup.T, wherein

[00005]$z_l^{*}=\underset{xX}{\min }.Math.f_l\left(x\right),l=1,2,\mathrm{.Math.}.Math.,m;$

and by taking 3-workpiece 3-machine as an example, obtaining a chromosome that meets the constraint conditions through integer coding, as shown in the following table:

[0033] b. generating progeny chromosomes

[0034] for the weight vector i, randomly selecting two indexes: , from B(i) random selection, and then selecting two chromosomes s.sub. and s.sub.; conducting simulated binary crossover operation on s.sub. and s.sub. as parent chromosomes in accordance with the crossover probability P.sub.c; conducting multinomial mutation operation in accordance with the mutation probability P.sub.m to generate a progeny chromosome s.sub.N+i; calculating fitness values to obtain a solution x.sub.N+i; generating N progeny chromosomes under each evolution operation in accordance with the above operation;

[0035] c. selecting an appropriate progeny population from the selected set

[0036] c1. combining a set of generated progeny chromosomes and a set of original parent chromosomes into a set S={s.sub.1, s.sub.2, . . . , s.sub.2N} of to-be-selected chromosomes, and a set of to-be-selected solutions being X={x.sub.1, x.sub.2, . . . , x.sub.2N};

[0037] c2. firstly, converting an m-dimensional target space F(x)=[f.sub.1(x), . . . f.sub.l(x), . . . f.sub.m(x)]R.sup.m into C.sub.m.sup.2 two-dimensional spaces F.sub.c(x)=[f.sub.u(x), f.sub.v(x)], wherein c is a number of the two-dimensional spaces, c=1, 2, . . . C.sub.m.sup.2; u and v are numbers of space dimensionality, u, v [1, 2, . . . , m]; f.sub.u(x) and f.sub.v(x) respectively indicate target values of the solution x X in the two-dimensional spaces; then determining a component .sub.uv=(.sub.u, .sub.v) of the weight vector w corresponding to the subproblem p P in the two-dimensional spaces; and finally, calculating an angle component .sub.uv(x, p) of the position information : .sub.uv(x, p)=arc tan(|f.sub.u(x).sub.u|/|f.sub.v(x).sub.v|), wherein angle .sub.uv(x, p) is a sum of angle components of the subproblem p and the solution x on C.sub.m.sup.2 two-dimensional planes, .sub.uv(x, p)[0, /2]; and is an algebraic sum of all angle components;

[0038] c3. constructing an adaptive transfer function, and introducing the position information , i.e.,

[00006]$\begin{array}{cc}{T}_L\left(\right)=\frac{1}{1+e^{-9.Math.\left(/-1\right)/L}}& \left(4\right)\end{array}$

wherein L is a control parameter, and the larger the L is, the more uniform the transfer function is; in order to solve the problem of overconvergence in the early stage of iteration and ensure the balance of convergence and diversity in the later stage of iteration, with the iteration of the algorithm, L setting is gradually increased from 1 to 20;

[0039] c4. calculating preference values through a preference value calculation formula of the subproblem with limit information for the solutions, e.g., calculating the preference value of the subproblem p.sub.r, r=1, . . . , N for the candidate solution x, x S through formula (5) to obtain preference values of the subproblem p.sub.r for 2N candidate solutions; arranging the preference values in an ascending order to obtain a preference sequence of one subproblem for the solutions; and using the preference sequence as a row of .sub.p, and thus .sub.p being N2N matrix,

[00007]$\begin{array}{cc}.Math..Math.p\left(p_r,x,\right)=g^{\mathrm{tch}}\left(x{}_r,z^{*}\right).Math.T_L\left(\right)=\frac{\underset{1lm}{\max }.Math.\left\{.Math.f_l\left(x\right)-z_l^{*}.Math./{}_{r,l}\right\}}{1+e^{-9.Math.\left(/-1\right)/L}}& \left(5\right)\end{array}$

wherein .sub.r is a weight vector of the subproblem p.sub.r and z* is a reference point;

[0040] c5. calculating the preference value of the solution x X for the subproblem p P through formula (6), e.g., calculating the preference value of the solution x.sub.l for N subproblems; arranging the preference values in an ascending order to obtain a preference sequence of one solution for the subproblems; and using the preference sequence as a row of .sub.x, and thus .sub.x being 2NN matrix,

[00008]$\begin{array}{cc}.Math..Math.x\left(x_t,p\right)=.Math.\stackrel{\_}{F}\left(x_t\right)-\frac{{}^T.Math.\stackrel{\_}{F}\left(x\right)}{{}^T.Math.}.Math..Math.& \left(6\right)\end{array}$

wherein F(x) is a target vector for standardization of the solution x and .Math. is Euclidean distance;

[0041] c6. using the information of the preference matrices .sub.p and .sub.x as input, and delaying an acceptance procedure to selection the solutions; selecting chromosomes corresponding to the selected solutions; and setting g=g+1;

[0042] d. judging whether cut-off conditions are satisfied

[0043] returning to step b if g<K, otherwise outputting Pareto solution set; and selecting a certain solution according to the will of the decision maker and decoding the solution into a feasible scheduling solution.

[0044] The solutions selected during evolution in the present invention have good diversity, as shown in FIG. 2. The selected solutions are uniformly distributed in the target space. FIG. 3 proves that the present invention is effective in optimal scheduling of the actual production process.