Analysis of M/G/1 queueing model with state dependent arrival and vacation

This investigation deals with single server queueing system wherein the arrival of the units follow Poisson process with varying arrival rates in different states and the service time of the units is arbitrary (general) distributed. The server may take a vacation of a fixed duration or may continue to be available in the system for next service. Using the probability argument, we construct the set of steady state equations by introducing the supplementary variable corresponding to elapsed service time. Then, we obtain the probability generating function of the units present in the system. Various performance indices, such as expected number of units in the queue and in the system, average waiting time, etc., are obtained explicitly. Some special cases are also deduced by setting the appropriate parameter values. The numerical illustrations are provided to carry out the sensitivity analysis in order to explore the effect of different parameters on the system performance measures.

In some daily life congestion problems, the service time of the units may not follow exponential distribution. Such situations can be noticed in the clinics performing X-rays and blood test, etc. of patients and in bank at cash counters and many other places. In queueing systems with arbitrary service time distribution, the number of units in the system at time t and the length of time for which the unit is in service (if any) are sufficient to determine the future stochastic properties of these variables. Several researchers have contributed in the direction of general distributed service time queueing system. To mention a few notable works of researchers in this area, we refer [Baba (1986]), [Doshi (1990]) and [Medhi (1997]) and references cited therein. The queueing system under the special consideration with respect to idle period (i.e., vacation) is not new. [Levy and Yechiali (1975]) have considered such model under the assumption that the server takes a sequence of vacations until it finds at least one unit is waiting in the system. The analysis of M/G/1 queue by using the method of supplementary variables has been done by [Takagi (1991]).

[Kimura (1981]) assumed general service time distribution function and used a diffusion approximation technique to determine the optimal policy. The queueing model with setup and vacation was considered by [Choudhury (2000]). Further, [Choudhury (2002]) studied a queueing system with two different vacation times under multiple vacation policy. Single server queueing system with time homogeneous breakdowns and deterministic repair times was analyzed by [Madan (2003]). [Wang (2004]) worked on the M/G/1 queueing system with second optional service and server breakdown. The multiple vacations system was considered by [Wu and Takagi (2006]). [Choudhury (2008]) discussed the queue size distribution of a queue with a random set-up time and Bernoulli vacation schedule under a restricted admissibility policy.

Recently, [Maraghi et al. (2009]) have studied batch arrival queueing system with random breakdowns and Bernoulli schedule random vacations having general vacation time. They have obtained steady state results in terms of probability generating functions for the number of customers in the queue. [Choudhury and Kalita (2009]) studied the steady state behavior of a model with repeated attempts and Bernoulli vacation schedule, which was a generalization of the classical model. [Banik (2010]) analyzed a queueing system with a single working vacation to obtain the performance measures using the embedded Markov chain. [Thangraj and Vanitha (2010]) discussed the single server model with two stages of heterogeneous service with different service time distributions subject to random breakdowns and compulsory service vacations with arbitrary vacation periods.

The queueing system with server vacations can be used to model a system wherein the server stops working during a vacation. Such system has wide applicability in analyzing the performance of various real life traffic situations of day-to-day as well as industrial queues. In some systems, the arrival of the units occurs according to a Poisson process or general distributed fashion with different arrival rates depending on the server's status.

[Madan (1999]) discussed the steady state behavior of an arbitrary service time queue with deterministic service vacation. In his investigation, he has considered that the customers arrive at the system with uniform arrival rates. In many congestion scenarios, the arrival rates of the customers are influenced by the status of the server. The queueing models with variable arrival rates of the units can be observed in health care systems. Besides this, it is applicable in the banks, at the checkout counters in the supermarket, etc. In some industrial scenario, the arrival rate of the units may also be dependent upon the states of the system, especially in production and manufacturing systems, wherein the management may optimize the cost of inventory by controlling the arrival rate of new units.

The present investigation is the extension of vacation model for single server general distributed service time studied by [Madan (1999]) and addresses the analysis of M/G/1 queueing system with deterministic server vacation in which the arrival rate of the units are state dependent. The layout of the investigation is as follows: The model description, by stating the requisite assumptions and notations, is given in the Model description section. In The steady state equations section, we construct the set of steady state equations by introducing the supplementary variable corresponding to elapsed service time. In The analysis section, we obtain the probability generating function of the queue size distribution in different states. Some system characteristics of the model are presented in Performance measures section. By selecting appropriate parameter values, some special cases are deduced in Special cases section. In Numerical illustration section, numerical illustration is provided to explore the effect of different parameters on the performance measures. In the Conclusions section, the noble features and future scope of the present model are highlighted.

Model description

Consider M/G/1 queueing system with deterministic server vacations under the following assumptions:

· The server may decide to take a vacation of fixed length d (>0) at the completion of each service with probability p or may continue to be available in the system for the next service with probability 1 p.

· The units arrive in the system according to Poisson fashion with state dependent rates.

· The service of the units is rendered according to the general (arbitrary) distribution.

