WORKFLOW SCHEDULING METHOD AND SYSTEM BASED ON MULTI-TARGET PARTICLE SWARM ALGORITHM, AND STORAGE MEDIUM

Abstract

The present disclosure discloses a workflow scheduling method and system based on a multi-target particle swarm algorithm, and a storage medium. The method comprises the following steps that first, the difference between the frequency reduction characteristic and the execution time of each server in a cluster is considered; a multi-target comprehensive evaluation model covering workflow execution overhead, execution time and cluster load balance is constructed on the basis of a traditional model; second, a multi-target particle swarm algorithm is provided for workflow scheduling, and an efficient solving method is provided. The method alleviates the defects of premature convergence and low species diversity of the particle swarm algorithm, reduces the execution overhead and execution time of the workflow on the cluster server, and better balances the load of the cluster server.

Claims

1. A workflow scheduling method based on a multi-target particle swarm algorithm, comprising the following steps: 1) constructing a workflow execution overhead evaluation equation; 2) constructing a workflow execution time evaluation equation; 3) constructing a cluster load evaluation equation; 4) constructing a comprehensive evaluation equation containing the indexes in the above three evaluation equations, and scheduling the workflow using the particle swarm optimization algorithm for the workflow execution overhead evaluation equation, the workflow execution time evaluation equation, the cluster load evaluation equation and the comprehensive evaluation equation, wherein the particle swarm optimization algorithm divides the particle swarm into four parts evenly, it is assumed that each part of particles is iterated for C times, the first % iterations of each part of particles search for the optimal solutions of the above four evaluation equations, respectively, the last C*(1−a%) iterations search for the optimal solution of the comprehensive evaluation equation, and the value range of coefficient a is [0,100].

