QoS约束下的分层工作流调度算法  

Hierarchical Workflow Scheduling Algorithm with QoS Constraint

作　　者：彭佳[1] 谭文安[1] 孙勇[1] 陈森博[1] 

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京210016

出　　处：《小型微型计算机系统》2015年第7期1444-1448,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61272036)资助

摘　　要：将工作流抽象为有向无环图(Directed Acyclic Graph,DAG)的建模方法已经取得广泛应用,时间约束下执行费用优化问题仍是其一个难解的问题.通过分析有向无环图中的并行结构,对模型进行有效的层次划分是一种有效的解决方案.针对如何合理划分分层后模型中的冗余时间问题,提出了一种基于结构分析的分层工作流调度算法(Structure Analysis Based Level,SAL).该算法针对分层后各层次中的并行执行过程,提出一种更加合理的冗余时间划分方法,通过模拟工作流DAG建模实验,对比分析SAL算法与最小关键路径法(Minimum Critical Path,MCP)、逆向分层算法(Deadline Bottom Level,DBL)效果,实验结果表明SAL算法的有效性.M odeling workflowusing Directed Acyclic Graph（ DAG） has been widely used in the academic and industrial domain,but cost-optimal problem within the time-constraint still needs to be addressed. The solution through analyzing the concurrency structure to partition the tasks into groups is an efficient way. To solve the problem that the redundancy time cannot be divided reasonably,this paper presents Structure Analysis Based Level WorkflowScheduling Algorithm（ SAL）. This algorithm presents the solution to distribute the redundancy time via analyzing the structure into each level. Comparing with M CP（ M inimum Critical Path） and DBL（ Deadline Bottom Level）,the results of the experiments reveal that SAL shows better performance.

关 键 词：工作流调度 有向无环图 结构分析 启发式算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]