A significant aspect of cloud computing is scheduling of a large number of real-time concurrent workflow instances. Most of the existing scheduling algorithms are designed for a single complex workflow instance. This study examined instance-intensive workflows bounded by SLA constraints, including user-defined deadlines.The scheduling method for theseworkflows with dynamicworkloads should be able to handle changing conditions and maximize the utilization rate of the cloud resources. The study proposes an adaptive two-stage deadline-constrained scheduling (ATSDS) strategy that considers run-time circumstances of workflows in the cloud environment. The stages are workflow fragmentation and resource allocation.In the first stage, the workflows according to cloud run-time circumstances (number of Virtual Machines (VMs) and average available bandwidth) are dynamically fragmented. In the second stage, using the workflow deadline and the capacity of the VMs, the workflow fragments created are allocated to the VMs to be executed. The simulation results show improvements in terms of workflow completion time, number of messages exchanged, percentage of workflows that meet the deadline and VM usage cost compared to other approaches.