Control Policies for the Mx/G/1 Queueing System Hyo-Seong Lee M. M. Srinivasan Department of Industrial and Operations Engineering The University of Michigan, Ann Arbor 48109-2117 Technical Report 87-20 September 1987

Abstract The MX/G/1 queueing system is studied under the following two situations: (1) At the end of a busy period, the server is turned off and inspects the length of the queue every time an arrival occurs. When the queue length reaches, or exceeds, a pre-specified value m for the first time, the server is turned on and serves the system until it is empty. (2) At the end of a busy period, the server takes a sequence of vacations, each for a random amount of time. At the end of each vacation, he inspects the length of the queue. If the queue length is greater than, or equal to, a pre-specified value m at this time, he begins to serve the system until it is empty. For both cases, the mean waiting time of an arbitrary customer for a given value of m is derived, and the procedure to find the stationary optimal policy under a linear cost structure is presented.

L Introduction In many real queueing systems, requests for service usually arrive in batches. For example, in manufacturing systems of the job-shop type, each job order often requires the manufacture of more than one unit; in computer communication systems, messages which are to be transmitted could consist of a random number of packets. When a cost structure is superimposed on such batch arrival systems, obtaining an optimal control policy under the given cost structure is very important. However, while a considerable amount of work has been done on control policies for queueing systems without batch arrivals, comparable work for the batch arrival case is rarely found in the literature. This motivates us to develop control policies for queueing systems with batch arrivals. We consider an MX/G/1 queueing system, where requests for service arrive to the system according to a Poisson process. Each request consists of a number, X, of units where X is an independent and identically distributed random variable. The units within a batch are served one at a time by a single server. The service time for an individual unit is independent and identically distributed. In this paper, we consider control policies for the following two situations. (a) Every time an arrival occurs, the server inspects the state of the queue. If the total number of units is found to have reached or exceeded a pre-specified value m, he takes a random amount of time to start up the system. Following this, the server begins to serve the queue until the system is empty. As soon as the system becomes empty, the server 1

is turned off and remains idle until the accumulated number of units reaches or exceeds m for the first time. (b) In this case, when the server finishes service and finds the system empty, he takes a vacation for a random amount of time. At the end of the vacation, the server determines the number of units present in the queue. If the queue length at that time is below m, he immediately takes another vacation. On the other hand, if the queue length is greater than, or equal to m, he takes a random amount of time to start up the system.. He then begins to serve the system until it is empty. It is to be noted that while the queueing system in (a) is continuously monitored, the system in (b) is monitored only at the times each vacation ends. In this paper, we refer to the policy in (a) as the m-policv without vacation and the policy in (b) as the m-policv with vacation. In these systems, it is assumed that there is a cost incurred each time the server is turned on, and that there is a cost incurred for every unit of time a unit waits for service. For both these policies, we obtain the mean waiting time of an arbitrary unit for a given value of m and find the stationary optimal m-policy which minimizes the expected cost in the long run, under this cost structure. 2. Previous Work As mentioned earlier, a considerable amount of work has been done on control policies for the M/G/1 queueing system without batch arrivals. Most of these studies present some special policies and derive the optimal 2

stationary policies under certain cost structures. Among them, the N-policy studied by Yadin and Naor[17], Heyman[8], Sobel[16] and Bell[4] is one of the earliest. In this policy, the server is turned on when the total number of units reaches N and turned off when the system becomes empty. Heyman[9] also considered the T-policy where the server is turned off at the end of each busy period and inspects the state of the queue after an interval of length T. If at least one unit is found awaiting service, a busy period begins and the units are served until the queue is exhausted. If there are no units found at the time of inspection, the server again inspects the queue after another interval of length T. Heyman showed that under a linear cost structure the optimal N-policy is superior to the optimal Tpolicy. Balachandran[2] and Balachandran and Tijms[3] proposed the Dpolicy in which the server is turned off at the end of a busy period and turned back on when the cumulative service time of the waiting units exceeds some fixed value D. They also showed[3] that under a linear cost structure the D-policy is superior to the N-policy for the service time distributions with decreasing, constant, and for some cases, increasing failure rates. Hofri[10] studied the control policy for the M/G/1 system in which the server takes a sequence of vacations at the end of busy period, inspecting the state of the queue at the end of each vacation. When the queue length exceeds a predetermined level m, the units are served until the system 3

becomes empty. Furthermore, he considered a control policy for the system where two queues are served by a single server. It is important to note that all these studies fall under the class of server vacation models for the M/G/1 queueing system, which have been extensively studied by Levy and Yechiali[12], Fuhrmann and Cooper[7], Scholl and Kleinrock[15], and Levy and Kleinrock[11], to name but a few. The m-policy in this paper extends the work on control policies to the situation where arrivals occur according to a discrete compound Poisson process and a start-up interval is allowed which takes a random amount of time. When the batch size is 1 and the start-up interval is zero, our mpolicy without vacation reduces to the N-policy model of Heyman, and our m-policy with vacation reduces to the vacation model studied by Hofri. In the case of batch arrivals, it is also possible to adopt a policy that uses information on the number of batches, instead of the total number of individual units in deciding whether the server is activated or not. This policy, which we will term as the n-policv in this paper, is described as follows: (1) n-policy without vacation At the end of a busy period, the server is turned off and begins to count the arrivals as and when they occur. When the total number of arrivals reaches a pre-specified value n, the server takes a random amount of time to start up the system. He then begins to serve the queue exhaustively. 4

(2) n-policy with vacation At the end of a busy period, the server takes a sequence of vacations. At the end of each vacation, the server counts the number of batches that have queued up for service. If the total number of batches at this time equals to or exceeds a pre-specified value n, the server takes a random amount of time to start up the system, and then begins to serve the queue exhaustively. Otherwise, the server immediately takes another vacation. If the n-policy is adopted, the mean waiting time of an arbitrary unit for a given value of n is obtained by treating a batch as if it were a single unit, i.e., (1) find the mean waiting time of a typical batch and (2) add to it the mean waiting time of a test(arbitrary) unit within a batch. This technique, however, cannot be applied to the m-policy since the m-policy uses the information about the individual units instead of batches. Therefore, known results by previous authors cannot be directly applied to the m-policy. This fact has led us to devise a different approach to obtain the mean waiting time experienced by an arbitrary unit in the m-policy. In section 7, the m-policy and the n-policy will be compared and it will be shown that the optimal m-policy is superior to the optimal n-policy under a linear cost structure. 3. The Approach Requests arrive in batches according to a stationary Poisson stream with rate X. Let X denote the number of units in a batch, where X is a random variable (r.v.) with a known discrete distribution. The service time 5

