Abstract: To deal with large numbers of business processes in constrained time,Directed Acyclic Graph (DAG) was used for solving the scheduling problem of multiple DAGs shared on heterogeneous distributed resources.Two parameter association methods that included relative strictness and laxity were put forward to balance the priority of constraint DAG.An improved Heterogeneous Earliest Finish Time(HEFT) algorithm based on priority was given to schedule multiple DAGs with deadline constraint.The phenomenon of “overload” was detected due to high emergency degree of DAG scheduling which could be selective discarded with corresponding measures so as to maximize DAG before deadline.Simulations showed that the proposed algorithm could greatly improve the scheduling performance.

Key words: business process, directed acyclic graph, task priority, deadline, relative rigor, heterogeneous earliest finish time algorithm

摘要： 为了在有限的时间内处理完成大量业务流程,用有向无环图(DAG)进行建模,解决多DAG共享异构资源调度问题。提出结合相对严格程度和宽松度两种权衡DAG时序约束紧急程度的方法,衡量多DAG任务的优先级;基于紧急程度的异构最早完成时间(HEFT)改进算法,对具有时序约束的多个DAG任务进行调度;探测由于DAG调度紧急程度过高产生的过载现象,利用相关策略对任务进行选择性丢弃,在用户截止期限内完成DAG数量最大化的目标。通过仿真实验证明,所提算法对调度性能有极大的提高。

关键词: 业务流程, 有向无环图, 任务优先级, 截止期限, 相对严格程度, HEFT算法