key: cord-0058738-qlat7oj0
authors: Ferreira, Fátima; Pacheco, António; Ribeiro, Helena
title: Numbers of Served and Lost Customers in Busy-Periods of M/M/1/n Systems with Balking
date: 2020-08-20
journal: Computational Science and Its Applications - ICCSA 2020
DOI: 10.1007/978-3-030-58808-3_12
sha: 4d3df2b5f1b3ee60684e18896d0c2e96c05d93d9
doc_id: 58738
cord_uid: qlat7oj0

In this work we analyze single server Markovian queueing systems with finite capacity and balking, that is M/M/1/n systems with balking. In these systems, the admission of customers is modulated by the state of the system at the instants of customer arrivals. Depending on the size of the queue upon arrival, customers that find place to join the system decide to enter the system with a certain probability. The number of customers in the system amounts to a Markov chain whose transition probabilities incorporate the balking probabilities. Using the Markovian regenerative property of the chain embedded at the instants of arrival or departure of customers, we characterize the joint probability distribution of the number of customers served and the number of customers lost in busy-periods, that is, during continuous occupation periods of the server. This is accomplished implementing a priori a recursive algorithmic procedure for computing the respective probability-generating function. Finally, a numerical illustration of the derived results is presented for different balking policies.

The perception of the queue length by an arriving customer plays a relevant role in their decision to whether join (or not) a queueing system. In fact, in current rush days there is a growing tendency of customers to balk (i.e., to not join the system) when facing at arrival a long queue size (that exceeds their patience level) or a short queue if a loaded system is perceived as a good condition.

As the balking phenomenon may result in significant loss of customers, the analysis of queueing systems with balking is important in practice.

In this work we address the study of finite capacity Markovian queues with a single server under different customer blocking policies when the customers arrive at the system. Using the notation introduced by David G. Kendall, this corresponds to a M/M/1/n system with balking or reverse balking. These systems have many applications because in many real-life situations customers often have the possibility to postpone or give up a given type of service when, on arrival at the system, the level of server congestion is considered unsatisfactory by the same customers.

The notion of customer balking was introduced in the work of Haight [5] that considers an M/M/1 queue in which customers do not join the system whenever they face at arrival a queue length larger than a fixed threshold. After this pioneering work, the study of queues under different balking and other types of customer's impatience policies has aroused the interest of several authors (cf [2] [3] [4] [7] [8] [9] [10] 12, 14, 15] and references therein). A review on queueing systems with impatient customers can be found in [13] .

The analysis of queues with balking in busy-periods, i.e., in continuous periods of effective use of the server, is relevant from the operator's point of view and provides crucial information for its management. We consider multi busy-periods, i.e., busy-periods initiated with multiple customers in the system. Specifically, by a busy-period initiated by i customers, hereinafter referred to as i-busy-period, we mean the period of time that starts at an arrival instant that makes the system stay with i customers, and ends at the first subsequent time at which the system becomes empty, with a customer initiating service after the arrival instant. This definition is in line with that of remaining busy-period from state i given in Harris [6] , of residual busy-period provided in Hanbali [1] and of busy-period initiated with i customers considered in Peköz et al. [11] .

The aim of this paper is to characterize the joint probability distribution function of the number of customers served and the number of customers lost in busy-periods of M/M/1/n system with balking. In Sect. 2, after describing the system we present the transition probability matrix of the discrete time Markov chain (DTMC) embedded at the moments of arrival or departure of customers. Taking advantage of the Markovian structure of these queues and by using the probability-generating function technique, we obtain in Sect. 3 the joint probability function of the number of customers served and the number of customers lost in busy-periods.

In Sect. 4 we illustrate the results obtained and, finally, we present some concluding remarks in Sect. 5.

We consider M/M/1/n systems with balking of customers. These are queues with finite capacity, n, at which the customers arrive (one by one) according to a Poisson process with rate λ and are served (one by one) by a single-server, in a first-come first-served discipline. Service times are independent and identically exponential distributed variables with rate μ, and are independent of the arrival process.

These systems differ from the traditional M/M/1/n given that the customer admission is modulated by the state of the system at the time of arrival. As in the traditional M/M/1/n systems, if on arrival a customer finds the system full (with n customers) he is blocked with probability 1. However, if on arrival a customer finds i < n customers in the system, even though there is place in the system to accommodate the customer, he either decides to join the queue with probability e i or not to enter (balk) with probability 1 − e i . For completeness we let e n = 0.

empty queue 2-busy-period We let Y (t) denote the number of customers in the system at time t. A typical sample path and the transition-rate diagram of Y (t) are given in Figures 1  and 2 , respectively. In Fig. 1 , the sequence (τ n ) n∈IN is the sequence of arrival or departure instants. As the interarrival and the service times have exponential distributions, the process

, and vector of transition rates out of states r = (r i ) i∈E with r i = λ + μ1 {i>0} , where 1 A denotes the indicator function of statement A. As a consequence, the processȲ = (Y (τ k )) k∈IN embedded at the sequence (τ k ) k∈IN of instants of arrival or departure of customers is a DTMC with state space E and transition probability matrix P = (p ij ) i,j∈E , such that

In this section we derive the joint probability function of the random vector (S i , L i ) where, for i ∈ E\{0}, S i denotes the number of customers served during an i-busy-period and L i denotes the number of customers lost during an i-busyperiod.

