Queue with Batch Service, Batch Size Determined by Emergency Customers

Abstract

We consider a queueing system o ering batch service for heterogeneous customers. Two types of customers called ordinary customers and emergency customers arrive to the system according to a marked Markovian arrival process of order 2. There is an in nite queue and nite bu er in front of the station. Ordinary customers arrive to the in nite queue and emergency customers to the nite bu er. Service is provided in batches with maximum batch size K: If the number of emergency customers is greater than or equal to K, the rst K of them will be taken together into service and if it is less than K, ordinary customers are taken along with emergency customers so as to maximize the batch size. In the absence of emergency customers, if there are at least K ordinary customers, then rst K of them will be served next. For a batch of size i; 1 i K, the service time follows a phase type distribution with representation P H( i; Si). The model possesses the characteristics of a vacation queueing model. The system is analyzed using Matrix analytic Method. Performance characteristics are derived. The model is numerically illustrated with suitable example.

Keywords

• Batch Service
• Marked Markovian Arrival Process
• Emergency Customer
• Matrix Analytic Methods
• Phase Type Distributions

-

In this paper we study the mathematical model of a courier delivery system with emergency arrivals and bulk service. The model has found applications in priority based signal transmission systems as well. Numerous real life problems can be modelled as queues with bulk service and a rich literature on bulk queues is available. Delivery systems of online marketing, courier services, transportation vehicles and airline services etc. are typical examples for bulk service systems. Each of these systems possesses its own special features. In delivering items, the emergency orders are usually served with priority. Sometimes instantaneous service is called for the emergency customers due to urgency (e.g. delivery of highly perishable items like samples of body uids for diagnostic service, animal sperm, medical essentials upon order placing etc.). It is e ective to incorporate threshold policies in bulk queues to maximize revenue generation and a great exploration for mathematical results is possible in this direction.

One of the early works in bulk queues is due to M. F. Neuts [ 13 ]. In this work, the customers are taken together to the service station until queue length reaches a speci ed level (L). If the queue grow beyond L and reaches K all the customers up to K are taken together, the customers beyond K must wait in queue. H. Gold and P. Tran-Gia [ 6 ] studied an M=G[a; b]=1 S queueing system. The main motivation for this model is the manufacturing systems with batch serving stations (machines for computer components and chip production).

M. L. Chaudhry and U. C. Gupta [ 5 ] describe an M=Ga;b=1=N queue and queue is studied using supplementary variables and embedded Markov chain techniques. A nite bu er M=G=1 queue with general bulk service rule and single vacation is studied by U. C. Gupta and K. Sidkar [ 8 ] and in this model batch size is restricted to a range of values, and when the queue length falls below the in mum, the server goes for a vacation.

W. B. Powell [ 16 ] studies a general class of vehicle dispatching strategies for bulk arrivals, bulk service queue. D. J. Van De Rzee, A. Van Haeten and P. C. Schuur [ 22 ] describe control strategies for reading the cost of multi server batch operation systems. S. Kuppa and G. Dattatreya [ 10 ] describe frame aggregation in unsaturated WLAN's with nite bu ers and in this model method for aggregation of more than one data form for transmission is described as an application for bulk queues. A. Banerjee and U. C. Gupta [ 1 ] analyze a single server nite bu er queue with Poisson arrival and bulk service and batches are arbitrarily distributed and depends the size of the current batch in service and the aim is to reduce congestion in the system.

J. Baetens, B. Steyaert, D. Claeys, and H. Bruneel [ 2 ] analyze a discrete time BM AP=Gl;c=1 queue in which service time of a batch depends the current batch size and a timing mechanism to reduce waiting time is also proposed. M. Yu and A. S. Alfa [ 23 ] describe an algorithm for computing the queue length distribution at various time epochs in a DM AP=Ga;b=1=N queue with batch size dependent service times and the impact of correlation on system characteristic is also discussed. [ 11,7,4 ] and [ 2 ] give live descriptions of batch service queues with dependent batch size.

