Time-aware application task scheduling system

Abstract

A time-aware application task scheduling system for a green data center (GDC) that includes a task scheduling processor coupled to one or more queue processors and an energy collecting processor connected to one or more renewable energy sources and a grid power source. The systems is capable of determining a service rate for a plurality of servers to process a plurality of application tasks in the GDC and scheduling, via processing circuitry, one or more of the application tasks to be executed in one or more of the servers at a rate according to a difference in an accumulated arriving rate for the plurality of application tasks into the one or more queues and a removal rate for the plurality of application tasks from the one or more queues. The system is further capable of removing the one or more application tasks from their associated queues for execution in the scheduled one or more servers.

Claims

1. A time-aware application task scheduling system for a green data center (GDC), the GDC having a task scheduling processor coupled to one or more queue processors and an energy collecting processor connected to one or more renewable energy sources and a grid power source, wherein the task scheduling processor is configured to periodically receive energy data from the energy collecting processor, regarding available energy from renewable energy resources, wherein the resources of the renewable energy source are used first and then-when necessary, resources from the grid power source are used, and wherein the one or more queue processors are configured to receive a plurality of application tasks from a plurality of electronic devices into the one or more queue processors of the application task scheduling system, per application, of the GDC, the time-aware application task scheduling system, comprising: a plurality of servers configured to process the plurality of application tasks; and the task scheduling processor configured to: determine a task service rate for each of the plurality of servers to schedule the plurality of application tasks received from the plurality of electronic devices, each of said task service rate being determined according to a difference in an accumulated arriving rate for the plurality of application tasks in a respective time interval into the one or more queue processors and a removal rate for the plurality of application tasks in the respective time interval for removing immediately a batch of L(1−δ(λ.sub.τ.sup.na,μ.sub.τ.sup.n))λ.sub.τ.sup.na application tasks from their associated queue processors for execution in the scheduled one or more servers, the number of the application tasks scheduled being based on the determined task service rate for the plurality of servers and the accumulated arriving rate into the one or more queue processors using a particle swarm optimization technique and a simulated annealing technique that solves a formulated novel profit maximization problem for a GDC, the profit maximization problem is derived with an M/M/1/C.sub.n/∞ queueing system, the task service rate representing a rate at which the application tasks are removed from the one or more queue processors and executed, the task scheduling processor further configured to: initialize a random velocity and a random position for a plurality of representative application tasks in a cluster of application tasks representing an initial swarm for the service rate, determine an initial fitness level of each representative application task in the cluster of application tasks, the initial fitness level representing a profit of the green data center based on a total revenue of the GDC for the initial swarm, an energy cost of the GDC, and a penalty associated with violated constraints, determine an initial optimum position of each representative application task and an initial optimum position of the cluster of application tasks, the position of each of the application tasks, which is represented by a particle, contains decision variables including μ.sub.τ.sup.n and {tilde over (μ)}.sub.τ+b.sup.n, initialize one or more predetermined task scheduling parameters associated with the particle swarm optimization technique, update a velocity and a position of each representative application task based upon the initialized task scheduling parameters using a Metropolis acceptance criterion, and based upon the initialized task scheduling parameters associated with the chaotic system, wherein said updating includes, for each said application task, if a new position of the application task is better than a current position thereof, the new position is accepted, otherwise, the new position is conditionally accepted only if the Metropolis acceptance criterion is met, calculate a current fitness level of each representative application task in a current cluster of application tasks, update a current optimum position of each representative application task and a current optimum position of the cluster of application tasks, decrease a temperature by a temperature cooling rate of each representative application task and an inertia weight of each representative application task from an upper bound inertia weight to a lower bound inertia weight, calculate a chaotic search parameter for an iteration in a chaotic system, the chaotic search parameter being distributed between zero and one, update the velocity and the position of each representative application task based in part upon the chaotic search parameter, and determine the task service rate for the plurality of servers based on the updated velocity and the updated position of each representative application task, the updated position including μ.sub.τ.sup.n and {tilde over (μ)}.sub.τ+b.sup.n, schedule, via the task scheduling processor, one or more of the plurality of application tasks to be executed in one or more of the plurality of servers at a rate determined according to a difference in an accumulated arriving rate for the one or more application tasks into the one or more queue processors and a removal rate for the one or more application tasks from the one or more queue processors, the number of the one or more application tasks scheduled being based on the determined task service rate for the plurality of servers and the accumulated arriving rate for the plurality of application tasks into the one or more queue processors, and a batch of L(1−δ(λ.sub.τ.sup.na,μ.sub.τ.sup.n))λ.sub.τ.sup.na tasks being immediately scheduled and executed in plurality of servers in the GDC; and remove immediately the batch of L(1−δ(λ.sub.τ.sup.na,μ.sub.τ.sup.n))λ.sub.τ.sup.na application tasks from their associated queue processors for execution in the scheduled one or more servers, wherein the one or more application tasks are scheduled to maximize a profit in the GDC while guaranteeing delay constraints of each application, wherein each application task is constrained by the following equations: $\begin{array}{cc}{\Lambda }_{\tau -B_n-1}^n+{\lambda }_{\tau -B_n}^{n}L\le D_{\tau -1}^n+\left({\lambda }_{\tau }^{\mathrm{na}}\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right)L\right)& \left(5\right)\end{array}$ $\begin{array}{cc}{\Lambda }_{\tau -B_n-1}^n+\underset{u=\tau -B_n}{\overset{\tau -B_n+b}{.Math.}}\left({\lambda }_u^{n}L\right)\le D_{\tau -1}^n+\left({\lambda }_{\tau }^{\mathrm{na}}\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right)L\right)+\underset{u=\tau +1}{\overset{\tau +b}{.Math.}}\left({\tilde{\lambda }}_u^{\mathrm{na}}\left(1-\delta \left({\tilde{\lambda }}_u^{\mathrm{na}},{\tilde{\mu }}_u^n\right)\right)L\right),1\le b\le B_n,\mathrm{and}& \left(6\right)\end{array}$ $\begin{array}{cc}{\Lambda }_{\tau -B_n-1}^n+\underset{u=\tau -B_n}{\overset{\tau }{.Math.}}.Math.\left({\lambda }_u^{n}L\right)=D_{\tau -1}^n+\left({\lambda }_{\tau }^{\mathrm{na}}\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right)L\right)+\underset{u=\tau +1}{\overset{\tau +B_n}{.Math.}}\left({\tilde{\lambda }}_u^{\mathrm{na}}\left(1-\delta \left({\tilde{\lambda }}_u^{\mathrm{na}},{\tilde{\mu }}_u^n\right)\right)L\right),& \left(9\right)\end{array}$ where Λ.sub.τ.sup.n is the number of already-arrived tasks, B.sub.n is the delay constraint, μ.sub.τ.sup.n is the arriving rate of its task in a time interval τ, L is length of each interval, D.sub.τ.sup.n is number of tasks scheduled in τ intervals, λ.sub.τ.sup.na is the accumulated arriving rate of tasks of application n in interval τ, μ.sub.τ.sup.n is the rate at which tasks of application n are removed from the queue, δ(λ.sub.τ.sup.na,μ.sub.τ.sup.n) is the loss possibility of tasks of application n in interval τ, and b is a time interval (1≤b≤B.sub.n), wherein the servers associated with each said application task are homogeneous, and wherein the servers across the application tasks are heterogeneous.

2. The task scheduling system of claim 1, further comprising: an energy collecting processor having circuitry configured to forward resource data from a grid power source and from the one or more renewable power sources to the plurality of servers and to a task scheduling processor.

3. The task scheduling system of claim 2, wherein the L(1−δ(λ.sub.τ.sup.na,μ.sub.τ.sup.n))λ.sub.τ.sup.na task scheduling processor has circuitry configured to receive data from the one or more queue processors and from the energy collecting processor to determine the task service rate, μ.sub.τ.sup.n of each of the servers, and a batch of tasks are immediately scheduled and executed in servers in GDC.

4. The task scheduling system of claim 2, wherein the resource data includes one or more of a price of the grid power source, a solar irradiance, a wind speed, an on-site air density, and an average idle peak power for each of the servers.

5. The task scheduling system of claim 1, wherein the processing circuitry is further configured to solve the formulated novel profit maximization problem for a GDC, the problem is derived with an M/M/1/C.sub.n/∞ queueing system, calculate a task service rate for one of the application tasks to execute in a time interval within the task scheduling system, wherein a batch of L(1−δ(λ.sub.τ.sup.na,μ.sub.τ.sup.n))λ.sub.τ.sup.na tasks are immediately scheduled and executed in the servers in the GDC in an individual time interval; and update the data task variables for all executed tasks.

6. The task scheduling system of claim 1, wherein determining the task service rate includes a combination of hybrid chaotic particle swarm optimization based on simulated annealing, where the chaotic search parameter is used in the update of velocity of each particle.

7. The task scheduling system of claim 1, wherein the chaotic search parameter, which is used to update the velocity of each particle, includes a stochastic pattern in the chaotic system.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) A more complete appreciation of the disclosure and many of the attendant advantages thereof will be readily obtained as the same becomes better understood by reference to the following detailed description when considered in connection with the accompanying drawings, wherein:

(2) FIG. 1 is a block diagram of an exemplary green data center (GDC) according to one embodiment;

(3) FIG. 2 is a graph illustrating arriving rates for application tasks of type 1, type 2, and type 3 according to one embodiment;

(4) FIG. 3 is a graph illustrating real-life price of grid data over a 24-hour adopted period according to one embodiment;

(5) FIG. 4 is a graph illustrating solar irradiance over the 24-hour adopted period according to one embodiment;

(6) FIG. 5 is a graph illustrating wind speed over the 24-hour adopted period according to one embodiment;

(7) FIG. 6 is a graph illustrating experimental results for a profit and penalty of the GDC according to one embodiment;

(8) FIG. 7 is a graph illustrating energy from grid, wind, and solar sources according to one embodiment;

(9) FIG. 8A is a graph illustrating cumulative and remaining tasks of application type 1 according to one embodiment;

(10) FIG. 8B is a graph illustrating cumulative and remaining tasks of application type 2 according to one embodiment;

(11) FIG. 8C is a graph illustrating cumulative and remaining tasks of application type 3 according to one embodiment;

(12) FIG. 9A is a graph illustrating cumulative arriving tasks (CATs) and cumulative scheduled tasks (CSTs) corresponding to application type 1 according to one embodiment;

(13) FIG. 9B is a graph illustrating CATs and CSTs corresponding to application type 2 according to one embodiment;

(14) FIG. 9C is a graph illustrating CATs and CSTs corresponding to application type 3 according to one embodiment;

(15) FIG. 10A is a graph illustrating TATS and benchmark Algorithms 1-3 corresponding to application type 1 according to one embodiment;

(16) FIG. 10B is a graph illustrating TATS and benchmark Algorithms 1-3 corresponding to application type 2 according to one embodiment;

(17) FIG. 10C is a graph illustrating TATS and benchmark Algorithms 1-3 corresponding to application type 3 according to one embodiment;

(18) FIG. 11 is a graph illustrating cumulative total profits for TATS that were compared with each of Algorithm 1, Algorithm 2, and Algorithm 3 according to one embodiment;

(19) FIG. 12 is a schematic of an exemplary computing device according to one embodiment;

(20) FIG. 13 illustrates an exemplary cloud computing system according to one embodiment; and