To this purpose, we introduce the probability-generating function of (S i , L i ),

with |u| ≤ 1 and |v| ≤ 1, from which, by derivation, we obtain the probability function of (S i , L i ),

The following theorem presents properties of the probability-generating function of (S i , L i ).

Proof. Denoting by X the type of event that occurs at the instant τ k of the first transition after starting a i-busy-period, we let

if a customer exits the system at τ k 0, if a customer arrives without entering the system at τ k 1, if a customer arrives and enters the system at τ k .

Conditioning on the event {X = x}, and letting = st denote equality in distribution, we obtain

and, for i ∈ E\{0, n}, 

and, for i ∈ E\{0, n},

We will now prove the statement of the theorem using induction, starting with the case i = n. Taking into account (1), (2) and (5), we obtain:

This implies that

Therefore, the Eqs. (3)-(4) are valid for i = n.

Let us now assume that the Eqs. (3)-(4) are valid for i = j + 1 with j being a fixed number such that 1 < j < n. Taking into account (1), (2) and (6), we obtain:

Thus,

Thus, isolating g j (u, v), we obtain Eqs. (3)-(4) for i = j. Therefore, by induction, the statement of the theorem is valid.

We conclude this section by presenting, in Fig. 3 , a recursive procedure to obtain the probability generating function of (S i , L i ) in M/M/1/n systems with balking, departing from g 0 (u, v) = 1.

In this section, using the above-derived results, we compute the joint probability function of the number of customers served and the number of customers lost in busy-periods of M/M/1/n systems with unit service rate (μ = 1) and the following three customer balking policies. 

End for Output: (gi(u, v) )i=1,2,...,n . . , 1 8 , 0) and arrival rates λ = 0.5 and λ = 1.1, respectively. In the system with low traffic intensity (Table 1) , as the arrival rate is much lower than the service rate, the queue has a small trend to fill up and to have a high number of losses. Consequently, the higher joint probabilities are associated to the lowest values of the number of customers served and of the number of customers lost. In fact, we observe that P (S 1 ≤ 3, L 1 ≤ 3) = 0.9831. Table 1 . Joint probability function of the number of customers served and the number of customers lost in 1-busy-period of a M/M/1/7 system with service rate μ = 1 and arrival rate λ = 0.50, P (S1 = s, L1 = l) for s = 1, . . . , 9 and l = 0, 1, . . . , 9. 

In contrast, the system with higher utilization rate (Table 2 ) has a greater tendency to fill up and to experience more balking and customers blocked. In this case, we observe that P (S 1 ≤ 3, L 1 ≤ 3) = 0.8933 as higher values of the number of customers served and of the number of customers lost still have positive joint probabilities. Figure 4 illustrates the sensitivity of the joint distribution function of (S 1 , L 1 ) at point (3, 3) of M/M/1/10 systems, as function of the utilization rate (ρ = λ/1), considering three customer balking policies: e (1) = (1, 1, . . . , 1, 0) , e (2) = ( 1 2 , 1 3 , . . . , 1 11 , 0) and e (3) = ( 1 11 , 1 10 , . . . , 1 2 , 0). As expected, for the three balking policies, the joint distribution at the considered point decreases as the utilization rate increases. This decrease is more highlighted in the traditional M/M/1/10 systems, that is the system with e (1) policy, where customers always enter in the system while it is not full up. Among the M/M/1/10 systems considered, the systems with balking, and in particular the system with e (3) policy (reverse balking), show higher joint distribution of (S 1 , L 1 ) at (3, 3) in contrast to the traditional M/M/1/10 system. 

The number of customers served and the number of customers lost during busyperiods are important queueing performance measures. Although the analysis of their joint behavior constitutes an added value for the characterization of the queueing system, to our knowledge, the joint probability distribution of such measures has not been derived in the literature.

In this work the joint probability function of the number of customers served and the number of customers lost in busy-periods was obtained for single server Markovian queueing systems with finite capacity and balking. In particular, we derived a recursive procedure to compute the probability-generating function of the number of customers served and the number of customers lost in busy-periods that can be initiated by multiple customers in the system.

The derived recursion was applied to numerically compute the joint probability function of the number of customers served and the number of customers lost in busy-periods of M/M/1/n systems under partial blocking and monotonic (increasing/decreasing) customer balking policies.

The approach followed in the paper can be generalized to obtain the joint probability distribution of the number of customers served and the number of customers lost during busy-periods of Markovian queues with batch arrivals and balking and reneging.

Busy period analysis of the level dependent P H/P H/1/K queue

Some queuing problems with balking and reneging II

Analysis of GI X /M (n)//N systems with stochastic customer acceptance policy

Algorithmic computation of steady-state probabilities in an almost observable GI/M/c queue with or without vacations under state dependent balking and reneging

Queuing with balking I

The remaining busy period of a finite queue

An M/M/1/N queuing system with reverse balking

Transient analysis of an M/M/c queuing system with balking and retention of reneging customers

An M/M/1/N queuing system with reverse balking and reverse reneging

Analysis of finite-buffer multi-server queues with group arrivals

Characterizing losses during busy periods in finite buffer systems

A heterogeneous queuing system with reverse balking and reneging

Queuing system with impatient customers: a review

Analysis of a busy period queuing system with balking, reneging and motivating

Optimal performance analysis of an M/M/1/N queue system with balking, reneging and server vacation