CN113191548A - Production scheduling method - Google Patents

Abstract

The invention discloses a production scheduling method, which considers two factors of a human interactive learning effect and processing interruptible, combines a heuristic rule design to improve an elite genetic algorithm, aims to obtain an optimal task scheduling scheme of a single working group and realizes the effective utilization of workers with different skill levels in the working group and the optimal scheduling target. Compared with the traditional model and method, the method disclosed by the invention is suitable for the basic requirements of the actual production situation, and can realize scientific distribution of tasks in a single working group.

Description

Production scheduling method

Technical Field

The invention belongs to the technical field of production scheduling, and particularly relates to a production scheduling method.

Background

The single-workgroup production scheduling problem refers to a scheduling problem which is provided with a workgroup unit and consists of a plurality of workers, and the scheduling problem comprises how to reasonably arrange task processing sequences under a determined personnel structure and reasonably distribute the workers for each task so as to improve the processing efficiency of the whole workgroup. In the fields of high-end equipment manufacturing, software project development, computer resource management and the like, China is limited by factors such as low technical maturity, large workload, complex production technology and processing technology or limited computing resources, high information exchange frequency and the like of newly-researched projects, a task scheduling mode taking a working group as a unit is widely adopted, the group processing of multiple persons leads to the generation of interactive learning effect of the persons, the processing process of the persons is interrupted due to periodic rest, and the scheduling research on the working group level can effectively solve the problem of low efficiency in the fields of high-end equipment manufacturing scheduling, software project scheduling, computer resource management and the like.

The related scheduling problems of the workgroup have been researched by a plurality of researchers, from the concept and structure of the Seru, the distribution of multi-skill workers in the production unit of the workgroup, and the labor-intensive production unit in recent years, but the research considering the scheduling constraint and characteristic of the single workgroup staff is less, and a plurality of models and methods are provided in the scheduling problem research of the learning effect, but the influence of the individual on the whole learning effect is usually ignored. When the work group finishes the work task, the interaction learning effect exists among the team members, and the resources can be better configured to realize the optimized scheduling by considering the factors of the scale of the work group, the structure of the personnel and the like.

Disclosure of Invention

In view of the above-mentioned shortcomings of the prior art, an object of the present invention is to provide a production scheduling method, so as to solve the problem in the prior art that the scheduling scheme is inaccurate due to the fact that the learning effect and the personnel processing interruption are not considered for the production scheduling of a single working group.

In order to achieve the purpose, the technical scheme provided by the invention is as follows: an examination production scheduling method comprises the following steps:

1) researching a production scheduling scene, firstly acquiring basic information of workers and basic information of tasks, then grading workers of a working group, initializing and generating a problem object;

2) problem parameters and variables are defined and established to minimize the maximum completion time (minC)_max) A mathematical model that is a scheduling objective;

3) realizing the mathematical model by using an elite genetic algorithm, coding a task processing sequence to generate an initial scheduling scheme population, and randomly generating an initial population with N individuals in a coding specified range;

4) calculating the fitness through personnel allocation and personnel processing break point identification, and reserving the individual with the best fitness;

5) generating a new population, carrying out selection, crossing and variation through elite reservation to generate a progeny population, and calculating the fitness value of individuals of the progeny population;

6) updating the elite individual, if the optimal individual of the filial generation is better than the elite individual, proving that the filial generation population finishes the evolution, and at the moment, replacing the worst individual of the filial generation with the elite individual of the parent generation, wherein the optimal individual of the filial generation becomes a new elite individual;

7) if the genetic algebra is larger than the initial evolution algebra, the iteration is terminated, the optimization is quitted, and the elite individuals and the scheduling information are output; otherwise, continuing to execute the step 4).

Further, the parameters and variables in step 2) specifically include: a group of workers M machine a group of workpieces J, h represents a worker serial number, h is 1,2, … …, l, k represents a workpiece serial number, k is 1,2, … …, n, and workers with high skill level have a learning rate alpha_h，h＝1,2,……,m^HWorkers with low skill level have a learning rate beta_h，h＝m^H+1,m^H+2, … …, l; workpiece J_kNumber of persons processed according to basic demand JM_k，[P_k]For average population, P_kIn order to achieve an actual processing time,

for the complete processing time after consideration of the learning effect at any time, S_kTo start the working time, C_kIn order to complete the time-out,

in order to distribute a high level of workers,

to a low number of workers assigned, a_eh、b_ehFor worker M_hE-th start interruption time and e-th end interruption time, e being 1,2, …, θ_hT represents the time of change of the state of the production staff, F represents the rank after rearrangement of the interruption time,

a^[F]means for producing all of the workpiecesA of the worker_eh、b_ehIn a non-decreasing order, a^[0]For the start of the machining of the workpiece, a^[f]The time when the personnel state change occurs for the last time before the workpiece is finished. The single workgroup scheduling model is constructed with the following three decision variables:

