CN108320059B - Workflow scheduling evolution optimization method and terminal equipment - Google Patents

Abstract

The invention is applicable to the technical fields of cloud computing and artificial intelligence, and provides a workflow scheduling evolutionary optimization method and terminal equipment. The workflow scheduling evolutionary optimization method includes: designing a multi-chromosome pair coding structure; constructing a balanced mixed initialization population; adaptively calculating relevant variables; performing a re-evolution operation; and optimizing a scheduling strategy. The above-mentioned workflow scheduling evolutionary optimization method can provide a scheduling strategy that meets user needs with a high deadline constraint satisfaction rate and low execution cost, and provides a reference implementation for building a workflow scheduling evolutionary optimization system under deadline constraints. .

Description

A workflow scheduling evolutionary optimization method and terminal device

technical field

The invention belongs to the technical field of cloud computing and artificial intelligence, and in particular relates to a workflow scheduling evolutionary optimization method and terminal equipment.

Background technique

Tasks in cloud computing increasingly exist in the form of workflows. Such workflows are typically data-intensive and computationally-intensive applications. Since the workflow has a large amount of data and computing requirements, cloud computing is required to provide high-performance computing resources. Cloud computing takes computing resources as a service and dynamically provides them to users in the form of virtual machines according to their needs. The modes of cloud computing to provide resource services mainly include: Infrastructure as a Service (IaaS), Platform as a Service (PaaS) and Software as a Service (SaaS). The infrastructure cloud provides services to users in the form of virtual resource pools, and allocating computing resources to workflows through scheduling technology has become a research focus in the field of cloud computing and artificial intelligence.

Workflow scheduling in the cloud environment refers to the process of matching different computing resources for different computing tasks in the workflow and finding the optimal matching solution according to the computing needs of users in a specific cloud environment. During workflow scheduling, tasks are allocated and optimized. By extracting the characteristics of workflow tasks and their mutual data dependencies, a formulaic description of the workflow problem is obtained, and then it is modeled, and computing resources are allocated to it, and the allocation strategy is determined to satisfy User needs and optimization. Workflow scheduling attempts to establish the corresponding relationship between computing tasks, computing resources, and user requirements, and measure its adaptability. Scheduling is used to map between computing tasks and computing resources. For example, from the changes in execution time and execution cost between computing tasks with different computing scales and computing resources with different computing performance, find out the trajectory of the change of the target optimization item. In the cloud computing workflow scheduling system, the workflow content is usually described by node characteristics. In fact, the workflow based on cloud computing can be divided into three steps: workflow modeling, task resource mapping and policy optimization.

Workflow scheduling is an important application of artificial intelligence. The main purpose is to allocate and adjust the required computing resources for computing tasks in the workflow. It can also be called the optimization problem of resource scheduling under constraints. Resource scheduling is mainly to allocate computing resources in the computing resource pool. Usually, the resource scheduling optimization problem under constrained conditions is to use a penalty function to punish inappropriate scheduling strategies and convert the constrained problem into an unconstrained problem. In addition to the continuous optimization and improvement of traditional scheduling algorithms, some evolutionary algorithms have also been adopted to generate near-optimal scheduling policies. Rodriguez and Buyya proposed a particle swarm optimization algorithm based on meta-heuristic optimization technology for scientific workflow scheduling in cloud environment. Some basic features, such as the elasticity and heterogeneity of computing resources. However, the use of a penalty function in the algorithm that the particles that do not meet the constraints are not as good as the legitimate particles may cause the algorithm to converge prematurely and fall into a local optimum. Li Liu et al. proposed a cooperative genetic algorithm CGA ² based on deadline constraints, which ensures that the overall execution cost is minimized under the conditions of meeting deadline constraints, which can accelerate convergence and avoid premature maturity. However, the introduction of co-evolutionary operations in the algorithm will increase the amount of computation, and because it is a greedy strategy in nature, the optimal value cannot be obtained according to the constraint requirements in some cases.

SUMMARY OF THE INVENTION

In view of this, embodiments of the present invention provide an evolutionary optimization method and terminal device for workflow scheduling, so as to solve the problems of low deadline constraint satisfaction rate and high execution cost in the prior art.

A first aspect of the embodiments of the present invention provides an evolutionary optimization method for workflow scheduling, including:

Step S1, according to the user input parameters and workflow data, select chromosomes in the genetic algorithm population as the scheduling strategy information carrier, and design the information encoding structure of the multiple chromosome pair W in combination with the population size M, the computing resource size N and the workflow data; the user Input parameters include deadline constraint parameters;

Step S2, according to any multiple chromosome pair constructed by the information coding structure, cycle the construction process of a single multiple chromosome pair according to the construction method to form a balanced mixed initialization population with a scale of M;

Step S3, initialize the population according to the balanced mixture, construct an evolution process, adjust the evolution direction according to the user input parameters, construct an improved fitness according to the user input parameters and the original fitness correction mean, and calculate according to the fitness During the evolution process, the adaptive crossover probability Pc and the adaptive mutation probability Pm of each chromosome of the population are genetically manipulated for each chromosome and the resulting scheduling strategy is stored in the scheduling optimization strategy pool A;

Step S4, the ω chromosomes in the optimal strategy pool A are used as the input of the re-evolution operation under the deadline constraint, and M-ω randomly generated chromosomes are added to obtain the re-evolved population as the input of step S3 and iteratively execute according to the established rules. After further evolution, the obtained scheduling strategies are stored in the scheduling optimization strategy pool B;

Step S5, comprehensively evaluate each scheduling strategy of the scheduling optimization strategy pool A and the scheduling optimization strategy pool B, match the deadline constraints, and compare the deadline constraint satisfaction rate and execution cost, evaluate the algorithm execution efficiency, and finally determine the optimal scheduling. Strategy.

Optionally, the information coding structure of the multiple chromosome pair W in step S1 contains a total of 2 chromosomes, that is,

Multiple chromosome pair W={chromesome1,chromesome2}

chromesome1=sequence of{Pc,Pm,gen ₀ ,gen ₁ ,…,gen _k ,…,gen _L-1 }

chromesome2={tof ₀ ,tof ₁ ,…,tof _i ,…,tof _N-1 }

Assuming that on the ith virtual machine, the size of the execution sequence is g, then tof _i can be expressed as:

Among them, Pc is the adaptive crossover probability of the chromosome; Pm is the adaptive mutation probability of the chromosome; gen _k is the gene at the k position of the chromosome, 0≤k<L; vm _i is the ith virtual machine in the computing resources, 0 ≤i<N; tof _i is the execution sequence of the computing task assigned to the computing resource vm _i ; the gene gen in the chromesome1 chromosome is coded as t(vm), indicating that the computing task t allocates the computing resource vm; the gene vm in the chromesome2 chromosome represents the computing resource , and the subsequent gene set {t} represents the computing task allocated to the computing resource vm.

Optionally, according to any multiple chromosome pair constructed by the information coding structure, cycle the construction process of a single multiple chromosome pair according to the construction method to form a balanced mixed initialization population with a scale of M. The specific process is as follows:

