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

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

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

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

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

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

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

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

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

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

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

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

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