of a typical unit is denoted by S and we assume that S has a finite second moment. Since we are only interested in the first moment of the waiting time, the service discipline is not & matter of concern to us. However, for analytical convenience, we assume that service is done in a First In First Out (FIFO) manner. We define some terms which will be used in the analysis. Primary units are defined to be units which arrive either while the server is turned off, or is being started up, and secondary units are those which arrive while the server is busy. We define a cycle to be the period that elapses from the end of a busy period till the end of the next busy period. In order to analyze the system, we divide the cycle into the following three phases. Phase 1 begins when the server is turned off and lasts until the server has completed the start-up. Thus, phase 1 consists of two sub-periods: a dormant period during which the server is turned off and a start-up period during which the server is starting up the system. Note that the units which arrive during phase 1 are the primary units. Phase 2 begins when the start-up by the server is completed, and lasts until all the primary units are served. Phase 3 begins at the end of phase 2 and lasts until all the secondary units are served. Note that primary units arrive during phase 1 and are served during phase 2. Secondary units arrive during both phase 2 and phase 3, and are served during phase 3. 6

Our general approach to obtain the mean waiting time experienced by an arbitrary unit in the m-policy is to analyze the mean waiting times of the primary and the secondary units seperately, and then to combine these results to yield the mean waiting time of an- arbitrary unit. To this end, let WP (Wi) be the mean waiting time of a primary (secondary) unit, and let p S NP (Nm) be the mean number of primary (secondary) units served in a cycle when we use m as a control value. Then the mean waiting time of an arbitrary unit, Wm, is obtained as NP WP + N W m m Nm m Wm= ~ - +Ns (3.1) m m To obtain WP in (3.1), we divide WP into two components, W and WP ), where W(') is the mean waiting time of an arbitrary primary unit in phase 1 and W'2) is its mean waiting time in phase 2. We obtain W(') and W(') in isolation and obtain WP as: WP =W(P,1)+W(p2) (3.2) m in in. (3.2) In the following sections, we develop the expressions for the terms W(p' W(' 2, W%, NP, Nm and the procedure to find the optimal m-policies with/without vacations. 7

4. m-Policy with Vacation In this section, we obtain the mean waiting time of an arbitrary unit in a system using the m-policy with vacation. In the m-policy with vacation, as explained in section 1, the server takes a sequence of vacations at the end of a busy period until the queue length reaches or exceeds m for the first time, at which point the start-up period begins immediately; as soon as the start-up is finished the server begins to serve the queue. For any discrete random variable, A, used in the analysis, we adopt the following notation: ai = P{A=i}, 00 A(z) = Xai zi, the probability generating function (p.g.f.) of A, i=O a(l) = E(A), a(2) = E(A(A-1)). Similarly, for any continuous random variable B used in the analysis, B(.) and B*(.) will denote the distribution function and Laplace-Stieltjes Transform(LST) of B respectively. We define V = vacation time, r.v., Q = number of batches that arrive during a vacation, r.v., U = start-up time, r.v., R = number of units that arrive during a vacation, r.v., Id,m = number of (primary) units that arrive during a dormant period, Is Im when m is used as a control value, r.v., = number of (primary) units arriving during a start-up period, r.v., = Id,m+Is = number of (primary) units present when the service begins, when m is used as a control value, r.v., 8

Ld,m = expected total waiting time of primary units during a dormant period, when m is used as a control value, Ls,m = expected total waiting time of primary units during a start-up period, when m is used as a control value, Lm = Ld,m+Ls,m = expected total waiting time of all the primary units in phase 1, when m is used as a control value, Id,m = expected length of dormant period, when m is used as a control value, Cm = 4d,m + E(U) = expected length of phase 1, when m is used as a control value, *(i) Xijs = P{i-fold convolution of X is j). From these definitions, the following relationships are obtained: a) By definition, 00 oo qi= J -t dV(t). (4.1) 0 However, for the computation of qi, we use the following equivalent expression: qi = i-V*(i)(), (4.2) where V*(i)() is the ith derivative of the LST of V with respect to 0. b) The probability that j units arrive during a vacation is given by J *(i) rj= qixj, j=0,1,2,.... (4.3) i=O We also present a lemma that will be useful for computing the moments of R, and for obtaining the pgf of Id,m: 9

Lemma 4.1. The probability generating function of R is given by R(z) = V*(X-X(z)). (4.4.a) Is(z) = U*(X-XX(z)). (4.4.b) (proof) By definition of the p.g.f., 00 R(z) = S rjz j=o 00 j *(i) C I qix zJ j=Oi=O 00 00 *(i) I qi x' zJ i=o j=i 00 = qiX(z))i i=O = Q(X(z)). Noting that Q(z) =V*(X-Xz), the result follows. Equation (4.4b) is proved in a similar manner. U From lemma 4.1, by differentiating R(z) and Is(z) with respect to z, we can obtain the first and second factorial moments of R and Is as: r(l) = E(R) = XE(V)x(l), (4.5.a) r(2) = E(R(R-1)) = (Xx(1))2E(V2) + Xx(2)E(V), (4.5.b).(1) i( = E(Is) = XE(U)x(l), (4.5.c) is = E(I(Is-1)) = (x(1))2E(U2) + Xx(2)E(U). (4.5.d) (P,1) 4.1 Computing the term W:.(1) Suppose we have available the values of Lm and i(m Then, the mean waiting time of a primary test(arbitrary) unit in phase 1 is obtained as 10

