Equilibrium Customer Strategies in the Geo/Geo/1 Queue with Single Working Vacation

Abstract

This paper is concerned with the equilibrium balking strategies of customers in a Geo/Geo/1 queue with single working vacation. Instead of completely stopping service, the server works with a small probability during the working vacation period. As soon as no customers exist in the system, the server takes a single vacation. The customers decide for themselves whether to enter the system or balk based on a natural reward-cost structure, the information available about the status of the server, and the queue length on hand upon arrival. We obtain the equilibrium balking strategies in two cases: fully observable and fully unobservable cases, which depend on whether the customers know both the queue length and the state of the server or none of them. Finally, we present several numerical experiments that demonstrate the effect of some parameters on the equilibrium behavior.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Academic Editor:Leonid Shaikhet

Department of Mathematics, Beijing Jiaotong University, Beijing 100044, China

Received 10 October 2013; Revised 8 January 2014; Accepted 28 January 2014; 23 March 2014

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.

1. Introduction

In recent years, considerable efforts have been devoted to the study of the economic analysis of queueing systems taking customers' behavior into account. It has wide applications for management in service system and electronic commerce. In these studies, customers are allowed to make their decisions based on some reward-cost structures and the information available about the system upon arrival. Usually the level of information is divided into the observable case and the unobservable case regarding whether the information of the queue length is available to customers or not upon their arrival.

The pioneering work goes back to Naor [1], who studied equilibrium and social optimal strategies with a simple linear reward-cost structure in an M/M/1 observable queueing system. Later on, Edelson and Hildebrand [2] considered the same queueing system with the assumptions that the customers make their decisions without being informed about the state of the system, that is, the unobservable case. Since then, there are a growing number of papers that deal with the economic analysis of the balking behavior of customers in various queueing systems. The interested readers are referred to the monograph of Hassin and Haviv [3] which summarizes the main approaches and several results in the broader area of the economic analysis of various queueing systems.

During the last decade, there has been an emerging interest in the study of the equilibrium analysis of the customers' actions in queueing systems with vacations. Detailed surveys about classical vacation queueing systems are contained in the monographs of Takagi [4, 5] and Tian and Zhang [6], among others. Regarding the strategic behavior of customers in classical vacation queueing models, the first study was the M/M/1 vacation queueing models in a single server by Burnetas and Economou [7]. Economou et al. [8] studied equilibrium and social optimization in the M/G/1 queue with generally distributed vacation times under two different information assumptions of unobservable and partially observable cases. Guo and Hassin [9, 10] considered the equilibrium customer behavior and social optimization in observable and unobservable queues with Markovian vacations and N-policy, respectively. Sun and Li [11] and Zhang et al. [12] both studied the single-server Markovian queues with multiple working vacations in which customers maximize their benefit, and they derived the customers' equilibrium and social optimal behavior under different levels of the system information.

Different from the classical vacation queueing models, Servi and Finn [13] introduced a half-vacation policy called working vacation (WV) in which the server serves customers at a low rate rather than to stop working during the vacation time. They studied the M/M/1/WV system and obtained the total numbers and expected mean sojourn time of the customers in the queue. Wu and Takagi [14] generalized the study of the model to an M/G/1 queue with working vacation. Baba [15] discussed a GI/M/1 queue with multiple working vacations. However, their discrete time counterparts received very little attention.

The analysis of discrete time queueing models has received considerable attention in view of their application in practical problems that arise from communication and computer systems including time-division multiple access (TDMA) schemes [16], asynchronous transfer mode (ATM) multiplexers in the broadband integrated services digital network (B-ISDN) [17], and slotted carrier-sense multiple access (CSMA) protocols. Our study is motivated by some practical systems in networks. For the network server located at computer center providing file transfer service, the packets transmitted through the network can be seen as the customers who receive the service from the server. To keep the server functioning well, virus scan is an important maintenance activity for the server. It can be performed when the server is idle. The server will provide his service with lower processing speed during the period of virus scan because the operation of virus scan would consume some system resources and reduce the processing speed. When virus scan is done the server will enter the idle state again and wait for the packets to arrive. Recently, Liu et al. [18] studied the equilibrium threshold strategies in observable queues under single vacation policy under discrete time. Ma et al. [19] studied the equilibrium behavior of customers in the Geo/Geo/1 queueing system under multiple vacation policy. Li and Tian [20] analyzed the Geo/Geo/1 queue with single working vacation. Literature reveals that there was no work concerning the equilibrium balking behavior in the discrete time queues with working vacations.

In this paper, we study the equilibrium balking strategies in the discrete time Geo/Geo/1 queue with single working vacation. Based on a natural linear reward-cost structure, we explore two cases with regard to the level of information available to customers upon arrival: fully observable and fully unobservable cases. The equilibrium balking strategies in these two cases are investigated and the stationary system behavior is analyzed. A variety of performance measures are developed under the corresponding strategies and furthermore some numerical experiments are presented to illustrate the effect of various parameters on the equilibrium behavior.

This paper is organized as follows. In Section 2, we present the detailed description of the model and give the cost structure. The individual optimal threshold strategies for the fully observable case and mixed Nash equilibrium balking strategies for the fully unobservable case are derived. Section 3 illustrates the information level on the equilibrium behavior by analytical and numerical comparisons. Finally, in Section 4, we give some necessary conclusions.

2. Model Description

In this paper, we consider a single server queueing system in discrete time domain. The server works with the probability _{μ b} and it enters into a vacation period once there is no customer at the instant of a service completion. If customers arrive during the vacation time, the server works with a small probability of _{μ v} . All arriving customers are served according to arrival order. When a working vacation ends, if there are customers in the queue, the server switches service probability from _{μ v} to _{μ b} , and a regular busy period starts. Otherwise, the server enters the idle period and a new busy cycle starts when a customer arrives. The detailed assumptions of the model are given below. Throughout the paper, for any real number x ∈ [ 0,1 ] , we denote x - ...1; 1 - x .

(1) Potential customer arrives at the end of the slot t = ^{n -} , n = 0,1 , ... . Interarrival time T is an independent and identically distributed sequence and follows a geometric distribution. Consider [figure omitted; refer to PDF]

(2) Assume that the vacation time starts or ends at the slot point = n , n = 0,1 , ... . And it occurs before customers' arriving. The distribution of the regular service time _{S b} is [figure omitted; refer to PDF] The distribution of service time _{S v} in a working vacation period is [figure omitted; refer to PDF]

(3) The distribution of vacation time V is [figure omitted; refer to PDF]

We assume that inter-arrival times, service times, and single working vacation times are mutually independent. The queueing system follows the First-In-First-Out (FIFO) service discipline. We assume that the regular service probability exceeds the arrival probability so that the server can accommodate all arrivals.

