# Performance of an M/M/1 Retrial Queue with Working Vacation Interruption and Classical Retrial Policy

Authors: Tao Li; Liyuan Zhang; Shan Gao
Journal: Advances in Operations Research
 (2016)

---

## Abstract

An M/M/1 retrial queue with working vacation interruption is considered. Upon the arrival of a customer, if the server is busy, it would join the orbit of infinite size. The customers in the orbit will try for service one by one when the server is idle under the classical retrial policy with retrial ratenα, where n is the size of the orbit. During a working vacation period, if there are customers in the system at a service completion instant, the vacation will be interrupted. Under the stable condition, the probability generating functions of the number of customers in the orbit are obtained. Various system performance measures are also developed. Finally, some numerical examples and cost optimization analysis are presented.


---

## Body

## 1. Introduction

Queueing models with server vacations have been well studied in the past three decades and successfully applied in manufacturing and production systems, service systems, and communication systems. Some vacation queues can be found in Tian and Zhang [1]. On the basis of ordinary vacation, Servi and Finn [2] first introduced a class of semivacation policy known as working vacation (WV), where the server provides service at a lower speed during the vacation period rather than stopping service completely. The motivation of analyzing M/M/1/WV queue is to model approximately a multiqueue system where each queue can be served at one of two service rates. From then onwards, several works [3–5] have appeared that analyzed the single server queue with working vacations. In order to utilize the server effectively, Li and Tian [6] introduced vacation interruption policy. During the working vacation period, if at least one customer is present in the system at a service completion epoch, the server will interrupt the vacation and resume regular service. Working vacation interruption has become an important aspect. Using the matrix analytic method, Li and Tian [7] analyzed a GI/Geo/1 queue with working vacations and vacation interruption and Li et al. [8] discussed the GI/M/1 queue. Using the method of a supplementary variable, Zhang and Hou [9] investigated an M/G/1 queue with working vacations and vacation interruption.Retrial queueing systems are described by the feature that the arriving customers who find the server busy join the retrial orbit to try again for their requests. During the last two decades, retrial queues have been studied extensively because of their applications in telephone switching systems, telecommunication networks, and computer systems. Readers can refer to Artalejo and Gómez-Corral [10] and Choudhury et al. [11]. Recently, the retrial queueing systems with working vacations have been investigated extensively. Do [12] first studied an M/M/1 retrial queue with working vacations. Li et al. [13] considered a discrete time Geo/Geo/1 retrial queue with working vacations and vacation interruption and Liu and Song [14] introduced nonpersistent customers into the Geo/Geo/1 retrial queue with working vacations. Tao et al. [15] discussed an M/M/1 retrial queue with collisions and working vacation interruption under N-policy. Using the matrix analytic method, Do [12], Li et al. [13], Liu and Song [14], and Tao et al. [15] obtained the stationary probability distribution and showed the conditional stochastic decomposition for the queue length. Using the method of a supplementary variable, Aissani et al. [16] and Jailaxmi et al. [17] both generalized the model of [12] to an M/G/1 queue. Gao and Wang [18] analyzed a GeoX/G/1 retrial queue with general retrial times and working vacation interruption, and the continuous-time M/G/1 queue was investigated by Gao et al. [19]. Note that the retrial policy of the above papers is either constant retrial policy or general retrial policy, where only the customer at the head of the orbit can request a service.Many of the queueing systems with repeated attempts operate under the classical retrial policy, where each block of customers generate a stream of repeated attempts independently of the rest of the customers in the orbit. In telephone systems, the calls which will be reattempted can be modeled by an infinite server queue where the time until reattempt follows an exponential distribution. Thus, it needs to discuss a retrial queue with working vacation under the classical retrial policy. Ayyappan et al. [20] first studied such a queueing system. In order to obtain the steady state probability vector, the orbit size is restricted to M such that any arriving customer finding the orbit full is considered lost. In this paper, we also analyze an M/M/1 retrial queue with multiple working vacations under the classical retrial policy, and vacation interruption policy is considered. Ayyappan et al. [20] mainly focus on numerical computation and approximation, and they apply the direct truncation method to find the steady state probability vector. We place more emphasis on the analytic solutions, and the orbit size is always infinite in our model. The novelty of this investigation is that we use probability generating function method to deal with the steady state joint distribution of the server state and the number of customers in the orbit, and the ergodicity condition is obtained by Foster’s criterion. Finally, a cost minimization problem is discussed.This paper is organized as follows. In Section2, we establish the model. Using Foster’s criterion, the stable condition is obtained. In Section 3, we get the balance equations and derive the probability generating function of the number of customers in the orbit. Various performance measures of this model are discussed in Section 4. Section 5 presents some numerical examples and cost optimization analysis. Finally, Section 6 concludes the paper.


