What are the most common measures of system performance in a queuing analysis?

Research Article | Open Access

Academic Editor: Yansheng Liu

Received07 Jul 2011

Accepted23 Sept 2011

Published24 Nov 2011

This paper focuses on new measures of performance in single-server Markovian queueing system. These measures depend on the moments of order statistics. The expected value and the variance of the maximum (minimum) number of customers in the system as well as the expected value and the variance of the minimum (maximum) waiting time are presented. Application to an M/M/1 model is given to illustrate the idea and the applicability of the proposed measures.

1. Introduction

Queueing systems have found wide applications in modeling and analysis of computer and communication systems, and several other engineering systems in which single server is attached to one or more workstations. The study of queueing systems has often been concerned with the busy period and the waiting time, because they play a very significant role in the understanding of various queueing systems and their management. A busy period in a queuing system normally starts with the arrival of a customer who finds the system empty and ends with the first time at which the system becomes empty again. The length of a busy period of an M/M/1 queue with constrained workload is discussed by Kinateder and Lee [1] using Laplace transform. Draief and Mairesse [2] analyzed the service times of customers in an M/M/1 queue depending on their position in a busy period. They provided a law of the service of a customer at the beginning, at the end, or in the middle of the busy period by considering a family of polynomial generating seires associated with Dyck paths of length . Details about using a busy period in an M/M/1 queue can be found in Guillemin and Pinchon [3] and references therein. Takagi and Tarabia [4] provided an explicit probability density function of the length of a busy period starting with customers for more general model M/M/1/L, where L is the capacity of the system; see also Tarabia [5]. Al Hanbali and Boxma [6] studied the transient behaviour of a state-dependent M/M/1/L queue during the busy period. Virtual waiting time at time is defined to be the time that imaginary customers would have to wait before service if they arrived in a queueing system at instant . Gross and Harris [7, Section 2.3] gave a derivation of the steady-state virtual waiting time distribution for an M/M/c model. The virtual waiting time distribution was first formulated for discrete time queues by Neuts [8] for the single-server case. Berger and Whitt [9] provided various approximation and simulation techniques for several different queueing processes (waiting time, virtual waiting time, and the queue length). For more general queue models in waiting time, see A. Brandt and M. Brandt [10]. A recursive procedure for computing the moments of the busy period for the single-server model can be found in Tarabia [5]. Limit theorems are proved by investigating the extreme values of the maximum queue length, the waiting time and virtual waiting time for different queue models in literature. Serfozo [11] discussed the asymptotic behavior of the maximum value of birth-death processes over large time intervals. Serfozo’s results concerned the transient and recurrent birth-death processes and related M/M/c queues. Asmussen [12] introduced a survey of the present state of extreme value theory for queues and focused on the regenerative properties of queueing systems, which reduced the problem to study the tail of the maximum of the queueing process during a regenerative cycle , where is in discrete or continuous time. Artalejo et al. [13] presented an efficient algorithm for computing the distribution for the maximum number of customers in orbit (and in the system) during a busy period for the M/M/c retrial queue. The main idea of their algorithm is to reduce the computation of the distribution of the maximum customer number in orbit by computing certain absorption probabilities. For more details in extreme value in queues, see Park [14] and Minkevičius [15] together with the references contained therein.

Our motivation is to obtain some complementary measures of performance of an M/M/1 queue. The expected value and the variance of the minimum (maximum) number of customers in system as well as the expected value and the variance of the minimum (maximum) waiting time are discussed.

Let us divide the number of arrival customers into intervals, and let be the number of customers in each interval. The corresponding order statistics is defined by . Three special cases are introduced: (a) , defines the maximum number of customers presented in the system, (b) , defines the minimum number of customers in the system, and (c) , defines the regular performance measures. So, our interest is to compute , , , and where and , for . Also, let be the waiting time in the interval . The expected value and the variance of the minimum (maximum) waiting times are computed, respectively, as , , , and where and , for . The remainder of this paper is organized as follows. The model description and some important theorems in order statistics are given in Section 2. The proposed performance measures are obtained in Section 3. Numerical results and conclusion are presented in Section 4.

2. Model and Description

Consider a single-server queue with interarrival time and service time which are exponentially distributed with rates and , respectively. Let be the number of customers in the system at time . We define Then, the governing differential-difference equations of the system under consideration are given by Taking the limit as when yields See, for example, Gross and Harris [7].

