第2章 離散事件系統(tǒng)仿真

1、生產(chǎn)系統(tǒng)建模與仿真生產(chǎn)系統(tǒng)建模與仿真 Modeling and Simulation of Production System第第2章章 離散事件系統(tǒng)仿真基礎(chǔ)離散事件系統(tǒng)仿真基礎(chǔ) 第2章 離散事件系統(tǒng)仿真基礎(chǔ) 2.1 基本概念 2.2 蒙特卡洛方法 2.3 離散事件系統(tǒng)仿真的基本原理 2.4 離散事件系統(tǒng)仿真的一般步驟 基本要求v了解蒙特卡洛方法的應(yīng)用v了解離散事件系統(tǒng)仿真的一般步驟v 了解離散事件系統(tǒng)仿真基本原理v 理解離散事件系統(tǒng)仿真的基本要素v 理解蒙特卡洛方法的基本思想離散事件系統(tǒng)離散事件系統(tǒng)v零件并行加工系統(tǒng)離散事件系統(tǒng)v零件簡單加工系統(tǒng)離散事件系統(tǒng)v 系統(tǒng)狀態(tài)是離散變化的，而引發(fā)狀

2、態(tài)變化的事系統(tǒng)狀態(tài)是離散變化的，而引發(fā)狀態(tài)變化的事件是隨機(jī)發(fā)生的，因此這類系統(tǒng)的模型很難用數(shù)件是隨機(jī)發(fā)生的，因此這類系統(tǒng)的模型很難用數(shù)學(xué)方程來描述。學(xué)方程來描述。v由于離散事件系統(tǒng)固有的隨機(jī)性由于離散事件系統(tǒng)固有的隨機(jī)性 ,對(duì)這類系統(tǒng)的對(duì)這類系統(tǒng)的研究往往十分困難。經(jīng)典的概率及數(shù)理統(tǒng)計(jì)理論研究往往十分困難。經(jīng)典的概率及數(shù)理統(tǒng)計(jì)理論和隨機(jī)過程理論雖然為之提供了理論基礎(chǔ)和隨機(jī)過程理論雖然為之提供了理論基礎(chǔ),并并 能能對(duì)一些簡單系統(tǒng)提供解析解對(duì)一些簡單系統(tǒng)提供解析解,但對(duì)于實(shí)際工程中的但對(duì)于實(shí)際工程中的大量系統(tǒng)大量系統(tǒng) ,唯有依靠計(jì)算機(jī)仿真技術(shù)才能提供較唯有依靠計(jì)算機(jī)仿真技術(shù)才能提供較為完整的結(jié)果。

3、為完整的結(jié)果。 離散事件系統(tǒng)仿真的基本要素v實(shí)體 (Entity) v屬性 (Attribute) v狀態(tài) (State) v事件(Event) v活動(dòng)(Activity) v進(jìn)程(Process) v仿真時(shí)鐘(Simalation Clock) v統(tǒng)計(jì)累加器 (Statistical Accumulator)離散事件系統(tǒng)仿真的基本要素v實(shí)體 (Entity) 通常是指需要在模型中明確表示的系統(tǒng)中的任何對(duì)象或要素,是描述系統(tǒng) 的三個(gè)基本要素 (即實(shí)體 、屬性、活動(dòng))之一。v臨時(shí)實(shí)體 、永久實(shí)體 在系統(tǒng)中只存在一段時(shí)間的實(shí)體,通常被稱為臨時(shí)實(shí)體 。到達(dá) 通過 離開 永久駐留在系統(tǒng)中的實(shí)體。是系統(tǒng)

4、活動(dòng)的必要條件。 離散事件系統(tǒng)仿真的基本要素v屬性 (Attribute) 離散事件系統(tǒng)仿真的基本要素v屬性選取原則 :v 便于實(shí)體的分類 。v 便于對(duì)實(shí)體行為的捕述。v 便于排隊(duì)規(guī)則的確定 。離散事件系統(tǒng)仿真的基本要素v狀態(tài) (State) 系統(tǒng)中所有實(shí)體的屬性的集合 ,它包含了描述系統(tǒng)在任何時(shí)間所必需的所有信息。例如：進(jìn)行作業(yè)的操作工人數(shù)、等待服務(wù)隊(duì)列中的工件數(shù) ,或正在加工處理中的工件數(shù) 以及下一個(gè)工件到達(dá)加工設(shè)備的時(shí)間等。 離散事件系統(tǒng)仿真的基本要素v事件(Event) 指引起系統(tǒng)狀態(tài)發(fā)生變化的事情。 離散事件系統(tǒng)仿真的基本要素v活動(dòng)(Activity) 實(shí)體在兩個(gè)事件之間保持某一狀態(tài)

