TEXT SIZE

CrossRef (0)
Conditional sojourn time distributions in M/G/1 and G/M/1 queues under -service policy

Sunggon Kim

aDepartment of Statistics, University of Seoul, Korea
Correspondence to: 1Department of Statistics, University of Seoul, 163 Seoulsiripdaero, Dongdaemun-gu, Seoul 02504, Korea. E-mail: sgkim@uos.ac.kr
Received May 15, 2018; Revised July 3, 2018; Accepted July 3, 2018.
Abstract

PλM-service policy is a workload dependent hysteretic policy. The policy has two service states comprised of the ordinary stage and the fast stage. An ordinary service stage is initiated by the arrival of a customer in an idle state. When the workload of the server surpasses threshold λ, the ordinary service stage changes to the fast service state, and it continues until the system is empty. These service stages alternate in this manner. When the cost of changing service stages is high, the hysteretic policy is more efficient than the threshold policy, where a service stage changes immediately into the other service stage at either case of the workload’s surpassing or crossing down a threshold. PλM-service policy is a modification of PλM-policy proposed to control finite dams, and also an extension of the well-known D-policy. The distributions of the stationary workload of PλM-service policy and its variants are studied well. However, there is no known result on the sojourn time distribution. We prove that there is a relation between the sojourn time of a customer and the first up-crossing time of the workload process over the threshold λ after the arrival of the customer. Using the relation and the duality of M/G/1 and G/M/1 queues, we obtain conditional sojourn time distributions in M/G/1 and G/M/1 queues under the policy.

Keywords : Array, hysteretic service policy, sojourn time distribution, duality
1. Introduction

We consider queueing systems under $PλM$-service policy. The policy is a workload-dependent hysteretic service policy with two service stages of different service rates 1 and M(> 1), i.e., there are the ordinary service stage with rate 1 and the fast service stage with rate M. The server starts to serve with rate 1 if a customer arrives to the server in an idle state. When the workload of the server reaches over λ, the service rate changes to M, and the rate continues until the system is empty. We obtain the conditional sojourn time distribution of a randomly chosen customer given the amount of work present in the server just after the arrival of the customer.

Bae et al. (2002) proposed $PλM$-service policy as a control policy for the M/G/1 queue, and obtained the distribution of the stationary workload. The policy is a modification of $PλM$ policy proposed by Faddy (1974) to control optimally a finite dam with the flow of water into the reservoir formed by a Wiener process. In a finite dam under $PλM$ policy, the release rate of water is 0 initially, and the rate changes to M instantaneously as soon as the level reaches λ. Once the dam becomes empty, the release rate remains zero until the level λ is reached again.

$PλM$-service policy can be considered as an extension of D-policy proposed by Balachandran (1973) as a control policy for single server queueing systems. Under the policy, the server is turned off at the end of a busy period, waits for the workload of the server to exceed some fixed value D, and starts the service. D-policy is identical to $PλM$ policy if we consider the level of water in a dam as the workload of the server, and let D = λ and M = 1.

Kim et al. (2006) considered the problem of finding the optimal value of M. They considered 4 types of costs; a switching cost for increasing service rate, an operating cost incurred when service rate is M, a holding cost per unit of workload, and a penalty cost due to being idle of the server. They showed that there exists the unique optimal value of M minimizing sum of the costs. Lee and Kim (2007) considered an M/G/1 queue under $PλM$-service policy with an exponentially distributed set-up time. They obtained the stationary workload distribution. Applying the duality between the M/G/1 and the G/M/1 queues, Kim and Bae (2008) obtained the distribution of the stationary workload in the G/M/1 queue under $PλM$-service policy. When the workload capacity is finite, Hur et al. (2006) developed an approximation method for some performance measures such as average workload, stationary workload distribution, and blocking probability.

Lee and Kim (2006) studied a generalization of $PλM$-service policy, where a fast service stage initiated by the up-crossing of level λ remains until the down-crossing of level τ instead of being empty of the server. The service rate depends on the workload and also on the service stage, i.e., there exist two service rate functions r1(x) for the ordinary service stage and r2(x) for the fast service stage. Under this service policy, they obtained the stationary workload distribution in an M/G/1 queue. The policy they considered is also a generalization of $Pλ,τM$ policy proposed by Yeh (1985) as a control policy for a finite dam. In this policy, r1(x) = 0 and r2(x) = M.