Let _{L n} denote the number of the customers at time ^{n +} . According to this model as a late arrival system we can know that a customer who finishes service and leaves at ^{n +} does not reckon in _{L n} and a customer who arrives at ^{n -} should reckon in _{L n} . We define that [figure omitted; refer to PDF] It is readily seen that { _{L n} , _{J n} } is a Markov chain with state space ... = { ( k , j ) |" k ∈ { 0,1 , 2 , ... } , j = 0,1 } , where state ( k , 0 ) , k ...5; 0 , indicates that the system is in the working vacation period and there are k customers; state ( k , 1 ) , k ...5; 0 , indicates that the system is in the regular busy period and there are k customers in the system.

Traditionally, four cases should be distinguished depending on the information provided to customers before making decisions, which include the levels of information about the status of the server and the queue length of the system. More specifically, consider the following: (1) fully observable case: customers observe { _{L n} , _{J n} } ; (2) almost observable case: customers observe only _{L n} ; (3) almost unobservable case: customers can observe only _{J n} ; (4) fully unobservable case: customers do not observe the system state.

However, in the present paper our interest is to consider the behavior of customers when they can decide whether to join or to balk upon their arrival where they get the full information and no information, that is, two extreme situations. To model the decision process, we assume that every customer receives a reward of R units for completing service. It may reflect a customer's satisfaction and the added value of being served. Moreover, there exists a waiting cost of C units per time unit that the customer remains in the system (in queue and in service area). Customers are risk neutral and maximize their expected net benefit. Finally, it is assumed that the customers' decisions are irrevocable; retrials of balking customers and reneging of entering customers are not allowed.

2.1. Equilibrium Threshold Strategies for the Fully Observable Case

We first consider the observable queue. In this case, customers know the exact state of the system ( _{L n} , _{J n} ) upon arrival. It will be shown that there exist equilibrium strategies of threshold type.

Theorem 1.

In the fully observable Geo/Geo/1 queue with single working vacation, there exist thresholds [figure omitted; refer to PDF] such that the strategy "observe ( _{L n} , _{J n} ) , enter if _{L n} ...4; _{L e} ( _{J n} ) and balk otherwise" is a unique equilibrium in the class of the threshold strategies, where _{x 0} is the unique root of equation. Consider [figure omitted; refer to PDF]

Remark 2.

_{L e} ( 0 ) is the threshold when an arriving customer finds the system is in a vacation and _{L e} ( 1 ) is the threshold when it is in a regular busy period. We get _{L e} ( 0 ) and _{L e} ( 1 ) from the condition S ( n , i ) ...5; 0 when i = 0 and i = 1 , respectively. The symbol [left floor] [right floor] indicates rounding down.

Proof.

The stochastic process { _{L n} , _{J n} } is a discrete Markov chain with state space _{... f o} = { ( k , 0 ) |" 0 ...4; k ...4; _{L e} ( 0 ) + 1 } ... { ( k , 1 ) |" 0 ...4; k ...4; _{L e} ( 1 ) + 1 } . We show transition probability diagram in Figure 1. The one-step transition probabilities of { _{L n} , _{J n} } are given by the following (Figure 1).

Case 1 . If _{X n} = ( 0,0 ) , [figure omitted; refer to PDF]

Case 2 . If _{X n} = ( 1 , 0 ) , [figure omitted; refer to PDF]

Case 3 . If _{X n} = ( k , 0 ) , 2 ...4; k ...4; _{L e} ( 0 ) , [figure omitted; refer to PDF]

Case 4 . If _{X n} = ( _{L e} ( 0 ) + 1,0 ) , [figure omitted; refer to PDF]

Case 5 . If _{X n} = ( 0 , 1 ) , [figure omitted; refer to PDF]

Case 6 . If _{X n} = ( 1 , 1 ) , [figure omitted; refer to PDF]

Case 7 . If _{X n} = ( k , 1 ) , 2 ...4; k ...4; _{L e} ( 1 ) , [figure omitted; refer to PDF]

Case 8 . If _{X n} = ( _{L e} ( 1 ) + 1,1 ) , [figure omitted; refer to PDF]

Based on the cost structure imposed on the system, we can get an arriving customer's expected net benefit as follows: [figure omitted; refer to PDF] where T ( n , j ) = E [ S |" ^{N -} = n , ^{I -} = j ] is his expected mean sojourn time when he finds the system at state ( _{L n} , _{J n} ) upon his arrival.

From the transition probability diagram, we have the following system: [figure omitted; refer to PDF]

Note that T ( 0,1 ) denotes the mean sojourn time of a customer who gets service immediately and it is equal to 1 / _{μ b} . Let us consider the tagged customer who finds n customers in the queue with the server in a working vacation period. Then, he has to wait for a geometric distributed time with probability _{μ v} θ - + θ for the next event to occur, which is a completed service or the end of the vacation period of the server. With probability _{μ v} θ - / ( 1 - _{μ - v} θ - ) the service is completed, and the server chooses the first customer in the queue to serve, so the server becomes busy and the tagged customer moves to the position n - 1 . On the other hand, with probability θ _{μ v} / ( 1 - _{μ - v} θ - ) the vacation period of the server is completed and a customer in front of him is served at the same time, so the server is free and the tagged customer moves to the position n - 1 . With probability θ _{μ - v} / ( 1 - _{μ - v} θ - ) the vacation period of the server is completed and the tagged customer remains in the n th position. Hence, we deduce (20). With a similar argument, (18) and (19) are deduced.

Substituting (17) into (18) we can get [figure omitted; refer to PDF] From (17) and (19) we can get [figure omitted; refer to PDF] Substituting (22) into (20), using (21), we can get [figure omitted; refer to PDF] Then we get the expressions below: [figure omitted; refer to PDF]

We can obviously see that T ( n , 0 ) is strictly increasing for n from (23); there exists only one root of (7). A customer chooses to enter if the reward of being served exceeds the expected cost for waiting and he is indifferent between entering and balking if the two values are equal. By solving S ( n , i ) ...5; 0 for n , we get that the arriving customer prefers to enter if and only if n ...4; _{L e} ( i ) , i = 0,1 , where ( _{L e} ( 0 ) , _{L e} ( 1 ) ) is given in (6).

Figure 1: Transition probability diagram for the ( _{L e} ( 0 ) , _{L e} ( 1 ) ) threshold strategy.

[figure omitted; refer to PDF]

Remark 3.

We assume that R > C / _{μ b} throughout the paper because the reward of the service must exceed the expected cost for a customer who finds the system empty. This strategy is preferable, independently of what the other customers do; that is, it is a weakly dominant strategy. Otherwise no one will enter the queue when arriving.

2.2. Equilibrium Strategies for the Fully Unobservable Case

In this case the customers cannot observe the state of the system at all. A mixed strategy for a customer is specified by the probability q of entering, where q is the probability of joining the queue whenever the server is in a regular busy period, a vacation period, or an idle period. So the effective arrival probability equals p q . With the pure strategies, all of the customers either join the queue or all balk. The behavior of the customers under equilibrium condition is described as follows.

In this fully unobservable case, we show the transition probability diagram in Figure 2. Using the lexicographical sequences for the states, the transition probability matrix can be written as follows: [figure omitted; refer to PDF] Where [figure omitted; refer to PDF]

Figure 2: Transition probability diagram for the q mixed strategy.

[figure omitted; refer to PDF]

Lemma 4.

In the fully unobservable Geo/Geo/1 queue system with single working vacation, the expected mean sojourn time of a customer is [figure omitted; refer to PDF] where [figure omitted; refer to PDF] The expected sojourn time of a customer who decides to enter is strictly increasing for q ∈ [ 0,1 ] .

Proof.

By [20], we can easily obtain the expression of E ( W ) . We define [figure omitted; refer to PDF] and we rewrite E ( W ) as [figure omitted; refer to PDF] Then we, respectively, consider the monotonicity of _{g 1} ( q ) and _{g 2} ( q ) with respect to q . First we will prove that α is strictly increasing for q ∈ [ 0,1 ] . This is due to the fact that [figure omitted; refer to PDF] Then we prove that r is strictly increasing for q ∈ [ 0,1 ] . Let [figure omitted; refer to PDF] and then r = y ( q ) / 2 _{p - 0 μ - v} . By direct calculation, we know that [figure omitted; refer to PDF] So r is increasing for q ∈ [ 0,1 ] .

From (29) and (32), we can see that _{g 1} ( q ) is strictly increasing for q ∈ [ 0,1 ] . We can prove that _{g 2} ( q ) has the same property. Observe the formula [figure omitted; refer to PDF] where [figure omitted; refer to PDF] Equation (36) is decreasing for q ∈ [ 0,1 ] as r increases. We can write the equation θ r / θ - ( 1 - r ) = _{p 0 μ - v} - r _{p - 0 μ v} in [20] as [figure omitted; refer to PDF] and (38) is obviously increasing for q ∈ [ 0,1 ] . So (37) is increasing for q ∈ [ 0,1 ] . The proof is completed.

Theorem 5.

In the fully unobservable Geo/Geo/1 queue with single working vacation, with p < _{μ b} and _{μ v} < _{μ b} , a unique Nash equilibrium mixed strategy "enter with probability _{q e} " exists, where _{q e} is given by [figure omitted; refer to PDF] where [figure omitted; refer to PDF]

Proof.

We consider a tagged customer at his arrival instant. If he decides to enter, his expected net benefit is [figure omitted; refer to PDF] where [figure omitted; refer to PDF]

From Lemma 4, we know that B ( q ) is strictly decreasing for q ∈ [ 0,1 ] . So when R ∈ ( C / _{μ b} , C ^{E *} ( W ) ) there exists a unique solution of the equation S ( q ) = 0 which lies in the interval (0,1) and is denoted by ^{q e *} . When R ∈ [ C ^{E *} ( W ) , ∞ ) , S ( q ) is positive for every q , so the unique equilibrium point is _{q e} = 1 in this case. In other words, the tagged customer's best choice is 1 in this case.

Remark 6.

For the case p ...5; _{μ b} and _{μ v} < _{μ b} , the analog of Theorem 5 is that a unique Nash equilibrium mixed strategy "enter with probability _{q e} " exists, where [figure omitted; refer to PDF] for R > C / _{μ b} .

3. Numerical Examples

In this section we study the effect of the information on customers' behavior for the fully observable system and the fully unobservable system.

We first consider the fully observable model and explore the sensitivity of the equilibrium thresholds with regard to the arrival probability p , service reward R , vacation probability θ , regular service probability _{μ b} , and probability _{μ v} in working vacation. We can see Figures 3(a), 3(b), 3(c), 3(d), and 3(e). We observe that the thresholds remain fixed since the arrival probability p is irrelevant to the customer's decision when he sees full state information. Or we can explain that the tagged customer who ignores the behavior of customers behind him could only know whether the customers ahead enter the queue or not. So the arrival probability p does not impact the strategies of the customers when arriving. When R varies, the equilibrium thresholds increase as the service reward increases. Obviously, more people would enter the queue if rewarded more. But we can see that _{L e} ( 0 ) is more sensitive than _{L e} ( 1 ) . We can explain that the customers who can endure the long waiting are more ready to receive the service even if the server is at the low service probability. It shows obviously that _{L e} ( 1 ) remains fixed as vacation probability θ increases but _{L e} ( 0 ) is a monotonically increasing function. The reason is that when the server's vacation period gets shorter, customers generally have a greater incentive to enter the queue. When _{μ b} is small, it means that the regular service probability is slower than normal level. The server may work at a low speed when fewer customers exist in queue in order to economize operation cost. Finally, along with the increasing of the probability _{μ v} in working vacation, the threshold of _{L e} ( 0 ) increases. But it is irrelevant to the value of _{L e} ( 1 ) when the server is in a normal working state.

Equilibrium thresholds for the fully observable model. Sensitivity with respect to (a) p , for _{μ b} = 0.9 , _{μ v} = 0.1 , θ = 0.2 , C = 1 , R = 30 ; (b) R , for p = 0.4 , _{μ b} = 0.9 , _{μ v} = 0.1 , C = 1 , θ = 0.2 ; (c) θ , for p = 0.5 , _{μ b} = 0.9 , _{μ v} = 0.3 , C = 1 , R = 30 ; (d) _{μ b} , for p = 0.4 , θ = 0.2 , _{μ v} = 0.5 , C = 1 , R = 30 ; (e) _{μ v} , for p = 0.4 , θ = 0.2 , _{μ b} = 0.9 , C = 1 , R = 30 .

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) [figure omitted; refer to PDF]