## 2. Model Formulation and Stable Condition

Let us consider an M/M/1 retrial queue with working vacations and vacation interruption. Customers arrive according to a Poisson process with rateλ. Upon the arrival of customers, if the server is free, arriving customers get service immediately. If the server is occupied, customers are forced to wait in the orbit of infinite size. In this paper, we adopt the classical retrial policy with retrial rate nα, where n is the orbit size. Upon the arrival of retrials, if the server is busy, retrials will go back to the orbit. If the server is not occupied, arriving retrials get services immediately. The service rate is μ when the system is not on vacation. The single server takes a working vacation when the system becomes empty. Vacation time follows an exponential distribution with parameter θ. During the vacation period, customers can be served with rate η. At a service completion instant in the vacation period, if there are customers in the system at that moment, the vacation is interrupted and the server comes back to the normal working level. The working vacation will continue if the system is empty. At the end of each vacation, the server only takes another new vacation if the system is empty.Next, we give an application example of this model. In our daily life, some social organizations can provide telephone psychological counseling. Here, we consider a telephone counseling system staffed with a psychological consultant (called main server) and an assistant (called substitute server). The assistant only provides service to people (called customers) when the consultant does not work. Generally speaking, there is a telephone operator who is responsible for establishing communications between servers and customers; the operator also needs to note down the calls’ information in a registration form (corresponding to the “orbit”). When a person makes a call and if the server is free, the operator notes down the information and the customer is served immediately by the consultant or the assistant. If the server is busy, on the other hand, the operator tells the customer to call again some time later (called retrial), and the customer’s information should also be noted down. When a retrial customer makes a call again, the operator does not need to note down the information again. Moreover, if the customer in the registration form completes his service, the telephone operator will make a note; then he can know whether the customer completed his service or not. When the operator finds that all customers in the registration form have completed their services (i.e., there is no customer in the orbit and the system is empty), the consultant will rest from his work (begin a vacation). During the consultant’s vacation period, the assistant will provide service. If a service is completed by the assistant and if there are customers in the registration form who have not received services (i.e., there are customers in the orbit and the system is nonempty), the consultant will come back from his vacation no matter whether his vacation ends or not (vacation interruption happens). Furthermore, when a vacation ends and if all customers in the registration form have completed their services, the consultant begins another vacation. Otherwise, the consultant takes over the assistant. In order to understand the customer’s need, the consultant will restart service no matter how long the assistant has served.LetQ(t) be the number of customers in the orbit at time t and let J(t) be the state of server at time t. There are four possible states of the server as follows:(1)Jt=0,the  server  is  in  a  working  vacation  period  at  timetand  the  server  is  free,1,the  server  is  in  a  working  vacation  period  at  timetand  the  server  is  busy,2,the  server  is  during  a  normal  service  period  at  timetand  the  server  is  free,3,the  server  is  during  a  normal  service  period  at  timetand  the  server  is  busy.Note that when the orbit is empty, it is impossible that the server is free in a normal service period. Thus,{Q(t),J(t)} is a Markov process with state space (2)Ω=0,j,j=0,1,3∪k,j,k≥1,j=1,2,3.Remark 1.
Note that, in this model, we consider working vacation interruption policy, so the state{(k,0),k≥1} does not exist.Define(3)ak=∫0∞λxkk!e-λxμe-μxdx,bk=∫0∞λxkk!e-λxe-θxηe-ηxdx,ck=∫0∞λxkk!e-λxθe-θxe-ηxdx,where {ak,k≥0} is the probability that k customers arrive during a normal service time; {bk,k≥0} represents the probability that k customers arrive during a lower service time and the working vacation does not end; {ck,k≥0} explains the probability that k customers arrive before the working vacation ends and no service is completed.Let{tn;n=1,2,…} be the sequence of epochs at which a normal service or a lower service completion occurs and Qn=Q(tn+); then the sequence of random variables {Qn;n=1,2,…} forms an embedded Markov chain.Theorem 2.
The embedded Markov chain{Qn;n=1,2,…} is ergodic if and only if ρ=λ/μ<1.Proof.
It is not difficult to see that{Qn;n=1,2,…} is an irreducible and aperiodic Markov chain, and the transition probability is given by (4)P=P00P01P02P03⋯P10P11P12P13⋯0P21P22P23⋯00P32P33⋯⋮⋮⋮⋮⋱,where(5)Pnk=bk+∑j=0kcjak-j,n=0,k≥0,nαnα+λa0,n≥1,k=n-1,nαnα+λak+1-n+λnα+λak-n,n≥1,k≥n.In order to discuss the ergodicity of the chain {Qn;n=1,2,…}, we use Foster’s criterion with the mean drift (6)xn=EfQk+1-fQk∣Qk=n,where the test function f(n)=n. From the transition matrix, it can be easily proved that (7)xn=ρθθ+η+λθ+η,n=0,ρ-nαnα+λ,n≥1.As n→∞, there exists x=limn→∞xn=ρ-1. Applying Foster’s criterion, we can get that the embedded Markov chain is ergodic if ρ<1. Besides, since Qn+1-Qn≥-1, applying the criterion from Sennott et al. [21], we can obtain that ρ<1 is necessary for ergodicity.Since the arrival process is Poisson, using PASTA property, it can be shown from Burke’s theorem (see [22, pp. 187-188]) that the steady state probabilities of the Markov process {Q(t),J(t)} exist if and only if the stable condition ρ<1 holds. Now we define the limiting probability (8)πkj=PQ=k,J=j=limt→∞⁡PQt=k,Jt=j,k,j∈Ω.


