CN112884368A - Multi-target scheduling method and system for minimizing delivery time and delay of high-end equipment - Google Patents

Abstract

The invention provides a multi-objective scheduling method with minimum delivery time and delay for high-end equipment, and relates to the technical field of task scheduling. After the parent population is generated, the invention divides the parent population into multiple small populations, and sets different quick sorting and crowding degree calculation rules for the multiple small populations. Crossover occurs, which can spread the excellent genes in the individual among the populations, effectively avoid the entire population from falling into the local optimal solution, expand the search range of the optimal solution, and effectively improve the effect of the optimal scheduling scheme. The method provided by the present invention effectively solves the problem of coordinated scheduling of research and development projects that minimizes project delivery time and delivery delay, shortens the delivery time and delay time of multiple projects, and can provide a good solution for enterprises when making plans. decision basis.

Description

Multi-target scheduling method and system for minimizing delivery time and delay of high-end equipment

Technical Field

The invention relates to the technical field of task scheduling, in particular to a multi-target scheduling method and system for minimizing delivery time and delay of high-end equipment.

Background

The multi-target development project cooperative scheduling problem is a typical combined optimization problem, and the problem is commonly existed in the research, development and manufacturing of high-end equipment. High-end equipment such as a launch vehicle needs to be developed in consideration of not only the restrictions on resources, locations, and the like, but also multiple project objectives such as minimization of project delivery time and minimization of project delivery delay. In the process of research and development of high-end equipment, minimizing the delivery time of a project has important significance on cost saving of enterprises, minimizing the delivery delay of the project has important significance on-time delivery of the enterprises, and the two goals are important goals pursued by the enterprises.

In the existing method, the problem of multi-target development project collaborative scheduling is proved to be an NP-Hard problem, so that students generally use intelligent algorithms and heuristic algorithms to solve the problem on a large scale. A paper "a fast elite-type multi-objective genetic algorithm (NSGA-II)" published by Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, T.Meyarrivan in IEEE evolutionary computing journal of 2002, which proposes an improved non-dominated sorting algorithm for multi-objective combinatorial optimization problems and introduces methods of non-dominated sorting, crowding and elite selection; a paper & lt multimode project scheduling based on particle swarm optimization & gt published in 2006 by Zhang H, Tam C M and Li H proposes a hybrid coding and serial decoding method considering activity priority and an activity execution mode based on a particle swarm algorithm aiming at a multi-project and multi-target scheduling problem. However, due to the fact that multiple pareto optimal solutions exist in the multi-objective problem and the time complexity of the algorithm is high, the non-dominated sorting genetic algorithm (NSGA-II) is prone to falling into local optimization, namely the existing algorithm of the multi-objective development project collaborative scheduling problem is prone to falling into local optimization.

Disclosure of Invention

The technical problem to be solved by the invention is that the algorithm of the multi-target development project cooperative scheduling problem in the prior art is easy to fall into the local optimum technical problem.

The invention solves the technical problems through the following technical means: the multi-target scheduling method for minimizing delivery time and delay of high-end equipment comprises the following steps:

s1, acquiring task data of high-end equipment, and setting input parameters of an improved non-dominated sorting genetic algorithm based on the task data; initializing execution parameters of the improved non-dominated sorting genetic algorithm; the execution parameters comprise a population size popsize, a maximum iteration number runtime and a current iteration number run;

s2, generating a father population based on the improved non-dominated sorting genetic algorithm and the input parameters, and calculating the fitness value of individuals in the father population;

s3, dividing the father population into a plurality of small populations, and executing an improved crossover operator, an improved mutation operator and an elite selection operator to the plurality of small populations to generate sub-populations;

s4, combining the father population and the child population into a new population;

s5, performing improved quick sorting on the new population, and performing improved crowding calculation on part of individuals in the quickly sorted new population;

s6, executing an improved selection operator on the new population according to the result of the rapid sequencing and the improved crowding calculation, and generating a new father population with the population size of popsize;

s7, calculating a key path of the individuals in the new father population, and determining the key path of the individuals;

s8, codes on the individual key paths are appointed, the individuals with the appointed key path codes are selected to a new sub population, and the individuals in the father population and the new sub population are updated;

s9, executing an improved crossover operator, an improved mutation operator and an elite selection operator on all the individuals in the updated parent population to generate a new sub population, selecting the individual with the minimum fitness value in the sub population as a superior individual, and recording the code and the fitness value of the superior individual;

s10, judging whether the current iteration number run is larger than the maximum iteration number runtime, if so, terminating the algorithm, enabling the value with the minimum fitness value in the optimal individuals to be the fitness value of the globally optimal individual, enabling the code of the optimal individual to be the code of the globally optimal individual, outputting the fitness value and the code of the globally optimal individual, and enabling the output globally optimal individual code to be the optimal scheduling scheme; if not, go to step S4, if run is equal to run + 1.

According to the invention, after the father population is generated, the father population is divided into a plurality of small populations, different rapid sequencing and crowding degree calculation rules are set for the plurality of small populations, and the plurality of small populations are crossed in the evolution process, so that excellent genes in individuals can be propagated among the populations, the whole population is effectively prevented from falling into a local optimal solution, the search range of the optimal solution is expanded, and the effect of the optimal scheduling scheme is effectively improved. The method provided by the invention effectively solves the problem of development project cooperative scheduling of minimized project delivery time and delivery delay, shortens the delivery time and delay time of multiple projects, and can provide good decision basis when an enterprise makes a plan.

Further, step S2 specifically includes:

s201, encoding input parameters;

s202, generating a father population according to the coded input parameters, wherein the father population comprises popsize initial individuals;

s203, calculating the total delivery time C of each initial individual_maxAnd the value of the delivery delay push, using the two values as a set of solutions, and using the set of solutions to represent the fitness of the original individualStress values.

Further, step S3 specifically includes:

s301, dividing the father population into a plurality of small populations, and executing an improved crossover operator and an improved mutation operator on the plurality of small populations to generate new temporary populations;

s302, calculating the fitness of individuals in the temporary population, executing an elite selection operator, and selecting popsize individuals from the temporary population to form a sub-population.

Further, step S301 specifically includes:

s30101, dividing the father population into 4 small populations with the size of popsize/4, and respectively recording the small populations as population 1, population 2, population 3 and population 4;

s30102, performing an improved crossover operator on the small population, including:

s30102a, for each of the group 1 and the group 2, let k be 1 and let the crossing probability of the kth individual be

Wherein f is₁max and f₁min is expressed as delivery time C of all individuals in population 1_maxMaximum and minimum values of f₁x_kIndicating delivery time C of kth individual of population 1_maxGo to step S30102 b;

s30102b, selecting the kth individuals in the population 1 and the population 2 respectively, generating a random number rand1 between 0 and1, and comparing the random number rand1 with P_c1(k) If rand1 is greater than P_c1(k) If so, go to step S30102c, otherwise, go to step S30102b if k is k + 1;

s30102c, performing single-point crossing on the kth individual of the population 1 and the population 2, determining whether k > popoise/4 is true, if yes, going to step S30102d, otherwise, going to step S30102b if k is k + 1;

s30102d, for each of the group 3 and the group 4, let k be 1, and let the crossing probability of the kth individual be

Wherein f is₄max and f₄min is respectively expressed as the maximum and minimum of the individual delivery delays Punish in the population 4, f₄x_kA value indicating the delivery delay push of the kth individual of the population 4, and the process goes to step S30102 e;

s30102e, selecting the kth individuals from the population 3 and the population 4 respectively, generating a random number rand2 between 0 and1, and comparing the random number rand2 with P_c4(k) If rand2 is greater than P_c4(k) If so, go to step S30102f, otherwise, go to step S30102e by setting k to k + 1.

S30102f, performing single-point crossing on the kth individual of the population 4 and the population 3, determining whether k > popoise/4 is true, if yes, ending the mutation, otherwise, k equals k +1, and going to step S30102 f;

s30103, performing an improved mutation operator on the small population after the improved crossover operator is performed, wherein the improved mutation operator comprises:

s30103a, for population 1 after the improved crossover operator is performed, k is set to 1, and the mutation probability of the kth individual is set to

Wherein f is₁max and f₁min is expressed as delivery time C of all individuals in population 1_maxMaximum and minimum values of f₁x_kIndicating delivery time C of kth individual of population 1_maxGo to step S30103 b;

s30103b, selecting the kth individual of the population 1, and generating a random number rand3 between 0 and1, if the random number rand3 is more than P_m1(k) If yes, go to step S30303c, otherwise, go to step S30103b if k is k + 1;

