PRODUCTION SCHEDULING METHOD AND SYSTEM BASED ON IMPROVED ARTIFICIAL BEE COLONY ALGORITHM AND STORAGE MEDIUM

Abstract

The present invention disclose a parallel machine batch scheduling method and system based on an improved artificial bee colony algorithm in a deterioration situation. With this method, a near-optimal solution for the parallel machine batch scheduling problem with deteriorating jobs and maintenance consideration can be obtained. The model of the present invention is derived from an actual production process with considerations of machine maintenance and batching as well as additional processing and maintenance time for jobs and machines over time in actual production. According to the present invention, the settlement of this problem is conducive to providing reliable decision support for the production and maintenance of an enterprise in complex real production conditions, thus reducing enterprise operation costs, increasing enterprise productivity, and promoting building of a modern smart factory of the enterprise.

Claims

1. A production scheduling method based on an improved artificial bee colony algorithm, the method being executed by a computer and comprising: S1, inputting the capacity of each machine and general processing time for a job, and setting parameters of the improved artificial bee colony algorithm, including maximum iterations t.sub.max, global optimal solution gbest, nectar source search limit UP, number of employed bees SN, and iteration t=1; S2, initializing the population with consideration of total SN nectar sources, with the position of the qth nectar source being defined as X.sub.q=(x.sub.q.sup.1, x.sub.q.sup.2, . . . , x.sub.q.sup.j, . . . , x.sub.q.sup.n), q=1, 2, . . . , SN, wherein x.sub.q.sup.j represents the position of the qth nectar source in the jth dimension, indicating that the jth job is assigned to machine x.sub.q.sup.j; S3, calculating a fitness value of each nectar source in a solution set, and updating the global optimal solution gbest; S4, calculating neighborhood selection probability $R_{a} = \frac{t}{t_{\max}}$ of the current generation, by setting the variable q=1; S5, determining whether rand(0,1) R.sub.a is true; if yes, performing an exchange mutation operation on X.sub.q, and retaining the nectar source according to a greedy rule, wherein rand(0,1) represents a random number between 0 and 1; otherwise, performing an inversion mutation operation on X.sub.q, and retaining nectar source according to the greedy rule; if the nectar source is updated, up.sub.q=0; otherwise, up.sub.q=up.sub.q+1, wherein up.sub.q represents searches for the qth nectar source; S6, with q=q+1, determining whether qSN is true; if yes, returning to the step S5; otherwise, performing step S7; S7, calculating probability ${pro}_{q} = \frac{1 .Math. / .Math. {fit}_{q}}{{.Math.}_{z = 1}^{SN} .Math. .Math. 1 .Math. / .Math. {fit}_{z}},$ wherein fit.sub.q represents the fitness value of the qth nectar source, and smaller fit.sub.q indicates a better solution since the problem to be solved is a minimization problem; S8, selecting the qth nectar source from the population with the probability pro.sub.q, and performing a tabu search operation; if the nectar source is updated, up.sub.q=0; otherwise, up.sub.q=up.sub.q+1; repeating this operation SN times to update the solution set; S9, setting the variable q=1; S10, if up.sub.qUP, q=q+1; otherwise, replacing X.sub.q with a randomly generated new solution, and let up.sub.q=0, q=q+1; S11, determining whether qSN is true; if yes, returning to the step S10; otherwise, performing step S12; and S12, replacing later 20% nectar sources in the solution set with randomly generated nectar sources; let t=t+1; determining whether tt.sub.max is true; if yes, returning to the step S3; otherwise, terminating the algorithm and outputting the global optimal solution gbest, and outputting optimal job assignment, job batching, batch processing order and starting time of maintenance on each machine.