worker M_hMachining workpiece J_kTotal time of (1), wherein

f＝max{e|a_eh·[y_kh]≤C_k}；

Further, the mathematical model established in step 2) is:

the single workgroup scheduling mixed integer programming model is as follows:

(21) an objective function: minimizing maximum completion time

min C_max

(22) Constraint 1: limiting each worker to process only one workpiece at the same time:

(23) constraint 2: restraining worker M_hIs distributed to the workpiece J_kIn the work J_kThe worker may not be assigned to other workpieces before completion:

(24) constraint 3: each workpiece is limited to be processed only once, and the number of processed workpieces is equal to the number of required workpieces:

(25) constraint 4: limiting workpiece J_kThe number of workers in the processing state at the same time t cannot exceed the distributed high-level total number of workers:

(26) constraint 5: limiting workpiece J_kThe number of workers in the processing state at the same time t cannot exceed the total number of distributed workers at a low level:

(27) constraint 6: defining a workpiece J_kMachining time P_kThe calculation formula of (2):

(28) constraint 7: limiting the completion time to be equal to the sum of the starting time and the actual processing time of the workpiece:

C_k＝S_k+P_k,k＝1,2,…,n

(29) constraint condition 8: workpiece J processed by limiting workers_kThe total time of (a) is not more than the actual machining time of the workpiece:

x_kh≤P_k,k＝1,2,…,n；h＝1,2,…,l

(210) constraint 9: limiting workpiece J_kThe time for starting to process is longer than that of the previous workpiece J_k-1Completion time:

C_k-1≤S_k,k＝1,2,…,n

(211) constraint 10: limiting the same worker to be allocated to other workpieces for processing, wherein the starting time of the worker for processing the workpiece is not less than the ending time of the original workpiece:

S_i[y_ih]+P_i[y_ih]+P_i+1[y_i+1,h]+…+P_j[y_j-1,h]≤S_j[y_jh],i＝1,2,…,n；j＝1,2,…,n；i＜j；h＝1,2,…,l

compared with the traditional scheduling model considering the learning effect, the model has the following characteristics. Firstly, the human interaction learning effect representation model proposed based on the Jiang learning effect representation model based on the standard processing time and the workers is the worker M_hIndependently process workpiece J_kBasic human being [ P_kh]Constraint 6-constraint 10 is a non-linear constraint; secondly, due to the existence of the interruption interval, the machining time P defined based on the constraint condition 6_kCalculating the moment a at which the personnel state change occurs last time before the workpiece is finished and can be found only by judging and iterating for multiple times^[f]Where f is max { e | a ═ m_eh·[y_kh]≤C_k}; finally, the invention needs personnel allocation to calculate the workpiece processing time before the group processing of a plurality of people and the interruption of the personnel processing process, and adds a decision variable x for identifying the workpiece processing information at the interruption point_khAnd y_khtBoth decision variables are related to the processing staff to which the work piece is actually assigned, where x_khIs equal to max { e | a_eh·[y_kh]≤C_kI.e. f, y_khtIs equal to

The total number of constraints is equal to:

therefore, the mathematical model is not easy to solve, and the invention provides an e-GA solving method based on heuristic rules.

Further, the encoding method in step 3) is as follows: the method adopts permutation coding to code generation processing workpieces in sequence, all the generation processing workpieces are arranged in a row to be used as a chromosome, and each workpiece corresponds to a gene on the chromosome.

Further, the process of calculating the individual fitness through personnel allocation and personnel processing break point identification in the step 4) is as follows:

(41) updating the total learning duration of staff of a working group, and grouping the workers according to the learning level;

(42) according to the basic demand number JM of the workpieces_kDetermining

And

and calculating that no processing by personnel occurs

Ideal processing time for time interruption;

(43) judgment of a_eh[y_kh]Or b_eh[y_kh]And

in which

(44) Searching for workers who interrupt the machining according to the interrupt interval, updating the interrupt point set, and recalculating the ideal machining

Time, repeating step (42);

(45)count＝f＝max{e|a_eh·[y_kh]≤C_kand when the interruption interval list is updated, updating the processing time of workers and updating the interruption interval list.

(46) At the beginning of the processing time of a^[0]＝S_k＝C_k-1During the actual machining of the workpiece, a^[0]Is equal to workpiece J_kIs equal to the finish machining time of the (k-1) th workpiece, a^[f]Indicating the time of last occurrence of personnel state change before completion of the workpiece, and deducing the total processing time of the workpieceIs formed by

(47) Repeating the step (41) -the step (46), and calculating the completion time of the workpiece in each individual scheme to further obtain individual fitness;

in step (44)

Computing to characterize a model based on standard processing time and worker learning effects

Based on this, the workpiece J is derived_kThe complete processing time after considering the learning effect at any time:

further, the step 5) specifically includes: selecting operation is carried out by adopting an elite selection strategy method; performing cross operation by adopting a partial matching cross method; performing mutation operation by inverse mutation method

