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 proposed scheduling model is built based on the critical jobs’ method, which allows scheduling of information-dependent tasks within the directed acyclic graph model. This schedule must consider the actual dynamics of the cloud resources’ utilization and lifecycle. In this way, 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 novel procedure to group and assign workflow tasks to VM instances provided by the cloud infrastructure provider. 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.