According to the chromosome pair coding structure obtained in step S1, assuming that k methods are used to construct the initialization population, then construct x ₁ chromosome pairs according to method 1, construct x _i chromosome pairs according to method i, and construct x _k chromosome pairs according to method k, An equilibrium mixed initial population of size M is obtained; where k ≥ 2,

Optionally, the improved fitness is constructed according to the user input parameters and the original fitness correction mean, and the adaptive crossover probability Pc and the adaptive mutation probability Pm of each chromosome of the population in the evolution process are calculated according to the fitness. The specific process as follows:

For the balanced mixed initialization population, the original fitness vector F _ini of the chromosome is calculated according to the deadline constraint, the mean value is corrected according to the original fitness, and the improved fitness vector F _imp is constructed;

Use the maximum improved fitness value to subtract the current improved fitness value, and divide by the difference between the maximum improved fitness value and the modified average value of the improved fitness to obtain the probability intermediate variable V _mi ;

When the improved fitness value is less than its revised mean, the probability correction variable takes the value of 1;

Multiply the relationship between the improved fitness value and its revised mean value with different parameters and mark it as Pc;

Take M target chromosome samples, and repeat the above process to obtain M Pc values;

Based on the same process, Pm can be obtained.

Optionally, the process of determining the preferred scheduling policy in step S5 is as follows:

Perform steps S2, S3 and S4 on all chromosomes in the population to obtain the scheduling optimization strategy pool A and the scheduling optimization strategy pool B, and use the deadline constraint satisfaction rate as the evaluation criterion to compare the scheduling optimization obtained in steps S4 and S5. Strategy pool A and scheduling optimization strategy pool B;

determining secondary constraints according to the user input information; the user input information further includes secondary constraint information;

If the fitness of a scheduling optimization strategy is optimal and does not violate the secondary deadline constraint, or the degree of violation of the deadline constraint is the smallest relative to other scheduling optimization strategies, the scheduling optimization strategy is determined as the target scheduling optimization strategy, and given output the scheduling result.

In a second aspect of the embodiments of the present invention, a terminal device is provided, including a memory and a processor, where the memory stores a computer program that can run on the processor, and when the processor executes the computer program Implement the following steps:

Step S1, according to the user input parameters and workflow data, select chromosomes in the genetic algorithm population as the scheduling strategy information carrier, and design the information encoding structure of the multiple chromosome pair W in combination with the population size M, the computing resource size N and the workflow data; the user Input parameters include deadline constraint parameters;

Step S2, according to any multiple chromosome pair constructed by the information coding structure, cycle the construction process of a single multiple chromosome pair according to the construction method to form a balanced mixed initialization population with a scale of M;

Step S3, initialize the population according to the balanced mixture, construct an evolution process, adjust the evolution direction according to the user input parameters, construct an improved fitness according to the user input parameters and the original fitness correction mean, and calculate according to the fitness During the evolution process, the adaptive crossover probability Pc and the adaptive mutation probability Pm of each chromosome of the population are genetically manipulated for each chromosome and the resulting scheduling strategy is stored in the scheduling optimization strategy pool A;

Step S4, the ω chromosomes in the optimal strategy pool A are used as the input of the re-evolution operation under the deadline constraint, and M-ω randomly generated chromosomes are added to obtain the re-evolved population as the input of step S3 and iteratively execute according to the established rules. After further evolution, the obtained scheduling strategies are stored in the scheduling optimization strategy pool B;

Step S5, comprehensively evaluate each scheduling strategy of the scheduling optimization strategy pool A and the scheduling optimization strategy pool B, match the deadline constraints, and compare the deadline constraint satisfaction rate and execution cost, evaluate the algorithm execution efficiency, and finally determine the optimal scheduling. Strategy.

Optionally, the information coding structure of the multiple chromosome pair W in step S1 contains a total of 2 chromosomes, that is,

Multiple chromosome pair W={chromesome1,chromesome2}

chromesome1=sequence of{Pc,Pm,gen ₀ ,gen ₁ ,…,gen _k ,…,gen _L-1 }

chromesome2={tof ₀ ,tof ₁ ,…,tof _i ,…,tof _N-1 }

Assuming that on the ith virtual machine, the size of the execution sequence is g, then tof _i can be expressed as:

Among them, Pc is the adaptive crossover probability of the chromosome; Pm is the adaptive mutation probability of the chromosome; gen _k is the gene at the k position of the chromosome, 0≤k<L; vm _i is the ith virtual machine in the computing resources, 0 ≤i<N; tof _i is the execution sequence of the computing task assigned to the computing resource vm _i ; the gene gen in the chromesome1 chromosome is coded as t(vm), indicating that the computing task t allocates the computing resource vm; the gene vm in the chromesome2 chromosome represents the computing resource , and the subsequent gene set {t} represents the computing task allocated to the computing resource vm.

Optionally, according to any multiple chromosome pair constructed by the information coding structure, cycle the construction process of a single multiple chromosome pair according to the construction method to form a balanced mixed initialization population with a scale of M. The specific process is as follows:

According to the chromosome pair coding structure obtained in step S1, assuming that k methods are used to construct the initialization population, then construct x ₁ chromosome pairs according to method 1, construct x _i chromosome pairs according to method i, and construct x _k chromosome pairs according to method k, An equilibrium mixed initial population of size M is obtained; where k ≥ 2,

Optionally, the improved fitness is constructed according to the user input parameters and the original fitness correction mean, and the adaptive crossover probability Pc and the adaptive mutation probability Pm of each chromosome of the population in the evolution process are calculated according to the fitness. The specific process as follows:

For the balanced mixed initialization population, the original fitness vector F _ini of the chromosome is calculated according to the deadline constraint, the mean value is corrected according to the original fitness, and the improved fitness vector F _imp is constructed;

Use the maximum improved fitness value to subtract the current improved fitness value, and divide by the difference between the maximum improved fitness value and the modified average value of the improved fitness to obtain the probability intermediate variable V _mi ;

When the improved fitness value is less than its revised mean, the probability correction variable takes the value of 1;

Multiply the relationship between the improved fitness value and its revised mean value with different parameters and mark it as Pc;

Take M target chromosome samples, and repeat the above process to obtain M Pc values;

Based on the same process, Pm can be obtained.

Optionally, the process of determining the preferred scheduling policy in step S5 is as follows:

Perform steps S2, S3 and S4 on all chromosomes in the population to obtain the scheduling optimization strategy pool A and the scheduling optimization strategy pool B, and use the deadline constraint satisfaction rate as the evaluation criterion to compare the scheduling optimization obtained in steps S4 and S5. Strategy pool A and scheduling optimization strategy pool B;

determining secondary constraints according to the user input information; the user input information further includes secondary constraint information;

If the fitness of a scheduling optimization strategy is optimal and does not violate the secondary deadline constraint, or the degree of violation of the deadline constraint is the smallest relative to other scheduling optimization strategies, the scheduling optimization strategy is determined as the target scheduling optimization strategy, and given output the scheduling result.

