Skip to main content
Journal cover image

The stochastic machine replenishment problem

Publication ,  Conference
Munagala, K; Shi, P
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
June 30, 2008

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.

Duke Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783540688860

Publication Date

June 30, 2008

Volume

5035 LNCS

Start / End Page

169 / 183

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Munagala, K., & Shi, P. (2008). The stochastic machine replenishment problem. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 5035 LNCS, pp. 169–183). https://doi.org/10.1007/978-3-540-68891-4_12
Munagala, K., and P. Shi. “The stochastic machine replenishment problem.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5035 LNCS:169–83, 2008. https://doi.org/10.1007/978-3-540-68891-4_12.
Munagala K, Shi P. The stochastic machine replenishment problem. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2008. p. 169–83.
Munagala, K., and P. Shi. “The stochastic machine replenishment problem.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5035 LNCS, 2008, pp. 169–83. Scopus, doi:10.1007/978-3-540-68891-4_12.
Munagala K, Shi P. The stochastic machine replenishment problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2008. p. 169–183.
Journal cover image

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783540688860

Publication Date

June 30, 2008

Volume

5035 LNCS

Start / End Page

169 / 183

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences