Control policy of a hysteretic bulk queueing system

Available online at www, sciencedirect.com solE.c-

ELSEVIER

MATHEMATICAL AND COMPUTER MODELLING

~.,.moT-

Mathematical and Computer Modelling 41 (2005) 571-579 www.elsevier.com/locate/mcm

Control Policy of a Hysteretic Bulk Queueing System L. TADJ Department of Statistics and Operations Research College of Science, King Saud University P.O. Box 2455, Riyadh 11451, Saudi Arabia lotft adj~ksu, edu. s a

JAU-CHUAN KE Department of Statistics National Taichung Institute of Technology No. 129, Sec. 3, Sanmin Rd. Taichung 404, Taiwan, R.O.C. j auchuan@mail, at it. edu. tw

(Received and accepted July 2003) Abstract--This paper is concerned with the optimal control of a batch arrival, bulk service queueing system under N-policy. If the number of customers in the system at a service completion is larger t h a n some integer r, then the server starts processing a group of r customers. If, on the other hand, it is smaller t h a n r, then the server idles and waits for the line to grow up to some integer N, ( N _> r). System characteristics are obtained by means of the embedded Markov chain and semiregenerative techniques, then the expected total cost per unit of time is developed for this model. Finally, a search procedure is presented to determine the optimal thresholds r and N t h a t yield the minimum cost. O 2005 Elsevier Ltd. All rights reserved.

K e y w o r d s - - B a t c h arrival, Bulk service, Hysteresis, Embedded Markov chain, Semiregenerative process, Control policy.

1. I N T R O D U C T I O N The goal of this paper is to design an optimal control policy for a batch arrival, bulk service queueing system under N-policy. In this system, customers arrive to the queueing facility in groups of random size and are served in groups of a fixed size. The server checks the queue at every service completion instant. Given two fixed thresholds r and N, ( N > r), if more than r customers are in line, then the server picks a group of r customers and processes them in a single batch. If less than r customers are in line, then the server idles and waits for the queue to reach the value N. Once the level N is reached (or exceeded, because arrivals are in batches), then a group is picked and the r customers are served altogether. Using Kendall's notation, the model considered here is an MX/Gr/1 under N-policy. The optimal control of bulk service systems was started by the authors in [1] where an M / G r / 1 under N-policy was considered. In this paper, the results of [1] are generalized to the case where 0895-7177/05/$ - see front m a t t e r (~ 2005 Elsevier Ltd. All rights reserved. doi:10.1016/j.mcm.2003.07.017

Typeset by ~4j~4S-TEX

572

L. TADJANDJ.-C. K~.

the arrival process is no longer orderly Poisson but compound Poisson. The literature on the optimal control of N-policy queueing systems is rich and varied. Various scenarios have been considered by the researchers, see [1] for a survey. Nevertheless, to the best of the authors' knowledge, except in [1], the optimal control of a bulk service system has not been dealt with. We analyze the model by the method of embedded Markov chain and semiregenerative techniques. We derive all the key elements required to build a prescriptive model for the queueing system: system-size steady-state probabilities of the discrete and continuous time parameter processes, along with some important system characteristics such as mean system size, mean busy period, mean idle period, and mean busy cycle. The prescriptive model of this system consists in designing an optimal control policy. We seek optimal values for the threshold levels r and N. What should these values be in order to minimize the system's expected cost per unit of time? The model is described and analyzed in Section 2. Section 3 discusses the control problem. Our interest is in the numerical results of Section 4, in which the model is studied in detail and some important operating characteristics are revealed. Conclusions are given in Section 5.

