CN-121979677-A - Workflow cost optimization scheduling method driven by random forest in multi-cloud environment

CN121979677ACN 121979677 ACN121979677 ACN 121979677ACN-121979677-A

Abstract

The invention discloses a workflow cost optimization scheduling method driven by random forests in a cloudy environment, which utilizes a random forest regression model to fuse task characteristics and resource characteristics, generates training samples through three strategies, combines an optimization scoring mechanism of cost and overtime punishment to screen out high-quality initial particles, utilizes dynamic parameters and boundary constraint strategies driven by population diversity to quantify the population diversity by utilizing the average Euclidean distance from all particles to the mass center of the population, dynamically adjusts non-linear attenuation inertia weight and learning factor, simultaneously introduces a reflection boundary mechanism to correct out-of-range particles, finally designs a dynamic weight fitness function, dynamically adjusts the solution of time constraint according to the urgency of cut-off time to apply gradient punishment, and dynamically adapts performance weight and cost weight. The invention has excellent success rate of searching the optimal solution, and is obviously superior to the similar algorithm in terms of reducing the dispatching execution cost.

Inventors

Zhang longxin
DU LILI
WEN ZHIHUA
Cao Buqing
AI LIHUA
GUO QINGSONG
LIN SHENG
ZHAO WENYU

Assignees

湖南工业大学

Dates

Publication Date: 20260505
Application Date: 20260120

Claims (10)

