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.