Let be the number of customers in the system. Define the cumulative distribution function (cdf) of as In steady-state case for M/M/1 queue, we can write In the following, we state two of the needed theorems. These two theorems can be found in Arnold et al. [16, page 43] and Barakat and Abdelkader [17], respectively. The first theorem gives expressions for the first two moments of the th order statistics, , in a sample of size in discrete case, and the second theorem deals with the th moments of in a continuous case.

Theorem 2.1. Let , the support of the distribution, be a subset of nonnegative integers. Then, whenever the moment on the left-hand side is assumed to exist.
Hence, the variance is given by In the case of independent identically distributed (iid) random variables, the expected value and the variance of the maximum are given by Similarly, the expected value and the variance of the minimum are given by where and .

Theorem 2.2. Let , be a non-negative r.v.’s with d.f.’s . Then, the th moment of the th order statistics in a sample of size k is given by In the case of iid random variables, when and , one gets respectively,

3. Performance Measures

This section is devoted to introduce the proposed performance measures which are often useful for investigating the behaviour of a queueing system. The mean and the variance of the minimum (maximum) number of customers in system as well as the mean and the variance of the minimum (maximum) waiting times are derived. The following lemma and consequence theorems give a procedure for the computations of these measures.

Lemma 3.1. Let be iid random variables; the cdf for the maximum and the minimum are given by

Proof. From the definitions of the cdf’s of and , we have Plugging the value of from (2.5) into the last two equations, we get (3.1) and (3.2). This completes the proof.

3.1. The Mean and the Variance of the Minimum and the Maximum Number of Customers in the System

We are now ready to formulate our results.

Theorem 3.2. The expected value and the variance of the minimum number of customers in the system are given by

Proof. Using (2.11) and (3.2), we get Applying (2.12) and (3.2), the second-order moment is given by Hence, according to (2.13), the variance of the minimum is given by

Theorem 3.3. The mean and the variance of the maximum number of customers in the system are given by

Proof. Applying (2.8) and (3.1), then expanding binomially, we obtain Applying (2.9) and (3.1), the second-order moment is given by of in Theorem 2.1, we get (3.9) and hence the proof.

Employing the above procedure,similar results can be obtained for the minimum and maximum queue length as stated in the following two corollaries.

Corollary 3.4. The mean and the variance of the minimum queue length are given by

Corollary 3.5. The mean and the variance of the maximum queue length are given by

According to Lemma 3.1 and the definitions of the expected value and the variance in Theorem 2.1, the proof of the above formulas can be easily established.

3.2. The Minimum and the Maximum Waiting Time in the Queue

Other useful performance measures are the mean and the variance of the minimum and maximum waiting time in the queue. The cumulative probability distribution of the waiting time for the M/M/1 queue is given by The expected waiting time in the queue is

Theorem 3.6. The th moments of the minimum waiting time in the queue are given by

Proof. Using (2.16) and (3.14), we have

The following corollary follows from Theorem 3.6.

Corollary 3.7. The mean and the variance of the minimum waiting time are given by Then, the variance is

Theorem 3.8. The th moments of the maximum waiting time in the queue are given by

Proof. Using (2.15) and (3.14), we can write

The following corollary follows from Theorem 3.8.

Corollary 3.9. The mean and the variance of the maximum waiting time are given by

Proof. Set and in (3.20), and using the definition of the variance, we get (3.22).

Since and give the sum of the expected value of the maximum number of customers in the system and queue, we compute the expected value of the maximum number of customers in the system and queue during each interval , respectively, by with conventional and Similarly, the expected value of the maximum waiting time in the queue during each interval is computed by

4. Numerical Results

To demonstrate the applicability of the results obtained in the previous sections, some numerical results have been presented in the form of tables showing the effectiveness and the applicability of the proposed measures. We have considered M/M/1 queue with and . Table 1 summarizes the values of , and for each interval . Table 2 gives the minimum number of customers in the system (queue) in each interval . Finally, Table 3 shows the expected values of the maximum waiting time in the queue.

Remarks 4. The obtained results in Tables 1–3 show that the expected value of the maximum (minimum) number of customers decreases gradually with the increasing number of intervals. Also, it is noted that the system will be almost empty in the 13rd interval. That is, the customer will get the service immediately when she (or he) arrived and will leave the system before the second arrival. This result agrees with the fact that the service rate is greater than the arrival rate. Similar conclusion can be deduced form Table 3. The traffic intensity decreases gradually to zero as the number of intervals increases.

5. Conclusions

In this paper, we have considered the Markovian queueing model with a single-server and infinite system capacity. The paper presents some complementary measures of performance which are depending on the methods of order statistics. The expected value and the variance of the minimum (maximum) number of customers in the system (queue) as well as the th moments of the minimum (maximum) waiting time in the queue are derived. Clearly, the expected value of the number of customers in the system (queue) as well as the expected waiting time can be obtained as special cases from our proposed measures when . Although this work is currently restricted to the M/M/1 model, it can be applied to other queueing models.