2. The method according to claim 1, wherein calculating the fitness value of each nectar source in the solution set in the step S3 comprises: step S31, successively assigning the jth job to machine x.sub.q.sup.j according to a code rule first, and on each machine, sorting the jobs in a non-decreasing order by the general processing time; step S32, on each machine, arranging first $n_{i} - (.Math. \frac{n_{i}}{c} .Math. - 1) .Math. c$ jobs into a first batch and deleting such jobs from a job list; then arranging first c jobs in the remaining list into a batch and deleting such jobs from the job list, and so on, until all jobs in the job list are arranged completely, wherein n.sub.i represents the number of jobs on the ith machine, while c represents the number of jobs that a machine is able to process simultaneously, and $.Math. \frac{x}{y} .Math.$ represents the smallest integer that is not less than $\frac{x}{y};$ step S33, setting parameter e=1, indicating that maintenance is started after the completion of processing of the first job; step S34, with regard to each machine, calculating $w_{hi} = {\begin{matrix} (d_{i} + 1) .Math. {(+ 1)}^{e - h} .Math. h = 1, 2, 3 .Math. .Math., e \\ {(+ 1)}^{e - h} .Math. h = 1, 2, 3, .Math., B_{i} \end{matrix}, i = 1, .Math., m,$ wherein B.sub.i represents the total number of batches on the ith machine; step S35, sorting all batches on each machine in a non-decreasing order by processing time, arranging the first batch in a position with the maximum value of w.sub.hi, i.e., arranging the first job to be processed as the hth one, and deleting this batch and w.sub.hi from the list; and repeating this operation until each batch corresponds to the processing order one to one; and step S36, calculating completion time C.sub.max.sup.i(e) on each machine; let e=e+1, determining whether eB.sub.i is true; if yes, returning to the step S34; otherwise, confirming on the machine that maintenance is started after the completion of processing of the (L*)th job, wherein L*=Arg max.sub.L=1,2, . . . ,B.sub.i{C.sub.max.sup.i(L)}, i.e., arranging the position with the shortest processing time among all positions to be the position of maintenance, and terminating the algorithm.

3. The method according to claim 1, wherein the step S5 comprises: step S51, obtaining a nectar source code, and generating a random number rand between 0 and 1; step S52, determining whether rand<R.sub.a is true; if yes, performing step S53; otherwise, performing step S54; step S53, randomly generating two positive integers x and y between 1 and n, and interchanging numerical values corresponding to the xth and yth positions in the nectar source, thereby obtaining a new nectar source position code; and step S54, randomly generating two positive integers x and y between 1 and n, and reversing a sequence between the xth and yth position, thereby obtaining a new nectar source position code.

4. The method according to claim 1, wherein the step S7 comprises: step S71, obtaining a nectar source code as current optimal solution, and defining iterations it max, tabu list length tabulong, and neighborhood searches Slong; step S72, randomly generating two positive integers x and y between 1 and n, moving the numerical value of the xth position to the yth position, and then arranging numerical values between the (x+1)th and the yth position to the xth to (y1)th positions of a new code, thereby obtaining a new nectar source code; step S73, repeating the step S72 until Slong new nectar source codes are generated, and calculating the fitnesses of all solutions; step S74, comparing the solution with the best fitness with the current optimal solution; if the solution with the best fitness is superior to the current optimal solution, performing step S76; otherwise, performing step S75; step S75, sorting all the solutions in a descending order, successively checking whether the corresponding x and y values of the solutions are present in the tabu list until the result for a solution is no, and then performing step S76 with the solution as the best-fit solution; step S76, replacing the current optimal solution with the best-fit solution; determining whether the number of records in the tabu list is greater than tabulong; if yes, deleting the last element in the tabu list, moving each element down by one position, and adding the x and y values corresponding to the best-fit solution to the first position of the tabu list; otherwise, directly moving each element down by one position, and adding the x and y values corresponding to the best-fit solution to the first position of the tabu list; and step S77, with it=it+1, determining whether itit max is true; if yes, returning to the step S72; otherwise, terminating search.

5. A production scheduling system based on an improved artificial bee colony algorithm, wherein the system comprises a computer, comprising: at least one storage unit; at least one processing unit; and at least one output unit; wherein the at least one storage unit stores at least one instruction to be loaded and executed by the at least one processing unit to implement the following steps: S1, inputting the capacity of each machine and general processing time for a job, and setting parameters of the improved artificial bee colony algorithm, including maximum iterations t.sub.max, global optimal solution gbest, nectar source search limit UP, number of employed bees SN, and iteration t=1; S2, initializing the population with consideration of total SN nectar sources, with the position of the qth nectar source being defined as X.sub.q=(x.sub.q.sup.1, x.sub.q.sup.2, . . . , x.sub.q.sup.j, . . . , x.sub.q.sup.n), q=1, 2, . . . , SN, wherein, . . . , represents the position of the qth nectar source in the jth dimension, indicating that the jth job is assigned to machine x.sub.q.sup.j; S3, calculating a fitness value of each nectar source in a solution set, and updating the global optimal solution gbest; S4, calculating neighborhood selection probability $R_{a} = \frac{t}{t_{\max}}$ of the current generation, by setting the variable q=1; S5, determining whether rand(0,1)R.sub.a is true; if yes, performing an exchange mutation operation on X.sub.q, and retaining the nectar source according to a greedy rule, wherein rand(0,1) represents a random number between 0 and 1; otherwise, performing an inversion mutation operation on X.sub.q, and retaining nectar source according to the greedy rule; if the nectar source is updated, up.sub.q=0; otherwise, up.sub.q=up.sub.q+1, wherein up.sub.q represents searches for the qth nectar source; S6, with q=q+1, determining whether qSN is true; if yes, returning to the step S5; otherwise, performing step S7; S7, calculating probability ${pro}_{q} = \frac{1 .Math. / .Math. {fit}_{q}}{{.Math.}_{z = 1}^{SN} .Math. .Math. 1 .Math. / .Math. {fit}_{z}},$ wherein fit.sub.q represents the fitness value of the qth nectar source, and smaller fit.sub.q indicates a better solution since the problem to be solved is a minimization problem; S8, selecting the qth nectar source from the population with the probability pro.sub.q, and performing a tabu search operation; if the nectar source is updated, up.sub.q=0; otherwise, up.sub.q=up.sub.q+1; repeating this operation SN times to update the solution set; S9, setting the variable q=1; S10, if up.sub.qUP, q=q+1; otherwise, replacing X.sub.q with a randomly generated new solution, and let up.sub.q=0, q=q+1; S11, determining whether qSN is true; if yes, returning to the step S10; otherwise, performing step S12; and S12, replacing later 20% nectar sources in the solution set with randomly generated nectar sources; let t=t+1; determining whether tt.sub.max is true; if yes, returning to the step S3; otherwise, terminating the algorithm; and the at least one output unit is configured to output the global optimal solution gbest, and output optimal job assignment, job batching, batch processing order and starting time of maintenance on each machine.

6. The system according to claim 5, wherein in the step S3 implemented through loading and execution of the at least one instruction by the at least one processing unit, the process of calculating the fitness value of each nectar source in the solution set comprises: step S31, successively assigning the jth job to machine x.sub.q.sup.j according to a code rule first, and on each machine, sorting the jobs in a non-decreasing order by the general processing time; step S32, on each machine, arranging first $n_{i} - (.Math. \frac{n_{i}}{c} .Math. - 1) .Math. c$ jobs into a first batch and deleting such jobs from a job list; then arranging first c jobs in the remaining list into a batch and deleting such jobs from the job list, and so on, until all jobs in the job list are arranged completely, wherein n.sub.i represents the number of jobs on the ith machine, while c represents the number of jobs that a machine is able to process simultaneously, and $.Math. \frac{x}{y} .Math.$ represents the smallest integer that is not less than $\frac{x}{y};$ step S33, setting parameter e=1, indicating that maintenance is started after the completion of processing of the first job; step S34, with regard to each machine, calculating $w_{hi} = {\begin{matrix} (d_{i} + 1) .Math. {(+ 1)}^{e - h} .Math. h = 1, 2, 3 .Math. .Math., e \\ {(+ 1)}^{e - h} .Math. h = 1, 2, 3, .Math., B_{i} \end{matrix}, i = 1, .Math., m,$ wherein B.sub.i represents the total number of batches on the ith machine; step S35, sorting all batches on each machine in a non-decreasing order by processing time, arranging the first batch in a position with the maximum value of w.sub.hi, i.e., arranging the first job to be processed as the hth one, and deleting this batch and w.sub.hi from the list; and repeating this operation until each batch corresponds to the processing order one to one; and step S36, calculating completion time C.sub.max.sup.j(e) on each machine; let e=e+1, determining whether eB.sub.i is true; if yes, returning to the step S34; otherwise, confirming on the machine that maintenance is started after the completion of processing of the (L*)th job, wherein L*=Arg max.sub.L=1,2, . . . ,B.sub.i, {C.sub.max.sup.i(L)}, i.e., arranging the position with the shortest processing time among all positions to be the position of maintenance, and terminating the algorithm.

7. The system according to claim 5, wherein the step S5 implemented through loading and execution of the at least one instruction by the at least one processing unit comprises: step S51, obtaining a nectar source code, and generating a random number rand between 0 and 1; step S52, determining whether rand<R.sub.a is true; if yes, performing step S53; otherwise, performing step S54; step S53, randomly generating two positive integers x and y between 1 and n, and interchanging numerical values corresponding to the xth and yth positions in the nectar source, thereby obtaining a new nectar source position code; and step S54, randomly generating two positive integers x and y between 1 and n, and reversing a sequence between the xth and yth position, thereby obtaining a new nectar source position code.

8. The system according to claim 5, wherein the step S7 implemented through loading and execution of the at least one instruction by the at least one processing unit comprises: step S71, obtaining a nectar source code as current optimal solution, and defining iterations it max, tabu list length tabulong, and neighborhood searches Slong; step S72, randomly generating two positive integers x and y between 1 and n, moving the numerical value of the xth position to the yth position, and then arranging numerical values between the (x+1)th and the yth position to the xth to (y1)th positions of a new code, thereby obtaining a new nectar source code; step S73, repeating the step S72 until Slong new nectar source codes are generated, and calculating the fitnesses of all solutions; step S74, comparing the solution with the best fitness with the current optimal solution; if the solution with the best fitness is superior to the current optimal solution, performing step S76; otherwise, performing step S75; step S75, sorting all the solutions in a descending order, successively checking whether the respective x and y values of the solutions are present in the tabu list until the result for a solution is no, and then performing step S76 with the solution as the best-fit solution; step S76, replacing the current optimal solution with the best-fit solution; determining whether the number of records in the tabu list is greater than tabulong; if yes, deleting the last element in the tabu list, moving each element down by one position, and adding the x and y values corresponding to the best-fit solution to the first position of the tabu list; otherwise, directly moving each element down by one position, and adding the x and y values corresponding to the best-fit solution to the first position of the tabu list; and step S77, with it=it+1, determining whether itit max is true; if yes, returning to the step S72; otherwise, terminating search.

9. A computer-readable storage medium that stores at least one instruction to be loaded and executed by a processor to implement the method of claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0041] Various other advantages and benefits will become obvious for those of ordinary skill in the art from the following detailed descriptions of preferred embodiments. The accompanying drawings are merely intended to illustrate the preferred embodiments rather than limit the invention. Furthermore, like reference numerals indicate like components throughout the drawings in which:

[0042] FIG. 1 is a schematic diagram of a parallel machine batch scheduling problem with maintenance consideration in accordance with an embodiment of the present invention;

[0043] FIG. 2 is a flowchart of a production scheduling method based on an improved artificial bee colony algorithm in accordance with an embodiment of the present invention; and

[0044] FIG. 3 is a structure diagram of a production scheduling system based on an improved artificial bee colony algorithm in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION OF THE PRESENT INVENTION

[0045] Technical solutions in the embodiments of the present invention will be described clearly and fully below in combination with the drawings accompanying the embodiments of the present invention. It is apparent that the described embodiments are merely part of embodiments of the present invention, rather than all. Other embodiments achieved by those of ordinary skill in the art based on the embodiments in the present invention without creative work shall all fall into the scope of protection of the present invention.

[0046] The embodiments of the present invention are meant to solve the parallel machine batch scheduling problem with maintenance consideration in a deterioration situation with the purpose of determining a specific machine to which each job will be assigned, the batching of jobs on the machine, the processing order of a batch and start time of maintenance. Based on the characteristics of the problem, an effective hybrid algorithm is developed by theoretical analysis and mathematical derivation to solve the combinatorial optimization problem, providing a new method for the management of an enterprise production schedule in complex conditions.

[0047] On this basis, one embodiment of the present invention provides a production scheduling method based on an improved artificial bee colony algorithm. The method is executed by a computer, as shown in FIG. 2, and includes:

[0048] S1, inputting the capacity of each machine and general processing time for a job, and setting parameters of the improved artificial bee colony algorithm, including maximum iterations t.sub.max, global optimal solution gbest, nectar source search limit UP, number of employed bees SN, and iteration t=1;

[0049] S2, initializing the population with consideration of total SN nectar sources, with the position of the qth nectar source being defined as X.sub.q=(x.sub.q.sup.1, x.sub.q.sup.2, . . . , x.sub.q.sup.j, . . . , x.sub.q.sup.n), q=1, 2, . . . , SN, wherein x.sub.q.sup.j represents the position of the qth nectar source in the jth dimension, indicating that the jth job is assigned to machine x.sub.q.sup.j;

[0050] S3, calculating a fitness value of each nectar source in a solution set, and updating the global optimal solution gbest;

[0051] S4, calculating neighborhood selection probability

[00005] $R_{a} = \frac{t}{t_{\max}}$

of the current generation, by setting the variable q=1;

[0052] S5, determining whether rand(0,1)R.sub.a is true; if yes, performing an exchange mutation operation on X.sub.q, and retaining the nectar source according to a greedy rule, wherein rand(0,1) represents a random number between 0 and 1; otherwise, performing an inversion mutation operation on X.sub.q, and retaining nectar source according to the greedy rule; if the nectar source is updated, up.sub.q=0; otherwise, up.sub.q=up.sub.q+1, wherein up.sub.q represents searches for the qth nectar source;

[0053] S6, with q=q+1, determining whether qSN is true; if yes, returning to the step S5; otherwise, performing step S7;

[0054] S7, calculating probability

[00006] ${pro}_{q} = \frac{1 / {fit}_{q}}{{.Math.}_{z = 1}^{SN} .Math. .Math. 1 / {fit}_{z}},$

wherein fit.sub.q represents the fitness value of the qth nectar source, and smaller fit.sub.q indicates a better solution since the problem to be solved is a minimization problem;

[0055] S8, selecting the qth nectar source from the population with the probability pro.sub.q, and performing a tabu search operation; if the nectar source is updated, up.sub.q=0; otherwise, up.sub.q=up.sub.q+1; repeating this operation SN times to update the solution set;

[0056] S9, setting the variable q=1;

[0057] S10, if up.sub.qUP, q=q+1; otherwise, replacing X.sub.q with a randomly generated new solution, and let up.sub.q=0, q=q+1;

[0058] S11, determining whether qSN is true; if yes, returning to the step S10; otherwise, performing step S12; and

[0059] S12, replacing later 20% nectar sources in the solution set with randomly generated nectar sources; let t=t+1; determining whether tt.sub.max is true; if yes, returning to the step S3; otherwise, terminating the algorithm and outputting the global optimal solution gbest, and outputting optimal job assignment, job batching, batch processing order and starting time of maintenance on each machine.

[0060] According to this embodiment of the present invention, a near-optimal solution for the parallel machine batch scheduling problem with deteriorating jobs and maintenance consideration can be obtained. The model of the present invention is derived from an actual production process with considerations of machine maintenance and batching as well as additional processing and maintenance time for jobs and machines over time in actual production. According to the present invention, the settlement of this problem is conducive to providing reliable decision support for the production and maintenance of an enterprise in complex real production conditions, thus reducing enterprise operation costs, increasing enterprise productivity, and promoting building of a modern smart factory of the enterprise.

[0061] In specific implementation, calculating the fitness value of each nectar source in the solution set in the step S3 may include:

[0062] step S31, successively assigning the jth job to machine x.sub.q.sup.j according to a code rule first, and on each machine, sorting the jobs in a non-decreasing order by the general processing time;

[0063] step S32, on each machine, arranging first

[00007] $n_{i} - (.Math. \frac{n_{i}}{c} .Math. - 1) .Math. c$

jobs into a first batch and deleting such jobs from a job list; then arranging first c jobs in the remaining list into a batch and deleting such jobs from the job list, and so on, until all jobs in the job list are arranged completely, wherein n.sub.i represents the number of jobs on the ith machine, while c represents the number of jobs that a machine is able to process simultaneously, and

[00008] $.Math. \frac{x}{y} .Math.$

represents the smallest integer that is not less than

[00009] $\frac{x}{y};$

[0064] step S33, setting parameter e=1, indicating that maintenance is started after the completion of processing of the first job;

[0065] step S34, with regard to each machine, calculating

[00010] $w_{hi} = {\begin{matrix} (d_{i} + 1) .Math. {(+ 1)}^{e - h} .Math. h = 1, 2, 3 .Math. .Math. .Math. .Math., e \\ {(+ 1)}^{e - h} .Math. h = 1, 2, 3, .Math. .Math., B_{i} \end{matrix}, i = 1, .Math. .Math., m,$

[0066] wherein B.sub.i represents the total number of batches on the ith machine;

[0067] step S35, sorting all batches on each machine in a non-decreasing order by processing time, arranging the first batch in a position with the maximum value of w.sub.hi, i.e., arranging the first job to be processed as the hth one, and deleting this batch and w.sub.hi from the list; and repeating this operation until each batch corresponds to the processing order one to one; and

[0068] step S36, calculating completion time C.sub.max.sup.i(e) on each machine; let e=e+1, determining whether eB.sub.i is true; if yes, returning to the step S34; otherwise, confirming on the machine that maintenance is started after the completion of processing of the (L*)th job, wherein L*=Arg max.sub.L=1,2, . . . ,B.sub.i {C.sub.max.sup.i(L)}, i.e., arranging the position with the shortest processing time among all positions to be the position of maintenance, and terminating the algorithm.

[0069] In specific implementation, the step S5 may include:

[0070] step S51, obtaining a nectar source code, and generating a random number rand between 0 and 1;

[0071] step S52, determining whether rand<R.sub.a is true; if yes, performing step S53; otherwise, performing step S54;

[0072] step S53, randomly generating two positive integers x and y between 1 and n, and interchanging numerical values corresponding to the xth and yth positions in the nectar source, thereby obtaining a new nectar source position code; and

[0073] step S54, randomly generating two positive integers x and y between 1 and n, and reversing a sequence between the xth and yth position, thereby obtaining a new nectar source position code.

[0074] In specific implementation, the step S7 may include:

[0075] step S71, obtaining a nectar source code as current optimal solution, and defining iterations it max, tabu list length tabulong, and neighborhood searches Slong;

[0076] step S72, randomly generating two positive integers x and y between 1 and n, moving the numerical value of the xth position to the yth position, and then arranging numerical values between the (x+1)th and the yth position to the xth to (y1)th positions of a new code, thereby obtaining a new nectar source code;

[0077] step S73, repeating the step S72 until Slong new nectar source codes are generated, and calculating the fitnesses of all solutions;

[0078] step S74, comparing the solution with the best fitness with the current optimal solution; if the solution with the best fitness is superior to the current optimal solution, performing step S76; otherwise, performing step S75;

[0079] step S75, sorting all the solutions in a descending order, successively checking whether the respective x and y values of the solutions are present in the tabu list until the result for a solution is no, and then performing step S76 with the solution as the best-fit solution;

[0080] step S76, replacing the current optimal solution with the best-fit solution; determining whether the number of records in the tabu list is greater than tabulong; if yes, deleting the last element in the tabu list, moving each element down by one position, and adding the x and y values corresponding to the best-fit solution to the first position of the tabu list; otherwise, directly moving each element down by one position, and adding the x and y values corresponding to the best-fit solution to the first position of the tabu list; and

[0081] step S77, with it=it+1, determining whether itit max is true; if yes, returning to the step S72; otherwise, terminating search.

[0082] The present invention has the following advantages:

[0083] 1. The present invention is aimed at the parallel machine batch scheduling problem with deteriorating jobs and maintenance consideration. By the improved artificial bee colony algorithm, jobs are firstly assigned to different machines by the means of codes. Then, an arrangement strategy with regard to job batching, sorting and maintenance for each machine is put forward according to the nature of the problem, and the optimal productive maintenance solution on each machine is obtained in polynomial time. Next, an adaptive neighborhood search operation is performed on each nectar source. Systematic updating based on tatu search is carried out selectively on the basis of the fitnesses of the nectar sources. By repeated iterations, continuous updating of the population is achieved, and the optimal solution is obtained eventually. The improved artificial bee colony algorithm is a highly efficient algorithm in convergence rate and convergence result. By this algorithm, the parallel machine batch scheduling problem with deteriorating jobs and maintenance consideration is solved and the enterprise productivity in actual complex conditions is improved, providing effective decision support for an enterprise and being conductive to speed up the intelligent development of the enterprise.

[0084] 2. The present invention provides the optimal algorithm for batching and sorting jobs and arranging maintenance on each particular machine in the deterioration situation, ensuring that the production capability of each machine can be brought into full play, i.e., the optimization of the processing schedule on each machine is achieved, after the completion of the process of assigning a set of jobs to machines.

[0085] 3. While a general artificial bee colony algorithm has the problem of easily plunging into local optimum, the artificial bee colony algorithm exhibits good performance when combined with a plurality of algorithms in use. According to the present invention, an adaptive neighborhood search mechanism is designed with regard to the disadvantages and advantages of the artificial bee colony algorithm in combination with specific use thereof in this problem, and the search capability of follower bees is enhanced by a tabu search algorithm so as to guarantee the updating efficiency of nectar sources. Thus, the convergence rate of the algorithm and the diversity of solutions are increased effectively, and the local convergence capability in the last phase of the algorithm is enhanced to a certain extent.

[0086] Based on the inventive concept, another embodiment of the present invention provides a production scheduling system based on an improved artificial bee colony algorithm. As shown in FIG. 3, the scheduling system includes a computer including:

[0087] at least one storage unit 201;

[0088] at least one processing unit 202; and

[0089] at least one output unit (not shown in the figure).

[0090] The processing unit may be, for example, a processor. The storage unit may be, for example, a memory. The output unit may be, for example, an output device formed by a data interface and a data cable. The output unit can output data to a display screen, other electronic devices and the like.

[0091] The at least one storage unit stores at least one instruction to be loaded and executed by the at least one processing unit to implement the following steps:

[0092] S1, inputting the capacity of each machine and general processing time for a job, and setting parameters of the improved artificial bee colony algorithm, including maximum iterations t.sub.max, global optimal solution gbest, nectar source search limit UP, number of employed bees SN, and iteration t=1;

[0093] S2, initializing the population with consideration of total SN nectar sources, with the position of the qth nectar source being defined as X.sub.q=(x.sub.q.sup.1, x.sub.q.sup.2, . . . , x.sub.q.sup.j, . . . , x.sub.q.sup.n), q=1, 2, . . . , SN, wherein x.sub.q.sup.j represents the position of the qth nectar source in the jth dimension, indicating that the jth job is assigned to machine x.sub.q.sup.j;

[0094] S3, calculating a fitness value of each nectar source in a solution set, and updating the global optimal solution gbest;

[0095] S4, calculating neighborhood selection probability

[00011] $R_{a} = \frac{t}{t_{\max}}$

of the current generation, by setting the variable q=1;

[0096] S5, determining whether rand(0,1)R.sub.a is true; if yes, performing an exchange mutation operation on X.sub.q, and retaining the nectar source according to a greedy rule, wherein rand(0,1) represents a random number between 0 and 1; otherwise, performing an inversion mutation operation on X.sub.q, and retaining nectar source according to the greedy rule; if the nectar source is updated, up.sub.q=0; otherwise, up.sub.q=up.sub.q+1, wherein up.sub.q represents searches for the qth nectar source;

[0097] S6, with q=q+1, determining whether qSN is true; if yes, returning to the step S5; otherwise, performing step S7;

[0098] S7, calculating probability

[00012] ${pro}_{q} = \frac{1 / {fit}_{q}}{{.Math.}_{z = 1}^{SN} .Math. .Math. 1 / {fit}_{z}},$

wherein fit.sub.q represents the fitness value of the qth nectar source, and smaller fit.sub.q indicates a better solution since the problem to be solved is a minimization problem;

[0099] S8, selecting the qth nectar source from the population with the probability pro.sub.q, and performing a tabu search operation; if the nectar source is updated, up.sub.q=0; otherwise, up.sub.q=up.sub.q+1; repeating this operation SN times, and updating the solution set;

[0100] S9, setting the variable q=1;

[0101] S10, if up.sub.qUP, q=q+1; otherwise, replacing X.sub.q with a randomly generated new solution, and let up.sub.q=0, q=q+1;

[0102] S11, determining whether qSN is true; if yes, returning to the step S10; otherwise, performing step S12; and

[0103] S12, replacing later 20% nectar sources in the solution set with randomly generated nectar sources; let t=t+1; determining whether tt.sub.max is true; if yes, returning to the step S3; otherwise, terminating the algorithm.

[0104] The at least one output unit 202 is configured to output the global optimal solution gbest, and output optimal job assignment, job batching, batch processing order and starting time of maintenance on each machine.

[0105] Alternatively, the at least one processing unit 201 calculates the fitness value of each nectar source in the solution set in the step S3, which may specifically include:

[0106] step S31, successively assigning the jth job to machine x.sub.q.sup.j according to a code rule first, and on each machine, sorting the jobs in a non-decreasing order by the general processing time;

[0107] step S32, on each machine, arranging first

[00013] $n_{i} - (.Math. \frac{n_{i}}{c} .Math. - 1) .Math. c$

[00014] $.Math. \frac{x}{y} .Math.$

represents the smallest integer that is not less than

[00015] $\frac{x}{y};$

[0108] step S33, setting parameter e=1, indicating that maintenance is started after the completion of processing of the first job;

[0109] step S34, with regard to each machine, calculating

[00016] $w_{hi} = {\begin{matrix} (d_{i} + 1) .Math. {(+ 1)}^{e - h} .Math. h = 1, 2, 3 .Math. .Math., e \\ {(+ 1)}^{e - h} .Math. h = 1, 2, 3, .Math., B_{i} \end{matrix}, i = 1, .Math., m,$

[0110] wherein B.sub.i represents the total number of batches on the ith machine;

[0111] step S35, sorting all batches on each machine in a non-decreasing order by processing time, arranging the first batch in a position with the maximum value of w.sub.hi, i.e., arranging the first job to be processed as the hth one, and deleting this batch and w.sub.hi from the list; and repeating this operation until each batch corresponds to the processing order one to one; and

[0112] step S36, calculating completion time C.sub.max.sup.i(e) on each machine; let e=e+1, determining whether eB.sub.i is true; if yes, returning to the step S34; otherwise, confirming on the machine that maintenance is started after the completion of processing of the (L*)th job, wherein L*=Arg max.sub.L=1,2 . . . ,B.sub.i{C.sub.max.sup.i(L)}, i.e., arranging the position with the shortest processing time among all positions to be the position of maintenance, and terminating the algorithm.

[0113] Alternatively, the at least one processing unit 201 performs the step S5, which may specifically include:

[0114] step S51, obtaining a nectar source code, and generating a random number rand between 0 and 1;

[0115] step S52, determining whether rand<R.sub.a is true; if yes, performing step S53; otherwise, performing step S54;

[0116] step S53, randomly generating two positive integers x and y between 1 and n, and interchanging numerical values corresponding to the xth and yth positions in the nectar source, thereby obtaining a new nectar source position code; and

[0117] step S54, randomly generating two positive integers X and y between 1 and n, and reversing a sequence between the xth and yth position, thereby obtaining a new nectar source position code.

[0118] Alternatively, the at least one processing unit 201 performs the step S7, which may specifically include:

[0119] step S71, obtaining a nectar source code as current optimal solution, and defining iterations it max, tabu list length tabulong, and neighborhood searches Slong;

[0120] step S72, randomly generating two positive integers x and y between 1 and n, moving the numerical value of the xth position to the yth position, and then arranging numerical values between the (x+1)th and the yth position to the xth to (y1)th positions of a new code, thereby obtaining a new nectar source code;

[0121] step S73, repeating the step S72 until Slong new nectar source codes are generated, and calculating the fitnesses of all solutions;

[0122] step S74, comparing the solution with the best fitness with the current optimal solution; if the solution with the best fitness is superior to the current optimal solution, performing step S76; otherwise, performing step S75;

[0123] step S75, sorting all the solutions in a descending order, successively checking whether the respective x and y values of the solutions are present in the tabu list until the result for a solution is no, and then performing step S76 with the solution as the best-fit solution;

[0124] step S76, replacing the current optimal solution with the best-fit solution; determining whether the number of records in the tabu list is greater than tabulong; if yes, deleting the last element in the tabu list, moving each element down by one position, and adding the x and y values corresponding to the best-fit solution to the first position of the tabu list; otherwise, directly moving each element down by one position, and adding the x and y values corresponding to the best-fit solution to the first position of the tabu list; and step S77, with it=it+1, determining whether itit max is true; if yes, returning to the step S72; otherwise, terminating search.

[0125] Since the production scheduling system based on the improved artificial bee colony algorithm introduced in this embodiment can execute the production scheduling method based on the improved artificial bee colony algorithm according to the embodiment of the present invention, those skilled in the art can understand specific embodiments of the production scheduling system based on the improved artificial bee colony algorithm according to this embodiment and various variations thereof based on the production scheduling method based on the improved artificial bee colony algorithm introduced in the embodiment of the present invention. Thus, how the production scheduling system based on the improved artificial bee colony algorithm implements the production scheduling system based on the improved artificial bee colony algorithm in the embodiment of the present invention will not be introduced in detail herein. Any implementation of the system employed in the production scheduling method based on the improved artificial bee colony algorithm in the embodiment of the present invention by those skilled in the art shall fall into the scope of protection of the present application.

[0126] An embodiment of the present invention also provides a computer-readable storage medium that stores at least one instruction to be loaded and executed by a processor to implement the above scheduling method.

[0127] Numerous specific details are provided in the description herein. However, it can be understood that the embodiments of the present disclosure may be practiced without these specific details. In some examples, well-known methods, structures and techniques are not shown in detail in order not to obscure the understanding of this description.

[0128] Similarly, it should be appreciated that in the foregoing descriptions of the example embodiments of the present disclosure, various features of the present disclosure are sometimes grouped together in a single embodiment, figure, or description thereof for the purpose of streamlining the disclosure and aiding in the understanding of one or more of the various inventive aspects. However, the method of the present disclosure is not to be interpreted as reflecting an intention that the claimed disclosure requires more features that are expressly contained in each claim. Rather, as the following claims reflect, inventive subject matter lies in less than all features of a single embodiment as disclosed above. Thus, the claims following the detailed description are hereby expressly incorporated into the detailed description, with each claim standing on its own as a separate embodiment of the present disclosure.

PRODUCTION SCHEDULING METHOD AND SYSTEM BASED ON IMPROVED ARTIFICIAL BEE COLONY ALGORITHM AND STORAGE MEDIUM

Inventors

Cpc classification

Classification Explorer

G05B2219/32283

PHYSICS

Classification Explorer

G06Q10/06311

PHYSICS

Classification Explorer

G05B2219/32252

PHYSICS

Classification Explorer

G05B19/41865

PHYSICS

International classification

Classification Explorer

G06Q10/06

PHYSICS

Classification Explorer

G05B19/418

PHYSICS

Abstract

Claims

Description