Abstract: Many workflow applications often have the timing constraints such that each processing of a workflow needs to be finished within its deadline. There have been some work to improve the performance of time-constrained workflow processing. Previous work mainly considered to meet the execution time request of the critical path tasks or all of the tasks both on the critical path and on the non-critical path. Few of them, however, have taken into account the fact that successful execution of workflow within its deadline is also affected by “normal state” and “abnormal state” of grid resources occurring in successive turns and by the relative difference in execution time between tasks on the critical path and tasks on the non-critical path. To solve the problems, some new definitions, such as critical region and reliability of critical region are defined, and then a new resource allocating algorithm is proposed in terms of the finite-state continuous-time Markov process through selecting a resource combination scheme which has the lowest expenditure under certain credit level of the resource reliability in the DAG-based workflow. Compared with previous algorithms, this method is much more efficient in resource allocating, and almost no degrading in successful grid workflow execution rate. The simulation shows the validity of the new algorithm.