CN-121979635-A - Instance intensive workflow scheduling method and system based on dynamic particle swarm optimization

CN121979635ACN 121979635 ACN121979635 ACN 121979635ACN-121979635-A

Abstract

The invention discloses an instance intensive workflow scheduling method and system based on dynamic particle swarm optimization, which constructs a multi-objective optimization function aiming at minimizing the total finishing time of a workflow and the total energy consumption of a system by acquiring an instance intensive workflow model and a container cloud resource model, initializing a particle swarm population by adopting two-stage codes, correcting the dependency relationship of the task priority codes, and finally executing a dynamic self-adaptive particle swarm optimization algorithm to output an optimal scheduling scheme. The method has the advantages that the task execution sequence and the mapping relation of the instance-virtual machine are respectively and accurately represented through two-stage coding, the dependence relation correction mechanism is combined, the scheduling scheme is ensured to accord with the topology constraint of the workflow, so that the feasibility of the scheme is improved, the particle swarm structure, the particle type and the key parameters are adaptively adjusted in the iterative process through the dynamic adaptive particle swarm optimization algorithm, and the global exploration capacity and the convergence efficiency of the algorithm in a complex solution space are enhanced.

Inventors

ZHANG ZHEN
WEI YI
LIN LIHUI
JIAO JINTAO

Assignees

武夷学院

Dates

Publication Date: 20260505
Application Date: 20260120

Claims (10)

