The execution of the workload using the Web Service Composition (WSC) in the heterogeneous cloud is a difficult task. The current real-time workload needs a dynamic method for the allocation of the resources for the different tasks and their sub-tasks with a good Quality-of-Service (QoS) requirement. Existing methods mainly focused on reducing the execution time and cost of the workload, which leads to an increase in energy and latency of the execution of the given workload. To overcome the problems of the existing algorithms this paper presents an Efficient Re-planning (ERP) Algorithm to execute the large number of scientific workloads in a heterogeneous cloud network. This paper presents an algorithm to increase the reliability and availability in the WSC for a dynamic workload. It also minimizes the energy consumption for the execution of the workload. The experimental results have been tested using the Montage Workflow. The results show that ERP-WSC model is more reliable and efficient when compared with the existing QL-HEFT Algorithm.