s30103c, mutating the code of the kth individual of the population 1, if the task corresponding to the code is a virtual layer task, the code is unchanged, if the task corresponding to the code is a meta-task, a resource is randomly selected from the available resource range of the meta-task as the code of the meta-task, and it is determined whether k > poison/4 is true, if yes, step S30103d is performed, otherwise, k is k +1, and step S30103b is performed;

s30103d, for population 4 after the improved crossover operator is performed, k is set to 1, and the mutation probability of the kth individual is set to

Wherein f is₄max and f₄min is expressed as the maximum and minimum delivery delay Punish of all individuals in the population 4, respectively, f₄x_kA value indicating the delivery delay push of the kth individual of the population 4, and the process goes to step S30103 b;

s30103e, selecting the kth individual of the population 4, and generating a random number rand4 between 0 and1, if the random number rand4 is more than P_m4(k) If so, go to step S30103c, otherwise, go to step S30103e if k is k + 1;

s30103f, mutating the code of the kth individual of the population 4, if the task corresponding to the code is a virtual layer task, the code is unchanged, if the task corresponding to the code is a meta task, randomly selecting a resource from the available resource range of the meta task as the code of the meta task, determining whether k > pop ose/4 is true, if yes, turning to step S30103g, otherwise, turning to step S30103e if k is k + 1;

s30103g, for population 2 after the improved crossover operator is performed, k is set to 1, and the mutation probability of the kth individual is set to

Where H represents the maximum dominance level produced by individuals in population 2 after non-dominance ranking, g_kIndicating the non-dominant ranking rank of the kth individual, go to step S30103 h;

s30103h, selecting kth individual of the population 2, generating a random number rand5 between 0 and1, and judging whether the random number rand5 is less than P_c2(k) If yes, go to step S30103i, otherwise k equals k + 1; go to step S30103 h;

s30103i, mutating the code of the kth individual of the population 2, if the task corresponding to the code is a virtual layer task, the code is unchanged, if the task corresponding to the code is a meta-task, a resource is randomly selected from the available resource range of the meta-task as the code of the meta-task, and it is determined whether k > poison/4 is true, if yes, step S30103j is performed, otherwise, k is k +1, and step S30103h is performed;

s30103j, for the population 3 after the improved crossover operator is performed, k is set to 1, and the mutation probability of the kth individual is set to

Where H represents the maximum dominance level produced by individuals in population 3 after non-dominance ranking, g_kIndicating the non-dominant ranking rank of the kth individual, go to step S30103 k;

s30103k, selecting kth individual of the population 3, generating a random number rand6 between 0 and1, and judging whether the random number rand6 is less than P_c3(k) If yes, go to step S30103m, otherwise k equals k + 1; go to step S30103 k;

s30103m, carrying out mutation on the code of the kth individual of the population 3, if the task corresponding to the code is a virtual layer task, the code is unchanged, if the task corresponding to the code is a meta-task, a resource is randomly selected from the available resource range of the meta-task as the code of the meta-task, whether k > poison/4 is satisfied is judged, if yes, the mutation operator is ended, otherwise, k is k +1, and the step S30103k is carried out;

s30104, forming a new temporary population by the 4 small population groups 1, 2, 3 and4 after the improved mutation operator is executed.

Further, step S302 specifically includes:

s30201, calculating the fitness of individuals in the temporary population;

s30202, executing an elite selection operator, selecting popsize individuals from the temporary population, and generating a sub-population, wherein the method comprises the following steps:

s30202a, for the population 1 in the temporary population, when the individual in the population 1 is mutated to generate a new individual, calculating the mutated individualDelivery time C_maxIf the delivery time C of the newly generated individual is_maxIf the value of (A) is less than the value of the original individual, the mutated individual is retained, and the original individual is discarded; otherwise, the original individual is kept, and the variant individual is discarded;

s30202b, for the population 4 in the temporary population, when the individuals in the population 4 generate new individuals through mutation, calculating the delivery delay Punish value of the mutated individuals, if the delivery delay Punish value of the newly generated individuals is smaller than that of the original individuals, keeping the mutated individuals, and discarding the original individuals; otherwise, the original individual is kept, and the variant individual is discarded;

S30202C, for the population 2 and the population 3 in the temporary population, when the individuals in the population 2 and the population 3 have variation, calculating the delivery time C of the varied individuals_maxIf the fitness value of the individual generated after the mutation is not governed by the fitness value of the original individual, the mutated individual is reserved; otherwise, the original individual is kept, and the variant individual is discarded;

the individuals retained in steps S30202a to S30202c constitute a sub-population, the population size of the sub-population being popsize.

Further, step S5 specifically includes:

s501, dividing the new population with the population scale of 2popsize into 4 populations with the population scale of 2popsize/4, wherein the 4 populations comprise a population 1, a population 2, a population 3 and a population 4;

s502, carrying out improved quick sequencing on the new population;

s503, calculating the improved crowding degree of part of individuals in the quickly sorted new population.

Further, in step S502, performing improved fast ranking on the new population, including:

s5021, calculating the fitness of the individuals in the 4 populations to obtain a fitness value f (x) of each individual;

s5022, aiming at minimizing delivery time C for the population 1_maxOn the principle of delivery time C_maxSequentially putting the individuals in the population 1 into the set C from small to large;

s5023, regarding the population 4, sequentially putting individuals in the population 1 into a set P from small to large according to the value of the delivery delay push on the principle of minimizing the delivery delay push of a target;

s5024, for the population 2 and the population 3, finding the solution set n of the dominated solution of each individual k in the population according to the pareto principle through the value of the fitness value f (x) of each individual_kAnd dominating solution set s_kTurning to step S5025;

s5025, enabling j to be 1, and finding out all n in the population_k0 individuals, storing them in the current set Z_jTurning to step S5026;

s5026, aiming at the current set Z_jEach individual k in (a), looking at the set s of individuals it governs_kWill aggregate s_kN of each individual k in_k Subtracting 1, i.e. the number of solution entities dominating the individual k minus 1, if n_k-1-0, let j-j +1 and store the individual k in another set Z_jTurning to step S5027;

s5027 with Z_jFor the current set, step S5026 is repeated until the entire new population is stratified.

Further, in step S503, the improved congestion is performed on a part of individuals in the quickly ranked new population

And (3) extrusion degree calculation, comprising:

s5031, performing rapid non-dominated sorting on each individual in the population 2 and the population 3 to obtain a layered population;

s5032, delivery time C for each layer_maxThe individual with the minimum value and the minimum delivery delay push value is made to have the crowdedness degree of 0; for the remaining individuals k, use the formula

The crowdedness distance of each individual is calculated. f. of₁(k +1) and f₁(k-1) shows delivery times C of two individuals in the vicinity of the individual, respectively_maxValue f₂(k +1) and f₂(k-1) each representsThe delivery of two individuals in the vicinity of the individual is delayed by the value of push.

Further, step S6 specifically includes:

s601, for all individuals in the population 2 and the population 3, making j equal to 1, and for a new population, finding out a set Z obtained by fast sequencing_jSelecting all the individuals in the individual group to a new father group;

s602, setting the selected individual number as D, judging whether the selected individual number D > popsize/4 is established, if so, executing a step S604, otherwise, executing a step S603;

s603, let j equal to j +1, find out the set Z_jAll congestion degrees in (2) are less than set Z_jIndividuals with average crowdedness, and marking these individuals as T_jAnd puts them into the new father group, executes step S602;

s604, marking the new father group as T_jThe individuals in the tree are sorted from big to small according to their crowdedness and the top is sorted

Individuals are removed from the new parent population;

s605, for the group 1, according to the delivery time C_maxSelecting the individuals in the set C into a set M from small to large, stopping selection if the number of the individuals in the set M is pop/4, and putting all the individuals in the set M into a new father group;

s606, as for the population 4, selecting the individuals in the set P to the set L from small to large according to the value of the delivery delay Punish, if the number of the individuals in the set L is popoise/4, stopping the selection, and putting all the individuals in the set L into a new father population.

The present invention also provides a multi-objective scheduling system for high-end equipment with minimum delivery time and delay, the system comprising a computer, the computer comprising:

at least one memory cell;

at least one processing unit;

wherein the at least one memory unit has stored therein at least one instruction that is loaded and executed by the at least one processing unit to perform the steps of:

s1, acquiring task data of high-end equipment, and setting input parameters of an improved non-dominated sorting genetic algorithm based on the task data; initializing execution parameters of the improved non-dominated sorting genetic algorithm; the execution parameters comprise a population size popsize, a maximum iteration number runtime and a current iteration number run;

s2, generating a father population based on the improved non-dominated sorting genetic algorithm and the input parameters, and calculating the fitness value of individuals in the father population;

s3, dividing the father population into a plurality of small populations, and executing an improved crossover operator, an improved mutation operator and an elite selection operator to the plurality of small populations to generate sub-populations;

s4, combining the father population and the child population into a new population;