## 3. Balance Equations and Probability Generating Functions

Figure1 presents the state transition rate diagram of the system. Under the stable condition ρ<1, the set of balance equations is given as follows:(9)λπ00=ηπ01+μπ03,(10)λ+θ+ηπ01=λπ00,(11)λ+μπ03=απ12+θπ01,(12)λ+θ+ηπn1=λπn-1,1,n≥1,(13)λ+nαπn2=ηπn1+μπn3,n≥1,(14)λ+μπn3=λπn2+λπn-1,3+n+1απn+1,2+θπn1,n≥1.Define the probability generating functions (pgfs)(15)G1z=∑n=0∞πn1zn,G2z=∑n=1∞πn2zn,G3z=∑n=0∞πn3zn,with Gi′(z)=∑n=1∞‍nπnizn-1,i=1,2,3.Figure 1
State transition rate diagram of the system.Multiplying by the appropriate power ofzn in (10) and (12), summing over n, and rearranging the terms, we get(16)λ+θ+η-λzG1z=λπ00.Multiplying by the appropriate power of zn in (13), summing over n, and using (9), we obtain(17)λG2z+αzG2′z=ηG1z+μG3z-ηπ01-μπ03=ηG1z+μG3z-λπ00.In a similar way, from (11) and (14), we derive(18)λ+μ-λzG3z=λG2z+αG2′z+θG1z.From (16), we get(19)G1z=λλ+θ+η-λzπ00.From (17), we obtain(20)G3z=λμG2z+αzμG2′z-ημG1z+λμπ00.Taking (20) into (18), using (19), after some computation, we can derive (21)G2′z-λ2μ-λzαG2z=λ2π00μ-λz1-zα+λπ001-zα-ηλπ00λ+θ+η-λz1-zα-θμ+ληλπ00λ+θ+η-λzμ-λz1-zα.Solving the first-order differential equation, we have(22)G2z=μ-λz-λ/αλ2π00αK1z+λπ00αK2z-ληπ00αK3z-θμ+ληλπ00αK4z,where(23)K1z=∫0z1-x-1μ-λxλ/α-1dx,K2z=∫0z1-x-1μ-λxλ/αdx,K3z=∫0zλ+θ+η-λx-11-x-1μ-λxλ/αdx,K4z=∫0zλ+θ+η-λx-11-x-1μ-λxλ/α-1dx.From (17) and (18), substituting G2′(z), we get(24)G3z=λ1-zG2z-η+θzG1z+λπ00μ-λz1-z.From (19), (22), and (24), we can see that G1(z), G2(z), and G3(z) are expressed in terms of π00. In the next section, using normalization condition, we will obtain π00.