(21) FIGS. 14A-14B are flowcharts illustrating an exemplary method of scheduling tasks according to one embodiment.

DETAILED DESCRIPTION

(22) The following descriptions are meant to further clarify the present disclosure by giving specific examples and embodiments of the disclosure. These embodiments are meant to be illustrative rather than exhaustive. The full scope of the disclosure is not limited to any particular embodiment disclosed in this specification, but rather is defined by the claims.

(23) It will be appreciated that in the development of any such actual implementation, numerous implementation-specific decisions need to be made in order to achieve the developer's specific goals, such as compliance with application- and business-related constraints, and that these specific goals will vary from one implementation to another and from one developer to another.

(24) Embodiments described herein meet delay constraints of tasks of each application by proposing a Time-Aware Task Scheduling (TATS) algorithm. It can achieve profit maximization for a GDC by smartly scheduling arriving tasks to execute within their delay bounds. Embodiments described herein differ from existing studies in that TATS can guarantee the delay bound of each admitted task in a GDC. Embodiments described herein can achieve profit maximization for a GDC provider by considering the temporal variation for revenue, price of the grid, and the green energy in delay bounds of various tasks. Tasks of each application are put into a separate queue, such as a FCFS queue. The associated delay bound constraints are guaranteed. Embodiments also provide a mathematical modeling of task refusal and service rates of tasks. In addition, temporal task scheduling is provided by hybrid chaotic Particle Swarm Optimization (PSO) based on simulated-annealing algorithm.

(25) The profit maximization problem for a GDC is formulated and implemented with a hybrid meta-heuristic algorithm. The delay constraint of each admitted task corresponding to each application can be strictly met by scheduling all admitted tasks to execute within their delay bounds.

(26) Simulation results with real-time data, such as tasks in Google cluster, virtual machine (VM) execution prices, price of a grid, solar irradiance, and wind speed are conducted to evaluate the proposed TATS. See M. Dabbagh, B. Hamdaoui, M. Guizani, and A. Rayes, “Energy-efficient resource allocation and provisioning framework for cloud data centers,” IEEE Transactions on Network and Service Management, vol. 12, no. 3, pp. 377-391, September 2015; NYISO. Extensive simulations demonstrate that it performs better than several typical scheduling algorithms with respect to profit and throughput.

(27) An exemplary GDC 100 used herein is illustrated in FIG. 1. A cloud provider manages the GDC 100 and provides multiple types of application services to users around the world. Tasks from users can be sent through multiple types of electronic devices 110, such as smart phones, computers, servers, and laptops.

(28) Tasks arriving from the electronic devices 110 can be processed on a First-Come-First-Served (FCFS) policy, for example. Tasks of each application are enqueued into a queue processor 120a-c, such as a FCFS queue processor. The information of all queue processors 120 is sent to a task scheduling processor 130.

(29) The GDC 100 can acquire electricity from multiple types of power suppliers. Three energy suppliers are illustrated, which include a grid power source 141, a solar power renewable source 142, and a wind power renewable source 143. However, other power sources and other renewable power sources are contemplated by embodiments described herein.

(30) The information about the grid power source 141, the solar power renewable source 142, and the wind power renewable source 143 primarily includes the price of the power grid, the solar irradiance, the wind speed, on-site air density, the average idle (peak) power of each server, etc. The information is collected, via an energy collecting processor 150, which is periodically reported to the task scheduling processor 130.

(31) The task is formulated into a constrained optimization problem, as described in more detail herein. The task is solved by a Hybrid Chaotic PSO, based on Simulated-annealing (HCPS) in each iteration of TATS. Based on the optimal solutions obtained by HCPS, time-aware scheduling of multi-application tasks is realized to achieve profit maximization for the GDC 100, while delay bounds of all tasks are strictly guaranteed.

(32) The task scheduling processor 130 is considered where TATS is executed. Based on the scheduling strategy specified by TATS, the task scheduling processor 130 can determine the service rates of servers 160 corresponding to each application in each interval, while respecting the corresponding delay bounds of each application.

(33) The setting information of servers 160 is sent to a resource provisioning processor 170, which configures the servers 160 in the GDC 100. It can be assumed that the servers 160 of each application are homogeneous, while servers 160 corresponding to different applications are heterogeneous in hardware. TATS runs to maximize the profit of GDC providers, while the user-specified delay constraint of each admitted task of each application is guaranteed.

(34) Arriving tasks of each application are enqueued into their corresponding queue processor 120. Let B.sub.n denote the delay bound of tasks of application n. For each application n, TATS can ensure that by each interval τ, all tasks arriving in interval τ-B.sub.n or before must be scheduled to the GDC 100. TATS is inclined to schedule remaining tasks that arrive earlier in each queue processor 120. Therefore, remaining tasks arriving in interval τ-B.sub.n are first executed in the GDC 100 by interval τ. In this way, delay constraints of all arriving tasks are strictly guaranteed.

(35) TATS also considers the temporal variation in the revenue, price of the power grid, and renewable energy sources in the delay bounds of tasks. As a result, TATS integrates the temporal variation into a constrained optimization problem, which is solved by HCPS. Therefore, TATS can intelligently schedule arriving tasks to execute in the GDC 100 and achieve profit maximization for GDC providers.

(36) FIG. 1 illustrates GDC 100. Similar to Bi et al., the GDC 100 is modeled as a system having discrete intervals. See J. Bi, H. Yuan, W. Tan, M. C. Zhou, Y. Fan, J. Zhang, and J. Li, “Application-aware dynamic fine-grained resource provisioning in a virtualized cloud data center,” to appear in IEEE Transactions on Automation Science and Engineering, doi: 10.1109/TASE.2015.2503325, 2016, incorporated herein by reference in its entirety.

(37) High-configuration servers are growingly deployed in current GDCs. Similar to Yuan et al., it is reasonable to assume that a single task of each application can be executed completely in an interval. In FIG. 1, tasks of each application are put into their corresponding queue processor 120.

(38) The following notations are used herein to develop a delay constraint. For application n, let λ.sub.τ.sup.n denote the arriving rate of its tasks in time interval τ. In addition, task service rates in intervals τ and τ+b (1≤b≤B.sub.n) are denoted by μ.sub.τ.sup.n and μ.sub.τ+b.sup.n, respectively. For example, let μ.sub.τ.sup.n denote the rate at which tasks of application n are removed from their corresponding queue processor 120, and executed in the GDC 100 in interval τ. For application n, the number of its tasks accumulated during t intervals is denoted by Λ.sub.τ.sup.n. Similarly, the number of tasks scheduled in τ intervals is denoted by D.sub.τ.sup.n. Let L denote the length of each interval. The number of tasks accumulated during τ intervals can be expressed as follows.

(39) $\begin{array}{cc}{\Lambda }_{\tau }^n=\underset{i=1}{\overset{\tau }{.Math.}}{\lambda }_i^{n}L& \left(1\right)\end{array}$$\begin{array}{cc}{D}_{\tau }^n=\underset{i=1}{\overset{\tau }{.Math.}}{\lambda }_i^{\mathrm{na}}\left(1-\delta \left({\lambda }_i^{\mathrm{na}},{\mu }_i^n\right)\right)L& \left(2\right)\end{array}$

(40) In Equation (2), the accumulated arriving rate of tasks of application n in interval τ is denoted by λ.sub.τ.sup.na. The remaining arriving rate of tasks of application n in interval τ is denoted by λ.sub.τ.sup.na. In addition, the proposed TATS can satisfy the delay constraint B.sub.n of tasks of application n. Therefore, all tasks of application n that arrive in interval τ−B or before need to be scheduled and executed in the GDC 100, which leads to λ.sub.i.sup.nr=0(i≤τ−B.sub.n−1). As a result, λ.sub.τ.sup.na can be obtained as follows in Equation (3).

(41) $\begin{array}{cc}{\lambda }_{\tau }^{\mathrm{na}}={\lambda }_{\tau }^n+\underset{i=\tau -B_n}{\overset{\tau -1}{.Math.}}{\lambda }_i^{\mathrm{nr}}& \left(3\right)\end{array}$

(42) In Equation (2), the loss possibility of tasks of application n in interval τ in the GDC 100 is denoted by δ(λ.sub.τ.sup.na,μ.sub.τ.sup.n). Similar to Zhu et al., servers 160 corresponding to each application n in the GDC 100 are modeled as an M/M/1/C.sub.n/∞ queueing system. See Z. Zhu, J. Bi, H. Yuan, and Y. Chen, “SLA based dynamic virtualized resources provisioning for shared cloud data centers,” in Proc. 2011 IEEE International Conference on Cloud Computing, 2011, pp. 630-637, incorporated herein by reference in its entirety. The task capacity of servers 160 of application n in the GDC 100 is C.sub.n in total. The loss possibility of tasks of application n in interval t in the GDC 100 can be expressed as follows.

(43) $\begin{array}{cc}\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)=\{\begin{array}{cc}\frac{1-\frac{{\lambda }_{\tau }^{\mathrm{na}}}{{\mu }_{\tau }^n}}{1-{\left(\frac{{\lambda }_{\tau }^{\mathrm{na}}}{{\mu }_{\tau }^n}\right)}^{C_n+1}}{\left(\frac{{\lambda }_{\tau }^{\mathrm{na}}}{{\mu }_{\tau }^n}\right)}^{C_n}& {\mu }_{\tau }^n>0,\\ 1& {\mu }_{\tau }^n=0.\end{array}& \left(4\right)\end{array}$

(44) Tasks of application n need to be scheduled and executed in the GDC 100 in their delay bound B.sub.n. Therefore, for application n, all its tasks arriving in interval τ need to be scheduled and executed from τ to τ+B.sub.n. For application n, all its tasks in interval τ-B.sub.n or before need to be scheduled and executed by interval τ, which can be expressed as follows.

(45) $\begin{array}{cc}{\Lambda }_{r-B_n-1}^n+{\lambda }_{r-B_n}^{n}L\le D_{r-1}^n+\left({\lambda }_r^{\mathrm{na}}\left(1-\delta \left({\lambda }_r^{\mathrm{na}},{\mu }_r^n\right)\right)L\right)& \left(5\right)\end{array}$

(46) In each interval τ, let {tilde over (λ)}.sub.u.sup.na denote the accumulated arriving rate of tasks of application n predicted in interval u (τ+1≤u≤τ+B.sub.n). Similarly, in each interval τ, let {tilde over (μ)}.sub.u.sup.n denote the task service rate of application n predicted in interval u (τ+1≤u≤τ+B.sub.n). Note that {tilde over (λ)}.sub.u.sup.na can be predicted by existing prediction algorithms, such as neural networks and robust regression. At the start of interval τ, {tilde over (λ)}.sub.u.sup.na is set to λ.sub.u.sup.n, i.e., {tilde over (λ)}.sub.u.sup.na=λ.sub.u.sup.n(τ+1≤u≤τ+B.sub.n). The decision variables of {tilde over (μ)}.sub.u.sup.n are determined by TATS. All application tasks of n in τ+b−B.sub.n or before are scheduled and executed by interval τ+b, which can be expressed as follows.

(47) $\begin{array}{cc}{\Lambda }_{\tau -B_n-1}^n+\underset{u=\tau -B_n}{\overset{\tau -B_n+b}{.Math.}}\left({\lambda }_u^{n}L\right)\le D_{\tau -1}^n+\left({\lambda }_{\tau }^{\mathrm{na}}\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right)L\right)+\underset{u=\tau +1}{\overset{\tau +b}{.Math.}}\left({\tilde{\lambda }}_u^{\mathrm{na}}\left(1-\delta \left({\tilde{\lambda }}_u^{\mathrm{na}},{\tilde{\mu }}_u^n\right)\right)L\right),1\le b\le B_n& \left(6\right)\end{array}$

