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

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