1. An instance-intensive workflow scheduling method based on dynamic particle swarm optimization, which is characterized by comprising the following steps: acquiring an instance-intensive workflow model and a container cloud resource model, wherein the instance-intensive workflow model comprises task sets, dependency relationships among tasks and instance sets corresponding to each task, and the container cloud resource model comprises virtual machine cluster resource information and container resource quota information deployed on a virtual machine; constructing a multi-objective optimization function aiming at minimizing the total finishing time of the workflow and the total energy consumption of a system based on the instance intensive workflow model and the container cloud resource model; Initializing a particle swarm population by adopting two-stage codes, wherein the first-stage code is a task priority code and is used for representing the execution sequence of tasks in a workflow, the second-stage code is an instance-virtual machine mapping code and is used for representing the number of a target virtual machine to which each task instance is scheduled, and the task priority code is subjected to dependency correction; And executing a dynamic self-adaptive particle swarm optimization algorithm to solve the multi-objective optimization function, and outputting a task scheduling scheme corresponding to the global optimal particle position vector when the dynamic self-adaptive particle swarm optimization algorithm meets a termination condition.
2. The instance-intensive workflow scheduling method based on dynamic particle swarm optimization of claim 1, wherein the dynamic adaptive particle swarm optimization algorithm comprises: performing dynamic subgroup division on the particle swarm population based on clustering and a Lewy flight mechanism; calculating global optimal position vectors of each sub group respectively, and calculating average optimal particle position vectors based on the global optimal position vectors of all sub groups; Dynamically adjusting individual learning factors, social learning factors, inertia weights and communication particle proportions in the current iteration by adopting a parameter self-adaptive strategy; Dividing particles in each subgroup into common particles and communication particles according to the communication particle proportion, and updating the speeds and positions of the two types of particles according to the individual learning factors, the social learning factors, the inertia weights, the global optimal position vector of the subgroup and the average optimal particle position vector respectively; After each iteration, updating the particle swarm population by adopting a population updating strategy based on roulette selection, multi-point crossing and constraint variation; And carrying out self-adaptive combination on the subgroups based on similarity detection results among the subgroup clustering centers, and combining all the subgroups into a single population for fine search after a preset iteration condition is reached.
3. The instance-intensive workflow scheduling method based on dynamic particle swarm optimization of claim 2, wherein the dynamic sub-swarm classification of the particle swarm population based on a clustering and a lewy flight mechanism comprises: randomly selecting a preset number of particles from the particle swarm population to serve as an initial clustering center; Calculating Euclidean distance between each particle in the particle swarm population and each initial clustering center, and distributing each particle to the nearest clustering center according to a minimum distance principle to form initial subgroup division; calculating the average value of all particle position vectors in each initial subgroup to be used as a new clustering center of the initial subgroup; A Lewy flight mechanism is adopted to apply random disturbance to the position of the new clustering center so as to update the position of the clustering center; and repeatedly executing the processes of calculating Euclidean distance, distributing particles, calculating a mean value and applying the disturbance of the Lewy flight mechanism until the change of the cluster center position is smaller than a preset threshold value or the maximum iteration number is reached, so as to obtain stable subgroup division and a final cluster center.
4. The instance-intensive workflow scheduling method based on dynamic particle swarm optimization of claim 2, wherein calculating a global optimal position vector for each sub-swarm, and calculating an average optimal particle position vector based on the global optimal position vectors of all sub-swarms, respectively, comprises: Adopting a normalized fitness function based on logarithmic transformation to respectively calculate fitness values corresponding to all particles in each subgroup; Selecting a particle with the largest fitness value in each subgroup, and determining the position vector of the particle as the global optimal position vector of the subgroup; acquiring the global optimal position vectors of all subgroups; and calculating the arithmetic average value of all the global optimal position vectors, and determining the calculation result as the average optimal particle position vector.
5. The instance-intensive workflow scheduling method based on dynamic particle swarm optimization of claim 2, wherein the dynamically adjusting individual learning factors, social learning factors, inertial weights, and communication particle proportions in the current iteration using a parameter adaptive strategy comprises: Dynamically adjusting the individual learning factors and the social learning factors through a nonlinear Sigmoid function according to the proportion of the current iteration times to the maximum iteration times, wherein a higher individual learning factor value and a lower social learning factor value are set at the initial stage of algorithm iteration, and the individual learning factor value is nonlinear decreased and the social learning factor value is nonlinear increased along with iteration; Dynamically adjusting the communication particle proportion through an exponential growth function according to the proportion of the current iteration times to the maximum iteration times, wherein the smaller communication particle proportion is set at the initial stage of algorithm iteration, and the communication particle proportion is gradually increased along with iteration; and adjusting the inertia weight by adopting a sectional self-adaptive strategy, wherein a fixed larger value is adopted at the initial stage of iteration, and the value of the inertia weight is dynamically calculated according to the evolutionary speed of particles and the aggregation degree of particle swarms at the middle and later stages of iteration.
6. The instance-intensive workflow scheduling method of claim 1, wherein the population of particles comprises a particle location vector, initializing the population of particles with a two-stage code, comprising: generating a position vector for each particle in the particle swarm population, wherein the position vector is formed by sequentially connecting a task priority coding segment and an instance-virtual machine mapping coding segment; The task priority coding segment comprises a first number of first dimensions, the first number is equal to the total number of tasks in the workflow, each first dimension of the task priority coding segment corresponds to one task, and the value stored in each first dimension is the priority value of the corresponding task; The instance-virtual machine mapping coding segment comprises a second number of second dimensions, the second number is equal to the total number of instances of all tasks in the workflow, each second dimension of the instance-virtual machine mapping coding segment corresponds to a task instance, and a value stored in each second dimension is the number of a target virtual machine to which the corresponding task instance is allocated; and correcting the dependency relationship of the task priority coding segment, wherein the method comprises the following steps of: Identifying all tasks meeting execution constraint in the workflow, for each task to be corrected, acquiring priority values of all direct precursor tasks of the tasks to be corrected, and calculating the minimum value of the priorities; If the priority of the task to be corrected is not greater than the minimum value, adjusting the priority of the task to be corrected to ensure that the priority value is greater than the minimum value; And combining the corrected task priority coding segment with the instance-virtual machine mapping coding segment to form an initialized particle position vector.
7. The instance-intensive workflow scheduling method based on dynamic particle swarm optimization of claim 1, wherein constructing a multi-objective optimization function targeting minimizing total completion time of a workflow and minimizing total system energy consumption based on the instance-intensive workflow model and a container cloud resource model, comprises: calculating the starting execution time and the finishing time of each task instance on a target virtual machine according to the task dependency relationship in the instance intensive workflow model, the instance resource requirement and the virtual machine and container resource configuration in the container cloud resource model; Determining the total finishing time of the workflow based on the finishing time of all task instances; calculating the total dynamic energy consumption of the system according to the rated power of the processors in the container cloud resource model, the dynamic power proportionality coefficient and the total execution time of each processor; calculating the total static energy consumption of the system according to the rated power of the processor, the state of the server to which the processor belongs and the dynamic power proportionality coefficient in the container cloud resource model; Adding the total dynamic energy consumption of the system to the total static energy consumption of the system to obtain the total energy consumption of the system; Constructing the multi-objective optimization function by taking the total finishing time of the minimum workflow as a first optimization target and the total energy consumption of the minimum system as a second optimization target; And carrying out normalization processing on the first optimization target and the second optimization target by adopting a logarithmic transformation strategy, and constructing an adaptability function for evaluating particle quality based on a normalization result, namely the multi-target optimization function.
8. The instance-intensive workflow scheduling method based on dynamic particle swarm optimization of claim 1, wherein executing a dynamic adaptive particle swarm optimization algorithm to solve the multi-objective optimization function comprises: starting an iterative optimization process by taking the initialized particle swarm population as an initial solution set; In each iteration, according to a dynamic self-adaptive particle swarm optimization algorithm, carrying out dynamic subgroup division, global optimal position vector and average optimal particle position vector calculation, parameter self-adaptive adjustment, particle speed and position update and population update operation based on roulette selection, multi-point crossing and constraint variation on an algorithm particle swarm in the current iteration; Wherein, the algorithm particle swarm consists of particle individuals representing candidate scheduling schemes in the current iteration; After each iteration, carrying out self-adaptive combination judgment and operation on the algorithm particle swarm structure in the current iteration based on the similarity detection result among the swarm clustering centers; when the iteration times reach a preset merging condition, merging all the current algorithm particle swarms into a single algorithm population, and carrying out fine search of a solution space on the single algorithm population by adopting a standard particle swarm optimization algorithm flow; And when the iterative optimization process reaches the preset maximum iterative times or meets the preset convergence condition, terminating the execution of the dynamic self-adaptive particle swarm optimization algorithm.
9. The instance-intensive workflow scheduling method based on dynamic particle swarm optimization according to claim 8, wherein when the dynamic adaptive particle swarm optimization algorithm satisfies a termination condition, outputting a task scheduling scheme corresponding to a global optimal particle position vector, comprising: When the dynamic self-adaptive particle swarm optimization algorithm reaches the preset maximum iteration times or the improvement amplitude of the global optimal fitness value in continuous multiple iterations is smaller than a preset convergence threshold value, judging that the algorithm meets a termination condition; Extracting particles with the highest fitness value from the final population, and determining the position vector of the particles as the global optimal particle position vector; resolving the global optimal particle position vector, comprising: decoding the execution sequence of all tasks in the workflow from the task priority coding segment of the global optimal particle position vector; decoding a target virtual machine number to which each task instance is allocated from the instance-virtual machine mapping coding segment of the global optimal particle position vector; Based on the analyzed task execution sequence and the instance-virtual machine mapping relation, a final task scheduling scheme comprising the starting execution time and the execution ending time of each task instance and the occupied virtual machine and container resource information is generated.
10. An instance-intensive workflow scheduling system based on dynamic particle swarm optimization, characterized in that it is adapted to the scheduling method of any of claims 1 to 9, said scheduling system comprising: The system comprises a model acquisition module, a model analysis module and a model analysis module, wherein the model acquisition module is used for acquiring an instance-intensive workflow model and a container cloud resource model, the instance-intensive workflow model comprises task sets, dependency relationships among tasks and instance sets corresponding to each task, and the container cloud resource model comprises virtual machine cluster resource information and container resource quota information deployed on a virtual machine; The optimization function construction module is used for constructing a multi-objective optimization function aiming at minimizing the total completion time of the workflow and the total energy consumption of the system based on the instance intensive workflow model and the container cloud resource model; the system comprises a population initialization module, a task priority code generation module and a task management module, wherein the population initialization module is used for initializing a particle population by adopting two-stage codes, the first-stage code is a task priority code and used for representing the execution sequence of tasks in a workflow, the second-stage code is an instance-virtual machine mapping code and used for representing the number of a target virtual machine to which each task instance is scheduled, and the task priority code is subjected to dependency relation correction; the dynamic self-adaptive optimization solving module is used for executing a dynamic self-adaptive particle swarm optimization algorithm to solve the multi-objective optimization function; and the scheduling scheme output module is used for outputting a task scheduling scheme corresponding to the global optimal particle position vector when the dynamic self-adaptive particle swarm optimization algorithm meets the termination condition.