5、的持續(xù)過程稱為活動(dòng)(Activity)。 例如，在上述簡單加工系統(tǒng)中，一個(gè)零件從“開始加工”到“加工結(jié)束”可看做是一個(gè)“加工”活動(dòng)。 離散事件系統(tǒng)仿真的基本要素v進(jìn)程(Process) 進(jìn)程(Process)描述了它所包括的事件及活動(dòng)之間的邏輯關(guān)系和時(shí)序關(guān)系，一個(gè)進(jìn)程由與某類實(shí)體相關(guān)的若干有序事件及活動(dòng)組成。 例如：把一個(gè)零件到達(dá)系統(tǒng)、等待加工(排隊(duì))、開始加工、加工結(jié)束離開系統(tǒng)的過程看做是一個(gè)進(jìn)程。事件、活動(dòng)和進(jìn)程之間的關(guān)系 離散事件系統(tǒng)仿真的基本要素v進(jìn)程(Process) 離散事件系統(tǒng)仿真的基本要素v仿真時(shí)鐘(Simalation Clock) 用于記錄仿真過程中當(dāng)前時(shí)間的一個(gè)特殊變量。

6、 離散事件系統(tǒng)仿真的基本要素v統(tǒng)計(jì)累加器 (Statistical Accumulator) 統(tǒng)計(jì)累加器的構(gòu)件, 用來跟蹤記錄各種輸出性能指標(biāo)在仿真進(jìn)程中的中間結(jié)果,通過統(tǒng)計(jì)分析，得到更有價(jià)值的信息。 例如在上述的簡單加工系統(tǒng)中,通常用于觀察的性能指標(biāo)主要有：迄今為止所加工完的零件數(shù)量、系統(tǒng)平均隊(duì)長、零件平均等待時(shí)間、最大系統(tǒng)逗留時(shí)間以及設(shè)備的利用率等。 蒙特卡羅方法 v蒙特卡羅方法又稱統(tǒng)計(jì)測試法、隨機(jī)抽樣技術(shù)，是一種隨機(jī)模擬方法，以概率和統(tǒng)計(jì)理論方法為基礎(chǔ)的一種計(jì)算方法，是使用隨機(jī)數(shù)（或更常見的偽隨機(jī)數(shù)）來解決很多計(jì)算問題的方法,是一種與一般數(shù)值計(jì)算方法有本質(zhì)區(qū)別的計(jì)算方法, 蒙特卡洛方法屬

7、于試驗(yàn)數(shù)學(xué)的一個(gè)分支。 蒙特卡羅方法 v基本思想 當(dāng)實(shí)驗(yàn)次數(shù)充分多時(shí),某一事件出現(xiàn)的頻率近似等于該事件發(fā)生的概率。 pnN一種一種“絕處逢生絕處逢生”的方法的方法。蒙特卡羅方法 v例子：計(jì)算單位圓形面積 對(duì)要計(jì)算的圓形構(gòu)造一個(gè)外接正方形。 在該正方形區(qū)域中隨機(jī)采樣 Ns個(gè)點(diǎn),則顯然有些點(diǎn)落在圓形內(nèi),有些點(diǎn)落在了圓形的外面。 圓形面積的計(jì)算表達(dá)式 。 蒙特卡羅方法 v例子2 假設(shè)我們有個(gè)y=x2的表達(dá)式，如何用MC方法求得函數(shù)在0,1區(qū)間的定積分呢？ 蒙特卡羅方法 蒙特卡羅方法 v蒙特卡羅方法的應(yīng)用要點(diǎn) 首先,對(duì)問題建立一個(gè)簡單且便于實(shí)現(xiàn)的概率統(tǒng)計(jì)模型 ,使要求的解恰好是所建模型的概率分布或數(shù)學(xué)