(48) In addition, at the start of interval τ for application n, the number of its already-arrived tasks, Λ.sub.τ.sup.n, is obtained. Therefore, the number of tasks that have already arrived can be expressed as follows.

(49) $\begin{array}{cc}{\Lambda }_{\tau }^n={\Lambda }_{\tau -B_n-1}^n+\underset{u=\tau -B_n}{\overset{\tau }{.Math.}}\left({\lambda }_u^{n}L\right)& \left(7\right)\end{array}$

(50) For application n, the delay constraint of its arriving tasks in interval τ is satisfied if they are executed from interval τ to τ+B.sub.n. Therefore, at the start of interval τ, the number of tasks of application n that are scheduled in interval τ is λ.sub.τ.sup.na(1−δ(λ.sub.τ.sup.na,μ.sub.τ.sup.n))L. At the start of interval τ, the expected number of tasks of application n scheduled in interval τ+b(1≤b≤B.sub.n) is ({tilde over (λ)}.sub.u.sup.na(1−δ({tilde over (λ)}.sub.u.sup.na,μ.sub.u.sup.n)) L). Therefore, for application n in interval τ, the predicted number of its tasks executed by τ+B.sub.n can be expressed as follows.

(51) $\begin{array}{cc}{D}_{\tau +B_n}^n=D_{\tau -1}^n+\left({\lambda }_{\tau }^{\mathrm{na}}\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right)L\right)+\underset{u=\tau +1}{\overset{\tau +B_n}{.Math.}}\left({\tilde{\lambda }}_u^{\mathrm{na}}\left(1-\delta \left({\tilde{\lambda }}_u^{\mathrm{na}},{\tilde{\mu }}_u^n\right)\right)L\right)& \left(8\right)\end{array}$

(52) As a result, owing to the conservation of tasks of each application n, Λ.sub.τ.sup.n should equal D.sub.τ+B.sub.n.sup.n, i.e., Λ.sub.τ.sup.n=D.sub.τ+B.sub.n.sup.n which is expressed as follows.

(53) $\begin{array}{cc}{\Lambda }_{\tau -B_n-1}^n+\underset{u=\tau -B_n}{\overset{\tau }{.Math.}}\left({\lambda }_u^{n}L\right)=D_{\tau -1}^n+\left({\lambda }_{\tau }^{\mathrm{na}}\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right)L\right)+\underset{u=\tau +1}{\overset{\tau +B_n}{.Math.}}\left({\tilde{\lambda }}_u^{\mathrm{na}}\left(1-\delta \left({\tilde{\lambda }}_u^{\mathrm{na}},{\tilde{\mu }}_u^n\right)\right)L\right)& \left(9\right)\end{array}$

(54) Hence, meeting constraints (5), (6), and (9) can guarantee the delay constraint of tasks of application n will be met.

(55) A power consumption model used in the GDC 100 is described herein. In this model, it is assumed that servers 160 corresponding to each application n in the GDC 100 are homogeneous in terms of configuration. Therefore, the energy consumption profiles of servers 160 corresponding to the same application are the same. Each switched-on server 160 of application n can execute σ.sub.n tasks of application n per minute. m.sub.τ.sup.n denotes the number of switched-on servers 160 of application n in the GDC 100 in interval τ. Therefore, the service rates of servers 160 in interval an be calculated as follows.

(56) $\begin{array}{cc}{\mu }_{\tau }^n={\sigma }_n{m}_{\tau }^n& \left(10\right)\end{array}$

(57) For application n, its corresponding available number of physical servers 160 is denoted by Ω.sub.n. Let τ=max.sub.n∈{1,2, . . . ,N}(B.sub.n). Therefore, for application n, the total number of switched-on servers 160 in interval τ+b, denoted by m.sub.τ+b.sup.n, needs to be no more than Ω.sub.n, which is expressed as follows.

(58) 0$\begin{array}{cc}{m}_{\tau +b}^n\le {\Omega }_n,0\le b\le \daleth & \left(11\right)\end{array}$

(59) The total power of the GDC 100 can be obtained by adding the power consumed by the facilities (e.g., lighting and cooling) to the power of servers 160 of all applications. For the GDC 100, the power usage effectiveness (PUE) can be obtained by calculating the ratio of power usage of the GDC 100 to the total power of its servers 160. See A. N. Toosi, K. Vanmechelen, F. Khodadadi, and R. Buyya, “An auction mechanism for cloud spot markets,” ACM Trans. Auton. Adapt. Syst, vol. 11, no. 1, pp. 2:1-2:33, April 2016, incorporated herein by reference in its entirety. PUE is an important metric to qualify a GDC's energy efficiency. Let γ denote the PUE of the GDC 100. γ of many current data centers is typically 1.2-2.0. See A. Beloglazov, J. Abawajy, and R. Buyya, “Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing,” Future Generation Computer Systems, vol. 28, no. 5, pp. 755-768, May 2012, incorporated herein by reference in its entirety.

(60) The average idle power of each server 160 of application n is denoted by P.sub.0.sup.n. The average peak power of each server 160 of application n when it is executing corresponding tasks is denoted by P.sub.1.sup.n. In addition, let u.sub.τ.sup.n denote the CPU utilization of servers 160 of application n in the GDC 100 in interval τ. Therefore, the total power usage of the GDC 100 in interval τ is obtained in Equation (12) as follows:

(61) $\begin{array}{cc}{P}_{\tau }=\underset{n=1}{\overset{N}{.Math.}}\left(m_{\tau }^n\left({\stackrel{\_}{P}}_0^n+\left(\gamma -1\right){\stackrel{\_}{P}}_1^n+\left({\stackrel{\_}{P}}_1^n-{\stackrel{\_}{P}}_0^n\right)u_{\tau }^n\right)\right)& \left(12\right)\end{array}$
See A. Qureshi, R. Weber, H. Balakrishnan, J. Guttag, and B. Maggs, “Cutting the electric bill for internet-scale systems,” SIGCOMM Comput. Commun. Rev, vol. 39, no. 4, pp. 123-134, August 2009, incorporated herein by reference in its entirety.

(62) For the loss possibility δ(λ.sub.τ.sup.na,μ.sub.τ.sup.n), the number of tasks of application n that each corresponding switched-on server 160 can execute in interval τ is expressed as follows.

(63) $\begin{array}{cc}\frac{L\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right){\lambda }_{\tau }^{\mathrm{na}}}{m_{\tau }^n}& \left(13\right)\end{array}$

(64) The busy time of each switched-on server 160 of application n is

(65) $\frac{L\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right){\lambda }_{\tau }^{\mathrm{na}}}{{\sigma }_n{m}_{\tau }^n}$
minutes. Therefore, μ.sub.τ.sup.na is calculated as follows.

(66) $\begin{array}{cc}{u}_{\tau }^n=\frac{\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right){\lambda }_{\tau }^{\mathrm{na}}}{{\sigma }_n{m}_{\tau }^n}& \left(14\right)\end{array}$

(67) Based on (10), (12), and (14), the total energy of the GDC 100 in interval τ, E.sub.τ, is obtained as follows.

(68) $\begin{array}{cc}{E}_{\tau }=\underset{n=1}{\overset{N}{.Math.}}\left(\frac{g_n{\mu }_{\tau }^n+h_n{\lambda }_{\tau }^{\mathrm{na}}\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right)}{{\sigma }_n}L\right)\mathrm{where}& \left(15\right)\end{array}$$\begin{array}{cc}{g}_n\stackrel{\Delta }{=}{P}_0^n+\left(\gamma -1\right)P_1^n& \left(16\right)\end{array}$$\begin{array}{cc}{h}_n\stackrel{\Delta }{=}{P}_1^n-P_0^n& \left(17\right)\end{array}$

(69) The maximum amount of available energy in the GDC 100 in each interval τs denoted by ω. Therefore, the total energy consumption of the GDC 100 in intervals τ or τ+b (1≤b≤τ) is no greater than ω, which is expressed as follows.

(70) $\begin{array}{cc}\underset{n=1}{\overset{N}{.Math.}}\left(\frac{g_n{\mu }_{\tau }^n+h_n{\lambda }_{\tau }^{\mathrm{na}}\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right)}{{\sigma }_n}L\right)\le \stackrel{\_}{\omega }& \left(18\right)\end{array}$$\begin{array}{cc}\underset{n=1}{\overset{N}{.Math.}}\left(\frac{g_n{\tilde{\mu }}_{\tau +b}^n+h_n{\tilde{\lambda }}_{\tau +b}^{\mathrm{na}}\left(1-\delta \left({\tilde{\lambda }}_{\tau +b}^{\mathrm{na}},{\tilde{\mu }}_{\tau +b}^n\right)\right)}{{\sigma }_n}L\right)\le \stackrel{\_}{\omega },1\le b\le \daleth & \left(19\right)\end{array}$

(71) In a conventional system, green energy generators (e.g., solar panels) are installed in a GDC. The power grid energy of a conventional GDC can be minimized when green energy is used.

(72) Two types of green energy sources are considered herein in developing a green power model. Since the length of an interval is small enough, it can be assumed that green energy remains unchanged within a single slot.

(73) The amount of energy produced by the solar source in interval τ is denoted by E.sub.τ.sup.s. The conversion rate of solar radiation to electricity is denoted by ψ. Let I.sub.τ denote the solar irradiance in interval τ. For solar panels, their active irradiation area is denoted by κ. Using the solar energy model, E.sub.τ.sup.s can be obtained as follows.

(74) $\begin{array}{cc}{E}_{\tau }^s=\mathrm{\kappa \psi }\left(I_{\tau }\right)L& \left(20\right)\end{array}$
See M. F. Hsieh, F. S. Hsu, and D. G. Dorrell, “Winding changeover permanent-magnet generators for renewable energy applications,” IEEE Transactions on Magnetics, vol. 48, no. 11, pp. 4168-4171, November 2012, incorporated herein by reference in its entirety.

(75) Similarly, E.sub.τ.sup.ω denotes the amount of energy generated by wind in interval τ. The rate at which wind is converted to electricity is denoted by η. The on-site air density is denoted by ρ. Let ζ denote the rotor area of wind turbines. Let ν.sub.r denote the wind speed. Using the wind energy model of Hsieh et al., E.sub.τ.sup.ω can be obtained as follows.

(76) $\begin{array}{cc}{E}_{\tau }^w=\frac{1}{2}{\mathrm{\eta \rho \zeta }\left(v_{\tau }\right)}^{3}L& \left(21\right)\end{array}$

(77) Developing a constrained optimization problem is discussed herein. Let {tilde over (δ)}.sub.τ.sup.n and {tilde over (δ)}.sub.τ+b.sup.n denote the revenue of tasks of application n in intervals τ and τ+b, respectively. In order to guarantee the performance for users' tasks, the service level agreement (SLA) is conventionally specified between users and a GDC. Let θ.sub.τ.sup.n denote the payment brought by the execution of each task of application n in interval τ. The penalty paid by the GDC due to the refusal of each task of application n in interval τ is denoted by ν.sub.τ.sup.n. Therefore, {tilde over (δ)}.sub.τ.sup.n and {tilde over (∂)}.sub.τ+b.sup.n can be obtained as follows.

