# Greedy window stochastic optimization algorithm for reducing data center energy consumption

Léa Bayati

► To cite this version:

Léa Bayati. Greedy window stochastic optimization algorithm for reducing data center energy consumption. Flexible Services and Manufacturing Journal, In press, 10.1007/s10696-025-09629-2. hal-05189456

HAL Id: hal-05189456

https://univ-evry.hal.science/hal-05189456v1

Submitted on 7 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

Check for
updates

# Greedy window stochastic optimization algorithm for reducing data center energy consumption

Léa Bayati<fnref n="1" />,<fnref n="2" /> ID

Accepted: 21 June 2025

© The Author(s) 2025

## Abstract

This paper presents a stochastic model for Dynamic Power Management (DPM) in data centers-a strategy that involves dynamically activating and deactivating servers to balance energy efficiency with the maintenance of high Quality of Service (QoS). Unlike traditional methods that rely on predefined job arrival distributions, our approach leverages histograms to dynamically characterize job arrival patterns derived from real-world traces, empirical data, or live traffic measurements. We model the data center as a queuing system and introduce an efficient Greedy Window algorithm that is fast, memory-efficient, and capable of adapting to real-time fluctuations in job arrivals. This algorithm computes a suboptimal policy that closely approximates the optimal strategy attainable through stochastic combinatorial optimization techniques such as the Markov Decision Process (MDP). However, MDP-based approaches face challenges related to state space explosion and substantial computational demands in both time and memory. We evaluate our method across a range of data center configurations using real Google traffic traces and compare its performance against several optimization strategies.

**Keywords** Stochastic combinatorial optimization · Dynamic power management (DPM) · Data centers · Energy efficiency · Quality of service (QoS) · Markov decision process (MDP)

<figure><img src="image_3.png" /></figure>

<footnote>Léa Bayati
lea.bayati@univ-evry.fr</footnote>

<footnote n="1">¹ Laboratoire d'Algorithmique Complexité et Logique, Université Paris-Est Créteil (UPEC), 61 Av. du Général de Gaulle, 94000 Créteil, Val-de-Marne, France</footnote>

<footnote n="2">² IBISC Laboratory (Informatique, Bioinformatique, Systèmes Complexes EA 4526), Université Évry Paris-Saclay, Bâtiment IBGBI – 2ème étage 23, Boulevard de France 91034, Évry, France</footnote>
<table><caption>**Table 1** Collection of several papers on energy optimization in data centers</caption><thead><tr><th>Paper</th><th>Time</th><th>Arrivals</th><th>Service</th><th>Servers</th><th>Buffer</th><th>QoS</th><th>Time latency</th><th>Energetic latency</th><th>Model</th><th>Solution method</th><th>Strategy</th><th>Energy saving</th></tr></thead><tbody><tr><td>Be-nini et al. (1999)</td><td>Discrete</td><td>Markov chain</td><td>Markov chain</td><td>Heterogeneous</td><td>Finite</td><td>Waiting jobs rejected jobs</td><td>Markov chain</td><td>Yes</td><td>MDP</td><td>Linear programming</td><td>Optimal (Constrained)</td><td>—</td></tr><tr><td>Gandhi et al. (2010a)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous</td><td>+∞</td><td>Response time</td><td>Deterministic</td><td>Yes</td><td>Mar-kov chain</td><td>Analytic simulation</td><td>Suboptimal</td><td>—</td></tr><tr><td>Nathujji et al. (2007)</td><td>Discrete</td><td>Bench-marks</td><td>Benchmarks</td><td>Heterogeneous</td><td>Finite</td><td>Through-put service</td><td>No</td><td>No</td><td>Ana-lytical prediction</td><td>Experimental</td><td>Suboptimal</td><td>20%</td></tr><tr><td>Gandhi et al. (2010b)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous</td><td>+∞</td><td>Response time</td><td>Exponential</td><td>Yes</td><td>Mar-kov chain</td><td>Analytic simulation</td><td>Suboptimal</td><td>—</td></tr><tr><td>Ghosh et al. (2013)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous</td><td>Finite</td><td>Response time rejected jobs</td><td>Exponential</td><td>Yes</td><td>SRN</td><td>Fixed-point iteration</td><td>Suboptimal</td><td>—</td></tr><tr><td>Mitrani (2013)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous</td><td>+∞</td><td>Waiting jobs</td><td>Exponential</td><td>No</td><td>Mar-kov chain</td><td>Analytic simulation</td><td>Suboptimal</td><td>—</td></tr><tr><td>Gandhi et al. (2013)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous</td><td>+∞</td><td>Response time</td><td>Exponential</td><td>Yes</td><td>Mar-kov chain</td><td>Analytic simulation</td><td>Suboptimal</td><td>40%</td></tr><tr><td>Norman et al. (2005)</td><td>Continuous</td><td>Markov chain</td><td>Markov chain</td><td>Homogeneous</td><td>Finite</td><td>Waiting jobs</td><td>No</td><td>Yes</td><td>Mar-kov chain</td><td>Linear programming</td><td>Suboptimal</td><td>—</td></tr></tbody></table>

<figure><img src="image_4.png" /></figure>
<table><caption>Table 1 (continued)</caption><thead><tr><th>Paper</th><th>Time</th><th>Arrivals</th><th>Service</th><th>Servers</th><th>Buffer</th><th>QoS</th><th>Time latency</th><th>Energetic latency</th><th>Model</th><th>Solution method</th><th>Strategy</th><th>Energy saving</th></tr></thead><tbody><tr><td>Mazucco and Dyachuk (2012)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous</td><td>+∞</td><td>Rejected jobs</td><td>Deterministic</td><td>Yes</td><td>Markov chain</td><td>Analytic simulation</td><td>Suboptimal</td><td>10% - 30%</td></tr><tr><td>Gandhi and Harchol-Balter (2011)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous</td><td>+∞</td><td>Response time</td><td>Exponential</td><td>Yes</td><td>Markov chain</td><td>Analytic simulation</td><td>Suboptimal</td><td>-</td></tr><tr><td>Efrosinin (2004)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Heterogeneous</td><td>Finite</td><td>System jobs</td><td>No</td><td>Yes</td><td>MDP</td><td>Value iteration algorithm</td><td>Optimal</td><td>-</td></tr><tr><td>Luh and Viniotis (2002)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Heterogeneous</td><td>+∞</td><td>System jobs</td><td>No</td><td>No</td><td>MDP</td><td>Linear programming</td><td>Optimal</td><td>-</td></tr><tr><td>Schwartz et al. (2012)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous</td><td>+∞</td><td>Waiting time</td><td>No</td><td>Yes</td><td>Markov chain</td><td>Analytic simulation</td><td>Suboptimal</td><td>40%</td></tr><tr><td>Li (2012)</td><td>Continuous</td><td>Poisson family</td><td>General</td><td>Heterogeneous</td><td>+∞</td><td>Response time</td><td>No</td><td>No</td><td>Queuing model</td><td>Analytic numerical</td><td>Suboptimal</td><td>-</td></tr><tr><td>Entezari-Maleki et al. (2017)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous</td><td>Finite</td><td>Response time throughput</td><td>Exponential</td><td>Yes</td><td>SAN</td><td>Fixed-point iteration</td><td>Suboptimal</td><td>5% - 10%</td></tr></tbody></table>
<table><caption>Table 1 (continued)</caption><thead><tr><th>Paper</th><th>Time</th><th>Arrivals</th><th>Service</th><th>Servers</th><th>Buffer</th><th>QoS</th><th>Time latency</th><th>Energetic latency</th><th>Model</th><th>Solution method</th><th>Strategy</th><th>Energy saving</th></tr></thead><tbody><tr><td>Kim et al. (2011)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Heterogeneous +∞</td><td>Waiting time</td><td>No</td><td>No</td><td>No</td><td>Queuing model</td><td>Analytic</td><td>Suboptimal</td><td>–</td></tr><tr><td>Slegers et al. (2008)</td><td>Continuous</td><td>Bi-Poisson</td><td>Exponential</td><td>Homogeneous</td><td>Response time</td><td>Exponential</td><td>Yes</td><td>Yes</td><td>MDP</td><td>Analytic heuristics</td><td>Suboptimal</td><td>–</td></tr><tr><td>Dyachuk and Mazucco (2010)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous +∞</td><td>Rejected jobs</td><td>No</td><td>Yes</td><td>Yes</td><td>Marakov chain</td><td>Experimental</td><td>Suboptimal</td><td>10% – 30%</td></tr><tr><td>Maccio and Down (2015)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous +∞</td><td>System jobs</td><td>Exponential</td><td>Yes</td><td>Yes</td><td>MDP</td><td>Analytic</td><td>Optimal</td><td>–</td></tr><tr><td>Xu and Tian (2008)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous +∞</td><td>Waiting time</td><td>Exponential</td><td>No</td><td>No</td><td>Marakov chain</td><td>Analytic</td><td>Suboptimal</td><td>–</td></tr><tr><td>Leng et al. (2016)</td><td>Discrete</td><td>Interrupted Bernoulli</td><td>Exponential</td><td>One server</td><td>Finite</td><td>Waiting time</td><td>No</td><td>Yes</td><td>MDP</td><td>Dynamic programming</td><td>Optimal</td><td>–</td></tr><tr><td>Yang et al. (2011)</td><td>Continuous</td><td>Poisson</td><td>Exponential</td><td>Homogeneous</td><td>Finite</td><td>Waiting jobs</td><td>No</td><td>Yes</td><td>MDP</td><td>Value iteration algorithm</td><td>Optimal</td><td>19%</td></tr><tr><td>Aidarov et al. (2013)</td><td>Continuous</td><td>Poisson family</td><td>Exponential family</td><td>Homogeneous +∞</td><td>Waiting time</td><td>No</td><td>No</td><td>No</td><td>Marakov chain</td><td>Analytic simulation</td><td>Suboptimal</td><td>20% – 35%</td></tr></tbody></table>

<figure><img src="image_5.png" /></figure>
<table><caption>Table 1 (continued)</caption><thead><tr><th>Paper</th><th>Time</th><th>Arrivals</th><th>Service</th><th>Servers</th><th>Buffer</th><th>QoS</th><th>Time latency</th><th>Energetic latency</th><th>Model</th><th>Solution method</th><th>Strategy</th><th>Energy saving</th></tr></thead><tbody><tr><td>Bayati (2018)</td><td>Discrete</td><td>General</td><td>Deterministic</td><td>Heterogeneous</td><td>Finite</td><td>Waiting jobs rejected jobs</td><td>No</td><td>Yes</td><td>MDP</td><td>Value iteration algorithm</td><td>Optimal</td><td>—</td></tr><tr><td>Bayati (2016)</td><td>Discrete</td><td>General</td><td>Deterministic</td><td>Homogeneous</td><td>Finite</td><td>Waiting jobs rejected jobs</td><td>No</td><td>No</td><td>Greedy algorithm</td><td>Numerical analysis</td><td>Suboptimal</td><td>—</td></tr><tr><td>Bayati et al. (2016)</td><td>Discrete</td><td>Markov chain</td><td>Deterministic</td><td>Homogeneous</td><td>Finite</td><td>Rejected jobs</td><td>No</td><td>Yes</td><td>Mar-kov chain</td><td>Numerical analysis</td><td>Suboptimal</td><td>—</td></tr><tr><td>Bayati (2023a)</td><td>Discrete</td><td>General</td><td>Deterministic</td><td>Homogeneous</td><td>Finite</td><td>Waiting jobs rejected jobs</td><td>No</td><td>Yes</td><td>MDP</td><td>Value iteration algorithm</td><td>Optimal</td><td>—</td></tr><tr><td>Bayati (2023b)</td><td>Discrete</td><td>General</td><td>General</td><td>Homogeneous</td><td>Finite</td><td>Waiting jobs rejected jobs</td><td>Yes</td><td>Yes</td><td>MDP</td><td>Value iteration algorithm</td><td>Optimal</td><td>—</td></tr><tr><td>Current work</td><td>Discrete</td><td>General</td><td>General</td><td>Heterogeneous</td><td>Finite</td><td>Waiting jobs rejected jobs</td><td>No</td><td>Yes</td><td>MDP</td><td>Greedy window algorithm</td><td>Suboptimal</td><td>—</td></tr></tbody></table>
# 1 Introduction

The rapid growth of data centers and the proliferation of cloud computing have led to significant energy and environmental challenges. Studies report a substantial increase in energy consumption and digital pollution caused by computing infrastructures, which now account for over 1.5% of global energy use. In 2020 alone, data centers and data transmission networks were responsible for approximately 330 million metric tons of CO₂-equivalent emissions, underscoring their growing environmental impact (Koomey 2011; Citaristi 2022).

Although data centers are designed to accommodate peak traffic loads, real-world measurements show that average traffic typically hovers around 60% of peak capacity (Benson et al. 2010). As a result, a large number of servers remain underutilized while still consuming up to 65% of their maximum power (Greenberg et al. 2009).

The study presented in Rteil et al. (2022) compares balanced and performance-oriented BIOS configurations across multiple server generations over the past decade, with the objective of evaluating potential energy savings. The results indicate that, under typical server utilization levels, there is limited justification for employing maximum performance settings, except in specific high-demand scenarios. This observation reinforces the critical need for energy-efficient strategies in data center management. A considerable share of data center energy consumption-and therefore operational cost-is associated with server operation and cooling infrastructure (Berl et al. 2010; Baliga et al. 2011; Lee and Zomaya 2012).

Considerable attention has been devoted to the advancement of server technologies and their associated cooling mechanisms. These efforts include the development of energy-efficient components and processors, the optimization of power distribution infrastructures, the design of more effective cooling systems, and the refinement of computing kernels (Grunwald et al. 2000; Benson et al. 2010; Patel et al. 2003; Jin et al. 2012).

Consequently, power optimization policies for server management have emerged as a crucial approach to balance the trade-off between maintaining Quality of Service (QoS) and reducing energy consumption. This balance involves the design of power management strategies that control server activation and deactivation states. The objective is to minimize energy usage while sustaining high QoS levels. Satisfying the QoS requirement generally necessitates keeping a large number of servers active, which lowers waiting times and job losses but increases energy consumption. In contrast, reducing energy consumption requires operating fewer servers, at the cost of longer waiting times and a higher risk of job rejection. The core challenge, therefore, lies in devising power management algorithms capable of jointly minimizing energy consumption, waiting times, and job losses, while maintaining acceptable QoS guarantees.

In the existing literature, numerous studies have investigated energy optimization in data centers, with a primary focus on continuous-time models. In contrast, comparatively fewer works have addressed discrete-time models (see Table 1).

Different studies have adopted various approaches to model arrival and service processes. Benini et al. (1999) and Gandhi et al. (2010a) employed both discrete-time and continuous-time Markov chains to represent these processes. In contrast, Nathuji
<figure><img src="image_6.png" /><figcaption>**Fig. 1** Illustration of the queuing model</figcaption></figure>

et al. (2007) relied on empirical benchmarks for modeling arrivals and services. A common trend in the literature is the use of Poisson arrival processes combined with exponential service times, as illustrated in Gandhi et al. (2010b) and Ghosh et al. (2013), reflecting a typical assumption in stochastic modeling.

Server heterogeneity is another critical aspect addressed in the literature. Benini et al. (1999) and Nathuji et al. (2007) examined heterogeneous server environments, incorporating variations in server capabilities into their models. In contrast, Gandhi et al. (2010a, b), and Ghosh et al. (2013) assumed homogeneous servers, thereby simplifying the analysis by considering identical performance across all machines. Furthermore, several other studies such as Bayati (2018), Nathuji et al. (2007), Li (2012), and Kim et al. (2011)-have investigated heterogeneous data centers, where jobs are processed by non-identical servers with varying speeds and power consumption profiles.

Quality of Service (QoS) considerations vary across the literature. Benini et al. (1999) addressed both waiting times and job rejections, whereas Nathuji et al. (2007) emphasized throughput and overall service quality. Gandhi et al. (2010a, b), and Ghosh et al. (2013) primarily focused on response time, with Ghosh et al. (2013) additionally considering job rejection. This diversity in QoS metrics highlights the multifaceted nature of performance modeling in data center environments.

Another aspect frequently examined in the literature is server latency, which may refer to either *time latency*—the duration required to power servers on or off (Mitrani 2013; Xu and Tian 2008)—or *energetic latency*, i.e., the additional energy consumed during these transitions (Dyachuk and Mazzucco 2010; Norman et al. 2005), or a combination of both (Mazzucco and Dyachuk 2012; Gandhi and Harchol-Balter 2011; Slegers et al. 2008; Entezari-Maleki et al. 2017; Maccio and Down 2015; Gandhi et al. 2013; Bayati 2023b).

Time latency has been modeled using various approaches, including Markov chains (Benini et al. 1999), deterministic delays (Gandhi et al. 2010a), and exponential distributions (Gandhi et al. 2010b; Ghosh et al. 2013). Energy-related latency has been explicitly incorporated in several studies, notably in Benini et al. (1999), Gan-
dhi et al. (2010a), and Gandhi et al. (2010b), underscoring the increasing emphasis on energy efficiency in data center operations.

Several studies, including those by Aidarov et al. (2013), Mazzucco and Dya-
chuk (2012), Schwartz et al. (2012), Gandhi and Harchol-Balter (2011), Slegers et al.
(2008), and Bayati et al. (2016), have investigated models grounded in specific man-
agement mechanisms, which often result in sub-optimal strategies such as threshold-
based policies.

The models employed across the literature also vary. Benini et al. (1999) utilized a Markov Decision Process (MDP), whereas Gandhi et al. (2010a) and Gandhi et al. (2010b) adopted Markov chain-based models. Nathuji et al. (2007) proposed an analytical prediction model, and Ghosh et al. (2013) applied a Stochastic Reward Network (SRN).

Solution methods differ significantly, ranging from linear programming tech-
niques (Benini et al. 1999), to analytical simulations (Gandhi et al. 2010a, b), and
experimental approaches (Nathuji et al. 2007). The optimality of the resulting strate-
gies also varies: Benini et al. (1999) achieved optimal constrained solutions, while
other works provided suboptimal outcomes.

Several studies have specifically addressed the search for optimal policies. In particular, works such as Benini et al. (1999); Efrosinin (2004); Luh and Viniotis (2002); Maccio and Down (2015); Yang et al. (2011); Leng et al. (2016); Bayati (2018, 2023a, b) formulate the energy optimization problem using MDP frameworks. These models are defined in either continuous or discrete time, and offer valuable insights into the structural properties of optimal policies-often exhibiting threshold-based characteristics.

Nevertheless, it is important to emphasize that MDP-based approaches face inher-
ent challenges related to the curse of dimensionality, particularly due to state space
explosion, which results in substantial computational costs in both time and memory.

More recent studies have continued to explore energy efficiency in data centers. Raizada et al. (2020) conducted a comprehensive survey on energy consumption in hyperscale data centers and reviewed optimization methods. Masanet et al. (2020) provided a recalibration of global data center energy-use estimates and discussed their implications, offering updated insights into consumption trends. Katal et al. (2023) reviewed software technologies aimed at improving energy efficiency in cloud data centers. More recently, Miao et al. (2024) proposed a deep reinforcement learning model for optimizing energy consumption in data center networks.

Lakhan et al. (2023) proposed a fuzzy decision-based evolutionary system to minimize energy consumption. Khan et al. (2022) employed machine learning for thermal classification and deep learning models to predict resource utilization and energy consumption, demonstrating the effectiveness of AI techniques and offering recommendations for more efficient energy management in data centers. Ding et al. (2020) applied Q-learning for dynamic task scheduling to enhance energy efficiency in cloud computing environments. Ilbeigi et al. (2020) explored the use of neural networks and genetic algorithms to predict and optimize energy consumption in buildings, with potential applicability to data center infrastructures.

An and Ma (2022) developed a dynamic energy consumption model that accounts for both IT equipment and cooling systems, enabling real-time analysis of energy

<figure><img src="image_7.png" /></figure>
usage and heat transfer within data centers. Karthikeyan et al. (2020) investigated energy consumption during virtual machine (VM) migration using hybrid swarm optimization techniques. These approaches provide comprehensive solutions for optimizing energy consumption associated with VM operations, which represent a critical component of efficient data center management.

Gao et al. (2020) investigated strategies to manage the instability of renewable energy sources in supporting cloud data centers. Peng et al. (2022) examined the potential for environmentally friendly and energy-efficient data centers through the integration of on-site renewable energy sources such as solar and wind. They proposed an energy management system incorporating a renewable-aware scheduler to optimize energy usage in data centers relying on both grid and renewable energy, thereby significantly improving renewable energy utilization.

Ajagekar and You (2024) introduced an innovative approach that combines variational quantum circuit learning with robust optimization to manage energy consumption and address uncertainties associated with renewable energy sources, enhancing both efficiency and sustainability. Zhao et al. (2023) focused on reducing energy consumption and carbon emissions in high-performance computing (HPC) environments by applying GPU power capping, effectively optimizing GPU performance while lowering energy usage.

Table 1 provides a summary of representative studies that have investigated various aspects of energy optimization in data centers. The final row outlines the distinguishing features of our proposed approach in comparison to the existing literature.

Previous research involving MDP-based methods for computing optimal strategies has encountered significant computational challenges when applied to large-scale data centers (Bayati 2023a). Markov Decision Processes (MDPs) can be viewed as a form of stochastic combinatorial optimization, suitable for modeling a wide range of decision-making problems where actions must be taken sequentially under uncertainty. MDPs are widely used in applications such as trajectory planning, resource management, and other constrained stochastic environments. By employing appropriate algorithms, it is theoretically possible to achieve optimal decision-making in these contexts.

However, solving MDPs becomes computationally intractable when applied to complex problems like energy optimization in data centers. This challenge is particularly acute when incorporating realistic factors such as server heterogeneity (Bayati 2018) and latency effects (Bayati 2023b). Furthermore, in scenarios where job arrival patterns follow a time-varying distribution, the MDP model must account for a potentially long planning horizon, denoted as *h*, which drastically increases the model's size. The primary limitation arises from the exponential growth of the state and action spaces with respect to *h*, making the identification of the optimal policy highly time- and memory-intensive. As a result, MDP-based approaches suffer from significant complexity in both computational time and memory requirements.

This paper addresses the challenge of reducing energy consumption in data centers while maintaining a high level of service quality. To this end, we introduce an algorithm designed to compute a suboptimal strategy that outperforms traditional threshold-based approaches. Crucially, our method produces a strategy that closely approximates the optimal solution without requiring the full construction of the MDP.
structure, which would otherwise involve enumerating all possible strategies. As a result, the proposed algorithm achieves significant reductions in both time and space complexity.

We employ the concept of histograms and associated operations to improve the modeling of job arrival and service processes. This approach enables the use of general discrete distributions derived from real-world traces, empirical observations, or live traffic measurements. In doing so, we move beyond conventional assumptions such as Poisson arrival rates and exponential service times. Based on this, we introduce a queuing model that provides a formal framework for addressing energy and performance management challenges in data centers.

We also revisit several classical methods for energy and QoS optimization. First, threshold-based strategies have been employed to identify optimal threshold values based on predefined system parameters (Bayati et al. 2015, 2016). Second, the Markov Decision Process (MDP) framework has been applied to determine optimal policies (Bayati 2023a, b, 2018). However, due to the high computational cost associated with solving full MDP models, alternative methods such as truncated MDPs and greedy algorithms have been proposed to reduce space and time complexity (Bayati 2016).

In this context, we introduce and detail our *Greedy Window* approach, designed to optimize both energy efficiency and Quality of Service (QoS) in data center environments. This method performs real-time monitoring of system states at each time slot—including job arrivals, queued and rejected jobs, and the number of active servers—and dynamically activates or deactivates servers to minimize energy consumption while preserving service quality. The procedure is outlined in Algorithm 4.

In this paper, certain aspects were intentionally simplified to focus on the core contribution. For instance, temporal latency was assumed to be negligible, as this factor has already been extensively analyzed in prior studies (Bayati 2016, 2018, 2023a, b; Bayati et al. 2015, 2016). The primary objective of this work is to demonstrate the effectiveness of the *Greedy Window* algorithm in computing a quasi-optimal strategy, thereby overcoming the limitations associated with traditional MDP-based methods.

The novelty of our contribution lies in the development of a stochastic model for Dynamic Power Management (DPM) in data centers, leveraging dynamic job arrival characterization through histograms constructed from real-world data. This approach departs from traditional methods that rely on predefined job arrival distributions. We propose an efficient *Greedy Window* algorithm that effectively handles real-time fluctuations in job arrivals while remaining both fast and memory-efficient. The algorithm approximates the optimal strategy without requiring the full construction of the Markov Decision Process (MDP), thereby overcoming the computational limitations typically associated with MDP-based methods.

Evaluations based on real Google traffic traces demonstrate the superiority of our approach across various data center scenarios, emphasizing its practical benefits compared to existing optimization techniques. By dynamically modeling job arrivals, our method adapts to real-world variability. Moreover, the *Greedy Window* algorithm exhibits linear time complexity with respect to the number of servers and quasi-linear complexity with respect to other system parameters.

<figure><img src="image_8.png" /></figure>
In addition, we present a comprehensive comparative analysis involving MDP, Truncated-MDP, and threshold-based strategies. This analysis highlights the practical effectiveness of our approach, particularly in large-scale settings where traditional methods suffer from severe computational overhead and state space explosion.

The remainder of this paper is organized as follows. We begin by defining the problem and outlining the key assumptions. Next, we review related work on energy optimization methods in data centers. We then present a detailed description of our *Greedy Window* optimization approach. This is followed by a comparative evaluation of our method against existing techniques, presented in the results and discussion section. Finally, we conclude the paper and suggest possible directions for future research.

## 2 Problem definition and assumptions

Let DC represent a data center composed of up to $\mathcal{M}$ identical servers. The data center receives job requests for the provided service. We assume that the job arrival process exhibits temporal variations, such as hourly or daily fluctuations. To capture this dynamic behavior, incoming jobs are modeled using a finite structure known as a histogram, which encodes a discrete probability distribution.

**Definition 1 (Histogram)** Let $A$ be a discrete random variable taking values in $\mathbb{N}$. The pair $\mathcal{H}_A = (S_A, P_A)$ denotes the histogram of $A$, where $P_A: \mathbb{N} \rightarrow [0, 1]$ is the probability mass function of $A$, and $S_A = \{i \in \mathbb{N} | P_A(i) > 0\}$ is the support of $P_A$.

The number of jobs arriving at DC during each time slot $t$ is represented by a histogram $\mathcal{H}_{A(t)}$. Here, $P_{A(t)}(i)$ denotes the probability of receiving $i$ job arrivals during time slot $t$. Importantly, we assume that these histograms are dynamically derived from real-world traces, empirical observations, or measurements of incoming traffic.

In a more general setting, the data center DC may consist of heterogeneous servers, grouped into several levels of energy consumption. For simplicity, we consider three levels, denoted by the set $G = \{\text{high, med, low}\}$ (with med referring to medium consumption). The number of active servers of type $g \in G$ at time $t$ is denoted by $m_g$, and $\text{max}_g$ denotes the maximum number of servers available at level $g$.

During one time unit, the number of jobs that can be processed by a server of type $g$ is described by a histogram $\mathcal{H}_{D_g}$, where $P_{D_g}(d)$ represents the probability of processing $d$ jobs. Consequently, the total number of operational servers at any time is given by $\sum_{g \in G} m_g$, and the total capacity of the data center is bounded by $\text{max} = \sum_{g \in G} \text{max}_g$.

For our analysis, we consider a time horizon of duration $h$, divided into discrete time slots. The queuing model is characterized as a batch arrival system with constant service rates and a finite-capacity buffer of size $b$.

At each time slot $t$, the number of jobs waiting in the buffer is denoted by $n(t)$, with its distribution represented by the histogram $\mathcal{H}_{N(t)}$. The number of servers actively
running at time t is denoted by $m(t)$. Any jobs rejected (i.e., lost) during this time slot are counted as $l(t)$, and their distribution is described by the histogram $\mathcal{H}_{L(t)}$.

We assume that, initially, there are $m_{g,0}$ operational servers of level $g \in G$, and $n_0$ jobs waiting in the buffer. The total number of active servers across all levels is constrained by the global upper bound $M$.

We initiate the job allocation process by first addressing the jobs already waiting in the buffer. Subsequently, newly arrived jobs are assigned to the available operational servers, and any remaining jobs are placed into the buffer, subject to its capacity. This allocation sequence-buffer, servers, then buffer again-is deliberately designed to preserve the First-In, First-Out (FIFO) scheduling principle.

The distribution of new jobs is therefore spread across all available system slots, including both idle servers and remaining buffer space. To model the system's evolution over time, we employ the histogram operators defined in Appendix A, which are used to inductively compute the evolution of the buffer distribution $\mathcal{H}_{N(t)}$.

$$ \mathcal{H}_{N(t+1)} \leftarrow MIN_b \left( \left( \mathcal{H}_{N(t)} \oplus \mathcal{H}_{A(t)} \right) \ominus \left( \sum_{g \in G} \mathcal{H}_{D_g} \times m_g \right) \right), \quad (1) $$

where

* $\mathcal{H}_{N(t)}$ is the histogram of jobs waiting in the buffer at time $t$,

* $\mathcal{H}_{A(t)}$ is the histogram of new job arrivals at time $t$,

* $\mathcal{H}_{D_g}$ is the service capacity histogram of a server of type $g$,

* $m_g$ is the number of active servers of type $g$,

* $b$ is the buffer capacity,

* $\oplus$ denotes the convolution (sum) of histograms,

* $\ominus$ represents histogram-based subtraction (removal of served jobs),

* $MIN_b$ truncates the histogram to enforce the buffer limit $b$.

When new incoming jobs are introduced into the system, they are subject to two capacity constraints: up to $m_g$ jobs can be processed by servers of type $g$, and up to $b$ jobs can reside in the buffer. Any excess jobs beyond this combined capacity cannot be accommodated and are therefore rejected.

In practice, the probability distribution of the number of rejected jobs is computed using the same histogram framework. Specifically, it is derived as follows:

$$ \mathcal{H}_{L(t+1)} \leftarrow \left( \mathcal{H}_{N(t)} \oplus \mathcal{H}_{A(t)} \ominus \left( \sum_{g \in G} \mathcal{H}_{D_g} \times m_g + b \right) \right), \quad (2) $$

where the expression inside the subtraction represents the system's total job-handling capacity (processing plus buffering), and the operator $\ominus$ identifies the number of jobs that exceed this capacity. The resulting histogram $\mathcal{H}_{L(t+1)}$ thus captures the distribution of jobs rejected at time $t+1$.
Energy consumption in this context depends on both the type and the state of each server, as well as on the transitions between states. Operational servers of type g consume energy at an average cost of $c_{M_g} \in \mathbb{R}^+$ per time slot. When a server is powered on, it incurs an additional energy cost $c_{o_n_g} \in \mathbb{R}^+$. Servers in the off state are assumed to have negligible consumption, and their cost is thus considered to be $c_{o_n} = 0$. The total energy cost at time slot t is computed as:

$$c_{\text{energy}}(t) = \sum_{g \in G} (m_g(t) \cdot c_{M_g} + \max\{0, m_g(t) - m_g(t-1)\} \cdot c_{o_n_g}). \quad (3)$$

As a Quality of Service (QoS) metric, we consider both the number of rejected jobs and the number of waiting jobs. Each rejected job incurs a penalty cost $c_L \in \mathbb{R}^+$, while each job waiting in the buffer is penalized by $c_N \in \mathbb{R}^+$ per time slot. The QoS cost at time slot t is calculated as:

$$c_{\text{QoS}}(t) = \sum_{i \in S_{L(t)}} P_{L(t)}(i) \cdot i \cdot c_L + \sum_{i \in S_{N(t)}} P_{N(t)}(i) \cdot i \cdot c_N, \quad (4)$$

where $P_{L(t)}(i)$ represents the probability of rejecting i jobs during slot t, and $P_{N(t)}(i)$ denotes the probability of having i waiting jobs in the buffer during slot t.

A dynamic power management system involves taking an action during each time slot, such as turning on or turning off a specific number of servers, to adjust the number of operational servers according to changes in incoming jobs. An effective strategy aims to identify a sequence of actions that minimizes the expected overall accumulated cost, which includes both the energetic cost and the performance cost. This expected cost incurred during each time slot can be expressed as a linear combination of energetic and QoS costs, referred to as the objective function:

$$c(t) = c_{\text{energy}}(t) + c_{\text{QoS}}(t). \quad (5)$$

## 3 Related optimization approaches

In this paper, we introduce a Greedy-Window approach for optimizing energy consumption and Quality of Service (QoS) in data centers. This method leverages key system parameters-including the number of arriving jobs, waiting jobs, rejected jobs, and available servers-to make server activation and deactivation decisions at each time slot. The objective is to minimize energy consumption while maintaining a high level of QoS.

To this end, it is necessary to evaluate the number of waiting and rejected jobs at each time step, which will be addressed in the following section. It is important to note that the parameters $n(t)$ (number of waiting jobs), $m(t)$ (number of active servers), and $l(t)$ (number of rejected jobs) are interdependent. As such, improvements in energy efficiency may come at the cost of degraded QoS, and vice versa.
To evaluate the effectiveness of our algorithm, we compare it against the following four baseline approaches:

(i) **Threshold-based approach:** This strategy uses predefined thresholds for server activation and deactivation, resulting in a sub-optimal policy due to its static nature.

(ii) **Markov Decision Process (MDP):** This method guarantees an optimal policy but suffers from the well-known issue of state space explosion, making it impractical for large-scale systems.

(iii) **Rolling horizon (truncated MDP):** This approach uses a finite planning window, similar to truncated value iteration, and provides a better sub-optimal policy than threshold methods. However, it still suffers from high computational complexity and memory usage.

(iv) **Greedy algorithm:** This method is both fast and memory-efficient but results in a strategy that is neither optimal nor quasi-optimal.

In the following, we briefly review these approaches before presenting the proposed *Greedy-Window* algorithm. Our algorithm computes a sub-optimal strategy that closely approximates the optimal solution while remaining efficient in both memory consumption and computational time.

## 3.1 Threshold-based optimization

In this approach, as detailed in Bayati et al. (2015, 2016), a predefined control mechanism is employed-though not necessarily optimal-to reduce the energy consumption of the data center while maintaining an acceptable level of QoS. Specifically, a double-threshold strategy is implemented, which relies on two integer parameters: an upper threshold *U* and a lower threshold *D*. The number of operational servers is adjusted based on the expected number of waiting jobs in the buffer.

At each time slot, this expected value is compared to the thresholds *D* and *U*. If the expected number of waiting jobs exceeds *U*, the number of active servers is increased by one.<fnref n="1" /> Conversely, if the expected value falls below *D*, the number of operational servers is decreased by one.

The objective of this threshold-based optimization is to determine the optimal pair (*U*, *D*) that minimizes a cost function combining energy consumption and QoS degradation penalties. Although this method offers reduced computational complexity and ease of implementation, its static nature often leads to sub-optimal performance in dynamic environments.

<footnote n="1">¹ In Bayati et al. (2015, 2016), a one-by-one server startup strategy was adopted to reduce peak energy usage caused by simultaneous server activation, thus promoting more sustainable energy consumption. A symmetric strategy was used for shutdowns, aiming to reduce sudden surges in task rejections associated with mass server deactivation, thereby contributing to a more stable QoS.</footnote>
## 3.2 MDP-based optimization

While we have extensively discussed the optimization methodology based on Markov Decision Processes (MDPs) in previous works (Bayati 2018, 2023a, b), we provide here a brief overview for completeness. MDP-based optimization entails the exhaustive exploration of all possible trajectories of length *h* from the system's initial state to the end of the analysis period. These trajectories correspond to decision sequences over time that influence the system's state evolution, as illustrated by the pink paths in Fig. 3a. Each path in this context represents a potential strategy. By computing the expected accumulated cost associated with each path, one can identify the optimal strategy. The total number of such paths is on the order of $O(M^h)$, where *M* is the maximum number of servers and *h* is the time horizon. Exhaustively exploring all paths leads to exponential complexity in both time and memory.

Nevertheless, applying the value iteration algorithm-based on dynamic programming principles-significantly reduces this complexity to a polynomial one. For a detailed complexity analysis, we refer the reader to the theorems established in Bayati (2018, 2023a, b).

## 3.3 Truncated MDP

The core idea behind the *rolling horizon procedure*-also referred to as the *truncated value iteration algorithm* (Wang and Liu 2011; Ilhuicatzi-Roldán and Cruz-Suárez 2013)-is to avoid the exhaustive exploration of all possible paths over the entire horizon *h* as required in classical MDP optimization. Instead, at each time slot, the search is restricted to a shorter planning horizon of length *w*, known as the *window*. This window defines the depth of the look-ahead used to determine the current decision (see Fig. 3b). In the literature, this concept is also known as the *sliding look-ahead window* (Gajane et al. 2018) or falls under the broader framework of *model predictive control* (MPC) (Arnold and Andersson 2011).

By integrating the window concept into the MDP framework, we obtain what is known as a *truncated MDP*, which balances computational feasibility and decision quality.

In Algorithm 1, for each time slot *t*, we seek the optimal sequence of actions {$m_g(t), m_g(t+1), \dots, m_g(t+w)$} for each server type *g* $\in$ *G*, to be executed over the time interval [*t*, *t* + *w*]. This sequence is selected to minimize the expected cumulative cost over the same interval. The first action of the sequence, $m_g(t)$, is then executed at time *t*.

At the next time step *t* + 1, the process is repeated: a new sequence of optimal actions over [*t* + 1, *t* + 1 + *w*] is computed, and only the first action $m_g(t+1)$ is applied. This iterative procedure continues until the end of the global horizon *h*, enabling an adaptive decision-making process while avoiding the exponential complexity of full-horizon MDP planning.
<table><caption>**Algorithm 1** Truncated value iteration algorithm.</caption><tr><td>Data: M, d, b, c<sub>M</sub>, c<sub>N</sub>, c<sub>L</sub>, c<sub>on</sub>, m<sub>g,0</sub>, n<sub>0</sub></td><td>1</td></tr><tr><td>Data: H<sub>A(0)</sub>, H<sub>A(1)</sub>, ..., H<sub>A(h)</sub></td><td>2</td></tr><tr><td>Result: m<sub>g</sub>(1), m<sub>g</sub>(2), ..., m<sub>g</sub>(h) for g ∈ G</td><td>3</td></tr><tr><td>m<sub>g</sub>(0) ← m<sub>g,0</sub>;</td><td>4</td></tr><tr><td>n(0) ← n<sub>0</sub>;</td><td>5</td></tr><tr><td>l(0) ← 0;</td><td>6</td></tr><tr><td>for t ← 0 to h do</td><td>7</td></tr><tr><td>/* Use a value iteration algorithm with a horizon w */ 8</td><td></td></tr><tr><td>/* to compute the optimal strategy over period [t..t+w] */ 9</td><td></td></tr><tr><td>(m<sub>g</sub>(t+0), m<sub>g</sub>(t+1), ..., m<sub>g</sub>(t+w) for g ∈ G) ← 10</td><td></td></tr><tr><td>value_itera<sub>tion</sub>(n(t-1), l(t-1), m<sub>g</sub>(t-1) for g ∈ G, [t..t+w]);</td><td></td></tr><tr><td>Compute n(t);</td><td>11</td></tr><tr><td>Compute l(t);</td><td>12</td></tr><tr><td>end</td><td>13</td></tr></table>

**Theorem 1** The computation time to determine the strategy using the truncated value iteration Algorithm 1 is in $O(h \times w \times M^2 \times b \times |S_A|)$.