s5, performing improved quick sorting on the new population, and performing improved crowding calculation on part of individuals in the quickly sorted new population;

s6, executing an improved selection operator on the new population according to the result of the rapid sequencing and the improved crowding calculation, and generating a new father population with the population size of popsize;

s7, calculating a key path of the individuals in the new father population, and determining the key path of the individuals;

s8, codes on the individual key paths are appointed, the individuals with the appointed key path codes are selected to a new sub population, and the individuals in the father population and the new sub population are updated;

s9, executing an improved crossover operator, an improved mutation operator and an elite selection operator on all the individuals in the updated parent population to generate a new sub population, selecting the individual with the minimum fitness value in the sub population as a superior individual, and recording the code and the fitness value of the superior individual;

s10, judging whether the current iteration number run is larger than the maximum iteration number runtime, if so, terminating the algorithm, enabling the value with the minimum fitness value in the optimal individuals to be the fitness value of the globally optimal individual, enabling the code of the optimal individual to be the code of the globally optimal individual, outputting the fitness value and the code of the globally optimal individual, and enabling the output globally optimal individual code to be the optimal scheduling scheme; if not, go to step S4, if run is equal to run + 1.

The invention has the advantages that:

1. according to the invention, after the father population is generated, the father population is divided into a plurality of small populations, different rapid sequencing and crowding degree calculation rules are set for the plurality of small populations, and the plurality of small populations are crossed in the evolution process, so that excellent genes in individuals can be propagated among the populations, the whole population is effectively prevented from falling into a local optimal solution, the search range of the optimal solution is expanded, and the effect of the optimal scheduling scheme is effectively improved. The method provided by the invention effectively solves the problem of development project cooperative scheduling of minimized project delivery time and delivery delay, shortens the delivery time and delay time of multiple projects, and can provide good decision basis when an enterprise makes a plan.

2. Aiming at the problem of development project cooperative scheduling aiming at minimizing project delivery time and delivery delay, the invention firstly encodes a plurality of projects of tasks and resources thereof through an improved non-dominated sorting algorithm, determines the close-before-close relationship and the used resources of each task, then executes the tasks according to the close-before-close relationship among the tasks, thereby obtaining the delivery time and the total delivery delay Punish of the plurality of projects, and finally generates a group of multi-target dominated solutions. The method comprises the steps of initially randomly assigning resources of each task, generating a sub-population after selecting, crossing and mutating the population, combining a father population and the sub-population, obtaining a new population through fast non-dominated sorting and congestion degree calculation and non-dominated sorting, then selecting, crossing and mutating the population to obtain a next generation population, and updating the population through continuous iteration to optimize solution space and finally obtain the optimal solution of the problem. The improved non-dominated sorting algorithm shows superiority in convergence speed and solution quality of the solution.

3. After a new father population is selected to be generated, the key routes of partial individuals in the population are calculated, the tasks on the key routes are subjected to resource assignment, the optimal resources are distributed to the key tasks, the understanding quality is greatly improved, and the convergence speed of the algorithm is accelerated.

Drawings

Fig. 1 is a flowchart of a multi-objective scheduling method for minimizing delivery time and delay of high-end equipment according to an embodiment of the present invention.

Detailed Description

In order to make the objects, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the embodiments of the present invention, and it is obvious that the described embodiments are some embodiments of the present invention, but not all embodiments. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present invention.

The embodiment of the invention provides a multi-target scheduling method for minimizing delivery time and delay of high-end equipment, which comprises steps S1-S10, and a flow chart of the method is shown in FIG. 1.

S1, acquiring task data of high-end equipment, and setting input parameters of an improved non-dominated sorting genetic algorithm based on the task data; initializing execution parameters of the improved non-dominated sorting genetic algorithm; the execution parameters comprise population size popsize, maximum iteration number runtime and current iteration number run;

s2, generating a father population based on the improved non-dominated sorting genetic algorithm and the input parameters, and calculating the fitness value of individuals in the father population;

s3, dividing the father population into a plurality of small populations, and executing an improved crossover operator, an improved mutation operator and an elite selection operator to the plurality of small populations to generate sub-populations;

s4, combining the father population and the son population into a new population;

s5, performing improved quick sorting on the new population, and performing improved crowding calculation on part of individuals in the quickly sorted new population;

s6, executing an improved selection operator on the new population according to the result of the rapid sequencing and the improved crowding calculation, and generating a new father population with the population size of popsize;

s7, calculating the key path of the individual in the new father population, and determining the key path of the individual;

s8, codes on the individual key paths are appointed, the individuals with the appointed key path codes are selected to a new sub population, and the individuals in the father population and the new sub population are updated;

s9, executing an improved crossover operator, an improved mutation operator and an elite selection operator on all the individuals in the updated parent population to generate a new sub population, selecting the individual with the minimum fitness value in the sub population as a superior individual, and recording the code and the fitness value of the superior individual;

s10, judging whether the current iteration number run is larger than the maximum iteration number runtime, if so, terminating the algorithm, enabling the value with the minimum fitness value in the optimal individuals to be the fitness value of the globally optimal individual, enabling the code of the optimal individual to be the code of the globally optimal individual, outputting the fitness value and the code of the globally optimal individual, and enabling the output globally optimal individual code to be the optimal scheduling scheme; if not, go to step S4, if run is equal to run + 1.

According to the embodiment of the invention, after the father population is generated, the father population is divided into a plurality of small populations, different rapid sequencing and crowding degree calculation rules are set for the plurality of small populations, and the plurality of small populations are crossed in the evolution process, so that excellent genes in individuals can be spread among the populations, the whole population is effectively prevented from falling into a local optimal solution, the search range of the optimal solution is expanded, and the effect of the optimal scheduling scheme is effectively improved. The method provided by the invention effectively solves the problem of development project cooperative scheduling of minimized project delivery time and delivery delay, shortens the delivery time and delay time of multiple projects, and can provide good decision basis when an enterprise makes a plan.

Each step is described in detail below.

In step S1, acquiring task data of the high-end equipment, and setting input parameters of the improved non-dominated sorting genetic algorithm based on the task data of the high-end equipment; initializing execution parameters of the improved non-dominated sorting genetic algorithm; the execution parameters comprise population size popsize, maximum iteration number runtime and current iteration number run. The specific implementation process is as follows:

the executing the parameters further comprises: cross probability p_cProbability of mutation P_mAnd the current iteration number run is 1.

S101, acquiring task data of high-end equipment in a manual entry mode and the like, wherein the task data of the high-end equipment comprises a project set required to be executed in the research and development and manufacturing processes of a plurality of high-end equipment projects, the number of tasks in each project, the types of project resources, available resources of each task and the like.

S102, setting input parameters of the improved non-dominated sorting genetic algorithm based on task data of high-end equipment.

Input parameters to the algorithm include: set of items I ═ { I } that needs to be performed during development and manufacturing of a plurality of high-end equipment items₁,I₂,I₃…I_nJ, the number of tasks in each item, J ═ J₁,J₂,J₃…J_nThe resource types are M, and M is equal to { M }respectively₁,m₂,m₃…m_MThe available quantity of each type of resource at a certain time is a unit, and the available resource of each task is J_m＝{J_m1,J_m2,J_m3…, and the execution time of the task J in each project I under the resource M is marked as I_jmt。

It should be noted that, in the implementation process, the input parameters of the algorithm further include constraints and an objective function.

The constraint conditions include:

1. in the whole development process of high-end equipment, a project can be decomposed into a plurality of subtasks, and the subtasks can be decomposed into a plurality of more specific subtasks and finally can be decomposed into the most basic tasks. These tasks that can no longer be decomposed are called meta-tasks and tasks that can continue to be decomposed are called virtual layer tasks. Only the meta-task allocates specific resources, and the virtual layer task does not allocate specific resources.

2. All tasks in each project have strict close-before-close relations, the tasks need to be executed in sequence according to the close-before-close relations, each resource can only execute one task at the same time, the time required for executing the same task by different resources is different, each task cannot be interrupted once being executed, and one task can be executed only after all the close-before tasks are executed.

3. Adding a virtual total initial task S before the initial tasks of the plurality of projects, wherein the task does not occupy any time and resources, adding a virtual summary bundle task E after the ending task of each project, wherein the task does not occupy any time and resources, and combining the total initial task, the tasks in the plurality of projects and the summary bundle task into a total project.

The objective function includes:

the goal of the total item is to minimize the delivery time C of the item_maxAnd minimize delivery delay push. Wherein the delivery time C of the entire item_maxTo summarize the completion time of the bind task E, the delivery time of each item is the completion time of the end task of each item, denoted C_i. Each project has a set completion time D_iDelay in completing an item may result in item delay, delay in delivery of individual items

Total delivery delay

Where N represents the number of items. In summary, the objective function is:

Min C_max

Min Punish。

in step S2, a parent population is generated based on the improved non-dominated sorting genetic algorithm and the input parameters, and fitness values of individuals in the parent population are calculated. The specific implementation process is as follows:

s201, encoding the input parameters, including:

and generating an effective task chain according to the close-before-close relation among the tasks in each project. And randomly generating corresponding resources according to the available resources of each task, thereby generating a single individual code. The method specifically comprises the following steps:

and S2011, setting a virtual total initial task S and a virtual summary bundle task E, enabling resources required by the tasks S and E to be empty, enabling the time of the tasks to be 0, setting the total initial task S as an immediately previous task of each item initial task, and setting the summary bundle task E as an immediately subsequent task of each item ending task.

S2012, setting a close-before relationship between the virtual layer task and its subtasks, and if one of the subtasks included in one of the virtual layer tasks has no other subtask as a close-before task of the subtask, using the virtual layer task as a close-before task of the subtask.

S2013, setting a close-before close-after relation between the virtual layer task and an immediately-before task, and if the immediately-before task of the virtual layer task is a primary task, setting the primary task as the immediately-before task of the virtual layer task; and if the task immediately before the virtual layer task is the virtual layer task, taking the meta task without the immediately after task in the meta tasks under the immediately before task as the task immediately before the virtual layer task.

S2014, sequentially generating a set of Task sets according to the immediate relationship between tasks of each project, and recording as Task ═ S, t₁,t₂,t₃…t_n,E}。

