In this work, we propose an approach for the execution of science-intensive applications within the framework of the concept of Workflow-as-a-Service (WaaS). WaaS platforms, being the so-called multitenant environments, provide efficient mechanisms for managing continuous and heterogeneous job-flows in cloud computing. The workflow execution schedule is built using the critical jobs method (CJM), which allows scheduling of information-dependent tasks within the directed acyclic graph (DAG) model. Nevertheless, it must be adjusted to consider the actual dynamics of the resources’ utilization during each scheduling cycle. In this scenario, along with the complexity of scheduling composite workflows, an additional problem arises to efficiently manage the cloud resources, that is, to determine the start and shutdown times of virtual machines (VMs), considering the available economic policy. To handle this problem, we propose a modification to CJM. The resulting solution combines several heuristics to optimize cloud resource management for WaaS platforms. Some experiments with the real-world workflows prove the optimization efficiency of the proposed approach.