中文摘要：

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

英文摘要：

The increasing demand for grid computing resources calls for an incentive-compatible pricing mechanism for differentiated service qualifies. 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 nile BFTCS （Best Fit with Timedependent Coupling Strength） is proposed, which is implemented in a heuristic to improve further the feasible initial solutions. Computational experiments indicate that nile 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.