According to the three-tier structure of the cloud computing system, the request initiated by the tenant is first processed through the request scheduling system, and then forwarded to the cloud application service for execution. The resource scheduling system monitors the real-time status of cloud application service and then scales them accordingly. However, cloud workflow engine service, the key component in the cloud business process management system, is characterized by long startup times and high resource consumption. Unreasonable scaling strategies often result in problems such as scaling late, scaling excessively and so on. Therefore, to achieve elastic scaling of the cloud workflow engine, it is essential to predict future request traffic in advance and calculate corresponding future resource demands. For the future request traffic, since all requests initiated by tenants will pass through the request scheduling system, this paper believes that the future request traffic can be predicted using the status information from both request scheduling system and cloud application service. So finally, this paper proposed a G/G/c queue model-based scaling algorithm, which works with the EDF-based request scheduling system, to resolve the issue of elastic scaling in cloud workflow services. The scaling algorithm predicts the future resource demands using real-time data from the request scheduling system and cloud application service. This algorithm reduces average cloud resource supply while maintaining low SLA violation rate and QoS over-provision rate, which can fully meet the requirements of cloud service providers.