Documents

jurnal 1.pdf

Description
Applied Mathematical Modelling 38 (2014) 4705–4716 Contents lists available at ScienceDirect Applied Mathematical Modelling journal homepage: www.elsevier.com/locate/apm Asymptotic stability of the M/G/1 queueing system with optional second service q Chao Gao a,⇑, Xing-Min Chen b, Fu Zheng c, Guangtian Zhu d a School of Information Science and Engineering, Dalian Polytechnic University, Dalian 116034, PR China School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, P
Categories
Published
of 12
22
Categories
Published
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Similar Documents
Share
Transcript
  Asymptotic stability of the M/G/1 queueing system withoptional second service q Chao Gao a, ⇑ , Xing-Min Chen b , Fu Zheng c , Guangtian Zhu d a School of Information Science and Engineering, Dalian Polytechnic University, Dalian 116034, PR China b School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, PR China c Department of Mathematics, Bohai University, Jinzhou 121002, PR China d  Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, PR China a r t i c l e i n f o  Article history: Received 19 October 2012Received in revised form 3 March 2014Accepted 20 March 2014Available online 31 March 2014 Keywords:C  0 -semigroupQueueing systemStability conditionAsymptotic stability a b s t r a c t AnM/G/1queueingsystemwithsecondoptionalserviceisconsideredinthispaper.Wearedevoted to studying the asymptotic stability of this kind of system by using  C  0 -semigrouptheory.Byanalyzingthespectral distributionofthesystemoperator, wederivethat0isaneigenvalue and is the only spectral point on the imaginary axis. It shows that thetime-dependent solution of the system converges to the steady-state solution as timeapproaches infinity. Using the steady-state solution, we obtain the mean queue length.   2014 Elsevier Inc. All rights reserved. 1. Introduction Varieties of systems based on the classical M/G/1 queueing system, such as M/G/1 queueing system with vacations [1],withserver breakdowns [2] etc., have been studied in the literature because of their prevalence in traffic, logistics, telecom-munication systems etc. Generally, it is assumed that the systemonly provides one service and customer leaves the systemas soon as service is completed. In practice, there are many situations in which the queues provide main service andsubsidiary service for every customer. For examples:   After all students complete their undergraduate program, some of them may join the postgraduate program. A surveyshows that over 83% of 1135 participants continued to plan for postgraduate education in the sciences following theirundergraduate research experience (see Ref. [3]).   After final products are produced in the supply chain process, they may be transported to retailers directly, or may betransported to the retailers indirectly through distribution facilities (see Ref. [4]).Basing on the actual background, Madan proposed an M/G/1 queue with second optional service [5], where all arrivingcustomers are providedwiththe first essential service (FES). The service times of the two phases are mutuallyindependent.After the FES is completed, the customer may immediately choose the second optional service (SOS) with probability  h  or http://dx.doi.org/10.1016/j.apm.2014.03.0320307-904X/   2014 Elsevier Inc. All rights reserved. q This work is supported by the National Natural Science Foundation of China under Grant Nos. 11201037 and 61203118. ⇑ Corresponding author. E-mail address:  gaochao198604@126.com (C. Gao).Applied Mathematical Modelling 38 (2014) 4705–4716 Contents lists available at ScienceDirect Applied Mathematical Modelling journal homepage: www.elsevier.com/locate/apm  leavethesystemwithprobability1   h .Thus,when h  ¼  0itcorrespondstotheclassicalM/G/1queueingsystem;when h  ¼  1it means that every customer chooses the SOS. The system is different from the M/G/1 system with feedback [6]. The lattermay model a system in which after being served each customer either joins the queue for the same service again withprobability  p  or leave the system with probability 1   p .MadanmodeledthesystemwithtwophasesofserviceinwhichtheservicetimeoftheFESisassumedtofollowageneraldistribution, whereas the one of the SOS follows exponential. By using Laplace transform, the time-dependent probabilitygenerating functions and corresponding steady-state results have been obtained in [5]. Then, Medhi extended the systemto a general case where the service time of the SOS is assumed to follow a general distribution. Transient solution andsteady-state solution were derived in [7]. Basing on the system, Choudhury obtained more generalized results in [8]. The steady-state results were obtained under the stability condition  k R  1 0  e  R   x 0 l 1 ð n Þ d n d  x  þ  kh R  1 0  e  R   x 0 l 2 ð n Þ d n d  x < 1 in the abovetwo literatures. Here  k  is the arrival rate of customers, and  l 1 ð  x Þ ;  l 2 ð  x Þ  are the service rates of the FES and the SOS,respectively. Although the steady-state results have been obtained, whether or not the time-dependent solution convergesto the steady-state solution as time approaches infinity has not been proven yet.The classical M/G/1 queueing systems have received a great deal of attention and many excellent methods have beenintroducedintheliterature,suchasprobabilitygeneratingfunction[9],stochasticdecomposition[10],singularperturbation method [11], Markov jump processes [12], semigroup theory [13,14], matrix analysis [15,16], etc. However, most results were based on the hypothesis that the systemconcerned has a unique time-dependent solution. It’s worth mentioning thatthe hypothesis was verified by introducing semigroup theory into queueing systems in [13]. When the service rate satisfies l < 1 ,theexistenceanduniquenessoftime-dependentsolutionoftheM/M/1queueingsystemhasbeenproved.Moreover,thespectral distributionof theM/M/1systemoperatorwasanalyzed. Asaresult, thetime-dependentsolutionof theM/M/1queueing system strongly converges to the steady-state solution under the stability condition  k l < 1, as time approachesinfinity. Here,  k  is the customer arrival rate of the M/M/1 system. Similarly, the well-posedness of the classical M/G/1queueing system has been proved in [13] with satisfying sup  x 2½ 0 ; 1Þ l ð  x Þ < 1 . But asymptotic result of the classical M/G/1system was not given there.The key to stability analysis is the investigation of spectral distribution of the system operator on the imaginary axis.However, the variables are coupled with each other in the M/G/1 system equations, and boundary conditions are even of integral form. It is hard to obtain an explicit solution of the system. Thus, to verify the existence of the nonzero eigenvectorcorresponding to eigenvalue 0 is a challenge. So is the solution of the resolvent equation. As yet only a few of articles haveappearedonstabilityanalysisoftheclassicalM/G/1system.Zhengetal.[17]assumedthattheserverrate l ð  x Þ andthearriverate  k  satisfy 8  x  >  0 ;  9 l  >  k  >  0 ;  s : t :  1  x Z   x 0 l ð n Þ d n  >  l  ð C1 Þ and used a technique to prove the asymptotic stability of the classical M/G/1 system. But it is a pity that the technique onlysuits condition (C1) rather than the stability condition  k R  1 0  e  R   x 0 l ð n Þ d n d  x < 1. Assuming k Z   1 0 e  R   x 0 l ð n Þ d n d  x  <  1 ;  0  <  inf   x 2½ 0 ; 1Þ l ð  x Þ 6  sup  x 2½ 0 ; 1Þ l ð  x Þ  <  1 ;  ð C2 Þ Gupur[14]obtainedthesameresultfortheclassicalM/G/1systemwithsomedifficultyandexplainedwhythesystemisnotexponentially stable. Nonetheless, condition (C2) is almost perfect except that the infimum of service rate is not equal tozero.In this paper, we consider the M/G/1 queue system with the SOS proposed in [8], with the service rate  l i ð  x Þ  satisfying k Z   1 0 e  R   x 0 l 1 ð n Þ d n d  x  þ  kh Z   1 0 e  R   x 0 l 2 ð n Þ d n d  x  <  1 ; where 0 6 l i ð  x Þ 6 sup  x 2½ 0 ; 1Þ l i ð  x Þ < 1 ;  i  ¼  1 ; 2. The well-posedness of the system has been investigated in Ref. [18]. Wegeneralizethetechniqueof [17]toderivethat0isaneigenvalueoftheM/G/1systemoperator.Andweuseashortandclearmethodtocompletetherestoftheproofwithoutrequiringinf   x 2½ 0 ; 1Þ l i ð  x Þ – 0 ;  i  ¼  1 ; 2.ThenbyusingTheorem14inRef.[13]we deduce that the time-dependent solution of the M/G/1 system with optional second service strongly converges to thesteady-state solution.The rest of the paper is organized as follows. The system is transformed into a mathematical problem in Section 2. Themain results are given in Section 3. And a brief conclusion is presented in Section 4. 2. System formulation The systemmodel is described specifically as follows: the systemhas a single server and customers arrive at the systemonebyoneaccordingtoaPoissonstreamwitharrivalrate k  ð k > 0 Þ .Allarrivingcustomersareprovidedwiththefirstessen-tial service. On completionof the first essential service, a customer may opt for the second optional service withprobability h  ð 0 6 h 6 1 Þ  or may opt to leave the system with probability 1   h . The service time of the two phases of service are 4706  C. Gao et al./Applied Mathematical Modelling 38 (2014) 4705–4716   mutually independent. Further, assuming  P  0 ; 0 ð t  Þ  represents the probability that there is no customer in the system at time t  ;  P  1 ;  j ð  x ; t  Þ d  x  denotestheprobabilityattime t  thatthereare  j customersinthequeueandonecustomerisbeingprovidedthefirstessentialservicewithelapsedservicetimelyingin ½  x ;  x  þ d  x Þ ;  j P 0 ;  P  2 ;  j ð  x ; t  Þ d  x  istheprobabilityattime t  thatthereare  j  customers in the queue and one customer is being provided the second optional service with elapsed service time lying in ½  x ;  x  þ d  x Þ ;  j P 0 ;  l 1 ð  x Þ  and  l 2 ð  x Þ  are essential service rate and optional service rate, respectively.Henceforth, assuming that the system is empty at the initial time  t   ¼  0. Then, the differential-integral equations of thesystem are as follows [18]: dd t þ  k   P  0 ; 0 ð t  Þ ¼ ð 1   h Þ Z   1 0 l 1 ð  x Þ P  1 ; 0 ð  x ; t  Þ d  x  þ Z   1 0 l 2 ð  x Þ P  2 ; 0 ð  x ; t  Þ d  x ;  ð 1 Þ @ @  t   þ  @ @   x   P  i ; 0 ð  x ; t  Þ ¼ ð k  þ l i ð  x ÞÞ P  i ; 0 ð  x ; t  Þ ;  i  ¼  1 ; 2 ;  ð 2 Þ @ @  t   þ  @ @   x   P  i ;  j ð  x ; t  Þ ¼ ð k  þ l i ð  x ÞÞ P  i ;  j ð  x ; t  Þ þ  k P  i ;  j  1 ð  x ; t  Þ ;  i  ¼  1 ; 2 ;  j P 1 :  ð 3 Þ The boundary conditions are P  1 ; 0 ð 0 ; t  Þ ¼  k P  0 ; 0 ð t  Þ þ ð 1   h Þ Z   1 0 l 1 ð  x Þ P  1 ; 1 ð  x ; t  Þ d  x  þ Z   1 0 l 2 ð  x Þ P  2 ; 1 ð  x ; t  Þ d  x ;  ð 4 Þ P  1 ;  j ð 0 ; t  Þ ¼ ð 1   h Þ Z   1 0 l 1 ð  x Þ P  1 ;  j þ 1 ð  x ; t  Þ d  x  þ Z   1 0 l 2 ð  x Þ P  2 ;  j þ 1 ð  x ; t  Þ d  x ;  j P 1 ;  ð 5 Þ P  2 ;  j ð 0 ; t  Þ ¼  h Z   1 0 l 1 ð  x Þ P  1 ;  j ð  x ; t  Þ d  x ;  j P 0 :  ð 6 Þ The initial conditions are P  0 ; 0 ð 0 Þ ¼  1 ;  P  i ;  j ð  x ; 0 Þ ¼  0 ;  i  ¼  1 ; 2 ;  j P 0 :  ð 7 Þ Concerning the practical background, assume that 0 6 l i ð  x Þ 6  sup  x 2½ 0 ; 1Þ l i ð  x Þ  <  1 ;  k Z   1 0 e  R   x 0 l i ð n Þ d n d  x  <  1 ;  i  ¼  1 ; 2 ;  ð H1 Þ k Z   1 0 e  R   x 0 l 1 ð n Þ d n d  x  þ  kh Z   1 0 e  R   x 0 l 2 ð n Þ d n d  x  <  1 :  ð H2 Þ Remark 1.  Condition(H1)abouttheserviceratesisnaturalinpracticalapplication.And(H2)isthestabilityconditionunder which the steady-state solution exists [7,8].Define the state of system (1)–(3) by ð P  ð 1 Þ ; P  ð 2 Þ Þð ; t  Þ ¼ P  0 ; 0 ð t  Þ P  1 ; 0 ð  x ; t  Þ P  1 ; 1 ð  x ; t  Þ ... 0BBBB@1CCCCA ; P  2 ; 0 ð  x ; t  Þ P  2 ; 1 ð  x ; t  Þ P  2 ; 2 ð  x ; t  Þ ... 0BBBB@1CCCCA0BBBB@1CCCCA ;  t  P 0 : Take a state space as follows:  X     Y   ¼ ð P  ð 1 Þ ; P  ð 2 Þ Þj P  ð 1 Þ 2  X  ;  P  ð 2 Þ 2  Y  ;  ð P  ð 1 Þ ; P  ð 2 Þ Þ  ¼  P  ð 1 Þ   X  þ  P  ð 2 Þ  Y  n o ; where  X   ¼  P  ð 1 Þ j P  ð 1 Þ 2 R   L 1 ½ 0 ; 1Þ   L 1 ½ 0 ; 1Þ   ;  P  ð 1 Þ   X  ¼  P  0 ; 0  þ X 1  j ¼ 0 Z   1 0 P  1 ;  j ð  x Þ  d  x  <  1 ( ) ; Y   ¼  P  ð 2 Þ j P  ð 2 Þ 2  L 1 ½ 0 ; 1Þ   L 1 ½ 0 ; 1Þ   ;  P  ð 2 Þ  Y  ¼ X 1  j ¼ 0 Z   1 0 P  2 ;  j ð  x Þ  d  x  <  1 ( ) : Obviously  X     Y   is a Banach space. For convenience, we introduce the operator  A  on  X     Y  , C. Gao et al./Applied Mathematical Modelling 38 (2014) 4705–4716   4707   A ð P  ð 1 Þ ; P  ð 2 Þ Þ ¼ k P  0 ; 0  þ ð 1   h Þ R  1 0  l 1 ð  x Þ P  1 ; 0 ð  x Þ  x  þ R  1 0  l 2 ð  x Þ P  2 ; 0 ð  x Þ  x   dd  x  þ  k  þ l 1 ð  x Þ   P  1 ; 0 ð  x Þ  dd  x  þ  k  þ l 1 ð  x Þ   P  1 ; 1 ð  x Þ þ  k P  1 ; 0 ð  x Þ  dd  x  þ  k  þ l 1 ð  x Þ   P  1 ; 2 ð  x Þ þ  k P  1 ; 1 ð  x Þ ... 0BBBBBBBB@1CCCCCCCCA ;   dd  x  þ  k  þ l 2 ð  x Þ   P  2 ; 0 ð  x Þ  dd  x  þ  k  þ l 2 ð  x Þ   P  2 ; 1 ð  x Þ þ  k P  2 ; 0 ð  x Þ  dd  x  þ  k  þ l 2 ð  x Þ   P  2 ; 2 ð  x Þ þ  k P  2 ; 1 ð  x Þ  dd  x  þ  k  þ l 2 ð  x Þ   P  2 ; 3 ð  x Þ þ  k P  2 ; 2 ð  x Þ ... 0BBBBBBBB@1CCCCCCCCA0BBBBBBBB@1CCCCCCCCA ; and the definition of   A  is as follows: D ð  A Þ ¼ ð P  ð 1 Þ ; P  ð 2 Þ Þ 2  X     Y  d P  i ;  j ð  x Þ d  x  2  L 1 ½ 0 ; 1Þ ; P  i ;  j ð  x Þ  is anabsolutely continuous function and P  ð 1 Þ ð 0 Þ ¼ X 2 k ¼ 1 R  1 0  C k ð  x Þ P  ð k Þ ð  x Þ d  x ; P  ð 2 Þ ð 0 Þ ¼ R  1 0  C 3 ð  x Þ P  ð 1 Þ ð  x Þ d  x 8>>>>>>><>>>>>>>:9>>>>>>>=>>>>>>>; ; where  i  ¼  1 ; 2 ;  j P 0, C 1 ð  x Þ ¼ e   x 0 0 0   k e   x 0  ð 1   h Þ l 1 ð  x Þ  0   0 0 0  ð 1   h Þ l 1 ð  x Þ ............ 0BBBB@1CCCCA ; C 2 ð  x Þ ¼ 0 0 0   0  l 2 ð  x Þ  0   0 0  l 2 ð  x Þ ......... 0BBBB@1CCCCA ;  C 3 ð  x Þ ¼ 0  h l 1 ð  x Þ  0 0   0 0  h l 1 ð  x Þ  0   0 0 0  h l 1 ð  x Þ 0 0 0 0  ............... 0BBBBBBB@1CCCCCCCA : Then, Eqs. (1)–(7) can be written into an abstract Cauchy problem in the Banach space  X     Y  : dd t  ð P  ð 1 Þ ; P  2 Þð ; t  Þ ¼  A ð P  ð 1 Þ ; P  ð 2 Þ Þð ; t  Þ ;  t   >  0 ; ð P  ð 1 Þ ; P  ð 2 Þ Þð ; 0 Þ ¼ ðð 1 ; 0 ; 0 ; . . . Þ T ;  ð 0 ; 0 ; 0 ; . . . Þ T Þ : (  ð 8 Þ Thefollowingresultsontheuniqueexistenceofthesolutionofsystem(8),whichhavebeenobtainedinRef.[18]byusing C  0 -semigroup theory, are necessary foundations for the next section.  Theorem 2.1.  Under condition ( H1 ), the system operator A generates a positive contraction C  0 -semigroup T  ð t  Þ .  Theorem 2.2.  Under condition ( H1 ), the system ( 8 ) has a unique positive time-dependent solution  ð P  ð 1 Þ ; P  ð 2 Þ Þð ; t  Þ ¼  T  ð t  Þð P  ð 1 Þ ; P  ð 2 Þ Þð ; 0 Þ , and  ð P  ð 1 Þ ; P  ð 2 Þ Þð ; t  Þ   ¼  1 ;  t  P 0 . 3. Main results In this section, we will analyze the spectral distribution of the M/G/1 systemoperator  A . It is necessary to verify that 0 isan eigenvalue and  f i v  j v   2 R ;  v  – 0 g  belongs to the resolvent set of the M/G/1 system operator  A .Prior to proceeding to the spectral analysis, we will derive several properties of relative series. First of all, we introducethe following notations for convenience: b i ;  j ð c Þ ¼ Z   1 0 ð k  x Þ  j  j !  l i ð  x Þ e  R   x 0 ð c þ k þ l i ð n ÞÞ d n d  x ;  i  ¼  1 ; 2 ;  j P 0 ;  ð 9 Þ b i ;  j  ¼ Z   1 0 ð k  x Þ  j  j !  l i ð  x Þ e  R   x 0 ð k þ l i ð n ÞÞ d n d  x ;  i  ¼  1 ; 2 ;  j P 0 ;  ð 10 Þ c  i ;  j ð c Þ ¼  k Z   1 0 ð k  x Þ  j  j !  e  R   x 0 ð c þ k þ l i ð n ÞÞ d n d  x ;  i  ¼  1 ; 2 ;  j P 0 ;  ð 11 Þ c  i ;  j  ¼  k Z   1 0 ð k  x Þ  j  j !  e  R   x 0 ð k þ l i ð n ÞÞ d n d  x ;  i  ¼  1 ; 2 ;  j P 0 ;  ð 12 Þ 4708  C. Gao et al./Applied Mathematical Modelling 38 (2014) 4705–4716 
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x