The stochastic machine replenishment problem

Conference Paper

We study the stochastic machine replenishment problem, which is a canonical special case of closed multiclass queuing systems in Markov decision theory. The problem models the scheduling of processor repairs in a multiprocessor system in which one repair can be made at a time and the goal is to maximize system utilization. We analyze the performance of a natural greedy index policy for this problem. We first show that this policy is a 2 approximation by exploring linear queuing structure in the index policy. We then try to exploit more complex queuing structures, but this necessitates solving an infinite-size, non-linear, non-convex, and non-separable function-maximization program. We develop a general technique to solve such programs to arbitrary degree of accuracy, which involves solving a discretized program on the computer and rigorously bounding the error. This proves that the index policy is in fact a 1.51 approximation. The main non-trivial ingredients of the proof are two folds: finding a way to analyze the complex queuing structure of the index policy, and bounding the error in discretization when numerically solving the non-linear function-maximization. We believe that this framework is general enough to be useful in the analysis of index policies in related problems. As far as we are aware, this is one of the first non-trivial approximation analysis of an index policy a multi-class queuing problem, as well as one of the first non-trivial example of an approximation ratio that is rigorously proven by numerical optimization via a computer. © 2008 Springer-Verlag Berlin Heidelberg.

Full Text

Duke Authors

Cited Authors

  • Munagala, K; Shi, P

Published Date

  • June 30, 2008

Published In

Volume / Issue

  • 5035 LNCS /

Start / End Page

  • 169 - 183

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540688862

International Standard Book Number 13 (ISBN-13)

  • 9783540688860

Digital Object Identifier (DOI)

  • 10.1007/978-3-540-68891-4_12

Citation Source

  • Scopus