**Proof** Let $w$ denote the length of the planning window. For each time slot $t \in \{0, \dots, h-1\}$, the algorithm explores all possible sequences of server activation levels over the window interval $[t, t+w]$. Let $m_k$ denote the number of operational servers at time $k$ within this window. For each time slot $k \in [t, t+w]$, all values $m_k \in \{0, \dots, M\}$ are considered, leading to a search over $M^{w+1}$ possible action sequences. However, since only one action $m_t$ is executed and the process restarts at each time step, we do not explore the full exponential tree. Instead, we perform a value iteration limited to a window of size $w$. At each time step, we compute the expected cost of each state-action pair over the window using histogram-based state transitions. The state space is composed of the number of active servers and the buffer occupancy, yielding $|S| = M \times b$ possible states. Additionally, computing the transition probabilities involves convolutions with the histogram of job arrivals, of size $|S_A|$. As a result, the complexity for computing the best action at a single time step is bounded by $O(w \times M^2 \times b \times |S_A|)$. Since this process is repeated at every time slot $t \in \{0, \dots, h-1\}$, the total complexity is: $O(h \times w \times M^2 \times b \times |S_A|)$. For a detailed analysis and validation of this complexity formulation, we refer the reader to Bayati (2018, 2023a, b). □

**Theorem 2** The memory (space) complexity of computing the strategy using the truncated value iteration Algorithm 1 is in $O(w \times M \times b)$.

**Proof** To compute the strategy via the truncated value iteration algorithm, the system's state at any given time slot $t$ is characterized by the number of operational servers $m(t)$, the number of waiting jobs in the buffer $n(t)$, and potentially the number of rejected jobs $l(t)$. However, since rejected jobs do not influence future state transitions directly, the relevant state space is defined by the tuple $(m(t), n(t))$. The num-
ber of possible values for $m(t)$ is bounded by $\mathcal{M}$, and for $n(t)$ by the buffer capacity $b$. Therefore, the total number of states at any given time is $\mathcal{M} \times b$. The algorithm applies a rolling horizon of length $w$, and for each time slot within this window, it must store the value function associated with each state. Thus, the memory required to store value functions across all slots in the window is: $O(w \times \mathcal{M} \times b)$. This space is needed to hold intermediate value estimates across the planning window during the execution of the truncated value iteration. Hence, the overall space complexity of the algorithm is $O(w \times \mathcal{M} \times b)$. □

### 3.4 Greedy optimization

As discussed in the previous sections, the Markov Decision Process (MDP) framework offers the advantage of enabling the computation of an optimal strategy by evaluating the expected accumulated cost associated with every possible sequence of actions. The strategy with the minimum total cost is then selected as optimal. As a baseline approach (see Bayati (2016)), we consider a simplified method that constructs a strategy by selecting, at each time slot, the action that minimizes the immediate (single-step) cost, without considering future consequences. The algorithm then proceeds to the next time slot and repeats the process (see Fig. 3c). This method belongs to the class of greedy algorithms (Black 2004). In our context, greedy optimization can be viewed as a special case of the truncated MDP framework, where the truncation parameter $w$ is set to 1. That is, the decision-making horizon is limited to a single time slot. This corresponds to Algorithm 2.

<table><caption>**Algorithm 2** Greedy optimization algorithm for one slot.</caption><tr><td>Data: $\mathcal{M}$, $d$, $b$</td><td>1</td></tr><tr><td>Data: $m_g(t-1)$ for $g \in G$, $\mathcal{H}_{N(t-1)}$, $\mathcal{H}_{A(t)}$</td><td>2</td></tr><tr><td>Data: $c_M$, $c_N$, $c_L$, $c_{on}$</td><td>3</td></tr><tr><td>Result: $m_g(t)$ for $g \in G$, $c(t)$</td><td>4</td></tr><tr><td>cost_min &larr; +&infin;;</td><td>5</td></tr><tr><td>for ($m_g \in G$) &larr; &prod;<sub>g&isin;G</sub> $\mathcal{M}_g$ do</td><td>6</td></tr><tr><td>N &larr; MIN<sub>b</sub>(($\mathcal{H}_{N(t-1)} \oplus \mathcal{H}_{A(t)}) - &sum;<sub>g&isin;G</sub> $\mathcal{H}_{D_g} \times m_g$);</td><td>7</td></tr><tr><td>$\tilde{m}_g$ &larr; max{0, $m_g - m_g(t-1)$} for $g \in G$;</td><td>8</td></tr><tr><td>c &larr; &sum;<sub>g&isin;G</sub> $c_{M_g} \times m_g + &sum;<sub>i&isin;S_N</sub> P_N(i) &times; i &times; c_N + &sum;<sub>i&isin;S_L</sub> P_L(i) &times; i &times; c_L + &sum;<sub>g&isin;G</sub> $c_{on_g} \times \tilde{m}_g$;</td><td>9</td></tr><tr><td>if c &lt; cost_min then</td><td>10</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;cost_min &larr; c;</td><td>11</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;servers_min_g &larr; $m_g$ for $g \in G$;</td><td>12</td></tr><tr><td>end</td><td>13</td></tr><tr><td>end</td><td>14</td></tr><tr><td>c(t) &larr; cost_min;</td><td>15</td></tr><tr><td>$m_g(t)$ &larr; servers_min_g for $g \in G$;</td><td>16</td></tr></table>
Given the system parameters known at time slot ($t-1$), our strategy consists in determining the optimal number of servers to activate at time slot $t$ in order to minimize the expected cost. At each time slot $t$, the algorithm proceeds as follows: for each possible configuration $m_g(t) \in \{0, 1, ..., M_g\}$, we compute the immediate expected cost $c(t)$. We then select the value of $m_g(t)$ that minimizes $c(t)$. Table 2 illustrates an example of the application of Algorithm 2, showing how the greedy decision is made at each step based solely on immediate cost minimization.

**Theorem 3** The space complexity of the Greedy Algorithm 2 is $O(q \log q)$, where $q = \max(S_A) + b$.

**Proof** The Greedy Algorithm 2 requires maintaining the probability distribution of the number of waiting jobs in the buffer. Since the buffer has a finite capacity $b$, this distribution can be stored in an array of size $O(b)$. To update this distribution at each time step, the algorithm performs a convolution between the arrival histogram $H_{A(t)}$ and the histogram of current waiting jobs. The size of the resulting histogram is bounded by $q = \max(S_A) + b$, where $S_A$ is the support of the arrival distribution. Using Fast Fourier Transform (FFT)-based convolution, this operation requires $O(q \log q)$ space. Thus, the overall memory required includes space for intermediate histograms and buffers, all of which are dominated by the convolution step. Therefore, the total space complexity is $O(q \log q)$. □

**Theorem 4** The time complexity of computing the strategy using Algorithm 2 is $O(h \times M \times q \log q)$, where $q = \max(S_A) + b$.

**Proof** The Greedy Algorithm 2 is executed over $h$ time slots. At each time slot $t$, the algorithm evaluates all possible configurations for the number of operational servers, i.e., $m_g(t) \in \{0, ..., M\}$, resulting in $M$ iterations. For each configuration, the algorithm computes the expected immediate cost, which requires evaluating the distribution of the number of waiting jobs. This involves a convolution between the histogram of job arrivals $H_{A(t)}$ and the histogram of currently waiting jobs $H_{N(t)}$. The size of the resulting histogram is bounded by $q = \max(S_A) + b$. Using the Fast Fourier Transform (FFT), this convolution can be performed in $O(q \log q)$ time. Therefore, the cost computation for each server configuration at a given time slot takes $O(q \log q)$ time, and the overall complexity per time slot is $O(M \times q \log q)$. Aggregating over all $h$ time slots, the total time complexity of the Greedy Algorithm is: $O(h \times M \times q \log q)$. □

While this method is evidently fast and avoids any explosion in the number of states, merely accumulating immediate minimum costs does not guarantee a strategy that

<table><caption>**Table 2** Example of optimization with identical servers. Suppose $M = 10$, $b = 15$, $d = 3$, $c_M = 11$, $c_N = 5$, $c_L = 0$ and for $t = 1$ we have: $H_N(t-1) = \Delta_5$ and $H_A(t) = \Delta_7$. In this case our algorithm chooses $m(t) = 4$ this value leads to the minimal cost</caption><tr><td>m(t)</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td></tr><tr><td>c(t)</td><td>60</td><td>56</td><td>52</td><td>48</td><td>44</td><td>55</td><td>66</td><td>77</td><td>88</td><td>99</td><td>110</td></tr></table>
closely approximates the optimal one. To address this limitation, we introduce the concept of a window, which enables the algorithm to incorporate limited foresight into the decision-making process and thus improve the quality of the resulting strategy.

## 4 Greedy-window optimization

It is evident that in the classical greedy algorithm, decisions are made by evaluating the system one time slot at a time. This approach can be extended by making decisions based on the analysis of w successive time slots, as demonstrated in Sect. 3.3. Such a generalization naturally leads to more informed decision-making and improved optimization. A larger window size w typically yields better results, but it also increases the computational burden. To avoid executing a full instance of the value iteration algorithm over the entire window of length w, we propose the Greedy-Window algorithm. This method computes a sub-optimal strategy over the interval $[t, t + w]$ while maintaining low computational complexity. For the sake of clarity, Algorithm 3 presents the Greedy-Window procedure in the simplified setting of identical servers.

<table><caption>**Algorithm 3** Greedy-window optimization algorithm.</caption><tr><td>Data: $\mathcal{M}$, $d$, $b$, $c_M$, $c_N$, $c_L$, $c_{on}$, $n_0$, $m_0$</td><td>1</td></tr><tr><td>Data: $\mathcal{H}_{A(0)}$, $\mathcal{H}_{A(1)}$, ..., $\mathcal{H}_{A(h)}$</td><td>2</td></tr><tr><td>Result: $m(1), \dots, m(h)$</td><td>3</td></tr><tr><td>$m(0) \leftarrow m_0$, $\mathcal{H}_{N(0)} \leftarrow \Delta_{n_0}$, $\mathcal{H}_{L(0)} \leftarrow \Delta_0$;</td><td>4</td></tr><tr><td>for $t \leftarrow 1$ to $h$ do</td><td>5</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;cost_min $\leftarrow +\infty$, servers_min $\leftarrow 0$;</td><td>6</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;for $m \leftarrow 0$ to $\mathcal{M}$ do</td><td>7</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$N \leftarrow \mathcal{H}_{N(t-1)}$;</td><td>8</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$L \leftarrow \mathcal{H}_{L(t-1)}$;</td><td>9</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\tilde{m} \leftarrow \max\{0, m - m(t - 1)\}$;</td><td>10</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;accumulated_cost $\leftarrow \tilde{m} \times c_{on}$;</td><td>11</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;for $k \leftarrow t$ to $t + w$ do</td><td>12</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$N \leftarrow \text{MIN}_b((N \oplus \mathcal{H}_{A(k)}) - d \times m)$;</td><td>13</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$L \leftarrow (N \oplus \mathcal{H}_{A(k)}) - (d \times m + b)$;</td><td>14</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$c \leftarrow c_M \times m + \sum_{i \in S_L} P_N(i) \times i \times c_N + \sum_{i \in S_L} P_L(i) \times i \times c_L$;</td><td>15</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;accumulated_cost $\leftarrow$ accumulated_cost + $c$;</td><td>16</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;end</td><td>17</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;if $accumulated_cost < cost_min$ then</td><td>18</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cost_min $\leftarrow$ accumulated_cost;</td><td>19</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;servers_min $\leftarrow m$;</td><td>20</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;end</td><td>21</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;end</td><td>22</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;$m(t) \leftarrow$ servers_min;</td><td>23</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{H}_{N(t)} \leftarrow \text{MIN}_b((\mathcal{H}_{N(t-1)} \oplus \mathcal{H}_{A(t)}) - d \times m(t))$;</td><td>24</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{H}_{L(t)} \leftarrow (\mathcal{H}_{N(t-1)} \oplus \mathcal{H}_{A(t)}) - (d \times m(t) + b)$;</td><td>25</td></tr><tr><td>end</td><td>26</td></tr></table>
This sub-optimal strategy is defined by selecting the best action within a restricted set of strategies that maintain the same server configuration over the entire window $[t, t + w]$. In other words, at each time slot $t$, the algorithm evaluates the impact of persisting with a fixed action throughout the window and selects the action that minimizes the accumulated cost over that interval. It is important to emphasize that this evaluation is performed at every time slot-not every $w$ slots-thus allowing for fine-grained adaptation over time. Conceptually, the *Greedy-Window* algorithm explores only a subset of possible paths, specifically those that follow a constant action across the $w$-slot window. Each such path is referred to as a *direction*, representing a trajec-tory where the same decision is applied at each slot (see Fig. 3d).

**4.1 Space time complexities**

**Theorem 5** The space complexity of Greedy-window Algorithm 3 is in $O(q \log(q))$ with $q = \max(S_A) + b$.

**Proof** See proof of Theorem 3.

<figure><img src="image_9.png" /></figure>

**Theorem 6** The time complexity of computing the strategy using the Greedy-Window Algorithm 3 is $O(w \times h \times M \times q \log q)$, where $q = \max(S_A) + b$.

**Proof** The Greedy-Window Algorithm operates over a time horizon of $h$ slots. At each time slot $t$, the algorithm evaluates $M$ possible configurations for the number of active servers. For each configuration, it computes the expected cumulative cost over a window of $w$ successive slots, assuming the same action is applied across the entire window. Within each evaluation, the algorithm updates the distribution of waiting and

<figure><img src="image_10.png" /><figcaption>**Fig. 2** Relationship between the window size and optimization efficiency</figcaption></figure>