(78) $\begin{array}{cc}{\partial }_{\tau }^n=\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right){\lambda }_{\tau }^{\mathrm{na}}{\theta }_{\tau }^n-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right){\lambda }_{\tau }^{\mathrm{na}}{\vartheta }_{\tau }^n& \left(22\right)\end{array}$$\begin{array}{cc}{\tilde{\partial }}_{\tau +b}^n=\left(1-\delta \left({\tilde{\lambda }}_{\tau +b}^{\mathrm{na}},{\tilde{\mu }}_{\tau +b}^n\right)\right){\tilde{\lambda }}_{\tau +b}^{\mathrm{na}}{\theta }_{\tau }^n-\delta \left({\tilde{\lambda }}_{\tau +b}^{\mathrm{na}},{\tilde{\mu }}_{\tau +b}^n\right){\tilde{\lambda }}_{\tau +b}^{\mathrm{na}}{\vartheta }_{\tau }^n& \left(23\right)\end{array}$

(79) Let f.sub.1 denote the total revenue of the GDC brought by tasks of all applications from interval τ to τ+b. As a result, f.sub.1 can be obtained as follows.

(80) 0$\begin{array}{cc}{f}_1=\underset{n=1}{\overset{N}{.Math.}}\left({\partial }_{\tau }^n+\underset{b=1}{\overset{B_n}{.Math.}}{\tilde{\partial }}_{\tau +b}^n\right)& \left(24\right)\end{array}$

(81) The grid energy price in intervals τ and τ+b are denoted by ρ.sub.τ and {tilde over (ρ)}.sub.τ+b, respectively. It is assumed that the grid energy price remains unchanged in each interval and can vary from interval to interval. In addition, the amount of grid energy for the GDC in interval τ is calculated as max(E.sub.τ−E.sub.τ.sup.s−E.sub.τ.sup.ω, 0). The amount of grid energy of the GDC consumed in interval τ+b is obtained as max({tilde over (E)}.sub.τ+b−{tilde over (E)}.sub.τ+b.sup.s−{tilde over (E)}.sub.τ+b.sup.ω, 0). Let f.sub.2 denote the grid energy cost of the GDC from intervals τ to τ+1 which is expressed as follows.

(82) $\begin{array}{cc}{f}_2=p_{\tau }\left(\max \left(E_{\tau }-E_{\tau }^s-E_{\tau }^w,0\right)\right)+\underset{b=1}{\overset{\daleth }{.Math.}}\left({\tilde{p}}_{\tau +b}\left(\max \left({\tilde{E}}_{\tau +b}-{\tilde{E}}_{\tau +b}^s-{\tilde{E}}_{\tau +b}^w,0\right)\right)\right)& \left(25\right)\end{array}$

(83) Based on (1)-(25), the Profit Maximization Problem (P.sub.1) for the GDC 100 according to embodiments described herein can be given as follows.

(84) $\begin{array}{cc}\underset{{\mu }_{\tau }^n,{\tilde{\mu }}_{\tau +b}^n}{\mathrm{Max}}\left\{f_1-f_2\right\}& \end{array}$$\begin{array}{cc}\mathrm{subject}\mathrm{to}& \end{array}$$\begin{array}{cc}.Math.m_{\tau +b}^n\le {\Omega }_n,0\le b\le \daleth & \left(26\right)\end{array}$$\begin{array}{cc}\underset{n=1}{\overset{N}{.Math.}}\left(\frac{g_n{\mu }_{\tau }^n+h_n{\lambda }_{\tau }^{\mathrm{na}}\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right)}{{\sigma }_n}L\right)\le \stackrel{\_}{\omega }& \left(27\right)\end{array}$$\begin{array}{cc}\underset{n=1}{\overset{N}{.Math.}}\left(\frac{g_n{\stackrel{\_}{\mu }}_{\tau +b}^n+h_n{\stackrel{\_}{\lambda }}_{\tau +b}^{\mathrm{na}}\left(1-\delta \left({\hat{\lambda }}_{\tau +b}^{\mathrm{na}},{\hat{\mu }}_{\tau +b}^n\right)\right)}{{\sigma }_n}L\right)\le \stackrel{\_}{\omega },1\le b\le \daleth & \left(28\right)\end{array}$$\begin{array}{cc}{\Lambda }_{\tau -B_n-1}^n+{\lambda }_{\tau -B_n}^{n}L\le D_{\tau -1}^n+\left({\lambda }_{\tau }^{\mathrm{na}}\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right)L\right)& \left(29\right)\end{array}$$\begin{array}{cc}{\Lambda }_{\tau -B_n-1}^n+\underset{u=\tau -B_n}{\overset{\tau -B_n+b}{.Math.}}\left({\lambda }_u^{n}L\right)\le D_{\tau -1}^n+\left({\lambda }_{\tau }^{\mathrm{na}}\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right)L\right)+\underset{u=\tau +1}{\overset{\tau +b}{.Math.}}\left({\tilde{\lambda }}_u^{\mathrm{na}}\left(1-\delta \left({\tilde{\lambda }}_u^{\mathrm{na}},{\tilde{\mu }}_u^n\right)\right)L\right),1\le b\le B_n& \left(30\right)\end{array}$$\begin{array}{cc}{\Lambda }_{\tau -B_n-1}^n+\underset{u=\tau -B_n}{\overset{\tau }{.Math.}}\left({\lambda }_u^{n}L\right)=D_{\tau -1}^n+\left({\lambda }_{\tau }^{\mathrm{na}}\left(1-\delta \left({\lambda }_{\tau }^{\mathrm{na}},{\mu }_{\tau }^n\right)\right)L\right)+\underset{u=\tau +1}{\overset{\tau +B_n}{.Math.}}\left({\tilde{\lambda }}_u^{\mathrm{na}}\left(1-\delta \left({\tilde{\lambda }}_u^{\mathrm{na}},{\tilde{\mu }}_u^n\right)\right)L\right)& \left(31\right)\end{array}$$\begin{array}{cc}{\mu }_{\tau }^n>0,{\stackrel{\_}{\mu }}_{\tau +b}^n>0,1\le b\le B_n& \left(32\right)\end{array}$$\begin{array}{cc}{\stackrel{\_}{\mu }}_{\tau +b}^n=0,B_n<b\le \daleth & \left(33\right)\end{array}$

(85) In the constrained optimization problem, the valid ranges of decision variables including μ.sub.τ.sup.n and {tilde over (μ)}.sub.τ+b.sup.n(1≤b≤1) are shown in Equations (32) and (33). It is assumed that time-related parameters including λ.sub.τ.sup.na, {tilde over (λ)}.sub.τ+b.sup.na, p.sub.τ{tilde over (p)}.sub.τ+b, Iτ, .sub.τ+b, ν.sub.τ, and {tilde over (ν)}.sub.τ+b can be obtained with existing prediction algorithms at the beginning of interval τ. See M. Dabbagh, B. Hamdaoui, M. Guizani, and A. Rayes, “Toward energy-efficient cloud computing: Prediction, consolidation, and overcommitment,” IEEE Network, vol. 29, no. 2, pp. 56-61, March 2015, incorporated herein by reference in its entirety.

(86) The solution algorithms for P.sub.1 are described herein. The decision variables (μ.sub.τ.sup.n and {tilde over (μ)}.sub.τ+b.sup.n) corresponding to the final solution to P.sub.1 can determine the service rates of servers 160 corresponding to each application while satisfying their delay bounds in the GDC 100. In this way, the profit of the GDC 100 can be maximized while delay constraints of tasks of all applications are also met.

(87) P.sub.1 is a constrained optimization problem. The mechanism of a penalty function in transforming P.sub.1 into unconstrained P.sub.2 is discussed herein to develop atime-aware task scheduling (TATS) algorithm.

(88) The decision variable vector includes μ.sub.τ.sup.n and {tilde over (μ)}.sub.τ+b.sup.n, which is denoted by {right arrow over (h)}. P.sub.2 can be calculated as follows.

(89) $\begin{array}{cc}\underset{\stackrel{.fwdarw.}{\hslash }}{\mathrm{Min}}\left\{\hat{f}=ϛ\epsilon -\left(f_1-f_2\right)\right\}& \left(34\right)\end{array}$

(90) The augmented objective function in Equation (34) is denoted by {circumflex over (f)}. Let c denote a relatively large positive constant. Let ε denote the penalty caused by the violation of all constraints. Therefore, ε is calculated as follows.

(91) $\begin{array}{cc}\epsilon =\underset{v=1}{\overset{V}{.Math.}}{\left(\max \left\{0,-g_v\left(\stackrel{.fwdarw.}{\hslash }\right)\right\}\right)}^{\alpha }+\underset{c=1}{\overset{C}{.Math.}}{.Math.h_c\left(\stackrel{.fwdarw.}{\hslash }\right).Math.}^{\beta }& \left(35\right)\end{array}$

(92) In Equation (35), inequality constraint ν(1≤ν≤V) is first converted into g.sub.ν({right arrow over (h)})≥0. Its penalty is

(93) ${\left(\max \left\{0,-g_v\left(\stackrel{.fwdarw.}{\hslash }\right)\right\}\right)}^{\alpha }$
if it is not met. Similarly, equality constraint c(1≤c≤C) is first converted into h.sub.c({right arrow over (h)})=0. Therefore, its penalty is

(94) ${.Math.h_c\left(\stackrel{.fwdarw.}{\hslash }\right).Math.}^{\beta }$
if it is violated. Here, α and β are positive integers. For example, constraint (26) is first converted into Ω.sub.n−m.sub.τ+b.sup.n≥0, and its penalty is (max{0, −(Ω.sub.n−m.sub.τ+b.sup.n)}).sup.α if it is violated. In this way, P.sub.2 is obtained and implemented with a hybrid meta-heuristic as described herein.

(95) Note that {circumflex over (f)} in P.sub.2 is a nonlinear function of continuous decision variables μ.sub.τ.sup.n and μ.sub.τ+b.sup.n. Therefore, P.sub.2 belongs to constrained nonlinear optimization problems. See Y.-C. Hsieh, Y.-C. Lee, and P.-S. You, “Solving nonlinear constrained optimization problems: An immune evolutionary based two-phase approach,” Applied Mathematical Modelling, vol. 39, no. 19, pp. 5759-5768, October 2015, incorporated herein by reference in its entirety.

(96) Some existing deterministic algorithms, such as conjugate gradient method and sequential quadratic programming can implement P.sub.2. However, these algorithms need first-order or second-order derivatives of {circumflex over (f)}, and therefore they largely rely on specific mathematical structures of optimization problems. See F. Lenti, F. Nunziata, C. Estatico, and M. Migliaccio, “Conjugate gradient method in Hilbert and Banach spaces to enhance the spatial resolution of radiometer data,” IEEE Transactions on Geoscience and Remote Sensing, vol. 54, no. 1, pp. 397-406, January 2016; and M. Subathra, S. Selvan, T. Victoire, A. Christinal, and U. Amato, “A hybrid with cross-entropy method and sequential quadratic programming to solve economic load dispatch problem,” IEEE Systems Journal, vol. 9, no. 3, pp. 1031-1044, September 2015, each incorporated herein by reference in their entirety. In addition, the search process is difficult and the quality of finally searched solutions has some drawbacks.