· The FCFS service discipline is followed to select the customer for the service.

The notations used in the formulation of the model are as follows:

λ₁: mean arrival rate of the units in idle state

λ₂(λ₃): mean arrival rate of the units in busy (vacation) state

B(v): distribution function of the service time

b(v): density function of service time

: Laplace transform of b(.)

x: elapsed service time

μ(x)dx: hazard rate of completion of the service of the unit during the interval (x, x + dx) with elapsed time x

K_r: probability of r arrivals during a vacation period

n: number of units in the queue, excluding the unit, which is in service (0)

W_n(t,x): probability of n units in the system at time t when the server is busy in rendering service to the unit with elapsed service time lying between x and x + dx

V_n(t): probability of n units in the queue at time t when the server is on vacation

Q(t): probability that there are no units in the system and the server is in idle state at time t

P_q(z): probability generating function of the queue length whether the server is on vacation or available in the system

P(z): probability generating function of the number of units in the system

The hazard rate (x) is given by Equation 1:

where,

In steady state, we have Equation 3:

and Equation 4

The steady state equations

In this section, we formulate the set of governing equations of the system using the appropriate rates as follows:

The above equations are to be solved subject to the following boundary conditions:

We define the following probability generating functions:

The analysis

In order to derive various performance indices, we obtain the probability generating function of the number of units in the system using the above set of equations as follows: on multiplying Equations 5 and 6 by zⁿ, summing over n and using Equation 11, we have Equation 12:

Similarly, multiplying Equation 8 by zⁿ, summing over n and using Equation 11, we have Equation 13:

Now, we obtain

Using Equations 9 to 11, we derive Equation 14:

With the help of Equation 7, the above Equation can be written as

From Equation 12, we get Equation 16:

Using Equation 16, we have Equation 17:

where

Theorem 1The probability generating function of the queue length, whether the server is on vacation or available in the system is

Proof: For proof, see Proof of Theorem 1^a in the Endnotes section.

Theorem 2The probability generating function of the number of units in the system is

Proof: For proof, see Proof of Theorem 2^b in the 'Endnotes' section.

Performance measures

Now, we shall establish various performance measures using the probability generating function of the queue length as follows:

Theorem 3The expected number of units in the queue is

Proof: The expected number of units in the queue (L_q) is obtained using

For detailed proof, see Proof of Theorem 3^c in the Endnotes section.

The expected number of units in the system can be obtained as

The expected waiting time in the queue is given by Little's formula

Special Cases

It is worthwhile to establish the performance measures in some special cases by setting appropriate parameters to tally our results with some existing results. When p = 0, Equation 20 gives

This provides the average queue length of M/G/1 model with state dependent rates. For no server vacation model, when units arrive according to Poisson fashion with homogeneous rate (λ) in all states by setting λ = λ₁ = λ₂ = λ₃, we have Equation 24:

Equation 24 provides the well-known result of M/G/1 queue (see [Gross and Harris 2003]).

In M/E_k/1 deterministic vacation queueing model, we put

Equation 20 reduces to

In M/M/1 deterministic vacation queueing model, we set

in Equation 20 so that

Numerical Illustration

In this section, we present the numerical illustration to evaluate the queue size distribution for the single server deterministic vacation model using the analytical results derived in previous section. The effects of variation of service rate (μ), vacation time (d) and vacation probability (p) on the queue length are displayed in Tables1 and 2. The service time assumed to be generally distributed, therefore, second moment of service time E(v²) for different distributions are as follows:

· M/E_k/1 deterministic vacation model:

· M/M/1 deterministic vacation model:

· M/D/1 deterministic vacation model: .

For computation purposes, we set default parameters as λ₁ = 1.0λ, λ₂ = 0.9λ, λ₃ = 0.7λ, p = 0.02 and d = 3. From Tables1 and 2, we observe that the queue length (L_q) decreases with the increase in service time. It is also noticed that the queue length decreases with the increase in the number of service phases (k). As far as the effects of parameters d and p are concerned, we see that the L_q increases significantly with the increment of both d and p.

Figure1a,b respectively reveals that the L_q increases with the increase in arrival rate (λ). However, the effect is more prevalent for higher values of . Figure2a,b exhibits the queue length L_q for M/M/1 and M/E₅/1 models by varying p. It is observed that the L_q increases with the increase in as well as p; the increment is more significant for larger values of and p. Figure3a,b reveal that the L_q decreases with the increase in the number of phases ( k ).

Finally, we conclude that when arrival rate (service rate) increases, the queue length increases (decreases); this situation matches with our expectation in various real life congestion problems. The queue length decreases with the increase in the number of service phases. The queue length increases slightly with the increase in the vacation time as well as vacation probability for low traffic condition, but as traffic increases, there is remarkable increase in it. Therefore, in case of heavy traffic, the frequent vacation of the server has adverse effect on the grade of service and it should be avoided as much as possible.