Further, the selecting operation in the step 5) is as follows:

(51) when the generation t is reached, a (t) in the population is the optimal individual;

(52) setting A (t +1) as a new generation group, and selecting the optimal individual in A (t + 1);

(53) if there are no individuals in A (t +1) that are superior to a (t), then a (t) is added to A (t +1) as the n +1 th individual of A (t +1) (n is the population size).

Further, the interleaving operation in step 5) is as follows:

(54) determining a parent initial population;

(55) randomly generating a number less than the length of the parent chromosome;

(56) interchanging segments in the chromosome corresponding to the length and position;

(57) keeping the exchanged segments still, finding the repeated value in the segments which are not exchanged, and then finding the element of the corresponding position in the replaced part of the parent to replace.

Further, the mutation operation in the step 5) is as follows: randomly selecting two points on the parent chromosome code as reversal points, and reversely ordering the genes between the two reversal points to obtain the chromosome after mutation.

The invention has the beneficial effects that: the invention considers the learning effect phenomenon and the processing interruptible phenomenon existing in the actual production. The invention provides a single workgroup scheduling problem considering the human interactive learning effect, a single workgroup scheduling model considering the human interactive learning effect and processing interruptible is constructed facing the problem, an e-GA model solving method based on heuristic rules is provided, and finally, the effectiveness of the constructed model and algorithm is demonstrated through different-scale example simulation. Firstly, analyzing and representing the human interactive learning effect in a workgroup unit, considering the processing interruptible phenomenon in the practical problem, and realizing the reduction of relevant data errors such as the working hour and the like of a single workgroup scheduling problem and the optimal matching of key resources of the workgroup; secondly, a single working group scheduling model and an algorithm which consider the interactive learning effect of personnel and can be interrupted in processing are constructed, the organic combination of the personnel allocation of the single working group and the workpiece scheduling is realized, the processing efficiency of the production system taking the working group as a processing unit is improved, and the problem that the learning level difference between people is ignored when the working group is taken as a whole in the past is solved; and finally, implementing e-GA-based computational simulation by utilizing python, analyzing the influence of the staff structure of a working group on a scheduling result in detail, and providing guidance for determining the replacement ratio in actual production.

Drawings

FIG. 1 is a flow chart of the method of the present invention.

Fig. 2 is a schematic diagram illustrating the calculation of man-hour for interrupting the processing of a workpiece k by a person during the task processing of a certain factory.

FIG. 3 is a Gantt chart of optimal scheduling under different personnel structures in a certain plant task processing process after calculation by the method.

FIG. 4 is an iterative graph of the calculation result of the method, wherein the ratio of the personnel in the task processing process of a certain plant is 0: 10.

FIG. 5 is an iterative graph of the calculated results of the method with a personnel ratio of 2:8 in the process of task processing of a certain plant.

FIG. 6 is an iterative diagram of the calculation result of the factory task processing process with a 5:5 ratio of personnel calculated by the method.

FIG. 7 is an iterative graph of the calculation result of the method, wherein the calculated personnel ratio of the task processing process of a certain plant is 8: 2.

FIG. 8 is an iterative graph of the calculation result of the method, wherein the calculated personnel ratio of the task processing process of a certain plant is 10: 0.

Detailed Description

In order to facilitate understanding of those skilled in the art, the present invention will be further described with reference to the following examples and drawings, which are not intended to limit the scope of the present invention.

Referring to fig. 1, a single workgroup production scheduling method considering human interactive learning effect and processing interruptible is described by constructing a factory task processing procedure example, which includes the following steps:

(1) in the background of enterprise production, a factory task processing process takes a 10-person work group as a scheduling unit, and the basic person of workers independently processing workpieces is [30,80 ]]Randomly distributed, the high-level learning rate is 30% (learning factor is-0.3), the low-level learning rate is 10% (learning factor is-0.1), each worker has 3 interruption intervals, and the interruption intervals are [0,41 ]]The internal fixed step length is 0.5 distribution, the processing number is 1-10 parts, and 10 workpieces J of the same part family exist_k，JM_kAnd [ P_k]See table 1.

TABLE 1 number of basic demands for work and basic man-hours

(2) Problem parameters and variables are defined and established to minimize the maximum completion time (minC)_max) For the mathematical model of the scheduling objective, the parameters and variables in the corresponding example specifically include: a group of workersM processes a group of workpieces J, h represents a worker serial number, h is 1,2, … …, l, k represents a workpiece serial number, k is 1,2, … …, n, and the workers with high skill level have learning rate alpha_h，h＝1,2,……,m^HWorkers with low skill level have a learning rate beta_h，h＝m^H+1,m^H+2, … …, l; workpiece J_kNumber of persons processed according to basic demand JM_k，[P_k]For average population, P_kIn order to achieve an actual processing time,