S2015, setting the resources of all virtual tasks to be empty and the task time to be 0; according to available resource J of each meta task_m＝{J_m1,J_m2,J_m3…, randomly allocating a resource to the meta-Task until the set Task is { S, t }₁,t₂,t₃…t_nAll meta-tasks in E are allocated to resources.

S2016. subject set Task ═ S, t₁,t₂,t₃…t_nAnd E) obtaining the time t required by actual completion of each task by the resources distributed by each task.

S2017, set Task ═ S, t₁,t₂,t₃…t_nE, storing the resource m and the time t required for actually completing each Task as the attributes of the Task into the Task, and setting the set Task containing the resource and the time t as { S, t }₁,t₂,t₃…t_nE as the code of the initial individual.

S202, generating a father population fPop according to the coded input parameters, wherein the father population fPop comprises popsize initial individuals and comprises the following steps:

the parent population was set to have popsize initial individuals. For each initial individual in the parent population, a coding operation is performed by the method as in step S201. Since the codes are generated with randomness to the resource allocation of the tasks, the individual codes thus obtained are different. The parent population is obtained by generating a code for popsize initial individuals.

S203, calculating the total delivery time C of each initial individual_maxAnd a delivery delay push value, using the two values as a set of solutions, and using the set of solutions to represent the fitness value of the initial individual.

S2031, according to the encoding rule, initially solving the set Task ═ S, t₁,t₂,t₃…t_nAnd E, traversing all elements in the set Task to obtain the resources used by each Task, setting the start time of all tasks to be 0, setting the end time to be-1, and setting k to be 1.

S2032 determines whether the end time of the kth task is-1, and if yes, executes step S2033, otherwise, lets k be k +1, and executes step S2037.

S2033, if K is 1, the start time K of the kth task is set_SIs 0, end time K_EIs 0; otherwise, step S2034 is executed.

S2034, determining whether the end time of all tasks immediately before the kth task is-1, if yes, setting the sequence number of the task whose end time of the kth task is-1 as t, and executing step S2034 if k is t; otherwise, let the start time of task K be the maximum value of the end time of all immediately preceding tasks, and record as K_SLet the elapsed time K of task K_tResource m used by task k_tThe time taken.

S2035, judging resource m_tWhether the task is occupied by other tasks or not, if so, waiting for the other tasks to finish, and recording the time as N_tStep S2036 is executed; otherwise, the starting time of the task K is K_SEnd time K_E＝K_S+K_tLet k be k +1, step S2037 is executed.

S2036, starting time K of task K_S＝N_tEnd time K_E＝K_S+K_tLet k be k + 1.

S2037, judgment k>N_PIf yes, outputting the end time C of the virtual summary bundle task E_maxWith the completion time C of the last task of each project_iAnd calculating the value of the item delivery delay push, otherwise returning to step S2032, N_PIndicating the length of the code of the initial individual.

S2038, end time C of virtual summary bundle task E_maxAnd delaying the delivery of the last item by push to generate a group of solutions, and the group of solutions are the fitness values of the initial individuals.

In step S3, the parent population is divided into a plurality of small populations, and the improved crossover operator, the improved mutation operator, and the elite selection operator are performed on the plurality of small populations to generate sub-populations. The specific implementation process is as follows:

s301, dividing the father population into a plurality of small populations, executing an improved crossover operator and an improved mutation operator to the plurality of small populations, and generating a new temporary population, wherein the method comprises the following steps:

s30101, dividing the father population fPop into 4 small populations with the size of popsize/4, and marking the small populations as population 1, population 2, population 3 and population 4 respectively. It should be noted that dividing into 4 sub-populations is only one preferred scheme in the embodiment of the present invention. In particular embodiments, the parent population may be divided into other numbers of smaller populations.

S30102, performing an improved crossover operator on the small population, including

S30102a, for each of the group 1 and the group 2, let k be 1 and let the crossing probability of the kth individual be

Wherein f is₁max and f₁min is expressed as delivery time C of all individuals in population 1_maxMaximum and minimum values of f₁x_kIndicating delivery time C of kth individual of population 1_maxGo to step S30102 b.

S30102b, selecting the kth individuals in the population 1 and the population 2 respectively, generating a random number rand1 between 0 and1, and comparing the random number rand1 with P_c1(k) If rand1 is greater than P_c1(k) If so, go to step S30102c, otherwise, go to step S30102b by setting k to k + 1.

S30102c, the method performs a single-point crossing between the kth individual of the population 1 and the population 2, determines whether k > popoise/4 is true, and if yes, goes to step S30102d, otherwise, goes to step S30102b if k is k + 1.

S30102d, for each of the group 3 and the group 4, let k be 1, and let the crossing probability of the kth individual be

Wherein f is₄max and f₄min is respectively expressed as the maximum and minimum of the individual delivery delays Punish in the population 4, f₄x_kThe value indicating the delivery delay push of the kth individual of the population 4 goes to step S30102 e.

S30102e, selecting the kth individuals from the population 3 and the population 4 respectively, generating a random number rand2 between 0 and1, and comparing the random number rand2 with P_c4(k) If rand2 is greater than P_c4(k) If so, go to step S30102f, otherwise, go to step S30102e by setting k to k + 1.

S30102f, performing single-point crossing between the kth individual of the population 4 and the population 3, determining whether k > popoise/4 is satisfied, if so, ending the mutation, otherwise, k equals k +1, and going to step S30102 f.

It should be noted that, the improved crossover operator in the embodiment of the present invention is an improvement on the prior art, and two objective functions of a problem are considered in the crossover operator according to a research problem, so that the crossover probability of different parts of individuals in a population is different in an algorithm iteration process, the crossover probability can change along with the change of an objective function value, the crossover probability of an individual with a poor objective function value is small, and the crossover probability of an individual with a good objective function is large. Therefore, more codes of better individuals of the target function can be reserved, and the convergence speed of the algorithm is accelerated.

S30103, performing an improved mutation operator on the small population after the improved crossover operator is performed, wherein the improved mutation operator comprises:

s30103a, for population 1 after the improved crossover operator is performed, k is set to 1, and the mutation probability of the kth individual is set to

Wherein f is₁max and f₁min is expressed as delivery time C of all individuals in population 1_maxMaximum and minimum values of f₁x_kIndicating delivery time C of kth individual of population 1_maxGo to step S30103 b.

S30103b, selecting the kth individual of the population 1, and generating a random number rand3 between 0 and1, if the random number rand3 is more than P_m1(k) If so, go to step S30103c, otherwise, go to step S30103b by setting k to k + 1.

S30103c, performing mutation on the code of the kth individual of the population 1, if the task corresponding to the code is a virtual layer task, the code is unchanged, if the task corresponding to the code is a meta-task, one resource is randomly selected from the available resource range of the meta-task as the code of the meta-task, and whether k > poison/4 is satisfied is determined, if yes, the step S30103d is performed, otherwise, k is k +1, and the step S30103b is performed.

S30103d, for population 4 after the improved crossover operator is performed, k is set to 1, and the mutation probability of the kth individual is set to

Wherein f is₄max and f₄min is expressed as the maximum and minimum delivery delay Punish of all individuals in the population 4, respectively, f₄x_kThe value indicating the delivery delay push of the kth individual of the population 4 goes to step S30103 b.

