Abstract: To map tasks into multiple resources for improving the execution efficiency,and to manage a business process effectively,a novel Directed Acyclic Graph (DAG) model was given based on the traditional DAG model,which divided the tasks into serial and parallel scheduling parts.A valid main path for task scheduling was extracted to make the task be expanded into parallel mode based on the novel DAG model.Based on completion time and deadline of the task,a stretch scheduling strategy was put forward to meet the deadline of tasks and reduce the occupation of resources,which made other tasks could be scheduled effectively.A simulation example was provided to prove the excellent feasibility of the proposed method.

Key words: directed acyclic graph, real-time scheduling, execution deadline, valid main path, parallel scheduling, stretch scheduling

摘要： 为了将任务映射到多个资源中运行,以提高任务的执行效率进而有效管理和组织一个业务流程。在传统有向无环图模型的基础上,首先给出一种新的模型,将调度任务分解成若干串行和可并行调度部分;然后在新的有向无环图模型基础上提取任务调度的一条有效主路径,按照有效主路径将任务并行展开;随后基于任务的执行完成时间和执行截止期限提出一种拉伸调度策略,使任务在满足执行截止期限的同时,尽可能减少对处理器资源的占用,使其他任务能有效地进行调度。通过仿真实例证明所提方法具有很好的适用性。

关键词: 有向无环图, 实时调度, 执行截止期限, 有效主路径, 并行调度, 拉伸调度