for the complete processing time after consideration of the learning effect at any time, S_kTo start the working time, C_kIn order to complete the time-out,

in order to distribute a high level of workers,

to a low number of workers assigned, a_eh、b_ehFor worker M_hE-th start interruption time and e-th end interruption time, e being 1,2, …, θ_hT represents the time of change of the state of the production staff, F represents the rank after rearrangement of the interruption time,

a^[F]a representing all workers producing the workpiece_eh、b_ehIn a non-decreasing order, a^[0]For the start of the machining of the workpiece, a^[f]The time when the personnel state change occurs for the last time before the workpiece is finished. The single-working-group scheduling model is constructed by the following three decision variables:

worker M_hMachining workpiece J_kTotal time of (1), wherein

f＝max{e|a_eh·[y_kh]≤C_k}；

The single workgroup scheduling mixed integer programming model is as follows:

(21) an objective function: minimizing maximum completion time

min C_max

(22) Constraint 1: limiting each worker to process only one workpiece at the same time:

(23) constraint 2: restraining worker M_hIs distributed to the workpiece J_kIn the work J_kThe worker may not be assigned to other workpieces before completion:

(24) constraint 3: each workpiece is limited to be processed only once, and the number of processed workpieces is equal to the number of required workpieces:

(25) constraint 4: limiting workpiece J_kThe number of workers in the processing state at the same time t cannot exceed the distributed high-level total number of workers:

(26) constraint 5: limiting workpiece J_kAt the same time t at additionThe number of workers in the low-level worker state cannot exceed the total number of the distributed workers in the low-level worker state:

(27) constraint 6: defining a workpiece J_kMachining time P_kThe calculation formula of (2):

(28) constraint 7: limiting the completion time to be equal to the sum of the starting time and the actual processing time of the workpiece:

C_k＝S_k+P_k,k＝1,2,…,n

(29) constraint condition 8: workpiece J processed by limiting workers_kThe total time of (a) is not more than the actual machining time of the workpiece:

x_kh≤P_k,k＝1,2,…,n；h＝1,2,…,l

(210) constraint 9: limiting workpiece J_kThe time for starting to process is longer than that of the previous workpiece J_k-1Completion time:

C_k-1≤S_k,k＝1,2,…,n

(211) constraint 10: the same worker is restricted from being assigned to other workpieces to be processed, and the worker processes the workpieces

The starting time of the workpiece is not less than the ending time of the original workpiece:

S_i[y_ih]+P_i[y_ih]+P_i+1[y_i+1,h]+…+P_j[y_j-1,h]≤S_j[y_jh],i＝1,2,…,n；j＝1,2,…,n；i＜j；h＝1,2,…,l

(3) and (4) numbering the processing sequence of the workpieces by natural numbers, and arranging the working procedures into a row as a chromosome according to the sequence relation of the processing of the workpieces. Taking chromosome [10, 2, 1, 6, 9, 5, 7, 3, 4, 8] as an example, this chromosome shows that workpiece 10 is machined for the first time,workpiece 2 is machined afterworkpiece 1 is machined,workpiece 1 … is machined afterworkpiece 2 is machined, andworkpiece 8 is machined for the last time.

(31) Producing chromosomes according to the rule, achieving the preset population scale, and finishing initialization.

(32) Calculating the fitness through personnel allocation and personnel processing break point identification: taking an initial population of a chromosome [1, 2, 10, 6, 9, 3, 7, 5, 4, 8] as an example, theworkpiece 1 is first processed, and the fitness value is calculated according to the following steps:

a) updating the total learning duration of the personnel, and grouping the processing workers needed by theworkpiece 1 according to the learning level;

b) number JM of basic demand persons according toworkpiece 1_kDetermining

And

and calculating the ideal processing time when the processing of the personnel is not interrupted;

c) judgment of a_eh[y_kh]Or b_eh[y_kh]And

in which

d) Searching for workers for interrupted processing according to the interruption interval, updating the interruption point set, recalculating the ideal processing time, and repeating the step (42);

e)count＝f＝max{e|a_eh·[y_kh]≤C_kand when the interruption interval list is updated, updating the processing time of workers and updating the interruption interval list.

f) At the beginning of the processing time of a^[0]＝S_k＝C_k-1During the actual machining of the workpiece, a^[0]Is equal to workpiece J_kIs equal to the finish machining time of the (k-1) th workpiece, a^[f]Indicating the last change in personnel status before completion of the workFrom FIG. 2, it is derived that the total processing time of the workpiece is

g) Repeating the step (41) -the step (46), and calculating the completion time of the workpiece in each individual scheme to further obtain individual fitness;

(33) selecting: the selection of population individuals according to the elite retention strategy is performed as follows:

a) when the generation t is reached, a (t) in the population is the optimal individual;

