A6離散事件系統(tǒng)仿真基礎(chǔ).ppt

離散事件動(dòng)態(tài)系統(tǒng)仿真基礎(chǔ),離散事件動(dòng)態(tài)系統(tǒng)系統(tǒng)的狀態(tài)只是在離散時(shí)間點(diǎn)上發(fā)生變化， 而且這些離散時(shí)間點(diǎn)一般是不確定的。 由于離散事件系統(tǒng)固有的隨機(jī)性，對(duì)這類系統(tǒng)的研究往往十分困難。 經(jīng)典的的概率及數(shù)理統(tǒng)計(jì)理論和隨機(jī)過(guò)程理論雖然為這類系統(tǒng)提供了 理論基礎(chǔ)，并能對(duì)一些簡(jiǎn)單系統(tǒng)提供解析解，但對(duì)工程實(shí)際中的大量實(shí)用系統(tǒng)，惟有依靠計(jì)算機(jī)仿真技術(shù)才能提供較為完整的結(jié)果。,隊(duì)列,服務(wù)員,排隊(duì)系統(tǒng),離散事件動(dòng)態(tài)系統(tǒng)仿真基礎(chǔ),離散事件動(dòng)態(tài)系統(tǒng)仿真基礎(chǔ),基本概念: (1)實(shí)體: 分為臨時(shí)實(shí)體和永久實(shí)體. 臨時(shí)實(shí)體-在系統(tǒng)中只存在一段時(shí)間的實(shí)體 (顧客) 永久實(shí)體-永遠(yuǎn)駐留在系統(tǒng)中的實(shí)體 (服務(wù)員) (2)事件: 引起系統(tǒng)狀態(tài)發(fā)生變化的行為.(這類系統(tǒng)是由事件來(lái)驅(qū)動(dòng)的,為了 實(shí)現(xiàn)對(duì)系統(tǒng)中的事件進(jìn)行管理,仿真模型中必須建立事件表） (3)活動(dòng): 通常用于表示兩個(gè)可以區(qū)分的事件之間的過(guò)程，它標(biāo)志著系統(tǒng)狀 態(tài)的轉(zhuǎn)移. ( 例如顧客開始接受服務(wù)到服務(wù)結(jié)束之間可稱為活動(dòng)) (4)進(jìn)程: 進(jìn)程由若干個(gè)有序事件及若干個(gè)有序 活動(dòng)組成,它描述了所包含的事件及活 動(dòng)間的相互邏輯關(guān)系及時(shí)序關(guān)系。 (5)仿真鐘: 在離散事件系統(tǒng)中仿真鐘的推進(jìn)呈 現(xiàn)跳躍性,推進(jìn)速度具有隨機(jī)性. (6)統(tǒng)計(jì)計(jì)數(shù)器: 離散事件系統(tǒng)仿真的結(jié)果具有統(tǒng)計(jì)性質(zhì).,顧客到達(dá)事件,服務(wù)開始事件,服務(wù)結(jié)束事件,排隊(duì)活動(dòng),服務(wù)活動(dòng),進(jìn)程,離散事件系統(tǒng)仿真基礎(chǔ),仿真鐘的推進(jìn)離散事件系統(tǒng)仿真的基礎(chǔ) 離散事件系統(tǒng)仿真的時(shí)鐘推進(jìn)方法有兩大類： 1）事件調(diào)度法時(shí)鐘是按下一個(gè)最早發(fā)生事件的發(fā)生時(shí)刻推進(jìn)。 舉例: 單服務(wù)臺(tái)排隊(duì)系統(tǒng) 事件表: 2）固定增量法類似于連續(xù)系統(tǒng)仿真中的定（等）步長(zhǎng)算法。,顧客到達(dá)時(shí)間間隔 A,服務(wù)員空閑?,A 15 32 24 40 22,S 43 36 34 28 ,經(jīng)過(guò)S,開始服務(wù),時(shí)間,47,15,0,58,58,71,94,事件,顧客 1到達(dá),顧客 2到達(dá),顧客 1 服務(wù)完畢,顧客 2 開始服務(wù),顧客 3 到達(dá),顧客 2 服務(wù)完畢,仿真開始,服務(wù)員狀態(tài),排隊(duì)長(zhǎng)度,0,閑,閑,閑,忙,忙,忙,忙,0,1,1,1,1,0,0,15,47,58,71,94,仿真開始,服務(wù)員,隊(duì)列,顧客,服務(wù)完畢,顧客離去,排隊(duì)等待,離散事件系統(tǒng)仿真基礎(chǔ),單服務(wù)臺(tái)排隊(duì)系統(tǒng)仿真：1918年，Erlang提出排隊(duì)系統(tǒng)，并將它用于電話系 統(tǒng)，其實(shí)質(zhì)就是研究服務(wù)臺(tái)與顧客之間的效率問(wèn)題，希望服務(wù)臺(tái)效率高，而顧客 的等待時(shí)間又不太長(zhǎng)。 排隊(duì)論又稱隨機(jī)服務(wù)理論。 （1）實(shí)體（顧客）到達(dá)模式：一般用到達(dá)時(shí)間間隔描述，可分為確定性到達(dá)及 隨機(jī)性到達(dá)。隨機(jī)性到達(dá)采用概率分布來(lái)描述，最長(zhǎng)采用泊松到達(dá)。 泊松到達(dá)在 內(nèi)到達(dá)的實(shí)體數(shù) 的概率為 其中 表示在 區(qū)間內(nèi)到達(dá)實(shí)體的個(gè)數(shù)， 為到達(dá)概率。 到達(dá)時(shí)間間隔服從指數(shù)分布，其密度函數(shù)為 為到達(dá)時(shí)間間隔。 （2）服務(wù)模式：服務(wù)臺(tái)為顧客服務(wù)的時(shí)間可以是確定性的，也可能是隨機(jī)的。隨機(jī)的服務(wù)時(shí)間也用概率分布來(lái)描述。,離散事件系統(tǒng)仿真基礎(chǔ),排隊(duì)系統(tǒng)的組成: 1) 到達(dá)模式 : 指動(dòng)態(tài)實(shí)體(顧客)按怎樣的規(guī)律到達(dá); 2) 服務(wù)模式 : 指同一時(shí)刻有多少服務(wù)設(shè)備可以接納動(dòng)態(tài)實(shí)體,它們的服務(wù) 需要多少時(shí)間; 3) 排隊(duì)模式: 指對(duì)下一個(gè)實(shí)體服務(wù)的選擇原則,通常采用: FIFO 先進(jìn)先出 LIFO 后進(jìn)先出 SIRO 隨機(jī)服務(wù),動(dòng)態(tài)實(shí)體,排隊(duì),服務(wù)機(jī)構(gòu),離散事件系統(tǒng)仿真基礎(chǔ),研究排隊(duì)系統(tǒng)的目的是為了得到系統(tǒng)的統(tǒng)計(jì)性能，比較普遍使用的性能有以下四種： （1）穩(wěn)態(tài)平均延誤時(shí)間 ：（實(shí)體在隊(duì)列中的平均等待時(shí)間） 為第 個(gè)實(shí)體的延誤時(shí)間； 是接受服務(wù)的實(shí)體數(shù)。 （2）實(shí)體通過(guò)系統(tǒng)的穩(wěn)態(tài)平均滯留時(shí)間 為第 個(gè)實(shí)體通過(guò)系統(tǒng)時(shí)的滯留時(shí)間，它等于實(shí)體在隊(duì)列中的等待時(shí)間 與 該實(shí)體接受服務(wù)的時(shí)間 之和。 （3）穩(wěn)態(tài)平均隊(duì)長(zhǎng) 為 時(shí)刻的隊(duì)列長(zhǎng)度， 為系統(tǒng)運(yùn)行時(shí)間。 （4）系統(tǒng)中穩(wěn)態(tài)平均實(shí)體數(shù) 為 時(shí)刻系統(tǒng)中的實(shí)體數(shù)，它是在隊(duì)列中的實(shí)體數(shù) 與正在接受服務(wù)的實(shí)體 數(shù) 之和。,離散事件系統(tǒng)仿真基礎(chǔ),上述四個(gè)性能指標(biāo)存在的條件是服務(wù)臺(tái)的利用率為： 的定義是： 平均服務(wù)時(shí)間 平均到達(dá)時(shí)間間隔 對(duì)于 M/M/1 排隊(duì)系統(tǒng)，上述4項(xiàng)指標(biāo)可解析計(jì)算得到，即,單服務(wù)臺(tái)排隊(duì)系統(tǒng)仿真舉例,系統(tǒng)的有關(guān)參數(shù)： （1）實(shí)體到達(dá)模式：到達(dá)時(shí)間間隔 服從均值為 的指數(shù)分布，即 （2）服務(wù)模式：服務(wù)時(shí)間為 ，它也服從均值為 的指數(shù)分布，即 （3）服務(wù)規(guī)則：按 FIFO方式服務(wù)。 根據(jù)均勻分布的隨機(jī)數(shù)求指數(shù)分布的方法（反變換法）： 令 u 是取值為0，1范圍內(nèi)服從均勻分布的隨機(jī)變量，即 反變換法要求用 u 對(duì) F(A)或 F(S) 進(jìn)行取樣，即令 可得：,離散事件系統(tǒng)仿真舉例,事件調(diào)度法程序結(jié)構(gòu)： 事件類型表 仿真結(jié)果： 理論計(jì)算結(jié)果： 由 可得 所以,仿真鐘初始化，系統(tǒng)狀態(tài)初始化 事件表初始化，統(tǒng)計(jì)計(jì)數(shù)初始化,主程序,輸入仿真控制參數(shù),調(diào)用初始化子程序,調(diào)用時(shí)間控制程序,調(diào)用事件 I 子程序,仿真結(jié)束否？,調(diào)用輸出 報(bào)告子程序,主程序,操作事件表，確定下一個(gè)最早發(fā)生的事件（類型 I ）；推進(jìn)仿真鐘,修改系統(tǒng)狀態(tài)，修改統(tǒng)計(jì)計(jì)數(shù)器 產(chǎn)生將來(lái)事件，加到事件表中,根據(jù)統(tǒng)計(jì)計(jì)數(shù)器進(jìn)行統(tǒng)計(jì)分析 打印輸出報(bào)告,初始化子程序,時(shí)間控制 子程序,報(bào)告產(chǎn)生器,時(shí)間類型,服務(wù)結(jié)束，離開系統(tǒng),事件描述,屬性