W(P,1) Lm (4.6) W^ ^.( (4.6) 1m.(1).(1). (1) The term im consists of two terms, i() and i. In order to obtain id m, we need to find the p.g.f. of Id,m. The following result, stated as Theorem 4.1 expresses the p.g.f. of Id,m. A proof of Theorem 4.1 is given in the Appendix. Theorem 4.1. R(z)-ro Id,m(Z) = z {Id,mj(z)-l} + 1-r0 m=1,2,... (4.7) j=1 Using Id,m(z) we obtain the first and second factorial moments of Id,m. The (2) second moment of Id,m will be used to calculate im..(1) I m-1.() 11 ) d m = E(Id,m) = rjid m-j + l-r m =1,2,.... (4.8.a) *(2) 1 -.(1).(2) r(2) d m = E(Id,m(Id,m-l)) =-r rj(2j id m- + id m-) + 1 m = 1,2,.... j=1 (4.8.b) Since the number of units which arrive during the start-up period is independent of the number of units which arrive during the dormant period, the following relationship holds: Im(z) = Id,m(z)Is(z). (4.9) By differentiating Im(z) with respect to z, we obtain the first and second factorial moments of Im(z) as: (1). + i (4.1.a) 1m = -dm + Is, (4.10.a) 11

.(2).(2).(2).(1).(1) m = ldm + is +2 dmls, (4.10.b).(1) (2) where is and is are obtained from equations (4.5.c) and (4.5.d). Now the term im can be obtained from (4.10.a). To compute the term Lm which is needed in (4.6), we first obtain the term Ld,m and then obtain the term Ls,m. In order to compute the term Ld,m, we require the following lemma. Lemma 4.2: Consider all the units that arrive during the first vacation. Let co denote the total waiting time experienced by these units during this vacation. Then its expected value, E(co) is given by E(co) =x) x E(V2). (4.11) (proof) Lemma 4.2 is proved using the following simple argument. 1) If we take an arbitrary unit which has arrived during the first vacation, its mean waiting time during the first vacation is the expected residual E(V2) life time of a vacation, i.e.,2E(V) 2) The expected number of units which arrive during the first vacation is XE(V)x(1). 1 The product of terms 1) and 2) yields E(o) = xl X E(V2). The term, Ld,m, is then obtained from the following recursive relation: m-1 Ld,m = E(co) + rrj(j d,m-j+Ld,m-j), m=1,2,. (4.12) j=o The explanation of equation ( 4.12) is as follows: For any value of m, the m-policy must have at least one vacation during the dormant period. Therefore, Ld,m is represented by the expected total 12