8、期望。 其次,根據(jù)概率統(tǒng)計(jì)模型的特點(diǎn)和實(shí)際計(jì)算的需要 ,對(duì)模型進(jìn)行改進(jìn) ,以便減小仿真結(jié)果的方差,降低成本 、提高效率。 再次,建立隨機(jī)變量的抽樣方法 ,其 中包括產(chǎn)生偽隨機(jī)數(shù)及各種分布隨機(jī)變量抽樣序列的方法。 最后,給出問題解的統(tǒng)計(jì)估計(jì)值及其方差或標(biāo)準(zhǔn)差 。 蒙特卡羅方法 v蒙特卡羅方法的應(yīng)用或?qū)嵤┻^程 ,主要包括如下三個(gè)步驟 :(l)構(gòu)造或描述概率過程 如例 2-2中單位圓形面積的計(jì)算,就必須事先構(gòu)造出一個(gè)人為的概率過程 ,使得它的某些參量正好是所求問題的解。(2)以已知概率分布進(jìn)行抽樣(3)建立各種估計(jì)量離散事件系統(tǒng)仿真的基本原理 v隨機(jī)離散事件 隨機(jī)離散事件主要包括:零件毛坯的到達(dá)(E

9、A)、零件在設(shè)備I上加工完畢后離開(EW1)和零件在設(shè)備上加工完畢后離開（EW2）。 離散事件系統(tǒng)仿真的基本原理 v并行加工中心系統(tǒng)的離散事件和系統(tǒng)狀態(tài) 可見，隨機(jī)發(fā)生的離散事件是導(dǎo)致系統(tǒng)狀態(tài)發(fā)生變化的原因。離散事件系統(tǒng)就是通過對(duì)這些隨機(jī)離散事件按發(fā)生時(shí)刻的先后進(jìn)行排序，并根據(jù)不同事件發(fā)生時(shí)系統(tǒng)狀態(tài)變化的影響來模擬實(shí)際系統(tǒng)運(yùn)行特性的。隨機(jī)離散事件是離散事件系統(tǒng)仿真中的要素之一，在離散事件系統(tǒng)仿真中有著特別重要的地位和作用。 離散事件系統(tǒng)仿真的基本原理 v仿真時(shí)鐘的推進(jìn)方式 仿真時(shí)鐘表示了仿真運(yùn)行的系統(tǒng)時(shí)間，是離散事件系統(tǒng)仿真中的基本組成部分之一。 （1）面向事件的仿真時(shí)鐘推進(jìn)方式 （2）面向時(shí)

10、間間隔的仿真時(shí)鐘推進(jìn)方式離散事件系統(tǒng)仿真的基本原理 v（1）面向事件的仿真時(shí)鐘推進(jìn)方式 仿真時(shí)鐘是按照下一個(gè)離散事件預(yù)計(jì)要發(fā)生的時(shí)刻, 以不同時(shí)間間隔向前推進(jìn)的。其實(shí)現(xiàn)，是對(duì)各離散事件按發(fā)生時(shí)間的先后次序進(jìn)行排列，然后仿真時(shí)鐘則按照這些事件順序發(fā)生的時(shí)刻向前推進(jìn)。 離散事件系統(tǒng)仿真的基本原理 v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v原理 離散事件系統(tǒng)仿真的基本原理v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v實(shí)例分析離散事件系統(tǒng)仿真的基本原理v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v實(shí)例分析離散事件系統(tǒng)仿真的基本原理v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v實(shí)例分析離散事件系統(tǒng)仿真的基本原理v（1）面向事件的仿真時(shí)鐘推

11、進(jìn)方式v實(shí)例分析離散事件系統(tǒng)仿真的基本原理v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v實(shí)例分析離散事件系統(tǒng)仿真的基本原理v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v實(shí)例分析離散事件系統(tǒng)仿真的基本原理v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v實(shí)例分析離散事件系統(tǒng)仿真的基本原理v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v實(shí)例分析離散事件系統(tǒng)仿真的基本原理v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v實(shí)例分析離散事件系統(tǒng)仿真的基本原理v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v實(shí)例分析離散事件系統(tǒng)仿真的基本原理v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v實(shí)例分析離散事件系統(tǒng)仿真的基本原理v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v實(shí)例分析2離散事件系統(tǒng)仿真的基本