For the real life congestion situations, where the arrival of units depends on the status of the server, our study may be very helpful in the design and development phases of the concerned systems. The fields of distributed computer system, wireless communications, production and manufacturing system, etc. have the major sources of motivation for the growth and creation of such queueing models.

In this investigation, we have studied the steady state behavior of a single server queueing model with vac-ation and varying arrival rates. The supplementary variable method is used to determine the probability generating function of the queue size which is further employed to evaluate other performance measures in explicit form. The sensitivity analysis is carried out which demon-strates the computational tractability and validity of the analytical results.

^aProof of Theorem 1 From Equations 2 and 16, we get Equation 27

On using Equation 27 in Equation 15, we have

On using Equation 28, Equation 17 gives,

With the help of Equation 27, Equation 13 becomes

On using Equation 28, from Equation 30 we have

On simplifying Equation 31, we have

From Equations 29 and 32, we get

Since; and , we have

and

The normalizing condition gives the unknown constant Q as

From Equation 36 we get

On using Equation 36 in Equations 32 and 33, we have

On adding Equations 38 and 39, we have

^bProof of Theorem 2 By using Equations 36 and 40, we get

^cProof of Theorem 3 From Equation 40, we have

where

On using above values, Equation 42 gives the result as given in Equation 20.

The authors declare that they have no competing interests.

CJS has worked on the modeling and analysis of non-markovian M/G/1 model. The queue size distribution and various performance measures via. queue theoretic approach based on supplementary variable and generating function method have been obtained by MJ. BK has performed numerical experiment and carried out sensitivity analysis by taking an illustration. All authors read and approved the final manuscript.

Charan Jeet Singh is Associate Professor in the department of Mathematics, Guru Nanak Dev University, Amritsar (India). Madhu Jain is a faculty member in the department of Mathematics, I.I.T. Roorkee (India). Binay Kumar is Lecturer in the department of Mathematics, M.L.U. DAV College, Phagwara (India).

The authors are thankful to the learned referee and editor for their valuable comments and suggestions for the improvement of the paper. First author is also thankful to the University Grants Commission, New Delhi for the financial support under major research project no. 37-191/2009 (SR).

1. Baba Y (1986) On the Mx/G/1 queue with vacation time. Operation Res Letter 5:93-98 Publisher Full Text

2. Banik AD (2010) Analysis of single working vacation in GI/M/1/N and GI/M/1/ queueing system. Int J Operational Res 7(3):314-333 Publisher Full Text

3. Choudhury G (2000) An Mx/G/1 queueing system with a setup period and vacation period. QUESTA 36:23-28

4. Choudhury G (2002) Some aspects of M/G/M queue with two different vacation times under multiple vacation policy. Stoch Anal Appl 20(5):901-909 Publisher Full Text

5. Choudhury G (2008) A note on the Mx/G/1 queue with a random set-up time under a restricted admissibility policy with a Bernoulli vacation schedule. Statistical Methodology 5:21-29 Publisher Full Text

6. Choudhury G, Kalita S (2009) A two-phase queueing system with repeated attempts and Bernoulli vacation schedule. Int J Operational Res 5(4):392-407 Publisher Full Text

7. Doshi BT (1990) Single server queues with vacations. In: Takagi H (ed) Stochastic analysis of computer and communication systems, Elsevier, North-Holland, Amsterdam. pp 217-265

8. Gross D, Harris CM (2003) Fundamentals of queueing theory. Wiley, New York.

9. Kimura T (1981) Optimal control of an M/G/M queueing system with removable server via diffusion approximation. Eur J Oper Res 8:390-398 Publisher Full Text

10. Levy Y, Yechiali U (1975) Utilization of idle time in an M/G/M queueing system. Manag Sci 22:202-211 Publisher Full Text

11. Madan KC (1999) An M/G/M queue with optional deterministic server vacations. Metron 57(34):83-95

12. Madan KC (2003) An M/G/M type queue with time homogeneous breakdowns and deterministic repair times. Soochow J Mathematics 29(1):103-110

13. Maraghi FA, Madan KC, Dowman KD (2009) Batch arrival queueing system with random breakdowns and Bernoulli schedule server vacations having general time distribution. Int J Inf Manag Sci 20:55-70

14. Medhi J (1997) Single server queueing system with poisson input: a review of some recent development. In: Balakrishnann N (ed) Advances in combinatorial method and applications in probability and statistics, Birkhauser, Switzerland.

15. Takagi H (1991) Queueing analysis. A foundation of performance evaluation, vacation and priority systems. , Elsevier, Amsterdam.

16. Thangraj V, Vanitha S (2010) M/G/M queue with two stage heterogeneous service compulsory server vacation and random breakdowns. Int J Contemporary Mathematical Sci 5(7):307-322

17. Wang J (2004) An M/G/M queue with second optional service and server breakdowns. Computers and Mathematics with Applications 47:1713-1723 Publisher Full Text

18. Wu DA, Takagi H (2006) M/G/M queue with multiple working vacations. Perform Eval 63:54-681