1. The workflow cost optimization scheduling method driven by random forests in a multi-cloud environment is characterized by comprising the following steps of: S1, constructing a workflow scheduling model in a cloud environment The workflow scheduling model comprises a workflow model and a resource model, wherein the workflow scheduling model meets the constraint of the deadline at the scheduling target On the premise of minimizing the total execution cost of the workflow , wherein, In order to calculate the cost of the process, Is the communication cost; S2, generating a group of high-quality initial scheduling scheme sets based on task features in a workflow and virtual machine resource features in a cloud environment by utilizing a random forest regression model, fusing the task features and the resource features to construct training sample feature vectors, generating training samples through multiple strategies, and screening high-quality initial particles by combining a cost and overtime punishment optimization scoring mechanism; s3, calculating the average Euclidean distance from all particles to the mass center of the population to quantify the population diversity, and dynamically adjusting the inertia weight and the learning factor of a particle swarm algorithm according to the population diversity; S4, performing an adaptive particle swarm optimization iteration process on the initial particle swarm until all particles are traversed, and updating the positions and the speeds of the particles through iteration; meanwhile, distinguishing a critical task from a non-critical task based on task looseness, and preferentially distributing virtual machine resources with high performance level for the critical task; s5, dynamically adjusting time and cost weight based on deadline urgency, constructing a dynamic weight fitness function, superposing a timeout penalty term, and evaluating scheduling schemes corresponding to all particles; s6, outputting a final scheduling scheme which meets the deadline constraint and has the optimal total execution cost.
2. The method for optimizing and scheduling workflow cost driven by random forest in a cloud environment according to claim 1, wherein in the step S4, the task relaxation is a calculation of a difference between a latest start time and an earliest start time of each task on each virtual machine as a relaxation time of the task on the virtual machine, and a task with a relaxation time less than or equal to zero is identified as a critical task on a critical path.
3. The method for optimizing and scheduling the workflow cost driven by the random forest in the cloud environment according to claim 1, wherein in the step S2, the training of the random forest regression model comprises the following steps: s21, generating training samples, namely generating a plurality of task-virtual machine mapping relations as candidate samples by adopting various strategies including a balance guiding strategy, a time performance priority strategy and a diversity exploration strategy, wherein the time performance priority strategy distributes all tasks to virtual machines in a high-performance resource pool; S22, calculating sample scores, namely calculating an optimization score for each candidate sample according to the estimated execution cost and the estimated timeout of each candidate sample and a scoring function integrating the cost and the timeout punishment, wherein the expression is as follows: Wherein the cost weight Above the timeout penalty, the economic cost is optimized preferentially, The weight for the timeout penalty is set to 800; S23, model training, namely training a random forest regression model by taking a feature vector formed by splicing task features and resource features as input and taking the optimization score as a prediction target, wherein the task features comprise task calculation amount, a hierarchy of tasks in a DAG, task input and output degrees and key path identification amount, and the calculation capability Price per unit time, cost per unit calculation; S24, generating an initial scheme, namely predicting the scores matched with all the optional virtual machines by using a trained model for each task in the workflow, and selecting the virtual machine with the optimal score as an initial allocation resource of the task, wherein the allocation results of all the tasks form an initial particle.
4. The method for optimizing and scheduling workflow costs driven by random forest in a cloudy environment according to claim 3, wherein in step S21, the balancing and guiding strategy is implemented by setting a threshold to be set as By the formula Computing tasks Will satisfy the level weight of Secondly, carrying out multidimensional screening on virtual machine resources to form a high-performance resource pool And low cost resource pool Assigning critical tasks Virtual machines within, assigning non-critical tasks Virtual machines within.
5. The method for optimizing and scheduling workflow cost driven by random forest in a cloudy environment according to claim 1, wherein in step S3, the ratio of the average euclidean distance from all particles to the centroid to the solution space dimension is population diversity The method comprises the following steps: Wherein the particle quantity is [ ] ) As a dynamic parameter, is adaptively determined according to the task scale, Represent the first The number of the individual particles is determined, In order to be able to carry out a number of tasks, Is the center of the population, Is the euclidean norm.
6. The method for optimizing and scheduling the workflow cost driven by random forest in a cloudy environment according to claim 1, wherein in the step S3, the inertia weight adopts a nonlinear attenuation strategy, and the expression is: Wherein, the For the current number of iterations, For the maximum iteration number, the initial value of the inertia weight is obtained by dynamic adjustment The setting is made to be 0.9, Indicating that the attenuation coefficient is set to 0.3. The embodiment sets two dynamic factors for dynamic adjustment, including individual cognitive factors And social learning factors The expressions are respectively: Wherein, the , Respectively set as 0.6,2.2; , is respectively set to be 1.4,2.2 parts of the two parts, Is the first Population diversity at each iteration.
7. The method for optimizing and scheduling the workflow cost driven by random forest in a cloudy environment according to claim 1, wherein in the step S4, the expression of particle velocity update is: Wherein, the Is the first Particles at the time of iteration In the first place The speed of the dimension is such that, For an individual optimal position of the particles, Is the first group Globally optimal position of dimension, dimension of particle In correspondence with the task(s), Is a random disturbance factor; According to the current position and updated speed of the particles, determining the position of the next moment, so as to realize the search of the optimal solution, wherein the expression of the update of the particle position is as follows: Wherein, the Is shown in the first At the time of iteration, the first The particles are at the first Position of dimension relative to the first The particles are the first Task allocation Indexing; Indicating particles In the first place The speed at which the iteration is performed, Is a particle Through the first New positions reached after a number of iterations.
8. The method for optimizing and scheduling workflow cost driven by random forest in a cloudy environment according to claim 1, wherein in step S4, boundary overflow is handled by a reflection boundary policy The expression is: Then according to the attenuation correction of the velocity of the overflowed particles, the correction expression is that , For the attenuation coefficient, 0.3 was set.
9. The method for optimizing and scheduling the workflow cost driven by random forest in a cloudy environment according to claim 1, wherein the time weight and the cost weight are dynamically adjusted according to the task deadline urgency, and the expressions are respectively: Wherein, the As the weight of the time in question, Is a cost weight.
10. The method for optimizing and scheduling workflow cost driven by random forest in a cloudy environment according to claim 1, wherein in step S5, the dynamic weight fitness function is a comprehensive fitness With timeout penalty Sum of all of them For a normalized linear weighted sum of the time and cost targets, The penalty of (2) is positively correlated with the constraint violation amount, and the final fitness function is: Wherein, the Representing the total execution cost of the device, The time at which the workflow is completed is indicated, The cost weight is represented by a weight of the cost, The time-weight is represented by a time-weight, The time of the cut-off is indicated, Representing penalty coefficients; When the neighborhood is optimal Is better than the current global optimal solution Updating the global optimum and outputting an optimum solution The expression is: 。

