Mean value analysis

Mean value analysis

In queueing theory, a specialty within the mathematical theory of probability, mean value analysis is a technique for computing expected queue lengths in equilibrium for a closed separable system of queues. It was developed by Reiser and Lavenberg[1] in 1980.

It is based on the arrival theorem, which states that when one customer in an M-customer closed system arrives at a service facility he/she observes the rest of the system to be in the equilibrium state for a system with M − 1 customers.

Contents

Problem setup

Consider a closed queueing network of K queues, with M customers circulating in the system.

Let μj be the (known) service rate for queue j, i.e. 1 / μj is the service time.

Let P be the (known) routing matrix, where each element pij is the probability that after visiting queue i the customer will visit queue j. From this matrix we can calculate the vector V=\{v_1,\cdots,v_K\} known as the visit-ratio vector by solving the eigenvector-like equation VP = V.

Let Nj(n) be the mean number of customers in queue j when there are a total of n customers in the system; this includes the job currently being served in queue j.

Let Wj(n) be the mean time spent by a customer in queue j when there are a total of n in the system; it is the total delay at this queue including the customer service time.

Algorithm

The algorithm[2] starts with an empty network (zero customers), then increases the number of customers by 1 until it reaches the desired number of customers M.

Initialization. Let Nk(0) = 0 for k = 1 to K

Repeat for m = 1 to M:

Step 1. For k = 1 to K let W_k(m)=\frac{N_k(m-1)+1}{\mu_k}. (This is based on the arrival theorem).
Step 2. Let \lambda=\frac{m}{\sum_{k=1}^K W_k(m) v_k}. (This is an application of Little's Law to find the system throughput).
Step 3. Let Nk(m) = vkλWk(m) for k = 1 to K. (This is another application of Little's law to each individual queue).

End repeat.

External links

References

  1. ^ Reiser, M.; Lavenberg, S. S. (April 1980). "Mean Value Analysis on Closed Multichain Queueing Networks". Journal of the ACM 27 (2). doi:10.1145/322186.322195. 
  2. ^ Bose, Sanjay K. (2001). An introduction to queueing systems. Springer. p. 174. ISBN 0306467348. http://books.google.com/books?id=39-jISti_zkC. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Mean value theorem — For the theorem in harmonic function theory, see Harmonic function#Mean value property. Topics in Calculus Fundamental theorem Limits of functions Continuity Mean value theorem Differential calculus  Derivative Change of variables …   Wikipedia

  • mean-value theorem — ▪ mathematics       theorem in mathematical analysis dealing with a type of average useful for approximations and for establishing other theorems, such as the fundamental theorem of calculus (analysis).  The theorem states that the slope of a… …   Universalium

  • Mean value theorem (divided differences) — In mathematical analysis, the mean value theorem for divided differences generalizes the mean value theorem to higher derivatives.[1] It states that for any n + 1 points x0, ..., xn in the domain of an n times differentiable… …   Wikipedia

  • Mean-variance analysis — Evaluation of risky prospects based on the expected value and variance of possible outcomes. The New York Times Financial Glossary …   Financial and business terms

  • mean-variance analysis — Evaluation of risky prospects based on the expected value and variance of possible outcomes. Bloomberg Financial Dictionary …   Financial and business terms

  • Mean — This article is about the statistical concept. For other uses, see Mean (disambiguation). In statistics, mean has two related meanings: the arithmetic mean (and is distinguished from the geometric mean or harmonic mean). the expected value of a… …   Wikipedia

  • Mean squared error — In statistics, the mean squared error (MSE) of an estimator is one of many ways to quantify the difference between values implied by a kernel density estimator and the true values of the quantity being estimated. MSE is a risk function,… …   Wikipedia

  • mean — mean1 /meen/, v., meant, meaning. v.t. 1. to have in mind as one s purpose or intention; intend: I meant to compliment you on your work. 2. to intend for a particular purpose, destination, etc.: They were meant for each other. 3. to intend to… …   Universalium

  • Mean Return — 1. In securities analysis, it is the expected value, or mean, of all the likely returns of investments comprising a portfolio. It is also known as expected return . 2. In capital budgeting, it is the mean value of the probability distribution of… …   Investment dictionary

  • Value investing — is an investment paradigm that derives from the ideas on investment and speculation that Ben Graham David Dodd began teaching at Columbia Business School in 1928 and subsequently developed in their 1934 text Security Analysis . Although value… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”