waiting time during the first vacation plus the expected total waiting time from the second vacation onwards until the end of dormant period. In (4.12), the first term expresses the expected total waiting time during the first vacation for all the units that arrive during this vacation and the second term expresses the expected total waiting time from the second vacation onward until the end of dormant period. The expression for the second term is based on the following reasoning: 1) If the number of units that arrive during the first vacation is more than or equal to m, dormant period ends as soon as the first vacation finishes and there is no further waiting in dormant period. 2) Suppose j units arrived during the first vacation. The probability that j units arrive during the first vacation is rj. If j is less than m, each of these j units must wait for 41,m-j on the average from the beginning of the second vacation onward until the end of dormant period. Noting that the expected total waiting time of the units that arrive from the second vacation onwards is Ld,m-j we get the second term of equation (4.12). If we solve equation (4.12) for Ld,m we obtain 1 1 m-l Ldm = -o({x(l)XE(V2)+ y rj(j 4d,m-j+Ld,m-j), m=1,2,, (4.13) j=1 0 where A is defined to be 0. j=1 The term, ld,k, which is needed (for k=1,2,w..,m-1) in equation (4.13), can be obtained by the following forward-type recursive equation. 13

k-1 d,k = E(V) + E rj d,k-j, k=l,2,..... (4.14) j=O The first term of equation (4.14) represents the fact that at least one vacation is needed for any value of m used in the m-policy. The second term of equation (4.14) is obtained using the fact that if the number of units which arrive during the first vacation is less than k, say j, the expected remaining length of dormant period is 4d,k-j, and also the probability that j units arrive during the first vacation is rj. If we solve equation (4.14) for ld,k, we obtain 1 k-1,k = r {E(V)+ Z rj d,k.j}, k=1,2,... (4.15) j=i 0 where, again, Z is defined to be 0. j=l Now that we can calculate the term Ld,m, the only remaining unknown needed to obtain W(') is Ls,m, which is obtained by the following equation. Ls,m = d m E(U) + 2 (4.16) In equation (4.16), the first term represents the expected total waiting time of the units during the start-up period which are already present at the beginning of that period. The second term represents the expected total waiting time for the units which arrive during that period. The second term is obtained using an approach similar to that used to obtain equation (4.11). 14

Now Lm is determined by summing Ld,m and Lsm, and im is obtained from equation (4.10.a). Thus we can finally calculate W') using equation (4.6). Remark 1 From a computational point of view, qi is easily obtained from equation (4.2) if V*(.) is a well defined differentiable function. On the other hand, we may have trouble calculating rj if j is large since calculation of gj is usually cumbersome if i is large (refer equation (4.3)). However, from a practical point of view, we can always calculate rj to the desired level of accuracy for the following reasons: 1) If the value of m used in the m-policy is not so big, we can calculate all the necessary rjs without difficulty since only ro,r," —,rm.l are needed to obtain W(. 2) Considering that qi converges to 0 very fast and xj is always less than or equal to 1, we can calculate rj using equation (4.3) by truncating the summation after k terms are summed up if qk=O for some k<j. 4.2. Determining W (p: We are now in a position to find W(,2) the mean waiting time of the primary test unit in phase 2. Let I be the number of primary units in a cycle that contains the test unit. Then, Wm') is obtained by the following equation (see, for example, Cooper[6]): W;2)= E(WV'2) I =j) P(I=j) (4.17) j=m 15

where P = P jj P{Im=j). P(I =j) (4.18) lm and ECW('2) I I=j) E(S). (4.19) Substitution of (4.18) and (4.19) into (4.17) yields.(2) i(P,2) (4.20)E(S).(1) (4.20) 21m 4.3. Determining Wm: To determine the mean waiting time for secondary units it is first noted that their waiting time in the system occurs only during phases 2 and 3. Further, note that as far as these units are concerned, phase 2 represents a'vacation' period during which the arriving secondary units find the server busy attending to primary units. Phase 3 then represents a busy period for these secondary units. Let Tm represent the duration of phase 2, which is the pseudo-vacation (for the secondary units). We first determine the first and second moments of Tm. For this, note that Tm is a sum of the service times of the primary units, and can be expressed as: Tm = Sl+S2+'"+SIm. The LST of Tm is then given by * 00 TM(0) = I {S*(0)}k P{Im=k) k=m 16

= Im(S*(O)). (4.21) By differentiating (4.21), we obtain E(Tm) = i()E(S), (4.22) E(T2) = i(2)(E(S))2+ )E(S2). (4.23) Having determined the first and second moments of Tm, we can now obtain WSm using Lemma 4.3. Lemma 4.3. Consider an MX/G/1 server vacation model where the server begins a vacation of random length T each time the system becomes empty. If the server finds at least one unit at the end of a vacation, he begins to serve the units until the queue is empty. If the server finds no units waiting at the end of the vacation, he takes another vacation immediately. The arrival rate, batch size and service time for an individual unit are assumed to follow our general notations. Then, the mean waiting time, W, for an arbitrary unit is given by E(T2) Mx(1)E(S2) + x(2) (E(S))2} E(S)x(2) W= 2E(T)+ 2(1-p) +2x(1) (4.24) where p=x(1)E(S). U Remark 2 Baba obtained equation (4.24) using a supplementary variable technique in [1]. However, equation (4.24) can be obtained directly if we combine the decomposition property of Furmann and Cooper[7] for the M/G/1 system with server vacation and Burke's method[5] to obtain the expected waiting time for the MX/G/1 system. That is, we first treat a batch as if it were an individual unit. Then by the decomposition property of the 17

M/G/1 server vacation model, the mean waiting time for a typical batch is expressed as the sum of the mean residual life time of a vacation plus the mean waiting time of a typical batch in the corresponding standard M/G/1 system. Then, using Burke's method, the mean waiting time of a test unit is obtained by adding the mean waiting time of a test unit within a batch to the mean waiting time for a typical batch. Therefore W consists of the following three independent components: the mean residual life time of a vacation, the mean waiting time of a batch in the corresponding M/G/1 system and the mean waiting time of the test unit within a batch. Each of these three components is represented by the first, second and the third terms of equation (4.24) respectively. U Substituting Tm in place of T in Lemma (4.3), and using equations (4.22) and (4.23), we obtain WSm as: E(T2) {x(l)E(S2) + x(2) (E(S))2} E(S)x(2) m 2E(Tm) 2(1-p) 2x() which can be rewritten, after some elementary algebra, as.(2) im {x(1)E(S2) + x(2) (E(S))2}. E(S)+. (4.25) - (1i) ES+2p(1-p) 4.4. Determining N and NS: It is clear that, NPm = i. (4.26) 18

To obtain Nm, we again treat a batch as if it were a single unit. Let Y be the number of batches that arrive during phase 2. Then, the length of phase 3 becomes a sum of Y independent busy periods of an M/G/1 queue. Applying the well known fact about the number of units served during the busy period of the M/G/1 queue, the expected number of batches served during phase 3 is E(Y)/(1-P) where E(Y)=XE(Tm). Since Nm is the expected number of units served during phase 3, it is expressed as s XE(Tm)x(1) N =1 1-P and using equation (4.22), this simplifies to s P.(1) N= Im. (4.27) m 1-p From equations (4.26) and (4.27), equation (3.1) reduces to Wm = (1-)WP + pWm. (4.28) Finally from equations (4.6), (4.20), (4.25) and (4.28), we obtain an expression for Wm, stated as Theorem 4.2: Theorem 4.2: The mean waiting time, Wm, for the m-Policy MX/G/1 queueing system with vacations is given by.(2) Lm im l {x(1)E(S2) + x(2) (E(S))2) Wm = (1-p).7 + E(S) + (4.29) m 2m U 19

Remark 3 As we see in equation (4.29), Wm consists of three terms which represent, respectively, the mean waiting time of a primary unit in phase 1 multiplied by l-p, the mean waiting time of a primary unit in phase 2, and the mean waiting time of a batch in the corresponding M/G/1 system. Since the fraction of primary units is l-p, the sum of the second and third terms of (4.29) represents the mean waiting time of an arbitrary unit after service begins, which is completely determined by the first and second moments of the number of primary units. U Let the busy period, which is the sum of phase 2 and phase 3, be denoted by Bm and let the LST of Bm be denoted by Bm(O). It has been shown [1,13] that LST of the busy period initiated with 1 unit in the system, B*(O), can be expressed by B*(O) = S*(+X-XX(B*(0))), (4.30) and that the LST of the busy period initiated with k units in the system is expressed by (B*(9))k. Therefore, the LST of the busy period in the m-policy is 00 Bm(O) = X P{Im=j)(B*(O))J j=m = Im(B*(6)). (4.31) From (4.30), we obtain the mean busy period initiated with 1 unit in the system as E(S) E(B)- E() (4.32) (l-p) By differentiating (4.31) with respect to 0 and using (4.32), we obtain the expected length of a busy period in the m-policy as im E(S) E(Bm) = (4.33) 1-p 20

.(1) 1m It can easily be shown (refer Property 4 in Section 6) that i = Xx(1) Using this result, the mean length of a cycle in the m-policy is then expressed as.(1) im f + E(Bm) = ( (4.34) (l-p)hx(1) Let the number of units served in a busy period initiated with 1 unit in the system be M and let the pgf of M be M(z). Then it is easy to show that M(z) = z S*(X-X(M(z)) (4.35) If we denote the number of units served in a busy period in the m-policy by Mm and its pgf by Mm(z), Mm(z) can be expressed as 00 Mm(z) = P{Im=j)(Mm(z))i j=m = Im(M(z)). (4.36) By differentiating (4.36) with respect to z, we obtain the mean number of units served in a busy period (or in a cycle), Nm, as:.(1) 1m Nm = (4.37) l-p Note that equation (4.37) can be also obtained from equations (4.26) and (4.27), using the fact that Nm = Nm + Nm. 5. m-Policy without Vacation The general approach used to obtain Wm for the case of the m-policy without vacation is basically similar to that outlined in the case of the mpolicy with vacation. Most of the equations used in the m-policy with vacation still hold and are used in the exactly same way. However, the 21

s(1) *(2) expressions for Id,m(z), id m, d m,Ld,m and 4d,m are different from those in the m-policy with vacation model. In this section, we obtain these alternate expressions..(1),(2) The probability generating function of Imr which yields id m and id m, is expressed by the following theorem. Theorem 5.1 m-1 Id,m(Z) = xjzJ{Id,m-j(z)-l) + X(z), m=1,2,.... (5.1) j=1 A proof of Theorem 5.1 is given in the Appendix. From (5.1), the first and second factorial moments of Id,m are obtained as nm-l.(1) m ld m - C xj Id m-j + x(1), (5.2) j=1.(2).- A(1) (2) Id m = j(2j d m-j + id m-j) +x(2), m=1,2,.... (5.3) j=1 The expected total waiting time in dormant period, Ld,m, is obtained by conditioning on the first arrival. Suppose the number of units in the first batch is j. If j exceeds m, dormant period ends upon the occurrence of the first arrival so that there is no waiting in dormant period. If j is less than m, these j units must wait for the length of 4d,m-j on the average and the expected total waiting time of the (primary) units, excluding these j units, is Ld,m-j. The term Ld,m can be obtained, therefore, by the following recursive equation 22

m-1 Ld,m = Xj(j Id,m-j+Ld,m-j), m=1,2,. (5.4) J=1 0 where Ld,l=O and, is defined to be 0. j=1 The terms (d,k, for k=l,...,m-1, in equation (5.4), is obtained from 1 k-1 l,k = -+ xj fd,k-j, k=1,2,. (5.5) h j=1 It is easy to see that we can obtain equation (5.5) by a similar argument as.(1).(2).(1).(2) was used to obtain equation (4.14). To obtain i, is, i m, m Ls,m and Lm we use the same equations as in the m-policy with vacation. If we substitute i( and Lm into (4.6), we obtain W('. To obtain WM(), Wm Np and Nm, we just follow the same procedure as described in section 4 using, however, the.(1) (2) new expressions for Lm, im and im derived above. 6. Optimal Design of the m-Policy In this section, we find the value of m which produces the optimal stationary m-policy. We assume that a start-up cost of cs is incurred each time the server is turned on and that a linear holding cost of ch per unit time is incurred for each unit that waits in this system. To obtain the optimal m policy, we first obtain the expected cost per unit for a given value of m, and then find the value of m which minimizes this cost. Since the expected number of units served during a cycle is Nm, the expected start-up cost per unit is expressed as. Similarly, the expected s -m` 23

waiting cost per unit is given by ChWm. From this, the expected (long run) total cost per unit, Cm, using m as a control value, is calculated as Cs Cm = m +ChWm (2) (1-p)cs { (l-p)Lm E(S)im Xx()E(S2) + x(2) (E(S))2}1 = (1E(S) + + +J(E(S))2 ch (6.1) im Im 2im Note that the last term is a constant and is independent of the policy adopted. Setting a = (1-p)cs, X{x(1)E(S2) + x(2) (E(S))2) P= -, - ^ - ch, 2(1-p) and 1 (2) hm = (l-p)chLm+ 2chE(S)i we can write Cm = Cm +, where the cost function, cm, is given by a+hm Cm=.(1) (6.2) im The terms 1m, im and Lm are all recursive in nature. For example, to.(1).(1) (1) obtain i( m which is needed to obtain im, all the terms id k, 0 < k < m have to be evaluated beforehand. Also note that once these terms are obtained, evaluating cm requires very little effort. Hence, in the process of evaluating Cm, we obtain all the information that is needed to quickly calculate cl, c2, 24

..., and Cm-1. In a sense, Cm is thus evaluated sequentially, starting with m=1. The recursive nature of the terms im) im, tm and Lm makes it very difficult to characterize Cm with regard to its convexity or unimodality. However, we now show that the function cm has a special characteristic which enables us to find a global minimum very efficiently. This characteristic is that, in the process of evaluating cm, m=1,2,..., the first local minimum encountered is the global minimum. This is stated below as Theorem 6.1. Before we state and prove this theorem, we develop some properties that the terms im, mi, n and Lm possess. These properties are not only used to prove Theorem 6.1 but are also used to significantly reduce the amount of computation required to obtain the terms i(2) and Lm. The proof of these properties are given in the Appendix..(1).(1) Property 1 n > in, for m>n, n=1,2,....... (6.3) Propertv 2 hm > hn, for m>n, n=1,2,....... (6.4).(2).(2).(2).(2) n - ia-1 l-n' lm-n-l.(1) Propert (1) (1) = (1) (1) + 2(1+i1 )n, for m>n, n=1,2,....... im' lm-1 im-n - im-n-1 (6.5) Im Proeretv4 (l)-.k, for all m, (6.6) im 1 where k= hX<'> 25

-Lm- Lm-1 Lm-n -Lm-n-1 Proertv 5.(1 (1) = - -+ (k+E(U))n, for m>n, n=1,2..... im 1m-1 im-n - im-n-l (6.7) where k is as defined in property 4. hm- hn+l hm - hn hmPropert 6 > ) ^, for m>n+l, n=1,2,....... (6.8) im - in+1 m - in Properties 1,2 and 6 are used to prove Theorem 6.1 and properties 3,4 and 5 (2) are used to calculate i'), ~m and Lm in a more efficient way. Also note that properties 1 and 2 imply that im and hm are both increasing functions with respect to m. Now we present the main result of this section, which gives a characteristic of the cost function, Cm. Theorem 6.1 If Ck+l > Ck, then Cn >ck for all n>k>0. Proof By contradiction. Suppose there exists an n such that n>k+l, and Cn < ck. Then the following inequalities hold: (i +hk+l a+hk (6.9.a) lk+1 lk a+hk a+hn (ii).(1) > (1) (6.9.b).(1) (i)'k in From (6.3), (6.4) and (6.9.a), we obtain: hk+l-hk (6.10) 1).(1) > Ck. (6.10) lk+l-lk 26

Similarly, from (6.3), (6.4) and (6.9.b), we obtain: a+hn hk+l-hn (6.11) (1) =Cn > (1).(1) (6.11) in 1k+l1k From (6.10), (6,11) and the assumption that Cn < ck, we get: hk+l-hk hn-hk+l.(1(1) 1) > (1).(1)12) 1k+lk in -lk+1 Noting that the numerator and the denominator are positive on both sides of the inequality given in (6.12), we can write: hn-hk hn-hk+l.(1).(1) >.(1).(1)' n -k in -k+1 which contradicts property 6. Thus, Cn > ck for all n>k. (2) Remark 4 In implementation, to calculate imy tm and Lm, we use properties 3,4 and 5 instead of using the recursive equations. Note that once.(1) (2) im is determined, im, m and Lm (and hence, cm,) are calculated easily using (6.5), (6.6) and (6.7). Thus, im (in fact i(d ) is the only term in which we must use a recursive method for the calculation. This reduces the computational effort significantly. The above remark, together with Theorem 6.1 produces an extremely simple, and fairly efficient procedure to obtain the optimal policy: sequentially evaluate cm, starting with m=1, until we encounter a point at which the cost function, cm, begins to rise. 27

Algorithm to find the optimal m-value 0. Set k=l. Compute ck. 1. Set k=k+l. Compute ck. 2. If ck>ck-1, stop. Optimal value of m is k-1. Otherwise, go to step 1. 7. Numerical Examples In order to verify the efficiency of our method and to show the superiority of the m-policy over the n-policy, we made extensive numerical tests. Some numerical examples are presented below, comparing the results of the m-policy with those of the n-policy. It is intuitively obvious that the optimal m-policy is superior to the optimal n-policy since the m-policy uses more information about the state of the queue than the n-policy. In fact, in all the problems we have tested up to date, the m-policy consistently performs better than the n-policy. Due to the complexity of the cost function, however, we could not prove this analytically. We present four examples below. Example 1 considers the m-policy without vacation and examples 2, 3, and 4 consider the m-policy with vacation. Also while examples 1 and 2 have no start-up times, examples 3 and 4 have start-up times. The vacation times in examples 2 and 3 are assumed to follow a uniform distribution and the vacation time in example 4 is assumed to follow an Erlang distribution.

<Example 1> =0.3, E(S)=1, E(S2)=1.8, x1=0.25, x2=0.25, x=0.25,x4=0.25, Cs=2000, Ch=3. <Example 2> X=0.3, E(S)=1, E(S2)=1.8, xi=0.2, x2=0.3, x3=0.3, x4=0.2, Cs=1000, ch=3, V follows a uniform distribution on [5, 10]. <Example 3> X=0.3, E(S)=1, E(S2)=1.8, x1=0.2, 2=0.3, x3=0.3, x4=0.2, E(U) = 5, E(U2) = 50, cs=1000, Ch=3, V follows a uniform distribution on [5, 10]. <Example 4> X=0.2, E(S)=1, E(S2)=3, x1=0.3, x2=0.3, x3=0.4, E(U) = 5, E(U2) = 25, cs=1500, ch=3, V follows a two stage Erlang distribution with mean 2. The results of the policy comparisons for these test examples are presented in table 1 through 3. In each table, the values of Wm and Cm are shown for each value of m in the m-policy. The results of the n-policy in the examples have been obtained by the technique which treats a batch as if it were a single unit. As shown in the tables, the optimal m-policy is better

than the optimal n-policy and the minimum points of the cost function Cm occur at the first local minimum points in all three examples. It might be thought that the optimal value of the m-policy should just be the optimal value of the n-policy multiplied by the expected batch size. As we see in tables 2 and 4, this is not necessarily true although in examples 1 and 3 this does happen to be the case. However, in many of the cases that were tested, these two values are observed to be fairly close. Finally, it must be stated that although only two distributions(uniform, Erlang) for the vacation are demonstrated in the examples, many other distributions can be easily implemented. 8. Conclusions We have introduced two control policies for the MX/G/1 queueing system: the m-policy without vacation which is used for the control of the ordinary MX/G/1 system and the m-policy with vacation which is used for the control of a queueing system where the server takes a sequence of vacations, possibly to do some other work at the end of each busy period. In both of these models, we allowed a start-up interval to represent real systems more accurately. For both policies, we obtained the mean waiting time of an arbitrary unit for a given value of m and developed an efficient procedure to find the stationary optimal m-policy using an important characteristic of ir the cost fction cmThe direct extension of the m-policy would be the control policy for the system with batch arrivals where one or more queues are served by a single server such as, for example, the model with two queues, studied by Hofri for the case of unit (non-batch) arrivals. 30

R erences [1] Baba, Y, "On the Mx/G/1 Queue with Vacation Time," Opns. Res. Letters, Vol. 5 (1986), pp. 93-98. [2] Balachandran, K.R., "Control Policies for a single server system," Mgmt. Sci., Vol. 21 (1975), pp. 1013-1018. [3] and Tijms,H.C., "On the D-Policy for the M/G/1 Queue," Mgmt. Sci., Vol. 21.(1975), pp. 1073-1076. [4] Bell, C. E., "Characterization and Computation of Optimal Policies for Operating an M/G/1 Queueing System with Removable Server," Opns. Res., Vol. 19 (1971), pp. 208-218. [5] Burke, P. J., "Delays in Single Server Queues with Batch Input," Opns. Res., Vol. 19 (1971), pp. 208-218. [6] Cooper, R.B., Introduction to Queueing Theory, Second Ed., Elsevier, North-Holand, New York. [7] Fuhrmann, S. W., and Cooper, R. B., "Stochastic Decompositions in the M/G/1 Queue with Generalized Vacations," Opns. Res. Vol. 33 (1985), pp. 1117-1129. [8] Heyman, D. P., "Optimal Operating Policies for M/G/1 Queueing Systems," Opns. Res. Vol. 16 (1968), pp. 362-382. [9], "The T-Policy for the M/G/1 Queue," Mgmt. Sci., Vol. 23 (1977), pp. 775-778. [10]Hofri, M., "Queueing Systems with a Procrastinating Server," Performance 86 and ACM Sigmetrics 1986, Proceedings of the Joint Conference on Computer Performance Modeling, Measurement, and Evaluation, Raleigh, N. Carolina (1986), pp. 245-253. 31

[ll]Levy, H.,and Kleinrock, L., "A Queue with Starter and a Queue with Vacations: Delay Analysis by Decomposition," Opns. Res. Vol. 34 (1986), pp. 426-436. [12]Levy, Y. and Yechiali, U., "Utilization of Idle Time in an M/G/1 Queueing System," Mgmt. Sci. Vol. 22 (1975), pp. 202-211. [13]Ramaswami, V., "The N/G/1 Queue and its Detailed Analysis," Adv. Appl. Prob. 12(1980), pp. 222-261. [14]Ross, S. M., Stochastic Processes, John Wiley & Sons, 1982. [15]Scholl, M. and leinrock, L., "On the M/G/1 queue with Rest Period and Certain Service Independent Queueing Disciplines," Opns. Res., Vol. 31 (1983), pp. 705-719. [16]Sobel, M.J., "Optimal Average-Cost Policy for a Queue with Start-up and Shut-down Costs," Opns. Res., Vol. 17 (1969), pp. 145-162. [17]Yadin, M. and Naor, P., "Queueing Systems with a Removable Service Station," Opns. Res. Quart. Vol. 14 (1963), pp. 393-405.

Table 1. result of example 1: m-policy without vacation (without start-up time) m-policy n-policy m W Cm n Wn Cn 10 12.09 81.74 1 6.70 220.10 11 12.75 79.94 2 8.37 125.10 12 13.42 78.71 3 10.03 96.77 13 14.08 77.96 4 11.70 85.10 14 14.74 77.57 5 13.37 80.10 *15 15.41 77.48 *6 15.03 78.43 16 16.07 77.63 7 16.70 78.67 17 16.74 77.99 8 18.37 80.10 18 17.40 78.52 9 20.03 82.32 ( * represents the optimal policy) 33

Table 2. result of example 2: m-policy with vacation (without start-up time) m-policy n-policy m W C n WnCn m mn 1 10.43 70.60 1 10.43 70.60 2 10.50 68.78 2 11.14 64.36 3 10.71 66.33 3 12.46 61.45 4 11.09 64.02 *4 14.01 61.42 5 11.56 62.31 5 15.60 63.03 6 12.04 61.37 6 17.21 65.58 7 12.61 60.82 7 18.83 68.73 *8 13.21 60.69 8 20.46 72.28 18 13.82 60.89 9 22.09 76.12 ( * represents the optimal policy ) 34

Table 3. result of example 3: m-policy with vacation (with start-up time) m-policy n-policy m W CW c m C Wn Cn 1 13.99 66.69 1 13.99 66.69 2 14.08 66.15 2 14.68 65.18 3 14.30 65.50 3 15.89 65.36 4 14.65 65.00 4 17.33 67.00 *5 15.09 64.81 5 18.83 69.53 6 15.53 64.90 6 20.36 72.63 7 16.05 65.26 7 21.92 76.11 ( * represents the optimal policy) 35

Table 4. result of example 4: m-policy with vacation (with start-up time) m-policy n-policy m W C n Wn C m m 8 13.83 117.54 1 7.09 200.67 9 14.95 114.81 2 9.11 152.83 10 16.11 113.00 3 11.36 130.44 11 17.24 111.96 4 13.71 119.31 *12 18.39 111.51 5 16.11 114.09 13 19.55 111.55 *6 18.54 112.36 14 20.71 111.99 7 20.98 112.86 ( * represents the optimal policy) 36

Ap-endix Proof of Theorem 4.1 Theorem 4.1: IdmZ)=m- 7 R(z)-ro Id,m(Z) = -r z{Id,m-j(z)-1) + 1-ro' m=1,2.... j=' Proof By conditioning on the number of units who arrive during the first vacation, we can obtain a recursive equation that yields P(Id,m=k) as m-1 P(Id,m=k}= I rjP(Id,m-j=k-j} + rk, k2m, m=1,2.... (A.1) j=o If we solve (A.1) in terms of P{Id,m=k), m-l I I P(Id,m=k}= P r.P(Id,m-j=k-j) + r k m, m=1,2 (A.2) j=i' rj where r. = j 1-ro From (A.2), the p.g.f. of Id,m is obtained as 00 Id,m(z) = PId,m=k}zk k=m oo m-l = X { X r.P(Id,m-j=k-j)+rk}zk k=mj=l m-l I c oo0 j= r.zj PId,m-j=k-j}zkJ+k rkzk j= k=m k=m m-1 o.t =~ rzJ{Id,m-j(z)-l}+k~rkzk m=1 J kl+ r-i rR(z)-ro = j=-roIdmj(z) 1-ro 37

Proof ofTheorem 5.1 Theorem 5.1: m-l Id,m(Z) = XjzJ{Id,m.j(z)-l) + X(z), m=1,2,.... j=1 Proof By conditioning on the number of units in the first arrival, we can obtain a recursive equation that yields P{Id,m=k) as m-l P(Id,m=k) = ~ xjP{Id,m-j=k-j) + xk, k2m, m=1,2,.... (A.3) j=1 From (A.3), the p.g.f. of Id,m is 00 Id,m(z) = P{Id,m=k)zk k=m oo m-l = k xjP(Id,m-j=k-j)+xk)zk k=m j= m-l oo oo = xjzJ I P{Id,m-j=k-j)zk-J+ Ixkzk j= k k=m k=m m-l = ~ xjzJ{Id,m-j(z)-l)+X(z). j=l 38

Proof of Propeties 1 through 6 Here we only provide proofs for the m-policy with vacation case. Proofs for the case without vacation can easily be shown analogously. Before proving the properties, we will present some propositions which will be used to prove properties 3, 4 and 5. ProDosition Al.(2).(2).(2).(2) d m' ld m-1 ld m-n l Id m-n-1.(1)=.(1)= () A.(1) + 2n, for m>n, n=1,2,..... (A.4) id m' ld m-1 ld m-n' ld m-n-1 proof The proof is by induction on m. If m=2 and n=O, (A.4) is trivially proved. If m=2 and n=1, from (4.8),.(2).(2) 1.(1).(2) r(2).(2) id 2 d -r2rlid 1 + rlid 1) +1 - ro - Id 1.(1).(1) = ~1.(1) r().(1) 1.r0~r lld 1) + 1 ro - ld (1(1) ) (2) r(2) (1).(2) (from the fact thatidl = 1-rO idl=ro andId0 id 0o) 21 l+odl.(1) ldl.(2).(2) d1 -I'd0 -.(1).(1) + 2 d 1 - M O So proposition Al is true if m=2. For the induction step, suppose (A.4) is true for m=k-1. To verify (A.4) for m=k, we use the following identity, which can be obtained after some algebraic manipulation using (4.8)..(2).(2).(1).(1) k d k' d k-1 Id k - dk k-1 _______ ______1 r V rj r (i).(A ).(2).(2) ().( 1).(1).(2).(2) [ l-ro 2j(d k-j' d k-l-j) d k-1 - d k-2 ld k-1' ld k-2 d k-1 d k-2 j=1 39

.(2).(2) Id k-1 -'d k-2.(2).(2) ______.(1).(1) -1) + (d kj - k-lj) - (1) d k-j d- k-il-jJi Id k-1 i- d k-2 If we apply the induction hypothesis on the right hand side of (A.5), we get.(2).(2).(1).(1) ld k - ld k-1 ld k - ld k-1.(2).(2) (1).(1) ld k-l' ld k-2 ld k-l' ld k-2 (A.5) k-1 1. S' 2j(P'.() r (2).(2) =.(2).(2) 1-ro { I d k-j - d k-l-j) +( id k-j - Id k-l-j) d k-1 - 1d k-2 j=l {.(2).(2) Id k-j - id k-j-1 rId k-j - d k1dk-j -k-j-1 2.(2).(2) d k-1 - ld k-2 k-1 rjj.(1 ).( 1) 1-ro d k-j d k-l-j j=l.(1).(1) ld k - d k-1 =2 = 2(2).(2) ld k-1 ld k-2 (A.6) where the last equality follows from the definition of i From (A.6), we obtain where the last equality follows from the definition of id k' From (A.6), we obtain.(2).(2) ld k -' d k-1.(2).(2) ld k-1 - ld k-2.(1).(1) ld k - ld k-1.(1).(1) = 2 ld k-1 ldk-2 So under induction hypothesis, (A.6) also holds for m=k. Thus, by the principle of mathematical induction, (A.4) holds for any m greater than 0. * 40

Proposition A2. =k, forall ml (A.7) Id m 1 where k 1 -x(1) - proof The proof is by induction on m. If m=l, (A.7) is trivially verified by using (4.8.a) and (4.15). For the induction step, suppose (A.7) is true for m=k-1. Under induction hypothesis we now prove that (A.7) is also true for m=k. k-1 E(V)+ Zrj k-j _d k jl j J=l1.(1) - k-1 i)'dk r(l)+ Yrjidk-j j=1 k-1 (1) kr(1) +k rjid k-j j=i - k-1 (1) r1+ rjlidk-j =k. So under the induction hypothesis, (A.7) also holds for m=k. Thus, by the principle of mathematical induction, we conclude that (A.7) holds for all m greater than 0. U Proposition A3 Ld m - Ld m-1 Ld m-n -Ld m-n-1.(1).(1) -.(1) (1) + kn, form>n, n=1,2,... (A.8) ld m' ld m-1 ld m-n' ld m-n-1 where k is defined in proposition A2. proof Proposition A3 can be proved in the same way as proposition Al, using proposition A2 appropriately. U We now prove properties 1 through 6. The proofs for Properties 3, 4 and 5 will use the above propositions. 41

.(1).(1) EPro rty 1 rn >in, for m>n, n-1,2,....... o(1) i (1) proof Note that we only need to prove that i'n >.1 for m>O. This can be easily proved by induction on m and using equation (4.12).. Property 2 hm > hn, for m>n, n=1,2,....... (2) proof By induction, we can prove that i' and Lm are both increasing functions with respect to m. Since hm is a positive combination of two increasing.(2) functions, namely, im and Lm, hence it is also an increasing function. U.( (2).(2) In'nm-1.(1).(1) m -lm1-.(2).(2) mn-n - lm-n-l (1) = (1).(1) + 2(1+i )n, for m>n, n=1,2,..... ir-n irm-n-l proof Using proposition Al, we have:.(2).(2).(1).(1) Im -lm-.(2).(2).(1).(1).(1) d m ldm-1 +2is (dm ld m-1) ^-.(1).(1) ld m' ld m-1.(2).(2) ld m' ld m-1 =. (.(1) + 2is'd m' ld m-1 = 2(1+,i ) From (A.9), we obtain property 3 directly. (A.9). Proert 4.(1) = im for all mnl, where k-x 1. kx(i). 42

proof Using proposition A2, we obtain: n lilm+ E(U) im id m+XE(U)x(l) ki1)+ E(U) id lm+kE(U)x(l) =k. * Lm- Lm-1.(1).(1) = im - m Lm-n -Lm-n-l + (k+ (i) —-n + (k+E(U))n lm-n - m-n-l for m>n, n=l,2,..... where k is defined in property 4. proof Using proposition A3, we have: Ldm-Ld m-l+m m-1)E() Ld m -Ld m-1 + (id m - id m-i)E(U) Lm - Lm-1.(1).(1) 1m - m-.(1).(1) ld m' ld m-1 = k +E(U). From (A.10), we obtain property 5 directly. (A.10) * hm- hn+l Proertv G.(1).(1) lm -in+l hm- hn h> - hn for m>n+1, n=1,2,....... im -In (A.11) proof From property 3, we know.(2).(2).(2).(2) rm -' m-1 m-1 i n-2.(.(2).(2) m-3 - lm-2.(1).(1) >. (1).(1).(1).(1) >... lm'!m-l lm-1' lm-2 im-2' lm-3 (A.12) To prove property 5, we use the following identity: If a, b, c, d, e, f, are all positive a c e a a+c a+c+e a> d > holds iff b+d > bd+V etc. If we apply this identity to (A.12), for m > n+1, we obtain 43

.(2).(2).(2).(2) Im - in+l'm - -.).(1 ).(1 ).(1) (A.13) xm - n+1 Xm -'n Similarly, we can prove that Lm - Ln+l Lm-Ln.(1).(1)>.(1) (1) (A.1 im - in+1 im - n (2) 1 Set hm = ClLm + c2im where cl = (l-p)ch and c2 = ZchE(S). Since cl and c2 are both positive, from (A.13) and (A.14) we can obtain (A.11). U 44