Highly Complex Resource Scheduling for Stochastic Demands in Heterogeneous Clouds

To handle user requests coming from all over the world, online services need to schedule resources to fulfill the corresponding stochastic demands for various resources in geo-distributed data centers. In order to make full use of the advantages of cloud resources and tap the potential of private infrastructure, the optimal schedule plan should consider the heterogeneity of different kinds of data centers. It results in a highly complex non-linear programming problem. To find efficient solutions, we introduce a related and simple problem to quickly obtain a feasible solution close to optimal one, and then leverage a differential evolution process with special steps to solve it quickly. By testing the algorithm using simulated and realistic data, we find that our algorithm outperforms the existing algorithms and can increase the revenue by more than 34%.

The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.

Authors and Affiliations

1. Key Laboratory of Grain Information Processing, Control, Ministry of Education, Henan University of Technology, Zhengzhou, 450001, China

   Wei Wei, Qi Wang, Heyang Xu & Yang Liu

2. College of Information Science and Engineering, Henan University of Technology, Zhengzhou, 450001, China

   Wei Wei, Qi Wang, Heyang Xu & Yang Liu

Corresponding author

Correspondence to Wei Wei.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

National Natural and Science Foundation of China (61702162, 62006071, 61772173, 61973104, U1604151, 61803146), the Key Laboratory of Grain Information Processing and Control (Henan University of Technology), the Ministry of Education (KFJJ-2016-104), Science and technology project of science and technology department of Henan province (No.202102210148), Cultivation Programme for Young Backbone Teachers in Henan University of Technology (2012012), Young Backbone Teacher Training Program of Henan Higher Education (2018GGJS066), Plan For Scientific Innovation Talent of Henan University of Technology (2018RCJH07, 2018QNJH26), Doctor Foundation of Henan University of Technology (2017025), Natural Science Foundation of the Henan Province (152102210068), National Key Research and Development Program of China (2017YFD0401001), Program for Science and Technology Innovation Talents in Universities of Henan Province (19HASTIT027), Key Science and Technology Research Project of Education Department Henan Province (18A520026).

Appendix

1.1 Proof of Lemma 1

Proof

The local optimal condition is that the marginal revenue of unit cost equals for each resource in each region. Given \({\lim _{ {{\varDelta }^{r}_{a}} \to +0 }}({({\varsigma ^{r}_{a}})}^{-1}({c^{r}_{a}}+{{\varDelta }^{r}_{a}}) - {f}^{r}_{a}({c^{r}_{a}})) = {{\varDelta }^{r}_{a}}\hat {f^{\prime }}^{r}_{a}({c^{r}_{a}})\), then the increase revenue when \({c^{r}_{a}}\) increased to \({c^{r}_{a}}+{{\varDelta }^{r}_{a}}\) can be:

Where \(\mathcal {U}^{r} = {\sum }_{r=1}^{\mathcal {R}{{({\varsigma ^{r}_{a}})}^{-1}({c^{r}_{a}})}}\) in (2) (i.e., the reduction form of (1)), so the marginal revenue relates to both \({c^{r}_{a}}\) and \(c^{r}_{a^{\prime }} (a^{\prime } \neq a)\), and does not necessarily monotonically change according to \({c^{r}_{a}}\). There may be different cases of \({c^{r}_{a}} (1 \le r \le \mathcal {R}, 1 \le a \le \mathcal {A})\) that can get equal marginal revenue, so there will be multiple local optimal conditions for (??).

□

1.2 Proof of Lemma 3

Proof

Suppose Θ is the optimal solution to the all-resource problem in (??), but Θ^r is not the optimal solution to problem in (??). By replacing Θ^r to better \({\varTheta ^{r}}^{\prime }\), the new solution \(\varTheta ^{\prime }\) is a better solution than Θ, which contradicts with the premise that Θ is the optimal solution. □

1.3 Proof of Lemma 2

Proof

