# Analysis of a Constant Retrial Queue with Joining Strategy and Impatient Retrial Customers.

1. IntroductionRetrial queueing systems have been extensively used to stochastically model many problems arising in computer networks, telecommunication, telephone systems, and daily life. About comprehensive surveys on retrial queues, readers are referred to the book of Falin and Templeton [1], the book of Artalejo and Gomez-Corral [2], the references listed in Artalejo [3,4], and the papers of [5,6] and references therein. In the majority of the above-mentioned, the interest of the investigators lies in the transient and/or the stationary distribution of the process of interest.

Recently, Economou and Kanta [7] considered a single-server M/M/1 retrial queue with constant retrial policy from an economic analysis viewpoint, in which customers are permitted to freely make decisions to maximize their own benefit based on some reward-cost structure. Such system can be analyzed by using the game theoretic analysis, and the fundamental consideration is to find the Nash equilibria; see Hassin and Haviv [8]. The pioneering work on the economic analysis of queueing systems can date back to Naor [9]. Naor [9] considered an M/M/1 queue with a simple linear reward-cost structure, where each customer observes the queue length before his decision. Later, Edelson and Hildebrand [10] investigated Naor's model by assuming that there is no information on the queue length for an arriving customer. Moreover, several researchers have studied the same problem for various queueing systems considering diverse characteristics, for example, retrials, breakdown and repairs, working vacations, priorities, reneging and jockeying, and schedules. The fundamental results in this area with extensive bibliographical references can be found in the comprehensive monograph by Hassin and Haviv [8]. Further studies can be referred to [917] and references therein.

In the present paper, we consider the Markovian single-server constant retrial queue with joining strategy and impatient retrial customers, which extends the model in Economou and Kanta [7] by considering the impatient phenomenon of the retrial customers. The customers observe the server state upon arrival and not the number of customers in the orbit and then decide whether to join the orbit or balk. We consider some performance indices, such as the stationary distribution and retrial numbers, and the (Nash) equilibrium balking strategies.

The rest of this paper is organized as follows. In Section 2, we give the model description and derive the stationary distribution and some performance measures and the distribution of the retrial numbers. In Section 3, we study the Nash equilibrium joining probability in unobservable case. Section 4 gives some numerical examples. Section 5 gives concluding remarks and possible related future research.

2. Model Formulation and Performance Analysis

We study here a retrial queue with constant retrial times, where customers arrive according to a Poisson process at rate A. Upon arrival, the arriving customer will immediately receive his service and leave the system after his service completion if he finds the server idle. Otherwise, if he finds the server busy, the arriving customer may enter the retrial orbit with some probability q (0 [less than or equal to] q [less than or equal to] 1) according to FCFS discipline or may leave the system with complementary probability [bar.q] = 1 - q (called balking customer). The service times are exponentially distributed with rate [mu]. Only the customer at the head of the retrial orbit is allowed to retry to access the server. Upon retrial, the customer begins the service if the server is idle; otherwise, he may rejoin the orbit with probability or leave the system 0 [less than or equal to] p [less than or equal to] 1 or leave the system (called impatient customer) with probability [bar.p] = 1 - p. The retrial times are assumed to follow exponential distribution with parameter 9. We assume that all random variables are mutually independent.

By assumption of the retrial queue, the state of the system under consideration can be described by a continuous Markov process X(t) = {(J(t), N(t)), t [greater than or equal to] 0} with state space S = {(j, k), j = 0,1; k [greater than or equal to] 0}, where J(t) is the state of the server at time t. J(t) = 0 or 1 according to the server is idle or busy; N(t) denotes the number of customers in the orbit at time t. Transition rate diagram of the Markov chain {(J(f), N(t)), t [greater than or equal to] 0} is depicted in Figure 1.

From Figure 1, we see that X(t) = {(J(t),N(t)), t [greater than or equal to] 0} is a continuous time quasi-birth-death process, and the infinitesimal generator Q of X(t) is given by

[mathematical expression not reproducible], (1)

where

[mathematical expression not reproducible] (2)

Let D = A + B + C; we obtain that

[mathematical expression not reproducible], (3)

