CMU-CS-13-105Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-13-105
Anshul Gandhi, Sherwin Doroudi*, April 2013
Keywords:
Queueing Theory, Setup Times, Renewal Reward
The M/M/k/setup model, where there is a penalty for turning servers on,
is common in data centers, call centers and manufacturing systems. Setup
costs take the form of a time delay, and sometimes there is additionally
a power penalty, as in the case of data centers. While the M/M/1/setup was
exactly analyzed in 1964, no exact analysis exists to date for the
M/M/k/setup with In this paper we provide the first exact, closed-form analysis for the M/M/k/setup and some of its important variants including systems in which: (i) idle servers delay for a period of time before turning off, or (ii) idle servers can either be turned off or put to sleep. Our analysis is made possible by our development of a new technique, Recursive Renewal Reward (RRR), for solving Markov chains with a repeating structure. RRR uses ideas from renewal reward theory and busy period analysis to obtain closed-form expressions for metrics of interest such as the transform of time in system and the transform of power consumed by the system. The simplicity, intuitiveness, and versatility of RRR makes it useful for analyzing Markov chains far beyond the M/M/k/setup. In general, RRR can be used to analyze any 2-dimensional Markov chain which is finite in one dimension and possibly infinite (with a repeating structure) in the other dimension. 37 pages *Tepper School of Business, Carnegie Mellon University
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |