METHOD AND SYSTEM FOR BATCH SCHEDULING UNIFORM PARALLEL MACHINES WITH DIFFERENT CAPACITIES BASED ON IMPROVED GENETIC ALGORITHM

Abstract

A method and system for batch scheduling uniform parallel machines with different capacities based on an improved genetic algorithm are provided. The method is to solve the batch scheduling problem of uniform parallel machines with different capacities. Jobs are distributed to machines by an improved genetic algorithm, and a corresponding batching strategy and a batch scheduling strategy are proposed according to the natural of the problem to obtain a fitness value of a corresponding individual; then, the quality of the solution is improved by a local search strategy; and, a crossover operation is performed on a population based on the fitness of the solution, and the population is continuously updated by repetitive iteration to eventually obtain an optimal solution.

Claims

1. A method for batch scheduling uniform parallel machines with different capacities based on an improved genetic algorithm, comprising: step 1: inputting a capacity of each machine and a processing time for a job, setting parameters of the improved genetic algorithm including the maximum number of iterations t.sub.max, a globally optimal solution gbest and the number of iterations t=1; step 2: initializing a population, and defining the gene of the h.sup.th chromosome among total Q chromosomes as X.sub.k=(x.sub.h.sup.1,x.sub.h.sup.2, . . . ,x.sub.h.sup.d, . . . ,x.sub.h.sup.n), h=1,2, . . . , Q, where x.sub.h.sup.d represents the gene of the h.sup.th chromosome in the d.sup.th dimension and indicates that the d.sup.th job is assigned to the (x.sub.h.sup.d).sup.th machine; step 3: generating an initial solution by a heuristic algorithm, and using the initial solution as a first chromosome in the population; step 4: performing a local search strategy on the population to improve the quality of the population; step 5: calculating a fitness value for each solution in the population, updating the globally optimal solution, and assigning the minimum fitness value to gbest; step 6: randomly selecting two solutions X.sub.h.sub.2 and X.sub.h.sub.1 from the population, comparing the fitness values of the two solutions, and using the solution having a larger fineness value as a first parent solution, and repeating this operation to generate another parent solution; step 7: setting a variable h=1; determining whether rand <0.5 is satisfied, where rand is a random number within [0,1]; if so, selecting the h.sup.th gene of the first parent solution as the h.sup.th gene of a filial generation; if not, selecting the h.sup.th gene of the second parent solution as the h.sup.th gene of the filial generation; assuming hh+1, and repeating this step until h>n, so as to generate a new chromosome; step 8: repeating the step 7 to generate Q filial solutions, and calculating a fitness value for each filial solution; step 9: sequencing the original population and the filial population in a non-descending order of the fitness values; and selecting first N.sub.s chromosomes in the original population and first QN.sub.s chromosomes in the filial population to form a new population; step 10: sequencing the new population in a non-descending order of the fitness values, and randomly generating N.sub.m chromosomes to replace last N.sub.m chromosomes in the new population so as to generate a next-generation population, where t=t+1; and step 11: determining whether tt.sub.max is satisfied; if so, returning to the step 4; if not, ending the algorithm, and outputting the globally optimal solution gbest as well as the optimal processing task assignment and the batching mode and batch processing sequences on each machine.

2. The method according to claim 1, wherein the step 3 further comprises: step 31: sequencing all jobs in a non-ascending order of the processing time to obtain a set of sequenced jobs; step 32: sequencing all machines in a non-ascending order of the processing speed, and sequencing the machines in a non-ascending order of the capacities of the machines if the processing speed is identical; step 33: assuming j=1, C.sub.j[i]=0, and A.sub.i0 and i=1, . . . , m, where C.sub.j[i] represents a completion time for a job j on a machine i, and A.sub.i represents an idle time for the machine i; step 34: calculating $C_{j} [i] = A_{i} + \frac{p_{j}}{v_{i .Math.}}, i = 1, .Math. .Math., m,$ where p.sub.j represents a processing time for the j.sup.th job, and v.sub.i represents a processing speed of the i.sup.th machine; step 35: selecting a machine having the minimum C.sub.j[i] as a machine min, and assuming A.sub.min=C.sub.j[min] and j=j+C.sub.min; step 36: if j <n, assigning jobs jC.sub.min to j1 to the machine min, and executing the step 34; or otherwise, assigning all unassigned jobs in the set of jobs to the machine min, and executing a step 37; and step 37: returning C.sub.max=max.sub.im{A.sub.i}, and ending the algorithm.

3. The method according to claim 1, wherein the step 4 further comprises: step 41: sequencing batches of the machines in a non-ascending order of the batch processing time, and sequencing jobs in the batches in a non-ascending order of the processing time; step 42: sequencing the machines in a non-ascending order of the completion time, and assuming i=1,h=m, where the completion time for each machine is a completion time for the last batch on the machine; step 43: selecting the i.sup.th machine as a machine i, and selecting the h.sup.th machine as a machine h; step 44: if h>1, executing a step 45; or otherwise, executing a step 48; step 45: selecting any batch b on the machine i, and selecting any batch f on the machine h; step 46: if there is a job j in the batch f, and P.sub.j<P.sup.b and P.sup.bP.sup.f are satisfied, exchanging the job j with the first job in the batch b, and executing a step 47; or otherwise, assuming h=h1 and executing the step 44, where P.sup.b represents the processing time for the batch b; step 47: sequencing the jobs in the batches b and f in a non-ascending order of the processing time, and executing the step 45; and step 48: ending the search.

4. The method according to claim 1, wherein the fitness of an individual is calculated by the following steps: step 1: for X.sub.k=(x.sub.1,x.sub.2, . . . ,x.sub.h, . . . ,x.sub.n), assigning the h.sup.th job to the (x.sub.h).sup.th machine to obtain a set of jobs on each machine; step 2: temporarily placing the y.sup.th unassigned job in the set of jobs on each machine in all batches capable of containing the y.sup.th unassigned job, and then selecting a batch having a minimum remaining capacity, and assigning the y.sup.th unassigned job to the selected batch; if the remaining space of all batches cannot contain the y.sup.th unassigned job currently, placing the y.sup.th unassigned job in a new batch having a batch capacity of c.sub.i, and assuming y=y+1; and step 3: repeating the step 2 until all jobs in the set of jobs are assigned to corresponding batches, where the processing time for each batch is determined by the maximum processing time for the jobs in the batch.

5. A system for batch scheduling uniform parallel machines with different capacities based on an improved genetic algorithm, comprising: a calculation module configured to: step 1: inputting the capacity of each machine and the processing time for each job, setting improved genetic algorithm parameters including the maximum number of iterations t.sub.max, a globally optimal solution gbest and the number of iterations t=1; step 2: initializing a population, and defining the gene of the h.sup.th chromosome among total Q chromosomes as X.sub.h=(x.sub.h.sup.1,x.sub.h.sup.2,. . . ,x.sub.h.sup.d,. . . ,x.sub.h.sup.n), h=1,2, . . . , Q, where x.sub.h.sup.d represents the gene of the h.sup.th chromosome in the d.sup.th dimension and indicates that the d.sup.th job is assigned to the (x.sub.h.sup.d).sup.th machine; step 3: generating an initial solution by a heuristic algorithm, and using the initial solution as a first chromosome in the population; step 4: performing a local search strategy on the population to improve the quality of the population; step 5: calculating a fitness value for each solution in the population, updating the globally optimal solution, and assigning the minimum fitness value to gbest; step 6: randomly selecting two solutions X.sub.h.sub.2 and X.sub.h.sub.1 from the population, comparing the fitness values of the two solutions, and using the solution having a larger fineness value as a first parent solution, and repeating this operation to generate another parent solution; step 7: setting a variable h=1; determining whether rand <0.5 is satisfied, where rand is a random number within [0,1]; if so, selecting the h.sup.th gene of the first parent solution as the h.sup.th gene of a filial generation; if not, selecting the h.sup.th gene of the second parent solution as the h.sup.th gene of the filial generation; assuming h=h+1, and repeating this step until h>n, so as to generate a new chromosome; step 8: repeating the step 7 to generate Q filial solutions, and calculating a fitness value for each filial solution; step 9: sequencing the original population and the filial population in a non-descending order of the fitness values; and selecting first N.sub.s chromosomes in the original population and first QN.sub.s chromosomes in the filial population to form a new population; and step 10: sequencing the new population in a non-descending order of the fitness values, and randomly generating N.sub.m chromosomes to replace last N.sub.m chromosomes in the new population so as to generate a next-generation population, where t=t+1; and an output module configured to perform step 11: determining whether tt.sub.max is satisfied; if so, returning to the step 4; if not, ending the algorithm, and outputting the globally optimal solution gbest and the optimal processing task assignment and the batching mode and batch processing sequences on each machine.

6. The system according to claim 5, wherein the step 3 comprises: step 31: sequencing all jobs in a non-ascending order of the processing time to obtain a set of sequenced jobs; step 32: sequencing all machines in a non-ascending order of the processing speed, and sequencing the machines in a non-ascending order of the capacities of the machines if the processing speed is identical; step 33: assuming j=1, C.sub.j[i]=0, A.sub.i=0 where C.sub.j[i] represents a completion time for a job j on a machine i, and represents an idle time for the machine i; step 34: calculating $C_{j} [i] = A_{i} + \frac{p_{j}}{v_{i .Math.}}, i = 1, .Math. .Math., m,$ where p.sub.j represents a processing time for the j.sup.th job, and v.sub.i represents a processing speed of the i.sup.th machine; step 35: selecting a machine having the minimum C.sub.j[i] as a machine min, and assuming A.sub.min=C.sub.j[min] and j=j+C.sub.min; step 36: if j<n, assigning jobs jC.sub.min to j1 to the machine min, and executing the step 34; or otherwise, assigning all unassigned jobs in the set of jobs to the machine min, and executing a step 37; and step 37: returning C.sub.max=max.sub.im{A.sub.i}, and ending the algorithm.

7. The system according to claim 5, wherein the step 4 comprises: step 41: sequencing batches of the machines in a non-ascending order of the batch processing time, and sequencing jobs in the batches in a non-ascending order of the processing time; step 42: sequencing the machines in a non-ascending order of the completion time, and assuming i=1,h=m, where the completion time for each machine is a completion time for the last batch on the machine; step 43: selecting the i.sup.th machine as a machine i, and selecting the h.sup.th machine as a machine h; step 44: if h>1, executing a step 45; or otherwise, executing a step 48; step 45: selecting any batch b on the machine i, and selecting any batch f on the machine h; step 46: if there is a job j in the batch f, and P.sub.j<P.sup.b and P.sup.bP.sup.f are satisfied, exchanging the job j with the first job in the batch b, and executing a step 47; or otherwise, assuming h=h1, and executing the step 44, where P.sup.b represents the processing time for the batch b; step 47: sequencing the jobs in the batches b and f in a non-ascending order of the processing time, and executing the step 45; and step 48: ending the search.

8. The system according to claim 5, wherein the calculation module is further used for calculating the fitness of an individual by the following steps: step 1: for X.sub.k=(x.sub.1,x.sub.2, . . . ,x.sub.h, . . . ,x.sub.n) assigning the h.sup.th job to the (x.sub.h).sup.thmachine to obtain a set of jobs on each machine; step 2: temporarily placing the y.sup.th unassigned job in the set of jobs on each machine in all batches capable of containing the y.sup.th unassigned job, and then selecting a batch having a minimum remaining capacity, and assigning the y.sup.th unassigned job to the selected batch; if the remaining space of all batches cannot contain the y.sup.th unassigned job currently, placing the y.sup.th unassigned job in a new batch having a batch capacity of c.sub.i, and assuming y=y+1; and step 3: repeating the step 2 until all jobs in the set of jobs are assigned to corresponding batches, where the processing time for each batch is determined by the maximum processing time for the jobs in the batch.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0075] Various other advantages and benefits will become apparent to a person of ordinary skill in the art by reading the following detailed description of the preferred embodiments. The drawings are only for the purpose of illustrating the preferred embodiments, but not for the purpose of limiting the present invention. Also, identical components are denoted by identical reference numbers throughout the drawings, in which:

[0076] FIG. 1 is a schematic diagram of a batch scheduling problem of uniform parallel machines with different capacities according to one embodiment of the present invention;

[0077] FIG. 2 is a schematic flowchart of a method for batch scheduling uniform parallel machines with different capacities based on an improved genetic algorithm according to one embodiment of the present invention; and

[0078] FIG. 3 is a schematic structure diagram of a system for batch scheduling uniform parallel machines with different capacities based on an improved genetic algorithm according to one embodiment of the present invention.

DETAILED DESCRIPTION OF THE PRESENT INVENTION

[0079] The technical solutions in the embodiments of the present invention will be clearly and completely described as below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only a part of, not all of, the embodiments of the present invention. All other embodiments obtained by a person of ordinary skill in the art based on the embodiments of the present invention without paying any creative effort shall fall into the protection scope of the present invention.

[0080] Various embodiments of the present invention are mainly to solve the batch scheduling problem of uniform parallel machines with different capacities, determine a machine to which job are to be assigned, and determine the batching mode and batch processing sequences on this machine, so as to minimize the makespan. Based on the natural of the problem, an effective algorithm is provided to solve this combinatorial optimization problem and facilitate the improvement of the production efficiency.

[0081] For ease of understanding, the problem to be solved by the embodiments of the present invention will be described below in detail with reference to FIG. 1.

[0082] As shown in FIG. 1, the batch scheduling problem of uniform parallel machines with different capacities is to minimize the makespan. This problem is described as follows: a set of tasks J={J.sub.1,J.sub.2,J.sub.3, . . . J.sub.n}) containing N jobs to be processed on m parallel batch processing machines is provided. Different jobs are different in processing time but identical in unit size. The processing time is denoted by P.sub.j(j=1,2, . . . , n). The description will be given under the following assumption:

[0083] (1) all jobs and machines get ready at moment 0, wherein the jobs are identical in unit size but different in processing time, and the batch processing machines are different in capacity and processing speed;

[0084] (2) all the jobs are compatible, a plurality of jobs can be processed in a same batch if the capacity of the machine is enough, and the time for processing the batch is determined by the job with the longest processing time in the batch and the processing machine; and

[0085] (3) the process of processing each batch is not allowed to be interrupted, and any job is not allowed to exit from or join in the process.

[0086] On this basis, an embodiment of the present invention provides a method for batch scheduling uniform parallel machines with different capacities based on an improved genetic algorithm, with reference to FIG. 2, including:

[0087] step 1: inputting the capacity of each machine and the processing time for each job, setting improved genetic algorithm parameters including the maximum number of iterations t.sub.max, a globally optimal solution gbest and the number of iterations t=1;

[0088] step 2: initializing a population, and defining the gene of the h.sup.th chromosome among total Q chromosomes as X.sub.h=(x.sub.h.sup.1,x.sub.h.sup.2, . . . ,x.sub.h.sup.d, . . . ,x.sub.h.sup.n), h=1,2, . . . , Q, where x.sub.h.sup.d represents the gene of the h.sup.th chromosome in the dimension and indicates that the d.sup.th job is assigned to the (x.sub.h.sup.d).sup.th machine;

[0089] step 3: generating an initial solution by a heuristic algorithm, and using the initial solution as a first chromosome in the population;

[0090] step 4: performing a local search strategy on the population to improve the quality of the population;

[0091] step 5: calculating a fitness value for each solution in the population, updating the globally optimal solution, and assigning the minimum fitness value to gbest;

[0092] step 6: randomly selecting two solutions X.sub.h.sub.2 and X.sub.h.sub.1 from the population, comparing the fitness values of the two solutions, and using the solution having a larger fineness value as a first parent solution, and repeating this operation to generate another parent solution;

[0093] step 7: setting a variable h=1; determining whether rand <0.5 is satisfied, where rand is a random number within [0,1]; if so, selecting the h.sup.th gene of the first parent solution as the h.sup.th gene of a filial generation; if not, selecting the h.sup.th gene of the second parent solution as the h.sup.th gene of the filial generation; assuming h=h+1, and repeating this step until h>n, so as to generate a new chromosome;

[0094] step 8: repeating the step 7 to generate Q filial solutions, and calculating a fitness value for each filial solution;

[0095] step 9: sequencing the original population and the filial population in a non-descending order of the fitness values; and selecting first N.sub.s chromosomes in

[0096] the original population and first QN.sub.s chromosomes in the filial population to form a new population;

[0097] step 10: sequencing the new population in a non-descending order of the fitness values, and randomly generating N.sub.m chromosomes to replace last N.sub.m chromosomes in the new population so as to generate a next-generation population, where t=t+1; and

[0098] step 11: determining whether tt.sub.max is satisfied; if so, returning to the step 4; if not, ending the algorithm, and outputting the globally optimal solution gbest as well as the optimal processing task assignment and the batching mode and batch processing sequences on each machine.

[0099] In a specific implementation, the generating an initial solution X_1 by a heuristic algorithm in the step 3 may be implemented in various embodiments, where an optional embodiment includes the following steps:

[0100] step 31: sequencing all jobs in a non-ascending order of the processing time to obtain a set of sequenced jobs;

[0101] step 32: sequencing all machines in a non-ascending order of the processing speed, and sequencing the machines in a non-ascending order of the capacities of the machines if the processing speed is identical;

[0102] step 33: assuming j=1, C.sub.j[i]=0, A.sub.i=0 and i=1, . . . , m, where C.sub.j[i] represents a completion time for a job j on a machine i, and A.sub.i represents an idle time for the machine i;

[0103] step 34: calculating

[00003] $C_{j} [i] = A_{i} + \frac{p_{j}}{v_{i .Math.}}, i = 1, .Math. .Math., m;$

[0104] step 35: selecting a machine having the minimum C.sub.j[i] as a machine min, and assuming A.sub.min=C.sub.j[min] and j=j+C.sub.min;

[0105] step 36: if j<n, assigning jobs jC.sub.min to j1 (total C.sub.min jobs) to the machine min, and executing the step 34; or otherwise, assigning all unassigned jobs in the set of jobs to the machine min, and executing a step 37; and

[0106] step 37: returning C.sub.max=max.sub.um{A.sub.i}, and ending the algorithm.

[0107] In a specific implementation, the performing a local search strategy on the population in the step 4 may be implemented in various embodiments, where an optional embodiment includes the following steps:

[0108] step 41: sequencing batches of the machines in a non-ascending order of the batch processing time, and sequencing jobs in the batches in a non-ascending order of the processing time;

[0109] step 42: sequencing the machines in a non-ascending order of the completion time (where the completion time for each machine is a completion time for the last batch on the machine), and assuming i=1, h=m;

[0110] step 43: selecting the i.sup.th machine as a machine i, and selecting the h.sup.th machine as a machine h;

[0111] step 44: if h>1, executing a step 45; or otherwise, executing a step 48;

[0112] step 45: selecting any batch b on the machine i, and selecting any batch f on the machine h;

[0113] step 46: if there is a job j in the batch f, and P.sub.j<P.sup.b and P.sup.bP.sup.f are satisfied, exchanging the job j with the first job in the batch b, and executing a step 47; or otherwise, assuming h=h1, and executing the step 44;

[0114] step 47: sequencing the jobs in the batches b and f in a non-ascending order of the processing time, and executing the step 45; and

[0115] step 48: ending the search.

[0116] In a specific implementation, in the method provided by the embodiment of the present invention, the fitness of an individual may be calculated by the following steps:

[0117] step 1: for X.sub.k=(x.sub.1,x.sub.2, . . . ,x.sub.h, . . . ,x.sub.n), assigning the h.sup.th job to the (x.sub.h).sup.th machine to obtain a set of jobs on each machine;

[0118] step 2: temporarily placing the y.sup.th unassigned job in the set of jobs on each machine in all batches capable of containing this job, selecting a batch having a minimum remaining batch capacity after this job is placed in the batch, and assigning this job to the selected batch; if the remaining space of all batches cannot contain the y.sup.th unassigned job currently, placing this job in a new batch having a batch capacity of c.sub.i, and assuming y=y+1; and

[0119] step 3: repeating the step 2 until all jobs in the set of jobs are assigned to corresponding batches, where the processing time for each batch is determined by the maximum processing time for the jobs in the batch.

[0120] The embodiment of the present invention has the following beneficial effects.

[0121] 1. In the embodiment of the present invention, in view of the batch scheduling problem of uniform parallel machines with different capacities, jobs are distributed to machines by encoding by an improved genetic algorithm, and a corresponding batching strategy and a batch scheduling strategy are proposed according to the natural of the problem to obtain a fitness value of a corresponding individual; then, the quality of the solution is improved by a local search strategy; and, a crossover operation is performed on a population based on the fitness of the solution, and the population is continuously updated by repetitive iteration to eventually obtain an optimal solution. The improved genetic algorithm is a high-efficiency algorithm in terms of convergence rate and convergence effect. By this algorithm, the batch scheduling of uniform parallel machines with different capacities is realized, the production efficiency of enterprises is improved, the cost is reduced for enterprises, and the service level of enterprises is enhanced.

[0122] 2. In the embodiment of the present invention, by using a heuristic method during the generation of an initial solution, the quality of the initial population is ensured; and, by providing an effective local search strategy based on the natural of the problem, and by adjusting and improving the population after the generation of the population, the quality of parent solutions in the crossover operation is improved, the convergence capability and the convergence speed of the algorithm are improved, it is advantageous for the escape of the algorithm from the local optimization, and the diversity of the population is ensured.