and then D is obviously a generator matrix, and its associated stationary probability vector [pi] = ([[pi].sub.0], [[pi].sub.1]) can be derived as ([[pi].sub.0], [[pi].sub.1]) = ([mu]/([lambda] + [mu] + [theta]),([lambda] + [theta])/([lambda] + [mu] + [theta])). Now, from the Theorem 3.1.1 in Neuts [18] which states that the necessary and sufficient condition for stability of QBD process is [pi]Ce < [pi]Ae, where e is a 2 x 1 column vector of 1s, we can get that

[rho] = [[lambda].sub.q] ([lambda] + [theta])/[theta][[mu].sub.p] < 1 (4)

is the stationary condition for our retrial system, where [[mu].sub.p] = [mu] + ([lambda] + [theta])[bar.p]. Hereinafter, we assume that the inequality [rho] < 1 holds.

2.1. Stationary Distribution. Under the condition [rho] < 1, we aim to find the stationary distribution [P.sub.j,k] = [lim.sub.t[right arrow][infinity]] P(J(f) = j, N(t) = k), j = 0,1; k [greater than or equal to] 0. By our assumption of the model, we can get the steady-state equations as follows:

[mathematical expression not reproducible], (5)

From (5), we can obtain that

[mathematical expression not reproducible] (6)

where [[delta].sub.0,k] = 1 if k = 0 or [[delta].sub.0,k] = 0 if k [not equal to] 0.

Using the normalizing condition yields

[mathematical expression not reproducible]. (7)

Based on the above results, we discuss some performance measures in the following subsection.

2.2. Performance Measures

2.2.1. Queue Length and the Server State Probabilities. (1) Let [P.sub.0] and [P.sub.1] be the probabilities that the server is idle and busy, respectively; then

[mathematical expression not reproducible] (8)

(2) Let [N.sub.O] and [N.sub.s] be the mean numbers of customers in the retrial orbit and in the system, respectively; then

[mathematical expression not reproducible], (9)

[N.sub.S] = [N.sub.O] + [P.sub.1]. (10)

2.2.2. Waiting Time in the Orbit. In this subsection, we focus on the analysis of the mean waiting time in the orbit of a tagged customer, denoted by [W.sub.O]. Let [[tau].sub.j,k] be the waiting time in the orbit of the tagged customer in the k-th position given that the server is currently at state j, and T(j,k) = E([[tau].sub.j,k]). Then we have the following theorem.

Theorem 1. W0 and T(j, k) satisfy the following equations:

[mathematical expression not reproducible], (11)

[mathematical expression not reproducible], (12)

[mathematical expression not reproducible], ... (13)

Proof. For T(1, k), we remark that the arriving customer who finds the server busy after the tagged customer has no effect on T(1, k), but the service time and the impatience of the customer at the head of the orbit do affect the value of T(1, k). However, T(0, k) depends on arrival rate, because the new arrival who finds the server idle immediately receives his service. We obtain that

[mathematical expression not reproducible], (14)

[mathematical expression not reproducible], ... (15)

[mathematical expression not reproducible], (16)

[mathematical expression not reproducible], ... (17)

It follows from (14) and (16) that (12) and (13) hold for k = 1. Equation (15) indicates that

[mathematical expression not reproducible], ... (18)

Inserting (17) into (18) leads to

[mathematical expression not reproducible], ... (19)

Then we obtain (12) that holds for k [greater than or equal to] 2. Substituting (12) into (17), we obtain that

[mathematical expression not reproducible]. (20)

Then by PASTA property, we have

[mathematical expression not reproducible], (21)

This ends the proof of Theorem 1.

Using (4) and comparing (11) with (9), we find that

[mathematical expression not reproducible], (22)

which shows that Little's law holds for our retrial queue with impatient customers.

Remark 2. To interpret (14)-(17), we take (15) as an example. Let B be the length of the service time and 0 be length of the retrial time. For T(1,k), k [greater than or equal to] 2, by comparing the length of the service time of the customer being served and the retrial time of the customer at the head of the orbit and using memoryless property of exponential distribution, we have

[mathematical expression not reproducible]. (23)

2.2.3. Number of Retrials. Define R as the number of repeated attempts made by a tagged customer before he departs the system, either with his service completion or without getting his service because of his impatience. Obviously, when, upon arrival, the tagged customer finds the server idle or the server busy but the customer chooses to leave the system, then R = 0. So we mainly focus on the case that the server is busy when the tagged customer arrives and enters the orbit. In this case R is obviously independent of the customer's position in the orbit. Without loss of generality, suppose that the tagged customer is in the 1st position in the orbit. We define the following:

