Abstract: In grid, users usually pay more attention to the execution time of workflow than other QoS metrics. Consequently how to effectively guarantee meeting users deadline requirements is a challenging problem for workflow scheduling in dynamic grid environment. Stochastic service model is utilized to describe dynamic processing capacity of grid resource and its dynamic workloads. The concept of deadline satisfaction degree (DSD) is defined and a corresponding calculation method for deadline satisfaction degree of workflow (DSDW) is provided. The task precedence relations represented in a DAG are converted into task execution priorities represented in numbers based on task length, and then the candidate resource for each task in the workflow is selected based on the rule of maximizing DSD. The deadline distribution is modeled as a non-linear programming problem with constraints and resolved with an interior point algorithm. A deadline satisfaction enhanced scheduling algorithm for workflow (DSESAW), which includes resource selection and overall deadline distribution, is put forward finally. The extensive simulations using real-world workflow application and grid system are made to validate this algorithm. The experimental results show that this scheduling algorithm achieves better performance than other two algorithms used in real grid system on adaptation to dynamic grid environment and users deadline guarantee.