Speed scaling

We aim to examine several classes of speed scaling algorithms.  Such algorithms typically make two decisions at each time: (i) a scheduling policy which decides which job(s) to serve, and (ii) a speed scaler which decides how fast the server operates.

Generally speaking, we are faced with dual objective optimization problems.  We will initially focus on minimizing a weighted sum of a service performance measure (like mean workload or mean response time) and energy usage per job, and on minimizing a performance measure under an energy usage constraint. 

A distinction will be made between dynamic algorithms (speed may vary at any moment in time) and static algorithms (speed is fixed for certain time intervals), and also between worst-case analysis and stochastic analysis.  In addition, we will study on-line as well as off-line scenarios, and touch upon issues like robustness and fairness.

A central goal is to understand the dynamic interaction of speed scaling algorithms at different servers in distributed network settings, where the control is decentralized and where jobs are buffered, dispatched, and passed on by various decision making entities in the network.

Our results will be of considerable relevance for processor farms in big data centers (where typically the energy usage term in the objective function is polynomial in the speed) as well as for wireless networks (where the energy usage term may be exponential in the speed).