Equilibrium customer and socially optimal balking strategies in a constant retrial queue with multiple vacations and $N$-policy

In many service and electronic commerce systems, there exists a new trend to study the behavior of customers in queuing models. In these models, customers can decide whether to join or balk, according to a natural tendency to maximize their personal utility. To this end, from the perspective of game-theory, the decentralized behavior of customers in the queuing system has attracted extensive attentions in recent decades. Generally, queuing systems are divided into the observable case and the unobservable case depending on whether customers can obtain the information about the system upon arrival. The observable case was first studied by Naor [16], who analyzed an $M/M/1$ queue model with a linear reward-cost structure, and obtained equilibrium and social optimal strategies. Subsequently, Naor’s study was extensively extended, see e.g. [6, 11, 18]. Specifically, Edelson and Hilderbrand [6] complemented the unobservable case to Naor’s model. Chen and Frank [2] generalized the model of Naor’s, who assumed that customers and servers use the same discount rate to maximize their expected discount utility. Afterward, some authors studied equilibrium strategies in various invisible models with many different characteristics. The monograph of Hassin and Haviv [10] summarized the main results of the subject under different levels of information.

The present paper aims to discuss equilibrium strategies and socially optimal balking strategies of customers in an $M/M/1$ constant retrial queue with multiple vacations and the $N$-policy. Customers’ retrials are a common phenomenon in service systems and enterprise engineering. For example, arriving calls to a call center will be connected immediately if service staff is available, otherwise customers may have to retry for service after a random time. With the development of information technology, modern call centers may provide some levels of information to callers, e.g., the current number of customers waiting for service and/or expected waiting time, among other possibilities. Server vacation is another useful concept in modeling for situations, in which optimization of resources and/or reduction of cost are/is required. For vacation models, due to technical and cost (or other) reasons, the server might not be able to obtain the information about the current system capacity during the vacation, or it is impossible for the server to immediately return to work when the number of customers reaches a predetermined threshold, or the number of customers in the system is small at the end of the server vacation so that the server is reluctant to return to work, or return to work at the normal service rate. In addition, too frequent startups and changeovers on operations could lead to severe server wear and overhead on cost, the $N$-policy is usually used to solve this predicament, such as batch traffic transfer systems, controlled manufacturing systems and possible others. In the literature, there are relatively fewer papers studying queueing models with $N$-policy from the perspective of economic. Therefore, a model combining customer retrials, server multiple vacations, and the $N$-policy is of practical interest and is our focus of this paper.

As for studies on equilibrium balking strategies of customers, Burnetas and Economou [1] considered queueing models with setup times under several information levels; Economou and Kanta [4] discussed balking strategies for an observable queue with breakdowns and repairs; Liu, Ma and Li [14] explored an observable queue under single vacation policy; Ma, Liu and Li [15] presented equilibrium balking behavior under a multiple vacation policy; Sun, Li and Cheng-Guo [19] investigated equilibrium strategies and optimal balking strategies for an unobservable queue with double adaptive working vacations. Customers’ equilibrium strategies for queue systems with retrials were also reported in the literature, for example, [12, 23] when balking is not allowed, and [5, 21, 13] when balking is allowed. Regarding models implemented with the $N$-policy, Guo and Hassin [7, 8] investigated models at two information levels with homogeneous and heterogeneous customers, respectively; Guo and Li [9] addressed the same issue for systems, which are partially observable, such as the system capacity is observable, or the state of system is observable. Wang, Zhang and Huang [22] presented customers’ strategic behavior and the social optimal problem in a constant retrial queue with the $N$-policy. Sun, Li and Tian [20] discussed equilibrium strategies and balking strategies with multiple vacations and the $N$-policy.

However, different from the previously mentioned literature on the $N$-policy, the present paper assumes that the system can be reactivated if and only if, upon the completion of a vacation, the server finds at least $N$ customers in the virtual orbit; otherwise, the server continues another vacation.