b) setting A (t +1) as a new generation group, and selecting the optimal individual in A (t + 1);

c) if there are no individuals in A (t +1) that are superior to a (t), then a (t) is added to A (t +1) as the n +1 th individual of A (t +1) (n is the population size).

(34) And (3) crossing: the operation of performing cross operation on population individuals according to a partial matching cross method is as follows:

a) parentinitial populations parent 1 andparent 2 are determined as in tables 2 and 3, as follows:

TABLE 2

TABLE 3

b) If the randomly generated number smaller than the length of the chromosome of the parents is 4, the two parents mutually exchange the gene sequences on the 3 rd to 6 th gene positions;

c) by interchanging the fragments corresponding to the length and position in the chromosome, the sequence of the genes in the gene segments [1, 6, 9, 5] in theparent 1 in theparent 2 is [6, 5, 7, 2], which replaces the original gene segment in theparent 1. Theunrerevised child 1 is obtained as in table 4, as follows:

TABLE 4

Similarly, gene segments [6, 5, 7, 2] inparent 2 were recombined in the order ofparent 1 to obtainunrefined offspring 2 as shown in Table 5, as follows:

TABLE 5

d) Revising repeated elements, wherein [7, 2] in theunrerevised child 1 has repeated elements with the exchanged [6, 5, 7, 2], keeping the exchanged segments still, finding repeated values in the segments without exchange, and then finding the elements in the corresponding positions in the exchanged parts of the parent to replace to obtain thechild 1 as shown in table 6, as follows:

TABLE 6

Operating onunrerevised child 2 in the same manner results inchild 2 as in Table 7, as follows:

TABLE 7

And only when the sub-generation fitness is higher than that of the parent generation, the parent generation is replaced, and otherwise, the intersection is carried out again.

(35) Mutation: randomly selecting two points on the parent chromosome code as reversal points, and reversely ordering the genes between the two reversal points to obtain the chromosome after mutation. And replacing the original process operation sequence according to the mutation probability, replacing if the fitness of the new individual is higher than that of the original individual, and if not, mutating again.

(36) Termination criteria: and when the maximum iteration times of the genetic algorithm is reached, the algorithm is ended, and the workpiece scheduling scheme and the personnel allocation scheme with the highest current fitness value are output.

It should be noted that in this embodiment, an algorithm solver is written by python, and in the context of 10 workpieces and 10 workers, 11 groups of examples of different personnel structures are set, and the personnel ratios are 0:10, 1:9, 2:8, 3:7, 4:6, 5:5, 6:4, 7:3, 8:2, 9:1, and 10:0, respectively. In order to improve the solving efficiency, an e-GA algorithm (the population size is 20, the iteration number is 200, the XOVR is 0.9, and Pm is 0.2) is designed for solving. All of the 11 examples converged within the set number of iterations. The processing sequence and the processing time of each optimal scheduling scheme are shown in fig. 3, wherein the proportion of high-level workers from scheme1 to scheme11 is gradually increased, and the maximum completion time of the optimal scheme is gradually shortened along with the increase of the proportion of the high-level workers. The proportion of analysts is 0:10, 2:8, 5:5, 8:2 and 10:0, the iteration times of the optimal solution obtained by the algorithm can be converged in 100 generations under the conditions of different staff structures as shown in the graphs in FIGS. 4-8, and the method can be used for solving the small and medium-scale problems, realizing the convergence fast and achieving the stable solution result and being applicable to the production scheduling problem of actual enterprises.

In addition, an embodiment of the present invention further provides a computer-readable storage medium, where the computer-readable storage medium may store a program, and when the program is executed, the program includes some or all of the steps of any production scheduling method described in the above method embodiments.

In addition, functional units in the embodiments of the present invention may be integrated into one processing unit, or each unit may exist alone physically, or two or more units are integrated into one unit. The integrated unit can be realized in a form of hardware, and can also be realized in a form of a software functional unit.

The integrated unit, if implemented in the form of a software functional unit and sold or used as a stand-alone product, may be stored in a computer readable memory. Based on such understanding, the technical solution of the present invention may be embodied in the form of a software product, which is stored in a memory and includes several instructions for causing a computer device (which may be a personal computer, a server, a network device, or the like) to execute all or part of the steps of the method according to the embodiments of the present invention. And the aforementioned memory comprises: a U-disk, a Read-Only Memory (ROM), a Random Access Memory (RAM), a removable hard disk, a magnetic or optical disk, and other various media capable of storing program codes.

Those skilled in the art will appreciate that all or part of the steps in the methods of the above embodiments may be implemented by associated hardware instructed by a program, which may be stored in a computer-readable memory, which may include: flash Memory disks, Read-Only memories (ROMs), Random Access Memories (RAMs), magnetic or optical disks, and the like.