S30103e, selecting the kth individual of the population 4, and generating a random number rand4 between 0 and1, if the random number rand4 is more than P_m4(k) If so, go to step S30103c, otherwise, go to step S30103e by setting k to k + 1.

S30103f, performing mutation on the code of the kth individual of the population 4, if the task corresponding to the code is a virtual layer task, the code is unchanged, if the task corresponding to the code is a meta-task, one resource is randomly selected from the available resource range of the meta-task as the code of the meta-task, and whether k > poison/4 is satisfied is determined, if yes, the step S30103g is performed, otherwise, k is k +1, and the step S30103e is performed.

S30103g, for population 2 after the improved crossover operator is performed, k is set to 1, and the mutation probability of the kth individual is set to

Where H represents the maximum dominance level produced by individuals in population 2 after non-dominance ranking, g_kThe non-dominant ranking rank of the kth individual is represented, and the process goes to step S30103 h.

S30103h, selecting kth individual of the population 2, generating a random number rand5 between 0 and1, and judging whether the random number rand5 is less than P_c2(k) If yes, go to step S30103i, otherwise k equals k + 1; go to step S30103 h.

S30103i, performing mutation on the code of the kth individual of the population 2, if the task corresponding to the code is a virtual layer task, the code is unchanged, if the task corresponding to the code is a meta-task, one resource is randomly selected from the available resource range of the meta-task as the code of the meta-task, and whether k > poison/4 is satisfied is determined, if yes, the step S30310 is performed, otherwise, k is k +1, and the step S30103h is performed.

S30103j, for executing the improved transactionIn the population 3 after the crossover operator, k is 1, and the mutation probability of the kth individual is

Where H represents the maximum dominance level produced by individuals in population 3 after non-dominance ranking, g_kThe non-dominant ranking rank of the kth individual is represented, and the process goes to step S30103 k.

S30103k, selecting kth individual of the population 3, generating a random number rand6 between 0 and1, and judging whether the random number rand6 is less than P_c3(k) If yes, go to step S30103m, otherwise k equals k + 1; go to step S30103 k.

S30103m, performing mutation on the code of the kth individual of the population 3, if the task corresponding to the code is a virtual layer task, the code is unchanged, if the task corresponding to the code is a meta-task, randomly selecting a resource from the available resource range of the meta-task as the code of the meta-task, determining whether k > poison/4 is satisfied, if so, ending the mutation operator, otherwise, k is k +1, and going to step S30103 k.

It should be noted that, the improved mutation operator in the embodiment of the present invention is an improvement on the prior art, and two objective functions of a problem are considered in the mutation operator according to a research problem, so that the variation probabilities of different parts of individuals in a population are different in an algorithm iteration process, the variation probability can change along with the change of an objective function value, the variation probability of an individual with a poor objective function value is large, and the variation probability of an individual with a good objective function is small. Therefore, the coding variation of the individual with the poor target function is more, the search range of the individual with the poor target function in the iterative process of the algorithm is expanded, and the probability of finding a better solution by the algorithm is increased.

S30104, forming a new temporary population by the 4 small population groups 1, 2, 3 and4 after the improved mutation operator is executed, wherein the population size of the temporary population is 2 popsize.

S302, calculating the fitness of individuals in the temporary population, executing an elite selection operator, and selecting popsize individuals from the temporary population to form a sub-population. The specific implementation process is as follows:

s30201, calculating the fitness of the individuals in the temporary population PopTemp.

This step can calculate the fitness value of the individual in the provisional population PopTemp, and refer to step S203 above, which is not described herein again.

S30202, executing an elite selection operator, selecting popsize individuals from the temporary population, and generating a sub-population, wherein the method comprises the following steps:

s30202a, for the temporary population 1, when a new individual is generated by mutation of the individual in the population 1, calculating the delivery time C of the mutated individual_maxIf the delivery time C of the newly generated individual is_maxIf the value of (A) is less than the value of the original individual, the mutated individual is retained, and the original individual is discarded; otherwise, the original individual is kept and the variant individual is discarded.

S30202b, for the population 4 in the temporary population, when the individuals in the population 4 generate new individuals through mutation, calculating the delivery delay Punish value of the mutated individuals, if the delivery delay Punish value of the newly generated individuals is smaller than that of the original individuals, keeping the mutated individuals, and discarding the original individuals; otherwise, the original individual is kept and the variant individual is discarded.

S30202C, for the population 2 and the population 3 in the temporary population, when the individuals in the population 2 and the population 3 have variation, calculating the delivery time C of the varied individuals_maxIf the fitness value of the individual generated after the mutation is not governed by the fitness value of the original individual, the mutated individual is reserved; otherwise, the original individual is kept and the variant individual is discarded.

The individuals reserved in the steps S30202a to S30202c constitute a sub-population sPop, and the population size of the sub-population sPop is popsize.

In step S4, the parent population and the child population are combined into a new population of the population size of yes. The specific implementation process is as follows:

the parent population fPop and the child population sPop are merged into a new population dPop with a population size of 2 popsize.

In step S5, the new population is subjected to improved quick ranking, and the improved crowdedness calculation is performed on a part of the individuals in the quickly ranked new population. The specific implementation process is as follows:

s501, dividing a new population dPop with the population size of 2popsize into 4 populations with the population size of 2popsize/4, wherein the 4 populations comprise population 1, population 2, population 3 and population 4. It should be noted that the individuals in the population 1 are the initial individuals of the population 1 in the parent population fPop and the individuals retained in the population 1 in the temporary population.

S502, carrying out improved quick sequencing on the dPop of the new population, comprising the following steps:

s5021, fitness calculation is carried out on the individuals in the 4 populations to obtain a fitness value f (x) of each individual.

S5022, aiming at minimizing delivery time C for the population 1_maxOn the principle of delivery time C_maxThe individuals in the population 1 are put into the set C from small to large.

S5023, regarding the population 4, the individuals in the population 1 are sequentially placed in the set P from small to large according to the value of the delivery delay push, on the basis of the target minimum delivery delay push.

S5024, for the population 2 and the population 3, finding the solution set n of the dominated solution of each individual k in the population according to the pareto principle through the value of the fitness value f (x) of each individual_kAnd dominating solution set s_kGo to step S5025.

S5025, enabling j to be 1, and finding out all n in the population_k0 individuals, storing them in the current set Z_jGo to step S5026.

S5026, aiming at the current set Z_jEach individual k in (a), looking at the set s of individuals it governs_kWill aggregate s_kN of each individual k in_k Subtracting 1, i.e. the number of solution entities dominating the individual k minus 1, if n_k-1-0, let j-j +1 and store the individual k in another set Z_jThen, the process goes to step S5027.

S5027 with Z_jFor the current set, step S5026 is repeated until the entire new population dPop is stratified.

It should be noted that, in the embodiment of the present invention, the improvement of the fast sorting is an improvement of the existing technology, since the population is divided into four (populations 1, 2, 3, and 4) during algorithm design, different sorting principles need to be designed for different parts, and the improvement is that the individuals in different parts of the population are sorted according to different objective functions in the fast sorting, so that the orders of the individuals in different parts of the population are different after being sorted, so that the difference of the individuals in different parts of the population on the two objective functions is large, the diversity of the whole population is increased, and the algorithm is effectively prevented from falling into a local optimal solution during iteration.

S503, performing improved crowding calculation on part of individuals in the quickly sorted new population, where it should be noted that, in the embodiment of the present invention, part of individuals refers to individuals in the population 2 and the population 3. The method comprises the following steps:

s5031, performing rapid non-dominant sequencing on each individual in the population 2 and the population 3 to obtain a layered population.

S5032, delivery time C for each layer_maxThe individual with the minimum value and the minimum delivery delay push value is made to have the crowdedness degree of 0; for the remaining individuals k, use the formula

The crowdedness distance of each individual is calculated. f. of₁(k +1) and f₁(k-1) shows delivery times C of two individuals in the vicinity of the individual, respectively_maxValue f₂(k +1) and f₂(k-1) respectively represents the delivery delay push values of two individuals in the vicinity of the individual.

In step S6, an improved selection operator is performed on the new population according to the result of the quick sorting and the congestion degree calculation, and a new parent population with a population size of popsize is generated. The specific implementation process is as follows:

s601, for all individuals in the population 2 and the population 3, j is made to be 1, and for the population dPop, a set Z obtained by fast sequencing is found out_jAll of which are selected to a new parent group, fPop₁In (1).

S602, setting the selected number of individuals as D, judging whether the selected number of individuals D > popsize/4 is established, if so, executing the step S604, otherwise, executing the step S603.

S603, let j equal to j +1, find out the set Z_jAll congestion degrees in (2) are less than set Z_jIndividuals with average crowdedness, and marking these individuals as T_jAnd send them to the new father group, fPop₁Step S602 is executed.

