Research On Crowdsourcing Task Scheduling Algorithm With Deadline Constraints In Hybrid Cloud Environment

As cloud resources are delivered in a pay-as-you-go manner,more and more users are willing to submit and execute bag-of-task(Bo T)applications on clouds.From the perspective of cloud providers,when their private clouds cannot provide insufficient resources to process all Bo T applications with user-specified quality of service(Qo S)requirements,cloud providers have to outsource certain tasks to public clouds and inccur extra costs.The research tasks of this thesis is oriented toward the bag-of-tasks scheduling problem in the hybrid cloud.Based upon the characteristics of Bo T applications,this thesis takes into account the Qo S requirements as well as the deadline constraint,and accordingly formulates the optimization model of Bo T scheduling problem for computation-intensive applications.We use a task sequence to represent a valid solution to the scheduling problem,and determine the latest start times of all tasks according to the deadline constraint for each application.We establish the mathematical expression for cloud provider's profit and set it as the scheduling objective of the optimization model.In addition,considering both computation-and data-intensive application scenarios,we further formulate the scheduling model for Bo T applications that are both computation-and data-intensive.Since the two task scheduling problems can be described as integer programming optimization models(task scheduling problems are in general NP-hard),intelligent optimization algorithms,such as genetic algorithm,are suitable for solving this category of optimization problems.In order to solve the Bo T scheduling problems in above-mentioned two scenarios,we develop two task scheduling algorithms based on the improved genetic algorithm.On one hand,for the computation-intensive Bo T scheduling problem,we propose a novel single-point crossover operator that incorporates the currently best chromosome into the evolutionary procedure,and employs a probabilistic model to explore global good genes hiding in the population.The proposed crossover operator not only can generate high-quality offspring individual,but also can address the limitation of traditional GAs which may easily fall into local optima.We further design a task dispatch strategy for calculation of each individual's fitness value.On the other hand,for both computation-and data-intensive Bo T scheduling problem,we improve the above-mentioned single-point crossover operator to further present new doublepoint and multi-point crossover operators,which are combined with a solution initialization strategy to enhance the solution exploration ability of the proposed algorithm.Furthermore,we design a new task dispatch and fitness calculation method for both computation-and dataintensive scheduling scenarios,and finally implement an effective scheduling algorithm for computation-and data-intensive application tasks.We perform simulation experiments to evaluate the performance of the two proposed task algorithms.Experimental results demonstrate that,for computation-intensive Bo T applications,our algorithm is capable of generating high-quality scheduling solutions while satisfying the Qo S requirements.For both computation-and data-intensive Bo T scheduling applications,our algorithm can achieve more reasonable and higher-quality scheduling solutions by taking into account the impact of data amount upon task scheduling.Oriented toward intensive computing and data-driven hybrid cloud environments,The Bo T scheduling algorithms proposed in this thesis are of great theoretical significance for maximizing cloud provider's profit and ensuring the Qos of hybrid clouds.