It is clear that if \({\mathcal {U}^{r}}^{\prime } < \mathcal {U}^{r}\) their maximal revenues \(\psi ^{r}({\mathcal {U}^{r}}^{\prime }) < \psi ^{r}(\mathcal {U}^{r})\). So for the solution vector ζ^r to (??), if it has \({\sum }_{a=1}^{\mathcal {A}}{ {{\varsigma ^{r}_{a}}} ({\zeta ^{r}_{a}}) } = \mathcal {C}^{r}\), then ζ^r is also a solution (not necessarily optimal) to (??), so it has \(\psi ^{r}(\mathcal {C}^{r}) > \psi ^{r}(\mathcal {U}^{r})\). Based on the above information, if the optimal solution of (??) has \({\sum }_{a=1}^{\mathcal {A}}{ \hat {{\varsigma ^{r}_{a}}}({c^{r}_{a}} ) } < \mathcal {U}^{r}\), the maximal revenue will be no more than \(\psi ^{r}(\mathcal {U}^{r})\), which contradicts with \(\psi ^{r}(\mathcal {C}^{r}) > \psi ^{r}(\mathcal {U}^{r})\) (\(\psi ^{r}(\mathcal {C}^{r})\) is the maximal revenue of (??)). The lemma is proved. □

1.4 Proof of Lemma 4

Proof

If CDF \({\mathscr{H}}^{r}_{(a,k)}(\cdot )\) is monotonically increasing, then the marginal revenue for each (a,r) \({\mu ^{r}_{a}}({\zeta ^{r}_{a}}) = {\sum }_{k=1}^{K}{ {\mathscr{H}}^{r}_{(a,k)}({\zeta ^{r}_{a}})}\) is monotonically decreasing. According to nonlinear optimization theory, the global optimal condition is that the marginal revenue equals with each other, i.e., \({\mu ^{r}_{a}}({\zeta ^{r}_{a}})\) is equal for each a. The lemma is proved. □

1.5 Proof of Lemma 5

Proof

Let divide all a s into two sets Φ₁ and Φ₂, where \(c^{r}_{a^{\prime }} >= \overline {{c^{r}_{a^{\prime }}}}\) for \({a^{\prime }} \in \varPhi _{1}\) and \(c^{r}_{a^{\prime \prime }} < \overline {c^{r}_{a^{\prime \prime }}}\) for \({a^{\prime \prime }} \in \varPhi _{2}\). Then according to Definition 1, it has \(\widetilde {c^{r}_{a^{\prime }}} <= c^{r}_{a^{\prime }} \quad \forall {a^{\prime }} \in \varPhi _{1} \) and \(\widetilde {c^{r}_{a^{\prime \prime }}} > c^{r}_{a^{\prime \prime }} \quad \forall {a^{\prime \prime }} \in \varPhi _{2}\). Let \(\overline {{p^{r}_{a}}}\) as the price at \(\overline {{c^{r}_{a}}}\) as, the average prices can be calculated as:

It is clear that \(\widetilde {p^{r}_{a^{\prime }}} \ge p^{r}_{a^{\prime }}\) and \(\widetilde {p^{r}_{a^{\prime \prime }}} \le p^{r}_{a^{\prime \prime }}\). The amount constraint of the near-optimal solution \(\overline {\mathcal {U}^{r}} \ge {\sum }_{a=1}^{J}{{\zeta ^{r}_{a}} } \) since c^r is below the lower bound, and it has:

Then, we can obtain \({\sum }_{a=1}^{\mathcal {A}}{({c^{r}_{a}} - \overline {{c^{r}_{a}}} ) / {p^{r}_{a}} } \le 0\), denote \(\overline {\varphi ^{r}}= {\overline {{c^{r}_{1}}}, \overline {{c^{r}_{2}}}, ..., \overline {c^{r}_{\mathcal {A}}}}\), for its reflection point \(\widetilde {{\varphi ^{r}}}= {\widetilde {{c^{r}_{1}}}, \widetilde {{c^{r}_{2}}}, ..., \widetilde {c^{r}_{\mathcal {A}}}}\), it has:

□

Reprints and permissions