Pointing at the current problems concerning workflow scheduling management for lowering the hiring cost of cloud services, this paper has focused on task scheduling and proposed an innovative approach based on task replication with a change order mechanism. Most previous works, generally, utilize a series of algorithms through optimizing target hosts with a process cycle and then choosing the optimal target hosts to achieve minimum turnaround time. However, it does not assure optimum cloud service cost. Based on this argument, the paper introduces an enhanced approach for cost optimization by studying the task dependencies in the task network of the workflow job and replicating the tasks on idle virtual machines. The workflow represented as task network shows a path with minimum idle time; known as the critical path. It basically employs the modified critical path and task replication. The simulation outcome shows that; the proposed algorithm decreases the execution time and cost for the given scientific workflow.