Workflow is currently the most common execution model for composite applications across multiple disciplines: seismology (CyberShake), bioinformatics (Epigenomics, SIPHT), astrophysics (Montage), gravitational wave physics (LIGO), hydro and aerodynamics, quantum chemistry, nanotechnology, hydrometeorology, modeling of social systems and transport infrastructure. The workflow is usually a collection of interrelated tasks within the directed acyclic graph (DAG) model parameterized by a priori, usually inaccurate, user estimates for tasks (relative computational or data transfer volumes, execution durations etc.). In this work, we propose an approach for scheduling science-intensive applications within the framework of the concept of Workflow-as-a-Service (WaaS). The proposed scheduling model is built based on the critical jobs’ method, which allows us to obtain the deadlines for completing each of the workflow tasks under given efficiency criteria and inaccurate user estimates. This schedule must consider the actual dynamics of the WaaS resources’ utilization and lifecycle of virtual machines (VMs). To solve this problem, we propose a novel procedure to group and assign workflow tasks to VMs instances provided by the Infrastructure as a Service (IaaS) provider.