Abstract: The existing workflow scheduling algorithms are simply designed for single complex instance, unsuitable for scheduling instance-intensive cloud workflows. To address this problem, a new scheduling algorithm, named Minimum Total Cost Under User-designated Total Deadline (MCUD), was proposed based on multiple instances. For the workflow instances of the same type, after classification, MCUD algorithm distributed the user-designated overall deadline into each task with a new distribution method. In addition, MCUD algorithm adjusted the sub-deadline of successive tasks dynamically during the scheduling process. Instances of the same nature are given the sub-deadline distribution results of some difference, which can avoid the fierce competition of cheaper services and increase the efficiency of resource utilization. The simulation results show that MCUD algorithm further decreases the total execution cost and total execution time while meeting the user-designated deadline in comparison with other algorithms.

Key words: cloud workflow, resource scheduling, workflow instance, workflow scheduling, deadline

摘要： 工作流调度算法仅适用于单个复杂工作流实例,而不适用于实例密集型云工作流实例,为此,提出了基于实例密集型的云工作流调度算法(MCUD)。MCUD算法先对待处理的一组工作流实例进行分类,再对分类后的同类工作流实例采用一种新的分配方法将用户指定的总最后期限分配到各任务;同时,在调度的过程中动态地调整后续任务的子最后期限。MCUD算法对同类工作流实例中的任务分配不同子最后期限,减小了资源竞争,提高了资源的利用率。仿真实验表明,MCUD相比于其他算法,在满足总的最后期限的前提下更进一步地降低了执行成本和执行时间。

关键词: 云工作流, 资源调度, 工作流实例, 工作流调度, 最后期限