Abstract: The characteristic of provisioning resource dynamically in cloud platform is suitable for the scientific computation of workflows.The existing works on workflow scheduling mainly consider the factors of makespan and cost optimization,and have little involving in robustness.In this paper,a resource scheduling algorithm based on Markov decision process theory is proposed,in which the tasks of the whole workflow are partitioned and the deadline on task partitions based on calculation time of task is distributed.Under the requirement that the deadline of whole workflow is not violated,the proposed algorithm makes the tolerance time maximum,and finally allocates resources on workflow tasks in heterogeneous cloud environment.The experimental results show that the proposed algorithm could effectively improve the robustness of the schedule within a given deadline and budget.