## 4. Performance Measures

From (19), we have(25)G11=λθ+ηπ00,(26)G1′1=limz→1⁡G1′z=limz→1⁡λ2λ+θ+η-λz2π00=λ2θ+η2π00.From (22), we get(27)G21=Kπ00,where(28)K=μ-λ-λ/αλ2αK11+λαK21-ληαK31-θμ+ληλαK41.From (24), using L’Hospital rule, we obtain(29)G31=limz→1⁡G3z=limz→1⁡-λG2z+λ1-zG2′z-θG1z-η+θzG1′z-λ1-z-μ-λz=λG21+θG11+η+θG1′1μ-λ=λKθ+η+λθ+λ2μ-λθ+ηπ00.Since(30)π00+G11+G21+G31=1,taking (25), (27), and (29) into the above equation, we can derive (31)π00=1+λθ+η+K+λKθ+η+λθ+λ2μ-λθ+η-1=λμ-η+μ1+Kθ+ημ-λθ+η-1.Thus, π00 is found out. From (19), (22), and (24), G1(z), G2(z), and G3(z) are completely computed. And the pgf of the number of customers in the orbit is given by(32)Gz=π00+G1z+G2z+G3z.The pgf of the number of customers in the system is given by (33)G~z=π00+zG1z+G2z+zG3z.Let E[Lj] denote the average number of customers in the orbit when the server’s state is j,j=1,2,3.Differentiating (19) with respect to z, we have (34)EL1=limz→1⁡G1′z=λ2θ+η2π00.From (18), we can get (35)EL2=limz→1⁡G2′z=μαG31-λαG21-θαG11.Differentiating (24) with respect to z and using L’Hospital rule twice, the expression for E[L3] is obtained as(36)EL3=limz→1⁡G3′z=μ-λθ+ηG1′′1+2θμ+ληEL1+2λμ-λEL2+2λθG11+λG212μ-λ2,and differentiating (19) twice with respect to z and taking z=1 yield G1′′(1) as (37)G1′′1=2λ3θ+η3π00.Therefore, the average orbit length (E[L]) is given by (38)EL=limz→1⁡G′z=EL1+EL2+EL3.And the average system length (E[L~]) is derived as (39)EL~=limz→1⁡G′~z=EL+G11+G31.The probability that the server is busy is (40)Pb=PJ=1+PJ=3=G11+G31.The probability that the server is free is (41)Pf=PJ=0+PJ=2=π00+G21=1-Pb.The probability that the server is in a working vacation period is given by (42)Pw=PJ=0+PJ=1=π00+G11.The probability that the server is in a normal service period is given by (43)Pn=PJ=2+PJ=3=G12+G23=1-Pw.Let E[W] (E[W~]) be the expected waiting (sojourn) time of a customer in the orbit (system), using Little’s formula: (44)EW=ELλ,EW~=EL~λ.The system busy period T is defined as the period that starts at an epoch when an arriving customer finds an empty system and ends at the departure epoch at which the system is empty. Using the theory of regenerative process, we get (45)π00=ET00ET00+ET,where T00 is the time length that the system is in the state (0,0). Since the interarrival time between two customers follows exponential distribution with parameter λ, we have E[T00]=1/λ. Thus, E[T]=λ-1(π00-1-1).