In a third aspect of the embodiments of the present invention, a computer-readable storage medium is provided, where the computer-readable storage medium stores a computer program, and when the computer program is executed by a processor, the implementation of the first aspect of the embodiments of the present invention is implemented. steps of any of the methods described.

In the embodiment of the present invention, in view of the characteristics of the workflow task set, a Re-Evolution strategy is proposed based on the genetic algorithm to solve the problems of local optimization and slow convergence, and a multi-chromosome pair coding structure is proposed, The workflow scheduling strategy can be fully described according to the workflow task node information, and then the survival rate of effective genes can be guaranteed by adaptively calculating the relevant variables of the mean value under the constraint of the deadline, and the final optimization can be selected from the two scheduling optimization resource pools according to the established rules. scheduling strategy. Compared with the existing scheduling methods based on evolutionary algorithms, this method reduces the amount of computation, can ensure the satisfaction rate required by the constraints of specific application scenarios, and ensure the controllable execution efficiency of the algorithm, and can avoid problems such as local optimization and slow convergence.

Description of drawings

In order to illustrate the technical solutions in the embodiments of the present invention more clearly, the following briefly introduces the accompanying drawings that need to be used in the description of the embodiments or the prior art. Obviously, the drawings in the following description are only for the present invention. In some embodiments, for those of ordinary skill in the art, other drawings can also be obtained according to these drawings without any creative effort.

1 is a block diagram of a workflow scheduling evolutionary optimization method provided by an embodiment of the present invention;

2 is a flowchart of a method for evolutionary optimization of workflow scheduling provided by an embodiment of the present invention;

3 is a schematic diagram of a scientific workflow structure provided by an embodiment of the present invention;

4 is a schematic diagram of a running environment of a workflow scheduling evolutionary optimization program provided by an embodiment of the present invention;

FIG. 5 is a program module diagram of a workflow scheduling evolution optimization program provided by an embodiment of the present invention.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are part of the embodiments of the present invention, but not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.

The invention constructs a workflow scheduling evolutionary optimization method based on a genetic algorithm (Genetic Algorithm, GA) for the workflow task set, designs and describes the coding structure of multiple chromosome pairs, establishes efficient chromosome pairs, and constructs a balanced mixed initialization population. Based on the relevant variables of the fitness of the contemporary population, the adaptive calculation designs the re-evolution operation, which provides a reference implementation for the optimization of the workflow scheduling strategy and the acceleration of the convergence.

The present invention is a calculation method for self-adaptively calculating relevant variables, constructing an evolutionary process and a re-evolutionary process, comprehensively evaluating the merits and demerits of scheduling strategies, and optimizing the final result according to the deadline constraint provided by the user. According to the information characteristics of the task nodes in the workflow task set, the coding structure of multiple chromosome pairs, balanced mixed initialization population, relevant variables for calculating the adaptive mean value under the constraint of deadline, re-evolution strategy, scheduling optimization strategy resource pool and search method are proposed. Based on concepts such as optimal scheduling strategy, a new evolutionary optimization method for workflow scheduling under the constraint of deadline is designed.

In order to illustrate the technical solutions of the present invention, the following specific embodiments are used for description.

In order to accurately describe the embodiments of the present invention, the following terms and meanings are first explained.

Task: refers to the basic unit scheduled by the scheduling evolutionary optimization method. The task of gene representation in chromosomes is used in the present invention. The task has information such as task number, scale, received data scale, sent data scale, and dependencies.

Resource: A resource is used for computing tasks, and in the present invention refers specifically to a virtual machine. Generally, a virtual machine has information such as virtual machine number, performance, status, and price.

Workflow: A form of collection of tasks. Generally, a workflow is a collection including multiple tasks and their dependencies, and a scientific workflow is a more important and complex one in the workflow.

Chromosome pair: In the present invention, chromosome pair specifically refers to the designed multiple chromosome pair, which is used to describe the main features of the work. Different chromosomes in the chromosome pair play different roles in different stages of gene manipulation, and are also called individuals.

Adaptive calculation of related variables: adaptive variables in scheduling evolutionary optimization methods, such as improved fitness, crossover and mutation probability, selection probability, and penalty function. The deficiency of premature and local convergence caused by the heterogeneity and dynamics of computing resources can be avoided by adaptively calculating relevant variables.

Gene manipulation: Gene manipulation mainly refers to operations such as crossover, mutation and selection in the evolutionary process of the present invention.

Scheduling optimization strategy resource pool: stores scheduling strategies to provide support for re-evolution and optimal scheduling strategies.

Constraints: Refers to the requirements put forward by users as the main constraints. The present invention takes the deadline as the main constraint, and takes the execution cost as the secondary constraint.

Constraint Satisfaction Rate: Compare the constraint item with the constraint condition, execute it several times, and count the ratio of satisfying the constraint. This ratio is called the constraint satisfaction rate. The higher the constraint satisfaction rate, the better the corresponding scheduling strategy.

Fitness: Determining the pros and cons of scheduling strategies is the key to determining the direction of evolution.

Re-evolution: On the basis of the current evolution results, rebuild the re-evolutionary population according to the established rules, evolve again, and store the re-evolution results in the corresponding scheduling optimization strategy resource pool, which can avoid falling into local optimum and premature evolution in ordinary evolution results. question.

Example 1

FIG. 1 and FIG. 2 respectively show the basic structure and implementation process of the workflow scheduling evolutionary optimization method provided in Embodiment 1 of the present invention, and the details are as follows:

Step S1, according to the user input parameters and workflow data, select chromosomes in the genetic algorithm population as the scheduling strategy information carrier, and design the information encoding structure of the multiple chromosome pair W in combination with the population size M, the computing resource size N and the workflow data; the user Input parameters include deadline constraint parameters.

In this step, the multiple chromosome pair coding structure includes multiple chromosome pairs, and different chromosomes contain different information. In the process of the scheduling evolution optimization method disclosed in the present invention, the workflow data is no longer relied on, and multiple chromosome pairs are used to describe the tasks and related information in the workflow. The method disclosed in the present invention selects the task number (0-(L-1)) and the number of tasks (L) extracted from the workflow; the number (0-(N-1)) and the number (N) of the virtual machines in the resource pool ; Crossover probability and mutation probability and other information, design multiple chromosome pairs W coding structure.

Wherein, the information coding structure of the multiple chromosome pair W in this step includes 2 chromosomes in total, namely

Multiple chromosome pair W={chromesome1,chromesome2}

chromesome1=sequence of{Pc,Pm,gen ₀ ,gen ₁ ,…,gen _k ,…,gen _L-1 }

chromesome2={tof ₀ ,tof ₁ ,…,tof _i ,…,tof _N-1 }

Assuming that on the ith virtual machine, the size of the execution sequence is g, then tof _i can be expressed as:

Among them, Pc is the adaptive crossover probability of the chromosome; Pm is the adaptive mutation probability of the chromosome; gen _k is the gene at the k position of the chromosome, 0≤k<L; vm _i is the ith virtual machine in the computing resources, 0 ≤i<N; tof _i is the execution sequence of the computing task assigned to the computing resource vm _i ; the gene gen in the chromesome1 chromosome is coded as t(vm), indicating that the computing task t allocates the computing resource vm; the gene vm in the chromesome2 chromosome represents the computing resource , and the subsequent gene set {t} represents the computing task allocated to the computing resource vm.

