Discrete-time retrial queue with Bernoulli vacation, preemptive resume and feedback customers

Chen, Peishu; Zhou, Yongwu; Li, Changwen Article Discrete-time retrial queue with Bernoulli vacation, preemptive resume and feedback customers Journal of Industrial Engineering and Management (JIEM) Provided in Cooperation with: The School of Industrial, Aerospace and Audiovisual Engineering of Terrassa (ESEIAAT), Universitat Politècnica de Catalunya (UPC) Suggested Citation: Chen, Peishu; Zhou, Yongwu; Li, Changwen (2015) : Discrete-time retrial queue with Bernoulli vacation, preemptive resume and feedback customers, Journal of Industrial Engineering and Management (JIEM), ISSN 2013-0953, OmniaScience, Barcelona, Vol. 8, Iss. 4, pp. 1236-1250, https://doi.org/10.3926/jiem.1487 This Version is available at: https://hdl.handle.net/10419/188732 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/3.0/ Journal of Industrial Engineering and Management JIEM, 2015 – 8(4): 1236-1250 – Online ISSN: 2013-0953 – Print ISSN: 2013-8423 http://dx.doi.org/10.3926/jiem.1487 Discrete-time Retrial Queue with Bernoulli Vacation, Preemptive Resume and Feedback Customers Peishu Chen, Yongwu Zhou, Changwen Li* School of Business Administration, South China University of Technology (China) [email protected], [email protected], *Corresponding author: [email protected] Received: April 2015 Accepted: September 2015 Abstract: Purpose: We consider a discrete-time retrial queue where the retrial time follows a general distribution, the server subject to Bernoulli vacation policy and the customer has preemptive resume priority, Bernoulli feedback strategy. The main purpose of this paper is to derive the generating functions of the stationary distribution of the system state, the orbit size and some important performance measures. Design/methodology/approach: Using probability generating function technique, some valuable and interesting performance measures of the system are obtained. We also investigate two stochastic decomposition laws and present some numerical results. Findings: We obtain the probability generating functions of the system state distribution as well as those of the orbit size and the system size distributions. We also obtain some analytical expressions for various performance measures such as idle and busy probabilities, mean orbit and system sizes. Originality/value: The analysis of discrete-time retrial queues with Bernoulli vacation, preemptive resume and feedback customers is interesting and to the best of our knowledge, no other scientific journal paper has dealt with this question. This fact gives the reason why efforts should be taken to plug this gap. Keywords: discrete-time queue, Bernoulli vacation, preemptive resume, Bernoulli feedback, general retrial time, stochastic decomposition -1236- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1487 1. Introduction More and more scholars are interested in analysis of discrete time queues due to their applications in communication system and other related areas (Bruneel & Kim, 1992; Takagi, 1993; Singh & Sreenivas, 2014; Wei, Qin & He, 2014). The analysis of discrete-time queues is very important and more suitable than their continuous-time counterparts for modeling telecommunication and computer systems, on account of these systems operate on a discretetime basis where events can only happen at regularly spaced epochs. More importantly, discrete-time models can be used to deduce the results for continuous-time models but not vice versa (Bruneel & Kim, 1992). Various classes of vacation mechanism have been discussed in the literature. Takagi (1993) investigated on discrete-time systems with vacations in his splendid monograph. Zhang and Tian (2001) presented a discrete queue with multiple adaptive vacations where the number of vacation is considered as random variable. Luo, Huang and Ding (2014) studied on the departure process of discrete-time queue with randomized vacations. Researches on Bernoulli vacation policy are relatively less. Servi (1986) and Ramaswamy and Servi (1988) have introduced the M/G/1 Bernoulli schedule: If the queue is empty after a service completion, then the server begins a vacation period. If there are customers in the orbit after a service completion, then another service begins with specified probability p or a vacation period begins with supplementary probability q = 1 - p. At the end of a vacation period, the server waits for service the next customer. In recent years, Wenhui (2005) study a continues-time retrial queue with Bernoulli vacation. Samanta (2009) analyzed a GI/Geo/1 queue with single Bernoulli vacation based on exhaustive service. Wang (2012) extended a continues-time retrial queue with Bernoulli vacation to the discrete-time Geo/G/1 retrial queues with Bernoulli vacation. Queueing models with preemptive resume phenomenon are characterized by the fact that arriving customers have the right to interrupt the customers in service and begin their own service with LCFS discipline. It occurs in many situations in our real life such as dealing with emergency patient in hospital and treating to transmission of information systems. Kumar, Vijayakumar and Arivudainambi (2002) studied an M/G/1 retrial system with two-phase service and preemptive resume. Wu, Liu and Peng (2011) investigated a discrete-time Geo/G/1 retrial queue with preemptive resume and collisions. Wei et al. (2014) discussed Geo/G/1 retrial queue with preemptive resume and Bernoulli feedback. Retrial queues are characterized by the feature that customers who find the server busy upon arrival are forced to leave the server temporarily and repeat their demand after a random time. A more realistic retrial queue with feedback phenomenon happens in many real world situations: for example, in communication networks where data transmissions need to be ensured error free within a certain probability, feedback scheme is used to request retransmission of packets that are lost or damaged in communication systems. Choi and -1237- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1487 Kulkarni (1992) have investigated M/G/1 retrial queue with feedback. Kumar, Vijayalakshmi, Krishnamoorthy and Basha (2010) have analyzed a single server retrial queue with linear retrial rate, collisions and feedback customers. The analysis of discrete-time retrial queues with Bernoulli vacation, preemptive resume and feedback customers is interesting and no work in this direction is found in the queueing literature at present. This fact gives the reason why efforts should be taken to plug this gap. The remainder of the paper is organized as follows. In Section 2, we give the mathematical model description of the considered queueing system. In Section 3, we study the Markov chain, and derive the probability generating functions of the system state, the orbit size and the system size distribution. We also obtain several performance measures of the system. In Section 4, we find two different stochastic decomposition laws. Some numerical results to illustrate the impact of the Bernoulli vacation policy, preemptive resume and feedback on the performance of the system are considered in Section 5. Finally, we give a conclusion in Section 6. 2. Model Description We take into account a discrete-time single server retrial queue where the time axis is divided into slots and the time axis is marked by 0, 1,...,m,.... We further assume that all queueing activities (arrivals, departures, retrials, vacations) occur at the slot boundaries. Since in discrete time systems, many events may occur at the same time, we must impose additional assumptions to ensure that our model follows the evolution of the underlying process. For mathematical clarity, we suppose that the departures, Bernoulli feedback and the end of the vacations occur in the interval (m-, m) in sequence, and the primary arrivals, the preemptive resume, the retrials, the beginning of a vacation occur in the interval (m, m+) in sequence, that is, early arrival scheme (known also as departure first rule) is adopted in this paper. New customers arrive from outside of the system according to a geometrical arrival process with rate p. We assume that there is no waiting space in front of the server, and therefore, if an arriving customer finds the server idle, he begins his service immediately. Otherwise, if the server is busy at the arrival epoch, the arriving customer either interrupts the customer in service to commence his own service with probability a or leaves the server and enters the orbit with probability a = 1 - a . The interrupted customer enters into the orbit. The server will take a single vacation with probability h once he completes a service process, or start a process of search in order to find the next customer to be served with probability h = 1 - h . If the system is on vacation, the arriving customer leaves the service area and enters the orbit. After vacation, the server becomes free and waits for the next customer. It is called “Bernoulli vacation” policy in this paper. After service completion, the customer decides either to join the orbit for another service with probability q or leaves the system with complementary probability q = 1 - q . The customers in the orbit retry in accordance with a first-come, first- -1238- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1487 serve discipline, that is, only the customer at the head of the orbit queue is permitted to access to the server. Successive inter-retrial times of any customer are governed by an arbitrary distribution { ai } i=0 +∞ with generating function A(x)=∑ i=0 +∞ aixi . Service times are governed by probability distribution { si } i=1 +∞ with generating function S(x)=∑ i=1 +∞ sixi and the n = th factorial moment b 1,n. The vacation times are independent and identically distributed with arbitrary distribution { vi } i=1 +∞ , generating function V(x)=∑ i=1 +∞ vixi and the n = th factorial moment b 2,n. Here we pointed out that various stochastic processes involved in the system are assumed to be independent of each other. To avoid trivial cases, we suppose 0 < p < 1, 0 < a < 1, 0 < q < 1, 0 ≤ h ≤ 1. The corresponding transition rate diagram is shown in Figure 1. Figure 1. Various time epochs in an early arrival model 3. Markov Chain At time m+, the model can be described through the process {Ym = (Cm, z o,m, z 1,m, z 2,m, Nm), m = 0, 1, ...}, where Cm represents the state of the server; 0, 1 or 2 according to whether the server is free, busy or on vacation, respectively; Nm denotes the number of repeated customers in the orbit. If Cm = 0, then z o,m denotes the remaining retrial time. If Cm = 1, then z 1,m denotes the remaining service time of the customer currently under service and if Cm = 2, then z 2,m corresponds to the rest vacation time. It can be proved that {Ym, m  N} is a Markov chain with the state space {(0,0),(0,i,k):i ≥ 1,k ≥ 1;(1,i,k):i ≥ 1,k ≥ 0;(2,i,k):i ≥ 1,k ≥ 0}. In order to obtain the stationary distribution of the process, we define the stationary probabilities of the Markov chain {Ym, m  N} as follows: π 0,0=lim m→ ∞ P[Cm=0,Nm=0], π 0, i,k=lim m→ ∞ P[Cm=0, ζ 0,m=i,Nm=k],i≥1,k≥1, π 1, i,k=lim m→ ∞ P[Cm=1, ζ 1,m=i,Nm=k],i≥1,k≥0, π 2,i,k=lim m→ ∞ P[Cm=2, ζ 2,m=i,Nm=k],i≥1,k≥0, -1239- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1487 The Kolmogorov equations for the stationary distribution are given as follows: π 0,0=p( π 0,0+ θ ηπ 1,1,0+ π 2,1,0) (1) π 0,i,k=p( π 0,i+1,k+ θ η ai π 1,1,k−1+ θη ai π 1,1, k+ai π 2,1, k),i≥1,k≥1, (2) π 1,i,k= δ 0,kpsi π 0,0+(1− δ 0,k)∑ j=1 +∞ π 0, j,kpsi+psi π 0,1,k+1+(1− δ 0,k)p θ η si π 1,1, k−1 +(p θ +p θ a0) η si π 1,1,k+p θη a0si π 1,1,k+1+(1− δ 0,k)p aπ 1,i+1, k−1+p π 1,i+1, k +(1− δ 0,k)p a si∑ j=2 +∞ π 1, j,k−1+psi π 2,1, k+pa0si π 2,1,k+1,i≥1,k≥0, (3) π 2,i,k=p θ η vi π 1,1, k+(1− δ 0,k)p θη vi π 1,1,k−1+(1− δ 0,k)p θ η vi π 1,1,k−1 +(1− δ 0,k)(1− δ 1,k)p θ η vi π 1,1,k−2+p π 2,i+1,k+(1− δ 0,k)p π 2,i+1,k−1,i≥1,k≥0, (4) where d i,j is the Kronecker’s symbol, and the normalization condition is π 0,0+∑ i=1 +∞ ∑ k=1 +∞ π 0, i , k +∑ i=1 +∞ ∑ k=0 +∞ π 1,i , k +∑ i=1 +∞ ∑ k=0 +∞ π 2,i ,k =1. In order to solve (1)–(4), we introduce the following generating functions: Φ 0(x , z)=∑ i=1 +∞ ∑ k=1 +∞ π 0,i ,k xizk, Φ 1(x , z)=∑ i=1 +∞ ∑ k=0 +∞ π 1,i ,k xizk, Φ 2(x , z)=∑ i=1 +∞ ∑ k=0 +∞ π 2,i , k xizk, and the auxiliary generating functions: Φ 0,i(z)=∑ k=1 +∞ π 0,i , k zk, Φ 1,i(z)=∑ k=0 +∞ π 1,i , k zk, Φ 2,i(z)=∑ k=0 +∞ π 2,i , k zk,i≥1. The following lemma will be used during the derivation of the main result. Lemma 1: For 0 ≤ z < 1, if [ a pA(p) + q + aq – ah p b 2,1]S(p + p a ) - (p + p a ) > 0, we have W(z) > 0, where W(z) = S( t (z)){ h [z + (1 - z)pA(p)](1 – a z)( q + q z)V(p + pz) – ah z2 + (1 - z) h [pA(p)(1 – a z)( q + q z) + ( q + aq z)z]} - z(1 – z) t (z), t (z) = p + a pz. Proof: Let us define the following functions f(z) = S( t (z)){ h [z + (1 - z)pA(p)](1 – a z)( q + q z)V(p + pz) – ah z2 + (1 - z) h [pA(p)(1 – a z)( q + q z) + ( q + aq z)z]}, g(z) = z(1 – z) t (z). -1240- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1487 In order to study the slope of the tangent of f(z) and g(z) we calculate: f ' (1) = - [ a p A (p) + q + aq - ah p b 2,1]S(p + p a ), g' (1) = - (p + p a ). Due to the fact that f(z) and g(z) are convex functions, we observe that if [ a p A (p) + q + aq - ah p b 2,1]S(p + p a ) - (p + p a ) > 0, i.e. f ' (1) < g ' (1), then we have f(z) > g(z) in 0 ≤ z < 1. Lemma 2: For 0 ≤ z < 1, if [ a p A (p) + q + aq - ah p b 2,1]S(p + p a ) - (p + p a ) > 0, the following limits exist lim z→1 (1−z) τ (z)−S( τ (z)) { (1−z) η ( θ + αθ z)+ η [(1− α z)( θ + θ z)V(p+pz)− α z] } Ω(z) =( θ + α θ − αη p β 2,1)S(p+p α )−(p+p α ) [ α p A(p)+ θ + αθ − α η p β 1,1]S(p+p α )−(p+p α ), lim z→1 (1−z)(1− α z) Ω(z)= α [ α p A(p)+ θ + α θ − αη p β 2,1]S(p+p α )−(p+p α ). The following theorem gives an explicit expression for the generating function of the stationary distribution of the system state. Theorem 1: If [ a p A (p) + q + aq - ah p b 2,1]S(p + p a ) - (p + p a ) > 0, then Φ 0(x,z)=[A(x)−A(p)] pxz π 0,0 x−p .(1−z) τ (z)−S( τ (z)) { (1−z) η ( θ + aθ z)+ η [(1− a z)( θ + θ z)V(p+pz)− a z] } Ω(z), Φ 1(x,z)= S(x)−S( τ (z)) x− τ (z).(1−z)(1− α z)px τ (z)A(p) π 0,0 Ω(z), Φ 2(x,z)=V(x)−V(p+pz) x−(p+pz).(1−z)(1− α z)(p+pz)( θ + θ z) η pxA(p)S( τ (z)) π 0,0 Ω(z), where π 0,0=[ α p A(p)+ θ + α θ − αη p β 2,1]S(p+p α )−(p+p α ) αθ A(p)S(p+p α ). -1241- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1487 Proof: Multiplying (2)–(4) by zk and summing over k and using the boundary condition (1), these equations become Φ 0,i(z)=p[ Φ 0,i+1(z)+( θ + θ z) η ai Φ 1,1(z)+ai Φ 2,1(z)]−pai π 0,0,i≥1, (5) Φ 1,i(z)= p zsi Φ 0,1(z)+[(pa0+pz)( θ + θ z) η z−p α z]si Φ 1,1(z)+(p+p α z) Φ 1,i+1(z) +psi Φ 0(1,z)+p α siz Φ 1(1,z)+(p+p a0 z)si Φ 2,1(z)+ z−a0 zpsi π 0,0 ,i≥1, (6) Φ 2,i(z)=(p+pz)[ η vi( θ + θ z) Φ 1,1(z)+ Φ 2,i+1(z)],i≥1 (7) Multiplying equations (5), (6) by xi and summing over i, we get (1−p x) Φ 0(x,z)=(A(x)−a0)[ p η ( θ + θ z) Φ 1,1(z)+p Φ 2,1(z)−p π 0,0]−p Φ 0,1(z), (8) (1− τ (z) x) Φ 1(x, z)=[ η (pa0+pz)( θ + θ z)S(x) z− α pzS(x)− τ (z)] Φ 1,1(z)+(z−a0)pS(x) z π 0,0 +pS(x) Φ 0(1, z)+ pS(x) z Φ 0,1(z)+ α pzS(x) Φ 0(1,z) Φ 1(1, z)+(p+p a0 z)S(x) Φ 2,1(z), (9) (1−p+pz x) Φ 2(x ,z)=(p+pz)[ η V(x)( θ + θ z) Φ 1,1(z)− Φ 2,1(z)]. (10) Choosing x = 1 in (8) and (9), we obtain p Φ 0(1,z)=(1−a0)[p η ( θ + θ z) Φ 1,1(z)+p Φ 2,1(z)−p π 0,0]−p Φ 0,1(z), (11) pz(1−z) Φ 1(1,z)=p(1−z) Φ 0,1(z)+ { η [z+pa0(1−z)]( θ + θ z)−(p+pz)z } Φ 1,1(z) +[z+pa0(1−z)] Φ 2,1(z)−p a0(1−z) π 0,0 . (12) Substituting above equations(11) and (12) into Equation (9), we get (1− τ (z) x) Φ 1(x ,z)=(1− a z)S(x) z[p Φ 0,1 (z)−pa0 π 0,0] + η S(x)[[z+pa0(1−z)]( θ + θ z) z+ a (pa0( θ + θ z)− θ z)]− aη zS (x) 1−z− τ (z) Φ 1,1(z) +(1− a z)S(x)( 1 1−z+pa0 z) Φ 2,1(z). (13) -1242- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1487 Setting x = p in (8), x = t (z) in (13) and x = p + pz in (10), we obtain p[A(p)−a0] π 0,0=−p Φ 0,1(z)+[ A(p)−a0][ p η ( θ + θ z) Φ 1,1(z)+p Φ 2,1 (z)], (14) (1− a z)S( τ (z)) zpa0 π 0,0=(1− a z)S( τ (z)) zp Φ 0,1(z) + η S( τ (z))[[z+pa0(1−z)]( θ + θ z) z+ a (p a0( θ + θ z)− θ z)]− aη zS ( τ (z)) 1−z− τ (z) Φ 1,1(z) +(1− a z)S( τ (z))( 1 1−z+pa0 z) Φ 2,1(z). (15) Φ 2,1(z)= η V(p+pz)( θ + θ z) Φ 1,1(z). (16) Therefore, from above equations (14)-(16), we find the auxiliary generating functions F 0,1(z), F 1,1(z) and F 2,1(z) as follows: Φ 0,1(z)=pz[A(p)−a0] π 0,0 p .(1−z) τ (z)−S( τ (z)) { (1−z) η ( θ + aθ z)+ η [(1− a z)( θ + θ z)V(p+pz)− a z] } Ω(z) (17) Φ 1,1(z)= pA(p)(1−z)(1− a z)S( τ (z)) π 0,0 Ω(z), (18) Φ 2,1(z)= pA(p)(1−z)(1− a z)S( τ (z))V(p+pz)( θ + θ z) π 0,0 Ω(z). (19) Using Lemmas 1 and 2, the auxiliary generating functions F 0,1(z), F 1,1(z) and F 2,1(z) are well d e f i n e d f o r z  [ 0 , 1 ) a n d c a n b e e x t e n d e d b y c o n t i n u i t y f o r z = 1 i f [ a p A(p)+ θ + aθ − aη p β 2,1]S(p+p a )−(p+p a )0. Substituting (17)–(19) into (8), (10) and (13), we get the generating functions F 0(x,z), F 1(x,z) and F 2(x,z), and in Theorem 1. From the relationship p 0,0 + F 0 (1,1) + F 1 (1,1) + F 2 (1,1) = 1 we can find the unknown constant p 0,0. Some marginal generating functions of the number of customers in different conditions are summarized in the following corollary 1. -1243- Journal of Industrial Engineering and Management – http://dx.doi.org/10.3926/jiem.1487 Wang, J. (2012). Discrete-time Geo/G/1 retrial queues with general retrial time and Bernoulli v a c a t i o n . Jo ur na l of S ys te ms Sci e n ce a nd C om pl ex i ty, 2 5( 3 ), 50 4 -5 1 3. http://dx.doi.org/10.1007/s11424-012-0254-7 Wei, C.M., Qin, Y.Y., & He, L.X. (2014). A Discrete-Time Geo/G/1 Retrial Queue with Preemptive Resume, Bernoulli Feedback and General Retrial Times. Fuzzy Information & Engineering and Operations Research & Management, 211, 539-550. http://dx.doi.org/10.1007/978-3-642-38667- 1_53 Wenhui, Z. (2005). Analysis of a single-server retrial queue with FCFS orbit and Bernoulli vacation. Applied Mathematics and Computation, 161(2), 353-364. http://doi:10.1016/j.amc.2003.12.032 Wu, J., Liu, Z., & Peng, Y. (2011). A discrete-time Geo/G/1 retrial queue with preemptive resume and collisions. Applied Mathematical Modelling, 35(2), 837-847. http://dx.doi.org/10.1016/j.apm.2010.07.039 Zhang, Z.G., & Tian, N. (2001). Discrete time Geo/G/1 queue with multiple adaptive vacations. Queueing Systems, 38(4), 419-429. http://dx.doi.org/ 10.1023/A:1010947911863 Journal of Industrial Engineering and Management, 2015 (www.jiem.org) Article's contents are provided on an Attribution-Non Commercial 3.0 Creative commons license. Readers are allowed to copy, distribute and communicate article's contents, provided the author's and Journal of Industrial Engineering and Management's names are included. It must not be used for commercial purposes. To see the complete license contents, please visit http://creativecommons.org/licenses/by-nc/3.0/. -1250-