The optimal control in batch arrival queue with server vacations, startup and breakdowns

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.

pdf15 trang | Chia sẻ: huongthu9 | Lượt xem: 523 | Lượt tải: 0download
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:

  • pdfthe_optimal_control_in_batch_arrival_queue_with_server_vacat.pdf