There are some studies on $Pλ,τM$ policy and its variants when input processes are more general than compound Poisson processes of M/G/1 queues. Abdel-Hameed (2000) studied $Pλ,τM$ policy in an infinite dam when the input is a compound Poisson process with positive drift. Abdel-Hameed and Nakhi (2006) studied the optimal control of the finite dam under $Pλ,τM$ policy when the input is a diffusion process and the release rate is state dependent. Abdel-Hameed (2011) analyzed an infinite dam under $Pλ,τM$ policy when the input is an increasing Lévy process. Bekker (2009) considered a single server queue under a variant of $Pλ,τM$ policy. He assumed Lévy input processes, and the Lévy exponents are different in each stage. He obtained the Laplace transform of the stationary workload.

Most studies on queues with workload dependent hysteretic service policy focus on obtaining a stationary workload distribution. In this paper, we obtain the conditional sojourn time distribution of a customer in M/G/1 and G/M/1 queues under $PλM$-service policy when the workload of the server just after the arrival of the customer is given. We reveal that there is a relation between the sojourn time of a customer and the first up-crossing time of the workload process over the level λ after the arrival of the customer. From the relation and the duality of M/G/1 and G/M/1 queues, we obtain the conditional sojourn time distribution.

The paper is organized as follows. In Section 2, we represent the sojourn time distribution using the conditional sojourn time distribution and the steady state distribution of the workload. In Section 3, we show the relation between the conditional sojourn time of a customer and the first up-crossing time of the workload process over the level λ. In Section 4, we obtain the conditional sojourn time distributions of M/G/1 and G/M/1 queues under $PλM$-service policy.

2. The conditional sojourn time

We consider aG/G/1 queuing system. Inter-arrival times of customers are independent and identically distributed (iid) with cumulative distribution function (cdf) A(·), and amounts of work brought by customers are also iid with cdf B(·). We assume that A(0) = 0 and B(0) = 0. Let α and β denote expectations of the inter-arrival times and the amounts of work, respectively. We define the workload of the server at time t as the amount of work present in the queueing system at time t. We choose random a customer, and shift the arrival time point of the customer to 0. We call this tagged customer. Let Y be the amount of work present in the server before time 0, and let W0 be the amount of work brought by the tagged customer. If we define X = Y + W0, then T, the sojourn time of the tagged customer, is defined as

$T=min {t|∫0tr(u) du=X},$

where r(t) is the service rate at time t. We define Tx as the conditional sojourn time of the tagged customer when X = x.

If x > λ, then the service rate is M until the system is empty. Thus,

$Tx=xM, x>λ.$

For the case of 0 < xλ, the service rate is 1 at time 0. Depending on the evolution of the workload process after time 0, the rate can be changed to M before the departure of the tagged customer. Thus, Tx is not a deterministic function of x, but a random variable dependent on x. We denote by F(t|x) the cdf of Tx, x > 0.

Since Y and W0 are independent, the cdf of X is the Stieltjes convolution of FY (·) and B(·), i.e.,

$FX(x)=∫0xB(x-y)dFY(y), x>0.$

Then, the stationary sojourn time distribution is given by

$Pr{T≤t}=∫0∞F(t∣x) dFX(x).$

Due to equation (2.1), Tx = x/M for x > λ. Then, we have

$Pr{T≤t}=∫0λF(t∣x)dFX(x)+∫λ∞I (xM≤t) dFX(x),$

where I(·) is the indicator function. The second term in the right hand side of equation (2.3) is evaluated as:

$∫λ∞I (xM≤t) dFX(x)={FX(Mt)-FX(λ),t≥λM,0,t<λM.$

Note that Tx ∈ (x/M, x] for xλ, which will be shown in Proposition 1. It implies that F(t|x) = 0 for tx/M, and that F(t|x) = 1 for tx. The first term in the right hand side of equation (2.3) is evaluated as:

$∫0λF(t∣x) dFX(x)={FX(λ),t≥λ,FX(t)+∫tMt∧λF(t∣x) dFX(x)t<λ,$

where Mtλ means min{Mt, λ}.

The sojourn time distribution is obtained by conditioning on the value of X as follows. From the above, we can see that for t < λ/M,

$Pr{T≤t}=FX(t)+∫tMtF(t∣x) dFX(x),$

and for λ/M < tλ,

$Pr{T≤t}=FX(t)+∫tλF(t∣x) dFX(x)+FX(Mt)-FX(λ),$

and for tλ,

$Pr{T≤t}=FX(Mt).$
3. The first upcrossing time over the level λ

Let Wi, i = 1, 2, …, be the amount of work brought by the ith customer after time 0, and Ui, i = 2, 3, …, the inter-arrival time of the (i − 1)th and ith customers. U1 denotes the arrival time of the first customer after time 0. Then, A(·) is the cdf of Wi, i = 1, 2, …, and B(·) is the cdf of Ui, i = 1, 2, …. We consider the following process, for 0 < xλ,

$X(t)=x+∑i=1N(t)Wi-t, t≥0,$

where N(t) is the number of customers arrived during (0, t], and N(0) = 0. Then, {X(t), t ≥ 0} is the workload process of the queueing system until it crosses up the level λ or becomes to be negative. Note that the process {X(t), t ≥ 0} is right-continuous.

The first up-crossing time over the level λ is defined as

$τx=inf{t>0:X(t)>λ}, 0

For x > λ, we let τx = 0. The assumption of B(0) = 0 says that there is no arrival except the tagged customer at time 0, and that for 0 < xλ, τx > 0 almost surely. We denote by G(t|x) the cdf of τx. Then, G(0|x) = 0 for 0 < xλ. From the following Proposition 1, we can see that it is sufficient to obtain the explicit form of G(t|x), 0 < xλ, in order to obtain the conditional sojourn time distribution F(t|x).

Proposition 1

For 0 < xλ, the support of Tx is (x/M, x]. The distribution of Tx is given by

$Pr{Tx=x}=1-G(x∣x),$

and

$F(t∣x)=G (MM-1 (t-xM)|x), xM
Proof

Suppose that 0 < xλ. If τxx, then the service rate during [0, x) is 1. The amount of work served during the time interval is x, which means that Tx = x. Conversely, the event {Tx = x} implies that τxx in the same reason. Thus, we can see that

$Pr{Tx=x}=Pr{τx≥x},$

which gives equation (3.3).

If 0 < τx < x, then the amount of work served during [0, τx] is τx. After time τx, (xτx) amount of work needs to be served before the completion of the service for the tagged customer. Therefore, we have

$Tx=τx+x-τxM=xM+M-1Mτx.$

From equation (3.6), we can see that Tx is an increasing function of τx and has values in (x/M, x) for 0 < τx < x. equation (3.4) follows from equation (3.6). Since τx > 0 almost surely, we can see that the support of Tx is (x/M, x].

From equations (3.5) and (3.6), it follows that for 0 < xλ,

$Tx=xM+M-1Mτx∧x,$

which gives

$E [Tx]=xM+M-1M (E [τx∣τx

To obtain another representation of τx in equation (3.2) for 0 < xλ, we consider the following random walk {S n, n = 0, 1, 2, …} associated with the G/G/1 queue:

$S0=x,Sn=x+∑i=1nWi-Ui, i=1,2,….$

Since we have assumed that the tagged customer arrives at time 0 and the inter-arrival times are U1,U2, …, the arrival time of the nth customer after time 0 is $tn=∑k=1nUk$ for n ≥ 1. From equation (3.1), it follows that

$Sn=X(tn), n=0,1,2,…,$

where t0 = 0. Therefore, for an n, S n > λ if and only if X(tn) > λ. We define

$N=min{n>0:Sn>λ}.$

Then, the process {X(t), t ≥ 0} crosses up the level λ first at time tN, i.e.,

$τx=∑i=1NUi.$

The first up-crossing time over the level λ is related to the initial busy period of a dual queue of the G/G/1 queue. In the dual queue, there is λx amount of work before t = 0, and the first customer arrives at time 0. The nth customer arrives at $t˜n=∑i=1n-1Wi$, n = 2, 3, …, i.e., inter-arrival times of customers are W1,W2, …. The amount of work brought by the nth customer is Un, n = 1, 2, …. The dual queue is a G/G/1 queue with initial workload λx, where the inter-arrival times are iid with cdf B(·) and amounts of work brought by customers are iid with cdf A(·). The initial busy period means the period from time 0 to the first epoch of being empty of the server. Applying the argument used in Cohen (1969) and Prabhu (1997), we show that τx can be represented using the length of the initial busy period of the dual G/G/1 queue as follows.

Proposition 2

Let τ̃y be the length of the initial busy period of the dual G/G/1 queue when there is y amount of work in the dual queue before t = 0. Then, for 0 < xλ,

$τx=dτ˜τ-x-(λ-x),$

where =d means the same in distribution.

Proof

Suppose that 0 < xλ. We consider the following process:

$X˜(t)=λ-x+∑i=1N˜(t)Ui-t, t≥0,$

where Ñ(t) is the number of customers arrived during [0, t] in the dual queue. From the definition of the dual queue, Ñ(0) = 1. We can see that (t) is the workload of the dual queue at time t during the initial busy period. The process {(t), t ≥ 0} is a right continuous process with left limit. Since $t˜n=∑i=1n-1Wi$, n = 2, 3, …. we have

$X˜(t˜n-)=λ-x+∑i=1n-1Ui-Wi, n=2,3,….$

If (i−) > 0 for in, then the initial busy period of the dual queue continues after time n. Let Ñ be the number of the customers served during the initial busy period. Then, (n−) > 0 for nÑ, and (n−) < 0 for n = Ñ + 1, which implies

$N˜=min{n>0:λ-x+∑i=1nUi-Wi<0}.$

By comparing equation (3.10) with equation (3.7), we can see that N and Ñ have the same distribution. Since the length of the initial busy period of the dual G/G/1 queue is equal to the amount of work served during the initial busy period, we have

$τ˜λ-x=λ-x+∑i=1N˜Ui.$

Applying above equation to equation (3.8) completes the proof.

4. Conditional sojourn time distributions in M/G/1 and G/M/1 queues

Suppose that the customers arrive according to a Poisson process with rate ν, i.e., ν = 1/α and A(x) = 1 − eνx, x ≥ 0. Then, the explicit form of G(t|x), 0 < xλ, is given in the following proposition.

Proposition 3

Suppose that A(x) = 1 − eνx, x ≥ 0, and define

$H(u,t)=∑k=0∞(νt)kk!e-νt Bk*(u),$

where Bn*(·) is the n-fold Stieltjes-convolution of B(·). Then,

$G(t∣λ)=1-1t∫0tH(u,t) du,$

and for 0 < x < λ,

$G(t∣x)=1-H(λ-x+t,t)+∫0t1t-u (∫0t-uH(y,t-u) dy) duH(λ-x+u,u).$
Proof

We can rewrite τx in equation (3.2) as: for 0 < xλ,

$τx=inf{t>0:λ-X(t)<0}=inf {t>0:λ-x+t-∑i=1N(t)Wi<0}.$

We denote $λ-x+t-∑i=1N(t)Wi$ by Y(t), t ≥ 0. Then, {Y(t), t ≥ 0} is a Cramér-Lundberg surplus process with initial surplus λx and premium rate 1. Then, τx is the time to the ruin of the process {Y(t), t ≥ 0}, and G(t|x) is the cdf of the ruin time. An explicit form of it is given in Asmussen (2000, pp.104–106), which completes the proof.

In equation (4.1), duH(λx + u, u) means H(λx + du, u). Note that $H(u,t)=Pr{∑i=1N(t)Wi≤u}$, i.e., for t > 0, H(u, t) is the cdf of the total amount of work arrived during (0, t]. Clearly, it has a point mass H(0, t) = eνt at 0. When B(·) has a density b(·), the total amount also has the density given by h(u, t) = ∂H(u, t)/∂u, i.e.,

$h(u,t)=∑k=1∞(νt)kk!e-νtb(k)(u),$

where b(k)(x) is the k-fold convolution of b(x), i.e.,

$b(1)(u)=b(u),b(k)(u)=∫0ub(k-1)(u-y)b(y) du, k≥2.$

In this case, equation (4.1) is rewritten as:

$G(t∣x)=1-H(λ-x+t,t)+∫0t1t-u (∫0t-uH(y,t-u) dy) h(λ-x+u,u) du.$

By change of variable w = tu, we have

$G(t∣x)=1-H(λ-x+t,t)+∫0t h(λ-x+w,w)e-ν(t-w) dw+∫0t1wh(t-w+λ-x,t-w) (∫0wyh(w-y,w) dy) dw.$

The above form of G(t|x) is also obtained by Stadje and Zacks (2003) in a different manner from Asmussen (2000). Let g(t|x) be the probability density function of the conditional sojourn time Tx. To obtain g(t|x) from equation (4.2) is not easy. Stadje and Zacks (2003) also obtained the explicit form of g(t|x) as:

$g(t∣x)=νe-νtB¯(λ-x+t)+ν∫0λ-x+t h(u,t)B¯(λ-x+t-u) du-ν∫0th(λ-x+u,u)e-ν(t-u)B¯(t-u) du-ν∫0t1u∫0u(u-y)h(y,u)B¯(u-y) dy du.$

Applying Proposition 3 to Proposition 1, we obtain F(t|x) for 0 < xλ. Since the tagged customer is chosen randomly, the system is in the stationary state at the arrival of the tagged customer due to the property of PASTA. It implies that Y follows the stationary workload distribution. An explicit form of FY (·) is obtained by Bae et al. (2002).

Now, we consider the case that the amount of the work brought by customers are exponentially distributed, i.e., B(x) = 1 − ex/β, x ≥ 0. In Section 2, we have assumed that the tagged customer arrives at time 0 and the workload of the server just after the arrival of the tagged customer is x. Then, the queueing system under consideration is the G/M/1 queue with X(0) = x. The dual queue of the G/M/1 queue is an M/G/1 queue with initial workload λx, which is defined in Section 3. The Laplace transform and the cdf of τ̃y, the length of the initial busy period of the dual M/G/1 with y = λx, is obtained in equations (4.94) and (4.95) of Cohen (1969, p.261), respectively, as:

$E [e-sτ˜y]=exp {-y (s+1-ψ(s)β)},$

where ψ(s) is the Laplace transform of the length of the initial busy period of the dual M/G/1 with y = 0, i.e., the length of the ordinary busy period, and

$Pr{τ˜y≤t}={∑k=0∞∫yte-sβskβkk! (ys)dsBk*(s-y),t≥y,0,t

where B0*(·) is the Heaviside step function. Proposition 2 says that

$E [e-sτx]=es(λ-x)E [e-sτλ-x],$

and that G(t|x) = Pr{τ̃λxt + λx}. Then, from equations (4.4) and (4.5), we have

$E [e-sτx]=exp {-(λ-x)1-ψ(s)β},$

and

$G(t∣x)=∑k=0∞∫0te-s+λ-xβ(s+λ-x)kβkk! (λ-xs+λ-x) dBk*(s), t>0.$

Applying equation (4.7) to Proposition 1, we obtain the conditional sojourn time distribution of a customer in the G/M/1 queue with $PλM$-service policy.

References
1. Abdel-Hameed, M (2000). Optimal control of a dam using policies and penalty cost when the input process is a compound Poisson process with positive drift. Journal of Applied Probability. 37, 408-416.
2. Abdel-Hameed, M (Array). Control of dams using policies when the input process is a nonnegative Lévy process. International Journal of Stochastic Analysis.
3. Abdel-Hameed, MS, and Nakhi, YA (2006). Optimal control of a finite dam with diffusion input and state dependent release rates. Computers & Mathematics with Applications. 51, 317-324.
4. Asmussen, S (2000). Ruin Probabilities. Singapore: World Scientific
5. Bae, J, Kim, S, and Lee, EY (2002). A -policy for an M/G/1 queueing system. Applied Mathematical Modelling. 26, 929-939.
6. Balachandran, KR (1973). Control policies for a single server system. Management Science. 19, 1013-1018.
7. Bekker, R (2009). Queues with Lévy input and hysteretic control. Queueing Systems. 63, 281-299.
8. Cohen, JW (1969). The Single Server Queue. Amsterdam, Amsterdam: North-Holland
9. Faddy, MJ (1974). Optimal control of finite dams: discrete (2-stage) output procedure. Journal of Applied Probability. 11, 111-121.
10. Hur, S, Lee, H, and Kim, S (2006). A simple approximation method for workload analyses in some queueing systems with control policies. Computers & Industrial Engineering. 51, 183-195.
11. Kim, J, Bae, J, and Lee, EY (2006). An optimal -service policy for an M/G/1 queueing system. Applied Mathematical Modelling. 30, 38-48.
12. Kim, S, and Bae, J (2008). A G/M/1 queueing system with -service policy. Operations Research Letters. 36, 201-204.
13. Lee, J, and Kim, J (2006). A workload-dependent M/G/1 queue under a two-stage service policy. Operations Research Letters. 34, 531-538.
14. Lee, J, and Kim, J (2007). Workload analysis of an M/G/1 queue under the policy with a set-up time. Applied Mathematical Modelling. 31, 236-244.
15. Prabhu, NU (1997). Stochastic Storage Processes: Queues, Insurance Risk, Dams, and Data Communication. New York: Springer
16. Stadje, W, and Zacks, S (2003). Upper first-exit times of compound Poisson processes revisited. Probability in the Engineering and Informational Sciences. 17, 459-465.
17. Yeh, L (1985). Optimal control of a finite dam: average-cost case. Journal of Applied Probability. 22, 480-484.