(97) Existing meta-heuristic algorithms can avoid shortcomings of the deterministic algorithms discussed herein and have been widely applied to solve different types of complex optimization problems due to robustness, wide applicability, and easy implementation. However, each existing meta-heuristic algorithm has its corresponding advantages and disadvantages. For instance, simulated annealing (SA) can suitably tackle continuous and discrete constrained optimization problems. One advantage is it can intelligently escape from local optima by moving in the direction that can worsen the objective function value. It is proven that SA converges to global optima by specifying a temperature cooling rate. However, the convergence speed of SA can be very slow. See F. Rodriguez, C. Garcia-Martinez, and M. Lozano, “Hybrid metaheuristics based on evolutionary algorithms and simulated annealing: Taxonomy, comparison, and synergy test,” IEEE Transactions on Evolutionary Computation, vol. 16, no. 6, pp. 787-800, December 2012, incorporated herein by reference in its entirety.

(98) Particle swarm optimization (PSO) can be used as a conventional meta-heuristic algorithm, due to its quick convergence. However, it often suffers from being trapped in local optima in its search process. Therefore, its final solutions may be unacceptable when it is applied to solve difficult problems with multidimensional search spaces. See L. Liu, S. Yang, and D. Wang, “Particle swarm optimization with composite particles in dynamic environments,” IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol. 40, no. 6, pp. 1634-1648, December 2010, incorporated herein by reference in its entirety.

(99) Moreover, chaotic search in chaotic PSO (CPSO) can approach global optima more easily and quickly than stochastic search in traditional PSO. The chaotic search can also increase the possibility of escaping from local optima due to dynamic and ergodic properties in the chaotic sequence. In CPSO, a chaotic search based on the logistic equation is adopted to perform local exploitation around solutions currently obtained by PSO. See G. Jakimoski and L. Kocarev, “Chaos and cryptography: Block encryption ciphers based on chaotic maps,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, vol. 48, no. 2, pp. 163-169, February 2001, incorporated herein by reference in its entirety. The equation (36) shown in Dabbagh et al. is expressed as follows.

(100) $\begin{array}{cc}{\chi }^i={\mathrm{ϵ\chi }}^{i-1}\left(1-{\chi }^{i-1}\right)& \left(36\right)\end{array}$

(101) χ.sup.i in Equation (36) is distributed between [0, 1], and represents the chaotic parameter at iteration i in a chaotic system. ∈ represents a control parameter specified in [0, 4]. ∈=4 and χ.sup.0∈[0, 1]−{0, 0.25, 0.5, 0.75, 1} are set, such that the stochastic pattern is added to the value of χ.sup.i.

(102) A hybrid meta-heuristic, called Hybrid Chaotic PSO is based on Simulated-annealing (HCPS) and is applied to solve P.sub.2 by combining SA and CPSO. In HCPS, the velocity of particle j in iteration i+1, V.sub.j.sup.i+1, is updated as follows,

(103) $\begin{array}{cc}{V}_j^{i+1}={\omega }^i{\chi }^i{V}_j^i+c_1{r}_1\left[{\Gamma }_j^i-q_j^i\right]+c_2{r}_2\left[{\Theta }^i-q_j^i\right]& \left(37\right)\end{array}$
where r.sub.1 and r.sub.2 are two random numbers in (0, 1). q.sub.j.sup.i denotes the position of particle j in iteration i. ω.sup.i represents the inertia weight in iteration i. For particle j, its best position in iteration i is denoted by Γ.sub.j.sup.i. For the swarm, its best position in iteration i is denoted by Θ.sup.i. c.sub.1 and c.sub.2 denote the individual and social acceleration coefficients, respectively.

(104) In HCPS, a particle changes its velocity based on positions of particles in a present population. The particle of each position is updated according to the Metropolis criterion of the SA. See K. Meer, “Simulated annealing versus metropolis for a TSP instance,” Information Processing Letters, vol. 104, no. 6, pp. 216-219, December 2007, incorporated herein by reference in its entirety.

(105) In each iteration of the HCPS, the new position of each particle is compared with its old position according to {circumflex over (f)}. The position of each particle with larger {circumflex over (f)} is accepted, while its position with smaller {circumflex over (f)} is conditionally accepted based on a certain possibility specified in the Metropolis criterion. Therefore, HCPS can increase the possibility of finding global optima to maximize the profit of the GDC 100 by escaping from local optima.

(106) TABLE-US-00001 Algorithm 1 TATS 1: Initialize λ.sub.τ.sup.n(− B.sub.n ≤ τ ≤  − 1) with 0 2: Initialize λ.sub.τ.sup.nr and λ.sub.τ.sup.na(┐ ≤ τ ≤ N.sub.1) with λ.sub.τ.sup.n 3: Initialize λ.sub.┐−B.sub.n.sub.−1.sup.n and D.sub.┐−1.sup.n with 0 4: τ ← 5: while τ ≤ N.sub.I do 6:  Update λ.sub.τ.sup.na based on (3) 7:  Solve P.sub.2 to obtain μ.sub.τ.sup.n and {tilde over (μ)}.sub.τ+b.sup.n via HCPS, respectively 8:  Schedule tasks to the GDC, and remove them from  corresponding FCFS queue 9:  Update λ.sub.i.sup.nr (τ − B.sub.n ≤ i ≤ τ) 10:  D.sub.τ.sup.n ← D.sub.τ−1.sup.n + (λ.sub.τ.sup.na , (1 − δ(λ.sub.τ.sup.na , μ.sub.τ.sup.n))L) 11:  Λ.sub.τ−Bn.sub.n ← Λ.sub.τ−B.sub.n.sup.n +λ.sub.τ-Bn.sup.nL 12:  τ ← τ + 1 13: end while

(107) Algorithm 1 shows the pseudo code of TATS. Line 1 initializes λ.sub.τ.sup.n(−B.sub.n ≤τ≤−1) with 0. Line 2 initializes λ.sub.τ.sup.nr and λ.sub.τ.sup.na(≤τ≤N.sub.1) with λ.sub.τ.sup.n. Line 3 sets ∧.sub.−Bn−1.sup.n and D.sub.−1.sup.n to 0. N.sub.1 denotes the number of intervals λ.sub.τ.sup.na, which is updated based on Equation (6). Line 7 solves P.sub.2 to obtain μ.sub.τ.sup.n and {tilde over (μ)}.sub.τ+b.sup.n by HCPS. Line 8 schedules (L(1−δ(λ.sub.τ.sup.na, μ.sub.τ.sup.n))λ.sub.τ.sup.na) tasks to execute. The tasks are removed from the head of their corresponding FCFS queue processors 120a-c. λ.sub.i.sup.nr(τ−B.sub.n<i<τ) is updated in Line 9. Lines 10-11 update D.sub.τ.sup.n and Λ.sub.τ−B.sub.n.sup.n.

(108) TABLE-US-00002 Algorithm 2 HCPS 1: Initialize particles’ velocities and positions randomly 2: Compute the fitness values of particles 3: Update Γ and Θ 4: Initialize c.sub.1, c.sub.2, v.sub.M, w.sub.m, w.sub.M, χ.sup.0, and d 5: Initialize  and w with t.sup.0 and w.sub.M, respectively 6. i ← 0 7: while i ≤ φ and  ≤ 95% do 8:  Update positions and velocities of particles using  Metropolis acceptance criterion 9:  Calulate fitness values of particles in the current swarm 10:  Update Γ and Θ 11:  Decrease the temperature by d 12:  Decrease w linearly from w.sub.M down to w.sub.m in iteration i 13:  Calculate the chaotic parameter χ.sup.i+1 using (36) 14:  Update V.sub.j.sup.i+1 and q.sub.j.sup.i + 1 15:  Calculate and update 16:  i ← i + 1 17: end while 18: Output Θ

(109) The pseudo of HCPS is shown in Algorithm 2. The upper and lower bounds of inertia weight ω are denoted by ω.sub.M and ω.sub.m, respectively. Velocities of particles are limited to [−ν.sub.M, ν.sub.M]. The total number of iterations is denoted by φ. The temperature in HCPS is denoted by , which is initialized with t.sup.0. The temperature cooling rate is denoted by d. In Algorithm 2, the velocities and positions of the particles are initialized randomly in Line 1. Lines 2-3 calculate fitness values of particles, and update Γ and Θ. Lines 4-5 initialize parameters including c.sub.1, c.sub.2, ν.sub.M, ω.sub.m, ω.sub.M, χ.sup.0, d, , and ω.

(110) Let denote the maximum percentage of particles whose fitness values are the same in the current swarm. In lines 6-7, the while loop ends when ψ is exceeded or ≤95%. The positions and velocities of particles are updated using the Metropolis acceptance criterion in Line 8. Lines 9-10 calculate fitness values of particles, and update Γ and Θ. Lines 11-12 decrease the temperature and w. Lines 13-14 calculate the chaotic parameter X.sup.i+1 using Equation (36), and update V.sub.j.sup.i+1 and q.sub.j.sup.i+1. In lines 15-18, Θ is obtained and transformed into μ.sub.τ.sup.n and {tilde over (μ)}.sub.τ+b.sup.nθ(1≤b≤).

(111) In an embodiment using TATS Algorithm 1 and HCPS Algorithm 2, a particle is a representative entity and a swarm is a cluster of entities. In another embodiment using TATS Algorithm 1 and HCPS Algorithm 2, a particle is an application task and a swarm is a cluster of application tasks. As a result, the service rates of applicable servers 160 for processing arriving application tasks within the GDC 100 are determined.

(112) The following experiments adopted real-life tasks, a price of a grid, and green energy data to evaluate TATS. Parameter settings are described herein.

(113) Public real-life arriving tasks of three applications (types 1, 2, and 3) over approximately a 24-hour period were adopted. FIG. 2 is a graph illustrating the arriving rates for application tasks of type 1, type 2, and type 3. The length of each interval was set to five minutes. Delay bounds of type 1, 2, and 3 applications were respectively 3, 4, and 5 intervals, i.e., B.sub.1=3, B.sub.2=4, and B.sub.3=5. FIG. 3 is a graph illustrating the real-life price of grid data over the 24-hour adopted period. M. Ghamkhari et al. describe energy and performance management of green data centers. See M. Ghamkhari and H. Mohsenian-Rad, “Energy and performance management of green data centers: A profit maximization approach,” IEEE Transactions on Smart Grid, vol. 4, no. 2, pp. 1017-1025, June 2013, incorporated herein by reference in its entirety. Parameters were set based on Ghamkhari and Mohsenian-Rad for the power consumption model, ω=5(MWH), P.sub.0.sup.1=200(W), P.sub.0.sup.2=100(W), P.sub.0.sup.3=50(W), P.sub.1.sup.1=400(W), P.sub.1.sup.2=200(W), P.sub.1.sup.3=100(W), γ=1.2, σ.sub.1=0.05 tasks/minute, σ.sub.2=0.1 tasks/minute, and σ.sub.3=0.2 tasks/minute. In addition, C.sub.1=12, C.sub.2=25, and C.sub.3=50. Ω.sub.1=3×10.sup.6, Ω.sub.2=1.5×10.sup.6, and Ω.sub.3=3×10.sup.6.