<figure><img src="image_11.png" /></figure>
<figure><img src="image_12.png" /><figcaption>Fig. 3 Comparison of the various path exploration approaches</figcaption></figure>

rejected jobs by performing convolutions between histograms of job arrivals and wait-
ing jobs. Each convolution involves a histogram of size at most $a = \max(S_A) + b$, where $S_A$ is the support of the arrival distribution and $b$ is the buffer capacity. Using the Fast Fourier Transform (FFT), these convolutions can be computed in $O(q \log q)$ time. Therefore, the complexity per time slot is $O(w \times M \times q \log q)$, and over the entire horizon $h$, the total computation time is: $O(w \times h \times M \times q \log q)$. $\square$

## 4.2 Selection of the window size

The choice of the window size $w$ plays a critical role in the performance of the Greedy-Window algorithm. As illustrated in Fig. 2, cost optimization is limited when $w$ is small (i.e., $w < 5$). However, a substantial improvement is observed for larger values of $w$ (i.e., $w \ge 5$). To ensure that the computed strategy closely approximates
the optimal one, it is therefore important to select a sufficiently large window size, typically $w \ge 5$.

At the same time, increasing $w$ also raises the computational cost. Hence, to balance solution quality and efficiency, it is recommended to keep $w$ within a reasonable upper bound (e.g., $w \le 10$), which has proven sufficient in practice.

Figure 2 shows the daily accumulated cost produced by the Greedy-Window algorithm as a function of the window size $w$ under various traffic patterns extracted from the Google cluster trace (Wilkes 2011; Reiss et al. 2011). The simulation uses the following parameters: $M = 150$, $d = 1$, $b = 1000$, $h = 1000$, $c_M = 10$, $c_N = 10$, and $c_L = 10$.

It is evident from the results that a significant cost reduction can be achieved even with a relatively small window size ($w \ll h$). For instance, under the arrival pattern observed on May 10, 2011, analyzing only a few successive time slots (i.e., $w > 1$) leads to an improvement of approximately 53% in the accumulated cost compared to the baseline case with $w = 1$.

This result highlights the practical benefit of incorporating short-term foresight in decision-making, as even modest window sizes yield considerable gains in performance while preserving computational efficiency.

## 4.3 Real time version

The optimization approach based on the Greedy-Window algorithm offers a compelling compromise between solution quality and computational efficiency. By incorporating limited foresight into each decision step, it significantly improves performance over purely greedy strategies, while avoiding the computational burden associated with full-horizon dynamic programming methods.

The Greedy-Window algorithm effectively mitigates the issues related to memory usage and computational time, avoiding the exponential complexity growth observed in MDP-based algorithms. Specifically, while MDP methods typically exhibit quadratic time complexity with respect to $M$, the Greedy-Window algorithm achieves a linear dependency, thus enabling more scalable optimization. Moreover, this algorithm supports real-time (online) execution, as it determines the action to take at each time slot independently, without requiring prior knowledge of the time horizon $h$. An example of such an online version is provided in Algorithm 4, which maintains a list named `arrival_history` to store the number of arrivals in previous time slots. To ensure efficiency and accuracy, this list should be bounded in size by periodically removing older entries. This prevents performance degradation and maintains a representative histogram of recent arrivals, enabling better responsiveness to evolving traffic patterns.
<table><caption>**Algorithm 4** The online version of the greedy-window algorithm.</caption><tr><td>Data: M, d, b</td><td>1</td></tr><tr><td>Data: c<sub>M</sub>, c<sub>N</sub>, c<sub>L</sub>, c<sub>on</sub></td><td>2</td></tr><tr><td>arrival_history ← [];</td><td>3</td></tr><tr><td>H<sub>A</sub> ← Δ<sub>0</sub></td><td>4</td></tr><tr><td>foreach beginning of slot t do</td><td>5</td></tr><tr><td>cost_min ← +∞;</td><td>6</td></tr><tr><td>servers_min ← 0;</td><td>7</td></tr><tr><td>/* Request the state of the system */</td><td>8</td></tr><tr><td>a ← the number of arrival jobs received in the last slot;</td><td>9</td></tr><tr><td>n ← the number of waiting jobs;</td><td>10</td></tr><tr><td>m ← the number of operational servers;</td><td>11</td></tr><tr><td>/* Add a to the arrival history */</td><td>12</td></tr><tr><td>arrival_history ← arrival_history + [a];</td><td>13</td></tr><tr><td>/* Use arrival history to update arrival histogram */</td><td>14</td></tr><tr><td>H<sub>A</sub> ← compute Chinese history);</td><td>15</td></tr><tr><td>for m ← 0 to M do</td><td>16</td></tr><tr><td>N ← Δ<sub>n</sub>;</td><td>17</td></tr><tr><td>m ← max{0, m − m(t − 1)};</td><td>18</td></tr><tr><td>accumulated_cost ← m × c<sub>on</sub>;</td><td>19</td></tr><tr><td>for k ← 1 to w do</td><td>20</td></tr><tr><td>N ← MIN<sub>b</sub>((N ⊕ H<sub>A</sub>) − d × m);</td><td>21</td></tr><tr><td>L ← (N ⊕ H<sub>A</sub>) − (d × m + b);</td><td>22</td></tr><tr><td>c ← c<sub>M</sub> × m + Σ<sub>i∈S<sub>N</sub></sub> P<sub>N</sub>(i) × i × c<sub>N</sub> + Σ<sub>i∈S<sub>L</sub></sub> P<sub>L</sub>(i) × i × c<sub>L</sub>;</td><td>23</td></tr><tr><td>accumulated_cost ← accumulated_cost + c;</td><td>24</td></tr><tr><td>end</td><td>25</td></tr><tr><td>if accumulated_cost < cost_min then</td><td>26</td></tr><tr><td>cost_min ← accumulated_cost;</td><td>27</td></tr><tr><td>servers_min ← m;</td><td>28</td></tr><tr><td>end</td><td>29</td></tr><tr><td>end</td><td>30</td></tr><tr><td>m ← servers_min;</td><td>31</td></tr><tr><td>set the number of operational servers to m;</td><td>32</td></tr><tr><td>end</td><td>33</td></tr></table>

# 5 Results and comparison

In this section, we present a comparative analysis of the performance and energy efficiency achieved by the different optimization methods discussed in this work. All methods are evaluated using real traffic traces to model job arrivals, ensuring realistic and representative conditions for assessment.

Specifically, we utilize the *clusterdata-2011-2* trace from the publicly available dataset (Wilkes 2011; Reiss et al. 2011). Our analysis focuses on the subset of data corresponding to job events directed to a specific Google data center during the entire month of May 2011. These job events are structured as an eight-attribute table, from which we extract the * timestamps column that records job arrival times in microseconds*.
<figure><img src="image_13.png" /><figcaption>Fig. 4 Arrival traffic distribution</figcaption></figure>

<figure><img src="image_14.png" /></figure>
To ensure a statistically sound modeling of the arrival process, we employ the turning point test (Kendall 1973) to validate the independence and identical distribution (iid) assumption. This enables the construction of an empirical histogram that captures the arrival distribution while preserving iid-ness (Bayati 2018). For further comparison, we also conduct experiments using a synthetic uniform arrival distribution.

In this analysis, we ensure that all methods are evaluated under consistent conditions, using the same set of parameters and assumptions. In the following sections, we detail the experiments conducted to compare the different optimization methods presented in this work.

# 5.1 Mid-scale data center

## 5.1.1 Real arrival jobs

In this experiment, job arrivals are modeled using real trace data, as illustrated in Fig. 4. The data center configuration corresponds to a relatively small-scale scenario, where the parameters $M$, $b$, and $|S_A|$ are each approximately 100. Detailed parameter values for this setup are provided in Table 3.

Figure 5 presents the results obtained using the Threshold-based method. The region where the threshold pair ($U, D$) is infeasible (i.e., $D > U$) is highlighted in blue. In the first sub-figure, we observe that the energy consumption cost is higher for small values of $U$ and $D$, as this configuration tends to activate a large number of servers early, regardless of actual demand. The second sub-figure shows that the QoS cost increases for large values of $U$ and $D$, due to a delayed server activation policy that leads to more job losses or longer waiting times. The third sub-figure presents the total cost, combining both energy and QoS costs. The fourth sub-figure highlights two regions of interest: the green region represents threshold pairs that achieve near-optimal performance, defined as cost values within 5% of the minimum cost (i.e., $min\_cost \le cost \le min\_cost + 0.05 \times min\_cost$); the red region corresponds to configurations with the highest total cost. Overall, these visualizations illustrate the trade-off inherent in threshold-based control: reducing energy consumption typically comes at the expense of QoS, and vice versa. Finding an appropriate ($U, D$) pair is therefore critical to balancing these conflicting objectives.

Figure 6 provides a comparative overview of the total cost associated with each optimization method. As expected, the MDP approach achieves the best results, delivering the lowest cost due to its ability to compute the optimal policy. The Truncated-MDP method follows closely, offering strong performance while reducing computational demands compared to the full MDP. The Greedy-Window algorithm ranks third, producing results that are near-optimal while maintaining reasonable computational efficiency. The Threshold-based method comes next, with a cost significantly higher than the optimal, reflecting its static and heuristic nature. Lastly, the classical Greedy algorithm exhibits the highest cost, as it makes decisions based solely on immediate costs without any foresight. In terms of memory and computation time, the Greedy and Greedy-Window algorithms are the most efficient, requiring minimal space and enabling fast execution. The Threshold method ranks second, with mod-
<table><caption>**Table 3** Settings of the numerical analysis</caption><thead><tr><th>Parameter</th><th>|G|</th><th>M</th><th>H<sub>D</sub></th><th>b</th><th>h</th><th>w</th><th>E(H<sub>A</sub>)|S<sub>A</sub>|</th><th>c<sub>M</sub></th><th>c<sub>N</sub></th><th>c<sub>On</sub></th></tr></thead><tbody><tr><td>Value</td><td>1</td><td>100</td><td>Δ<sub>2</sub></td><td>100</td><td>200</td><td>5</td><td>49</td><td>99</td><td>0.1</td><td>0.1</td><td>0.1</td></tr><tr><td>Unit</td><td>Level</td><td>Server</td><td>Job/server</td><td>Job</td><td>Slot</td><td>Slot</td><td>Job</td><td>-</td><td>$</td><td>$</td><td>$</td></tr></tbody></table>

<figure><img src="image_15.png" /><figcaption>**Fig. 5** Threshold results</figcaption></figure>

erate space and time usage. In contrast, both MDP and Truncated-MDP exhibit the highest resource demands, requiring substantial memory and computational time to evaluate large state spaces and perform dynamic programming operations.

### 5.1.2 Uniform arrival jobs

From an academic perspective, fully understanding the performance and limitations of the proposed algorithm requires evaluating it under diverse conditions. In this experiment, we consider a uniform probability distribution for job arrivals, where each possible number of incoming jobs is equally likely. This setup enables us to assess the behavior of the algorithms in the absence of temporal patterns or skewed distributions. Figure 7 illustrates the results obtained under this uniform arrival model. The data center parameters remain relatively small, with *M*, *b*, and *|S<sub>A</sub>|* all approximately equal to 100, as detailed in Table 3.
<figure><img src="image_16.png" /><figcaption>Fig. 6 Cost, and space-time computation comparison</figcaption></figure>

Figure 7, when compared to Fig. 6, highlights consistent performance trends across both real and uniform job arrival scenarios. The MDP approach remains the most effective method, achieving the lowest overall cost by computing the optimal policy regardless of the arrival distribution. Truncated-MDP also demonstrates strong performance, closely approximating the MDP results while being more computationally feasible.

The Greedy-Window algorithm emerges as a practical compromise, offering reasonable performance with significantly reduced resource requirements. It is particu-
<figure><img src="image_17.png" /><figcaption>Fig. 7 Cost, and space-time computation comparison for uniform arrival traffic distribution</figcaption></figure>

larly well-suited for environments where computational constraints limit the use of
full dynamic programming.

The Threshold method exhibits moderate performance. While it struggles to adapt to the variability in real traces, it performs better under uniform arrivals, where its static control policy aligns more naturally with the regularity of the input.

Finally, the Greedy algorithm remains the least effective across both settings, as its lack of foresight prevents it from adapting to workload fluctuations, resulting in higher overall costs.

**5.2 Big data center**

In this experiment, job arrivals are modeled using real trace data, as illustrated in Fig. 8. The data center is configured with relatively large parameter values, where

<figure><img src="image_18.png" /></figure>
<figure><img src="image_19.png" /><figcaption>Fig. 8 Arrival traffic distribution</figcaption></figure>

<table><caption>**Table 4** Settings of the numerical analysis</caption><thead><tr><th>Parameters</th><th><i>M</i></th><th><i>d</i></th><th><i>b</i></th><th><i>h</i></th><th><i>w</i></th><th><i>E</i>(<i>H</i><sub>A</sub>)</th><th>|<i>S</i><sub>A</sub>|</th><th>max(<i>S</i><sub>A</sub>)</th><th><i>c</i><sub>M</sub></th><th><i>c</i><sub>N</sub></th><th><i>c</i><sub>On</sub></th></tr></thead><tbody><tr><td>Value</td><td>200</td><td>1</td><td>200</td><td>200</td><td>5</td><td>50</td><td>299</td><td>328</td><td>0.1</td><td>0.1</td><td>0.1</td></tr><tr><td>Unit</td><td>Server</td><td>Job/server</td><td>Job</td><td>Slot</td><td>Slot</td><td>Job</td><td>-</td><td>Job</td><td>$</td><td>$</td><td>$</td></tr></tbody></table>

