For the N policy M[x]/G/1 queuing system, we easily derived some important
system characteristics through the key probability - generating function and
decomposition property. We also performed a numerical analysis between the optimal
value N and the specific values of system parameters. The model is significant since
more general situations in practical applications are considered in the model.
15 trang |
Chia sẻ: huongthu9 | Lượt xem: 536 | Lượt tải: 0
Bạn đang xem nội dung tài liệu The optimal control in batch arrival queue with server vacations, startup and breakdowns, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Yugoslav Journal of Operations Research
14 (2004), Number 1, 41-55
THE OPTIMAL CONTROL IN BATCH ARRIVAL QUEUE
WITH SERVER VACATIONS, STARTUP AND
BREAKDOWNS
Jau-CHUAN KE*
National Taichung Institute of Technology
Taichung 404, Taiwan, R.O.C.
Received: January 2003 / Accepted: January 2004
Abstract: This paper studies the N policy M[x]/G/1 queue with server vacations; startup
and breakdowns, where arrivals form a compound Poisson process and service times are
generally distributed. The server is turned off and takes a vacation whenever the system
is empty. If the number of customers waiting in the system at the instant of a vacation
completion is less than N, the server will take another vacation. If the server returns from
a vacation and finds at least N customers in the system, he is immediately turned on and
requires a startup time before providing the service until the system is empty again. It is
assumed that the server breaks down according to a Poisson process whose repair time
has a general distribution. The system characteristics of such a model are analyzed and
the total expected cost function per unit time is developed to determine the optimal
threshold of N at a minimum cost.
Keywords: Breakdowns, cost model, queue, startup, vacation.
1. INTRODUCTION
We consider an M[x]/G/1 queuing system in which the server operates N policy
and is typically a subject to unpredictable breakdowns. The server leaves for a vacation
of random length whenever the system becomes empty. At the end of a vacation, the
server inspects the system and decides whether to take a vacation, or to take a general
startup time. The server immediately starts serving the waiting customers whenever he
completes his startup.
* Jau-Chuan Ke. Email: jauchuan@ntit.edu.tw. Postal address: Department of Statistics, National
Taichung Institute of Technology, No. 129, Sec. 3, Sanmin Rd., Taichung 404, Taiwan, R.O.C.
J.-C. Ke / The Optimal Control in Batch Arrival Queue 42
Queuing systems with server vacations have attracted much attention from
numerous researchers since Levy and Yechiali (1975). Server vacations are useful for the
system in which the server wants to utilize his idle time for different purposes. An
excellent survey of queuing systems with server vacations was found in Doshi (1986) and
Takagi (1991). Queuing systems with the threshold policy (N policy) and multiple
vacations, including some applications, were first Lee and Srinivasan (1989) and Kella
(1989). They respectively dealt with the batch arrival M/G/1 and the single-unit arrival
M/G/1 queuing systems, examined the system performances, and obtained the optimal
policy under a stationary cost function. Lee et al. (1994 a, b) further analyzed Lee and
Srinivasan’s model with a single vacation and multiple vacations, respectively. They
provided the probabilistic interpretation of the single (multiple) vacation system with N
policy, and their results confirmed the stochastic decomposition property given by
Fuhrmann and Cooper (1985).
The server startup corresponds to the preparatory work of the server before
starting the service. In some actual situations, the server often requires a startup time
before starting his each service period. Examining queuing systems which combine the N
policy with startup time, Baker (1973) first proposed the N policy M/M/1 queuing system
with exponential startup time. Borthakur et al. (1987) extended Baker's results to the
general startup time. The N policy M/G/1 queuing system with startup time was first
studied by Minh (1988) and was investigated by several researchers such as Medhi and
Templeton (1992), Takagi (1993), Lee and Park (1997), and others. Recently, Hur and
Paik (1999) examined the operation characteristics of the N policy M/G/1 queuing system
with server startup and explained how the system’s optimal policy and cost behave for
various arrival rates.
Most studies on queuing systems use “perfect” (reliable) servers. In many real
systems, however, the server may meet unpredictable breakdowns. Therefore, queuing
models with server breakdowns are more realistic representation of the systems.
Discussing queuing systems with N policy and server breakdowns, Wang (1995)
proposed the N policy M/M/1 queuing system with server breakdowns at first. Wang
(1997) and Wang et al. (1999) extended Wang’s model to the N policy M/Ek/1 and
M/H2/1 queuing system cases, respectively. They developed the analytic closed-form
solutions and provided a sensitivity analysis. Comparable work on the batch arrival
queues where the server operates an N policy with vacations, startup and breakdowns is
rarely found in the literature. This motivates us to develop the N policy for an M[x]/G/1
queuing system where the server is characterized with vacations, startup and breakdowns.
In this paper, we develop the probability-generating function of the number of
customers present when the server begins performing startup. We also derive other
important system characteristics, such as the expected number of customers in the
system, waiting time distribution in the queue, the expected length of the idle period and
busy period, etc. Following the construction of the expected cost function per unit time,
an efficient and quick procedure is developed for searching the optimal threshold N*
value that minimize the cost function. Some numerical examples are also presented.
J.-C. Ke / The Optimal Control in Batch Arrival Queue 43
2. THE SYSTEM ASSUMPTIONS AND NOTATIONS
In this paper, we consider the control policy for an M[x]/G/1 queuing system
with the following specifications. It is assumed that customers arrive in batches to occur
according to a compound Poisson with rate λ . Let kX denote the number of customers
belonging to the k th arrival batch, where kX , 1, 2, 3, k = " , are with a common
distribution, where
Pr[ ]k nX n g= = , 1,2,3,...n =
The service times for a customer are independent and identically distributed
random variables (S) with a common distribution function S(t). The server is subject to
breakdowns at any time with Poisson breakdown rate α when he is working. Whenever
the server fails, it is immediately repaired at a repair facility, where the repair times are
independent and identically distributed random variables (R) with a common distribution
function ( )R t . If at any time any customer arrives, he goes to the service facility for
service. Arriving customers form a single waiting line based on the order of their arrivals;
that is, they are queued according to the first-come, first-served (FCFS) discipline. The
server can serve only one customer at a time. A customer who arrives and finds the
server busy or broken down must wait in the queue until a server is available. Although
no service occurs during the repair period of a broken down server, customers continue to
arrive according to a Poisson process.
Furthermore, we consider the system in which the server is turned off and takes
a sequence of vacations for a period of random length V whenever the system becomes
empty. When the server returns from a vacation and finds that the number of customers
waiting in the system is less than N, he will go on a vacation again. If N or more
customers are accumulated in the system, the server is immediately turned on but is
temporarily unavailable to the waiting customers. He needs a startup time with random
length U before starting his service. As soon as the server finishes startup, he starts
serving the waiting customers until the system becomes empty. Service is allowed to be
interrupted if the server breaks down, and the server is immediately repaired. Once the
broken down server is repaired, he immediately returns to serve a customer until the
system is empty.
For any discrete random variable, Y, used in the analysis, we adopt the following
notation:
1
( ) i i
i
Y z z y
∞
=
= ∑ ,
the probability generating function (p.g.f.) of Y, where Pr[ ]iy Y i= = .
Similarly, for any continuous random variable Z used in the analysis, ( )Z t
denotes the distribution function of Z, Z*(θ )
0
( )te dZ tθ
∞= ∫ denotes its Laplace-Stieltjes
transform (LST) of and Z*(l)(θ ) the l th order derivative of Z*(θ ) with respect to θ .
J.-C. Ke / The Optimal Control in Batch Arrival Queue 44
3. PROBABILITY GENERATING FUNCTION
In this section we first construct the probability generating function of the
number of customers present when the server begins performing startup. Then, we study
various system characteristics by means of the probability generating function.
Let us define that B is the number of batches that arrive during a vacation.
Using the definition of Poisson arrivals, ( ) / !t ke t kλ λ− is the probability that k batches
arrive during [0, ]t . We have
0
( )Pr( ) ( )
!
k
t
k
tb B k e dV t
k
λλ∞ −= = = ∫ .
For convenience of computation of kb , we use the following equivalent
expressions:
*( )( ) ( )
!
k
k
kb Vk
λ λ−= .
Furthermore, we define that Q is the number of customers that arrive during a
vacation. Using the property of convolution, the probability that there are exact n
customers during k batches arriving as follow:
'
( )
1 2Pr[ ]
nk g s
k
n n n n kg g g g X X X n= ⊗ ⊗ ⊗ = + + + =
HJJJJJJJJJJJJJJJJGJ
" " ,
where (0)0g is defined to be 1.
From the definitions of Q and ( )kng , we have the following relations
( )
0
Pr( )
n
k
n k n
k
q Q n b g
=
= = = ∑ , 0,1,2,...n = (1)
From (1), we obtain the following Theorem 1.
Theorem 1. The probability generating function of Q is given by
*( ) ( ( ))Q z V X zλ λ= − .
Differentiating ( )Q z with respect to z , it finally yields the first and second
factorial moments of Q as follows:
(1) [ ] [ ] [ ]Q E Q E X E Vλ= = , (2a)
and
(2) 2 2[ ( 1)] [ ( 1)] [ ] ( [ ]) [ ]Q E Q Q E X X E V E X E Vλ λ= − = − + . (2b)
J.-C. Ke / The Optimal Control in Batch Arrival Queue 45
Let NΠ be the number of customers present when the server begins performing
startup. The following result, stated as Theorem 2 expresses the p.g.f. of NΠ .
Theorem 2.
0
1( )
1N
z
q
Π = −
1
1 1
[ ( ) 1]
N
j k
j N j k
j k
q z z z q
− ∞
−
= =
Π − + ∑ ∑ , 1, 2,3,...N = (3)
Proof: Conditioning on the number of customers who arrive during the previous
vacation, we have
1
0
Pr[ ] Pr [ ]
N
N j N j k
j
k q k j q
−
−
=
Π = = Π = − +∑ , k N≥ , 1, 2,3,...N = (4)
It is easy to solve (4) in term of Pr[ ]N kΠ = , and it yields
1
10
1Pr[ ] Pr [ ]
1
N
N j N j k
j
k q k j q
q
−
−
=
Π = = Π = − + − ∑ , k N≥ , 1, 2,3,...N = (5)
From (5), we get the p.g.f. of NΠ is obtained as
0
1( )
1N
z
q
Π = −
1
1
Pr [ ]
N
k k
j N j k
k N j k N
z q k j z q
∞ − ∞
−
= = =
Π = − + ∑ ∑ ∑ . (6)
Simplify (6) to obtain the desired result of (3). ■
Using (3), [ ]NE Π and [ ( 1)]N NE Π Π − are obtained by taking first and second
order derivative of ( )N zΠ with respect to z .
Let (1) [ ]N NEπ = Π and (2) [ ( 1)]N N NEπ = Π Π − . Thus we have as follows:
1
(1) (1) (1)
10
1
1
N
N j N j
j
q Q
q
π π− −
=
= + − ∑ , 1,2,3,...N = (7)
and
(2)
0
1
1N q
π = −
1
(1) (2) (2)
1
[2 ]
N
j N j N j
j
q j Qπ π− − −
=
+ + ∑ , 1, 2,3,...N = (8)
where
b
a
∑ indicates zero when a b> , and (1)Q and (2)Q are given in (2).
To complete the computations of (1)Nπ and (2)Nπ , we may obtain (1)kπ and (2)kπ
( 1 )k N≤ ≤ recursively using (7) and (8).
J.-C. Ke / The Optimal Control in Batch Arrival Queue 46
4. SYSTEM CHARACTERISTICS
4.1. Expected number of the customers in the system
We recall some results in the ordinary M[x]/G/1 queuing system with server
breakdowns. Let H be a random variable representing the completion time of a customer
service, which includes both the service time of a customer and the repair time of a
server. The useful results of Tang (1997) are as follows;
[ ] [ ](1 [ ])E H E S E Rα= + , (9)
2 2 2 2[ ] (1 [ ]) ( [ ]) [ ] [ ]E H E R E S E S E Rα α= + + , (10)
and
[ ] [ ] (1 [ ])H E X E H E Rρ λ ρ α= = + . (11)
where [ ] [ ]E X E Sρ λ= . Note that Hρ is traffic intensity and it should be assumed to be
less than unity.
Applying the results of Chae and Lee (1995) and Tang (1997), we obtain the
expected waiting time in the queue for the N policy M[x]/G/1 queuing system with server
vacations, startup and breakdowns given by
( [ ]) [ ] [ ] (1 ) [ ]q q r H r H rW L E X E H E H E Iρ ρ= + + + − , (12)
where qL denotes the expected number of customers in the queue, rX denotes the
residual batch size, rH denotes the residual completion time and rI denotes the residual
idle time.
Substituting Hρ Wq for [ ]qL E H in (12), and then solving for Wq yields
[ ] [ ] [ ] [ ]
1 1
r H r
q r
H H
E H E X E HW E Iρρ ρ= + +− − . (13)
where Hρ is given in (11).
From Chae and Lee (1995), we obtain [ ]rE X given by
21 [ ][ ] 1
2 [ ]r
E XE X
E X
= −
. (14)
It is well-known results of the Kleinrock (1975) that [ ]rE H is given by
2[ ][ ]
2 [ ]r
E HE H
E H
= . (15)
Let rV and rU denote the residual vacation time and the residual startup time.
Following the result of Chae and Lee (1995) and using the definition of NΠ , the
expected residual vacation time is given by
J.-C. Ke / The Optimal Control in Batch Arrival Queue 47
2[ ]1 1[ ] 1 [ ]
[ ] 2 [ ]
N
r r
N
EE V E X
E X Eλ
Π = − − Π
. (16)
Inserting (14) in (16), we obtain
(2)
(1)
1 [ ( 1)][ ]
2 [ ] [ ]
N
r
N
E X XE V
E X E X
π
λ π
−= −
. (17)
According to the results of Takagi (1991, section 2.2) and Chae and Lee (1995), we have
22 [ ] [ ][ ]
2(1 [ ])r
E U E UE U
E U
λ
λ
+= + . (18)
Since the idle time is consisted of the vacation time and the startup time, we have the
expected residual idle time as follows:
[ ] [ ] [ ]r r rE I E V E U= + .
From (17) and (18), we have
(2) 2
(1)
1 [ ( 1)] 2 [ ] [ ][ ]
2 [ ] [ ] 2(1 [ ])
N
r
N
E X X E U E UE I
E X E X E U
π λ
λ λπ
− += − + +
. (19)
Finally follows from (9)-(10), (13)-(15) and (19), after using Little’s rule ( vs q HL L ρ= +
q HWλ ρ= + ) we obtain an expression for vsL , stated as Theorem 3.
Theorem 3. The expected number of customers for the N policy M[x]/G/1 queuing system
server vacations, startup and breakdowns is given by
2 2 2 2
(2)
(1)
2 2
[ ](1 [ ]) [ ] [ ]
2(1 )
[ ](1 [ ]) [ ( 1)]
2(1 ) [ ]
1 [ ( 1)]
2 [ ] [ ]
2 [ ] [ ] .
2(1 [ ])
vs
H
H
N
N
H
E X E R E S E RL
E S E R E X X
E X
E X X
E X E X
E U E U
E U
λ α λαρ
ρ
λ α
ρ
π
π
λ λ ρλ
+ += −
+ −+ −
−+ −
++ ++
(20)
4.2. Expected length of the complete period, the idle period and the busy cycle
The server remains on vacations until he finds N or more customers after
returning from a vacation. This is called the vacation period. The startup period begins
when the server performs startup as soon as the server returns from a vacation and finds
at least N customers. This startup period terminates when he starts providing the service.
J.-C. Ke / The Optimal Control in Batch Arrival Queue 48
The customers arriving during startup and vacation periods will not be immediately
served until the server completes the startup. Therefore, the idle period is the sum of the
vacation and startup period. The busy period is initiated when the server completes his
startup and starts serving the waiting customers. During the busy period, the server may
break down and start his repair immediately. This is called the breakdown period. After
the server is repaired, he returns and provides service until there are no customers in the
system. Since the complete period starts when the startup period is over and terminates
when there are no customers in the system, the complete period is represented by the sum
of the busy period and the breakdown period.
First let * ( )oH θ denote the LST of the complete period in the ordinary M[x]/G/1
queuing system with server breakdowns and * ( )osH θ be the LST of the complete period
in ordinary the M[x]/G/1 queuing system with server startup time. It is useful results of
Baba (1986), Tang (1997), and Wang (1997) that the LST of the complete period started
with one customer in the M/G/1 queuing system with server breakdowns can be
expressed by
* * *( ) [ ( ( ))]o oH H X Hθ θ λ λ θ= + − , (22)
where * ( )H ⋅ is LST of completion time H .
Applying the well-known results of Takagi (1991, section 2.2) and Tang (1997)
we have the following important results
* * * *( ) ( ) [ ( ( ))]os o oH H U X Hθ θ λ λ θ= − , (23)
where * ( )oH θ is given in (22).
Differentiating (22) with respect to θ , we derive the expected length of the
complete period initiated with one customer in the system as
[ ][ ]
1o H
E HE H ρ= − . (24)
where [ ]E H and Hρ are given in (9) and (11), respectively.
Differentiate (23) with respect to θ and using (24), it follows that
[ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]
1 (1 [ ]) 1 (1 [ ])
os o oE H E H E X E U E H
E H E X E U E H
E R E R
λ
λ
ρ α ρ α
= +
= +− + − +
. (25)
Expected length of the complete period
Let * ( )vsH θ be the LST of complete period for the N policy M[x]/G/1 queuing
system with server vacations, startup and breakdowns, and the first customer in each
complete period needs to wait for a server startup time U before receiving the service.
After the server finishes startup, he resumes the supply of service. The time spent on
serving the customers who arrive during the vacation period and the subsequent arrivals
J.-C. Ke / The Optimal Control in Batch Arrival Queue 49
while the server is providing service is denoted by vH with LST
* ( )vH θ . And sH
denotes the time spent on serving the arrivals during the server startup period and those
subsequent arrivals before the system becomes empty again, where * ( )sH θ is the LST of
sH . It is clear that
* ( )vsH θ is convolution of * ( )vH θ and * ( )sH θ . Since the vacation and
the startup times are independent, we have
* * * * *( ) ( ) ( ) ( ) ( )vs v s v sH H H H Hθ θ θ θ θ= ⊗ = . (26)
Find [ ]sE H
Recall that the expected length of complete period given by (25) decomposes
into two parts: one (the first term) is the expected length of complete period in the
ordinary M[x]/G/1 queuing system with server breakdowns, the other (the second term) is
the expected length of the complete period caused by the server startup. Using the
meanings of the above listed sH we have
[ ][ ] [ ] [ ][ ]
1 (1 [ ]) 1
H
s
H
E UE X E U E HE H
E R
ρλ
ρ α ρ= =− + − . (27)
Find [ ]vE H
Since * ( )oH θ is the LST of the complete period started with one customer and
arrival process is Poisson, the LST of the complete period initiated with n customers in
the system is given by *[ ( )]noH θ . Thus, using the definitions of vH we have
* * *( ) Pr[ ]( ( )) ( ( ))kv N o N o
k N
H k H Hθ θ θ∞
=
= Π = = Π∑ . (28)
Differentiating (28) with respect to θ and using (24), we get
[ ]vE H
(1) [ ]
1 (1 [ ])
N E H
E R
π
ρ α= − +
(1) [ ](1 [ ])
1 (1 [ ])
N E S E R
E R
π α
ρ α
+= − + . (29)
Differentiating (26) with respect to θ and using (27) and (29), we obtain an expression
for [ ]vsE H , stated as Theorem 4.
Theorem 4. The expected length of the complete period for the N policy M[x]/G/1
queuing system with server vacations, startup and breakdowns is given by
(1) [ ](1 [ ])[ ] ( [ ] [ ])
1 (1 [ ])vs N
E S E RE H E X E U
E R
απ λ ρ α
+= + − + . (30)
J.-C. Ke / The Optimal Control in Batch Arrival Queue 50
Expected length of the busy period and the breakdown period
The expected length of the busy period and the expected length of breakdown
period are denoted by [ ]vsE B and [ ]vsE D , respectively. Recall that the complete period
is the sum of the busy and the breakdown periods which imply [ ] [ ] [ ]vs vs vsE H E B E D= + .
Hence, from (30) we have
(1)( [ ] [ ]) [ ]
[ ]
1 (1 [ ])
N
vs
E X E U E SE B
E R
π λ
ρ α
+= − + , (31)
and
(1)( [ ] [ ]) [ ] [ ]
[ ]
1 (1 [ ])
N
vs
E X E U E S E RE D
E R
π λ α
ρ α
+= − + . (32)
Expected length of the idle period
Let * ( )vsI θ be the LST of the idle period, which is the sum of vacation period
and startup period, for the N policy M[x]/G/1 queuing system with server vacations,
startup and breakdowns. Suppose * ( )vI θ denotes the LST of the vacation period. It is
clear that * ( )vsI θ is convolution of * ( )vI θ and * ( )U θ . Since the vacation time and the
startup time are independent, we have
* * * * *( ) ( ) ( ) ( ) ( )vs v vI I U I Uθ θ θ θ θ= ⊗ = . (33)
Since (1)Nπ is the expected number of arrivals before the server starts performing
startup, we have the expected length of the vacation period as follows;
(1)
[ ]
[ ]
N
vE I E X
π
λ= . (34)
Differentiating (33) with respect to θ and using (34), the expected length of the
idle period for this system is expressed by the following theorem.
Theorem 5.
(1)
[ ] [ ]
[ ]
N
vsE I E UE X
π
λ= + . (35)
Expected length of the busy cycle
The busy cycle for the N policy M[x]/G/1 queuing system with server vacations,
startup and breakdowns, denoted by vsΘ , is the length of time from the beginning of the
last idle period to the beginning of the next idle period. From (30) and (35), we have
J.-C. Ke / The Optimal Control in Batch Arrival Queue 51
[ ]
(1) [ ] [ ]
[ ]
[ ] 1 (1 [ ])
N
vs
E X E UE
E X E R
π λ
λ ρ α
+Θ = − + . (36)
5. SPECIAL CASES
In this section, we present some existing results in the literature which are
special cases of our system.
Case 1: It is to be noted that when Pr[ 0] 1U = = , 0α = and 1N = , we recover the
results for the ordinary M[x]/G/1 queuing system with multiple vacations (i.e. a sequence
of the same vacations of random length). In this case, the expected residual vacation
time, [ ]rE V given in equation (17), can be reduced to a special case for the last term of
expression (3.21a) of Takagi (1991, p143) or the expression (6) of Chae and Lee (1995).
Case 2: When Pr[ 0] 1U = = , 0α = and 1N > , we recover the results for the N policy
M[x]/G/1 queuing system with multiple vacations. In this case, expression (7) for (1)Nπ ,
expression (8) for (2)Nπ , and (36) for [ ]vsE Θ can be reduced to a special case for the
expressions (4.10), (4.11) and (4.38) of Lee and Srinivasan (1989).
6. OPTIMAL POLICY
In this section, we develop the total expected cost function per unit time for the
N policy M[x]/G/1 queuing system with server vacations, startup, and breakdowns, in
which N is decision variable. Let us consider the following costs:
sc ≡ setup cost for per busy cycle;
hc ≡ holding cost per unit time for each customer present in the system;
rc ≡ startup cost per unit time for the preparatory work of the server before
starting the service;
oc ≡ cost per unit time for keeping the server on and in operation;
dc ≡ breakdown cost per unit time for a failed server.
Using the definitions of each cost element and its corresponding system performances,
the total expected cost with threshold N becomes
( )
[ ]
s
h vs
vs
cF N c L
E
= + +Θ
[ ] [ ][ ]
[ ] [ ] [ ]
vs vs
r o d
vs vs vs
E B E DE Uc c c
E E E
+ +Θ Θ Θ . (37)
Substituting (21), (31)-(32), and (36) into (37), we obtain
J.-C. Ke / The Optimal Control in Batch Arrival Queue 52
( )
(1)
22 2 2
(2)
(1)
2 2
[ ](1 )( [ ])
( )
[ ] [ ]
[ ] 1 [ ] [ ] [ ]
2(1 )
[ ](1 [ ]) [ ( 1)] 1 [ ( 1)]
2(1 ) [ ] 2 [ ] [ ]
2 [ ] [ ] [ ]
2(1 [ ])
H s r
N
h
H
N
H N
H d o
E X c c E UF N
E X E U
E X E R E S E R
c
E S E R E X X E X X
E X E X E X
E U E U c E R c
E U
λ ρ
π λ
λ α λαρ
ρ
πλ α
ρ π
λ λ ρ ρα ρλ
− += +
+ ++ −
+ − −+ + − −
++ + + ++
(2)
1
2(1) (1) ,2 [ ][ ] [ ]
h N
N N
cA A
E XE X E U
π
π λ π= + ++
(38)
where 1 [ ](1 )( [ ])H s rA E X c c E Uλ ρ= − + ,
( )22 2 2
2
2 2
2
[ ] 1 [ ] [ ] [ ]
2(1 )
[ ](1 [ ]) [ ( 1)] 2 [ ] [ ]
2(1 ) [ ] 2(1 [ ])
[ ( 1)] [ ] ,
2( [ ])
h
H
H
H d o
E X E R E S E R
A c
E S E R E X X E U E U
E X E U
E X X c E R c
E X
λ α λαρ
ρ
λ α λ λ
ρ λ
ρ ρα ρ
+ += −
+ − ++ +− +
−− + + +
and Hρ is given by (11).
We want to find the value of N that yields the minimum expected cost per unit
of time. Following the concepts of Lee and Srinivasan (1989), the optimal value *N of
N is given by the first N such that ( ) 0I N > . That is
{ }* min 1 ( ) 0N N I N= ≥ > . (39)
where
1 (1) (1)
1
(2) (2)
1
(1) (1)
1
( ) ( 1) ( )
1 1
[ ] [ ] [ ] [ ]
.
2 [ ]
N N
h N N
N N
I N F N F N
A
E X E U E X E U
c
E X
π λ π λ
π π
π π
+
+
+
= + −
= − + +
+ −
(40)
The sign of ( )I N determines whether ( )F N increases or decreases with
respect to N. Numerical experiments based on (39) can convince us that the expected cost
function is convex which is performed in the following section.
J.-C. Ke / The Optimal Control in Batch Arrival Queue 53
7. NUMERICAL EXAMPLES
We present some numerical examples in this section to demonstrate how the
management of a production line system uses the above results to make the decision to
minimize the total expected cost function regarding the threshold value.
Consider a production line in which the production does not start until at least
some specified number of units, N (N 1≥ ), are accumulated during an idle period. The
units arrive in batches according to a compound Poisson process with batch arrival rate
0.6λ = . The operator will take a sequence vacations whenever there are no units to
process. The operator of the machine may utilize his vacation time to perform some extra
operations such as preventive maintenance, or some other work, etc. When the operator
returns from a vacation and finds that the number of processed units is less than
threshold, N, he will go on a vacation again. It is noted that the operator requires a startup
time to operate machine when he finds that the number of processed units reaches or
exceeds N and the operation may be interrupted because of emergent events. We wish to
obtain an optimal policy regarding the threshold value, which minimizes the total
expected cost function and the costs are assumed as follows;
1000sc = , 1hc = , 100rc = , 200dc = , 100oc = .
The above system can be modeled as M[x]/G/1 queue with the following assumptions:
Batch arrival size distribution is geometric with parameter p ;
vacation time is a 2-stage Erlang distributions with mean [ ]E V ;
startup time is an exponential distribution with mean [ ]E U ;
service time is a 2-type hyperexponential distribution with probability density
function
21 1 1 2 2
( ) exp( ) exp( )f s s sξ µ µ ξ µ µ= − + − and mean [ ]E S (We let
1 3 / 4ξ = , 2 1/ 4ξ = , 1 3µ = , and 2 1µ = in all numerical examples, and
therefore [ ] 0.5E S = );
repair time of the server is a 3-stage Erlang distribution with mean [ ]E R .
First, we select 0.6λ = , 0.55p = , [ ] 0.5E S = , [ ] 5.0E V = , [ ] 1.0E U = , and
change in specific values ( , [ ])E Rα . The numerical results of the optimal threshold and
its minimum expected cost are summarized in Table 1. One easily sees from Table 1 that
the optimal threshold and its minimum expected cost slightly change when α is from
0.05 to 0.3 or [ ]E R from 0.2 to 1.0.
Table 1: The optimal threshold *N and its minimum expected cost *( )F N
( 0.6, λ = 0.55,p = [ ] 0.5, [ ] 5.0, [ ] 1.0)E S E V E U= = = .
( , [ ])E Rα (0.2, 0.2) (0.2, 0.5) (0.2, 1) (0.3, 0.5) (0.1, 0.5) (0.05, 0.5)
*N 25 25 24 24 25 25
*( )F N 59.982 62.716 67.263 64.981 60.439 59.301
J.-C. Ke / The Optimal Control in Batch Arrival Queue 54
Finally, we select 0.6λ = , 0.45p = , 0.05α = , [ ] 0.5E S = , [ ] 0.4E R = , and
change in specific values ( [ ], [ ])E V E U . The numerical results of the optimal threshold
and its minimum expected cost are summarized in Table 2. We observe from Table 2 that
the optimal threshold *N and the minimum expected cost *( )F N increase as [ ]E V or
[ ]E U increase.
Table 2: The optimal threshold *N and its minimum expected cost *( )F N
( 0.6λ = , 0.45, 0.05, [ ] 0.5, [ ] 0.4) p E S E Rα= = = = .
( [ ], [ ])E V E U (10, 2) (5, 2) (1, 2) (5, 5) (5, 10) (5, 15)
*N 35 34 12 36 39 41
*( )F N 74.139 70.423 50.322 74.743 81.237 87.130
8. CONCLUSIONS
For the N policy M[x]/G/1 queuing system, we easily derived some important
system characteristics through the key probability - generating function and
decomposition property. We also performed a numerical analysis between the optimal
value N and the specific values of system parameters. The model is significant since
more general situations in practical applications are considered in the model.
REFERENCES
[1] Baba, Y., "On the Mx/G/1 queue with vacation time", Operations Research Letters, 5 (1986)
93-98.
[2] Baker, K.R., "A note on operating policies for the queue M/M/1 with exponential startup",
INFOR, 11 (1973) 71-72.
[3] Borthakur, A., Medhi, J., and Gohain, R., "Poisson input queueing systems with startup time
and under control operating policy", Computers Ops Res., 14 (1987) 33-40.
[4] Chae, K.C., and Lee, H.W., "Mx/G/1 vacation models with N-policy: Heuristic interpretation
of the mean waiting time", Journal of the Operational Research Society, 46 (1995) 258-264.
[5] Doshi, B.T., "Queueing system with vacations – A survey", Queueing Systems, 1 (1986) 29-
66.
[6] Fuhrmann, S.W., and Cooper, R.B., "Stochastic decompositions in the M/G/1 queue with
generalized vacations", Operations Research, 33 (1985) 1117-1129.
[7] Hur, S., and Paik, S.J., "The effect of different arrival rates on the N-policy of M/G/1 with
server setup", Applied Mathematical Modelling, 23 (1999) 289-299.
[8] Kella, O., "The threshold policy in the M/G/1 queue with server vacations", Naval. Res.
Logist., 36 (1989) 111-123.
[9] Kleinrock, L., Queueing Systems, Vol. 1, Wiley, New York, 1975.
[10] Lee, S.S., Lee, H.W., and Chae, K.C., "On a batch arrival queue with N policy and single
vacation", Computers Ops Res., 22 (1995) 173-189.
J.-C. Ke / The Optimal Control in Batch Arrival Queue 55
[11] Lee, H.W., Lee, S.S., Park, J.O., and Chae, K.C., "Analysis of Mx/G/1 queue with N policy
and multiple vacations", J. Appl. Prob., 31 (1994) 467-496.
[12] Lee, H.W., and Park, J.O., "Optimal strategy in N-policy production system with early set-
up", Journal of the Operational Research Society, 48 (1997) 306-313.
[13] Lee, H.S., and Srinivasan, M.M., "Control policies for the Mx/G/1 queueing system",
Management Science, 35 (1989) 708-721.
[14] Levy, Y., and Yechiali, U., "Utilization of idle time in an M/G/1 queueing system",
Management Science, 22 (1975) 202-211.
[15] Medhi, J., and Templeton, J.G.C., "A Poisson input queue under N-policy and with a general
start up time", Computers Opns Res., 19 (1992) 35-41.
[16] Minh, D.L., "Transient solutions for some exhaustive M/G/1 queues with generalized
independent vacations", European Journal of Operational Research, 36 (1988) 197-201.
[17] Takagi, H., Queueing Analysis: A Foundation of Performance Evaluation, Vol. I, Vacation
and Priority Systems, Part I., North-Holland, Amsterdam, 1991.
[18] Takagi, H., "M/G/1/K queues with N-policy and setup times", Queueing Systems, 14 (1993)
79-98.
[19] Tang, Y.H., "A single-server M/G/1 queueing system subject to breakdowns - some reliability
and queueing problem", Microelectron. Reliab., 37 (1997) 315-321.
[20] Wang, K.-H., "Optimal operation of a Markovian queueing system with a removable and non-
reliable server", Microelectron. Reliab., 35 (1995) 1131-1136.
[21] Wang, K.-H., "Optimal control of an M/Ek/1 queueing system with removable service station
subject to breakdowns", Journal of the Operational Research Society, 48 (1997) 936-942.
[22] Wang, K.-H., Chang, K.-W., and Sivazlian, B.D., "Optimal control of a removable and non-
reliable server in an infinite and a finite M/H2/1 queueing system", Applied Mathematical
Modelling, 23 (1999) 651-666.
Các file đính kèm theo tài liệu này:
- the_optimal_control_in_batch_arrival_queue_with_server_vacat.pdf