2. M O D E L D E S C R I P T I O N A N D S T E A D Y - S T A T E R E S U L T S Consider the MX/Gr/1 queueing system. The arrival process is compound Poisson with rate A. Sizes of successive arriving batches are Xo, X1,..., where X0 = i and X1,X2,... are lid, distributed as a(z) = E[zX1]. The first and second moments, a = E[X1] and a2 = E[X~], respectively, are assumed to be finite. The process Sn = Xo + X1 + ... + Xn is a delayed renewal process. The service time as of n th batch of customers has a general distribution B(t) with LaplaceStieltjes transform B*(s) = E[e-8a~], and finite first and second moments, b --- E[a~] and b2 = E[a2], respectively. The waiting room is unlimited. The service discipline is FIFO. The process of interest is the number Q(t) of customers in the system at time t. Let T~ denote the n t h service completion instant. Then, Q~ = Q(T~+) is the embedded process and represents the number of customers in the system at a service completion epoch. The service discipline is as follows. If at a service completion there are more than r customers in the queue, then the server takes a batch of customers of size r to process in a single batch. On the other hand, if at a service completion there are less than r customers in the queue, then the server starts an idle period and when the queue size reaches (or, most probably, exceeds) for the first time the value N, (N > r), then he takes a batch of customers of size r to process in a single batch. Analysis of this bulk queueing system requires knowledge of the first excess level and other related processes. Let the index ~ be, such that u = inf{k : Sk

>_N}.

If ~'i denotes the arrival epoch of group Xi, then the instant T. is the first passage time after Tn of the queueing process to reach or exceed level N. The level S~ is called the level of the first excess. It was studied in a work of Abolnikov and Dshalalow [2], who show that its probability generating function L(~) (z) = Ei[zSv], satisfies L(~)(z)= where the operator ~

z

N,,-,g-i-l {

a(z)~la(x) } :a x)l

'

i 0, by :D~ (.) = Ik. lim Ok

(')"

(2)

Control Policy

573

THE PROCESS {Q~}. Let Va denote the number of customer arrivals during the service time of the n TM batch. Since Su-F V n + l - r , Q~ < r, (3)

Qn+l-=

QnwVn+l-r,

Qn>_r,

then the process {Q~} is a Markov chain. Denote by lim P{Q~ = i},

p~ -

(4)

the steady-state probability (when it exists) of state i, by Pn(z) = E[zQ~], the probability generating function of Qn. Also, let F(z) = E[z y~] = B*(£ -Aa(z)), let U = {0, 1,... , r - 1} and let Iv(.) denote the indicator function of set U. THEOREM 1. The Markov chain {Qn} is ergodic if and only if p :----

a)~b < 1. ?-

(5)

Its probability generating function P(z) = limn-~o¢ P~ (z) is given by

z ~ TC(r,g). T h a t is, (21)

N* (r) = min {N > 11 1(~, N) > 0}, where

I (r, N) = TC (r, N + 1) - TC (r, N). A numerical experiment based on (21) can convince us that the expected cost function is convex. We summarize the procedure to find the optimal values (r*, N*) as follows. Step 1. Set r = 1. Determine N*(r) using (21) and compute TC(r, N*(r)) using (20). Step 2. Compute N*(r + 1) using (21) and TC(r + 1 , N * ( r + 1)) using (20). Step 3. If TC(r + 1, N*(r + 1)) > TC(r, N*(r)), STOP. The optimal values are (r*, N*) = (r, N*(r)). Otherwise, G O T O Step 2. 4. NUMERICAL

RESULTS

In order to illustrate the above solution procedure, some examples are presented through MATLAB program. For the MX/Gr/1 queueing system, we first assume that the service time follows an exponential distribution with mean b -- 0.5 and arrival batch size has a geometric distribution with parameter p = 0.4. Other parameters value are considered as Ch = 10, Co = 200, c8 = 10000, % = 200, and A = 0.2. The expected cost TC(r, N) is demonstrated in Figure 1 for various values of r and N. We can see that a minimum value cost per unit time of $355.226 is achieved at r* = 10 and N* = 10. .,.-.. ...,"

,.

. . . " ' "

~"

:: " x ~ " ~ " ~

5000. /l!!II ,~, 4000~

~s00o. 2000.

!

~ .