12、原理 v（1）面向事件的仿真時(shí)鐘推進(jìn)方式v特點(diǎn) 離散事件系統(tǒng)仿真的基本原理 v（2）面向時(shí)間間隔的仿真時(shí)鐘推進(jìn)方式 在這種時(shí)鐘推進(jìn)方式下，仿真時(shí)鐘按照某一足夠小的時(shí)間間隔等距地向前推進(jìn)，使得時(shí)間間隔中基本上不會(huì)同時(shí)出現(xiàn)兩個(gè)或兩個(gè)以上的離散事件，每次仿真時(shí)鐘向前推都需要對(duì)所有活動(dòng)的完成時(shí)刻進(jìn)行掃描。 離散事件系統(tǒng)仿真的基本原理 v（2）面向時(shí)間間隔的仿真時(shí)鐘推進(jìn)方式v原理離散事件系統(tǒng)仿真的基本原理 v（2）面向時(shí)間間隔的仿真時(shí)鐘推進(jìn)方式v特點(diǎn)離散事件系統(tǒng)仿真的基本原理 v結(jié)論離散事件系統(tǒng)仿真的基本原理 v未來事件表 概念 為了在仿真執(zhí)行過程中跟蹤未來(仿真)時(shí)間假定發(fā)生的各種事件，常常需要把發(fā)生

13、時(shí)間大于仿真時(shí)鐘當(dāng)前時(shí)刻的所有事件放在一個(gè)時(shí)序列表中。這種由發(fā)生時(shí)間大于當(dāng)前時(shí)刻的隨機(jī)離散事件所構(gòu)成的時(shí)序列表，即被稱為未來事件表( Future Event Calendar)。 事件按其所發(fā)生的時(shí)間順序由先向后排列 離散事件系統(tǒng)仿真的基本原理 v未來事件表離散事件系統(tǒng)仿真的基本原理 v在仿真執(zhí)行的過程中，當(dāng)t = TNOW時(shí)，系統(tǒng)中應(yīng)包括以下內(nèi)容: 被仿真系統(tǒng)在t時(shí)所處的狀態(tài)。 系統(tǒng)在t時(shí)正在執(zhí)行的活動(dòng)。 由t時(shí)刻發(fā)生事件所產(chǎn)生的新的未來事件以及由它們構(gòu)成的未來事件表。系統(tǒng)統(tǒng)計(jì)數(shù)據(jù)的當(dāng)前值和累計(jì)數(shù)等。 離散事件系統(tǒng)仿真的基本原理 v未來事件產(chǎn)生的邏輯關(guān)系 離散事件系統(tǒng)仿真的基本原理 v 未

14、來事件時(shí)刻表生成未來事件表的長度和內(nèi)容都是隨著仿真過程的推進(jìn)而不斷變化的未來事件表的長度和內(nèi)容都是隨著仿真過程的推進(jìn)而不斷變化的它不僅是仿真時(shí)鐘向前推進(jìn)的依據(jù)，同時(shí)也是控制仿真運(yùn)行的依據(jù)。它不僅是仿真時(shí)鐘向前推進(jìn)的依據(jù)，同時(shí)也是控制仿真運(yùn)行的依據(jù)。離散事件系統(tǒng)仿真的基本原理 離散事件系統(tǒng)仿真的基本原理 v例子簡單加工系統(tǒng)仿真運(yùn)行（零件的到達(dá)、零件加工完后離開和仿真的結(jié)束，各事件處理的內(nèi)容 ） 離散事件系統(tǒng)仿真的基本原理 離散事件系統(tǒng)仿真的基本原理 離散事件系統(tǒng)仿真的基本原理 離散事件系統(tǒng)仿真的基本原理 v仿真運(yùn)行的終止 1.規(guī)定仿真運(yùn)行時(shí)間長度TE 當(dāng)仿真時(shí)鐘推進(jìn)到時(shí)刻TE (即TNOWTE)時(shí)，則仿真運(yùn)行終止。2.規(guī)定某個(gè)未來事件E 在仿真運(yùn)行中，如果系統(tǒng)發(fā)現(xiàn)規(guī)定的某個(gè)未來事件E已經(jīng)發(fā)生，則立即終