(114) The execution time of each task corresponding to each application was sampled based on the uniform distribution over interval (0, L). Based on Yuan et al., VM execution prices per unit time in each interval τ were sampled based on uniform distribution oveτ intervals (0.24, 0.48), (0.16, 0.32), and (0.08, 0.16), respectively. See H. Yuan, J. Bi, W. Tan and B. H. Li, “Temporal Task Scheduling With Constrained Service Delay for Profit Maximization in Hybrid Clouds,” to appear in IEEE Transactions on Automation Science and Engineering, doi: 10.1109/TASE.2016.2526781, incorporated herein by reference in its entirety. θ.sub.τ.sup.n was calculated accordingly.

(115) Public data over a 24-hour period were adopted for solar irradiance and for wind speed. FIG. 4 is a graph illustrating the solar irradiance over the 24-hour adopted period. FIG. 5 is a graph illustrating the wind speed over the 24-hour adopted period. In addition, based on Ghamkhari and Mohsenian-Rad, κ=1.5*10.sup.5(m.sup.2), ψ=0.2, ρ=1.225(kg/m.sup.3), ζ=2.5*10.sup.5(m.sup.2), and η=0.3. The power ratings of solar and wind energy sources were set to 1.65*10.sup.8(W) and 9*10.sup.8(W), respectively.

(116) The parameter setting of HCPS in Algorithm 2 is ω.sub.M=0.95, ω.sub.m=0.4, φ=200, ξ=100, k=0.975, c.sub.1=c.sub.2=0.5, and t.sup.0=10.sup.30.

(117) FIG. 6 is a graph illustrating experimental results for the profit and penalty of the GDC 100 and the corresponding penalty brought by each solution finally specified by TATS in each interval. In Equation (34), ζ=10.sup.20. In Equation (35), α=β=2. It is illustrated in FIG. 6 that the corresponding penalty in each interval τs nearly zero. As shown in Equation (35), the penalty of almost zero shows that TATS can find a close-to-optimal solution that can meet all constraints in P.sub.1. In addition, as is shown in Equation (34), TATS can minimize the new objective function {tilde over (ƒ)}, and therefore maximize the profit of the GDC 100.

(118) The consumption of grid and green energy, including solar and wind, was evaluated. FIG. 7 is a graph illustrating energy from grid, wind, and solar sources. The maximum amount of available energy in the GDC 100 is set to 5×10.sup.7 (MWH), i.e., ω=5×10.sup.7. TATS is inclined to first use renewable energy generated from solar and wind sources, and then to consume grid energy purchased in each interval. TATS is inclined to use wind energy rather than use solar energy when both of them are available. This is because the power rating of a wind energy source is more than five times higher than the power rating of solar energy. If the sum of wind and solar energy is still not enough, TATS uses grid energy.

(119) In this experiment, the length of each interval was five minutes. FIGS. 8A-8C are graphs illustrating cumulative and remaining tasks of types 1, 2, and 3, respectively in corresponding intervals that were evaluated. For example in FIG. 8B, λ.sub.τ−4.sup.2r, λ.sub.τ−3.sup.2r, λ.sub.τ−2.sup.2r, λ.sub.τ−1.sup.2r, and λ.sub.τ.sup.2a correspond to tasks of type 2 in each interval τ, respectively. Note that λ.sub.τ.sup.2a=λ.sub.τ.sup.2+λ.sub.τ−1.sup.2r+λ.sub.τ−2.sup.2r+λ.sub.τ−3.sup.2r+λ.sub.τ−4.sup.2r. λ.sub.τ−4.sup.2r is the smallest among λ.sub.τ−4.sup.2r, λ.sub.τ−3.sup.2r, λ.sub.τ−2.sup.2r, and λ.sub.τ−1.sup.2r. This is because TATS enqueues arriving tasks into their corresponding FCFS queue and inclines to schedule remaining tasks that arrive earlier. TATS attempts to ensure that by interval τ, all tasks in interval τ−B.sub.2 or before are scheduled to the GDC 100. Remaining tasks arriving in intervals τ−3, τ−2, and τ−1 can only be scheduled until λ.sub.τ−4.sup.2r=0. Similarly, λ.sub.τ−3.sup.2r is smaller than λ.sub.τ−2.sup.2r and λ.sub.τ−1.sup.2r. Remaining tasks arriving in intervals τ−2 and τ−1 can only be scheduled until λ.sub.τ−4.sup.2r=0 and λ.sub.τ−3.sup.2r=0. Remaining tasks in interval τ−1 are scheduled until all tasks arriving earlier have already been executed, i.e., λ.sub.τ−4.sup.2r=0, λ.sub.τ−3.sup.2r=0 and λ.sub.τ−2.sup.2r=0. Thus, λ.sub.τ−1.sup.2r is much larger than λ.sub.τ−4.sup.2r, λ.sub.τ−3.sup.2r, and λ.sub.τ−2.sup.2r in each interval.

(120) FIGS. 9A-9C are graphs illustrating cumulative arriving tasks (CATs) and cumulative scheduled tasks (CSTs) corresponding to the applications of types 1, 2, and 3, respectively that were evaluated. Similar to Yuan et al. (See H. Yuan, J. Bi, W. Tan, M. Zhou, B. H. Li, and J. Li, “TTSA: An effective scheduling approach for delay bounded tasks in hybrid clouds,” to appear in IEEE Transactions on Cybernetics, doi: 10.1109/TCYB.2016.2574766, 2016, incorporated herein by reference in its entirety), delay constraints of the three applications were artificially specified to 3, 4, and 5 intervals, respectively, i.e., Bi=3, B.sub.2=4, and B.sub.3=5. Tasks of each application were all scheduled to the GDC 100 within their delay bounds. For example in FIG. 9B, the number of CATs in interval 161 is equal to the number of CSTs in interval 165. This indicates tasks of type 2 arriving in interval 161 or before are all scheduled to the GDC 100 by interval 165. Therefore, the experimental result shows that TATS can satisfy the delay constraint of tasks of each application.

(121) The following results can be made when TATS is compared with a number of conventional benchmark algorithms (See X. Deng; D. Wu, J. Shen, and J. He, “Eco-aware online power management and load scheduling for green cloud datacenters,” IEEE Systems Journal, vol. 10, no. 1, pp. 78-87, March 2016; J. Bi, H. Yuan, W. Tan, and B. H. Li, “TRS: Temporal request scheduling with bounded delay assurance in a green cloud data center,” Information Sciences, vol. 360, pp. 57-72, April 2016; and X. Zuo, G. Zhang, and W. Tan, “Self-adaptive learning PSO-based deadline constrained task scheduling for hybrid IaaS cloud,” IEEE Transactions on Automation Science and Engineering, vol. 11, no. 2, pp. 564-573, April 2014, each incorporated herein by reference in their entirety) with respect to the throughput and the profit of the GDC 100. 1) Algorithm 1, similar to cheap-first scheduling algorithm (See X. Deng, D. Wu, J. Shen, and J. He, “Eco-aware online power management and load scheduling for green cloud datacenters,” IEEE Systems Journal, vol. 10, no. 1, pp. 78-87, March 2016, incorporated herein by reference in its entirety), schedules arriving tasks in a selected interval when the price of the grid is minimal in their corresponding delay bounds. The maximum amount of available energy in the GDC 100 in each interval is fixed and limited. Therefore, some tasks may not be admitted into the GDC 100. 2) Algorithm 2 in (See X. Zuo, G. Zhang, and W. Tan, “Self-adaptive learning PSO-based deadline constrained task scheduling for hybrid IaaS cloud,” IEEE Transactions on Automation Science and Engineering, vol. 11, no. 2, pp. 564-573, April 2014, incorporated herein by reference in its entirety) ignores the temporal difference in the price of the grid and green energy. Therefore, tasks are scheduled to the GDC 100 in their arriving interval. 3) Algorithm 3, similar to the first scheduling algorithm (See J. Bi, H. Yuan, W. Tan, and B. H. Li, “TRS: Temporal request scheduling with bounded delay assurance in a green cloud data center,” Information Sciences, vol. 360, pp. 57-72, April 2016, incorporated herein by reference in its entirety), schedules arriving tasks in selected intervals in which the amount of green energy is a maximum in their corresponding delay bounds. Similar to Algorithm 1, some arriving tasks might be refused because of the limit of the maximum amount of available energy in the GDC 100.

(122) FIGS. 10A-10C are graphs illustrating TATS and benchmark Algorithms 1-3, corresponding to the applications of types 1, 2, and 3, respectively that were compared. The cumulative throughput in each interval was obtained by calculating the sum of tasks scheduled from t to i+T. For example in FIG. 10B, the cumulative throughput corresponding to type 2 in interval τ was obtained by calculating the sum of tasks scheduled in interval τ to τ+B.sub.2. The cumulative throughput of TATS was larger than that of Algorithm 1, Algorithm 2, and Algorithm 3 by 77.4%, 64.3%, and 81% on average, respectively. This is because Algorithm 1, Algorithm 2, and Algorithm 3 all need to selectively admit tasks due to the limited energy in the GDC 100. Therefore, results demonstrate that TATS can effectively increase the cumulative throughput of the GDC 100.

(123) FIG. 11 is a graph illustrating the cumulative total profits for TATS that were compared with each of Algorithm 1, Algorithm 2, and Algorithm 3. To guarantee the performance of tasks, a conventional SLA that specifies a penalty cost for each refused task is signed between users and cloud providers. See D. Ardagna, B. Panicucci, and M. Passacantando, “Generalized Nash equilibria for the service provisioning problem in cloud systems,” IEEE Transactions on Services Computing, vol. 6, no. 4, pp. 429-442, October 2013, incorporated herein by reference in its entirety. Therefore, the refused tasks cause the penalty cost for a GDC provider. In conventional SLAs, ν.sub.τ.sup.n is larger than the maximum profit brought by each task of application n from τ to τ+B.sub.n. Let YT denote the profit per task of application n in interval τ. Thus,
ν.sub.τ.sup.n=max.sub.i∈{0,1 . . . ,B.sub.n.sub.}(Y.sub.τ+i.sup.n).
The cumulative total profit in r is the difference between the profit brought by the execution of tasks and the penalty cost corresponding to refused tasks from interval τ to i+B.sub.n. FIG. 11 illustrates that compared with Algorithm 1, Algorithm 2, and Algorithm 3, the cumulative total profit of TATS can be increased significantly. This occurs because TATS can intelligently schedule more arriving tasks to the GDC 100 by investigating the temporal variation in the price of the grid, revenue, and green energy in the delay bounds of tasks.

(124) Each of the functions of the described embodiments can be implemented by one or more processing circuits. A processing circuit includes a programmed processor (for example, the servers 160 or the electronic devices 110 of FIG. 1), which includes circuitry. A processing circuit/circuitry can also include devices such as an application specific integrated circuit (ASIC) and circuit components arranged to perform the recited functions. The processing circuitry can be referred to interchangeably as circuitry throughout the disclosure.

(125) In addition, when processors are programmed to perform the processes described herein, they become special-purpose devices. The processes performed by the electronic devices 110, the queue processors 120, the task scheduling processor 130, the energy collecting processor 150, the servers 160, and the resource provisioning processor 170 have specialized processing circuitry. Incoming delay-bounded tasks are received and queued in the queue processors 120, such that the incoming delay-bounded tasks can be scheduled for processing by the task scheduling processor 130 within the GDC 100.

(126) The specialized processing circuitry of the task scheduling processor 130 receives energy data from the energy collecting processor 150 regarding available energy from renewable energy resources of the solar power source 142 and the wind power source 143. The renewable energy resources are used first and when necessary, resources from the grid power source 141 are used. As a result, the specialized circuitry of processors within the GDC 100 provides a very efficient and ecologically sound computing system.