$M$, $b$, and $|S_A|$ are all approximately 200. Detailed configuration parameters for this experimental setup are provided in Table 4.

Due to extensive execution times and memory limitations, both the MDP and Truncated-MDP approaches were unable to complete the strategy computation under this experimental setup. Figure 9 presents the comparative cost results for the remaining methods. The Greedy-Window algorithm achieves the lowest total cost, demonstrating its effectiveness even in large-scale scenarios.

The classical Greedy algorithm ranks second, although it incurs a significantly higher cost compared to the Greedy-Window method. The Threshold-based method follows, with performance further behind. In terms of space and time efficiency, both the Greedy and Greedy-Window algorithms clearly stand out. They require minimal memory and allow for rapid execution. The Threshold method comes next, with moderate computational requirements. By contrast, the MDP and Truncated-MDP methods exhibit prohibitive resource demands, placing them last in terms of practical feasibility for large-scale environments.

## 5.3 Varying unitary cost parameters

Additional experiments were conducted to analyze the system's behavior under varying unitary cost parameters: $c_N$ (cost per time slot for a waiting job), $c_L$ (penalty cost for lost jobs), $c_M$ (cost per time slot for maintaining an active server), and $c_{on}$ (startup cost for powering on a server).

These experiments aim to evaluate how changes in these cost components influence the overall performance and resource efficiency of the system. The correspond-
<figure><img src="image_20.png" /><figcaption>Fig. 9 Cost, space and computation-time comparison</figcaption></figure>

ing results are presented in Fig. 10, offering insights into the sensitivity of each method with respect to these parameters.

In each subfigure of Fig. 10, two unitary cost parameters are varied simultaneously over the range [0, 100], while the remaining cost parameters are held constant at a value of 50. The system configuration used for these experiments is derived from the baseline parameters presented in Table 3.

For ease of comparison, the resulting total costs are normalized within the range [0, 1], where 0 corresponds to the minimum observed cost and 1 to the maximum. This normalization allows for a clearer visualization of the sensitivity of the system's performance to the various cost components.

<figure><img src="image_21.png" /></figure>
<figure><img src="image_22.png" /><figcaption>**Fig. 10** Varying pairs of unitary cost parameters</figcaption></figure>
The first subfigure (top-left) is a heatmap representing the expected cost as a func-
tion of varying parameters $c_N$ (cost per slot for a waiting job) and $c_M$ (cost per slot
for an active server). Red areas indicate high costs and are located where both $c_N$ and
$c_M$ are elevated. This implies that the penalties for waiting jobs and the energy costs
for running servers are critical factors in cost optimization. Blue areas indicate low
costs and are found where $c_N$ or $c_M$ is low. This zone demonstrates that when the
costs associated with waiting jobs or active servers are low, the overall expected cost
is also reduced. The heatmap shows a gradual transition from blue to red diagonally
across the image, highlighting that both $c_N$ and $c_M$ significantly influence the total
cost, with $c_N$ having a more substantial impact.

The second subfigure (top-right) is a heatmap representing the expected cost as a function of varying parameters $c_N$ (cost per slot for a waiting job) and $c_{on}$ (cost for turning on a server). Red areas indicate high costs and are located where $c_{on}$ is high, regardless of variations in $c_N$. This implies that the penalties for starting a server are critical factors in cost optimization. Blue areas indicate low costs and are found where $c_{on}$ is low, independent of variations in $c_N$. This again implies that the penalties for starting a server are crucial in cost optimization. Additionally, we observe that when $c_{on}$ exceeds 50, the value of $c_N$ begins to slightly influence the total cost, causing it to increase.

The third subfigure (middle-left) is a heatmap representing the expected cost as a function of varying parameters $c_L$ (cost for losing a job) and $c_{on}$ (cost for turning on a server). Yellow areas indicate high costs and are located where $c_L$ is high, regardless of variations in $c_{on}$, especially when $c_{on}$ exceeds 20. This implies that the penalties for losing a job are more critical than the cost of starting a server. Blue areas indicate low costs and are found where $c_L$ is low, independently of variations in $c_{on}$. This again implies that the penalties for losing a job are crucial in cost optimization. Additionally, we observe that as $c_L$ increases, the total cost gradually increases, may indicating a certain proportionality between the total cost and $c_L$.

<figure><img src="image_23.png" /><figcaption>**Fig. 11** Average cost per slot for MDP and window-greedy algorithm when varying *h*</figcaption></figure>

<figure><img src="image_24.png" /></figure>
The fourth subfigure (middle-right) is a heatmap representing the expected cost as a function of varying parameters $c_L$ (cost for losing a job) and $c_M$ (cost for running a server for a slot). Red areas indicate high costs and are located where both $c_L$ and $c_M$ are high, but the impact of $c_M$ is more pronounced, especially when $c_M$ exceeds 40. This implies that the penalties for losing a job and the cost of running a server are both critical factors for high total cost. Blue areas indicate low costs and are found where $c_L$ is low, independently of variations in $c_M$. This implies that the penalties for losing a job are crucial for low-cost optimization, regardless of $c_M$.

The last subfigure (bottom-right) is a heatmap representing the expected cost as a function of varying parameters $c_L$ (cost of losing a job) and $c_N$ (cost for waiting per slot). We observe that the total cost gradually increases as both parameters incrementally rise, with the cost being low (blue region) when both $c_L$ and $c_N$ are low. However, when $c_L$ exceeds a value of 60, the cost becomes primarily dependent on $c_L$ and becomes very high (red zone), regardless of the value of $c_N$. This implies that the penalties for losing jobs are crucial in explaining high total costs.

## 5.4 Comparison between Greedy-Window and MDP

Figure 11 presents a comparison of the average cost per slot for the MDP (Markov Decision Process) and the *Greedy-Window* algorithms as a function of the planning horizon *h*. The graph displays the normalized accumulated cost per slot on the *y*-axis and the planning horizon *h* on the *x*-axis. The blue curve corresponds to the MDP algorithm, while the red curve represents the Greedy-Window algorithm. Across all values of *h*, the MDP algorithm consistently yields a slightly lower cost per slot than the Greedy-Window algorithm. However, the difference remains minimal, with the Greedy-Window algorithm producing a cost less than 2% higher than that of the MDP. This demonstrates that the Greedy-Window approach closely approximates the performance of the optimal MDP policy.

<figure><img src="image_25.png" /><figcaption>**Fig. 12** Expected cost for a limited amount of time</figcaption></figure>
As *h* increases, both algorithms exhibit stabilization in their accumulated cost per slot, indicating convergence to a steady-state regime. While the MDP shows a marginal increase in cost with increasing *h*, it remains relatively flat beyond *h* = 50. Similarly, the Greedy-Windows algorithm stabilizes at a slightly higher cost level. Overall, while the MDP algorithm remains marginally more effective, particularly for longer planning horizons, the Greedy-Windows algorithm offers a highly competitive and quasi-optimal alternative. Its ability to approximate optimal performance with significantly lower computational cost makes it a practical and efficient choice, especially in environments with limited computational resources or where real-time responsiveness is required.

## 5.5 Comparison between Greedy-Windows and truncated MDP

As confirmed by the previous results, the Truncated MDP algorithm generally yields lower total costs compared to the Greedy-Windows algorithm. However, this improvement comes at the expense of significantly higher computation time. This observation raises an important question: if both algorithms were constrained to run for approximately the same amount of time, which one would produce better results? To address this question, we conduct a set of experiments where the window length *w* is varied from 1 to 25 for both algorithms. The values of *w* are adjusted such that the runtimes of the two algorithms are approximately equal. This setup allows for a fair comparison based on equal time budgets. It is important to note that, for the Truncated MDP algorithm, we only measure the time required to compute the optimal policy. The time needed to build the MDP model is excluded from the comparison, as it is independent of the parameter *w* and would otherwise bias the evaluation unfairly. Figure 12 presents a comparison of the expected cost as a function of the allocated computation time for two algorithms: the Truncated MDP and the Greedy-Windows algorithm.

The *y*-axis represents the expected total cost, while the *x*-axis indicates the computation time allocated to each method. The blue curve corresponds to the Truncated MDP algorithm, and the red curve represents the Greedy-Windows algorithm. Initially, both algorithms exhibit higher expected costs, which rapidly decrease as more computation time is allocated. The Truncated MDP stabilizes more quickly, reaching a near-optimal cost level with less additional computation. The Greedy-Windows algorithm converges more gradually but ultimately reaches a cost level comparable to that of the Truncated MDP. The final cost difference between the two algorithms is minimal-less than 2%-which confirms that the Greedy-Windows algorithm closely approximates the performance of the Truncated MDP. These results underscore the strong cost-minimization capabilities of the Truncated MDP, but also highlight its higher computational complexity. In contrast, the Greedy-Windows algorithm offers a compelling trade-off: while slightly less efficient in terms of cost, it performs very closely to the Truncated MDP and requires significantly less computation. This makes it a competitive and practical alternative in scenarios with limited computational resources or real-time constraints.
<figure><img src="image_26.png" /><figcaption>**Fig. 13 Performance comparison**</figcaption></figure>
## 5.6 Performance evaluation

This section presents a comprehensive experimental evaluation of the computation time required by the five optimization methods under consideration. While both time and memory usage were initially investigated, we focus here exclusively on computation time due to the strong correlation between these two factors. The analysis explores the scalability and practical performance of each method under varying system parameters, including buffer size *b*, total number of servers *M*, length of the arrival histogram $|S_A|$, and planning horizon *h*.

Figure 13a illustrates how computation time evolves with increasing buffer size *b*. Although all methods exhibit growth in computation time, the rate and magnitude differ significantly. The *Greedy* and *Greedy-Windows* algorithms demonstrate excellent efficiency, with minimal increases even for large buffer sizes. In contrast, the *MDP* and *Threshold* methods show markedly steeper growth, suggesting reduced scalability. The *Truncated-MDP* approach offers intermediate performance, reducing the computational load relative to the full *MDP*, but remaining more costly than the *Greedy*-based methods.

Figure 13b examines computation time as a function of the number of servers *M*. The *MDP* and *Truncated-MDP* methods display a clear nonlinear increase, reflecting their sensitivity to system size due to the expansion of the decision space. In contrast, both *Greedy* and *Greedy-Windows* algorithms exhibit stable performance, with computation times remaining consistently low across the full range of *M*. The *Threshold* method also maintains constant computation time, though with a higher baseline compared to the *Greedy* methods.

Figure 13c explores the impact of the arrival histogram length $|S_A|$. The results show that the *Greedy* and *Greedy-Windows* algorithms scale gracefully with increasing histogram length, maintaining computation times below 0.6 s. By contrast, both *MDP* and *Truncated-MDP* methods experience rapid growth in execution time, highlighting their sensitivity to the complexity of arrival patterns.

Figure 13d presents computation time as a function of the planning horizon *h*. Most methods show slow or negligible increases as *h* grows. The *Threshold* method is the exception, with a linear increase in computation time from 0.4 to over 4 s. The *Greedy* and *Greedy-Windows* algorithms remain the most efficient, with computation

<table><caption>**Table 5** Time complexity comparison: Notice that the complexities are for the homogeneous model without considering latency</caption><thead><tr><th></th><th>Time</th><th>Space</th></tr></thead><tbody><tr><td>Thresholds<br>U/D</td><td>O(hb<sup>2</sup>(b + max(S<sub>A</sub>)) log(b + max(S<sub>A</sub>)))</td><td>O(b<sup>2</sup>)</td></tr><tr><td>MDP</td><td>O(hM<sup>2</sup>b|S<sub>A</sub>|)</td><td>O(h × M × b)</td></tr><tr><td>Truncated<br>MDP</td><td>O(whM<sup>2</sup>b|S<sub>A</sub>|)</td><td>O(w × M × b)</td></tr><tr><td>Greedy</td><td>O(hM(b + max(S<sub>A</sub>)) log(b + max(S<sub>A</sub>)))</td><td>O((b + max(S<sub>A</sub>)) × log(b + max(S<sub>A</sub>)))</td></tr><tr><td>Greedy-window</td><td>O(whM(b + max(S<sub>A</sub>)) log(b + max(S<sub>A</sub>)))</td><td>O((b + max(S<sub>A</sub>)) × log(b + max(S<sub>A</sub>)))</td></tr></tbody></table>
times below 0.1 and 0.4 s respectively, making them suitable for long-horizon appli-
cations. In contrast, the *MDP* method maintains a high and nearly constant compu-
tation time, illustrating the fixed cost of full policy computation over a static state
space.

Table 5 summarizes the theoretical time complexities associated with each method. These expressions highlight the dominant computational parameters, such as *h*, *b*, *M*, *w*, and *|S*<sub>*A*</sub>|. The observed experimental trends align well with these theoretical formulations:

* *MDP* and *Truncated-MDP* methods show quadratic growth in *M*, consistent with their computational trajectories as system size increases.

* *Greedy* and *Greedy-Windows* methods rely on histogram convolutions, yielding quasi-linear behavior with respect to *b* and *|S*<sub>*A*</sub>*, as confirmed by their stable computation times.

* The *Threshold* method, while simpler, exhibits quadratic growth in *b*, which explains the gradual increase in its execution time for larger buffers.