2. The workflow scheduling method based on the multi-target particle swarm algorithm according to claim 1, wherein: in step 1), the workflow execution overhead evaluation equation includes the workflow execution overhead and the data transmission cost of a pre-task and a post-task, and the formula is: $\begin{array}{cc}\mathrm{Cos}t=\underset{\text{?}}{\overset{M}{.Math.}}\underset{\text{?}}{\overset{N}{.Math.}}{k}_{\text{?}}*{\mathrm{ET}}_{\text{?}}*{\mathrm{Price}}_{\text{?}}+\underset{\text{?}}{\overset{N}{.Math.}}\underset{\text{?}}{\overset{\mathrm{PR}\text{?}}{.Math.}}{\mathrm{TT}}_{\text{?}}*{\mathrm{Price}}_{\text{?}}& \left(4\right)\end{array}$ $\begin{array}{cc}{k}_{t_i{\mathrm{vm}}_j}=\{\begin{array}{cc}1& t_i\mathrm{is}\mathrm{executed}\mathrm{on}{\mathrm{vm}}_j\\ 0& t_i\mathrm{is}\mathrm{not}\mathrm{executed}\mathrm{on}{\mathrm{vm}}_j\end{array}& \left(5\right)\end{array}$ $\begin{array}{cc}\mathrm{Cos}t\le \mathrm{revenue}& \left(6\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ where the number of tasks in the workflow is N, the number of virtual machines is M, is a two-dimensional variable, represents the execution time of the task in the virtual machine , , represents the execution cost coefficient of a task in a virtual machine , which is used to represent the overhead per unit time of a server executing a task. represents the time it takes for a task to complete data transmission to a task , represents the data transmission cost of two tasks in a cloud server network, which is used to represent the network overhead per unit time of data transmission, represents all the pre-tasks of the task , and the total overhead Cost of the workflow does not exceed the overhead limit revenue of a user.

3. The workflow scheduling method based on the multi-target particle swarm algorithm according to claim 1, wherein: in step 2), the completion time of the task is represented by , and the execution time of the workflow is represented by the maximum completion time of its subtasks , in which the target equation of the completion time of the task includes the execution time and the waiting time of the task , the waiting time of the task includes the maximum execution time of all pre-tasks and the data time transmitted from all pre-tasks to the post-tasks, and the formula is as follows: $\begin{array}{cc}{\mathrm{WT}}_{\text{?}}=\underset{\text{?}}{\overset{\mathrm{PR}\text{?}}{.Math.}}{\mathrm{TT}}_{\text{?}}+\underset{\text{?}}{\max }\left\{{\mathrm{ET}}_{\text{?}}\right\}& \left(7\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ where represents the waiting execution time of the task , represents all the pre-tasks of the task , represents the time it takes for the task to complete data transmission to the task , and represents the execution time of on ; represents the execution time of all pre-tasks of the task on (this is a set), and the maximum value is selected from the set; the completion time of the task is by , and the formula is as follows: $\begin{array}{cc}\mathrm{Makespan}\text{?}=\mathrm{WT}\text{?}+\mathrm{ET}\text{?}& \left(8\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ where represents the waiting execution time of the task , and represents the execution time of on ; the execution time evaluation equation of the workflow is as follows: $\begin{array}{cc}\mathrm{Makespan}=\stackrel{\text{?}}{\underset{\text{?}}{\max }}\left\{{\mathrm{Makespan}}_{\text{?}}\right\}& \left(9\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ where the number of the workflow tasks is N, represents the maximum completion time of the task .

4. The workflow scheduling method based on the multi-target particle swarm algorithm according to claim 1, wherein: in step 3), the load balance evaluation equation is established according to the difference of the execution time of the server, that is, it is expressed by the variance of the task execution time of a single virtual machine and the average task execution time of a virtual machine cluster, and the smaller variance indicates that the server load is more balanced, in which the total time equation of the execution task of a single virtual machine is as follows: $\begin{array}{cc}{\mathrm{ET}}_{\text{?}}=\underset{j=1}{\overset{N}{.Math.}}{k}_{\text{?}}*{\mathrm{ET}}_{\text{?}}& \left(10\right)\end{array}$ $\begin{array}{cc}{k}_{t_2{v}_j}=\{\begin{array}{cc}1& t_j\mathrm{is}\mathrm{executed}\mathrm{on}{v}_i\\ 0& t_j\mathrm{is}\mathrm{not}\mathrm{executed}\mathrm{on}{v}_i\end{array}& \left(11\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ where the total number of tasks in the workflow is N, is a two-dimensional variable, and represents the execution time of on , the average task execution time of the virtual machine is: $\begin{array}{cc}{\mathrm{AVE}}_{\text{?}}=\frac{\underset{\text{?}}{\overset{M}{.Math.}}\underset{\text{?}}{\overset{N}{.Math.}}{k}_{\text{?}}*{\mathrm{ET}}_{\text{?}}}{M}=\frac{\underset{i}{\overset{M}{.Math.}}{\mathrm{ET}}_{\text{?}}}{M}& \left(12\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ in the above formula, the number of tasks in the workflow is N, the number of virtual machines is M, represents the execution time of on , , is a two-dimensional variable, represents the total time of the task execution in the virtual machine , the maximum load target equation of the server cluster is expressed by the variance of the execution time of each virtual machine workflow and the average execution time of the total virtual machine workflow, and the equation expression is as follows: $\begin{array}{cc}\mathrm{LD}=\frac{\sqrt{\underset{\text{?}}{\overset{M}{.Math.}}{\left({\mathrm{ET}}_{\text{?}}-{\mathrm{AVE}}_{\text{?}}\right)}^2}}{M}& \left(13\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ where the number of virtual machines is M, represents the total time of the task execution of the virtual machine , represents the average time of the task execution of the virtual machine, LD represents the workload of the virtual machine cluster, and the smaller LD indicates that the load of the virtual machine is more balanced.

5. The workflow scheduling method based on the multi-target particle swarm algorithm according to claim 1, wherein: in step 4), the workflow comprehensive evaluation equation consists of the workflow execution overhead evaluation equation, the workflow execution time evaluation equation and the cluster load evaluation equation, and the equation expressions are as follows:
Fitness=x.sub.1*Cost+x.sub.2*Makespan+x.sub.3*LD  (14)
Cost≥revenue (15)
Makespan≥D  (16) where x.sub.1, x.sub.2, and x.sub.3 are the overhead weight coefficient, the time weight coefficient and the cluster load weight coefficient, respectively, and the weight coefficient varies with the characteristics of the task; Cost represents the workflow execution overhead; D represents the deadline of the workflow; Makespan represents the workflow execution time, and LD represents the workload of the virtual machine cluster.

6. The workflow scheduling method based on the multi-target particle swarm algorithm according to claim 1, wherein: in step 4), the specific execution flow of the particle swarm optimization scheduling algorithm includes the following steps: step 1), the particle swarm initializing the total iteration number C, the inertia factor ω, the acceleration constant and the acceleration constant , the random number and the random number , t=1, the particle grouping coefficient k=0, i=1, initializing the number n of the particle swarms, randomly generating n particles, representing the individual extremum of particles using the execution overhead evaluation equation and the global extremum of particles using the execution overhead evaluation equation by the execution overhead evaluation equation Cost, representing the individual extremum of particles using the execution time evaluation equation and the global extremum of particles using the execution time evaluation equation by the execution time evaluation equation Makespan, representing the individual extremum of particles using the cluster load evaluation equation and the global extremum of particles using the cluster load evaluation equation by the cluster load evaluation equation LD, representing the individual extremum of particles using the workflow comprehensive evaluation equation and the global extremum of particles using the workflow comprehensive evaluation equation by the workflow comprehensive evaluation equation Fitness, and each dimension of particles represents each workflow; step 2), judging whether the iteration number is less than or equal to C*a%, otherwise, jumping to step 3; starting to update the speed v and the position x of n particle swarms using For loop i=1:n , and in order to reduce the negative effect of the complexity increase caused by the multi-target particle swarm, using an alternating update method: when i=4k+1: the particle uses the following evaluation equation: $\begin{array}{cc}\mathrm{Cos}t=\underset{\text{?}}{\overset{M}{.Math.}}\underset{\text{?}}{\overset{N}{.Math.}}{k}_{\text{?}}*{\mathrm{ET}}_{\text{?}}*{\mathrm{Price}}_{\text{?}}+\underset{\text{?}}{\overset{N}{.Math.}}\underset{\text{?}}{\overset{\mathrm{PR}\text{?}}{.Math.}}{\mathrm{TT}}_{\text{?}}*{\mathrm{Price}}_{\text{?}}& \left(21\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ where the number of tasks in the workflow is N, the number of virtual machines is M, is a two-dimensional variable, represents the execution time of the task in the virtual machine , represents the execution cost coefficient of a task in a virtual machine , which is used to represent the overhead per unit time of a server executing a task, represents the time it takes for a task to complete data transmission to a task , represents the data transmission cost of two tasks in a cloud server network, which is used to represent the network overhead per unit time of data transmission, and represents all the pre-tasks of the task the following particle swarm formula is used to update the speed v and the position x: $\begin{array}{cc}{v}_{i,d}^{t-1}=\omega \text{?}v\text{?}+r_1{c}_1\left(p\text{?}-x\text{?}\right)+r_2{c}_2\left(g\text{?}-x\text{?}\right)& \left(22\right)\end{array}$ $x_{i,d}^{t+1}=x_{i,d}^t+v_{i,d}^{t+1}$ $\text{?}\text{indicates text missing or illegible when filed}$ the formula of the probability update speed v and the position x is as follows: $\begin{array}{cc}p\left(x^{\text{?}}.fwdarw.x^{\text{?}},v^{\text{?}}.fwdarw.v^{\text{?}+1}\right)=\{\begin{array}{cc}1& \mathrm{Cos}t\left(x^{\text{?}}\right)<\mathrm{Cos}t\left(x^{\text{?}}\right)\\ e\frac{\text{?}}{T}& \mathrm{Cos}t\left(x^{\text{?}}\right)\ge \mathrm{Cos}t\left(x^{\text{?}}\right)\end{array}& \left(23\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ if <, is updated, is the individual information recording the found optimal particle; if a better is found, the newly found particle information replaces the previously stored old particle information; if in the search process, the particle finds <, <, <, <, the corresponding is updated: when i=4k+2: the particle i uses the following evaluation function: $\begin{array}{cc}\mathrm{Makespan}=\stackrel{N}{\underset{i=1}{\max }}\left\{\mathrm{Makespan}\text{?}\right\}& \left(24\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ the following particle swarm formula is used to update the speed v and the position x: $\begin{array}{cc}v\text{?}=\omega \text{?}v\text{?}+r_1{c}_1\left(p\text{?}-x\text{?}\right)+r_2{c}_2\left(g\text{?}-x\text{?}\right)& \left(25\right)\end{array}$ $x_{i,d}^{t+1}=x_{i,d}^t+v_{i,d}^{t-1}$ $\text{?}\text{indicates text missing or illegible when filed}$ the formula of the probability update speed v and the position x is as follows: $\begin{array}{cc}p\left(x^{\text{?}}.fwdarw.x^{\text{?}},v^{\text{?}}.fwdarw.v^{\text{?}+1}\right)=\{\begin{array}{cc}1& \mathrm{Makespan}\left(x^{\text{?}}\right)<\mathrm{Makespan}\left(x^{\text{?}}\right)\\ e\frac{\text{?}}{T}& \mathrm{Makespan}\left(x^{\text{?}}\right)\ge \mathrm{Makespan}\left(x^{\text{?}}\right)\end{array}& \left(26\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ if <, is updated, if the particle finds <, <, <, <, the corresponding is updated; when i=4k+3: the particle i uses the following evaluation function: $\begin{array}{cc}\mathrm{LD}=\frac{\sqrt{\underset{\text{?}}{\overset{M}{.Math.}}{\left({\mathrm{ET}}_{\text{?}}-{\mathrm{AVE}}_{\text{?}}\right)}^2}}{M}& \left(27\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ the following particle swarm formula is used to update the speed v and the position x: $\begin{array}{cc}v\text{?}=\omega v\text{?}+r_1{c}_1\left(p\text{?}-x\text{?}\right)+r_2{c}_2\left(g\text{?}-x\text{?}\right)& \left(28\right)\end{array}$ $x_{i,d}^{t+1}=x_{i,d}^t+v_{i,d}^{t-1}$ $\text{?}\text{indicates text missing or illegible when filed}$ the formula of the probability update speed v and the position x is as follows: $\begin{array}{cc}p\left(x^{\text{?}}.fwdarw.x^{\text{?}},v^{\text{?}}.fwdarw.v^{\text{?}+1}\right)=\{\begin{array}{cc}1& \mathrm{LD}\left(x^{\text{?}}\right)<\mathrm{LD}\left(x^{\text{?}}\right)\\ e\frac{\text{?}}{T}& \mathrm{LD}\left(x^{\text{?}}\right)\ge \mathrm{LD}\left(x^{\text{?}}\right)\end{array}& \left(29\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ if <, is updated, if the particle finds <, <, <, <, the corresponding is updated; when i=4k+4: the particle i uses the following comprehensive evaluation function:
Fitness=x.sub.1*Cost+x.sub.2*Makespan+x.sub.3*LD  (30) the following particle swarm formula is used to update the speed v and the position x: $\begin{array}{cc}v\text{?}=\omega \text{?}v\text{?}+r_1{c}_1\left(p\text{?}-x\text{?}\right)+r_2{c}_2\left(g\text{?}-x\text{?}\right)& \left(31\right)\end{array}$ $x_{i,d}^{t+1}=x_{i,d}^t+v_{i,d}^{t-1}$ $\text{?}\text{indicates text missing or illegible when filed}$ the formula of the probability update speed v and the position x is as follows: $\begin{array}{cc}p\left(x^{\text{?}}.fwdarw.x^{\text{?}},v^{\text{?}}.fwdarw.v^{\text{?}+1}\right)=\{\begin{array}{cc}1& \mathrm{Fitness}\left(x^{\text{?}}\right)<\mathrm{Fitness}\left(x^{\text{?}}\right)\\ e\frac{\text{?}}{T}& \mathrm{Fitness}\left(x^{\text{?}}\right)\ge \mathrm{Fitness}\left(x^{\text{?}}\right)\end{array}& \left(32\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ if <, is updated, if the particle finds < <, <, <, the corresponding is updated; after the above execution process, updating k: k=k+1, updating c: c=c+1, and jumping back to step 2); step 3) judging whether the iteration number is less than or equal to D, otherwise, jumping to step 4); starting to update the speed v and the position x of n particles using For loop: n particles all use the following comprehensive evaluation function:
Fitness=x.sub.1*Cost+x.sub.2*Makespan+x.sub.3*LD  (33) the following particle swarm formula is used to update the speed v and the position x: $\begin{array}{cc}v\text{?}=\omega \text{?}v\text{?}+r_1{c}_1\left(p\text{?}-x\text{?}\right)+r_2{c}_2\left(g\text{?}-x\text{?}\right)& \left(34\right)\end{array}$ $x\text{?}=x_{i,d}^t+v\text{?}$ $\text{?}\text{indicates text missing or illegible when filed}$ the judging formula of updating the speed v and the position x is as follows: $\begin{array}{cc}p\left(x^{\text{?}}.fwdarw.x^{\text{?}},v^{\text{?}}.fwdarw.v^{\text{?}+1}\right)=\{\begin{array}{cc}1& \mathrm{Fitness}\left(x^{\text{?}}\right)<\mathrm{Fitness}\left(x^{\text{?}}\right)\\ e\frac{\text{?}}{T}& \mathrm{Fitness}\left(x^{\text{?}}\right)\ge \mathrm{Fitness}\left(x^{\text{?}}\right)\end{array}& \left(35\right)\end{array}$ $\text{?}\text{indicates text missing or illegible when filed}$ if <, is updated, if the corresponding is updated; step 4) outputting the final result, and scheduling the workflow to the corresponding \initial machine using a scheduler; checking whether there is a new workflow coming, if so, starting a new cycle, if not, ending the process.

7. A workflow scheduling system based on a multi-target particle swarm algorithm, comprising the following program modules: an overhead evaluating module, which is configured to construct a workflow execution overhead evaluation equation; an execution time evaluating module, which is configured to construct a workflow execution time evaluation equation; a cluster load evaluating module, which is configured to construct a cluster load evaluation equation: a solving module, which is configured to construct a comprehensive evaluation equation containing the indexes in the above three evaluation equations, and schedule the workflow using the particle swarm optimization algorithm for the workflow execution overhead evaluation equation, the workflow execution time evaluation equation, the cluster load evaluation equation and the comprehensive evaluation equation, wherein the particle swarm optimization algorithm (PSO) divides the particle swarm into four parts evenly, it is assumed that each part of particles is iterated for C times, the first C*a% iterations of each part of particles search for the optimal solutions of the above four evaluation equations, respectively, and the last C*(1−a%) iterations search for the optimal solution of the comprehensive evaluation equation.

8. A computer readable storage medium, which is used to store the workflow scheduling method based on the multi-target particle swarm algorithm according to claim 1.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0023] FIG. 1 is an exemplary workflow model of the present disclosure.

[0024] FIG. 2 is a flow chart of the operation of a particle swarm optimization scheduling algorithm according to the present disclosure.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0025] The present disclosure will be further described with reference to the accompanying drawings hereinafter. The following embodiments are only used to illustrate the technical scheme of the present disclosure more clearly, rather than limit the scope of protection of the present disclosure.

Embodiment 1

[0026] The workflow scheduling method based on the multi-target particle swarm algorithm according to the present disclosure comprises the following steps:

[0027] 1) constructing a workflow execution overhead evaluation equation;

[0028] 2) constructing a workflow execution time evaluation equation;

[0029] 3) constructing a cluster load evaluation equation;

[0030] 4) constructing a comprehensive evaluation equation containing the indexes in the above three evaluation equations, and scheduling the workflow using the particle swarm optimization algorithm for the workflow execution overhead evaluation equation, the workflow execution time evaluation equation, the cluster load evaluation equation and the comprehensive evaluation equation, wherein the particle swarm optimization algorithm (PSO) divides the particle swarm into four parts evenly, it is assumed that each part of particles is iterated for C times, the first C*a% iterations of each part of particles search for the optimal solutions of the above four evaluation equations, respectively, and the last C*(1−a%) iterations search for the optimal solution of the comprehensive evaluation equation. In the process of searching for the optimal solution, the annealing probability formula is used to update the state information of each particle.

[0031] The optimized target function is constructed.

[0032] As shown in the workflow simulation diagram in FIG. 1, each ball t represents a task, and the workflow is a combination of several tasks t.sub.1, t.sub.2 . . . t.sub.n. For the workflow, most tasks are interdependent, and the workflow is represented by a weighted directed acyclic graph G=(T, E), where T={t.sub.1, t.sub.2 . . . t.sub.N} represents N tasks of the workflow, and E={e.sub.ij|i,j=1, . . . N} represents the dependency of the task. For example, e.sub.12 indicates that the task t.sub.1 completes execution, and the task t.sub.2 can only be executed after the data is transmitted to the task t.sub.2. Assuming that virtual machines are represented by vm.sub.i, in which , i=1,2 . . . M, where M is the number of virtual machines.

[0033] The formula of the execution time of each task is as follows:

[00001]$\begin{array}{cc}E\text{?}=\frac{\text{?}}{\text{?}}& \left(1\right)\end{array}$$\begin{array}{cc}E\text{?}\le \text{?}& \left(2\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0034] where L.sub.i, represents the instruction length of the task t.sub.i, C.sub.vj represents the execution capability (MIPS) of the virtual machine vm.sub.i, RP.sub.vm, represents the attenuation coefficient of the virtual machine vm.sub.i (the server cannot work at the maximum workload for a long time), ET.sub.i,vm, represents the execution time of the task t.sub.i in the virtual machine vm.sub.i, and the execution time ET.sub.t.sub.i of each task cannot exceed the deadline deadline.sub.t .sub.i of the respective task t.sub.i.

[0035] The formula of data transmission time for a pre-task and a post-task is as follows:

[00002]$\begin{array}{cc}\mathrm{TT}\text{?}=\{\begin{array}{cc}\frac{\mathrm{TR}\text{?}}{\mathrm{bw}}& i\ne j\\ 0& i=j\end{array}& \left(3\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0036] where bw represents the network bandwidth of the cloud server, TR.sub.c.sub.n represents the size of data transmitted from the task to the task , and represents the time it takes for the task to complete data transmission to the task .

[0037] In step 1), the workflow execution overhead evaluation equation includes the workflow execution overhead and the data transmission cost of a pre-task and a post-task, and the formula is:

[00003]$\begin{array}{cc}\mathrm{Cos}t=\stackrel{M}{\underset{\text{?}}{.Math.}}\underset{\text{?}}{\overset{N}{.Math.}}k\text{?}\star \mathrm{ET}\text{?}\star \mathrm{Price}\text{?}+\stackrel{N}{\underset{j=1}{.Math.}}\underset{i=1}{\overset{\mathrm{PR}\text{?}}{.Math.}}\mathrm{TT}\text{?}\star {\mathrm{Price}}_{\mathrm{IE}}& \left(4\right)\end{array}$$\begin{array}{cc}{k}_{t_l{\mathrm{vm}}_j}=\{\begin{array}{cc}1& t_i\mathrm{is}\mathrm{executed}\mathrm{on}{\mathrm{vm}}_j\\ 0& t_i\mathrm{is}\mathrm{not}\mathrm{executed}\mathrm{on}{\mathrm{vm}}_j\end{array}& \left(5\right)\end{array}$$\begin{array}{cc}\mathrm{Cos}t\le \mathrm{revenue}& \left(6\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0038] where the number of tasks in the workflow is N, the number of virtual machines is M, is a two-dimensional variable, represents the execution time of the task in the virtual machine , represents the execution cost coefficient of a task in a virtual machine , which is used to represent the overhead per unit time of a server executing a task, represents the time it takes for a task to complete data transmission to a task , represents the data transmission cost of two tasks in a cloud server network, which is used to represent the network overhead per unit time of data transmission, represents all the pre-tasks of the task , and the total overhead Cost of the workflow does not exceed the overhead limit revenue of a user.

[0039] In step 2), the completion time of the task is represented by , and the execution time of the workflow is represented by the maximum completion time of its subtasks , in which the target equation of the completion time of the task includes the execution time and the waiting time of the task , the waiting time of the task includes the maximum execution time of all pre-tasks and the data time transmitted from all pre-tasks to the post-tasks, and the formula is as follows:

[00004]$\begin{array}{cc}\mathrm{WT}\text{?}=\underset{\text{?}}{\overset{\mathrm{PR}\text{?}}{.Math.}}\mathrm{TT}\text{?}+\underset{\text{?}}{\max }\left\{{\mathrm{ET}}_{\mathrm{kvm}}\text{?}\right\}& \left(7\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0040] where represents the waiting execution time of the task , represents all the pre-tasks of the task , represents the time it takes for the task to complete data transmission to the task , and represents the execution time of on ; represents the execution time of all pre-tasks of the task on (this is a set), and the maximum value is selected from the set.

[0041] The completion time of the task is by , and the formula is as follows:

[00005]$\begin{array}{cc}\mathrm{Makespan}\text{?}=\mathrm{WT}\text{?}+\mathrm{ET}\text{?}& \left(8\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0042] where represents the waiting execution time of the task , and represents the execution time of on .

[0043] The execution time evaluation equation of the workflow is as follows:

[00006]$\begin{array}{cc}\mathrm{Makespan}=\stackrel{N}{\underset{i=1}{\max }}\left\{\mathrm{Makespan}\text{?}\right\}& \left(9\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0044] where the number of the workflow tasks is N, represents the maximum completion time of the task .

[0045] In step 3), the load balance evaluation equation is established according to the difference of the execution time of the server, that is, it is expressed by the variance of the task execution time of a single virtual machine and the average task execution time of a virtual machine cluster, and the smaller variance indicates that the server load is more balanced, in which the total time equation of the execution task of a single virtual machine is as follows:

[00007]$\begin{array}{cc}\mathrm{ET}\text{?}=\underset{j=1}{\overset{N}{.Math.}}k\text{?}\star \mathrm{ET}\text{?}& \left(10\right)\end{array}$$\begin{array}{cc}k\text{?}=\{\begin{array}{cc}1& t_j\mathrm{is}\mathrm{executed}\mathrm{on}{v}_i\\ 0& t_j\mathrm{is}\mathrm{not}\mathrm{executed}\mathrm{on}{v}_i\end{array}& \left(11\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0046] where the total number of tasks in the workflow is N, is a two-dimensional variable, and represents the execution time of on .

[0047] The average task execution time of the virtual machine is:

[00008]$\begin{array}{cc}{\mathrm{AVE}}_{\mathrm{ET}}=\frac{\stackrel{M}{\underset{\text{?}}{.Math.}}\underset{\text{?}}{\overset{N}{.Math.}}k\text{?}\star \mathrm{ET}\text{?}}{M}=\frac{\underset{i}{\overset{M}{.Math.}}\mathrm{ET}\text{?}}{M}& \left(12\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0048] in the above formula, the number of tasks in the workflow is N, the number of virtual machines is M, represents the execution time of on , is a two-dimensional variable represents the total time of the task execution in the virtual machine .

[0049] The maximum load target equation of the server cluster is expressed by the variance of the execution time of each virtual machine workflow and the average execution time of the total virtual machine workflow, and the equation expression is as follows:

[00009]$\begin{array}{cc}\mathrm{LD}=\frac{\sqrt{\underset{i=1}{\overset{M}{.Math.}}{\left(\mathrm{ET}\text{?}-{\mathrm{AVE}}_{\mathrm{ET}}\right)}^2}}{M}& \left(13\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0050] where the number of virtual machines is M, represents the total time of task execution of the virtual machine , represents the average time of the task execution of the virtual machine, LD represents the workload of the virtual machine cluster, and the smaller LD indicates that the load of the virtual machine is more balanced.

[0051] In step 4), the workflow comprehensive evaluation equation consists of the workflow execution overhead evaluation equation, the workflow execution time evaluation equation and the cluster load evaluation equation, and the equation expressions are as follows:

Fitness=x.sub.1*Cost+x.sub.2*Makespan+x.sub.3*LD  (14)

Cost≤revenue  (15)

Makespan≤D  (16)

[0052] where , , and are the overhead weight coefficient, the time weight coefficient and the cluster load weight coefficient, respectively, and the weight coefficient varies with the characteristics of the task; Cost represents the workflow execution overhead; D represents the deadline of the workflow; Makespan represents the workflow execution time, and LD represents the workload of the virtual machine cluster.

[0053] In step 4), a particle swarm optimization algorithm is constructed.

[0054] The particle swarm algorithm is a meta-heuristic algorithm that uses multiple particles to simulate the behavior of birds searching for food. Each particle can be regarded as a searching individual in the N-dimensional search space, and the current position of the particle is a candidate solution of the corresponding optimization problem. The flight process of the particle is the searching process of the individual. The flight speed of the particle can be dynamically adjusted according to the historical optimal position of the particle and the historical optimal position of the population. Particles only have two attributes: speed r and position x. The optimal solution searched by each particle individually is referred to as the individual optimal solution, and the optimal individual extremum in the particle swarm is the current global optimal solution. The speed and the position are constantly iteratively updated. Finally, the optimal solution satisfying the termination condition is obtained.

[0055] The formula of the traditional particle swarm algorithm is as follows:

[00010]$\begin{array}{cc}{v}_{i,d}^{t+1}=\omega \text{?}v\text{?}+r_1{c}_1\left(p\text{?}-x\text{?}\right)+r_2{c}_2\left(g\text{?}-x\text{?}\right)& \left(17\right)\end{array}$$x_{i,d}^{t-1}=x_{i,d}^t+v_{i,d}^{t+1}$$\text{?}\text{indicates text missing or illegible when filed}$

[0056] where d represents the dimension of the particle, represents the speed of the d-dimension of the i-th particle in the t-th iteration, and represents the position of the s-dimension of the i-th particle in the t-th iteration; and are the acceleration constant I and the acceleration constant 2, respectively, is the individual learning factor of each particle, is the social learning factor of each particle, and generally c, and c, are constants in the range of (0, 4); and are the random number I and the random number 2 in the range of (0, 1), respectively, represents the individual extreme value of the evaluation equation of the d-dimension of the i-th particle in the t-th iteration, represents the global extreme value of the evaluation equation of the d-dimension in the t-th iteration, and to is referred to as the inertia factor with a non-negative value. The larger the inertia factor, the stronger the global optimization ability but the weaker the local optimization ability. The smaller the inertia factor, the weaker the global optimization ability but the stronger the local optimization ability:

[00011]$\begin{array}{cc}{\omega }^t=\left({\omega }_{\mathrm{start}}-{\omega }_{\mathrm{end}}\right)\left(C-t\right)/C+{\omega }_{\mathrm{end}}& \left(18\right)\end{array}$

[0057] where to ω′ represents the value of the inertia factor ω in the t-th iteration, =0.9 is the initial value of the inertia factor ω, =0.4 is the final value of the inertia factor ω, C represents the total iteration number, and t represents the current iteration number.

[0058] The probability formula of the traditional simulated annealing algorithm is:

[00012]$\begin{array}{cc}p\left(x\text{?}.fwdarw.x\text{?}\right)=\{\begin{array}{cc}1& f\left(x\text{?}\right)<f\left(x\text{?}\right)\\ e\text{?}& f\left(x\text{?}\right)\ge f\left(x\text{?}\right)\end{array}& \left(19\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0059] where represents the probability that transitions to . If a target function is , the transition probability is 1. If ≥ the transition probability is

[00013]$e^{-\frac{f\left(x^{t+1}\right)-f\left(x^t\right)}{T^t},}$

T′ represents the annealing temperature of the t-th iteration, which varies with the iteration number, and the variation formula is as follows:

[00014]$\begin{array}{cc}T\text{?}=100\star e\text{?}& \left(20\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0060] The present disclosure uses the natural cooling equation of water from 100 degrees Celsius to 0 degrees Celsius for the change in temperature T′ in the formula, where t represents the current iteration number and n represents the number of particle swarms.

[0061] The specific execution flow of the particle swarm optimization scheduling algorithm according to the present disclosure is as shown in FIG. 2:

[0062] step 1), the particle swarm initializing the total iteration number C, the inertia factor ω, the acceleration constant and the acceleration constant , the random number and the random number , t=1, the particle grouping coefficient k=0 , i=1, initializing the number n of the particle swarms, randomly generating n particles, representing the individual extremum of particles using the execution overhead evaluation equation and the global extremum of particles using the execution overhead evaluation equation by the execution overhead evaluation equation Cost, representing the individual extremum of particles using the execution time evaluation equation and the global extremum of particles using the execution time evaluation equation by the execution time evaluation equation Makespan, representing the individual extremum of particles using the cluster load evaluation equation and the global extremum of particles using the cluster load evaluation equation by the cluster load evaluation equation LD, representing the individual extremum of particles using the workflow comprehensive evaluation equation and the global extremum of particles using the workflow comprehensive evaluation equation by the workflow comprehensive evaluation equation Fitness, and each dimension of particles represents each workflow;

[0063] step 2), judging whether the iteration number is less than or equal to C*a%, otherwise, jumping to step 3; starting to update the speed v and the position x of n particle swarms using For loop i=1:n , and in order to reduce the negative effect of the complexity increase caused by the multi-target particle swarm, using an alternating update method:

[0064] when i=.sup.4k+1:

[0065] the particle uses the following evaluation equation:

[00015]$\begin{array}{cc}\mathrm{Cos}t=\stackrel{M}{\underset{\text{?}}{.Math.}}\underset{\text{?}}{\overset{N}{.Math.}}k\text{?}\star \mathrm{ET}\text{?}\star \mathrm{Price}\text{?}+\stackrel{N}{\underset{j=1}{.Math.}}\underset{i=1}{\overset{\mathrm{PR}\text{?}}{.Math.}}\mathrm{TT}\text{?}\star {\mathrm{Price}}_{\mathrm{IE}}& \left(21\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0066] where the number of tasks in the workflow is N, the number of virtual machines is M, is a two-dimensional variable, represents the execution time of the task in the virtual machine , represents the execution cost coefficient of a task in a virtual machine , which is used to represent the overhead per unit time of a server executing a task, represents the time it takes for a task to complete data transmission to a task , represents the data transmission cost of two tasks in a cloud server network, which is used to represent the network overhead per unit time of data transmission, and represents all the pre-tasks of the task ;

[0067] the following particle swarm formula is used to update the speed c and the position x:

[00016]$\begin{array}{cc}{v}_{i,d}^{t+1}=\omega \text{?}v\text{?}+r_1{c}_1\left(p\text{?}-x\text{?}\right)+r_2{c}_2\left(g\text{?}-x\text{?}\right)& \left(22\right)\end{array}$$x_{i,d}^{t-1}=x_{i,d}^t+v_{i,d}^{t+1}$$\text{?}\text{indicates text missing or illegible when filed}$

[0068] the formula of the probability update speed v and the position x is as follows:

[00017]$\begin{array}{cc}p\left(x\text{?}.fwdarw.x\text{?},v\text{?}.fwdarw.v\text{?}\right)=\{\begin{array}{cc}1& \mathrm{Cos}t\left(x^{t+1}\right)<\mathrm{Cos}t\left(x^t\right)\\ e\text{?}& \mathrm{Cos}t\left(x^{t+1}\right)\ge \mathrm{Cos}t\left(x^t\right)\end{array}& \left(23\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0069] if <, is updated, is the individual information recording the found optimal particle; if a better is found, the newly found particle information replaces the previously stored old particle information; if in the search process, the particle finds <, <, <, <, the corresponding is updated;

[0070] when i=4k+2:

[0071] the particle i uses the following evaluation function:

[00018]$\begin{array}{cc}\mathrm{Makespan}=\stackrel{N}{\underset{i=1}{\max }}\left\{\mathrm{Makespan}\text{?}\right\}& \left(24\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0072] the following particle swarm formula is used to update the speed v and the position x:

[00019]$\begin{array}{cc}{v}_{i,d}^{t+1}=\omega \text{?}v\text{?}+r_1{c}_1\left(p\text{?}-x\text{?}\right)+r_2{c}_2\left(g\text{?}-x\text{?}\right)& \left(25\right)\end{array}$$x_{i,d}^{t-1}=x_{i,d}^t+v_{i,d}^{t+1}$$\text{?}\text{indicates text missing or illegible when filed}$

[0073] the formula of the probability update speed v and the position x is as follows:

[00020]$\begin{array}{cc}p\left(x\text{?}.fwdarw.x\text{?},v\text{?}.fwdarw.v\text{?}\right)=\{\begin{array}{cc}1& \mathrm{Makespan}\left(x^{t+1}\right)<\mathrm{Makespan}\left(x\text{?}\right)\\ e\text{?}& \mathrm{Makespan}\left(x^{t+1}\right)\ge \mathrm{Makespan}\left(x\text{?}\right)\end{array}& \left(26\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0074] if <, is updated, if the particle finds <, <, −, <, the corresponding is updated;

[0075] when i=4k+3:

[0076] the particle i uses the following evaluation function:

[00021]$\begin{array}{cc}\mathrm{LD}=\frac{\sqrt{\underset{\text{?}}{\overset{M}{.Math.}}{\left(\mathrm{ET}\text{?}-{\mathrm{AVE}}_{\mathrm{ET}}\right)}^2}}{M}& \left(27\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0077] the following particle swarm formula is used to update the speed v and the position x:

[00022]$\begin{array}{cc}{v}_{i,d}^{t+1}=\omega v\text{?}+r_1{c}_1\left(p\text{?}-x\text{?}\right)+r_2{c}_2\left(g\text{?}-x\text{?}\right)& \left(28\right)\end{array}$$x_{i,d}^{t-1}=x_{i,d}^t+v_{i,d}^{t+1}$$\text{?}\text{indicates text missing or illegible when filed}$

[0078] the formula of the probability update speed v and the position x is as follows:

[00023]$\begin{array}{cc}p\left(x\text{?}.fwdarw.x\text{?},v\text{?}.fwdarw.v\text{?}\right)=\{\begin{array}{cc}1& \mathrm{LD}\left(x\text{?}\right)<\mathrm{LD}\left(x^t\right)\\ e\text{?}& \mathrm{LD}\left(x\text{?}\right)\ge \mathrm{LD}\left(x^t\right)\end{array}& \left(29\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0079] if <, is updated, if the particle finds <, <, <, <, the corresponding is updated;

[0080] when i=4k+4:

[0081] the particle i uses the following comprehensive evaluation function:

Fitness=x.sub.i*Cost+x.sub.2*Makespan+x.sub.3*LD  (30)

[0082] the following particle swarm formula is used to update the speed V and the position x:

[00024]$\begin{array}{cc}{v}_{i,d}^{t+1}=\omega \text{?}v\text{?}+r_1{c}_1\left(p\text{?}-x\text{?}\right)+r_2{c}_2\left(g\text{?}-x\text{?}\right)& \left(31\right)\end{array}$$x_{i,d}^{t-1}=x_{i,d}^t+v_{i,d}^{t+1}$$\text{?}\text{indicates text missing or illegible when filed}$

[0083] the formula of the probability update speed v and the position x is as follows:

[00025]$\begin{array}{cc}p\left(x^{\text{?}}.fwdarw.x^{\text{?}},v^{\text{?}}.fwdarw.v^{\text{?}+1}\right)=\{\begin{array}{cc}1& \mathrm{Fitness}\left(x^{\text{?}}\right)<\mathrm{Fitness}\left(x^{\text{?}}\right)\\ e\frac{\text{?}}{T}& \mathrm{Fitness}\left(x^{\text{?}}\right)\ge \mathrm{Fitness}\left(x^{\text{?}}\right)\end{array}& \left(32\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0084] if <, is updated, if the particle finds <, <, <, <, the corresponding is updated:

[0085] after the above execution process, updating k: k=k+1, updating c: c=c+1, and jumping back to step 2);

[0086] step 3) judging whether the iteration number is less than or equal to D, otherwise, jumping to step 4); starting to update the speed v and the position x of n particles using For loop:

[0087] n particles all use the following comprehensive evaluation function:

Fitness=x.sub.1*Cost+x.sub.2*Makespan+x.sub.3*LD  (33)

[0088] the following particle swarm formula is used to update the speed and the position x:

[00026]$\begin{array}{cc}{v}_{i,d}^{t+1}=\omega \text{?}v\text{?}+r_1{c}_1\left(p\text{?}-x\text{?}\right)+r_2{c}_2\left(g\text{?}-x\text{?}\right)& \left(34\right)\end{array}$$x_{i,d}^{t-1}=x_{i,d}^t+v_{i,d}^{t+1}$$\text{?}\text{indicates text missing or illegible when filed}$

[0089] the judging formula of updating the speed and the position x is as follows:

[00027]$\begin{array}{cc}p\left(x^{\text{?}}.fwdarw.x^{\text{?}},v^{\text{?}}.fwdarw.v^{\text{?}+1}\right)=\{\begin{array}{cc}1& \mathrm{Fitness}\left(x^{\text{?}}\right)<\mathrm{Fitness}\left(x^{\text{?}}\right)\\ e\frac{\text{?}}{T}& \mathrm{Fitness}\left(x^{\text{?}}\right)\ge \mathrm{Fitness}\left(x^{\text{?}}\right)\end{array}& \left(35\right)\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0090] if <, is updated, if <, the corresponding is updated;

[0091] step 4) outputting the final result, and scheduling the workflow to the corresponding virtual machine using a scheduler (a module responsible for scheduling tasks to the corresponding virtual machine); checking whether there is a new workflow coming, if so, starting a new cycle, if not, ending the process.

[0092] A workflow scheduling system based on a multi-target particle swarm algorithm is provided, comprising the following program modules:

[0093] an overhead evaluating module, which is configured to construct a workflow execution overhead evaluation equation;

[0094] an execution time evaluating module, which is configured to construct a workflow execution time evaluation equation;

[0095] a cluster load evaluating module, which is configured to construct a cluster load evaluation equation;

[0096] a solving module, which is configured to construct a comprehensive evaluation equation containing the indexes in the above three evaluation equations, and schedule the workflow using the particle swarm optimization algorithm for the workflow execution overhead evaluation equation, the workflow execution time evaluation equation, the cluster load evaluation equation and the comprehensive evaluation equation, wherein the particle swarm optimization algorithm (PSO) divides the particle swarm into four parts evenly, it is assumed that each part of particles is iterated for C times, the first C*a% iterations of each part of particles search for the optimal solutions of the above four evaluation equations, respectively, and the last C*(1−a%) iterations search for the optimal solution of the comprehensive evaluation equation.

[0097] A computer readable storage medium is provided, which is used to store the workflow scheduling method based on the multi-target particle swarm algorithm described above.

[0098] The above embodiments are only used to illustrate the technical scheme of the present disclosure, rather than limit e the technical scheme. Researchers in the field can still make modifications or equivalent substitutions to the detailed description of embodiments of the present disclosure by referring to the above embodiments. Any modifications or equivalent substitutions that do not depart from the spirit and scope of the present disclosure are within the scope of protection of the pending claims of the present disclosure.