(d) [figure omitted; refer to PDF]

(e) [figure omitted; refer to PDF]

Next we focus on exploring the sensitivity of the equilibrium entrance probability in the fully unobservable case. The results are presented in Figures 4(a) and 4(b). Evidently, along with the increase of the _{μ v} , that is, the service probability in the vacation period, the equilibrium entrance probability increases. We can see that if the value of _{μ v} is too small, it is not worth taking service in vacation period. When the probability θ increases, the probability of entering the queue increases. Because of the server's shorter vacation period, the regular busy period probability will increase. Such trends are consistent with the practical situations. We find that the entrance probability is decreasing with respect to the arrival probability p . When the arrival probability is higher, arriving customers expect that the system is more loaded and are less inclined to enter as they have no information about the present queue length or the server's state.

Equilibrium entrance probability for the fully unobservable model. Sensitivity with respect to (a) _{μ v} , for _{μ b} = 1 , p = 0.5 , C = 1 , R = 10 ; (b) _{μ v} , for _{μ b} = 0.6 , C = 1 , R = 10 , θ = 0.1 .

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

4. Conclusions

In this paper we studied the equilibrium customer behavior in fully observable and fully unobservable Geo/Geo/1 discrete time queueing systems with single working vacation. To the authors' knowledge, this is the first time that this discrete time queueing system with single working vacation is explored from a game-theoretic economic viewpoint. Furthermore, we have analyzed the effect of various parameters on the behavior of the customers in the fully observable case and the sensitivity of the equilibrium entrance probability in the fully unobservable case. One extension to the work would be to consider the other two cases as the almost observable case and the almost unobservable case.