An exemplary flow chart of a method for implementing a service chain according to an embodiment of the present invention is described above with reference to the accompanying drawings. It should be noted that the numerous details included in the above description are merely exemplary of the invention and are not limiting of the invention. In other embodiments of the invention, the method may have more, fewer, or different steps, and the order, inclusion, function, etc. of the steps may be different from that described and illustrated.

Claims (10)

Translated fromChinese

1.一种生产调度方法，其特征在于,包括步骤如下：1. a production scheduling method, is characterized in that, comprises the steps as follows:1)获取工人基本信息和任务基本信息，然后将工作组人员进行等级划分，初始化并生成问题对象；1) Obtain the basic information of workers and basic tasks, and then divide the work group personnel into levels, initialize and generate problem objects;2)定义问题参数和变量，并建立以最小化最大完工时间为调度目标的数学模型；2) Define the problem parameters and variables, and establish a mathematical model with the scheduling goal of minimizing the maximum completion time;3)利用精英遗传算法实现所述数学模型，对任务处理顺序进行编码，生成初始调度方案种群，在编码规定的范围内随机生成具有N个个体的初始种群；3) using elite genetic algorithm to realize the mathematical model, coding the task processing sequence, generating an initial scheduling scheme population, and randomly generating an initial population with N individuals within the range specified by the coding;4)通过人员分配和人员加工中断点识别计算个体适应度，保留适应度值最高的个体；4) Calculate individual fitness through personnel allocation and personnel processing interruption point identification, and retain the individual with the highest fitness value;5)产生新种群，通过精英保留进行选择、交叉、变异产生子代种群，并计算子代种群个体的适应度值；5) Generate a new population, select, cross, and mutate to generate a progeny population through elite retention, and calculate the fitness value of the progeny population;6)精英个体更新，若子代最优个体比精英个体更优，则证明子代种群完成进化，此时将父代精英个体替代子代最劣个体，子代最优个体成为新的精英个体；6) The elite individual is updated. If the optimal individual of the offspring is better than the elite individual, it proves that the offspring population has completed the evolution. At this time, the elite individual of the parent generation will replace the worst individual of the offspring, and the optimal individual of the offspring will become a new elite individual;7)若遗传代数大于初始进化代数，迭代终止，退出寻优，输出精英个体和调度信息；否则继续执行步骤4)。7) If the genetic algebra is greater than the initial evolution algebra, the iteration is terminated, the optimization is exited, and the elite individuals and scheduling information are output; otherwise, continue to step 4).2.根据权利要求1所述的生产调度方法，其特征在于，所述步骤2)中的参数和变量具体包括：一组工人M加工一组工件J，h表示工人序号，h＝1,2,……,l，k表示工件序号，k＝1,2,……,n，高技能水平工人具有学习率α_h，h＝1,2,……,m^H，低技能水平工人具有学习率β_h，h＝m^H+1,m^H+2,……,l；工件J_k基本需求加工人数JM_k，[P_k]为平均总人时，P_k为实际加工时间，

为任意时刻考虑学习效应后的完整加工时间，S_k为开始加工时间，C_k为完工时间，

为分配的高水平工人数，

为分配的低水平工人数，a_eh、b_eh为工人M_h的第e个开始中断时刻和第e个结束中断时刻，e＝1,2,…,θ_h，t表示生产人员状态变动时刻，F表示中断时间重新排列后的秩，

a^[F]表示生产工件所有工人的a_eh、b_eh按非减序的排列，a^[0]为工件开始加工时间，a^[f]为工件完工之前最后一次发生人员状态变动的时刻。构建的单工作组调度模型中，有以下三个决策变量：2. The production scheduling method according to claim 1, wherein the parameters and variables in the step 2) specifically include: a group of workers M processes a group of workpieces J, h represents the worker serial number, h=1,2 ,...,l,k represent the workpiece serial number, k=1,2,...,n, high-skilled workers have learning rate α_h , h=1,2,...,m^H , low-skilled workers have learning rate α h , h=1,2,...,m H rate β_h , h=m^H +1,m^H +2,...,l; the basic requirement of the workpiece J_k is the number of workers JM_k , when [P_k ] is the average total number of people, P_k is the actual processing time,

is the complete processing time after considering the learning effect at any time, S_k is the starting processing time, C_k is the finishing time,

is the number of high-level workers assigned,

is the number of assigned low-level workers, a_eh , be_eh are the e-th starting interruption time and the e-th ending interruption time of worker M_h , e=1,2,…,θ_h , t represents the state change time of production personnel , F represents the rank after the interruption time rearrangement,

a^[F] represents the non-decreasing order of a_eh and be_eh of all workers producing the workpiece, a^[0] is the time when the workpiece starts to be processed, and a^[f] is the last time the staff state changes before the workpiece is completed. In the constructed single-workgroup scheduling model, there are the following three decision variables:

工人M_h加工工件J_k的总时间，其中