(127) FIG. 12 is a schematic of an exemplary computing device 550, such as the electronic devices 110, the queue processors 120, the task scheduling processor 130, the energy collecting processor 150, the servers 160, and the resource provisioning processor 170, all of which can be used to implement the techniques described in this disclosure. The computing device 550 is intended to represent various forms of digital hardware, such as laptops, desktops, workstations, personal digital assistants, servers, blade servers, mainframes, and other appropriate computers. The components shown here, their connections and relationships, and their functions are meant to be examples only and are not meant to be limiting.

(128) The computing device 550 includes a processor 500, a memory 502, a storage device 504, a high-speed interface 512 connecting to the memory 502 and multiple high-speed expansion ports 516, and a low-speed interface 510 connecting to a low-speed expansion port 514 and the storage device 504. Each of the processor 500, the memory 502, the storage device 504, the high-speed interface 512, the high-speed expansion ports 516, and the low-speed interface 510 are interconnected using various busses, such as communication bus 526, and may be mounted on a common motherboard or in other manners as appropriate.

(129) The processor 500 can process instructions for execution within the computing device 550, including instructions stored in the memory 502 or on the storage device 504 to display graphical information for a GUI on an external input/output device, such as a display 508 coupled to the high-speed interface 512. In other implementations, multiple processors and/or multiple buses may be used, as appropriate, along with multiple memories and types of memory. Also, multiple computing devices may be connected, with each device providing portions of the necessary operations (e.g., as a server bank, a group of blade servers, or a multi-processor system). The memory 502 stores information within the computing device 550. In some implementations, the memory 502 is a volatile memory unit or units. In some implementations, the memory 502 is a non-volatile memory unit or units. The memory 502 can also be another form of computer-readable medium, such as a magnetic or optical disk.

(130) The storage device 504 is capable of providing mass storage for the computing device 550. In some implementations, the storage device 504 can be or contain a computer-readable medium, such as a floppy disk device, a hard disk device, an optical disk device, a tape device, a flash memory or other similar solid state memory device, or an array of devices, including devices in a storage area network or other configurations. Instructions can be stored in an information carrier. The instructions, when executed by one or more processing devices (for example, processor 500), perform one or more methods, such as those described above. The instructions can also be stored by one or more storage devices, such as computer- or machine-readable mediums (for example, the memory 502, the storage device 504, or memory on the processor 500).

(131) The high-speed interface 512 manages bandwidth-intensive operations for the computing device 550, while the low-speed interface 510 manages lower bandwidth-intensive operations. Such allocation of functions is an example only. In some implementations, the high-speed interface 512 is coupled to the memory 502, the display 508 (e.g., through a graphics processor or accelerator), and to the high-speed expansion ports 516, which may accept various expansion cards (not shown). In the implementation, the low-speed interface 510 is coupled to the storage device 504 and the low-speed expansion port 514. The low-speed expansion port 514, which can include various communication ports (e.g., USB, Bluetooth, Ethernet, wireless Ethernet) can be coupled to one or more input/output devices 518, such as a keyboard, a pointing device, a scanner, or a networking device such as a switch or router, e.g., through a network adapter.

(132) The computing device 550 also includes a network controller 506, such as an Intel Ethernet PRO network interface card from Intel Corporation of America, for interfacing with a network 55. As can be appreciated, the network 55 can be a public network, such as the Internet, or a private network such as an LAN or WAN network, or any combination thereof and can also include PSTN or ISDN sub-networks. The network 55 can also be wired, such as an Ethernet network, or can be wireless such as a cellular network including EDGE, 3G and 4G wireless cellular systems. The wireless network can also be Wi-Fi, Bluetooth, or any other wireless form of communication that is known.

(133) Although the computing device of FIG. 12 is described as having a storage medium device 504, the claimed advancements are not limited by the form of the computer-readable media on which the instructions of the described processes are stored. For example, the instructions can be stored on CDs, DVDs, in FLASH memory, RAM, ROM, PROM, EPROM, EEPROM, hard disk, or any other information processing device with which the computing device communicates.

(134) In other alternate embodiments, processing features according to the present disclosure may be implemented and commercialized as hardware, a software solution, or a combination thereof. Moreover, instructions corresponding to processes described herein could be stored in a portable drive, such as a USB Flash drive that hosts a secure process.

(135) Computer programs (also known as programs, software, software applications, or code) associated with the processes described herein include machine instructions for a programmable processor, and can be implemented in a high-level procedural and/or object-oriented programming language, and/or in assembly/machine language. As used herein, the terms machine-readable medium and computer-readable medium refer to any computer program product, apparatus, and/or device (e.g., magnetic discs, optical disks, memory, Programmable Logic Devices (PLDs)) used to provide machine instructions and/or data to a programmable processor, including a machine-readable medium that receives machine instructions as a machine-readable signal. The term machine-readable signal refers to any signal used to provide machine instructions and/or data to a programmable processor.

(136) To provide for interaction with a user, the systems and techniques described herein can be implemented on a computer having a display device 508 (e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor) for displaying information to the user and a keyboard and a pointing device 518 (e.g., a mouse or a trackball) by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well. For example, feedback provided to the user can be any form of sensory feedback (e.g., visual feedback, auditory feedback, or tactile feedback), and input from the user can be received in any form, including acoustic, speech, or tactile input.

(137) The systems and techniques described herein can be implemented in a computing system that includes a back end component (e.g., as a data server), or that includes a middleware component (e.g., an application server), or that includes a front end component (e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the systems and techniques described here), or any combination of such back end, middleware, or front end components. The components of the system can be interconnected by any form or medium of digital data communication (e.g., a communication network). Examples of communication networks include a local area network (LAN), a wide area network (WAN), and the Internet.

(138) The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.

(139) A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of this disclosure. For example, preferable results may be achieved if the steps of the disclosed techniques were performed in a different sequence, if components in the disclosed systems were combined in a different manner, or if the components were replaced or supplemented by other components. The functions, processes, and algorithms described herein may be performed in hardware or software executed by hardware, including computer processors and/or programmable circuits configured to execute program code and/or computer instructions to execute the functions, processes, and algorithms described herein. Additionally, an implementation may be performed on modules or hardware not identical to those described. Accordingly, other implementations are within the scope that may be claimed.

(140) FIG. 13 illustrates an exemplary cloud computing system, wherein users access the cloud through mobile device terminals or fixed terminals that are connected to the Internet or other network. One or more of the devices illustrated in the GDC 100 of FIG. 1 could be used in the cloud computing system illustrated in FIG. 13.

(141) The mobile device terminals can include a cell phone 610, a tablet computer 612, and a smartphone 614, for example. The mobile device terminals can connect to a mobile network service 620 through a wireless channel such as a base station 656 (e.g., an Edge, 3G, 4G, or LTE Network), an access point 654 (e.g., a femto cell or WiFi network), or a satellite connection 652. In one implementation, signals from the wireless interface to the mobile device terminals (e.g., the base station 656, the access point 654, and the satellite connection 652) are transmitted to a mobile network service 620, such as an EnodeB and radio network controller, UMTS, or HSDPA/HSUPA. Mobile users' requests and information are transmitted to central processors 622 that are connected to servers 624 to provide mobile network services, for example. Further, mobile network operators can provide service to mobile users for authentication, authorization, and accounting based on home agent and subscribers' data stored in databases 626, for example. The subscribers' requests are subsequently delivered to a cloud 630 through the Internet.

(142) A user can also access the cloud 630 through a fixed terminal 616, such as a desktop or laptop computer or workstation that is connected to the Internet via a wired network connection or a wireless network connection. The mobile network service 620 can be a public or a private network such as an LAN or WAN network. The mobile network service 620 can be wireless such as a cellular network including EDGE, 3G and 4G wireless cellular systems. The wireless mobile network service 620 can also be Wi-Fi, Bluetooth, or any other wireless form of communication that is known.

(143) The user's terminal, such as a mobile user terminal and a fixed user terminal, provides a mechanism to connect via the Internet to the cloud 630 and to receive output from the cloud 630, which is communicated and displayed at the user's terminal. In the cloud 630, a cloud controller 636 processes the request to provide users with the corresponding cloud services. These services are provided using the concepts of utility computing, virtualization, and service-oriented architecture.

(144) In one implementation, the cloud 630 is accessed via a user interface such as a secure gateway 632. The secure gateway 632 can for example, provide security policy enforcement points placed between cloud service consumers and cloud service providers to interject enterprise security policies as the cloud-based resources are accessed. Further, the secure gateway 632 can consolidate multiple types of security policy enforcement, including for example, authentication, single sign-on, authorization, security token mapping, encryption, tokenization, logging, alerting, and API control. The cloud 630 can provide to users, computational resources using a system of virtualization, wherein processing and memory requirements can be dynamically allocated and dispersed among a combination of processors and memories to create a virtual machine that is more efficient at utilizing available resources. Virtualization creates an appearance of using a single seamless computer, even though multiple computational resources and memories can be utilized according to increases or decreases in demand. In one implementation, virtualization is achieved using a provisioning tool 640 that prepares and equips the cloud resources, such as the processing center 634 and data storage 638 to provide services to the users of the cloud 630. The processing center 634 can be a computer cluster, a data center, a main frame computer, or a server farm. In one implementation, the processing center 634 and data storage 638 are collocated.

(145) Embodiments described herein can be implemented in conjunction with one or more of the devices described above with reference to FIGS. 12-13. Embodiments described herein are a combination of hardware and software, and circuitry by which the software is implemented.

(146) FIG. 14A is a flowchart illustrating an exemplary method 700 of scheduling tasks. In step S710, a plurality of application tasks are received into one or more processing queues of a GDC. In an embodiment, a plurality of FCFS queues receive the application tasks.

(147) In step S720, a service rate is determined for a plurality of servers to process the plurality of application tasks in the GDC, via processing circuitry. In an embodiment, the task service rate for an application to execute in a time interval τs calculated, wherein a single task of each application is executed in an individual time interval.

(148) In FIG. 14B, steps S721-S729 are described herein as sub-processing steps for determining the service rate of step S720. In step S721, the velocities and positions of the particles are initialized randomly for a plurality of representative entities in a cluster of entities. In an embodiment, the plurality of representative entities includes a plurality of application tasks, and the cluster of entities includes a cluster of application tasks.

(149) In step S722, an initial fitness level of each representative entity in the cluster of entities is determined. In step S723, an initial best position of each representative entity and an initial best position of the cluster of entities are determined.

(150) In step S724, one or more task scheduling parameters are initialized for a given number of time slots. In an embodiment, the task scheduling parameters include one or more of individual and social acceleration coefficients, a maximum particle velocity, upper and lower bounds of inertia weight, and a temperature cooling rate of each representative entity. In step S725, a velocity and a position of each representative entity are updated based upon the initialized parameters.

(151) In step S726, a current fitness level of each representative entity in a current cluster of entities is calculated. In step S727, a current best position of each representative entity and a current best position of the cluster of entities are updated.

(152) In step S728, a chaotic search parameter in a chaotic system is calculated. In an embodiment, the chaotic search parameter includes a stochastic pattern in the chaotic system.

(153) In step S729, the velocity and the position of each representative entity are updated based upon the chaotic search parameter. In an embodiment, tasks are scheduled to execute in the GDC based upon a difference in an arriving rate of tasks in the respective time interval and a task service rate in the respective time interval.