Acknowledgments

Research is supported by the National Natural Science Foundation of China (nos. 11171019 and 71390334) and the Program for New Century Excellent Talents in University (no. NCET-11-0568).

Conflict of Interests

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

References

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

[2] N. M. Edelson, D. K. Hildebrand, "Congestion tolls for Poisson queuing processes," Econometrica , vol. 43, pp. 81-92, 1975.

[3] R. Hassin, M. Haviv To Queue or Not to Queue: Equilibrium Behavior in Queueing Systems , vol. 59, of International Series in Operations Research & Management Science, Kluwer Academic, Boston, Mass, USA, 2003.

[4] H. Takagi Queueing Analysis: A Foundation of Performance Evaluation. Vol. 1 , North-Holland, Amsterdam, The Netherlands, 1991.

[5] H. Takagi Queueing Analysis: A Foundation of Performance Evaluation. Vol. 3 , North-Holland, Amsterdam, The Netherlands, 1993.

[6] N. Tian, Z. G. Zhang Vacation Queueing Models , vol. 93, of International Series in Operations Research & Management Science, Springer, New York, NY, USA, 2006.

[7] A. Burnetas, A. Economou, "Equilibrium customer strategies in a single server Markovian queue with setup times," Queueing Systems , vol. 56, no. 3-4, pp. 213-228, 2007.

