Exploring the Tradeoff between Waiting Time and Service Cost in Non-Asymptotic Operating Regimes

Abstract—Motivated by the problem of demand management in smart grids, we study the problem of minimizing a weighted-sum of the mean delay of user demands and the power generation cost, where the latter metric increases with both the mean and the variance of the service demand. The state-of-the-art algorithms for this problem are asymptotically optimal, i.e., they are optimal only when the mean delay of user demands increases to infinity or decreases to zero. Yet, these algorithms may perform poorly for moderate delay, which is the regime in which most applications operate. Hence, there is a pressing need for the design of algo-rithms that can operate efficiently in the moderate delay regime. We attack this challenging problem in a generic framework by first proposing two classes of parameterized algorithms, which include some existing policies as special instances. Then, we obtain the optimal designs by explicitly characterizing the mean delay and the power generation cost as a function of the algorithmic parameters. The proposed algorithms with the optimal parameters not only are asymptotically optimal but also outperform the existing algorithms uniformly for all cases. I