(i) [R.sub.s](j,k): the conditional probability that the tagged customer makes a total of k retrials, where the last one finds the server idle, and the rest k -1 unsuccessful retrials are made and the customer enters the orbit, given that the server is at state j currently.

(ii) [R.sub.v](j,k): the conditional probability that the tagged customer makes a total of k retrials, where the last one finds the server busy and chooses to leave the system, and the rest k -1 vain retrials are made and the customer enters the orbit, given that the server is at state j currently.

(iii) [P.sub.s]: the probability that the tagged customer in the orbit successfully accepts his service.

(iv) [P.sub.v]: the probability that the tagged customer in the orbit leaves the system without getting his service because of his impatience.

Then [P.sub.s] = [[summation].sup.[infinity].sub.k=1] [R.sub.s](1, k) and [P.sub.v] = [[summation].sup.[infinity].sub.k=1] [R.sub.v](1, k). To find the expressions of E(R), [P.sub.s], and [P.sub.v], we need to give the expressions of [R.sub.s](j, k) and [R.sub.v](j, k), k [greater than or equal to] 1. Following the similar analysis as Section 2.2.2, we have

[mathematical expression not reproducible], ... (24)

Solving (24) yields

[mathematical expression not reproducible], ... (25)

and so, we obtain the distribution of R as follows:

[mathematical expression not reproducible], ... (26)

which leads to

[mathematical expression not reproducible]. (27)

From (25), [P.sub.s] and [P.sub.v] can be expressed as

[mathematical expression not reproducible]. (28)

Remark 3. (1) Define [W.sub.s] as the mean sojourn time in the system of a tagged customer and then by the PASTA property, (10) and (12), we have

[mathematical expression not reproducible], (29)

which indicates that Little's law holds.

(2) Let E[WS | J = 1] be the conditional sojourn time in the system of a tagged customer given that he finds the server busy upon his arrival and decided to enter the retrial orbit. Then

[mathematical expression not reproducible] (30)

3. Analysis of Nash Equilibrium Joining Strategy-Unobservable Case

In this section, we aim to analyze the Nash equilibrium joining strategy under a given reward-cost structure, which is given in the following, because customers have the right to decide whether to enter the orbit or not depending on the server's state, not on the number of customers in the orbit, which is called unobservable case.

The reward-cost structure considered in this paper is as follows: (i)

(i) [R.sub.s]: each customer receiving a reward of [R.sub.s] units for completing service.

(ii) [R.sub.v]: each customer receiving a reward of [R.sub.v] units in case that he is forced to leave the system due to a retrial failure.

(iii) C: a waiting cost of C units per time unit where a customer remains in the system.

Assume that all customers follow a given joining strategy q and [lambda]([lambda] + d)/[theta][[mu].sub.p] < 1, which implies that the retrial queueing system in this paper is also stable because of [rho] < 1 holding for the joining strategy q. Customers are assumed to be risk neutral and maximize their expected net benefit and

[R.sub.s]/C > 1/[mu] (31)

which ensures that the customer who finds the server idle will join the system because of the positive benefit [R.sub.s] - C/[mu].

First we introduce some notations about Nash equilibrium (see [8,11] for details).

Assume that all customers are indistinguishable; we can consider the situation as a symmetric game among them. Denote the common set of strategies and the payoff function of a symmetric game by S and F, respectively. More concretely, let E([s.sub.tagged], [s.sub.others]) be the payoff of a tagged customer who adopts strategy stagged when all other customers select sothers. Strategy [s.sub.e] is a (symmetric) Nash equilibrium, if and only if F([s.sub.e], [s.sub.e]) [greater than or equal to] F(s, [s.sub.e]), [for all]s [member of] S. The intuitive interpretation of a Nash equilibrium is that an equilibrium strategy is the best response against itself, so that if all customers agree to follow it, no one can benefit by deviating from it. Strategy s, is said to dominate strategy [s.sub.2] if F([s.sub.1], s) [greater than or equal to] F([s.sub.2], s), for every s [member of] S and for at least one s the inequality is strict. Strategy is said to be dominant if it dominates all other strategies in S. We should remark that the notion of a dominant strategy is stronger than the notion of a Nash equilibrium.