S604, aiming at the new father group fPop₁Marked as T_jThe individuals in the tree are sorted from big to small according to their crowdedness and the top is sorted

Individual from a new father group fPop₁And (4) removing.

S605, for the group 1, according to the delivery time C_maxThe value of (C) is from small to large, the individuals in the set C are selected to the set M, if the number of the individuals in the set M is pop/4, the selection is stopped, and all the individuals in the set M are placed into a new father group fPop₁In (1).

S606, for the population 4, selecting the individuals in the set P to the set L from small to large according to the value of the delivery delay Punish, if the number of the individuals in the set L is popoise/4, stopping the selection, and putting all the individuals in the set L into a new father population fPop₁In (1).

It should be noted that, in the embodiment of the present invention, the improvement of the selection operator is to improve the prior art, and different selection operators are designed for different parts (populations 1, 2, 3, and 4) of the population, and through the improved selection operator, different individuals in different parts of the population can be selected to the new parent population, so that the individual difference in the new parent population can be increased, the diversity of the population individuals is increased, the algorithm is prevented from falling into the local optimal solution, and the convergence speed of the algorithm is increased.

In step S7, a critical path is calculated for the individuals in the new parent population, and an individual critical path is determined. The specific implementation process is as follows:

s701, obtaining the end time of the individual virtual summary bundle task E in the new parent group, and putting the virtual summary bundle task E into a set G to enable the virtual summary bundle task E to be the current task Ntask.

S702, finding out all the tasks immediately before the current task Ntask, traversing the tasks immediately before, finding out the task of which the ending time of one task is equal to the starting time of the current task Ntask, putting the task immediately before into a set G, and simultaneously replacing the current task Ntask with the task immediately before.

S703, judging whether the current task Ntask is a virtual total start task S, and if yes, performing step S704; otherwise, step S702 is executed.

S704, all tasks in the set G are connected according to the close-front close-back relation of the tasks to obtain the individual critical path, and all the tasks in the set G are all the tasks on the critical path.

In step S8, codes on the key paths of the individuals are designated, and the individuals to which the key path codes are designated are selected to the new sub-population, and the individuals in the parent population and the new sub-population are updated. The specific implementation process is as follows:

first, a new father group fPop is added₁The population is divided into populations with the population scale of popsize/4, including population 1, population 2, population 3 and population 4. Then executing:

s801, selecting non-dominant individuals in each population for the population 2 and the population 3 respectively, and recording the number f of the non-dominant individuals₂、f₃。

S802, respectively calculating and finding out the key paths of the individuals selected in the step S801.

And S803, sequentially assigning resources to the tasks on the key path of the selected individual, assigning the optimal resource in the available resources of the task to the task, and placing the individual into a progeny population sPop.

S804, for the population 1, according to the delivery time C_maxThe values of (c) are sorted from small to large, and the front f is selected₂And (4) individuals.

And S805, calculating and finding out the key path of the individual selected in the step 4.

S806, sequentially assigning resources to the tasks on the key paths of the selected individuals, assigning the optimal resource in the available resources of the tasks to the tasks, and placing the individuals into the filial generation population sPop.

S807, for the population 4, according to the delivery time C_maxThe values of (c) are sorted from small to large, and the front f is selected₃And (4) individuals.

And S808, calculating and finding out the key path of the selected individual in the step S807.

And S809, sequentially assigning resources to the tasks on the key path of the selected individual, assigning the optimal resource in the available resources of the task to the task, and placing the individual into a progeny population (sPop).

By executing steps S801 to S809, the individuals of the parent population and the new child population are updated.

In step S9, performing an improved crossover operator, an improved mutation operator, and an elite selection operator on all individuals in the updated parent population to generate a new child population, selecting an individual with the smallest fitness value in the child population as a superior individual, and recording the coding and fitness value of the superior individual. The specific implementation process is as follows:

and S901, executing an improved crossover operator and an improved mutation operator on all individuals in the updated parent population to generate a new temporary population.

In this step, an improved crossover operator and an improved mutation operator are performed on all individuals in the updated parent population to generate a new temporary population, which may refer to step S301 above, and details are not described here.

S902, calculating the fitness value of the temporary population, executing an elite selection operator, putting the selected individuals into a new sub-population until the population size is popsize, selecting the individuals with the minimum fitness value in the sub-population as optimal individuals, and recording the codes and the fitness values of the optimal individuals. The specific implementation process is as follows:

s90201, calculating the fitness value of the temporary population, executing an elite selection operator, and placing the selected individuals into a new sub-population until the population size is popsize.

In this step, the fitness value of the temporary population is calculated, and an elite selection operator is executed to place the selected individuals into a new sub-population, which can refer to step S302 above and will not be described herein again.

S90202, selecting an individual with the maximum fitness value in the sub-population sPop to be marked as an optimal individual pBest, and recording a code pBestCode and the fitness value pBestFit of the optimal individual.

In step S10, it is determined whether the current iteration number run is greater than the maximum iteration number runtime, if so, the algorithm is terminated, the value with the minimum fitness value in the optimal individuals is the fitness value of the globally optimal individual, and the code of the optimal individual is the code of the globally optimal individual, the fitness value and the code of the globally optimal individual are output, and the output globally optimal individual code is the optimal scheduling scheme; if not, go to step S4, if run is equal to run + 1. The specific implementation process is as follows:

judging whether run > runtime is established, if so, terminating the algorithm, enabling the maximum value of the fitness value pBestFit in the optimal individual to be the fitness value gBestFit of the global optimal individual, enabling the code pBestCode of the optimal individual to be the code gBestCode of the global optimal individual, finally outputting the optimal solution gBestFit and gBestCode, and enabling the output global optimal individual code gBestCode to be the optimal scheduling scheme; if not, go to step S4, if run is equal to run + 1.

The embodiment of the invention also provides a multi-target scheduling system for minimizing delivery time and delay of high-end equipment, which comprises a computer, wherein the computer comprises:

at least one memory cell;

at least one processing unit;

wherein, at least one instruction is stored in the at least one storage unit, and the at least one instruction is loaded and executed by the at least one processing unit to realize the following steps:

s1, acquiring task data of high-end equipment, and setting input parameters of an improved non-dominated sorting genetic algorithm based on the task data; initializing execution parameters of the improved non-dominated sorting genetic algorithm; the execution parameters comprise population size popsize, maximum iteration number runtime and current iteration number run;

s2, generating a father population based on the improved non-dominated sorting genetic algorithm and the input parameters, and calculating the fitness value of individuals in the father population;

s3, dividing the father population into a plurality of small populations, and executing an improved crossover operator, an improved mutation operator and an elite selection operator to the plurality of small populations to generate sub-populations;

s4, combining the father population and the son population into a new population;

s5, performing improved quick sorting on the new population, and performing improved crowding calculation on part of individuals in the quickly sorted new population;

s6, executing an improved selection operator on the new population according to the result of the rapid sequencing and the improved crowding calculation, and generating a new father population with the population size of popsize;

s7, calculating the key path of the individual in the new father population, and determining the key path of the individual;

s8, codes on the individual key paths are appointed, the individuals with the appointed key path codes are selected to a new sub population, and the individuals in the father population and the new sub population are updated;

s9, executing an improved crossover operator, an improved mutation operator and an elite selection operator on all the individuals in the updated parent population to generate a new sub population, selecting the individual with the minimum fitness value in the sub population as a superior individual, and recording the code and the fitness value of the superior individual;

s10, judging whether the current iteration number run is larger than the maximum iteration number runtime, if so, terminating the algorithm, enabling the value with the minimum fitness value in the optimal individuals to be the fitness value of the globally optimal individual, enabling the code of the optimal individual to be the code of the globally optimal individual, outputting the fitness value and the code of the globally optimal individual, and enabling the output globally optimal individual code to be the optimal scheduling scheme; if not, go to step S4, if run is equal to run + 1.

According to the embodiment of the invention, after the father population is generated, the father population is divided into 4 small populations, different rapid sequencing and congestion degree calculation rules are set for the 4 small populations, and the 4 small populations are crossed in the evolution process, so that excellent genes in individuals can be transmitted among the populations, the whole population is effectively prevented from falling into a local optimal solution, the search range of the optimal solution is expanded, and the effect of the optimal scheduling scheme is effectively improved. The method provided by the invention effectively solves the problem of development project cooperative scheduling of minimized project delivery time and delivery delay, shortens the delivery time and delay time of multiple projects, and can provide good decision basis when an enterprise makes a plan.