Description

Workflow cost optimization scheduling method driven by random forest in multi-cloud environment Technical Field The invention belongs to the technical field of cloud computing systems and resource management, and particularly relates to a workflow cost optimization scheduling method driven by random forests in a multi-cloud environment. Background In the field of today's rapidly developing cloud computing, with the continuous expansion of workflow scale, single cloud service providers gradually expose limitations in terms of resource supply capability, service continuity, and the like. To this end, a multi-cloud environment integrating multiple cloud service provider resources becomes the core computing infrastructure for enterprises and research institutions to meet diverse workflow applications and workload requirements. In the field of multi-cloud computing, amazon, google, microsoft and other mainstream cloud service providers can provide abundant and flexible solutions and services for users by virtue of widely distributed computing and storage facilities. The workflow scheduling technology in the existing multi-cloud environment has advanced to some extent, for example, a traditional Particle Swarm Optimization (PSO) algorithm has global searching capability by simulating a natural mechanism, and local optimization can be avoided to a certain extent. The scheduling method based on machine learning can capture implicit association of tasks and resources by means of historical data, so that the intelligent scheduling level is improved, but the technologies still have obvious short plates, and the scheduling cost is difficult to be minimized while strict deadline constraint is met. Specifically, the meta heuristic algorithm is mostly set by adopting static parameters, and inertia weight and learning factors cannot be dynamically adjusted according to population distribution, so that searching blindness is easy to occur in the global exploration stage of the algorithm, convergence stagnation is easy to occur in the local development stage, and searching breadth and precision are difficult to balance. The initial solution is generated by a multi-dependency random allocation mechanism, the cooperative guidance of task features and resource features is lacking, the initial population quality is low, and the search period of the global optimal solution is greatly prolonged. The matching of the critical tasks and the resources lacks pertinence, and task priorities are distinguished without combining task looseness, so that the critical path tasks are difficult to obtain high-performance resources preferentially, and the deadline satisfaction rate is directly influenced. Meanwhile, the traditional search mechanism lacks of fine exploration of a solution space, the boundary processing mode is unreasonable, a large number of invalid search behaviors exist, and the scheduling cost is further increased. The scheduling method based on machine learning faces the problems of high training cost and high dependence on real-time data quality, and is difficult to adapt to dynamic changes of resource performance, pricing and task dependence in a cloudy environment. The prior art still has challenges in balancing search efficiency and solution quality, adapting to a multi-cloud dynamic environment, controlling scheduling cost and the like, and how to minimize workflow scheduling cost on the premise of meeting deadline constraint becomes a core problem to be solved currently. Ye et al in 2023 proposed an F-ant colony optimization algorithm (F-ant colony optimization, F-ACO), fusing deadline allocation, adaptive ant colony optimization and cost-driven feedback mechanisms. The algorithm dynamically adjusts the expiration date of the task sub-through a weight ascending order model, utilizes self-adaptive ant colony optimization to construct a task scheduling sequence, and combines a resource idle slot feedback mechanism to reduce the idle time of the virtual machine. By decomposing the deadline constraint to the task level and combining the cost-driven resource allocation strategy, the overall scheduling cost is effectively reduced while the workflow is ensured to be completed on time. According to the algorithm, a multi-level dynamic adjustment mechanism formed by deadline decomposition, self-adaptive ant colony optimization and cost feedback is adopted, so that the scheduling accuracy is improved, but higher collaborative calculation cost is introduced by serial dependence and real-time coordination of each level, and the overall complexity of the algorithm is obviously increased. Sun ET al in 2024 proposed an enhanced task type priority algorithm (ENHANCED TASK TYPE FIRST algorithm, ET2 FA) aimed at coping with cloud environments with instance dormancy and charging per second characteristics, and designed a three-phase scheduling framework. The algorithm sorts the tasks according to topology level and task type and directs t