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

效用网格下的工作流时间约束-费用优化调度是一个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的优越性.

Workflow Cost Optimization Heuristics Based on Advanced Priority Rule

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.