(154) In FIG. 14A, method 700 also includes scheduling, via the processing circuitry, one or more of the application tasks to be executed in one or more of the servers at a rate according to a difference in an accumulated arriving rate for the plurality of application tasks into the one or more queues and a removal rate for the plurality of application tasks from the one or more queues in step S730. Method 700 also includes removing the one or more application tasks from their associated queues for execution in the scheduled one or more servers in step S740.

(155) In conclusion, the temporal variations in revenue, price of the grid, and green energy make it a challenge to maximize the profit of a GDC provider while strictly satisfying the delay constraint of each admitted task. GDCs attempt to achieve profit maximization by cost-effectively scheduling tasks while meeting their delay constraints.

(156) Several advantages are realized by the described disclosure. Embodiments herein describe a TATS algorithm that can intelligently schedule each admitted task to execute within its delay bounds. The mathematical equations herein describe task refusal and service rates. In each iteration, TATS addresses a profit maximization problem through the disclosed Hybrid Chaotic PSO based on SA. Extensive simulation experiments according to realistic data demonstrate that TATS can effectively improve profit and throughput without exceeding the delay bound of each admitted task, compared with several existing scheduling algorithms.

(157) Some conventional data center systems are powered by different energy sources, including grid power and renewable power. In one conventional example, a management system executes computational tasks by enabling the movement of data components between different data centers. The module of price determination in the management system specifies prices required to execute tasks.

(158) Other conventional data center systems reduce energy and financial costs by adopting techniques to dynamically place computing jobs. For example, different computing jobs can be dynamically placed at multiple data centers. Multiple factors include bandwidth cost to transfer jobs, resource constraints, electricity availability, marginal consumption of electricity, and expected costs. These techniques can reduce the overall cost brought by the execution of computing in multiple data centers.

(159) However, embodiments described herein overcome the deficiencies and shortcomings of many conventional data center systems, such as those described above. Embodiments described herein achieve profit maximization for a GDC provider by considering the temporal variation in the revenue, the price of the grid, and the green energy for delay bounds of each task. Tasks of each application are put into a separate queue, such as a FCFS queue and their delay bound constraints are guaranteed. In addition, the mathematical modeling of task refusal and service rates of tasks are provided. Temporal task scheduling is achieved by solving the formulated profit maximization problem using the hybrid chaotic PSO based on SA algorithm.

(160) Other conventional data center systems include a system to support computing services at multiple response time constraints and energy demands, wherein customers may sacrifice response time performance of some tasks by adopting green products. Another conventional data center system includes an online job and energy scheduling algorithm that attempts to maximize the profit for a GDC using a randomized algorithm and propose to dispatch jobs and energy for the GDC. The expected competitive ratio of the online algorithm in different settings is used to guarantee its performance.

(161) Another conventional data center system has several energy-efficient job scheduling algorithms for both discrete and continuous processor speeds. The energy consumption of a cloud data center can be minimized while sequential tasks within a specified deadline are executed on different servers with discrete and continuous speeds.

(162) Still another conventional data center system focuses on the energy efficiency and sustainability of current Information Communication Technology (ICT) data centers. It uses a unified green ICT framework to integrate multiple features and aspects of software to illustrate the effect of software on energy efficiency in cloud data centers.

(163) However, embodiments described herein overcome the deficiencies and shortcomings of many conventional data center systems, such as those described above. Embodiments described herein focus on tasks with different deadlines corresponding to multiple delay-bounded applications. All delay-bounded tasks are put into a queue, such as a FCFS queue. The mathematical modeling of task refusal and service rates of tasks are presented. The profit of a GDC is maximized by considering the temporal variation in the revenue, the price of the grid, and green energy in delay bounds of each task. The scheduling algorithm described herein can strictly guarantee delay bound constraints of all admitted tasks.

(164) Embodiments described herein include the following aspects.

(165) (1) A method of scheduling tasks includes receiving a plurality of application tasks into one or more queues of a green data center (GDC), and determining a service rate for a plurality of servers to process the plurality of application tasks in the GDC, via processing circuitry. Determining the service rate for the plurality of servers includes initializing, via the processing circuitry, a random velocity and a random position for a plurality of representative application tasks in a cluster of application tasks; determining, via the processing circuitry, an initial fitness level of each representative application task in the cluster of application tasks; determining, via the processing circuitry, an initial optimum position of each representative application task and an initial optimum position of the cluster of application tasks; initializing, via the processing circuitry, one or more task scheduling parameters for a given number of time slots; updating, via the processing circuitry, a velocity and a position of each representative application task based upon the initialized task scheduling parameters; calculating, via the processing circuitry, a current fitness level of each representative application task in a current cluster of application tasks; updating, via the processing circuitry, a current optimum position of each representative application task and a current optimum position of the cluster of application tasks; calculating, via the processing circuitry, a chaotic search parameter for an iteration in a chaotic system; and updating, via the processing circuitry, the velocity and the position of each representative application task based in part upon the chaotic search parameter. The method also includes scheduling, via the processing circuitry, one or more of the application tasks to be executed in one or more of the servers at a rate according to a difference in an accumulated arriving rate for the plurality of application tasks into the one or more queues and a removal rate for the plurality of application tasks from the one or more queues; and removing the one or more application tasks from their associated queues for execution in the scheduled one or more servers.

(166) (2) The method of (1), wherein the task scheduling parameters include one or more of individual and social acceleration coefficients, a maximum particle velocity, upper and lower bounds of inertia weight, and a temperature cooling rate of each representative entity.

(167) (3) The method of either (1) or (2), further includes decreasing a temperature according to the temperature cooling rate; and decreasing the inertia weight of each representative application task from the upper bound inertia weight to the lower bound inertia weight.

(168) (4) The method of any one of (1) through (3), further includes calculating, via the processing circuitry, a maximum percentage of representative application tasks in which the fitness levels are equal within a current cluster of application tasks; and outputting a new best position for the cluster of application tasks.

(169) (5) The method of any one of (1) through (4), further includes calculating, via the processing circuitry, a task service rate for an application to execute in a time interval within the GDC, wherein a single task of each application is executed in an individual time interval; and updating, via the processing circuitry, the data task variables for all executed tasks.

(170) (6) The method of any one of (1) through (5), further includes scheduling the application tasks, via the processing circuitry, to execute in the GDC based upon a difference in an arriving rate of the application tasks in the respective time interval and an application task service rate in the respective time interval.

(171) (7) The method of any one of (1) through (6), wherein the GDC includes energy resources from a grid power source and a renewable energy source.

(172) (8) The method of any one of (1) through (7), wherein the renewable energy source includes one or more of a solar energy source and a wind energy source.

(173) (9) The method of any one of (1) through (8), wherein the chaotic search parameter includes a stochastic pattern in the chaotic system.

(174) (10) The method of any one of (1) through (9), wherein the method includes a combination of hybrid chaotic particle swarm optimization based on simulated annealing.

(175) (11) A task scheduling system includes a plurality of queue processors configured to receive a plurality of application tasks into the task scheduling system, a plurality of servers configured to process the plurality of application tasks, and processing circuitry configured to determine a task service rate for each of the servers to schedule the plurality of application tasks received from the plurality of queue processors at a rate according to a difference in an accumulated arriving rate into the plurality of queue processors and a removal rate from the plurality of queue processors. The processing circuitry is further configured to initialize a random velocity and a random position for a plurality of representative application tasks in a cluster of application tasks, determine an initial fitness level of each representative application task in the cluster of application tasks, determine an initial optimum position of each representative application task and an initial optimum position of the cluster of application tasks, initialize one or more task scheduling parameters for a given number of time slots, update a velocity and a position of each representative application task based upon the initialized task scheduling parameters, calculate a current fitness level of each representative application task in a current cluster of application tasks, update a current optimum position of each representative application task and a current optimum position of the cluster of application tasks, calculate a chaotic search parameter for an iteration in a chaotic system, and update the velocity and the position of each representative application task based in part upon the chaotic search parameter.

(176) (12) The task scheduling system of (11), further includes an energy collecting processor having circuitry configured to forward resource data from a grid power source and from one or more renewable power sources to the plurality of servers and to a task scheduling processor.

(177) (13) The task scheduling system of either (11) or (12), wherein the task scheduling processor has circuitry configured to receive data from the plurality of queue processors and from the energy collecting processor to determine the service rate of each of the servers.

(178) (14) The task scheduling system of any one of (11) through (13), wherein the resource data includes one or more of a price of the grid power source, a solar irradiance, a wind speed, an on-site air density, and an average idle peak power for each of the servers.

(179) (15) The task scheduling system of any one of (11) through (14), wherein the processing circuitry is further configured to calculate a task service rate for one of the application tasks to execute in a time interval within the task scheduling system, wherein a single task of each application task is executed in an individual time interval, and update the data task variables for all executed tasks.

(180) (16) The task scheduling system of any one of (11) through (15), wherein determining the task service rate includes a combination of hybrid chaotic particle swarm optimization based on simulated annealing.

(181) (17) The task scheduling system of any one of (11) through (16), wherein the chaotic search parameter includes a stochastic pattern in the chaotic system.

(182) (18) A non-transitory computer-readable medium having computer-executable instructions embodied thereon that when executed by a computing device, perform a method of scheduling tasks. The method includes receiving a plurality of application tasks into one or more queues of a green data center (GDC), and determining a service rate for a plurality of servers to process the plurality of application tasks in the GDC. Determining the service rate for the plurality of servers includes initializing a random velocity and a random position for a plurality of representative application tasks in a cluster of application tasks, determining an initial fitness level of each representative application task in the cluster of application tasks, determining an initial optimum position of each representative application task and an initial optimum position of the cluster of application tasks, initializing one or more task scheduling parameters for a given number of time slots, updating a velocity and a position of each representative application task based upon the initialized task scheduling parameters, calculating a current fitness level of each representative application task in a current cluster of application tasks, updating a current optimum position of each representative application task and a current optimum position of the cluster of application tasks, calculating a chaotic search parameter in a chaotic system, and updating the velocity and the position of each representative application task based upon the chaotic search parameter. The method also includes scheduling one or more of the application tasks to be executed in one or more of the servers at a rate according to a difference in an accumulated arriving rate for the plurality of application tasks into the one or more queues and a removal rate for the plurality of application tasks from the one or more queues, and removing the one or more application tasks from their associated queues for execution in the scheduled one or more servers.

(183) A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of this disclosure. For example, preferable results may be achieved if the steps of the disclosed techniques were performed in a different sequence, if components in the disclosed systems were combined in a different manner, or if the components were replaced or supplemented by other components. The functions, processes, and algorithms described herein may be performed in hardware or software executed by hardware, including computer processors and/or programmable circuits configured to execute program code and/or computer instructions to execute the functions, processes, and algorithms described herein. Additionally, an implementation may be performed on modules or hardware not identical to those described. Accordingly, other implementations are within the scope that may be claimed.

(184) The foregoing discussion describes merely exemplary embodiments of the present disclosure. As will be understood by those skilled in the art, the present disclosure may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. Accordingly, the disclosure is intended to be illustrative, but not limiting of the scope of the disclosure, as well as the claims. The disclosure, including any readily discernible variants of the teachings herein, defines in part, the scope of the foregoing claim terminology such that no inventive subject matter is dedicated to the public.