The total time for worker M_h to process workpiece J_k , wheref＝max{e|a_eh·[y_kh]≤C_k}；f=max{e|a_eh ·[y_kh ]≤C_k };

。

.3.根据权利要求1所述的生产调度方法，其特征在于，所述步骤2)中建立的数学模型为：3. production scheduling method according to claim 1, is characterized in that, the mathematical model established in described step 2) is:单工作组调度混合整数规划模型如下：The mixed integer programming model for single-workgroup scheduling is as follows:(21)目标函数：最小化最大完工时间(21) Objective function: minimize the maximum completion timemin C_maxmin C_max(22)约束条件1：限制同一时刻每个工人只能加工一个工件：(22) Constraint 1: Limit each worker to only one workpiece at the same time:

(23)约束条件2：限制工人M_h被分配到工件J_k，在工件J_k完工前该工人不可以被分配其他工件：(23) Constraint 2: restricting worker M_h to be assigned to workpiece J_k , the worker cannot be assigned other workpieces before the completion of workpiece J_k :

(24)约束条件3：限制每个工件只能被加工一次，且加工人数等于工件需求人数：(24) Constraint 3: Restrict each workpiece to be processed only once, and the number of people to be processed is equal to the number of people required for the workpiece:

(25)约束条件4：限制工件J_k在同一时刻t处于加工状态的高水平工人数不能超过分配的高水平总人数：(25) Constraint 4: The number of high-level workers who limit the workpiece J_k to be processed at the same time t cannot exceed the total number of high-level workers assigned:

(26)约束条件5：限制工件J_k在同一时刻t处于加工状态的低水平工人数不能超过分配的低水平总人数：(26) Constraint 5: The number of low-level workers who limit the workpiece J_k to be processed at the same time t cannot exceed the total number of assigned low-level workers:

(27)约束条件6：定义工件J_k加工时间P_k的计算公式：(27) Constraint 6: Define the calculation formula of workpiece J_k processing time P_k :

(28)约束条件7：限制完工时间等于开始时间与工件实际加工时间之和：(28) Constraint 7: Limit the completion time equal to the sum of the start time and the actual processing time of the workpiece:C_k＝S_k+P_k,k＝1,2,…,nC_k =S_k +P_k ,k=1,2,...,n(29)约束条件8：限制工人加工工件J_k的总时间不大于工件的实际加工时间：(29) Constraint 8: Restrict the total time for workers to process workpiece J_k to be no greater than the actual processing time of the workpiece:x_kh≤P_k,k＝1,2,…,n；h＝1,2,…,lx_kh ≤P_k , k=1,2,…,n; h=1,2,…,l(210)约束条件9：限制工件J_k开始加工时间大于上一个工件J_k-1完工时间：(210) Constraint 9: Limit the start processing time of workpiece J_k to be greater than the completion time of the previous workpiece J_k-1 :C_k-1≤S_k,k＝1,2,…,nC_k-1 ≤S_k ,k=1,2,...,n(211)约束条件10：限制同一工人被分配到其他工件进行加工时，工人加工该工件的开始时间不小于原工件结束时间：(211) Constraint 10: When the same worker is restricted to be assigned to other workpieces for processing, the start time of the worker processing the workpiece is not less than the end time of the original workpiece:S_i[y_ih]+P_i[y_ih]+P_i+1[y_i+1,h]+…+P_j[y_j-1,h]≤S_j[y_jh],i＝1,2,…,n；j＝1,2,…,n；i＜j；h＝1,2,…,l。S_i [y_ih ]+P_i [y_ih ]+P_i+1 [y_i+1,h ]+…+P_j [y_j-1,h ]≤S_j [y_jh ],i=1 ,2,...,n; j=1,2,...,n; i<j; h=1,2,...,l.4.根据权利要求1所述的生产调度方法，其特征在于，所述步骤3)中编码方式为：采用排列编码将所有代加工工件按加工顺序进行编码，所有代加工工件排成一列作为一条染色体，每个工件对应染色体上的一个基因。4. production scheduling method according to claim 1, is characterized in that, in described step 3), coding mode is: adopt arrangement coding to encode all substitute processing workpieces in processing order, and all substitute processing workpieces are arranged in a row as a row. Chromosomes, each artifact corresponds to a gene on the chromosome.5.根据权利要求1所述的生产调度方法，其特征在于，所述步骤4)中通过人员分配和人员加工中断点识别计算个体适应度的过程如下：5. production scheduling method according to claim 1, is characterized in that, in described step 4), the process of calculating individual fitness by personnel assignment and personnel processing interruption point identification is as follows:(41)更新工作组人员总学习时长，结合学习水平对工人进行分组；(41) Update the total learning time of the working group members, and group the workers according to their learning levels;(42)根据工件的基本需求人数JM_k确定

和

并计算人员加工不发生中断时的理想加工时间；(42) Determined according to the basic demand for the workpiece JM_k