A. Sikadar and S. K. Samantha [ 19 ] studied a bulk service queue with service vacation and vacation starts when all the customers are exhaustively served. In [ 17 ] G. V. Krishna Reddy, R. Nadarajan and P. R. Kandasamy considered a bulk service system with heterogeneous arrivals and bulk service is provided to the class of customers with low priority. In [ 2 ] J. Baetens, B. Steyaert, D. Claeys, and H. Bruneel analyze a two class batch service queueing model with variable server capacity and batch size is determined by number of consecutive same-class customers. In [ 3 ] J. Baetens, B. Steyaert, D. Claeys, and H. Bruneel analyze delay of a random customer in a two class batch service queueing model with variable service capacity and batch size is determined by the length of the sequence of same class customers. An excellent survey by S. Sasikala, K. Indhira on bulk service queueing models is demonstrated in [ 18 ].

A phase type distribution may be de ned as the distribution of the time until absorption takes place in a Markov process with a nite state space and a single absorption state de ned over nonnegative real line. A phase type distribution with transient states f1; 2; : : : ; ng and an absorbing state n + 1 is represented by a two tuple of the form ( ; T ), where is the probability vector of length n according to which the process selects the initial state from f1; 2; : : : ; ng and T

T T 0 is an n n matrix such that 0 0 generates the process, given the column vector T 0 satis es the condition T e+T 0 = 0, where e is the vector of ones. ( ; T ) is called the representation of the phase type distribution. The distribution F of time until the chain gets absorbed into the state n + 1 is given by F (x) = 1 exp(T x)e, x 0. The set of all phase type distributions is a dense subset of the set of all distributions on the non-negative real line and hence it is a best tool to approximate any arbitrary distribution in this set. For more descriptions on phase type distributions see [ 14 ].

A Marked Markovian arrival process (MMAP) is a stochastic point process with heterogeneous arrivals in discrete or continuous time. MMAP may be described as follows: Let C be set of indices which describes di erent types of customers. Let Nh(t) be the number of arrivals of type h in [0; t] such that Nh(0) = 0; 8h 2 C: Consider the set of nonnegative matrices fDh : h 2 Cg: Let D0 is a matrix with nonnegative o -diagonal elements and negative diagonal elements, and D = D0 + Ph2C Dh be an in nitesimal generator of order m, and fI(t) : t 0g be a continuous time Markov chain de ned by D: Then (D0; Dh; h 2 C) de nes an MMAP fNh(t); h 2 C; I(t); t 0g: The Markov chain fI(t) : t 0g is called the underlying Markov chain of fNh(t); h 2 C; I(t); t 0g: For description of MMAP model see [ 9 ]. Analysis of queues using matrix analytic method can be seen in [ 20,21 ]

Upcoming sections are arranged as follows: Section 2 describes the mathematical model stability condition and stationary distribution is also obtained in this section. Performance characteristics are included in Section 3. Service time analysis is done in Section 4. Waiting time analysis is given in Section 5. The model is numerically illustrated in Section 6. Section 7 concludes the work. 2

Mathematical Model

The customers arriving to the system are of two types, namely ordinary customers and emergency customers. The arrival is according to a MMAP determined by the matrices D0; D1 and D2. D0 gives the rate of transitions in the underlying process without an arrival, D1 and D2 gives the rate of transitions for ordinary and emergency arrivals respectively. The matrix D = D0 + D1 + D2 is an in nitesimal generator of the underlying process. If is the steady state distribution of D then i = Die; i = 1; 2 is the fundamental rates of ordinary and emergency arrivals.

We de ne

For each i < K, where and

2 (2 1 2 + (X

k=1 The service discipline is as follows: service is provided in batches with maximum batch size K: If the number of emergency customers is greater than or equal to K, the rst K of them will be taken together into service and if it is less than K, ordinary customers are taken along with emergency customers so as to maximize the batch size. In the absence of emergency customers, if there are at least K ordinary customers, then rst K of them will be served next. Service time for a batch of size j is distributed with a phase type representation P H( j ; Sj ): The following are system descriptors at the time t.

N1(t) - Length of the in nite queue.

N2(t) - Number of customers in nite bu er. I(t) - Status of the server.

S(t) - Phase of the service.

a(t) - Phase of MMAP.

The server status is de ned as follows.

I(t) = 0; if the server is idle i; if the sever is busy with i customers; 1 i

K:

Y(t) = fN1(t); N2(t); I(t); S(t); a(t)g: Then fY(t); t

0g is a continuous time Markov process on the state space

If the covariance of number of ordinary customers n1(t) and that of emergency customers n2(t) is given by cov(n1(t); n2(t)) =

Dk(D

e ) 1D3 k)e)t e ) 1exp(DtI (D

e ) 1)D3 k))e: (1)