Description

Instance intensive workflow scheduling method and system based on dynamic particle swarm optimization Technical Field The invention relates to the technical field of computers, in particular to an instance intensive workflow scheduling method and system based on dynamic particle swarm optimization. Background Container cloud platforms have become a key infrastructure supporting big data analysis and scientific computing tasks that provide flexible resource provisioning for instance-intensive workflows through virtual machines and container technology. An instance-intensive workflow is composed of a large number of task instances with complex topological dependencies, and the scheduling problem is a typical multi-constraint, high-dimensional optimization problem. The existing scheduling method usually adopts a particle swarm optimization and other element heuristic algorithms, but when the traditional particle swarm algorithm solves the problems, the particle coding mode is difficult to simultaneously and accurately represent the task execution sequence and the resource mapping relation, and the generated scheduling scheme is low in feasibility due to lack of explicit guarantee of task dependency constraint. Disclosure of Invention In view of the above, the present invention aims to provide an example intensive workflow scheduling method and system based on dynamic particle swarm optimization. In order to achieve the technical purpose, the invention adopts the following technical scheme: in a first aspect, the present invention provides an instance-intensive workflow scheduling method based on dynamic particle swarm optimization, comprising: Acquiring an instance intensive workflow model and a container cloud resource model, wherein the instance intensive workflow model comprises task sets, dependency relations among tasks and instance sets corresponding to each task, and the container cloud resource model comprises virtual machine cluster resource information and container resource quota information deployed on a virtual machine; Constructing a multi-objective optimization function aiming at minimizing the total finishing time of the workflow and the total energy consumption of a system based on the instance intensive workflow model and the container cloud resource model; Initializing a particle swarm population by adopting two-stage codes, wherein the first-stage code is a task priority code and is used for representing the execution sequence of tasks in a workflow, the second-stage code is an instance-virtual machine mapping code and is used for representing the number of a target virtual machine to which each task instance is scheduled, and the dependency relation correction is carried out on the task priority code; And executing a dynamic self-adaptive particle swarm optimization algorithm to solve the multi-objective optimization function, and outputting a task scheduling scheme corresponding to the global optimal particle position vector when the dynamic self-adaptive particle swarm optimization algorithm meets the termination condition. In some embodiments, the dynamic adaptive particle swarm optimization algorithm comprises: carrying out dynamic subgroup division on particle swarm population based on clustering and a Lewy flight mechanism; calculating global optimal position vectors of each sub group respectively, and calculating average optimal particle position vectors based on the global optimal position vectors of all sub groups; Dynamically adjusting individual learning factors, social learning factors, inertia weights and communication particle proportions in the current iteration by adopting a parameter self-adaptive strategy; Dividing particles in each subgroup into common particles and communication particles according to the proportion of the communication particles, and updating the speeds and positions of the two types of particles according to individual learning factors, social learning factors, inertia weights, global optimal position vectors of the subgroups and average optimal particle position vectors respectively; After each iteration, updating the particle swarm population by adopting a population updating strategy based on roulette selection, multi-point crossing and constraint variation; And carrying out self-adaptive combination on the subgroups based on similarity detection results among the subgroup clustering centers, and combining all the subgroups into a single population for fine search after a preset iteration condition is reached. In some embodiments, dynamic sub-population partitioning of particle swarm populations based on clustering and a lewy flight mechanism includes: Randomly selecting a preset number of particles from a particle swarm population to serve as an initial clustering center; calculating Euclidean distance between each particle in the particle swarm population and each initial clustering center, and distributing each particle to the nearest clustering