Research On Scheduling Strategy Of Scientific Workflow In Grid Environments

Nowadays, Grid technology is still an important supporting environment for scientific workflow management system. In such a decentralized, dynamic and autonomous environment, providing non-trivial QoS for end users is a major challenge, which has gained more and more attention. As a core component of scientific workflow management system, scheduling strategies have important and direct impact on the performance of system, resource utilization and QoS guarantee. However, some QoS metrics are contracted and restricted with each other. How to optimize the operation efficiency among these aspects is still a hot topic. Because of the dynamicity and autonomy of Grid system, existing scheduling strategies cannot to be applied into real Grid environment and provide an effective and efficient QoS guarantee service. As a result, the studies for workflow scheduling strategy are helpful for accelerating the pace of scientific progress in both theory and practice.Based on the discussion of the current studies and drawbacks of scientific workflow management system and scheduling strategies, this thesis deeply investigates efficient and effective workflow scheduling strategies in Grid environments. The main contribution of this thesis can be summarized as follows:(1) Research on the cost optimization problems for scientific workflow with deadline constraint. Leveling technology is a popular method in solving the problem, which has been researched by many researchers. However, leveling technology need to set fixed time period for workflow tasks and restrict the search scope. In the paper, a novel cost optimization algorithm, called CROTD is proposed, which combine CRO algorithm and a heuristic algorithm called GreedyCost-TD. Aimed at the optimization problem, a construction method of random initial molecule based on task dependency and detail implementation for four different molecules reaction are proposed. Orthogonal experiment is introduced into the parameter selection of algorithm. Experimental result show CROTD algorithm can obtain better performance. (2) Research on the on-line workflow scheduling algorithm based performance evaluation. Because of the autonomy and task completion of Grid resource, it is difficult to predict the execute time of task in dynamic Grid environment. Based on the analysis of task characteristic in Grid resource, M/M/C stochastic service model is used to model the service capacity and workload status of Grid resource. Then, the calculating method approximately for task execution time is presented. Aimed at the minimizing the makespan of workflow with cost constraint, a dynamic workflow scheduling algorithm based on performance evaluation, called SSWC_PE, is proposed. Compared with Greedytime-CD and LOSS, SSWC_PE performs better on makespan.(3) Research on the reliable workflow scheduling algorithm with time constraint. In order to improve the execution reliability of workflow and enhanced user satisfaction, a stochastic service model considering the impact of local tasks is adopted to describe dynamic workloads of Grid resources. A definition called execution reliability of task is presented to evaluate the probability that meeting deadline of task. Then, combined with the traditional definition for resource reliability, a novel resource reliability evaluation model is introduced. Based on the model, a reliability scheduling algorithm for scientific workflow with cost constraint called RSA_TC is presented. The results of extensive simulation experiments show that the proposed algorithm outperforms PRMS and HEFT, with respect to guarantee deadline and adaptability to dynamic Grid environment.(4) Research on the deadline guarantee enhanced scientific workflow management system architecture and corresponding scheduling strategy. Current workflow management system usually adopt following different techniques to alleviate this problem:resource reservation, rescheduling, task migration, task duplication, which cannot solve the problem efficiently. Aimed at the time sensitive scientific workflow, a novel workflow orchestrating system architecture called EDGESA is presented, which enforces the deadline guarantee of e-science applications by leasing reliable Cloud services. Aimed at the scheduling strategy of deadline-sensitive scientific workflow, metric called Default Risk of Task is provided to judge whether Cloud services should be used. Time Series Model is adopted to evaluate the reponse time of Cloud service. The experimental results show that EDGESA can achieve better performance than other strategies on user’s deadline guarantee.