S = [i 0L(i):

L(i) = L1(i) [ L2(i); L1(i) = f(i; 0; l); 1 l

ag L2(i) = f(i; i1; 1; j; k); 0 i1 L1 contains the states in which there are no priority customers and the server is idle and L2(i) corresponds to states in which server is active and in this case bu er can be empty or non empty.

For i The states in all the levels greater than or equal to K will only contain states in which server is busy.

The in nitesimal generator Q of Y takes the form 0 Note that the Kronecker sum and product are used. The non zero blocks in the above matrix arise due to the transitions described below.

From (i,0,0,l), 0 i < K (i,0,0,l), i K

(h,0,0,l), h (i,0,g,j,k), 1 i (i,i',g,j,k), 1 k; k (i,i',g,j,k), k; k (i,1,j,k), K + 1 i (i,1,j,k), K + 1 i (i,1,j,k),K + 1 i

1 k; k a (i,1,j,k), 0 i K (i,1,j,k),0 i K (i,1,j,k),i > K 0 K 2K 2K 2K 2

Clearly in the in nitesimal generator Q there are non-zero blocks Aj ; 1 j K, due to which Q loses its QBD structure. In order to gain a QBD structure for the matrix Q, the levels are rede ned by merging them appropriately. The levels lK + 1 to (l + 1)K, l = 0; 1; 2; : : : , are merged together, and modi ed generator Q0 is described below.

After merging of cells the modi ed form of Q take the structure A00 = D0; A01 = (D1 1

D2); B10 = [A1A2 : : : AK ]T ;

B11 = diag(A11; A21; : : : ; AK1) + ( 0 + diag(A12; A22; : : : ; Ak 12)); B21 = diag(AK+11; AK+21; : : : ; A2K1) + ( 0 + diag(A12; A22; : : : ; Ak 12)); B1 = diag(A2K+11; A2K+21; : : : ; A3K1) + ( 0 + diag(A12; A22; : : : ; Ak 12)); B12 = diag(diag(D0; Ir (D1 + D2); : : : ; diag(D0; Ir

(D1 + D2));

B2 = diag(A1#; A2#; : : : ; A#K ); B0 = diag(Ir (D1 + D2); : : : ; Ir (D1 + D2)):

Clearly Q0 posses a QBD structure. The matrix B = B0 + B1 + B2 is an in nitesimal generator and the steady state distribution of B is obtained below.

B = IK

diag(V1; V2; : : : ; Var); Vi = e i (S30 ar: Let = ( 1; 2; : : : K ) be the corresponding steady state probability vector, i = ( i1; i2; : : : ; iK ); i 1: may be obtained as the solution to the system B = 0 and eKar = 1 where eKar is a column vector of ones having length Kar. B is a singular matrix as it can have at most Kar 1 linearly independent rows. Hence B = 0 has a non trivial solution , this solution can be normalized to satisfy the condition eKar = 0.

Theorem 1. The system is stable if and only if

K X i=1 iIr

K (D1 + D2) < X i(e

i=1 Proof. The system is stable if and only if B2e < de ned in Lemma 2 i (S30

Ia)):

B0e; see [15]. From matrices

K B2e = X

i=1

K B0e = X i(e i=1 iIr (D1 + D2); i (S30

Ia)): tu

The stationary distribution of the system process is obtained as follows. Under the assumption of the stability condition, the steady state probability distribution exists. Let y = (y0; y1; y2; : : : ) be the steady state probability vector of the Markov Chain Y, where yi = (yi0; yi1; : : : ; yiM ). Then y is the unique solution to the system of equations yQ = 0 and ye = 1. Then each component yi ia a vector of length Kar.

From yQ0 = 0 and ye = 1, we have the system of equations

y0A00 + y1B10 = 0 y0A01 + y1B11 + y2B20 = 0 y1B12 + y2B21 + y3B2 = 0 y1B0 + y3B1 + y4B2 = 0 . .

.

Now from Matrix analytic method, yc+i = ycRi, i = 0; 1; 2 : : :,where R is the minimal nonnegative solution of matrix quadratic equation R2A2+RA1+A0 = 0. R is computed algorithmically, using the logarithmic reduction algorithm [ 12 ]. 3

Performance Characteristics of the System

Expected number of ordinary customers in the system. The expected service time of a customer is described as follows. The service process can be considered as a continuous time Markov process on the nite state space f#g [ f(j; l; m); 1 j

K; 1 r; 1 m ag and f#g is the absorbing state. 0 A11 A12

A21 A22 . . .

l ; Qs =

Expected service time of an arbitrary customer is given by

Est = . . .

0 S0

1 S0

2 0

SK0 1 . . . 0

K 1 K CC

CC ; 0 C

C K A

Expected Waiting Time of an Emergency Customer

When at Least K Ordinary Customers are in Waiting

The expected waiting time of an emergency customer is described as follows. Consider the process H = f( (t); I(t); s(t)); t 0g. Then H is clearly an irreducible continuous time stochastic process de ned on a nite state space f(i; j; k); 1 i M; 1 j K; 1 k rg [ f g, where represents the absorption state and all other states are transient. The in nitesimal generator of this process is as shown below.

QH =

0 C C 0 0 ; where

C0 = (CM0 ; CM0 1; : : : ; C10)T ; Ci0 = (0; 0; : : : ; SK0

K ); 0 i

M: The waiting time of an emergency customer follows a phase type distribution with representation ( ; C), where = ( 1; 2; : : : ; K ) and i = K1r i eT : Expected waiting time of an emergency customer is

Eew =

C 1e: 6

Numerical Example

We illustrate the model by considering a system with K = 2; the service times are exponentially distributed with parameters 1 and 2: We take arrival rate of ordinary customers as and arrival rate of emergency customers as . The matrices de ning the MMAP process takes the form D0 = ( ); D1 = ( ); D2 = ( ): . . .

1 C C C

CC ; C0 CC

C

A

C1 g

M

K;

Fig. 1. Variation in queue length with respect arrival rates.

In Figure 1 variation in expected number of ordinary customers in the system, (EN1 ) with respect to the variations in arrival rates of ordinary and emergency customers is depicted. It is observed from Figure 1 that accumulation of ordinary customers increases in the queue as arrival rate of emergency customers increases. Figure 2 describes the variation in (EN1 ) with respect to the service rates 1 and 2: Figure 3 shows that the probability that system is in idle state decreases with the increase of rate arrival of the ordinary customers. 7

Conclusion

In this paper we have studied a queue with batch service and batch size depends the number of customers in the bu er. The model is observed in a courier delivering system with two kinds of arrivals. The strategy for batch size determination is designed for reducing system cost. The model is analyzed using matrix analytic method and is illustrated with a numerical example.

Acknowledgment

Sinu Lal T. S. thanks University Grants Commission(UGC) of India for UGCJunior Research Fellowship(Roll no.-432693,June 2017).

References

1. Banerjee , A. , Gupta , U. C., Sikdar , K. : Analysis of nite bu er bulk-arrival bulkservice queue with variable service capacity and batch size-dependent service , International Journal of Mathematics in Operational Research , 5 , ( 3 ), 358 - 386 ( 2013 ).

2. Baetens , J. , Steyaert , B. , Claeys , D. , Bruneel , H.: System occupancy of a two class batch service queue with class dependent variable server capacity , International Conference on Analytical and Stochastic Modeling Techniques and Applications , 32 - 44 , Springer ( 2016 ).

3. Baetens , J. , Steyaert , B. , Claeys , D. , Bruneel , H.: Delay analysis of a two class batch service queue with class dependent variable server capacity . Mathematical Methods of Operations Research , 88 ( 1 ), 37 - 57 ( 2018 ).

4. Baetens , J. , Steyaert , B. , Claeys , D. , Bruneel , H.: System occupancy in a multiclass batch-service queueing system with limited variable service capacity . Annals of Operations Research , 1 - 24 ( 2019 ).

5. Chaudhry , M. L. , Gupta , U. C. : Modelling and analysis of M=Ga;b=1=n queue a simple alternative approach , Queueing Systems , 31 ( 1-2 ), 95 - 100 ( 1999 ).

6. Gold , H., Tran-Gia , P. : Performance analysis of a batch service queue arising out of manufacturing system modelling . Queueing Systems , 14 ( 3-4 ), 413 - 426 ( 1993 ).

7. Gupta , G. , Banerjee , A. : On M=G( a;b)=1=n queue with batch size and queue length dependent service . International Conference on Mathematics and Computing , 249 - 262 , Springer ( 2018 ).

8. Gupta , U. C., Sikdar , K. : The fnite-bu er m/g/1 queue with general bulk-service rule and single vacation , Performance Evaluation , 57 ( 2 ), 199 - 219 ( 2004 ).

9. He , Q-M.: Fundamentals of matrix-analytic methods , Vol. 365 , Springer, New York ( 2014 ).

10. Kuppa , S. , Dattatreya , G.: Modeling and analysis of frame aggregation in unsaturated wlans with nite bu er stations , IEEE International Conference on Communications , 3 , 967 - 972 , IEEE ( 2006 ).

11. Maity , A. , Gupta , U. C. : Analysis and optimal control of a queue with in nite bu er under batch size dependent versatile bulk-service rule . Oper. research , 52 ( 3 ), 472 - 489 ( 2015 ).

12. Latouche , G. , Ramaswami , V. : Introduction to matrix analytic methods in stochastic modeling , Vol. 5 , Siam ( 1999 ).

13. Neuts , M. F. : A general class of bulk queues with Poisson input . The Annals of Mathematical Statistics , 38 ( 3 ), 759 { 770 , JSTOR ( 1967 ).

14. Neuts , M. F. : Probability distributions of phase type . Liber Amicorum Prof . Emeritus H. Florin ( 1975 ).

15. Neuts , M. F. : Matrix-geometric solutions in stochastic models: an algorithmic approach . Courier Corporation ( 1994 ).

16. Powell , W. B.: Analysis of vehicle holding and cancellation strategies in bulk arrival, bulk service queues . Transportation Science . 19 ( 4 ), 352 { 377 , INFORMS ( 1985 ).

17. Reddy , G. K. , Nadarajan , R. , Kandasamy , P.: A nonpreemptive priority multiserver queueing system with general bulk service and heterogeneous arrivals . Computers and operations research , 20 ( 4 ), 447 - 453 ( 1993 ).

18. Sasikala , S. , Indhira , K. : Bulk service queueing models survey . International Journal of Pure and Applied Mathematics 106 ( 6 ), 43 - 56 ( 2016 ).

19. Sikdar , K. , Samanta , S.: Analysis of a nite bu er variable batch service queue with batch markovian arrival process and servers vacation . Oper. research , 53 ( 3 ), 553 - 583 ( 2016 ).

20. Sinu Lal , T. S. , Krishnamoorthy , A. , Joshua , V. C. : A Multiserver Tandem Queue with a Specialist Server Operating with a Vacation Strategy . Automation and Remote Control , 81 , 760 - 773 ( 2020 ).

21. Sinu Lal , T. S. , Krishnamoorthy , A. , Joshua , V. C. September . A Queueing Inventory System with Search and Match-An Organ Transplantation Model . International Conference on Distributed Computer and Communication Networks , 273 - 287 , Springer, Cham ( 2019 ).

22. Van De Rzee , D. J., Van Harten , A. , Schuur , P. C. : Dynamic job assignment heuristics for multi-server batch operations-a cost based approach . International Journal of Production Research , 35 ( 11 ), 3063 - 3094 ( 1997 ).

23. Yu , M. , Alfa , A. S. : Algorithm for computing the queue length distribution at various time epochs in DM AP=G(1;a;b)=1=n queue with batch size dependent service time . European Journal of Operational Research , 244 ( 1 ), 227 - 239 ( 2015 ).