Scheduling Deadline-Constrained Workflows To Maximize Profit In Hybrid Cloud Computing

Complex scientific computing tasks requires a large number of resources for execution.It is crucial for cloud providers to rent public resources to meet users' requirements when private resources are insufficient.This thesis considers scheduling deadline-constrained workflows to optimize the monetary cost of energy and lease public resources or maximize the profit of a cloud provider.This problem is of important practical significance.Compared to other NPhard workflow scheduling problems,the main challenges of the considered problem lie in:(i)The time-varying electricity price in the private cloud makes it much difficult to allocate tasks of workflow applications to appropriate resources to reduce the total electricity cost of private provider.(ii)The heterogeneity of the provided resources leads the problem much hard to find the best solution with the maximal profit of private cloud provider since different allocations result in various slack times using various the slack time processing strategies.For the problem under study,an adaptive swarm-entropy-based PSO workflow scheduling algorithm(SEPSO)is proposed which consists in two phases: workflow application sequencing and task allocating.The former generates workflow application sequences while the latter allocates tasks to resources which is composed of four components: deadline partition based on maximum depth of tasks,initial task sequence constructing,dynamic resource allocation and task sequence updating.Four rules are presented to generate initial task sequences: minimal processing time first,maximum successors first,shortest slack time first and random task sequencing.In the resource allocation component,a dynamic resource allocating method is developed which allocates tasks to private cloud preferentially.In case of private resources not meeting the deadline constraint,tasks are allocated to public resources and VMs are selected based on cost performance ratio.Since task sequences have great influence on scheduling performance,different task sequences might generate different rental costs and electricity cost which affect the profit of the private cloud provider.In order to search better solutions for the considered problem,a task sequence adjustment algorithm is introduced in which the flight parameters of PSO are adaptively adjusted based on the swarm distribution entropy to balance the intensification and diversification in the search process and avoid the algorithm to premuture.To verify the performance of the proposed algorithm,the multi-factor analysis of variance(ANOVA)technique is adopted to analyze the involved parameters and algorithm components.The proposed algorithm with the calibrated parameters and components is compared to other three existing algorithms for similar problems over standard scientific workflow instances.Experimental results indicate that the proposed algorithm outperforms the compared algorithms with different deadline levels,workflow scales and the number of tasks.