




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、1,Elements of Queuing Theory,The queuing model Core components; Notation; Parameters and performance measures Characteristics; Markov Process Discrete-time Markov chain; Continuous-time Markov chain; Birth-death process; Some typical and often-used distributions Exponential Distribution; Poisson Dis
2、tribution; M/M/1 Littles Law Brief review of M/M/s, M/G/1, M/D/1 Some additional discussions.,2,Queuing Systems,Core components of the model Arrival process Buffer (the so-called queue) Infinite or finite; Service process single or parallel servers Service discipline (FIFO, random),3,Kendall Notatio
3、n for Queuing Systems (1951),a/b/s/e/p/d a, specifies the arrival process b, specifies the service process s, is the number of parallel servers in the system e, (usually ) is buffer size (i.e. maximum number of customers allowed in system) p, (usually ) is size of customer population d, is the servi
4、ce discipline (FIFO, LIFO, etc.),4,Queuing model parameters, = average rate of customer arrivals (no. of customers/unit time) = average rate of customer serviced by a server (no. of customers/unit time) (1/ = average service time) s = number of servers (channels) in the system If s , then . . . If s
5、 , then . . . The queuing systems is in steady state when the rate of departures from the system equals the rate of arrivals.,5,Performance Evaluation,6,Queuing Performance Measures,Lq = average number of customers in queue Wq = average waiting time in queue (until service starts) L = average number
6、 of customers in system = Lq + (average number being served) W = average time a customer spends in system = Wq + 1/ = utilization factor = /(s ) = fraction of time a server is busy (on average) Pn = the probability that exactly n customers are in the system Pzn = the probability that at least n cust
7、omers are in the system PW = Pzs = the probability that a customer must wait for service (or the fraction of customers who must wait at least some time in the queue),7,Markov Process,The probabilistic future of the process depends only on the current state and not upon the history of the process. In
8、 other words, the entire history of the process is summarized in the current state. Markov chain: A Markov process with discrete state space discrete-time Markov chain and continuous-time Markov chain: focus of our further discussions.,8,Discrete-Time Markov chain,9,Discrete-Time Markov chain (contd
9、),A matrix that satisfies the above properties is called a stochastic matrix.,10,Discrete-Time Markov chain (contd),The Chapman-Kolomogorov Equation:,11,Discrete-Time Markov chain (contd),Apparently,The matrix form:,12,Discrete-Time Markov chain (contd),Therefore, by solving the system of linear equ
10、ations defined by:,Where:,We get the system invariant measure or stable d.f.,It is not discussed in this course the conditions under which the above results hold. For ones who are interested, pls. refer to corresponding papers or books where detailed discussions or analysis are made.,13,Discrete-Tim
11、e Markov chain (contd),The example: one-step transition matrix:,The transition diagram:,The equilibrium equation in matrix notation:,The invariant measure:,14,Continuous-time Markov chain,The Chapman-Kolmgorov Equation for C-M.C.:,15,Continuous-time Markov chain(contd),Where:,16,Continuous-time Mark
12、ov chain(contd),By solving the following system of equations, we can get the invariant measure:,17,Continuous-time Markov chain(contd),It is not discussed in this course the conditions under which the above results hold. For ones who are interested, pls. refer to corresponding papers or books where
13、detailed discussions or analysis are made.,18,Continuous-time Markov chain (contd),The example: the Q matrix:,The transition diagram:,The equilibrium equation in matrix notation:,The invariant measure:,19,Birth-Death Process,20,Birth-Death Process (contd),Then we get the differential equation:,21,Bi
14、rth-Death Process (contd),Then we get:,Or equivalently:,The equilibrium equations or the balance equations of a birth and death process,22,Birth-Death Process (contd),The computation of p0 relies on the fact:,Cinfinite,23,Exponential Distribution,(Continuous random variable),24,Exponential Distribut
15、ion,(Continuous random variable),Memoryless Property,25,Exponential Distribution,26,Poisson distribution,(Discrete random variable),X 0, 1, 2, 3, .,X = 0, 1, 2, ., parameter,e = 2.718,Expected value of X = , Variance of X = ,27,Poisson Process,28,Poisson Process (contd),The counting process,Proof:,2
16、9,Poisson Process (contd),Proof (contd):,For n0, we have:,30,Poisson Process (contd),Proof (contd):,By noting the initial condition Pk(0) = 0, k0, solving the differential equation recursively yields the desired results.,This says, in particular, the mean number of events per time unit, or equivalen
17、tly, the rate at which events occur, is given by EN(t)/ t = . This is why is called the rate of the Poisson process.,31,Poisson Process (contd),Proof:,32,Poisson Process (contd),Additional properties of Poisson Process:,The inverse is also valid.,33,Catalogue of Queues,Single server, Poisson arrival
18、s M/G/1 M/M/1 M/D/1 Multiple servers, Poisson arrivals M/G/s M/M/s etc, etc,34,M/M/1,In summary: Arrival process is Poisson Process; Departure process is Poisson Process; Service discipline is FCFS; Work-conserving;,35,M/M/1 (contd),36,M/M/1 (contd),This parameter is often called the utilization lev
19、el of the system because it tells the average load status of the system.,The transition diagram:,37,M/M/1 (contd),Ls = Lq + Ws = Wq + 1/,38,Littles Law,Relationship between the performance measures for any queue.,39,Littles Law,40,MultiServer Systems with Exponential Service Times (M/M/s Systems), =
20、 /(s) Pn = Lq = (/ )sP0/s!(1- )2 Ls = Lq + / Wq = Lq / Ws = Wq + 1/,41,Queuing Example,Purchase two facsimile transmission (fax) machine for use of two departments. For each dept:,42,Example: Two separate queues,Modelled as two separate M/M/1 queues, we get the following performance measures:,43,36/
21、day from Design + 36/day from sales = 72items/day = M/M/2 system with = 72 items per day and =48 items per day.,Example: Common pool,44,Benefits of Pooling Servers,The result for example 2 holds in general: If customers are homogeneous, then there will be less customer waiting on average if servers
22、are pooled into one queuing system. Notice that in both systems the utilization rates are the same, so the servers do not work any harder or longer in one configuration versus the other. Instead, they work more effectively in a pooled system by coordinating their idle time so that a server is never
23、idle while other servers have queues. As long as customers can choose which queue to enter and can switch among queues, system with s queues should behave no differently than a system with one queue.,45,M/G/1 Systems,the variance of the service time = 2,46,M/D/1 Systems,When the service times are a constant, so that 2=0, we say that the service distribution is deterministic. Everything else being equal, the more variation in ser
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 安全生產(chǎn)服務(wù)月
- 職業(yè)健康培訓(xùn)課件大綱
- 2025年01B卷《中國(guó)近現(xiàn)代史綱要》參考答案
- 年鑒編纂培訓(xùn)課件下載
- 學(xué)生資助推動(dòng)一站式學(xué)生社區(qū)建設(shè)研究
- 2025至2030保險(xiǎn)基金行業(yè)發(fā)展趨勢(shì)分析與未來(lái)投資戰(zhàn)略咨詢研究報(bào)告
- 2025至2030建筑防腐行業(yè)市場(chǎng)深度分析及發(fā)展規(guī)劃及有效策略與實(shí)施路徑評(píng)估報(bào)告
- 2025至2030安全錘市場(chǎng)發(fā)展現(xiàn)狀分析及行業(yè)發(fā)展趨勢(shì)分析與未來(lái)投資戰(zhàn)略咨詢研究報(bào)告
- 2025至2030流體加熱器裝置行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 2025至2030中國(guó)客戶管理系統(tǒng)行業(yè)市場(chǎng)發(fā)展現(xiàn)狀及發(fā)展趨勢(shì)與投資報(bào)告
- 中國(guó)房地產(chǎn)開發(fā)企業(yè)esg表現(xiàn)報(bào)告-仲量聯(lián)行-202302
- GB/T 8566-2022系統(tǒng)與軟件工程軟件生存周期過(guò)程
- GB/T 20975.1-2007鋁及鋁合金化學(xué)分析方法第1部分:汞含量的測(cè)定冷原子吸收光譜法
- 設(shè)計(jì)管理資料課件
- 劍橋商務(wù)英語(yǔ)BEC(初級(jí))全套課件
- 醫(yī)療器械臨床評(píng)價(jià)課件
- 滬科版九年級(jí)物理全一冊(cè)教案(完整版)教學(xué)設(shè)計(jì)含教學(xué)反思
- DB32∕T 2880-2016 光纖傳感式橋隧結(jié)構(gòu)健康監(jiān)測(cè)系統(tǒng)設(shè)計(jì)、施工及維護(hù)規(guī)范
- 開發(fā)報(bào)建流程及細(xì)則
- 潔凈室塵埃粒子檢測(cè)規(guī)范
- 系統(tǒng)開發(fā)需求確認(rèn)單
評(píng)論
0/150
提交評(píng)論