[8] A. Economou, A. Gómez-Corral, S. Kanta, "Optimal balking strategies in single-server queues with general service and vacation times," Performance Evaluation , vol. 68, no. 10, pp. 967-982, 2011.

[9] P. Guo, R. Hassin, "Strategic behavior and social optimization in Markovian vacation queues," Operations Research , vol. 59, no. 4, pp. 986-997, 2011.

[10] P. Guo, 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.

[11] W. Sun, S. Y. Li, "Equilibrium and optimal behavior of customers in Markovian queues with multiple working vacation," Top , 2013.

[12] F. Zhang, J. Wang, B. Liu, "Equilibrium balking strategies in Markovian queues with working vacations," Applied Mathematical Modelling , vol. 37, no. 16-17, pp. 8264-8282, 2013.

[13] L. D. Servi, S. G. Finn, " M/M/1 queues with working vacations (M/M/1/WV )," Performance Evaluation , vol. 50, no. 1, pp. 41-52, 2002.

[14] D.-A. Wu, H. Takagi, " M/G/1 queue with multiple working vacations," Performance Evaluation , vol. 63, no. 7, pp. 654-681, 2006.

[15] Y. Baba, "Analysis of a GI/M/1 queue with multiple working vacations," Operations Research Letters , vol. 33, no. 2, pp. 201-209, 2005.

[16] I. Rubin, Z. Zhang, "Message delay and queue-size analysis for circuit-switched TDMA systems," IEEE Transactions on Communications , vol. 39, no. 6, pp. 905-914, 1991.

[17] H. Bruneel, B. G. Kim Discrete-Time Models for Communication Systems Including ATM , Kluwer Academic, Boston, Mass, USA, 1993.

[18] W.-Q. Liu, Y. Ma, J.-H. Li, "Equilibrium threshold strategies in observable queueing systems under single vacation policy," Applied Mathematical Modelling , vol. 36, no. 12, pp. 6186-6202, 2012.

[19] Y. Ma, W.-Q. Liu, J.-H. Li, "Equilibrium balking behavior in the Geo/Geo/1 queueing system with multiple vacations," Applied Mathematical Modelling , vol. 37, no. 6, pp. 3861-3878, 2013.

[20] J.-H. Li, N.-S. Tian, "Analysis of the discrete time Geo/Geo/1 queue with single working vacation," Quality Technology & Quantitative Management , vol. 5, no. 1, pp. 77-89, 2008.