* The influence of the window size *w*, present only in the *Truncated-MDP* and *Greedy-Windows* methods, introduces a linear factor that remains relatively insignificant compared to other parameters, as previously discussed in Sect. 4.

The experimental results offer strong empirical validation for the theoretical time complexities. The *Greedy* and *Greedy-Windows* algorithms consistently demonstrate superior scalability and responsiveness, making them especially well-suited for real-time or large-scale applications where computational efficiency is critical.

**6 Conclusion and future work**

In this paper, we have demonstrated that, compared to the MDP approach, the proposed *Greedy-Windows* algorithm exhibits significantly lower computational complexity. Specifically, it features linear time complexity with respect to the number of servers *M* and quasi-linear complexity with respect to the buffer size *b*, whereas the MDP method shows quadratic complexity in *M* and linear complexity in *b*. Moreover, as noted at the end of Sect. 4, the influence of the window size parameter *w* remains relatively minor compared to other parameters such as *b*, *h*, and *M*, further underscoring the efficiency of our approach.

Although MDP provides an optimal strategy, it requires substantial memory and
execution time. In particular, for large model parameters (e.g., when *b* or *M* exceeds
200), existing implementations of the value iteration algorithm-such as those in
PRISM (Kwiatkowska et al. 2011)-often fail to complete the computation due to
state space explosion, as evidenced by the experimental results in Sect. 5.1.2. In such
cases, PRISM outputs an *out of memory* error.

In contrast, the *Greedy-Windows* algorithm consistently avoids this issue and deliv-
ers a nearly optimal strategy, with performance differing by less than 2% from the
MDP solution. As shown in Sect. 5.1, our algorithm offers a clear advantage in terms
of execution time and memory usage compared to MDP, Truncated MDP, Greedy, and Threshold-based methods.

Table 5 provides a comprehensive summary of the theoretical time and space complexities associated with each method. This overview aligns with our experimental findings and serves as a practical guide for selecting the most appropriate optimization strategy based on available computational resources and application-specific constraints.

Furthermore, it is worth noting that the analysis performed using the *Greedy-Window* algorithm can be characterized as *online, dynamic, and adaptive*. At each time slot, the algorithm takes into account the current system parameters—including potential changes in the arrival process modeled through histograms-and computes in real time a sub-optimal strategy that determines the number of servers to activate based on the current number of waiting jobs.

When comparing the time and space complexities of the MDP and Greedy-Window approaches, we observe that the MDP requires substantial resources to store the full state-action transition matrix. Additionally, it incurs a significant computational overhead to solve Bellman's equations and obtain the optimal policy. In contrast, the Greedy-Window algorithm delivers a policy that is remarkably close to optimal: the MDP outperforms it by only about 2%, as shown in Fig. 11.

The strength of the Greedy-Window algorithm lies in its computational efficiency and scalability. It avoids the explosion of the state space while providing decisions that are sufficiently accurate for practical deployment. These features make it a highly effective alternative to MDP-based methods, especially in large-scale or real-time environments.

After introducing various modeling approaches, formalizations, and solution strategies for the energy optimization problem in data centers-and supporting these contributions with both theoretical and numerical analyses-we aim to extend our work to real-world deployments and evaluations. Specifically, we plan to test and compare the proposed methods within an actual heterogeneous server cluster architecture.

In this setting, a dedicated manager node, connected to the cluster network, will host a software application implementing the Greedy-Window algorithm. This manager will monitor the system and make real-time decisions regarding server activation. To operate effectively, it must have access to several critical data sources: (i) the cluster network to issue activation commands to specific servers, (ii) the incoming request stream to dynamically update job arrival distributions via histograms, (iii) energy consumption metrics for each server, and (iv) system-level query statistics to estimate the number of pending and rejected jobs. This deployment will offer valuable insights into the real-world performance, adaptability, and efficiency of the proposed algorithms.

In parallel, we also plan to investigate the *coherence* and *robustness* properties of the optimization algorithms introduced or discussed in this paper, especially under noisy, partial, or changing input conditions.

Furthermore, we are consolidating the various components developed throughout this research into a unified software framework that integrates and implements all the optimization strategies presented in this work. Finally, we aim to extend the application scope of the Greedy-Window algorithm beyond the domain of energy-efficient

<figure><img src="image_27.png" /></figure>
data center management. This will allow us to explore the versatility and effectiveness of the Greedy-Window algorithm in addressing broader classes of optimization problems beyond energy-efficient data center management, including domains such as healthcare systems, smart grid control, transportation planning, and cloud infrastructure scheduling.

## Appendix A Histogram operators

As mentioned before, in the literature, modeling the arrival of jobs consists in obtaining a continuous time distribution by fitting the experimental data. Another approach consists in modeling the arrival of jobs by a DTMC<fnref n="2" /> as in Benini et al. (1999). In this work, we suggest using the discrete finite distributions that may be obtained from sampling real traces, empirical data, or incoming traffic measurements directly.

In fact, we model the random variables of our systems (arriving jobs, waiting jobs, lost jobs, etc.) by finite discrete distributions represented by finite structures called histograms.

**Definition 2 (Histogram)** Let $X$ be a discrete random variable taking values in $\mathbb{N}$. The couple $\mathcal{H}_X = (S_X, P_X)$ denotes the histogram of $X$ where $P_X: \mathbb{N} \to [0, 1]$ is the probability mass function of $X$ and $S_X = \{i \in \mathbb{N}: P_X(i) > 0\}$ is the support of $P_X$. Notice that $\sum_{i \in S_X} P_X(i) = 1$.

**Example 1** Let $A$ be a random variable for the arriving jobs of a system. Let $\mathcal{H}_A$ be its histogram. We have:

$$ \mathcal{H}_A = \left\{ \begin{array}{l} S_A = \begin{bmatrix} 2 & & 4 & & 5 & & 7 \end{bmatrix} \\ P_A = \begin{bmatrix} 0.2 & & 0.3 & & 0.4 & & 0.1 \end{bmatrix} \end{array} \right\}. $$

Thus, we can say, for example, that we have a probability of 0.2 to receive 2 jobs during a slot (one time unit) and a probability of 0.1 for receiving 7 jobs. Implicitly, we note that the probability of receiving 0, 1, 3, 8 jobs or more is zero.

To perform calculations on histograms, the following operators defined over histograms are needed to compute the evolution of a stochastic system:

1. $\Delta_v$ is the Dirac histogram with $v \in \mathbb{N}$, where the probability mass function is defined as follows:

$$ \forall i \in \mathbb{N}: P(i) = \begin{cases} 1 & \text{if } i = v \text{ and} \\ 0 & \text{otherwise.} \end{cases} \qquad (A1) $$

2. Given a random variable $X$ and a natural number $v \in \mathbb{N}$, the histogram of the variable $Y = X - v$, noted by $\mathcal{H}_Y = \mathcal{H}_X - v$, corresponds to the histogram of $\mathcal{H}_X$ translated by the constant $v$:

<footnote n="2">² Discrete Time Markov Chain.</footnote>
$$P_Y(i) = P_X(i - v) \text{ if } i > v \text{ and } P_Y(0) = \sum_{i \le v} P_X(i). \qquad (A2)$$

3. $\mathcal{H}_Y = \text{MIN}_b(\mathcal{H}_X)$ is the distribution of the variable $X$ bounded above by the constant $b$. This operation corresponds to a minimum on the underlying random variable. It is defined by:

$$P_Y(i) = P_X(i) \text{ if } i < b \text{ and } P_Y(b) = \sum_{i \ge b} P_X(i). \qquad (A3)$$

4. Given two random variables $X$ and $Y$, the histogram of the variable $Z = X + Y$, noted by $\mathcal{H}_Z = \mathcal{H}_X \oplus \mathcal{H}_Y$, corresponds to the convolution of the histograms $\mathcal{H}_X$ and $\mathcal{H}_Y$:

$$\forall i \in \mathbb{N}: \quad P_Z(i) = \sum_{j=0}^{i} P_X(j) \times P_Y(i-j). \qquad (A4)$$

**Example 2** Let $\mathcal{H}_X$ be an histogram such that:

$$\mathcal{H}_X = \left\{ \begin{array}{c} S_X \\ P_X \end{array} \begin{array}{c} \begin{bmatrix} 1 & 2 & 3 & 5 & 9 & 11 \\ 0.1 & 0.2 & 0.3 & 0.1 & 0.15 & 0.15 \end{bmatrix} \end{array} \right\}$$

We have:

$$\text{MIN}_4(\mathcal{H}_X) = \left\{ \begin{array}{c} S_{\text{MIN}_4(\mathcal{H}_X)} \\ P_{\text{MIN}_4(\mathcal{H}_X)} \end{array} \begin{array}{c} \begin{bmatrix} 1 & 2 & 3 & 4 \\ 0.1 & 0.2 & 0.3 & 0.1 + 0.15 + 0.15 \end{bmatrix} \\ \begin{bmatrix} 1 & 2 & 3 & 4 \\ 0.1 & 0.2 & 0.3 & 0.4 \end{bmatrix} \end{array} \right\}$$

$$\text{MIN}_0(\mathcal{H}_X) = \left\{ \begin{array}{c} S_{\text{MIN}_0(\mathcal{H}_X)} \\ P_{\text{MIN}_0(\mathcal{H}_X)} \end{array} \begin{array}{c} \begin{bmatrix} 0 \\ 0.1 + 0.2 + 0.3 + 0.1 + 0.15 + 0.15 \end{bmatrix} \\ \begin{bmatrix} 0 & 1 \\ 0.1 & 0.2 & 0.3 & 0.1 & 0.15 & 0.15 \end{bmatrix} \end{array} \right\}$$
$$= \left\{ \begin{array}{c} S_{\text{MIN}_0(\mathcal{H}_X)} \\ P_{\text{MIN}_0(\mathcal{H}_X)} \end{array} \begin{array}{c} \begin{bmatrix} 0 \\ 1 \end{bmatrix} \\ \begin{bmatrix} 0 & 1 \\ 0.1 & 0.2 & 0.3 & 0.1 & 0.15 & 0.15 \end{bmatrix} \end{array} \right\}$$
$$= \Delta_0.$$

$$\text{MIN}_{18}(\mathcal{H}_X) = \left\{ \begin{array}{c} S_{\text{MIN}_{18}(\mathcal{H}_X)} \\ S_{\text{MIN}_{18}(\mathcal{H}_X)} \end{array} \begin{array}{c} \begin{bmatrix} 1, 2, 3, 5, 9, 11 \\ 0.1, 0.2, 0.3, 0.1, 0.15, 0.15 \end{bmatrix} \\ \begin{bmatrix} 1, 2, 3, 5, 9, 11 \\ 0.1, 0.2, 0.3, 0.1, 0.15, 0.15 \end{bmatrix} \end{array} \right\}$$
$$= \mathcal{H}_X.$$

We have also:
$$ \mathcal{H}_X - 4 = \begin{cases} S_{\mathcal{H}_X - 4} & [0, 1, 5, 7] \\ P_{\mathcal{H}_X - 4} & [0.1 + 0.2 + 0.3, 0.1, 0.15, 0.15] \end{cases} \\ = \begin{cases} S_{\mathcal{H}_X - 4} & [0, 1, 5, 7] \\ P_{\mathcal{H}_X - 4} & [0.6, 0.1, 0.15, 0.15] \end{cases}. $$

**Example 3** Let $\mathcal{H}_X$ and $\mathcal{H}_Y$ be two histograms such that:

$$ \mathcal{H}_X = \begin{cases} S_X & [2, 3] \\ P_X & [0.4, 0.6] \end{cases} \quad \text{and} \quad \mathcal{H}_Y = \begin{cases} P_Y & [10, 20] \\ S_Y & [0.1, 0.9] \end{cases}. $$

We have:

$$ \begin{aligned} \mathcal{H}_Z &= \mathcal{H}_X \oplus \mathcal{H}_Y \\ &= \begin{cases} S_Z & [2+10, 3+10, 2+20, 3+20] \\ P_Z & [0.4 \times 0.1, 0.6 \times 0.1, 0.4 \times 0.9, 0.6 \times 0.9] \end{cases} \\ &= \begin{cases} S_Z & [12, 13, 22, 23] \\ P_Z & [0.04, 0.06, 0.36, 0.54] \end{cases}. \end{aligned} $$

With the **quadratic direct method**, the convolution of two probability distributions $P_X$ and $P_Y$ is computed by summing the products of their probabilities over all possible pairs of values that sum to $z$. However, the **FFT-based method** computes the convolution by leveraging the Fast Fourier Transform (FFT), which exploits the property that convolution in one domain (time or spatial) corresponds to multiplication in the frequency domain.

<figure><img src="image_28.png" /><figcaption>Fig. 14 Convolution FFT-based method</figcaption></figure>
**Remark 1** Notice that the computation of a convolution by the direct method described by Eq. (A4) requires $O(|S_X| \times |S_Y|)$ operations, which can be significantly reduced with fast algorithms, typically by the use of fast convolution algorithms (Pavel and David 2013; Jan 2000), to reduce the cost of the convolution to $O(n \log n)$ complexity where $n$ is the extent of the support of the histograms: $n = \max(S_X) + \max(S_Y)$.

Figure 14 shows an experimental comparison between the quadratic direct method and the FFT-based method using the scipy Python package, which implements both methods. It shows a comparison between the direct method and the FFT-based method for computing the convolution of two histograms $H_X \oplus H_Y$. The histograms were generated randomly where the extent of each histogram is close to the support of the histograms: $\max(S_X) = n$, $\max(S_Y) = n$, $|S_X| \sim n$, and $|S_Y| \sim n$.