I\

...~....... • :

~:

i ~ . . . ....

•

i .......... :

~',~ "

"

......... 30

"

"

:

:

':,~ ~",~:\:~ : ~ ~,~ ,':L~, "~. [!~.......!-"

....

0 40

..--"

~" ~

~5

. .......... ...':"

iii=i;!~ !

1000.

["...

c:=-10; ~'-200, cs =10000,.¢.~-2~0 k---O,2, " . . . ........ ' . . . n q .,.." p '. Geo(O,4).arrii,al batch size, an~ ! ...... i ""....

..,.'"

............

,.:

•"

,.. . . . .-. .". .

.....

~ ..'":'-

.

"..

: /, "...

'-.

"ii

:.....

....... ::

::: .... ...... i:

...... ":!.....

::........ ....

"

'""-~

":.... . . . . . . """ :, • .........

10

"-

i

' i"

i

....... i

:

"' •

"'.....: """..

10 0

:

..

! ........ i

" ', •

..

. ..... ':'.

'..,.

::,-:.

".. 'L

!...........

-~......

: .

.... :

.... i

~ : . - ~

.....i .....

...... :

:

::

i

0

Figure 1. The expected cost TC(r, N) for different values of r and N.

:

": 40

Control Policy

577

Table 1. The optimal values (r*, N*) and its minimum expected cost TC(r*, N*) for various values of (A, b) when arrival batch size is Geo(0.4) and service time is E4. (A, b) Case 1 Case 2 Case 3

Case 4 Case 5 Case 6

(r*, N*)

TC(r*,N*) (r*, N*) TC(r*, N* ) (r*, g * )

TO(r*, N*) (r*, N*)

TC(r*,N*) (r*, N*)

TC(r*, N*) (r*, N*)

TC(r*, N*)

(0.4, 0.25)

(0.8, 0.25)

(1.0, 0.25)

(0.6, 0.5)

(0.6, 0.25)

(0.6, 0.125)

(4, 8) 256.903

(3, 8) 307.009

(2, 7) 322.301

(2, 6) 271.431

(4, 9) 285.136

(4, 9) 286.677

(4, s)

(3, s)

(2, 7)

(2, 6)

(4, 9)

(4, 9)

356.903 (7, 19) 619.695 (3, 6) 434.274 (6, 15) 822.850 (4, 10) 1127.135

407.009 (7, 22) 761.823 (2, 5) 505.237 (6, 17) 1031.197 (5, 13) 1431.813

422.301 (7, 23) 816.235 (2, 5) 529.518 (6, 18) 1109.614 (5, 14) 1545.218

371.431 (2, 11) 683.022 (2, 5) 455.901 (2, 9) 899.915 (2, 7) 1223.634

385.136 (7, 21) 697.988 (2, 5) 474.956 (6, 16) 937.948 (4, 11) 1297.038

386.677 (7, 21) 701.486 (4, 8) 480.986 (7, 18) 943.587 (6, 14) 1304..876

Table 2. The optimal values (r*, N*) and its minimum expected cost TC(r*, N*) for various values of (A, b) when arrival batch size is Geo(0.4) and service time is//2.

(J,,b) Case 1 Case 2 Case 3 Case 4 Case 5 Case 6

(0.4,0.25)

(r*,N*)

TC(r*, N*) (r*, N*) TC(r*, g*) (r*,N*) TC(r *, N*) (r*,Y*) TO(r*, Y*) (T*,lv*) TC(r*, N*) (r*,N*) TC(r*, N*)

(4,8) 257.382 (4,8) 357.382 (7,19) 620.001 (3,6) 435.480 (6, 15) 823.531

(4, 9) 1590.279

(0.8, 0.25) (3,8)

(1.0,0.25) (2, 7)

(0.6, 0.5) (2,6)

309.536 (3, 8) 409.536 (7,22) 763.090 (2, 5) 512.936 (6, 17) 1033.996 (4, 10) 2040.818

328.688 (2, 7) 428.688 (7,23) 818.247 (3, 7) 541.660 (6,18) 1114.027

274.373 (2, 6) 374.373 (2,11) 682.730 (2, 5) 462.649 (2,9) 902.218

(2,6)

(2, 7) 2210.619

1726.604

(0.6,0.25)

(0.6,0.12~)

(4, 9) 286.224 (4, 9) 386.224 (7,21) 698.685 (3, 6) 477.988 (6, 16) 939.503

(4,9) 287.284 (4, 9) 387.284 (7,21) 701.875 (3, 6) 481.436 (7,18) 944.355 (5, 11) 1851.411

(4, 9) 1838.841

A numerical illustration of the sensitivity analysis on the o p t i m u m joint thresholds r* and N* based on changes in specific values of system p a r a m e t e r s is c o n d u c t e d in the following different cost cases. Case1 :

Ch = 10

co = 100,

cs = 1000,

and

cp = 100.

Case2 :

Ch = 10

co = 200,

cs = 1000,

and

% -- 200.

Case3 :

Ch =

10

co = 200,

c8 = 10000,

and

cp = 200.

Case4 :

Ch -~ 20

co -- 200,

c8 -- 1000,

and

cp = 200.

Case5 :

Ch ---- 2 0

co = 200,

cs = 10000,

and

cp ----200.

Case6 :

Ch = 80

co = 200,

cs = 10000,

and

% = 200.

T h e o p t i m a l values and the m i n i m u m expected cost for the above six cost cases are s u m m a r i z e d in Tables 1 and 2 for various values of (A, b). T h e numerical evaluations in Tables 1 a n d 2 used four-stage E r l a n g (E4) a n d two-stage hyperexponential (/-/2) service times, respectively, and the arrival b a t c h size is a G e o ( 0 . 4 ) . For the c o m p u t a t i o n s of H2, we choose ql = 0.75 and q2 = 0.25. T h e numerical results in Tables 1 and 2 show t h a t (i) T C ( r * ,

N*)

increases as A increases, and

578

L. TADJ AND J.-C. KE Table 3. The optimal values (r*, N*) and its minimum expected cost TC(r*, N*) for various values of (A, b) when arrival batch size is U[1, 4] and service time is E4. (A, b)

Case 1 Case 2 Case 3 Case 4 Case 5 Case 6

(r*,N*) TC(r*, N*) (r*, N*)

TO(r*, N* ) (r*, N*)

TC(r*, N*) (r*,N*)

TC(r*, N*) (r*, N*)

TC(r*, N*) (~*,N*) TC(r*, N*)

(0.4, 0.25)

(0.8, 0.25)

(1.0, 0.25)

(0.6, 0.5)

(0.6, 0.25)

(0.6, 0.125)

(3,7) 239.934 (3, 7) 339.934 (5, 17) 586.822 (3,6) 407.183 (6, 15) 756.977 (4,8) 1438.062

(4,9) 287.689 (4, 9) 387.689 (6, 21) 714.712 (3,7) 475.961 (4, 14) 966.548 (4, 10) 1848.646

(4,10) 304.901 (4, 10) 404.901 (6, 21) 765.361 (2,6) 498.882 (5, 17) 1038.140

(2,6) 255.939 (2, 6) 355.939 (5, 17) 650.097 (2,5) 434.063 (2, 9) 856.709 (2, 6) 1570.218

(4,9) 266.473 (4, 9) 366.473 (6, 20) 657.555 (3,6) 444.810 (4, 13) 880.751 (4,9) 1666.864

(4,9) 267.264 (4, 9) 367.264 (6, 20) 657.117 (3,6) 447.738 (4, 13) 889.024 (4,9) 1680.046

(4,1o) 2007.365

Table 4. The optimal values (r*,N*) and its minimum expected cost TC(r*, N*) for various values of (A, b) when arrival batch size is U [, 4] and service time is H2. (A, b)

(0.4, 0.25)

(0.8, 0.25)

(1.0, 0.25)

(0.6,0.5)

(0.6,0.25)

(0.6, 0.125)

Case 1

(r*, g*) TC(r*, N*)

(4, 8)

(4, 9)

(4,10)

(2,6)

(4,9)

(4, 9)

239.068

289.290

309.186

(r*, N*) TC(r*, g*)

(4, 8) 339.068

(4, 9) 389.290

(4, 10) 409.186

267.237 (4,9) 367.237 (6,20) 657.885 (3,6) 447.676 (4, 13) 883.205 (4,9) 1672.612

267.529

Case 2

258.832 (2,6) 358.832 (5,17) 649.786 (2,5) 440.971 (2,9) 858.051 (2,6) 1593.288

Case 3 Case 4 Case 5 Case 6

(~*, g*) TC(r*, N*) (r*,N*) TC(r*, N*) (r*, N*)

TC(r*, N* )

(5,17)

(6, 21)

(6, 21)

587.012 (3,6) 408.423 (6, 15) 757.238

714.856 (4,8) 480.196 (4, 14) 970.546

765.872 (3,7) 508.011 (5, 17) 1041.787 (5, 12) 2031.791

(r*, N*)

(4,8)

(4,10)

TC(r*, N*)

1429.523

1874.098

(4, 9) 367.529

(9, 23) 633.042 (4,8) 448.925 (4, 13) 890.835 (4, 9) 1681.752

(ii) (r*, N * ) decrease as b increases for any case. Moreover, from Tables 1 and 2, we can find t h a t N* increases as cs increases (see Cases 2-5) or

Ch decreases (see Cases 2 and 4, Cases 3 and 5, Cases 5 and 6). In Tables 3 and 4, we s u m m a r i z e the o p t i m a l values and the m i n i m u m e x p e c t e d cost for the above six cases and for various values of (A, b). T h e arrival b a t c h size is a s s u m e d to follow U[1,4] where U[1, 4] represents the discrete uniform distribution on [1, 2] and service t i m e is a s s u m e d to follow E4 a n d / / 2 distributions, respectively. T h e numerical conclusions of Tables 3 and 4 are the s a m e as Tables 1 a n d 2 for geometric arrival b a t c h size. O u r numerical investigations indicate t h a t (i) t h e o p t i m a l values (r*,N*) and the m i n i m u m e x p e c t e d cost TC(r*,N*) are slightly changed in service time distribution when p a r a m e t e r values (A, b) are given, and (ii) ch and cs have a much significant effect on (r*, N * ) t h a n co and Cp do.

5. C O N C L U S I O N S In this paper, we have studied the M X / G r / 1 queueing s y s t e m with batch-arrival and bulkservice under bysteretic policy. T h e probability generating functions for the s t e a d y - s t a t e were derived in b o t h discrete time and continuous t i m e p a r a m e t e r . Some s y s t e m characteristics were

Control Policy

579

obtained by means of the two probability generating functions. Although the unimodality or convexity of the expected cost function can not be proved theoretically in this study, we present a finite and quick search for the optimal joint thresholds. We also performed a sensitivity analysis a m o n g the optimal value of (r, N), the specific values of system parameters, and cost elements.

REFERENCES 1. L. Tadj and J.-C. Ke, Control policy of a hysteretic queueing system, Mathematical Methods o/ Operations Research 57 (3), (2003). 2. L. Abolnikov and A. Dukhovny, Markov chains with transition delta-matrix: Ergodicity conditions, invariant probability measures and applications, Journal of Applied Mathematics and Stochastic Analysis 4 (4), 335355, (1991). 3. L. Abolnikov and J.H. Dshalalow, A first passage problem and its applications to the analysis of a class of stochastic models, J. App. Math. Stoeh. Anal. 5, 83-98, (1991). 4. R.E. Bellman, Dynamic Programming, Princeton University Press, (1957).