Abstract: Cloud computing has demonstrated to be a modern model that offers IT assets depend on the payper- use basis as a service over the internet. Scientific workflow applications are benefiting from running on the cloud computing services. However, the challenge is to optimize workflow scheduling algorithms are still required an additional work. This study proposes max-min+ which is an extension for the max-min algorithm that is able to minimize the total execution time and cost of workflow execution. We tested the proposed algorithm via WorkflowSim with using 5 realistic scientific workflow applications. The results of max-min+ outperforms the original max-min algorithm by minimizing the overall workflow execution time.