References

1. K. K. J. Kinateder and E. Y. Lee, “A new approach to the busy period of the M/M/1 queue,” Queueing Systems, vol. 35, no. 1–4, pp. 105–115, 2000.

   View at: Publisher Site | Google Scholar | Zentralblatt MATH

2. M. K. Draief and J. Mairesse, “Services within a busy period of an M/M/1 queue Dyck paths,” Queueing Systems, vol. 49, no. 1, pp. 73–84, 2005.

   View at: Publisher Site | Google Scholar | Zentralblatt MATH

3. F. Guillemin and D. Pinchon, “On the area swept under the occupation process of an M/M/1 queue in a busy period,” Queueing Systems, vol. 29, no. 2–4, pp. 383–398, 1998.

   View at: Publisher Site | Google Scholar | Zentralblatt MATH

4. H. Takagi and A. M. K. Tarabia, “Explicit probability density function for the length of a busy period in an M/M/1/K queue,” in Advances in Queueing Theory and Network Applications, chapter 12, pp. 213–226, Springer, New York, NY, USA, 2009.

   View at: Google Scholar

5. A. M. K. Tarabia, “A new formula for the transient behaviour of a non-empty M/M/1/∞ queue,” Applied Mathematics and Computation, vol. 132, no. 1, pp. 1–10, 2002.

   View at: Publisher Site | Google Scholar | Zentralblatt MATH

6. A. Al Hanbali and O. Boxma, “Busy period analysis of the state dependent M/M/1/K queue,” Operations Research Letters, vol. 38, no. 1, pp. 1–6, 2010.

   View at: Publisher Site | Google Scholar | Zentralblatt MATH

7. D. Gross and C. Harris, Fundamentals of Queuing Theory, Wiley Series in Probability, 3rd edition, 2003.

8. M. F. Neuts, “The single server queue in discrete time-numerical ananlysis,” Naval Research Logistic Quart., vol. 20, no. 1, pp. 297–304, 1973.

   View at: Google Scholar

9. A. W. Berger and W. Whitt, “Maximum values in queueing processes,” Probability in the Engineering and Informational Sciences, vol. 9, no. 3, pp. 375–409, 1995.

   View at: Publisher Site | Google Scholar

10. A. Brandt and M. Brandt, “Waiting times for M/M systems under state-dependent processor sharing,” Queueing Systems, vol. 59, no. 3-4, pp. 297–319, 2008.

    View at: Publisher Site | Google Scholar | Zentralblatt MATH

11. R. F. Serfozo, “Extreme values of birth and death processes and queues,” Stochastic Processes and Their Applications, vol. 27, no. 2, pp. 291–306, 1987.

    View at: Google Scholar | Zentralblatt MATH

12. S. Asmussen, “Extreme value theory for queues via cycle maxima,” Extremes, vol. 1, no. 2, pp. 137–168, 1998.

    View at: Publisher Site | Google Scholar | Zentralblatt MATH

13. J. R. Artalejo, A. Economou, and M. J. Lopez-Herrero, “Algorithmic analysis of the maximum queue length in a busy period for the M/M/c retrial queue,” INFORMS Journal on Computing, vol. 19, no. 1, pp. 121–126, 2007.

    View at: Publisher Site | Google Scholar

14. Y. S. Park, “Asymptotic distributions of maximum queue lengths for M/G/1 and GI/M/1 systems,” Journal of the Korean Statistical Society, vol. 24, no. 1, pp. 19–29, 1994.

    View at: Google Scholar

15. S. Minkevičius, “On extreme value in open queueing networks,” Mathematical and Computer Modelling, vol. 50, pp. 1058–1066, 2009.

    View at: Publisher Site | Google Scholar

16. B. C. Arnold, N. Balakrishnan, and H. N. Nagaraja, A First Course in Order Statistics, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, New York, NY, USA, 1992.

17. H. M. Barakat and Y. H. Abdelkader, “Computing the moments of order statistics from nonidentical random variables,” Statistical Methods & Applications, vol. 13, no. 1, pp. 15–26, 2004.

    View at: Publisher Site | Google Scholar | Zentralblatt MATH

Copyright © 2011 Yousry H. Abdelkader and Maram Al-Wohaibi. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

What are the performance measures of a queuing system?

Which of the following is a measure of performance in queueing analysis?

Which of the following is a common measure of a queue performance?

What are the measures of system performance?