Abstract: Leveling heuristics are used to solve the time-cost trade-off problems in the grid workflow scheduling with temporal constraint by distributing the tasks into groups based on levels and scheduling them level by level. However, due to the absence of an effective method to ensure the temporal constraint, the applicability and performance of these leveling heuristics are damaged. Based on the previous heuristic deadline bottom level (DBL), an advanced heuristic referred to as temporal consistency based deadline bottom level (TCDBL) is proposed by studying the temporal properties of workflows and by optimizing their execution cost based on the temporal consistency. TCDBL satisfies the workflow temporal constraint by setting a consistent temporal point for each task, distributes the redundancy time based on the parallel degree of each level, and optimizes the workflow cost with a soft temporal constraint strategy. As a result, the workflow execution cost decreases. The experimental results in this study demonstrate that the average execution cost of TCDBL is 14% less than the cost of DBL.