It is recommended to use a distributed cloud to construct a high resource consumption system such as streaming media service, which not only meets the requirements of multi-region deployment, but can also make full use of the resources in the cloud to ensure the service quality while controlling system budget costs. Make the difference of cost functions in cloud centers sitting in different regions, the heterogeneous cost model should be introduced in distributed cloud oriented scheduling. Given the highly dynamic and random characteristics of user requests in streaming media applications, it is expected to respond to as many user requests as possible under a given cost budget. Mean demand model ignores details of changes in resource requirements over short time intervals, and leads to inefficient use of resources. To overcome the disadvantages of mean demand model, we use a stochastic model to capture the fine-grained information of resource demand, and use a common cost function to describe the heterogeneous cost model, and also establish a general nonlinear programming problem model. To reduce the algorithm complexity, the lower bound of the solution is quickly obtained based on dynamic programming, and then the near optimal solution is obtained by iteratively approximation. The simulation results show that, compared with the classical average demand model based scheduling algorithm, the proposed algorithm can additionally meet 15% more of the user requests when the number of regions is large, and can additionally satisfy up to nearly 40% of the user requests as the budget decreases. The algorithm is not affected by differences in price functions or by user requests statistics across different regions. As a result, when used in globally deployed large-scale streaming media system, the proposed algorithm can significantly increase the number of satisfied user requests with limited computing time, thus is adaptable to a wide range of cloud infrastructure service providers.