Step S2, according to any multiple chromosome pair constructed by the information coding structure, cycle the construction process of a single multiple chromosome pair according to the construction method to form a balanced mixed initialization population with a scale of M.

As a kind of embodiment, the concrete process of this step is as follows:

According to the chromosome pair coding structure obtained in step S1, assuming that k methods are used to construct the initialization population, then construct x ₁ chromosome pairs according to method 1, construct x _i chromosome pairs according to method i, and construct x _k chromosome pairs according to method k, An equilibrium mixed initial population of size M is obtained; where k ≥ 2,

Suppose that any multiple chromosome pair a is constructed according to the coding structure proposed in step (1); If there are M chromosome pairs in population B, there are k methods in total; the set of chromosome pairs constructed by method 1 is B1; the set of chromosome pairs constructed by method 2 is B2; ...; the set of chromosome pairs constructed by method k is Bk; then initialize the population B consists of k subpopulations. Follow method 1 to construct x ₁ chromosome pairs, method 2 to construct x ₂ chromosome pairs, ..., method i to construct x _i chromosome pairs, ..., method k to construct x _k chromosome pairs, resulting in a balanced mixture of size M initial population.

Let the set of chromosome pairs constituted by method 1

The set of chromosome pairs formed by method 2

By analogy, the set of chromosome pairs formed by method k is

Therefore, the composition of the balanced mixed initialization population B is: B={B1,B2,...,Bk}.

Step S3, initialize the population according to the balanced mixture, construct an evolution process, adjust the evolution direction according to the user input parameters, construct an improved fitness according to the user input parameters and the original fitness correction mean, and calculate according to the fitness In the evolution process, the adaptive crossover probability Pc and adaptive mutation probability Pm of each chromosome of the population are genetically manipulated for each chromosome and the resulting scheduling strategy is stored in the scheduling optimization strategy pool A.

Optionally, the improved fitness is constructed according to the user input parameter and the original fitness correction mean, and the adaptive crossover probability Pc and the adaptive mutation probability Pm of each chromosome of the population in the evolution process are calculated according to the fitness, The specific process is as follows:

For the balanced mixed initialization population, the original fitness vector F _ini of the chromosome is calculated according to the deadline constraint, the mean value is corrected according to the original fitness, and the improved fitness vector F _imp is constructed;

Use the maximum improved fitness value to subtract the current improved fitness value, and divide by the difference between the maximum improved fitness value and the modified average value of the improved fitness to obtain the probability intermediate variable V _mi ;

When the improved fitness value is less than its revised mean, the probability correction variable takes the value of 1;

Multiply the relationship between the improved fitness value and its revised mean value with different parameters and mark it as Pc;

Take M target chromosome samples, and repeat the above process to obtain M Pc values;

Based on the same process, Pm can be obtained.

specific,

Among them, P _c (i) represents the crossover probability of the ith chromosome pair in the contemporary population, and P _m (i) represents the mutation probability of the ith chromosome pair in the contemporary population. In equations (1) and (2), when the fitness f(i) of the i-th chromosome pair is less than or equal to the revised mean value f _cavg of the fitness of the current population, it is considered that the chromosome pair is in the Matured and Matured stages in the evolutionary process, using Crossover parameter k ₃ and mutation parameter k ₄ ; when the fitness f(i) of the i-th chromosome pair is greater than or equal to the revised mean value f _cavg of the fitness of the current population, it is considered that the chromosome pair is in the Initial and Undermatured stages in the evolution process, using Crossover parameter k ₁ and mutation parameter k ₂ . In order to avoid the influence of extremely poor chromosomes caused by mutation on the overall fitness average of the population, this embodiment adopts λ to correct the mean value f _cavg . Only used to correct for very poor chromosome pairs.

In formula (3), S _p represents the size of the current population, and f _c (i) represents the fitness of the corrected population chromosome pair.

Step S4, the ω chromosomes in the optimal strategy pool A are used as the input of the re-evolution operation under the deadline constraint, and M-ω randomly generated chromosomes are added to obtain the re-evolved population as the input of step S3 and iteratively execute according to the established rules. After further evolution, the obtained scheduling strategies are stored in the scheduling optimization strategy pool B.

In this step, according to the established rules, the ω chromosomes in the resource pool A of the scheduling optimization strategy are used as the input of the re-evolution operation, and (M-ω) randomly generated chromosomes are added to obtain the re-evolved population as the input of step S3, Iteratively re-evolves the algebra according to the established rules, and the obtained chromosomes are stored in the scheduling optimization strategy resource pool B to provide the scheduling strategy spare resources for step S5.

Let the storage population in the scheduling optimization strategy resource pool A be S _A : S _A ={a ₀ ,a ₁ ,...,a _M-1 };

The partial population selected according to the established rules is S ₁ : S ₁ ={a _i ,a _i+1 ,...a _i+ω };

The newly generated partial population is S ₂ : S ₂ ={a ₀ ,a ₁ ,...,a _M-1-ω };

Therefore, the resulting evolutionary population is S _new :

S _new ={S ₁ ,S ₂ }

Step S5, comprehensively evaluate each scheduling strategy of the scheduling optimization strategy pool A and the scheduling optimization strategy pool B, match the deadline constraints, and compare the deadline constraint satisfaction rate and execution cost, evaluate the algorithm execution efficiency, and finally determine the optimal scheduling. Strategy.

Optionally, the process of determining the preferred scheduling policy in this step is as follows:

Perform steps S2, S3 and S4 on all chromosomes in the population to obtain the scheduling optimization strategy pool A and the scheduling optimization strategy pool B, and use the deadline constraint satisfaction rate as the evaluation criterion to compare the scheduling optimization obtained in steps S4 and S5. Strategy pool A and scheduling optimization strategy pool B;

determining secondary constraints according to the user input information; the user input information further includes secondary constraint information;

If the fitness of a scheduling optimization strategy is optimal and does not violate the secondary deadline constraint, or the degree of violation of the deadline constraint is the smallest relative to other scheduling optimization strategies, the scheduling optimization strategy is determined as the target scheduling optimization strategy, and given output the scheduling result.

Specifically, let the number of re-evolution be z; the population formed by re-evolution is Sr; the storage population set in the scheduling optimization strategy pool B is S _B : S _B ={S _r1 ,S _r2 ,...,S _rz }; Let the number of chromosomes with the highest constraint satisfaction rate be h, then the set is represented as M _B : M _B ={m ₀ ,m ₁ ,...,m _h-1 }; Let the number of chromosomes with the lowest execution cost is e, then the set is represented as C _B : C _B ={c ₀ ,c ₁ ,...,c _e-1 }.

Compare each chromosome in the population set _{S B} and the population SA, first compare the constraint satisfaction rate, find all the chromosomes with the highest constraint satisfaction rate, and store these chromosomes in the constraint satisfaction rate chromosome set _MB ; if the scale of _MB is greater than ₁ , then traverse all chromosomes in the set MB, then compare the execution costs, find all the chromosomes with the lowest execution cost, and store them in the execution cost chromosome set _CB ; if the scale of _CB is greater than 1, traverse all the chromosomes in the set _CB , Then compare the efficiency of the method and find all the chromosomes with the highest efficiency. If the number of chromosomes is greater than 1, a chromosome is randomly selected as the result output.

The process of this embodiment is described below with a specific calculation example.

The experiment adopts the scientific workflow montage-25, in which there are 25 task nodes, the schematic diagram of which is shown in Figure 3; and 5 different types of virtual machines are used for simulation, and the virtual machine parameter settings refer to the Amazon EC2 configuration.

(1) Design multiple chromosome pair coding structures

Let the multiple chromosome pair description workflow task be set W. Due to space limitations, only the data of the 0th chromosome pair is listed.

W ₀ = {chromesome1,chromesome2}

chromesome1=sequence of{ _0.45,0.011 ,T4(0),...T24( ₄ )}

chromesome2=sequence of{vm ₀ ,T ₄ ,T ₁ ,T ₁₂ ,T ₁₆ ,T ₂₀ ,T ₂₁ ,T ₂₃ }

...

sequence of{vm ₄ ,T ₇ ,T ₁₀ ,T ₁₁ ,T ₁₇ ,T ₂₄ }

Among them, the first two genes of chromesome1 are 0.45 and 0.011, respectively, the crossover probability and mutation probability; the last 25 genes are the mapping pairs of computing tasks and computing resources, with a total of 27 genes.

Similarly, chromesome2 consists of five sub-chromosomes, in which the first gene in the sub-chromosome represents the allocated computing resources, and the subsequent genes represent the computing tasks performed on the No. 1 gene.

(2) Constructing a balanced mixed initialization population

According to step (1), the workflow task feature set W for obtaining multiple chromosome pairs has a total of 50 chromosome pairs. For example, two scheduling algorithms and random algorithms are selected, each scheduling generates 15 chromosome pairs, and the remaining 20 chromosome pairs are generated by the random algorithm.

(3) Adaptive calculation of relevant variables

According to formulas (1) and (2), the crossover probability and mutation probability of all chromosome pairs in W are adaptively calculated, and the probability matrix P is obtained,

And write the corresponding crossover probability and mutation probability to the corresponding locus of the corresponding chromosome pair.

(4) Perform re-evolution

According to the established rules, the 25 chromosome pairs in the resource pool A of the scheduling optimization strategy are used as the input of the re-evolution operation, and 25 randomly generated chromosome pairs are added to obtain the re-evolved population as the input of step (3), and iterate according to the established rules. The algebra is re-evolved, and the obtained chromosome pairs are all stored in the resource pool B of the scheduling optimization strategy to provide the scheduling strategy spare resources for step (5).

Let the storage population in the scheduling optimization strategy resource pool A be S _A :

S _A ={a ₀ ,a ₁ ,...,a ₄₉ };

Part of the population selected according to the established rules is S ₁ :

S ₁ ={a _i ,a _i+1 ,...,a _i+24 };

The newly generated partial population is S ₂ : S ₂ ={a ₀ ,a ₁ ,...,a ₂₄ };

Therefore, the resulting evolutionary population is S _new :

S _new ={S ₁ ,S ₂ }

Due to space limitations, only the data of the 0th chromosome pair is listed.

W ₀ = {chromesome1,chromesome2}

chromesome1=sequence of{0.25,0.002,T ₀ (2),...,T ₂₄ (3)}

chromesome2=sequence of{vm ₀ ,T ₄ ,T ₁ ,T ₃ ,...,T ₁₄ ,T ₁₆ ,T ₂₂ }

...

sequence of{vm ₄ ,T ₁₀ ,T ₂₀ ,T ₁₇ ,T ₁₉ ,T ₂₁ ,T ₂₃ }

(5) Optimal scheduling strategy

Comprehensively evaluate each chromosome in the scheduling optimization strategy pool A and the scheduling optimization strategy pool B, compare the fitness value and the execution cost, match the constraints, and finally determine the optimal scheduling strategy Final.

Final={chromesome1,chromesome2}

chromesome1=sequence of{0.07,0.001,T ₀ (2),...,T ₂₄ (2)}

chromesome2=sequence of{vm ₀ ,T ₄ ,T ₁ ,T ₃ ,...,T ₁₄ ,T ₁₇ ,T ₂₁ }

...

sequence of{vm ₄ ,T ₁₀ ,T ₂₀ ,T ₁₆ ,T ₁₉ ,T ₂₂ }

The comparison between the results of this embodiment and the other two methods is shown in Table 1. For example, when the application requirement deadline is constrained to be 328.7 units of time, the constraint satisfaction rate proposed by the present invention is 100%, and the execution cost is 13.2 units of cost; The constraint satisfaction rate is 10%, and the execution cost is 41.6 units; the CGA ² method has a constraint satisfaction rate of 60%, and the execution cost is 18.9 units. It can be seen from the table that under a given deadline constraint, the scheduling evolutionary optimization method of the present invention has a higher constraint satisfaction rate and lower execution cost than the PSO and CGA ² scheduling methods.

Table 1 Results comparison between the method of this embodiment and other methods

The above-mentioned workflow scheduling evolutionary optimization method, according to the characteristics of workflow task set, proposes a Re-Evolution strategy based on genetic algorithm to solve the problems of local optimization and slow convergence speed, and proposes a variety of chromosomes For the coding structure, the workflow scheduling strategy can be fully described according to the workflow task node information, and then the survival rate of effective genes can be guaranteed by adaptively calculating the relevant variables of the corrected mean value under the constraint of the deadline. The established rules prefer the final scheduling policy. Compared with the existing scheduling methods based on evolutionary algorithms, this method reduces the amount of computation, can ensure the satisfaction rate required by the constraints of specific application scenarios, and ensure the controllable execution efficiency of the algorithm, and can avoid problems such as local optimization and slow convergence. It has been verified that the workflow scheduling evolutionary optimization method under the deadline constraint disclosed in the present invention can meet the actual needs of the specified application, and has extensive reference value in the field of workflow scheduling optimization based on deadline constraint.

Corresponding to the workflow scheduling evolutionary optimization method described in the above embodiment, FIG. 4 shows a schematic diagram of the running environment of the workflow scheduling evolutionary optimization program provided by the embodiment of the present invention. For convenience of explanation, only the parts related to this embodiment are shown.

In this embodiment, the workflow scheduling evolution optimization program 400 is installed and run in the terminal device 40 . The terminal device 40 may include, but is not limited to, a memory 401 and a processor 402 . Figure 4 shows only the terminal device 40 having components 401-402, but it should be understood that implementation of all of the illustrated components is not required, and more or fewer components may be implemented instead.