[0123] 3. In the embodiment of the present invention, in view of the problems of insufficient local convergence and premature convergence of the genetic algorithm, a population update strategy is provided based on the original population, cross-genes and immigrants, and both the inheritance of excellent individuals and the diversity of the population are taken into consideration. Accordingly, the problem of premature convergence of the genetic algorithm is solved, and the search efficiency of the algorithm is improved effectively.

[0124] Based on the same concept, another embodiment of the present invention further provides a system for batch scheduling uniform parallel machines with different capacities based on an improved genetic algorithm, with reference to FIG. 3, including:

[0125] a calculation module 21 used for:

[0126] step 1: inputting the capacity of each machine and the processing time for each job, setting improved genetic algorithm parameters including the maximum number of iterations t.sub.max, a globally optimal solution gbest and the number of iterations t=1.

[0127] step 2: initializing a population, and defining the gene of the h.sup.th chromosome among total Q chromosomes as X.sub.h=(x.sub.h.sup.1,x.sub.h.sup.2, . . . ,x.sub.h.sup.d, . . . ,x.sub.h.sup.n), h=1,2, . . . , Q, where x.sub.h.sup.d represents the gene of the h.sup.th chromosome in the d.sup.th dimension and indicates that the d.sup.th job is assigned to the (x.sub.h.sup.d).sup.th machine;

[0128] step 3: generating an initial solution by a heuristic algorithm, and using the initial solution as a first chromosome in the population;

[0129] step 4: performing a local search strategy on the population to improve the quality of the population;

[0130] step 5: calculating a fitness value for each solution in the population, updating the globally optimal solution, and assigning the minimum fitness value to gbest;

[0131] step 6: randomly selecting two solutions X.sub.h.sub.2 and X.sub.h.sub.1 from the population, comparing the fitness values of the two solutions, and using the solution having a larger fineness value as a first parent solution, and repeating this operation to generate another parent solution;

[0132] step 7: setting a variable h=1; determining whether rand <0.5 is satisfied, where rand is a random number within [0,1]; if so, selecting the h.sup.th gene of the first parent solution as the h.sup.th gene of a filial generation; if not, selecting the h.sup.th gene of the second parent solution as the h.sup.th gene of the filial generation; assuming h=h+1 and repeating this step until h>n, so as to generate a new chromosome;

[0133] step 8: repeating the step 7 to generate Q filial solutions, and calculating a fitness value for each filial solution;

[0134] step 9: sequencing the original population and the filial population in a non-descending order of the fitness values; and selecting first N.sub.s chromosomes in the original population and first QN.sub.s chromosomes in the filial population to form a new population; and

[0135] step 10: sequencing the new population in a non-descending order of the fitness values, and randomly generating N.sub.m chromosomes to replace last N.sub.m chromosomes in the new population so as to generate a next-generation population, where t=t+1; and

[0136] an output module used for: step 11: determining whether tt.sub.max is satisfied; if so, returning to the step 4; if not, ending the algorithm, and outputting the globally optimal solution gbest as well as the optimal processing task assignment and the batching mode and batch processing sequences on each machine.

[0137] Optionally, the step 3 of generating an initial solution by a heuristic algorithm executed by the calculation module 21 includes the following steps:

[0138] step 31: sequencing all jobs in a non-ascending order of the processing time to obtain a set of sequenced jobs;

[0139] step 32: sequencing all machines in a non-ascending order of the processing speed, and sequencing the machines in a non-ascending order of the capacities of the machines if the processing speed is identical;

[0140] assuming j=1, C.sub.j[i]=0, A.sub.i=0 and i=1, . . . , m, where C.sub.j[i] represents a completion time for a job j on a machine i, and A.sub.i represents an idle time for the machine i;

[0141] step 34: calculating

[00004] $C_{j} [i] = A_{i} + \frac{p_{j}}{v_{i .Math.}}, i = 1, .Math. .Math., m;$

[0142] step 35: selecting a machine having the minimum C.sub.j[i] as a machine min, and assuming A.sub.min=C.sub.j[min] and j=j+C.sub.min;

[0143] step 36: if j<n, assigning jobs jC.sub.min to j1 (total C.sub.min jobs) to the machine min, and executing the step 34; or otherwise, assigning all unassigned jobs in the set of jobs to the machine min, and executing a step 37; and

