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

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