## 5. Numerical Results

In this section, under the stable condition, we present some numerical examples to illustrate the effect of the varying parameters on the mean orbit lengthE[L], the probability that the system is busy 1-π0,0, and the probabilities of server’s state (Pb, Pf, Pw, and Pn). Moreover, a cost minimization problem is also discussed. The various parameters of this model are arbitrarily chosen as λ=2, η=1, μ=5, α=3, and θ=0.2, unless they are considered as variables or their values are mentioned in Figures 2, 3, 4, and 5.Figure 2
The effect ofθ on E[L] for different values of η.Figure 3
The effect ofθ on 1-π0,0 for different values of η.Figure 4
The effect ofη on E[L] for two different retrial policies.Figure 5
The probability of server’s state with the change ofη.


### 5.1. Sensitivity Analysis

Figures2 and 3 illustrate the effect of θ on E[L] and 1-π0,0 for different values of η, respectively. When η<μ, we find that E[L] and 1-π0,0 both decrease as θ increases, and θ has a noticeable effect on the performance measures which cannot be ignored. An especial case is η=μ; that is, the service rate in the vacation period is equal to the service rate in the normal period, and the model we consider reduces to an M/M/1 retrial queue with classical retrial policy. Clearly, θ has no effect on E[L] and 1-π0,0, which agrees with the intuitive expectation.The effect ofη on E[L] is presented in Figure 4; as expected, E[L] decreases with increasing values of η. When η is large, it can be observed that the effect of η on E[L] is not obvious as η increases; this is because we consider working vacation interruption policy. If the system is not empty at a service completion instant in the vacation period, the server will come back to the normal working level. Moreover, since constant retrial policy means that only the customer at the head of the orbit can request a service, we can find that E[L] of M/M/1 queue with classical retrial policy is smaller than that of M/M/1 queue with constant retrial policy. As shown in Figure 5, Pb decreases with increasing values of η, and Pf has the opposite tendency. The reason is that as η increases, the mean orbit length E[L] and the mean service time 1/η both decrease.Figure6 indicates that E[L] decreases with increasing values of α; this is because the mean retrial time decreases as α increases. From the instant when the server becomes idle, an external potential primary customer and retrial customers compete to access the server, and the smaller the mean retrial time is, the bigger the probability that the server is busy is, which leads to decreasing of E[L]. Furthermore, under the same condition, decreasing of E[L] results in the increase in the probability that the system is empty, and Figure 7 reveals that Pw increases with increasing values of α, while Pn decreases as α increases. In Figure 6, compared with constant retrial policy, we can also find that classical retrial policy decreases the waiting jobs effectively.Figure 6
The effect ofα on E[L] for two different retrial policies.Figure 7
The probability of server’s state with the change ofα.


### 5.2. Cost Analysis

In this subsection, we establish a cost function to search for the optimal service rateη, so as to minimize the expected operating cost function per unit time.Define the following cost elements:CL: cost per unit time for each customer present in the orbit.Cμ: cost per unit time for service during a normal service period.Cη: cost per unit time for service in a working vacation period.Cθ: fixed cost per unit time during a vacation period.Based on the definitions of each cost element listed above, the expected operating cost function per unit time can be given by(46)minη:fη=CLEL+Cμμ+Cηη+Cθθ.Because the expected operating cost function is highly nonlinear and complex, it is not easy to get the derivative of it. We assume CL=6, Cμ=10, Cη=8, and Cθ=4 and develop approximations by MATLAB program to find the optimum value of η, say η∗.From Figure8, we can see that there is an optimal service rate η to minimize the cost. Implementing the computer software MATLAB by the parabolic method and controlling the error by 10-4, we find the solution η∗=0.8584 with f(η∗)=69.0971.Figure 8
Effect ofη on the expected operating cost per unit time.