Aiming at the problem of development project cooperative scheduling aiming at minimizing project delivery time and delivery delay, the embodiment of the invention firstly encodes a plurality of projects of tasks and resources thereof through an improved non-dominated sorting algorithm, determines the immediate front-to-back relationship and the used resources of each task, and then executes the tasks according to the immediate front-to-back relationship among the tasks, thereby obtaining the delivery time C of the plurality of projects_minAnd the total delivery delay Punish, and finally generating a group of multi-target dominance solutions. The method comprises the steps of initially randomly assigning resources of each task, generating a sub-population after selecting, crossing and mutating the population, combining a father population and the sub-population, obtaining a new population through fast non-dominated sorting and congestion degree calculation and non-dominated sorting, then selecting, crossing and mutating the population to obtain a next generation population, and updating the population through continuous iteration to optimize solution space and finally obtain the optimal solution of the problem. The improved non-dominated sorting algorithm shows superiority in convergence speed and solution quality of the solution.

After the embodiment of the invention selects and generates a new father population, the key routes of partial individuals in the population are calculated, the tasks on the key routes are subjected to resource assignment, and the optimal resources are distributed to the key tasks, so that the understanding quality is greatly improved, and the convergence speed of the algorithm is accelerated.

The above examples are only intended to illustrate the technical solution of the present invention, but not to limit it; although the present invention has been described in detail with reference to the foregoing embodiments, it will be understood by those of ordinary skill in the art that: the technical solutions described in the foregoing embodiments may still be modified, or some technical features may be equivalently replaced; and such modifications or substitutions do not depart from the spirit and scope of the corresponding technical solutions of the embodiments of the present invention.

Claims (10)

1. The multi-target scheduling method for minimizing delivery time and delay of high-end equipment is characterized by comprising the following steps of:

s1, acquiring task data of high-end equipment, and setting input parameters of an improved non-dominated sorting genetic algorithm based on the task data; initializing execution parameters of the improved non-dominated sorting genetic algorithm; the execution parameters comprise a population size popsize, a maximum iteration number runtime and a current iteration number run;

s2, generating a father population based on the improved non-dominated sorting genetic algorithm and the input parameters, and calculating the fitness value of individuals in the father population;

s3, dividing the father population into a plurality of small populations, and executing an improved crossover operator, an improved mutation operator and an elite selection operator to the plurality of small populations to generate sub-populations;

s4, combining the father population and the child population into a new population;

s5, performing improved quick sorting on the new population, and performing improved crowding calculation on part of individuals in the quickly sorted new population;

s6, executing an improved selection operator on the new population according to the result of the rapid sequencing and the improved crowding calculation, and generating a new father population with the population size of popsize;

s7, calculating a key path of the individuals in the new father population, and determining the key path of the individuals;

s8, codes on the individual key paths are appointed, the individuals with the appointed key path codes are selected to a new sub population, and the individuals in the father population and the new sub population are updated;

s9, executing an improved crossover operator, an improved mutation operator and an elite selection operator on all the individuals in the updated parent population to generate a new sub population, selecting the individual with the minimum fitness value in the sub population as a superior individual, and recording the code and the fitness value of the superior individual;

s10, judging whether the current iteration number run is larger than the maximum iteration number runtime, if so, terminating the algorithm, enabling the value with the minimum fitness value in the optimal individuals to be the fitness value of the globally optimal individual, enabling the code of the optimal individual to be the code of the globally optimal individual, outputting the fitness value and the code of the globally optimal individual, and enabling the output globally optimal individual code to be the optimal scheduling scheme; if not, go to step S4, if run is equal to run + 1.

2. The multi-objective scheduling method for high-end equipment-oriented delivery with minimum delay as claimed in claim 1, wherein the step S2 specifically comprises:

s201, encoding input parameters;

s202, generating a father population according to the coded input parameters, wherein the father population comprises popsize initial individuals;

s203, calculating the total delivery time C of each initial individual_maxAnd a delivery delay push value, using the two values as a set of solutions, and using the set of solutions to represent the fitness value of the initial individual.

3. The multi-objective scheduling method for high-end equipment-oriented delivery with minimum delay as claimed in claim 1, wherein the step S3 specifically comprises:

s301, dividing the father population into a plurality of small populations, and executing an improved crossover operator and an improved mutation operator on the plurality of small populations to generate new temporary populations;

s302, calculating the fitness of individuals in the temporary population, executing an elite selection operator, and selecting popsize individuals from the temporary population to form a sub-population.

4. The multi-objective scheduling method for high-end equipment-oriented delivery with minimum delay as claimed in claim 3, wherein the step S301 specifically comprises:

s30101, dividing the father population into 4 small populations with the size of popsize/4, and respectively recording the small populations as population 1, population 2, population 3 and population 4;

s30102, performing an improved crossover operator on the small population, including:

s30102a, for each of the group 1 and the group 2, let k be 1 and let the crossing probability of the kth individual be

Wherein f is₁max and f₁min is expressed as delivery time C of all individuals in population 1_maxMaximum and minimum values of f₁x_kIndicating delivery time C of kth individual of population 1_maxGo to step S30102 b;

s30102b, selecting the kth individuals in the population 1 and the population 2 respectively, generating a random number rand1 between 0 and1, and comparing the random number rand1 with P_c1(k) If rand1 is greater than P_c1(k) If so, go to step S30102c, otherwise, go to step S30102b if k is k + 1;

s30102c, performing single-point crossing on the kth individual of the population 1 and the population 2, determining whether k > popoise/4 is true, if yes, going to step S30102d, otherwise, going to step S30102b if k is k + 1;

s30102d, for each of the group 3 and the group 4, let k be 1, and let the crossing probability of the kth individual be

Wherein f is₄max and f₄min is respectively expressed as the maximum and minimum of the individual delivery delays Punish in the population 4, f₄x_kA value indicating the delivery delay push of the kth individual of the population 4, and the process goes to step S30102 e;

s30102e, selecting the kth individuals from the population 3 and the population 4 respectively, generating a random number rand2 between 0 and1, and comparing the random number rand2 with P_c4(k) If rand2 is greater than P_c4(k) If so, go to step S30102f, otherwise, go to step S by setting k to k +130102e。

S30102f, performing single-point crossing on the kth individual of the population 3 and the population 4, judging whether k > popoise/4 is established or not, if so, finishing mutation, otherwise, turning to step S30102f, wherein k is k + 1;

s30103, performing an improved mutation operator on the small population after the improved crossover operator is performed, wherein the improved mutation operator comprises:

s30103a, for population 1 after the improved crossover operator is performed, k is set to 1, and the mutation probability of the kth individual is set to

Wherein f is₁max and f₁min is expressed as delivery time C of all individuals in population 1_maxMaximum and minimum values of f₁x_kIndicating delivery time C of kth individual of population 1_maxGo to step S30103 b;

s30103b, selecting the kth individual of the population 1, and generating a random number rand3 between 0 and1, if the random number rand3 is more than P_m1(k) If yes, go to step S30303c, otherwise, go to step S30103b if k is k + 1;

s30103c, mutating the code of the kth individual of the population 1, if the task corresponding to the code is a virtual layer task, the code is unchanged, if the task corresponding to the code is a meta-task, a resource is randomly selected from the available resource range of the meta-task as the code of the meta-task, and it is determined whether k > poison/4 is true, if yes, step S30103d is performed, otherwise, k is k +1, and step S30103b is performed;

s30103d, for population 4 after the improved crossover operator is performed, k is set to 1, and the mutation probability of the kth individual is set to

Wherein f is₄max and f₄min is expressed as the maximum and minimum delivery delay Punish of all individuals in the population 4, respectively, f₄x_kValue representing the delivery delay Punish of the kth individual of the population 4, step by stepS30103b；

S30103e, selecting the kth individual of the population 4, and generating a random number rand4 between 0 and1, if the random number rand4 is more than P_m4(k) If so, go to step S30103c, otherwise, go to step S30103e if k is k + 1;

s30103f, mutating the code of the kth individual of the population 4, if the task corresponding to the code is a virtual layer task, the code is unchanged, if the task corresponding to the code is a meta-task, a resource is randomly selected from the available resource range of the meta-task as the code of the meta-task, and it is determined whether k > poison/4 is true, if yes, step S30103g is performed, otherwise, k is k +1, and step S30103e is performed;

s30103g, for population 2 after the improved crossover operator is performed, k is set to 1, and the mutation probability of the kth individual is set to

Where the slice represents the maximum dominance level produced by the individuals in population 2 after non-dominance ranking, g_kIndicating the non-dominant ranking rank of the kth individual, go to step S30103 h;

s30103h, selecting kth individual of the population 2, generating a random number rand5 between 0 and1, and judging whether the random number rand5 is less than P_c2(k) If yes, go to step S30103i, otherwise k equals k + 1; go to step S30103 h;