[0144] step 37: returning C.sub.max=max.sub.im{A.sub.i}, and ending the algorithm.

[0145] Optionally, the step 4 of performing a local search strategy on the population executed by the calculation module 21 specifically includes:

[0146] step 41: sequencing batches of the machines in a non-ascending order of the batch processing time, and sequencing jobs in the batches in a non-ascending order of the processing time;

[0147] step 42: sequencing the machines in a non-ascending order of the completion time (where the completion time for each machine is a completion time for the last batch on the machine), and assuming i=1, h=m;

[0148] step 43: selecting the i.sup.th machine as a machine i, and selecting the h.sup.th machine as a machine h;

[0149] step 44: if h>1, executing a step 45; or otherwise, executing a step 48;

[0150] step 45: selecting any batch b on the machine i, and selecting any batch f on the machine h;

[0151] step 46: if there is a job j in the batch f, and P.sub.j<P.sup.b and P.sup.bP.sup.f are satisfied, exchanging the job j with the first job in the batch b, and executing a step 47; or otherwise, assuming h=h1 and executing the step 44;

[0152] step 47: sequencing the jobs in the batches b and f in a non-ascending order of the processing time, and executing the step 45; and

[0153] step 48: ending the search.

[0154] Optionally, the calculation module 21 is further used for calculating the fitness of an individual by the following steps:

[0155] step 1: for X.sub.k=(x.sub.1,x.sub.2, . . . ,x.sub.h, . . . ,x.sub.n) assigning the h.sup.th job to the (x.sub.h).sup.th machine to obtain a set of jobs on each machine;

[0156] step 2: temporarily placing the y.sup.th unassigned job in the set of jobs on each machine in all batches capable of containing this job, selecting a batch having a minimum remaining batch capacity after this job is placed in the batch, and assigning this job to the selected batch; if the remaining space of all batches cannot contain the y.sup.th unassigned job currently, placing this job in a new batch having a batch capacity of c.sub.i, and assuming y=y+1; and

[0157] step 3: repeating the step 2 until all jobs in the set of jobs are assigned to corresponding batches, where the processing time for each batch is determined by the maximum processing time for the jobs in the batch.

[0158] With the system provided in this embodiment of the present invention, an approximately optimal solution can be obtained in view of the batch scheduling problem of uniform parallel machines with different capacities, so that the production cost is reduced for enterprises and the service level of enterprises is enhanced.

[0159] An embodiment of the present invention further discloses a computer program product which includes computer programs. The computer programs include program instructions that, when executed by a computer, enable the computer to execute the method according to the above method embodiments, for example, the method described in the first aspect.

[0160] A lot of specific details have been described in the specification provided herein. However, it can be appreciated that the embodiments of the present invention may be practiced without these specific details. In some examples, well-known methods, structures and techniques have not been shown in detail so as not to obscure the understanding to this specification.

[0161] Similarly, it should be appreciated that in the above description of exemplary embodiments of the present invention, various features of the present invention are sometimes combined 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 disclosure is not to be interpreted as reflecting an intention that the claimed embodiments of the invention require more features than those expressly recited in each claim. Rather, as reflected by the following claims, inventive aspects are less than all features of a single foregoing embodiment. Thus, the claims following the specific implementation mode are hereby expressly incorporated herein just as each claim itself is a separate embodiment of the present invention.

METHOD AND SYSTEM FOR BATCH SCHEDULING UNIFORM PARALLEL MACHINES WITH DIFFERENT CAPACITIES BASED ON IMPROVED GENETIC ALGORITHM

Inventors

Cpc classification

Classification Explorer

G06F9/46

PHYSICS

Classification Explorer

G06Q50/04

PHYSICS

Classification Explorer

Y02P90/02

GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

Classification Explorer

Y02P90/30

GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

Classification Explorer

G06F9/4881

PHYSICS

Classification Explorer

G05B2219/39167

PHYSICS

Classification Explorer

G05B2219/32091

PHYSICS

Classification Explorer

G06Q10/04

PHYSICS

Classification Explorer

G06N3/126

PHYSICS

Classification Explorer

G06F9/5066

PHYSICS

Classification Explorer

G05B19/41865

PHYSICS

International classification

Classification Explorer

G05B19/418

PHYSICS

Classification Explorer

G06N3/12

PHYSICS

Classification Explorer

G06Q10/04

PHYSICS

Classification Explorer

G06Q50/04

PHYSICS

Abstract

Claims

Description