and

And calculate the ideal processing time without interruption of personnel processing;(43)判断a_eh[y_kh]或b_eh[y_kh]和

count＝0,1,…,num的关系，其中

(43) Judge a_eh [y_kh ] or b_eh [y_kh ] and

The relationship of count=0,1,…,num, where

(44)依据中断区间寻找中断加工的工人，更新中断点集合，重新计算理想加工时间，重复步骤(42)；(44) according to the interruption interval, find the worker who interrupts the processing, update the interruption point set, recalculate the ideal processing time, and repeat step (42);(45)count＝f＝max{e|a_eh·[y_kh]≤C_k}时，更新所有工人的加工时间，更新中断区间列表。(45) When count=f=max{e|a_eh ·[y_kh ]≤C_k }, update the processing time of all workers and update the list of interruption intervals.(46)在开始加工时间为a^[0]＝S_k＝C_k-1的工件实际加工过程中，a^[0]等于工件J_k的开始加工时间，等于第k-1个工件的结束加工时间,a^[f]表示工件完工之前最后一次发生人员状态变动的时刻，推导可以得到该工件的总加工时间为

(46) In the actual machining process of the workpiece whose starting processing time is a^[0] =_Sk =_Ck-1 , a^[0] is equal to the starting processing time of the workpiece Jk, and is equal to the end processing of the_k -1th workpiece Time, a^[f] represents the last time the personnel state changes before the completion of the workpiece, and the total processing time of the workpiece can be obtained by deduction as

(47)重复步骤(41)--步骤(46)，计算每个个体方案中工件的完工时间，进而得到个体适应度；(47) Repeat step (41)--step (46), calculate the completion time of the workpiece in each individual scheme, and then obtain the individual fitness;步骤(44)中

计算以基于标准加工时间和工人的学习效应表征模型

为基础，推导得到工件J_k在任意时刻考虑学习效应后的完整加工时间：In step (44)

Computation to characterize models based on standard processing time and worker learning effects

Based on , the complete machining time of the workpiece J_k after considering the learning effect at any time is derived:

。

.6.根据权利要求1所述的生产调度方法，其特征在于，所述步骤5)具体包括：采用精英选择策略方法进行选择操作；采用部分匹配交叉方法进行交叉操作；采用逆转变异方法进行变异操作。6. The production scheduling method according to claim 1, wherein the step 5) specifically comprises: using an elite selection strategy method to perform a selection operation; using a partial matching crossover method to perform a crossover operation; using a reverse mutation method to perform a mutation operation .7.根据权利要求5所述的生产调度方法，其特征在于，所述步骤5)中的选择操作如下：7. The production scheduling method according to claim 5, wherein the selection operation in the step 5) is as follows:(51)设到第t代时，群体中a(t)为最优个体；(51) When it is set to the t-th generation, a(t) in the population is the optimal individual;(52)设A(t+1)为新一代群体，挑选A(t+1)中的最优个体；(52) Let A(t+1) be the new generation group, and select the best individual in A(t+1);(53)若A(t+1)中没有比a(t)优的个体，则a(t)加入A(t+1)中作为A(t+1)的第n+1个个体，其中n为群体大小。(53) If there is no individual better than a(t) in A(t+1), then a(t) is added to A(t+1) as the n+1th individual of A(t+1), where n is the population size.8.根据权利要求5所述的生产调度方法，其特征在于，所述步骤5)中的交叉操作如下：8. The production scheduling method according to claim 5, wherein the crossover operation in the step 5) is as follows:(54)确定父代初始种群；(54) Determine the initial population of the parent;(55)随机产生小于父代染色体长度的数；(55) Randomly generate a number smaller than the length of the parent chromosome;(56)互换染色体中对应该长度与位置的片段；(56) Swap fragments corresponding to the length and position in the chromosome;(57)保持被交换的片段不动，在没有交换的片段中寻找重复值，然后在父代被换走的部分中找到对应位置的元素进行替换。(57) Keep the exchanged segments unchanged, search for duplicate values in the segments that are not exchanged, and then find the elements at the corresponding positions in the part where the parent is exchanged for replacement.9.根据权利要求5所述的生产调度方法，其特征在于，所述步骤5)中的变异操作如下：在父代染色体编码上随机选择两个点作为逆转点，将两个逆转点之间的基因进行逆向排序得到变异后的染色体。9. The production scheduling method according to claim 5, wherein the mutation operation in the step 5) is as follows: randomly select two points on the parent chromosome code as reversal points, The mutated chromosomes are obtained by reverse sequencing of the genes.10.一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现如权利要求1至9任一项所述的一种生产调度方法的步骤。10. A computer-readable storage medium storing a computer program, characterized in that, when the computer program is executed by a processor, a method according to any one of claims 1 to 9 is implemented The steps of a production scheduling method.

Images