In some embodiments, the memory 401 may be an internal storage unit of the terminal device 40 , such as a hard disk or a memory of the terminal device 40 . In other embodiments, the memory 401 may also be an external storage device of the terminal device 40, such as a plug-in hard disk, a smart memory card (Smart Media Card, SMC), a secure digital Secure Digital, SD) card, flash memory card (Flash Card), etc. Further, the memory 401 may also include both an internal storage unit of the terminal device 40 and an external storage device. The memory 401 is used to store application software and various types of data installed in the terminal device 40 , such as program codes of the workflow scheduling evolution optimization program 400 , and the like. The memory 401 can also be used to temporarily store data that has been output or will be output.

In some embodiments, the processor 402 may be a central processing unit (Central Processing Unit, CPU), a microprocessor or other data processing chips, and is used to execute the program code stored in the memory 401 or process data, such as executing The workflow scheduling evolution optimization program 400 and the like.

The terminal device 40 may further include a display, which in some embodiments may be an LED display, a liquid crystal display, a touch-sensitive liquid crystal display, an organic light-emitting diode (Organic Light-Emitting Diode, OLED) touch panel, and the like.

Please refer to FIG. 5 , which is a program module diagram of a workflow scheduling evolutionary optimization program 400 provided by an embodiment of the present invention. In this embodiment, the workflow scheduling evolution optimization program 400 may be divided into one or more modules, and the one or more modules are stored in the memory 401 and processed by one or more modules The processor (in this embodiment, the processor 402) is executed to complete the present invention. For example, in FIG. 5 , the workflow scheduling evolution optimization program 400 can be divided into an information coding structure design module 501 , a balanced mixed initialization population formation module 502 , a scheduling optimization strategy module 503 and a decision module 504 . The module referred to in the present invention refers to a series of computer program instruction segments capable of accomplishing specific functions, and is more suitable for describing the execution process of the workflow scheduling evolutionary optimization program 400 in the server 40 than a program. The following description will specifically introduce the functions of the modules 501-504.

Among them, the information coding structure design module 501 is used to select the chromosomes in the genetic algorithm population as the scheduling strategy information carrier according to the user input parameters and workflow data, and combine the population size M, computing resource size N and workflow data to design multiple chromosome pairs W information coding structure; the user input parameters include deadline constraint parameters.

The balanced mixed initialization population forming module 502 is used for any multiple chromosome pair constructed according to the information coding structure to cycle through the construction process of a single multiple chromosome pair according to the construction method to form a balanced mixed initialization population with a scale of M.

The scheduling optimization strategy module 503 is used for initializing the population according to the balanced mixture, constructing the evolution process, adjusting the evolution direction according to the user input parameters, constructing the improved fitness according to the user input parameters and the original fitness correction mean, and Calculate the adaptive crossover probability Pc and the adaptive mutation probability Pm of each chromosome of the population in the evolution process according to the fitness, perform genetic manipulation on each chromosome and store the obtained scheduling strategy in the scheduling optimization strategy pool A; and

The ω chromosomes in the optimal strategy pool A are used as the input of the re-evolution operation under the deadline constraint, and M-ω randomly generated chromosomes are added to obtain the re-evolved population as the input of step S3, and the re-evolution is performed iteratively according to the established rules, The obtained scheduling strategies are stored in the scheduling optimization strategy pool B;

The determination module 504 is used to comprehensively evaluate each scheduling strategy of the scheduling optimization strategy pool A and the scheduling optimization strategy pool B, match the deadline constraints, and compare the deadline constraint satisfaction rate and execution cost, evaluate the algorithm execution efficiency, and finally. Determine the preferred scheduling strategy.

As an embodiment, the information coding structure of the multiple chromosome pair W contains 2 chromosomes in total, namely

Multiple chromosome pair W={chromesome1,chromesome2}

chromesome1=sequence of{Pc,Pm,gen ₀ ,gen ₁ ,…,gen _k ,…,gen _L-1 }

chromesome2={tof ₀ ,tof ₁ ,…,tof _i ,…,tof _N-1 }

Assuming that on the ith virtual machine, the size of the execution sequence is g, then tof _i can be expressed as:

Among them, Pc is the adaptive crossover probability of the chromosome; Pm is the adaptive mutation probability of the chromosome; gen _k is the gene at the k position of the chromosome, 0≤k<L; vm _i is the ith virtual machine in the computing resources, 0 ≤i<N; tof _i is the execution sequence of the computing task assigned to the computing resource vm _i ; the gene gen in the chromesome1 chromosome is coded as t(vm), indicating that the computing task t allocates the computing resource vm; the gene vm in the chromesome2 chromosome represents the computing resource , and the subsequent gene set {t} represents the computing task allocated to the computing resource vm.

As another possible implementation manner, the balanced mixed initialization population forming module 502 is specifically configured to:

According to the chromosome pair coding structure obtained in step S1, assuming that k methods are used to construct the initialization population, then construct x ₁ chromosome pairs according to method 1, construct x _i chromosome pairs according to method i, and construct x _k chromosome pairs according to method k, An equilibrium mixed initial population of size M is obtained; where k ≥ 2,

Optionally, the scheduling optimization strategy module 503 constructs the improved fitness according to the user input parameters and the original fitness correction mean, and calculates the adaptive crossover probability Pc and adaptive crossover probability of each chromosome of the population in the evolution process according to the fitness. Mutation probability Pm, the specific process is as follows:

For the balanced mixed initialization population, the original fitness vector F _ini of the chromosome is calculated according to the deadline constraint, the mean value is corrected according to the original fitness, and the improved fitness vector F _imp is constructed;

Use the maximum improved fitness value to subtract the current improved fitness value, and divide by the difference between the maximum improved fitness value and the modified average value of the improved fitness to obtain the probability intermediate variable V _mi ;

When the improved fitness value is less than its revised mean, the probability correction variable takes the value of 1;

Multiply the relationship between the improved fitness value and its revised mean value with different parameters and mark it as Pc;

Take M target chromosome samples, and repeat the above process to obtain M Pc values;

Based on the same process, Pm can be obtained.

Further, the determination module 504 is specifically used for:

Perform steps S2, S3 and S4 on all chromosomes in the population to obtain the scheduling optimization strategy pool A and the scheduling optimization strategy pool B, and use the deadline constraint satisfaction rate as the evaluation criterion to compare the scheduling optimization obtained in steps S4 and S5. Strategy pool A and scheduling optimization strategy pool B;

determining secondary constraints according to the user input information; the user input information further includes secondary constraint information;

If the fitness of a scheduling optimization strategy is optimal and does not violate the secondary deadline constraint, or the degree of violation of the deadline constraint is the smallest relative to other scheduling optimization strategies, the scheduling optimization strategy is determined as the target scheduling optimization strategy, and given output the scheduling result.

Those skilled in the art can clearly understand that, for the convenience and simplicity of description, only the division of the above-mentioned functional units and modules is used as an example for illustration. In practical applications, the above-mentioned functions can be allocated to different functional units, Module completion, that is, dividing the internal structure of the device into different functional units or modules to complete all or part of the functions described above. Each functional unit and module in the embodiment may be integrated in one processing unit, or each unit may exist physically alone, or two or more units may be integrated into one unit, and the above-mentioned integrated units may adopt hardware. It can also be realized in the form of software functional units. In addition, the specific names of the functional units and modules are only for the convenience of distinguishing from each other, and are not used to limit the protection scope of the present application. For the specific working processes of the units and modules in the above-mentioned system, reference may be made to the corresponding processes in the foregoing method embodiments, which will not be repeated here.

