Can the popular shortest remaining processing time (SRPT) algorithm achieve a constant competitive ratio on multiple servers when server speeds are adjustable (speed scaling) with respect to the flow time plus energy consumption metric? This question has remained open for a while, where a negative result in the absence of speed scaling is well known. Our main result is to show that multi-server SRPT can be constant competitive, with a competitive ratio that only depends on the power-usage function of the servers, but not on the number of jobs/servers or the job sizes (unlike when speed scaling is not allowed). When all job sizes are unity, we show that round-robin routing is optimal and can achieve the same competitive ratio as the best known algorithm for the single server problem. When job arrivals are stochastic, with Poisson arrivals and i.i.d. job sizes, we show that random routing and a simple speed scaling and routing algorithm achieves a constant competitive ratio. This is joint work with Rahul Vaze.
Jayakrishnan Nair is an Assistant Professor of Electrical Engineering at IIT Bombay. His research draws on tools from queueing theory, applied probability, game theory, and control theory to address performance evaluation and design issues in networks, service systems, and smart power grids