**Funding** Open access funding provided by Université d'Évry Val-d'Essonne. This study was not funded by any company.

**Data availability** The data used in this study are derived from publicly available datasets. Processed or aggregated data supporting the findings of this study are available from the corresponding author upon reasonable request.

## Declarations

**Conflict of interest** Author A declares that she has no conflict of interest.

**Ethical approval** This article does not contain any studies with human participants or animals performed by any of the authors.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

## References

Aidarov K, Ezhilchelvan PD, Mitrani I (2013) Energy-aware management of customer streams. Electr Notes Theor Comput Sci 296:199–210. https://doi.org/10.1016/j.entcs.2013.07.013

Ajagekar A, You F (2024) Variational quantum circuit learning-enabled robust optimization for AI data center energy control and decarbonization. Adv Appl Energy 14:100179

An H, Ma X (2022) Dynamic coupling real-time energy consumption modeling for data centers. Energy Rep 8:1184–1192

Arnold M, Andersson G (2011) Model predictive control of energy storage including uncertain forecasts. In: Power systems computation conference (PSCC), Stockholm, Sweden, vol 23, pp 24–29

Baliga J, Ayre RW, Hinton K, Tucker RS (2011) Green cloud computing: balancing energy in processing, storage, and transport. Proc IEEE 99(1):149–167
Bayati M (2016) Managing energy consumption and quality of service in data centers. In: Proceedings of the 5th international conference on smart cities and green ICT systems, pp 293–301

Bayati M (2018) Power management policy for heterogeneous data center based on histogram and discrete-time MDP. Electr Notes Theor Comput Sci 337:5–22. https://doi.org/10.1016/j.entcs.2018.03.031

Bayati L (2023a) Discrete-time MDP policy for energy-aware data center. In: Smartgreens, pp 89–97

Bayati L (2023b) Energy consumption optimization in data center with latency based on histograms and discrete-time MDP. In: Smartgreens, pp 98–105

Bayati M, Dahmoune M, Fourneau J, Pekergin N, Vekris D (2015) A tool based on traffic traces and stochastic monotonicity to analyze data centers and their energy consumption. In: Valuetools ’15: 9th international conference on performance evaluation methodologies and tools. ACM (to appear)

Bayati M, Dahmoune M, Fourneau J, Pekergin N, Vekris D (2016) A tool based on traffic traces and stochastic monotonicity to analyze data centers and their energy consumption. EAI Endorsed Trans Energy Web 3(10):e3. https://doi.org/10.4108/eai.14-12-2015.2262652

Benini L, Bogliolo A, Paleologo G, De Micheli G (1999) Policy optimization for dynamic power management. IEEE Trans Comput Aided Des Integr Circuits Syst 18(6):813–833

Benson T, Akella A, Maltz DA (2010) Network traffic characteristics of data centers in the wild. In: Proceedings of the 10th ACM sigcomm conference on internet measurement, pp 267–280

Berl A, Gelenbe E, Di Girolamo M, Giuliani G, De Meer H, Dang MQ, Pentikousis K (2010) Energy-efficient cloud computing. Comput J 53(7):1045–1051

Black PE (2004) Dictionary of algorithms and data structures. National Institute of Standards and Technology Gaithersburg, Gaithersburg

Citaristi I (2022) International energy agency-IEA. The Europa directory of international organizations 2022. Routledge, pp 701–702

Ding D, Fan X, Zhao Y, Kang K, Yin Q, Zeng J (2020) Q-learning based dynamic task scheduling for energy-efficient cloud computing. Future Gener Comput Syst 108:361–371

Dyachuk D, Mazzucco M (2010) On allocation policies for power and performance. In: 2010 11th IEEE/ACM international conference on grid computing, pp 313–320

Efrosinin D (2004) Controlled queueing systems with heterogeneous servers. Unpublished doctoral dissertation, Univ. Trier, FB 4, Informatik

Entezari-Maleki R, Sousa L, Movaghar A (2017) Performance and power modeling and evaluation of virtualized servers in IaaS clouds. Inf Sci 394:106–122

Gajane P, Ortner R, Auer P (2018) A sliding-window algorithm for Markov decision processes with arbitrarily changing rewards and transitions. arXiv preprint arXiv:1805.10066

Gandhi A, Harchol-Balter M (2011) How data center size impacts the effectiveness of dynamic power management. In: 2011 49th annual Allerton conference on communication, control, and computing (Allerton), pp 1164–1169

Gandhi A, Gupta V, Harchol-Balter M, Kozuch MA (2010a) Optimality analysis of energy-performance trade-off for server farm management. Perform Eval 67(11):1155–1171

Gandhi A, Harchol-Balter M, Adan I (2010b) Server farms with setup costs. Perform Eval 67(11):1123–1138

Gandhi A, Doroudi S, Harchol-Balter M, Scheller-Wolf A (2013) Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward. In: ACM SIGMETRICS performance evaluation review, vol 41, pp 153–166

Gao J, Wang H, Shen H (2020) Smartly handling renewable energy instability in supporting a cloud datacenter. In: 2020 IEEE international parallel and distributed processing symposium (IPDPS), pp 769–778

Ghosh R, Longo F, Naik VK, Trivedi KS (2013) Modeling and performance analysis of large scale IaaS clouds. Future Gener Comput Syst 29(5):1216–1234

Greenberg AG, Hamilton JR, Maltz DA, Patel P (2009) The cost of a cloud: research problems in data center networks. Comput Commun Rev 39(1):68–73

Grunwald D, Morrey III CB, Levis P, Neufeld M, Farkas KI (2000) Policies for dynamic clock scheduling. In: Proceedings of the 4th conference on symposium on operating system design & implementation—volume 4. USENIX Association, Berkeley, CA, USA, pp 6–6

Ilbeigi M, Ghomeishi M, Dehghanbanadaki A (2020) Prediction and optimization of energy consumption in an office building using artificial neural network and a genetic algorithm. Sustain Cities Soc 61:102325

Ilhuicatzi-Roldán R, Cruz-Suárez H (2013) Rolling horizon procedures for the solution of an optimal replacement problem of n-machines with random horizon. Investig Oper 34(2):105–116
Jan J (2000) Digital signal filtering, analysis and restoration (telecommunications series). INSPEC, Inc,
Canton

Jin Y, Wen Y, Chen Q (2012) Energy efficiency and server virtualization in data centers: an empirical investigation. In: 2012 IEEE conference on computer communications workshops (INFOCOM WKSHPS), pp 133–138

Karthikeyan K, Sunder R, Shankar K, Lakshmanaprabu S, Vijayakumar V, Elhoseny M, Manogaran G (2020) Energy consumption analysis of virtual machine migration in cloud using hybrid swarm optimization (ABC-BA). J Supercomput 76:3374–3390

Katal A, Dahiya S, Choudhury T (2023) Energy efficiency in cloud computing data centers: a survey on software technologies. Clust Comput 26(3):1845–1875

Kendall M (1973) Time-series (Griffin, Ed.). Griffin. https://books.google.fr/books?id=hYZYAAAAMA AJ

Khan S, Hayder IA, Habib MA, Ahmad M, Mohsin SM, Khan FA, Mustafa K (2022) Enhanced machine-
learning techniques for medium-term and short-term electric-load forecasting in smart grids. Ener-
gies 16(1):276

Kim JH, Ahn H, Righter R (2011) Managing queues with heterogeneous servers. J Appl Probab 48(02):435–452

Koomey J (2011) Growth in data center electricity use 2005 to 2010. A report by Analytical Press, com-
pleted at the request of The New York Times, 9

Kwiatkowska M, Norman G, Parker D (2011) PRISM 4.0: verification of probabilistic real-time systems.
In: Gopalakrishnan G, Qadeer S (eds) Proceedings of the 23rd international conference on computer
aided verification (cav’11), vol 6806. Springer, pp 585–591

Lakhan A, Mohammed MA, Abdulkareem KH, Jaber MM, Kadry S, Nedoma J, Martinek R (2023) Fuzzy decision based energy-evolutionary system for sustainable transport in ubiquitous fog network. Hum-Centric Comput Inform Sci 13:34

Lee YC, Zomaya AY (2012) Energy efficient utilization of resources in cloud computing systems. J Super-
comput 60(2):268–280

Leng B, Krishnamachari B, Guo X, Niu Z (2016) Optimal operation of a green server with bursty traffic.
In: 2016 IEEE global communications conference (globecom), pp 1–6

Li K (2012) Optimal power allocation among multiple heterogeneous servers in a data center. Sustain
Comput Inform Syst 2(1):13–22

Luh HP, Viniotis I (2002) Threshold control policies for heterogeneous server systems. Math Methods
Oper Res 55(1):121–142

Maccio VJ, Down DG (2015) On optimal control for energy-aware queueing systems. In: 2015 27th inter-
national teletraffic congress (ITC 27), pp 98–106

Masanet E, Shehabi A, Lei N, Smith S, Koomey J (2020) Recalibrating global data center energy-use
estimates. Science 367(6481):984–986

Mazzucco M, Dyachuk D (2012) Optimizing cloud providers revenues via energy efficient server alloca-
tion. Sustain Comput Inform Syst 2(1):1–12

Miao C, Cui Y, Li H, Wu X (2024) Efficient multi-agent reinforcement learning HVAC power consump-
tion optimization. Energy Rep 12:5420–5431. https://doi.org/10.1016/j.egyr.2024.11.011

Mitrani I (2013) Managing performance and power consumption in a server farm. Ann OR 202(1):121–134

Nathuji R, Isci C, Gorbatov E (2007) Exploiting platform heterogeneity for power efficient data centers.
In: Fourth international conference on autonomic computing, 2007. icac’07, pp 5–5

Norman G, Parker D, Kwiatkowska M, Shukla S, Gupta R (2005) Using probabilistic model checking for
dynamic power management. Formal Asp Comput 17(2):160–176

Patel CD, Bash CE, Sharma R, Beitelmal M (2003) Smart cooling of data centers. Proc ipack

Pavel K, David S (2013) Algorithms for efficient computation of convolution. In: Design and architectures
for digital signal processing. IntechOpen

Peng X, Bhattacharya T, Mao J, Cao T, Jiang C, Qin X (2022) Energy-efficient management of data centers using a renewable-aware scheduler. In: 2022 IEEE international conference on networking, architec-ture and storage (nas), pp 1–8

Raizada A, Singh KP, Sajid M (2020) Worldwide energy consumption of hyperscale data centers: a survey.
Int Res J Adv Sci Hub 2(Special Issue ICAET 11S):8–15

Reiss C, Wilkes J, Hellerstein JL (2011) Google cluster-usage traces: format + schema (technical report).
Mountain View, CA, USAGoogle Inc. Revised 20 Mar 2012
Rteil N, Burdett K, Clement S, Wynne A, Kenny R (2022) Balancing power and performance: a multi-generational analysis of enterprise server bios profiles. In: 2022 international conference on green energy, computing and sustainable technology (gecost), pp 81–85

Schwartz C, Pries R, Tran-Gia P (2012) A queuing analysis of an energy-saving mechanism in data centers. In: 2012 international conference on information networking (icoin), pp 70–75

Slegers J, Thomas N, Mitrani I (2008) Dynamic server allocation for power and performance. In: Spec international performance evaluation workshop, pp 247–261

Wang B, Liu D (2011) Rolling horizon procedure for large-scale equipment replacement problems with multiple alternatives. In: 2011 Chinese control and decision conference (CCDC), pp 2741–2746

Wilkes J (2011) More Google cluster data. Google research blog. Posted at http://googleresearch.blogspot.com/2011/11/more-google-cluster-data.html

Xu X, Tian N (2008) The M/M/c queue with (e, d) setup time. J Syst Sci Complex 21(3):446–455

Yang Z, Chen M-H, Niu Z, Huang D (2011) An optimal hysteretic control policy for energy saving in cloud computing. In: Global telecommunications conference, pp 1–5

Zhao D, Samsi S, McDonald J, Li B, Bestor D, Jones M, Gadepally V (2023) Sustainable supercomputing for AI: GPU power capping at HPC scale. In: Proceedings of the 2023 ACM symposium on cloud computing, pp 588–596

**Publisher's Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

**Dr. Léa Bayati** is currently a research associate at the IBISC Laboratory (Informatique, Bioinformatique et Systèmes Complexes, EA 4526) of Université d'Évry Paris-Saclay, where she specializes in combinatorial optimization, stochastic combinatorial optimization, energy-efficient computing, operations research, and distributed systems. She holds a Ph.D. in Computer Science from Université Paris-Est Créteil (UPEC), awarded in 2019 for her work on energy optimization in data centers using discrete-time Markov Decision Processes and heuristic algorithms. She has held academic positions at Université Sorbonne Nouvelle-Paris 3, Université Paris-Est Créteil, and has contributed to national projects such as ANBLIC (secure computation on encrypted health data in cloud environments) and MARMOTE (Markovian Modeling Tools and Environments). Her research contributions include the development of the Greedy-Window algorithm for real-time energy-aware control policies and scalable algorithms for homomorphic computation on multi-core architectures. She is actively involved in both pedagogical innovation and scientific dissemination, coordinating interdisciplinary teaching in sustainable computing and supervising numerous graduate-level research projects. Her work has been presented in several international conferences (e.g., SMARTGREENS, ISPDC) and published in journals such as Electronic Notes in Theoretical Computer Science.