关键词: 并行分层, 工作流调度, 有向无环图, 启发式, 优化算法

Abstract: Aiming at the workflow time cost optimization problem described by scheduling Directed Acyclic Graph (DAG) under deadline constraint,the Deadline Bottom Level (DBL) algorithm didn't considered the concurrence in the real executing process which caused much more shatter time.For this reason,a novel heuristics algorithm of Concurrent Level Workflow Scheduling (CLWS) was proposed.In this algorithm,some tasks of workflow in actual executive process were divided into the same level with the other concurrent tasks.The redundant time was distributed according to the concurrent degree of each level,and the multiple adjacent tasks with dependency relationship in each level were optimized by using Markov Decision Process (MDP) algorithm.Based on the workflow described by balanced structure and unbalanced structure of DAG,a number of simulation experiments were made to compare three algorithms of Minimum Critical Path (MCP),DBL and Deadline Top Level (DTL),and the results showed that CLWS algorithm had significant improvement.

Key words: concurrent level, workflow scheduling, directed acyclic graph, heuristics, optimization algorithm