基于改进优先级规则的工作流费用优化方法  

Workflow Cost Optimization Heuristics Based on Advanced Priority Rule

作　　者：刘灿灿[1] 张卫民[1] 骆志刚[1] 任开军[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073

出　　处：《计算机研究与发展》2012年第7期1593-1600,共8页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2006AA01A123);国家自然科学基金项目(60903042)

摘　　要：效用网格下的工作流时间约束-费用优化调度是一个NP难问题,基于时间耦合强度(time-dependent coupling strength,TCS)的最适规则(best fit time-dependent coupling strength,BFTCS)将作业的资源特征与工作流的结构特征作为优先级规则的两个重要方面应用于迭代算法的改进阶段,取得了良好效果,然而,BFTCS忽略了工作流的时序特征.在已有工作的基础上,定义任务的时间灵活度(temporal mobility,TM)并设计基于时间耦合强度和时间灵活度的最适规则(best fit based on time-dependent coupling strength and temporal mobility,BFTCSTM).该规则在BFTCS规则的基础上选择TM较大的任务优先迭代,有效减缓了迭代过程中工作流长度的增长过程,使其他任务能进一步优化费用的机会增大,改善了工作流的费用优化效果.实验结果证明了BFTCSTM的优越性.The time and cost trade-off problem in workflow scheduling with deadline constraint in utility grids is an NP-hard, but attractive problem. In the past studies, the priority rule, best fit based on time-dependent coupling strength （referred as BFTCS）, was adopted to solve this question because BFTCS considers both the features of resources and workflow structures and uses them as two important factors in the iterative heuristic for cost optimization. However, BFTCS did not consider another important factor： the temporal feature of the workflow. In this paper, we define temporal mobility （TM） to describe the temporal feature of the workflow, and incorporate TM into the iterative stage as an important factor to improve the workflow execution cost further. This novel priority rule （referred as best fit based on time-dependent coupling strength and temporal mobility, BFTCSTM） gives priority to the tasks with larger TM and smaller TCS （time-dependent coupling strength） during the iterative stage. Therefore, compared with BFTCS, BFTCSTM slows down the increasing rate of the workflow execution time greatly, and provides more opportunities to other tasks to optimize cost, which decreases the total cost further. The experimental results demonstrate the advantages of BFTCSTM based iterative heuristic.

关 键 词：工作流调度 效用网格 费用优化 时间耦合强度 时间灵活度 

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