For a tagged customer who finds the server busy and decides to join the orbit, under the given reward-cost structure, he will receive a reward [R.sub.s] with probability [P.sub.s] and a reward [R.sub.s] with probability PV, and he will be charged total cost CE[WS | J =1]. Then from (28) and (30), his net benefit is given by

[mathematical expression not reproducible]. (32)

Then the expected net benefit of a tagged customer that enters the orbit with probability q given that the system is found busy, when everyone else follows a strategy q, is given by

[s.sub.un] (q', q) = q' [s.sub.un] (1, q). (33)

In the following theorem, we aim to present the Nash equilibrium joining strategy.

Theorem 4. In the unobservable retrial queue with constant retrial times and impatient, assume that [lambda]([lambda] + d)/[theta][[mu].sub.p] < 1 and [R.sub.s]/C > 1/[mu] hold; a unique mixed Nash equilibrium joining strategy exists: enter the retrial orbit with probability [q.sub.e] whenever finding the server busy. [q.sub.e] is given by

[mathematical expression not reproducible], (34)

where

[mathematical expression not reproducible] (35)

Proof. From (32), we can see that the function [S.sub.un](1,q) is strictly decreasing on the interval (0,1). Then the unique maximum of [S.sub.un](1, q) is

[mathematical expression not reproducible], (36)

and the unique minimum is

[mathematical expression not reproducible]. (37)

Therefore, we consider the following three cases.

(i) If 1/[mu] + (([lambda] + [theta][bar.p]/[mu])([R.sub.v]/C) < [R.sub.s]/C + (([lambda] + [theta])[bar.p]/[mu])([R.sub.v]/C) [less than or equal to] ([lambda] + [theta] + [mu])/[theta][mu] + 1/[mu], that is, [S.sub.un](1, 0) [less than or equal to] 0, which leads to [S.sub.un](1, q) [less than or equal to] 0 for any q [member of] [0,1], the best response of the tagged customer who finds the server busy is balking, and the unique equilibrium joining probability is [q.sub.e] = 0.

(ii) If ([lambda] + [theta] + [mu])/[theta][mu]+1/[mu] < [R.sub.s]/C + (([lambda]+[theta])[bar.p]/[mu])([R.sub.v]/C) < [[mu].sub.p]([lambda] + [theta] + [mu])/[mu]([theta][[mu].sub.p] - [lambda]([lambda] + [theta])) + 1/p, then [S.sub.un](1,q) = 0 has a unique solution in (0,1), which is given by [q.sup.*.sub.e], which leads to [S.sub.un](1, q) > 0 for q < [q.sup.*.sub.e] and [S.sub.un](1, [q.sup.*.sub.e]) = 0 and [S.sub.un](1, q) < 0 for q > [q.sup.*.sub.e]. So the best response is [q.sup.*.sub.e]. As a result, the joining strategy with probability [q.sup.*.sub.e] is the unique equilibrium strategy.

(iii) If [R.sub.s]/C + (([lambda]+[theta])[bar.p]/[mu])([R.sub.v]/C) [greater than or equal to] [[mu].sub.p]([lambda]+[theta] + [mu])/[mu]([theta][[mu].sub.p] - [lambda]([lambda] + [theta])) + 1/[mu], that is, [S.sub.un](1, 1) [greater than or equal to] 0, then the net benefit given by (32) is always positive for [R.sub.S]/C+(([lambda]+ [theta])[bar.p]/[mu])(Rv/C) > [[mu].sub.p]([lambda] + [theta] + [mu])/[mu]([theta][[mu].sub.p] - [lambda]([lambda] + [theta])) + 1/[mu]; that is, the best response for the tagged customer who finds the server busy is joining the retrial orbit; that is, [P.sub.q] = 1

4. Numerical Illustration

To illustrate the effect of some parameters on the equilibrium joining probability [q.sub.e], we give some numerical examples.

In Figures 2 and 3, we present the influence of [R.sub.v] and [R.sub.s] on [q.sub.e] for model with ([lambda], [theta], [mu], p, [R.sub.s], C) = (2, 3,4,0.5,2,3) and ([lambda], [theta], [mu], [R.sub.v], C) = (2.5,3, 3.5, 0.5,2.25,2.5), respectively. Figures 2 and 3 show that the equilibrium joining probability [q.sub.e] is increasing as rewards [R.sub.v] and [R.sub.s] increase. The reason is that the higher the reward that the customers receive, the greater the willingness that customers take to enter the orbit.

In Figures 4 and 5, we present the curves of [q.sub.e] versus [mu] and [theta] for models with ([lambda], [theta], [mu], [R.sub.s], [R.sub.v], C) = (2.5, 3.5, 0.5, 4, 2.25, 2.5) and ([lambda], [mu], p, [R.sub.s], [R.sub.v], C) = (2, 0.25, 0.25, 3, 1, 2.5), respectively. Customers can get more profit as the service rates [mu] and [theta] increase, because the mean sojourn time decreases with [mu] and [theta] increasing and then customers prefer to enter the orbit, so [q.sub.e] is increasing as [mu] and [theta] increase.

In Figures 6 and 7, we examine the effect of [lambda] and p on [q.sub.e] for models with ([theta], [mu], p, [R.sub.s], [R.sub.v], C) = (2, 2, 0.5, 4, 2.25, 2.5) and ([lambda], [mu], [R.sub.s], [R.sub.v], C) = (0.5, 2, 3, 3, 0.75, 2.5), respectively. Figures 6 and 7 indicate that [q.sub.e] increases with the values of [lambda] and p increasing. The reason is that the larger the values of [lambda] and p are, the longer the customers sojourn in the system, and then the less profit the customers can get, which leads to customers being less willing to enter the orbit.

5. Conclusions

This paper has first presented the performance analysis of an M/M/1 retrial queue with impatient customers. Second, adopting a linear reward-cost structure, we have provided customer Nash equilibrium strategies from an economic viewpoint. However, we considered two different types of reward: one is the reward received by the customer who leaves the system after his service completion; the other is the reward received by the customer who is forced to leave the system due to a retrial failure. As an extension of this study, one can generalize the queue to the case that the server may take Bernoulli vacation. For this generalized model, one could study the observable and unobservable cases.

Competing Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

https://doi.org/10.1155/2017/9618215

Acknowledgments

This work is supported by the Natural Science Foundation of Anhui Higher Education Institutions of China under Grant nos. KJ2017A340 and KJ2016A875, the National Natural Science Foundation of China under Grant nos. 61672006 and 11301306, and the Natural Science Foundation of Shandong Province under Grant no. ZR2014AM021.

References

[1] G. I. Falin and J. G. C. Templeton, Retrial Queues, Chapman and Hall, London, UK, 1997

[2] J. R. Artalejo and A. Gomez-Corral, Retrial Queueing Systems, Springer, Berlin, Germany, 2008.

[3] J. R. Artalejo, "A classified bibliography of research on retrial queues: progress in 1990-1999" Top, vol. 7, no. 2, pp. 187-211, 1999.

[4] J. R. Artalejo, "Accessible bibliography on retrial queues: progress in 2000-2009" Mathematical and Computer Modelling, vol. 51, no. 9-10, pp. 1071-1081, 2010.

[5] G. Choudhury and J.-C. Ke, "An unreliable retrial queue with delaying repair and general retrial times under Bernoulli vacation schedule" Applied Mathematics and Computation, vol. 230, pp. 436-450, 2014.

[6] S. Gao and J. Wang, "Performance and reliability analysis of an M/G/1-G retrial queue with orbital search and non-persistent customers" European Journal of Operational Research, vol. 236, no. 2, pp. 561-572, 2014.

[7] A. Economou and S. Kanta, "Equilibrium customer strategies and social-profit maximization in the single-server constant retrial queue" Naval Research Logistics, vol. 58, no. 2, pp. 107-122, 2011.

[8] R. Hassin and M. Haviv, To Queue or Not to Queue: Equilibrium Behavior in Queueing Systems, Kluwer Academic, Boston, Mass, USA, 2003.

[9] P. Naor, "The regulation of queue size by levying tolls" Econometrica, vol. 37, no. 1, pp. 15-24, 1969.

[10] N. M. Edelson and K. Hildebrand, "Congestion tolls for poisson queuing processes," Econometrica, vol. 43, no. 1, pp. 81-92, 1975.

[11] O. Boudali and A. Economou, "Optimal and equilibrium balking strategies in the single server Markovian queue with catastrophes" European Journal of Operational Research, vol. 218, no. 3, pp. 708-715, 2012.

[12] P. Chen and Y. Zhou, "Equilibrium balking strategies in the single server queue with setup times and breakdowns," Operational Research, vol. 15, no. 2, pp. 213-231, 2015.

[13] A. Economou and S. Kanta, "Optimal balking strategies and pricing for the single server Markovian queue with compartmented waiting space" Queueing Systems, vol. 59, no. 3-4, pp. 237-269, 2008.

[14] A. Economou and S. Kanta, "Equilibrium balking strategies in the observable single-server queue with breakdowns and repairs" Operations Research Letters, vol. 36, no. 6, pp. 696-699, 2008.

[15] P. Guo and R. Hassin, "Strategic behavior and social optimization in Markovian vacation queues: the case of heterogeneous customers" European Journal of Operational Research, vol. 222, no. 2, pp. 278-286, 2012.

[16] J. Wang and F. Zhang, "Equilibrium analysis of the observable queues with balking and delayed repairs," Applied Mathematics and Computation, vol. 218, no. 6, pp. 2716-2729, 2011.

[17] J. Wang and F. Zhang, "Strategic joining in M/M/1 retrial queues," European Journal of Operational Research, vol. 230, no. 1, pp. 76-87, 2013.

[18] M. F. Neuts, Matrix Geometric Solutions in Stochastic Models--An Algorithmic Approach, John Hopkins University Press, Baltimore, Md, USA, 1981.

Shan Gao, (1,2) Xiangyang Niu, (1) and Tao Li (3)

(1) School of Mathematics and Statistics, Fuyang Normal College, Fuyang Anhui 236037, China

(2) Regional Logistics Planning and Modern Logistics Engineering Key Laboratory of Anhui Province, Fuyang, Anhui 236037, China

(3) School of Science, Shandong University of Technology, Zibo 255049, China

Correspondence should be addressed to Shan Gao; sgao_09@yeah.net

Received 4 August 2016; Revised 14 November 2016; Accepted 27 November 2016; Published 26 March 2017

Academic Editor: Vladimir Turetsky

Caption: FIGURE 1: Transition rate diagram of X(t) = {(J(t), N(t)), t [greater than or equal to] 0}.

Caption: FIGURE 2: [q.sub.e] versus [R.sub.v] for [lambda] = 2, [theta] = 3, [mu] = 4, p = 0.5, [R.sub.s] = 2, and C = 3.

Caption: FIGURE 3: [q.sub.e] versus [R.sub.s] for [lambda] = 2.5, [theta] = 3.5, [mu] = 3.5, p = 0.5, [R.sub.v] = 2.25, and C = 2.5.

Caption: FIGURE 4: [q.sub.e] versus [mu] for [lambda] = 2.5,0 = 3.5, p = 0.5, [R.sub.s] = 4, [R.sub.v] = 2.25, and C = 2.5.

Caption: FIGURE 5: [q.sub.e] versus [theta] for [lambda] = 2, [mu] = 0.25, p = 0.25, [R.sub.s] = 3, [R.sub.v] = 1, and C = 2.5.

Caption: FIGURE 6: versus [lambda] for [theta] = 2, [mu] = 2, p = 0.5, [R.sub.s] = 4, [R.sub.v] = 2.25, and C = 2.5.

Caption: FIGURE 7: [q.sub.e] versus p for [lambda] = 0.5, 0 = 2, [mu] = 3, [R.sub.s] = 3, [R.sub.v] = 0.75, and C = 2.5.

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Gao, Shan; Niu, Xiangyang; Li, Tao |

Publication: | Mathematical Problems in Engineering |

Article Type: | Report |

Date: | Jan 1, 2017 |

Words: | 4293 |

Previous Article: | Level-of-Service Based Hierarchical Feedback Control Method of Network-Wide Pedestrian Flow. |

Next Article: | Modelling of the First-Order Time-Varying Filters with Periodically Variable Coefficients. |

Topics: |