## 5.1. Sensitivity Analysis

Figures2 and 3 illustrate the effect of θ on E[L] and 1-π0,0 for different values of η, respectively. When η<μ, we find that E[L] and 1-π0,0 both decrease as θ increases, and θ has a noticeable effect on the performance measures which cannot be ignored. An especial case is η=μ; that is, the service rate in the vacation period is equal to the service rate in the normal period, and the model we consider reduces to an M/M/1 retrial queue with classical retrial policy. Clearly, θ has no effect on E[L] and 1-π0,0, which agrees with the intuitive expectation.The effect ofη on E[L] is presented in Figure 4; as expected, E[L] decreases with increasing values of η. When η is large, it can be observed that the effect of η on E[L] is not obvious as η increases; this is because we consider working vacation interruption policy. If the system is not empty at a service completion instant in the vacation period, the server will come back to the normal working level. Moreover, since constant retrial policy means that only the customer at the head of the orbit can request a service, we can find that E[L] of M/M/1 queue with classical retrial policy is smaller than that of M/M/1 queue with constant retrial policy. As shown in Figure 5, Pb decreases with increasing values of η, and Pf has the opposite tendency. The reason is that as η increases, the mean orbit length E[L] and the mean service time 1/η both decrease.Figure6 indicates that E[L] decreases with increasing values of α; this is because the mean retrial time decreases as α increases. From the instant when the server becomes idle, an external potential primary customer and retrial customers compete to access the server, and the smaller the mean retrial time is, the bigger the probability that the server is busy is, which leads to decreasing of E[L]. Furthermore, under the same condition, decreasing of E[L] results in the increase in the probability that the system is empty, and Figure 7 reveals that Pw increases with increasing values of α, while Pn decreases as α increases. In Figure 6, compared with constant retrial policy, we can also find that classical retrial policy decreases the waiting jobs effectively.Figure 6
The effect ofα on E[L] for two different retrial policies.Figure 7
The probability of server’s state with the change ofα.


## 5.2. Cost Analysis

In this subsection, we establish a cost function to search for the optimal service rateη, so as to minimize the expected operating cost function per unit time.Define the following cost elements:CL: cost per unit time for each customer present in the orbit.Cμ: cost per unit time for service during a normal service period.Cη: cost per unit time for service in a working vacation period.Cθ: fixed cost per unit time during a vacation period.Based on the definitions of each cost element listed above, the expected operating cost function per unit time can be given by(46)minη:fη=CLEL+Cμμ+Cηη+Cθθ.Because the expected operating cost function is highly nonlinear and complex, it is not easy to get the derivative of it. We assume CL=6, Cμ=10, Cη=8, and Cθ=4 and develop approximations by MATLAB program to find the optimum value of η, say η∗.From Figure8, we can see that there is an optimal service rate η to minimize the cost. Implementing the computer software MATLAB by the parabolic method and controlling the error by 10-4, we find the solution η∗=0.8584 with f(η∗)=69.0971.Figure 8
Effect ofη on the expected operating cost per unit time.


## 6. Conclusion

This paper analyzes a single server retrial queue with working vacation interruption under the classical retrial policy. Using embedded Markov chain and Foster’s criterion, we get the condition of stability. The pgf of the number of customers in the orbit is obtained, and some important performance measures are also discussed. Moreover, the effects of various parameters on the system performance measures are examined numerically. Under the stable condition, a cost minimization problem is considered. For future research, using the same method, one can investigate a similar model with batch arrival and without vacation interruption.



---

*Source: 4538031-2016-05-30.xml*