Scheduling Methods For Cloud Workflows With Various Resource Provisioning Manners

Workflow scheduling problems in cloud computing are widely used in scientific computation,business analysis,traffic planning,manufacturing and other fields.The important problem is to select the appropriate resource provisioning manners for different type of workflow applications with the total renting cost minimization.Generally,three types of resource provisioning manners are provided by the Cloud service providers: reserved instances,on-demand instances and spot instances.In this paper,we consider three types of typical workflow applications: periodical workflow applications,batch workflow applications and preemptive workflow applications.According to the characteristics of different workflow applications and resource provisioning manners,different resource provisioning model and scheduling methods were proposed.The objective is to minimize the total resource renting costs.The main work of the paper is described as follows:(1)Periodic workflow applications with the reserved resource provisioning manners are considered.According to the characteristics of the long-term periodical workflow applications,the reserved manner is used to rent virtual machine resources.A Precedence Tree based Heuristic(PTH)is developed.Three types of sink nodes are established for the workflow combination.Based on the enumeration tree scheme,a dynamic one-step global search strategy is developed for the schedule construction.Two main schedule improvement procedures considering both execution modes and resource types are presented.The multi-factor analysis of variance technique is used to calibrate different rules,parameters and verify the effectiveness of the proposed method.(2)Batch workflow applications with the hybridization of reserved and on-demand resource provisioning manners are considered.According to the parallelization of batch tasks,a mathematical model is established for the considered problem.An iterative population-based meta-heuristic(APA)is developed.According to the shift vectors obtained during the search procedure,timetables are generated quickly.The appropriate amounts of reserved and on-demand resources are determined by an incremental optimization method.The utilization of each resource is balanced in a swaying way,in terms of which the probabilistic matrix is updated for the next iteration.Components and parameters of APA are calibrated with the ANOVA technique.Experimental results demonstrate the effectiveness and efficiency of the proposed algorithm.(3)Short-term preemptive workflow applications with the hybridization of spot and ondemand resource provisioning manners are considered.An idle time block-based method(ITB)is proposed for the considered problem.The initial task allocation sequence is determined by the priority of each task.Workflow deadlines are divided into task deadlines to balance the idle time block between tasks.Different idle time block-based searing and improving strategies are developed to construct schedules for the workflow applications.Schedules are improved by a forward and backward moving mechanism.Components and parameters of ITB are calibrated with the ANOVA technique.Experimental and statistical results demonstrate the effectiveness of the proposed algorithm over a lot of tests.