This paper studies equilibrium strategies and optimal balking strategies of customers in a queue with a constant retrial rate, multiple server vacations, and the $N$-policy under two information levels (the observable case and the unobservable case). In this system, there is no waiting area in front of the server and an arriving customer will be serviced immediately if the state of server is idle; otherwise (when the state of the server is busy or on vacation, it has to leave the system to join a virtual retrial orbit waiting for retries according to the FCFS rule. After the completion of each service, the server will take a vacation if the system is empty, or becomes idle if there is at least one customer in the orbit. The idle server will serve the next customer, either a new arrival or a retried customer, whichever comes earlier. The server be reactivated, upon return from the vacation, if at least $N$ customers are presented in the virtual orbit; otherwise, the server will start another vacation. For each type of information level, we determine equilibrium strategies and optimal balking strategies of customers and social welfare. For the observable case, in order to ensure that the server can be reactivated, we derive the optimal balking threshold of customers in the vacation state, which must be greater than the optimal threshold in busy state, and also greater than $N-1$. Therefore, there are three different queuing cases for the observable case, and we study the corresponding stationary distributions for the three queuing cases, and obtain the equilibrium social welfare per time unit. For the unobservable case, we derive the positive equilibrium arrival rate and optimal arrival rate, which are both unique. However, due to the complexity of equations involved, explicit expressions for the equilibrium balking thresholds of customers, socially optimal balking thresholds and optimal social welfare are not available in general. Hence, we use the Particle Swarm Optimization (PSO) algorithm to solve the complex analytic characteristics, by which the numerical optimal solution $({n^{*}}(1),{n^{*}}(2))$, and optimal social welfare ${U_{s}}({n^{*}}(0),{n^{*}}(1))$ and ${U_{s}}({\overline{\lambda}^{*}})$ are obtained. By comparing the numerical results for the two different information levels, respectively, we conclude that the customers’ equilibrium behavior makes the system more congested than that under the socially optimal strategy, and whether the system information should be disclosed to customers depends on how to maintain the growth of the social welfare (i.e., potential demand arrivals). Obviously, in order to maximize the social welfare, which factor determines the level of information disclosure and when to disclose system information to customers are also crucial for the server or social planner. To conclude our main contributions made in this paper, we emphasize that to our best knowledge, a model, which combines features of retrials, multiple vacations, and the $N$-policy, has not been considered in the literature for the purpose of customers’ equilibrium, and optimal balking strategies.

The remaining sections are organized as follows: In Section 2, we describe the model in detail. We derive the corresponding stationary distributions for the three queueing cases, equilibrium thresholds and social benefit per time unit in Section 3. Section 4 contributes to studies for the unobservable case, and we derive the equilibrium arrival rate and optimal arrival rate. Section 5 focuses on using numerical analysis to explore the theoretical findings in the previous sections, and compare the observable and unobservable cases of this model. Section 6 presents discussions and possible further studies.

Consider a single-server retrial queueing system with a constant retrial rate, multiple server vacations, and the exhaustive $N$-policy. We assume that customers arrive to the system according to a Poisson process with rate $\lambda$, served by a single server with exponential service rate $\mu$. There is no waiting area in front of the server. An arriving customer will be serviced immediately if the server is idle and leave the system immediately upon the completion of the service; otherwise (the server is either busy or on a vacation), it will join a virtual retrial orbit according to the first-come, first-served discipline (FCFS). In practice, a customer in the orbit can be viewed as a customer on the waiting list. After the completion of a service, the server becomes idle and immediately searches for the customer from the top of the waiting list. The time of the search is a random variable, exponentially distributed with rate $\theta$. In the search process, if a new customer arrives, the search will be immediately interrupted and the server will return to serving the arriving customer; otherwise (no arrivals during the search process), the customer at the head of the waiting line will be served and will leave the system upon the completion of its service. After all customers in the system are served, or when the system becomes empty, the server will take a vacation of exponential amount of time $V$ with rate $\xi$. During the vacation time, the server will be not available to serve customers. Upon the completion of a vacation, the server will continue to another (independent) vacation with the same parameter if there are fewer than $N$ customers in the system; otherwise, the server will return from vacations (to idle state) and immediately start the same search process as that for the case, described above, when the server becomes idle from busy. This type of queue systems is referred to as the M/M/1/MV queue. Inter-arrival times of customers, service times and the times of retrials are assumed to be mutually independent.

The state of the system at time $t$ can be represented by a random vector $\{(M(t),I(t))\}$, where $I(t)$ denotes the number of customers in the orbit, and $M(t)$ denotes the state of the server at time $t$:

Obviously, the stochastic process $\{(M(t),I(t))\}$ is a continuous-time Markov chain. The corresponding transition rate diagram is shown in Fig. 1. Moreover, the observable case means that arriving customers can observe all information about $M(t)$ and $I(t)$, and the unobservable case implies that arriving customers can not observe any information about $M(t)$ and $I(t)$.

The study of strategic customer behavior is important. In our case, we are interested in deciding whether an arriving customers would join or balk the system. Suppose that every customer receives the same reward of $R$ units for completing its service, which is used to quantify customer satisfaction or the added value of service. In addition, there is a waiting cost of $C$ units per time unit. The total waiting time for a customer is the continuous accumulation of the time when the customer reaches the system and until he leaves the system (including the service time). Customers are risk neutral and want to maximize their expected net benefit. Specifically, if a customer receives the reward of service is more than the expected waiting cost, then he will join the system. If a customer receives the reward of service equal to the expected waiting cost, the customer will be indifferent between joining and balking. Therefore, we only need to consider the reward with satisfying the following inequality:

The above constrain assures that all customers, who find server being idle, always enter the system since his reward $R$ is more than the waiting cost during his expected service time ($1/\mu$). We adopt a natural linear reward-cost structure, and $U$ is defined as the expected net benefit after the service completion, i.e., $U=R-CE[W]$, where $E[W]$ is mean sojourn time of the customer. Obviously, if the customer is balking, it will generate $U=0$.

Under both levels of information levels, under the condition in (1), customers will be sure to enter the system if they find that the state of the system is idle upon arrivals. However, if an arriving customer finds a vacation or busy state, he has to decide whether to leave his contact details (enter retrial orbit) or leave for ever. We further assume that the arriving customers know the policy of the system, i.e., their decisions are irrevocable: the balking customers cannot retry and customers, who joined the system, cannot renege.

As mentioned above, the observable case means that arriving customers can observe all information about $M(t)$ and $I(t)$. Obviously, the information about $I(t)$ (orbit length) is useful when the arriving customer finds the server being busy or on the vacation, but it is useless when the customer finds the server being idle upon arrivals, since in this case the customer will be served immediately regardless of the orbit length. Therefore, in all cases, the information about the system (both $M(t)$ and $I(t)$) is valuable for the arriving customer to make a better assessment on whether or not he should join the system. More specifically, if $M(t)$ is idle, the customer will join the system for sure regardless of $I(t)$; if $M(t)$ is busy or on vacation, according to the FCFS discipline, the arriving customer knows his position in the orbit, which can help him in deciding whether entering the system is preferable. In the observable case, define $W(i,n)$ to be the sojourn time of the marked customer, who joins the system at state $(i,n-1)$ ($i=1,2,3$). For studying optimal balking strategies, we need to consider the expected (residual) net benefit of the marked customer, who is at the $n$th position in the orbit and the state of the server is $i$, after he receives the service. We denote the equilibrium balking threshold of customers and the integrated strategy at sate $i$ by ${n_{e}}(i)$ and $({n_{e}}(0),{n_{e}}(1))$, respectively. In addition, we denote the socially optimal balking threshold of customers and the integrated strategy at state $i$ by ${n^{*}}(i)$ and $({n^{*}}(0),{n^{*}}(1))$, respectively. To characterize ${n_{e}}(0)$ and ${n_{e}}(1)$, we first give the following theorem.

Since $T(1,0)$ represents the mean residual service time of the customer, who is receiving the service, we have

For $n\geq 1$, let $m(n)$ be the probability of joining the virtual orbit for the arriving customer, who finds the server being busy and $n$ customers being in the orbit. Then, based on a first step argument and noticing that the mean time to the next event is $1/(\lambda m(n)+\mu)$, and the next event is an arrival or a service completion with probability $\lambda m(n)/(\lambda m(n)+\mu)$ or $\mu/(\lambda m(n)+\mu)$, respectively, we have

When the server state is idle, we can similarly get

For $i=0$, we only need expressions for $n\geq N$ (see Remark 3.1), which is given by

In terms of (7) and by solving (6) for $T(1,n)$, we get

which leads to (3). Substituting (3) into (7) produces (4). Finally, substituting (4) into (8) gives (2), which completes the proof.