s30103i, mutating the code of the kth individual of the population 2, if the task corresponding to the code is a virtual layer task, the code is unchanged, if the task corresponding to the code is a meta-task, a resource is randomly selected from the available resource range of the meta-task as the code of the meta-task, and it is determined whether k > poison/4 is true, if yes, step S30103j is performed, otherwise, k is k +1, and step S30103h is performed;

s30103j, for the population 3 after the improved crossover operator is performed, k is set to 1, and the mutation probability of the kth individual is set to

Where the slice represents the maximum dominance level produced by the individuals in population 3 after non-dominance ranking, g_kIndicating the non-dominant ranking rank of the kth individual, go to step S30103 k;

s30103k, selecting kth individual of the population 3, generating a random number rand6 between 0 and1, and judging whether the random number rand6 is less than P_c3(k) If yes, go to step S30103m, otherwise k equals k + 1; go to step S30103 k;

s30103m, carrying out mutation on the code of the kth individual of the population 3, if the task corresponding to the code is a virtual layer task, the code is unchanged, if the task corresponding to the code is a meta-task, a resource is randomly selected from the available resource range of the meta-task as the code of the meta-task, whether k > poison/4 is satisfied is judged, if yes, the mutation operator is ended, otherwise, k is k +1, and the step S30103k is carried out;

s30104, forming a new temporary population by the 4 small population groups 1, 2, 3 and4 after the improved mutation operator is executed.

5. The multi-objective scheduling method for high-end equipment-oriented delivery with minimum delay as claimed in claim 3, wherein the step S302 specifically comprises:

s30201, calculating the fitness of individuals in the temporary population;

s30202, executing an elite selection operator, selecting popsize individuals from the temporary population, and generating a sub-population, wherein the method comprises the following steps:

s30202a, for the temporary population 1, when a new individual is generated by mutation of the individual in the population 1, calculating the delivery time C of the mutated individual_maxIf the delivery time C of the newly generated individual is_maxIf the value of (A) is less than the value of the original individual, the mutated individual is retained, and the original individual is discarded; otherwise, the original individual is kept, and the variant individual is discarded;

s30202b, for the population 4 in the temporary population, when the individuals in the population 4 generate new individuals through mutation, calculating the delivery delay Punish value of the mutated individuals, if the delivery delay Punish value of the newly generated individuals is smaller than that of the original individuals, keeping the mutated individuals, and discarding the original individuals; otherwise, the original individual is kept, and the variant individual is discarded;

S30202C, for the population 2 and the population 3 in the temporary population, when the individuals in the population 2 and the population 3 have variation, calculating the delivery time C of the varied individuals_maxIf the fitness value of the individual generated after the mutation is not governed by the fitness value of the original individual, the mutated individual is reserved; otherwise, the original individual is kept, and the variant individual is discarded;

the individuals retained in steps S30202a to S30202c constitute a sub-population, the population size of the sub-population being popsize.

6. The multi-objective scheduling method for high-end equipment-oriented delivery with minimum delay as claimed in claim 1, wherein the step S5 specifically comprises:

s501, dividing the new population with the population scale of 2popsize into 4 populations with the population scale of 2popsize/4, wherein the 4 populations comprise a population 1, a population 2, a population 3 and a population 4;

s502, carrying out improved quick sequencing on the new population;

s503, calculating the improved crowding degree of part of individuals in the quickly sorted new population.

7. The multi-objective scheduling method for high-end equipment-oriented delivery with minimum delay of claim 6, wherein in step S502, the improved fast ranking of new population comprises:

s5021, calculating the fitness of the individuals in the 4 populations to obtain a fitness value f (x) of each individual;

s5022, aiming at minimizing delivery time C for the population 1_maxOn the principle of delivery time C_maxSequentially putting the individuals in the population 1 into the set C from small to large;

s5023, regarding the population 4, sequentially putting individuals in the population 1 into a set P from small to large according to the value of the delivery delay push on the principle of minimizing the delivery delay push of a target;

s5024, for the population 2 and the population 3, finding the solution set n of the dominated solution of each individual k in the population according to the pareto principle through the value of the fitness value f (x) of each individual_kAnd dominating solution set s_kTurning to step S5025;

s5025, enabling j to be 1, and finding out all n in the population_k0 individuals, storing them in the current set Z_jTurning to step S5026;

s5026, aiming at the current set Z_jEach individual k in (a), looking at the set s of individuals it governs_kWill aggregate s_kN of each individual k in_kSubtracting 1, i.e. the number of solution entities dominating the individual k minus 1, if n_k-1-0, let j-j +1 and store the individual k in another set Z_jTurning to step S5027;

s5027 with Z_jFor the current set, step S5026 is repeated until the entire new population is stratified.

8. The multi-objective scheduling method for high-end equipment-oriented delivery time and delay minimization of claim 6, wherein in step S503, the performing the improved crowdedness calculation on the part of individuals in the rapidly-sorted new population comprises:

s5031, performing rapid non-dominated sorting on each individual in the population 2 and the population 3 to obtain a layered population;

s5032, delivery time C for each layer_maxThe individual with the minimum value and the minimum delivery delay push value is made to have the crowdedness degree of 0; for the remaining individuals k, use the formula

The crowdedness distance of each individual is calculated. f. of₁(k +1) and f₁(k-1) shows delivery times C of two individuals in the vicinity of the individual, respectively_maxValue f₂(k +1) and f₂(k-1) respectively represents the delivery delay push values of two individuals in the vicinity of the individual.

9. The multi-objective scheduling method for high-end equipment-oriented delivery with minimum delay as claimed in claim 1, wherein the step S6 specifically comprises:

s601, for all individuals in the population 2 and the population 3, making j equal to 1, and for a new population, finding out a set Z obtained by fast sequencing_jSelecting all the individuals in the individual group to a new father group;

s602, setting the selected individual number as D, judging whether the selected individual number D is more than popsize/4, if so, executing a step S604, otherwise, executing a step S603;

s603, let j equal to j +1, find out the set Z_jAll congestion degrees in (2) are less than set Z_jIndividuals with average crowdedness, and marking these individuals as T_iAnd puts them into the new father group, executes step S602;

s604, marking the new father group as T_jThe individuals in the tree are sorted from big to small according to their crowdedness and the top is sorted

Individuals are removed from the new parent population;

s605, for the group 1, according to the delivery time C_maxSelecting the individuals in the set C into a set M from small to large, stopping selection if the number of the individuals in the set M is pop/4, and putting all the individuals in the set M into a new father group;

s606, as for the population 4, selecting the individuals in the set P to the set L from small to large according to the value of the delivery delay Punish, if the number of the individuals in the set L is popoise/4, stopping the selection, and putting all the individuals in the set L into a new father population.

10. A multi-objective scheduling system for high-end equipment-oriented delivery with minimal time and delay, the system comprising a computer, the computer comprising:

at least one memory cell;

at least one processing unit;

wherein the at least one memory unit has stored therein at least one instruction that is loaded and executed by the at least one processing unit to perform the steps of:

s1, acquiring task data of high-end equipment, and setting input parameters of an improved non-dominated sorting genetic algorithm based on the task data; initializing execution parameters of the improved non-dominated sorting genetic algorithm; the execution parameters comprise a population size popsize, a maximum iteration number runtime and a current iteration number run;

s2, generating a father population based on the improved non-dominated sorting genetic algorithm and the input parameters, and calculating the fitness value of individuals in the father population;

s3, dividing the father population into a plurality of small populations, and executing an improved crossover operator, an improved mutation operator and an elite selection operator to the plurality of small populations to generate sub-populations;

s4, combining the father population and the child population into a new population;

s5, performing improved quick sorting on the new population, and performing improved crowding calculation on part of individuals in the quickly sorted new population;

s6, executing an improved selection operator on the new population according to the result of the rapid sequencing and the improved crowding calculation, and generating a new father population with the population size of popsize;

s7, calculating a key path of the individuals in the new father population, and determining the key path of the individuals;

s8, codes on the individual key paths are appointed, the individuals with the appointed key path codes are selected to a new sub population, and the individuals in the father population and the new sub population are updated;

s9, executing an improved crossover operator, an improved mutation operator and an elite selection operator on all the individuals in the updated parent population to generate a new sub population, selecting the individual with the minimum fitness value in the sub population as a superior individual, and recording the code and the fitness value of the superior individual;

s10, judging whether the current iteration number run is larger than the maximum iteration number runtime, if so, terminating the algorithm, enabling the value with the minimum fitness value in the optimal individuals to be the fitness value of the globally optimal individual, enabling the code of the optimal individual to be the code of the globally optimal individual, outputting the fitness value and the code of the globally optimal individual, and enabling the output globally optimal individual code to be the optimal scheduling scheme; if not, go to step S4, if run is equal to run + 1.

Images