Abstract: With the development of cloud computing, deploying workflows onto cloud computing platforms has become a popular choice. Compared with the traditional local workflow, cloud workflow not only needs to consider the requirements such as the execution time, but also considers the economic cost. In order to improve the resource utilization, cloud computing service providers provide spot instances, which are very cheap but unstable. Aiming at the problem of workflow scheduling and execution in cloud computing, this paper proposes a spot instance configuration and scheduling method that meets the workflow execution time budget. This method uses Markov models and dynamic programming methods to predict the price of spot instances and obtain the lowest cost bid strategy. At the same time, to satisfy the execution time budget of the workflow, the instances used in the workflow are configured under the estimated bid strategy. Experimental results show that, compared with using ondemand instances, our method can save up to 89.9% computation cost, while meeting the workflow execution time budget.

Key words: cloud computing, spot instance, workflow scheduling, pricing strategy