Those of ordinary skill in the art can realize that the units and algorithm steps of each example described in conjunction with the embodiments disclosed herein can be implemented in electronic hardware, or a combination of computer software and electronic hardware. Whether these functions are performed in hardware or software depends on the specific application and design constraints of the technical solution. Skilled artisans may implement the described functionality using different methods for each particular application, but such implementations should not be considered beyond the scope of the present invention.

In the embodiments provided by the present invention, it should be understood that the disclosed apparatus and method may be implemented in other manners. For example, the system embodiments described above are only illustrative. For example, the division of the modules or units is only a logical function division. In actual implementation, there may be other division methods. For example, multiple units or components may be Incorporation may either be integrated into another system, or some features may be omitted, or not implemented. On the other hand, the shown or discussed mutual coupling or direct coupling or communication connection may be through some interfaces, indirect coupling or communication connection of devices or units, and may be in electrical, mechanical or other forms.

The units described as separate components may or may not be physically separated, and components displayed as units may or may not be physical units, that is, may be located in one place, or may be distributed to multiple network units. Some or all of the units may be selected according to actual needs to achieve the purpose of the solution in this embodiment.

In addition, each functional unit in each embodiment of the present invention may be integrated into one processing unit, or each unit may exist physically alone, or two or more units may be integrated into one unit. The above-mentioned integrated units may be implemented in the form of hardware, or may be implemented in the form of software functional units.

The integrated unit, if implemented in the form of a software functional unit and sold or used as an independent product, may be stored in a computer-readable storage medium. Based on such understanding, the technical solutions of the embodiments of the present invention are essentially or contribute to the prior art, or all or part of the technical solutions may be embodied in the form of software products, and the computer software products are stored in a storage The medium includes several instructions for causing a computer device (which may be a personal computer, a server, or a network device, etc.) or a processor (processor) to execute all or part of the steps of the methods described in the various embodiments of the present invention. The aforementioned storage medium includes: U disk, mobile hard disk, read-only memory (Read-Only Memory, ROM), random access memory (Random Access Memory, RAM), magnetic disk or optical disk and other media that can store program codes .

The above-mentioned embodiments are only used to illustrate the technical solutions of the present invention, but not to limit them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: it is still possible to implement the foregoing implementations. The technical solutions described in the examples are modified, or some technical features thereof are equivalently replaced; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the spirit and scope of the technical solutions of the embodiments of the present invention, and should be included in the within the protection scope of the present invention.

Claims (3)

1. a workflow scheduling evolutionary optimization method, is characterized in that, comprises: Step S1, according to the user input parameters and workflow data, select chromosomes in the genetic algorithm population as the scheduling strategy information carrier, and design the information encoding structure of the multiple chromosome pair W in combination with the population size M, the computing resource size N and the workflow data; the user Input parameters include deadline constraint parameters; Step S2, according to any multiple chromosome pair constructed by the information coding structure, cycle the construction process of a single multiple chromosome pair according to the construction method to form a balanced mixed initialization population with a scale of M; Step S3, initialize the population according to the balanced mixture, construct an evolution process, adjust the evolution direction according to the user input parameters, construct an improved fitness according to the user input parameters and the original fitness correction mean, and calculate according to the fitness During the evolution process, the adaptive crossover probability Pc and the adaptive mutation probability Pm of each chromosome of the population are genetically manipulated for each chromosome and the resulting scheduling strategy is stored in the scheduling optimization strategy pool A; Wherein, the genetic manipulation refers to the operations of crossover, mutation and selection in the evolutionary process; Step S4, take the ω chromosomes in the optimal strategy pool A as the input of the re-evolution operation under the deadline constraint, and add M-ω randomly generated chromosomes to obtain the re-evolved population as the input population of step S3 and iterate according to step S3. Perform re-evolution, and the obtained scheduling strategies are stored in the scheduling optimization strategy pool B; The conditions for stopping the iteration are: the number of iterations reaches a preset number of times; Step S5, match the deadline constraints, and compare the deadline constraint satisfaction rate and execution cost, evaluate the algorithm execution efficiency, and determine each scheduling strategy in the scheduling optimization strategy pool A and the scheduling optimization strategy pool B to determine the preferred scheduling strategy. ; Wherein, the information coding structure of the multiple chromosome pair W in step S1 includes a total of 2 chromosomes, namely Multiple chromosome pair W={chromesome1,chromesome2} chromesome1=sequence of{Pc,Pm,gen ₀ ,gen ₁ ,…,gen _k ,…,gen _L-1 } chromesome2={tof ₀ ,tof ₁ ,…,tof _i ,…,tof _N-1 } Assuming that on the ith virtual machine, the size of the execution sequence is g, then tof _i can be expressed as:

Among them, Pc is the adaptive crossover probability of the chromosome; Pm is the adaptive mutation probability of the chromosome; gen _k is the gene at the k position of the chromosome, 0≤k<L; vm _i is the ith virtual machine in the computing resources, 0 ≤i<N; tof _i is the execution sequence of computing tasks allocated to computing resource vm _i ; Among them, L is an integer greater than 0, N is the number of virtual machines,

is the g-1th computing task of computing resource vm _i ; Wherein, according to any multiple chromosome pair constructed by the information coding structure, the construction process of a single multiple chromosome pair is cycled according to the construction method to form a balanced mixed initialization population with a scale of M. The specific process is as follows: According to the chromosome pair coding structure obtained in step S1, assuming that k methods are used to construct the initialization population, then construct x ₁ chromosome pairs according to method 1, construct x _i chromosome pairs according to method i, and construct x _k chromosome pairs according to method k, An equilibrium mixed initial population of size M is obtained; where k ≥ 2,

The improved fitness is constructed according to the user input parameters and the original fitness correction mean, and the adaptive crossover probability Pc and the adaptive mutation probability Pm of each chromosome of the population in the evolution process are calculated according to the fitness. The specific process is as follows: For the balanced mixed initialization population, the original fitness vector F _ini of the chromosome is calculated according to the deadline constraint, the mean value is corrected according to the original fitness, and the improved fitness vector F _imp is constructed; Use the maximum improved fitness value to subtract the current improved fitness value, and divide by the difference between the maximum improved fitness value and the modified average value of the improved fitness to obtain the probability intermediate variable V _mi ; When the improved fitness value is less than its revised mean, the probability correction variable takes the value of 1; Multiply the relationship between the improved fitness value and its revised mean value with different parameters and mark it as Pc; Take M target chromosome samples, and repeat the above process to obtain M Pc values; Based on the same process, Pm can be obtained; Wherein, the calculation formula for calculating the adaptive crossover probability Pc and the adaptive mutation probability Pm of each chromosome of the population in the evolution process according to the fitness includes:

