CN-121979651-A - Cloud computing task scheduling method and system based on two-stage adaptive search

CN121979651ACN 121979651 ACN121979651 ACN 121979651ACN-121979651-A

Abstract

The invention discloses a cloud computing task scheduling algorithm and a cloud computing task scheduling system based on two-stage self-adaptive search. The scheduling algorithm module completes population aggregation through a preference perception distance strategy, and when the mass center variance of the population reaches a threshold value, a preference region classification strategy is adopted to conduct second-stage search, and a double-layer coding mode and a task balance mapping strategy are combined to generate a child population so as to realize multi-objective collaborative optimization. Under the medium-large scale cloud environment, the method is superior to the existing algorithm in indexes such as finishing time, lease cost, energy consumption, load balancing index and the like, can effectively balance the benefits of multiple parties, and provides a new scheme for task scheduling in the complex cloud environment.

Inventors

ZHAO ZHICHENG
LI YONGWEI
LIU JIE
HOU HUANHUAN

Assignees

太原工业学院

Dates

Publication Date: 20260505
Application Date: 20251203

Claims (8)

1. The cloud computing task scheduling system based on the two-stage self-adaptive search is characterized by comprising a task receiving module, a virtual machine management module, a scheduling model construction module, a two-stage self-adaptive scheduling algorithm module and a result output module; the task receiving module is used for receiving cloud tasks submitted by users, collecting and storing attribute information of each task, wherein the task attribute information comprises task byte length, input size and output size; The virtual machine management module is used for managing virtual machine clusters in the cloud platform, recording configuration attributes of each virtual machine, wherein the configuration attributes comprise the number of CPUs, CPU processing capacity, bandwidth, memory and lease cost per unit time, and monitoring the running state of the virtual machine in real time; The scheduling model construction module is used for establishing a multi-objective scheduling model based on the preference of a user and a cloud service provider, and the optimization targets of the multi-objective scheduling model comprise total task completion time, total lease cost, total energy consumption and server load balancing indexes; the two-stage self-adaptive scheduling algorithm module is used for calling a preset two-stage self-adaptive searching scheduling algorithm to solve the multi-target scheduling model and outputting an optimal task scheduling scheme; and the result output module is used for issuing the optimal task scheduling scheme to the virtual machine cluster, controlling the virtual machine to execute the corresponding task, and feeding back the task execution state to the user.
2. The system according to claim 1, wherein in the scheduling model building module, the total task completion time Makespan is determined by the maximum task completion time of all virtual machines, and the calculation formula is: ; The VT j is the task completion time of the jth virtual machine, which is determined by the sum of the completion times of all tasks distributed on the virtual machine, the total lease Cost is the sum of the transmission Cost and the calculation Cost of all virtual machines, the total Energy Cost is the sum of the Energy consumption of all virtual machines in an active state and the Energy consumption of the virtual machines in an idle state, and the Load balancing index Load is calculated by the variance of the task execution time of each virtual machine and the average execution time of all virtual machines.
3. A cloud computing task scheduling method based on two-stage adaptive search, applied to the cloud computing task scheduling system according to any one of claims 1-2, comprising the following steps: step 1, initializing and setting, namely generating an initial population P by adopting a double-layer coding mode, wherein a first layer of double-layer coding represents the sequence of adding tasks into a dispatching center, and a second layer of double-layer coding represents the mapping relation between the tasks and a virtual machine; Generating a child population, namely generating a child population O by combining an initial population P by adopting a cross variation and task balance mapping strategy, wherein the cross variation adopts a sequence-based cross method, simulates binary cross and polynomial variation, and the task balance mapping strategy is used for balancing loads by sequencing the virtual machines according to task completion time and exchanging tasks on different virtual machines; Step 3, two-stage self-adaptive searching, namely merging the parent population P and the child population O to obtain a new population P ', and executing two-stage self-adaptive environment selection based on the new population P' to obtain a next-generation parent population CP; And step 4, terminating the judgment, namely outputting a non-dominant solution as an optimal task scheduling scheme if the maximum iteration number is reached, and returning to the step 2 to continue iteration if the maximum iteration number is not reached.
4. A method according to claim 3, wherein the specific procedure of two-stage adaptive environment selection in step 3 comprises: Step 3.1, calculating an angle value between an individual and a reference vector in the population CP, associating the individual to a subarea corresponding to the reference vector with the minimum angle, performing non-dominant ranking on the population, and reserving the number of non-dominant ranking layers of the individual; Step 3.2, calculating an adaptive conversion condition, wherein the adaptive conversion condition is judged through a population centroid Variance and iteration times, the population centroid Centroid is calculated from a preference perception distance average value of individuals in the population, the Variance is used for measuring the population aggregation degree, and the method enters a first stage when the comprehensive stage conversion strategy meets the following formula, otherwise, enters a second stage: ; wherein G is the current iteration number, G max is the maximum iteration number, η is a two-stage conversion parameter, m is the number of objective functions, and ∂ is a conversion threshold; step 3.3, searching in the first stage, wherein in each subarea, individuals with the minimum non-dominant layer number are reserved, if a plurality of individuals with the minimum PBI value based on the punishment boundary intersection are selected, and the individuals with the minimum preference perception distance are reserved to form a population after pre-screening; And 3.4, searching in the second stage, namely dividing a target space into a plurality of space levels, pre-screening, classifying the preferred areas of the individuals according to the reference points, preferentially reserving the area individuals for balancing the benefits of the users and the cloud service provider, and supplementing the population to a set scale.
5. The method of claim 4, wherein the preference perceived distance ED (x) is calculated by the formula Wherein For the euclidean distance of an individual from a reference point, Is the euclidean distance of the individual from the current spatial origin.
6. The method of claim 4, wherein the target space is divided into four regions by the preference region classification in step 3.4, and the regions to which the individual belongs are determined according to an average space level gp of the individual, an average space level gu of the user preference, and an average space level gc of the server preference, corresponding to a region for balancing benefits of both sides, a region for maintaining benefits of the user, a region for satisfying requirements of the cloud service provider, and a region for failing to satisfy requirements of either side, respectively.
7. The method of claim 3, wherein in the task balancing mapping strategy, the tasks of the virtual machines are first sorted according to ascending order of task completion time, the index numbers K i of the virtual machines are recorded, the task minimum z of all the virtual machines is determined, and then part of the tasks on the virtual machines with less tasks are exchanged with the corresponding tasks on the virtual machines with more tasks until all the virtual machines complete task balancing adjustment.
8. A method according to claim 3, wherein the two-stage transition parameter η has a value of 0.7, the transition threshold ∂ has a value of 0.025, the population size is set to 100 and the maximum number of iterations is set to 100.

Description

Cloud computing task scheduling method and system based on two-stage adaptive search Technical Field The invention relates to the technical field of cloud computing, in particular to a cloud computing task scheduling method and system based on two-stage self-adaptive search. Background Cloud computing integrates multiple technologies such as parallel computing and distributed computing, provides elastic computing resources, large-scale data storage and efficient data processing services by means of the Internet and virtual machine technology, and is widely applied to scenes such as deep learning model training and large-scale intelligent reasoning. With the continuous expansion of cloud computing user groups, task scheduling pressure of cloud data centers is increasing, and meanwhile, benefit conflicts between users and cloud service providers are becoming more obvious. Users are more concerned with task completion time and rental costs, while cloud service providers are focused on load balancing, resource utilization, and energy consumption control. Most of the existing scheduling algorithms are designed from a single angle, and multi-party interest requirements are difficult to consider. The traditional heuristic algorithm is based on static task and resource information decisions, cannot adapt to dynamic changes of cloud computing environments, and the multi-objective optimization algorithm can obtain global non-dominant solutions, but the solutions are not selected specifically, so that win-win of a user and a cloud service provider is difficult to achieve. Therefore, there is a need for an efficient task scheduling method and system that can leverage the benefits of multiple parties and accommodate different scale cloud environments. Disclosure of Invention The application provides a cloud computing task scheduling method and system based on two-stage self-adaptive search, and aims to solve the problems of aggravation of conflict of interests of users and cloud service providers and difficulty in multi-objective trade-off in the existing cloud computing task scheduling. According to a first aspect, in one embodiment, a cloud computing task scheduling system based on two-stage adaptive search is provided, including a task receiving module, a virtual machine management module, a scheduling model construction module, a two-stage adaptive scheduling algorithm module, and a result output module; the task receiving module is used for receiving cloud tasks submitted by users, collecting and storing attribute information of each task, wherein the task attribute information comprises task byte length, input size and output size; The virtual machine management module is used for managing virtual machine clusters in the cloud platform, recording configuration attributes of each virtual machine, wherein the configuration attributes comprise the number of CPUs, CPU processing capacity, bandwidth, memory and lease cost per unit time, and monitoring the running state of the virtual machine in real time; The scheduling model construction module is used for establishing a multi-objective scheduling model based on the preference of a user and a cloud service provider, and the optimization targets of the multi-objective scheduling model comprise total task completion time, total lease cost, total energy consumption and server load balancing indexes; the two-stage self-adaptive scheduling algorithm module is used for calling a preset two-stage self-adaptive searching scheduling algorithm to solve the multi-target scheduling model and outputting an optimal task scheduling scheme; and the result output module is used for issuing the optimal task scheduling scheme to the virtual machine cluster, controlling the virtual machine to execute the corresponding task, and feeding back the task execution state to the user. In some embodiments, in the scheduling model building module, the total task completion time Makespan is determined by the maximum task completion time of all virtual machines, and a calculation formula is as follows: ; The VT j is the task completion time of the jth virtual machine, which is determined by the sum of the completion times of all tasks distributed on the virtual machine, the total lease Cost is the sum of the transmission Cost and the calculation Cost of all virtual machines, the total Energy Cost is the sum of the Energy consumption of all virtual machines in an active state and the Energy consumption of the virtual machines in an idle state, and the Load balancing index Load is calculated by the variance of the task execution time of each virtual machine and the average execution time of all virtual machines. According to a second aspect, in one embodiment, there is provided a cloud computing task scheduling method based on two-stage adaptive search, including the steps of: step 1, initializing and setting, namely generating an initial population P by adopting a double-layer coding mode, wherein a