【摘要】 网格资源需求的不断增长使价格成为资源进行竞争的有效手段,有向无环图DAG(Directed Acyclic Graph)表示的工作流时间费用优化问题是网格环境下一个重要问题.通常情况下,DAG应用调度属于NP-Hard问题.通过分析活动间的时序特征,给出时间耦合强度TCS(Time-dependent Coupling Strength)的定义,用于标识一个活动最大的时间耦合活动个数;将其作为优先级规则的一个重要信息和BF规则(BestFit)结合,设计出时间耦合强度最适规则BFTCS(Best Fit with Time-dependent Coupling Strength),用于启发式算法的改进阶段,逐步提高初始可行解的性能.模拟实验结果表明,相对现有的启发式算法,基于BFTCS规则的启发算法能获得最好的性能和较快的运行效率;最后讨论了问题参数对算法性能和效率的影响.更多还原

【Abstract】 The increasing demand for grid computing resources calls for an incentive-compatible pricing mechanism for differentiated service qualities.The Time-Cost tradeoff problem for grid workflow applications described by Directed Acyclic Graph(DAG) becomes a significant problem.DAG-based optimization problem has been shown to be NP-hard in general cases.In this paper,a new concept called TCS(Time-dependent Coupling Strength) is introduced,which is identified for a given activity the maximum number of time-dependent coupling activities.By incorporating it into priority rule BF(Best Fit) which only takes into account the ratio of the cost improvement to the increase of duration of an activity,a novel priority rule BFTCS(Best Fit with Time-dependent Coupling Strength) is proposed,which is implemented in a heuristic to improve further the feasible initial solutions.Computational experiments indicate that rule BFTCS based heuristic can perform better than other existing heuristics but require a little more computation time.As well,the impact of problem parameters on the heuristics is discussed.更多还原