Among them, P _c (i) represents the crossover probability of the ith chromosome pair in the contemporary population, P _m (i) represents the mutation probability of the ith chromosome pair in the contemporary population, f _max represents the maximum improved fitness value, f(i ) represents the current improved fitness of the i-th chromosome, f _cavg represents the revised mean of the fitness of the current population, k ₁ and k ₃ represent crossover parameters, and k ₂ and k ₄ represent mutation parameters; Wherein, in step S5, it is determined that each scheduling strategy of the scheduling optimization strategy pool A and the scheduling optimization strategy pool B is determined, and the process of determining the preferred scheduling strategy is as follows: Perform steps S2, S3 and S4 on all chromosomes in the population to obtain the scheduling optimization strategy pool A and the scheduling optimization strategy pool B, and use the deadline constraint satisfaction rate as the evaluation criterion to compare the scheduling optimization obtained in steps S4 and S5. Strategy pool A and scheduling optimization strategy pool B; determining secondary constraints according to the user input information; the user input information further includes secondary constraint information; If the fitness of a scheduling optimization strategy is optimal and does not violate the secondary deadline constraint, or the degree of violation of the deadline constraint is the smallest relative to other scheduling optimization strategies, the scheduling optimization strategy is determined as the target scheduling optimization strategy, and given output the scheduling result. 2. A terminal device, comprising a memory and a processor, wherein a computer program that can be run on the processor is stored in the memory, and the processor implements the following steps when executing the computer program: Step S1, according to the user input parameters and workflow data, select chromosomes in the genetic algorithm population as the scheduling strategy information carrier, and design the information encoding structure of the multiple chromosome pair W in combination with the population size M, the computing resource size N and the workflow data; the user Input parameters include deadline constraint parameters; Step S2, according to any multiple chromosome pair constructed by the information coding structure, cycle the construction process of a single multiple chromosome pair according to the construction method to form a balanced mixed initialization population with a scale of M; Step S3, initialize the population according to the balanced mixture, construct an evolution process, adjust the evolution direction according to the user input parameters, construct an improved fitness according to the user input parameters and the original fitness correction mean, and calculate according to the fitness During the evolution process, the adaptive crossover probability Pc and the adaptive mutation probability Pm of each chromosome of the population are genetically manipulated for each chromosome and the resulting scheduling strategy is stored in the scheduling optimization strategy pool A; Wherein, the genetic manipulation refers to the operations of crossover, mutation and selection in the evolutionary process; Step S4, take the ω chromosomes in the optimal strategy pool A as the input of the re-evolution operation under the deadline constraint, and add M-ω randomly generated chromosomes to obtain the re-evolved population as the input population of step S3 and iterate according to step S3. Perform re-evolution, and the obtained scheduling strategies are stored in the scheduling optimization strategy pool B; The conditions for stopping the iteration are: the number of iterations reaches a preset number of times; Step S5, match the deadline constraints, and compare the deadline constraint satisfaction rate and execution cost, evaluate the algorithm execution efficiency, and determine each scheduling strategy in the scheduling optimization strategy pool A and the scheduling optimization strategy pool B to determine the preferred scheduling strategy. ; Wherein, the information coding structure of the multiple chromosome pair W in step S1 includes a total of 2 chromosomes, namely Multiple chromosome pair W={chromesome1,chromesome2} chromesome1=sequence of{Pc,Pm,gen ₀ ,gen ₁ ,…,gen _k ,…,gen _L-1 } chromesome2={tof ₀ ,tof ₁ ,…,tof _i ,…,tof _N-1 } Assuming that on the ith virtual machine, the size of the execution sequence is g, then tof _i can be expressed as:

Among them, Pc is the adaptive crossover probability of the chromosome; Pm is the adaptive mutation probability of the chromosome; gen _k is the gene at the k position of the chromosome, 0≤k<L; vm _i is the ith virtual machine in the computing resources, 0 ≤i<N; tofi is the execution sequence of computing tasks allocated to the computing resource vmi; Among them, L is an integer greater than 0, N is the number of virtual machines,

is the g-1th computing task of computing resource vm _i ; Wherein, according to any multiple chromosome pair constructed by the information coding structure, the construction process of a single multiple chromosome pair is cycled according to the construction method to form a balanced mixed initialization population with a scale of M. The specific process is as follows: According to the chromosome pair coding structure obtained in step S1, assuming that k methods are used to construct the initialization population, then construct x ₁ chromosome pairs according to method 1, construct x _i chromosome pairs according to method i, and construct x _k chromosome pairs according to method k, An equilibrium mixed initial population of size M is obtained; where k ≥ 2,

The improved fitness is constructed according to the user input parameters and the original fitness correction mean, and the adaptive crossover probability Pc and the adaptive mutation probability Pm of each chromosome of the population in the evolution process are calculated according to the fitness. The specific process is as follows: For the balanced mixed initialization population, the original fitness vector F _ini of the chromosome is calculated according to the deadline constraint, the mean value is corrected according to the original fitness, and the improved fitness vector F _imp is constructed; Use the maximum improved fitness value to subtract the current improved fitness value, and divide by the difference between the maximum improved fitness value and the modified average value of the improved fitness to obtain the probability intermediate variable V _mi ; When the improved fitness value is less than its revised mean, the probability correction variable takes the value of 1; Multiply the relationship between the improved fitness value and its revised mean value with different parameters and mark it as Pc; Take M target chromosome samples, and repeat the above process to obtain M Pc values; Based on the same process, Pm can be obtained; Wherein, the calculation formula for calculating the adaptive crossover probability Pc and the adaptive mutation probability Pm of each chromosome of the population in the evolution process according to the fitness includes:

Among them, P _c (i) represents the crossover probability of the ith chromosome pair in the contemporary population, P _m (i) represents the mutation probability of the ith chromosome pair in the contemporary population, f _max represents the maximum improved fitness value, f(i ) represents the current improved fitness of the i-th chromosome, f _cavg represents the revised mean of the fitness of the current population, k ₁ and k ₃ represent crossover parameters, and k ₂ and k ₄ represent mutation parameters; Wherein, in step S5, it is determined that each scheduling strategy of the scheduling optimization strategy pool A and the scheduling optimization strategy pool B is determined, and the process of determining the preferred scheduling strategy is as follows: Perform steps S2, S3 and S4 on all chromosomes in the population to obtain the scheduling optimization strategy pool A and the scheduling optimization strategy pool B, and use the deadline constraint satisfaction rate as the evaluation criterion to compare the scheduling optimization obtained in steps S4 and S5. Strategy pool A and scheduling optimization strategy pool B; determining secondary constraints according to the user input information; the user input information further includes secondary constraint information; If the fitness of a scheduling optimization strategy is optimal and does not violate the secondary deadline constraint, or the degree of violation of the deadline constraint is the smallest relative to other scheduling optimization strategies, the scheduling optimization strategy is determined as the target scheduling optimization strategy, and given output the scheduling result. 3. A computer-readable storage medium storing a computer program, characterized in that, when the computer program is executed by a processor, the steps of the method according to claim 1 are implemented.

Images