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

1、 第五章第五章 離散事件系統(tǒng)仿真離散事件系統(tǒng)仿真組員：王茂馨、湯丹、施天嬌、組員：王茂馨、湯丹、施天嬌、馬慧蓉、劉珠珠、劉素瑞、劉馬慧蓉、劉珠珠、劉素瑞、劉璠、錢漾、蔡躍宇、金臻、景璠、錢漾、蔡躍宇、金臻、景象象知識點基本概念 離散事件的基本要素 離散事件系統(tǒng)仿真模型的部件和結(jié)構(gòu) 離散事件系統(tǒng)特點仿真時鐘的推進機制離散事件系統(tǒng)仿真策略 基本概念離散事件系統(tǒng)系統(tǒng)的狀態(tài)僅在離散的時間點上方式變化的系統(tǒng)，而且這些離散時間點一般是不確定。面向事件：反映系統(tǒng)各部分相互作用的一些事件，模型為反映事件狀態(tài)的數(shù)集，仿真結(jié)果是產(chǎn)生處理這些事件的時間歷程連續(xù)系統(tǒng)：時間常為均勻間隔計時；系統(tǒng)動力學模型由表征系統(tǒng)變量

2、間關系的方程描寫，結(jié)果常為變量隨時間的變化歷程典型的離散系統(tǒng)訂票系統(tǒng)、庫存系統(tǒng)、加工制造系統(tǒng)、交通系統(tǒng)、計算機系統(tǒng)、網(wǎng)絡系統(tǒng)等單服務臺 排隊系統(tǒng)系統(tǒng)工作時間長度固定顧客到達時間隨機服務員服務時間隨機工作情況，以決定是否增加服 務臺要求通過仿真估計系統(tǒng)屬性屬性的集合來描述實體的狀態(tài)用來反映實體的某些性質(zhì)例：單機器加工過程中，工件是一個實體，材質(zhì)、形狀、顏色、到達時間、加工時間、離開時間就是屬性狀態(tài)在某一確定時刻，系統(tǒng)的狀態(tài)是系統(tǒng)中所有實體的屬性的集合 離散事件系統(tǒng)的基本要素實體永久實體：永久駐留在系統(tǒng)中，是系統(tǒng)處于活動的必要條件臨時實體：僅在系統(tǒng)中存在一段時間，按一定規(guī)律到達例：單機器加工系統(tǒng)中

3、，工件是臨時實體，機器是永久實體兩者的關系：臨時實體按一定規(guī)律出現(xiàn)在仿真系統(tǒng)中，引起永久實體狀態(tài)變化，又在永久實體作用下離開系統(tǒng)，如此整個系統(tǒng)呈現(xiàn)出動態(tài)變化的過程活動導致系統(tǒng)狀態(tài)變化的一個過程為活動活動表示兩個可區(qū)分事件之間的過程，標志著系統(tǒng)狀態(tài)的轉(zhuǎn)移例：工件開始加工到該工件加工完畢后離開生產(chǎn)線可視為一個活動，在此過程中機器處于忙狀態(tài)事件引起系統(tǒng)狀態(tài)發(fā)生變化的行為離散事件系統(tǒng)本質(zhì)是由事件驅(qū)動的例：工件的到達，系統(tǒng)狀態(tài)中機器的狀態(tài)可能由閑變?yōu)槊?，或是隊列狀態(tài)發(fā)生變化。工件加工完畢離開系統(tǒng)，此事件可能使機器的狀態(tài)由忙變閑，同時生產(chǎn)線上現(xiàn)有工件數(shù)減一。進程相當于系統(tǒng)的子系統(tǒng)，包含若干個事件及活動間的

4、邏輯關系和時序關系例：一個工件到達系統(tǒng)排隊機器為之加工加工完畢后離去的過程，可視為一個進程。事件、活動和進程三者之間的關系如圖事件、活動和進程三者之間的關系仿真時鐘離散事件動態(tài)系統(tǒng)的狀態(tài)本來就只在離散時間點上發(fā)生變化，因而不需要進行離散化處理。離散事件系統(tǒng)一般不以時間推動，但事件間有時序關系，仿真中仍必須有控制時間的部件由于引起狀態(tài)變化的事件發(fā)生時間的隨機性，仿真鐘的推進步長則完全是隨機的兩個相鄰發(fā)生的事件之間系統(tǒng)狀態(tài)不會發(fā)生任何變化，因而仿真鐘可以跨過這些不活動周期仿真鐘推進呈現(xiàn)跳躍性，推進速度具有隨機性離散系統(tǒng)仿真事例 淮安22路公交汽車始發(fā)點：動物園終點站：枚乘東路初始事件：從動物園出發(fā)

5、狀態(tài)：車上乘客數(shù)量（隨機變量）活動：兩站之間的行駛過程和時間（注意在行駛過程中狀態(tài)是不會發(fā)生變化的）事件:到站和離站 離散事件系統(tǒng)仿真的部件與結(jié)構(gòu)離散事件仿真模型都有許多通用的部件，并用一種邏輯結(jié)構(gòu)將這些部件組織起來以便于編碼、調(diào)試。 部件系統(tǒng)狀態(tài)：它由一組系統(tǒng)狀態(tài)變量構(gòu)成，用它來描述系統(tǒng)在不同時刻的狀態(tài)。仿真時鐘：用來提供仿真時間的當前時刻的變量，它描述了系統(tǒng)內(nèi)部的變化。時間表：在仿真過程中按時間順序所發(fā)生的事件類型和時間對應的一張表。統(tǒng)計計數(shù)器：由于控制與儲存關于仿真過程中的結(jié)果的統(tǒng)計信息，在計算機仿真中經(jīng)常設計一些工作單位來進行統(tǒng)計中的計數(shù)用，這些工作單元就叫做統(tǒng)計計數(shù)器。定時子程序：該

6、程序根據(jù)時間表來確定下一事件，并將仿真時鐘推進到下一事件的發(fā)生時間。初始化子程序：在仿真開始時對系統(tǒng)進行初始化工作。事件子程序：一個事件子程序?qū)谝环N類型的事件，它在相應的事件發(fā)生時，就轉(zhuǎn)入該事件的處理子程序，并更新系統(tǒng)狀態(tài)。仿真報告子程序：在仿真結(jié)束后，用來計算和打印仿真結(jié)果。主程序：調(diào)用定時子程序，控制整個系統(tǒng)的仿真過程，并確定一下事件，產(chǎn)地控制給各事件子程序以更新系統(tǒng)狀態(tài)。 離散事件系統(tǒng)的特點模型的多數(shù)變量在一定時間內(nèi)保持常數(shù)，且僅在某些時刻才發(fā)生改變，這些變量稱之為逐段常數(shù)變量。模型的一些變量隨著仿真時鐘的推進，逐步線性遞減直到為零，這些變量叫做遞減時標變量。模型狀態(tài)發(fā)生變化的時刻，

7、也就是某個遞減時標變量值為零的時刻。 仿真時鐘的推進機制是指在仿真進程中將仿真時間從一個時刻推進到另一個時刻的方法，以便 模擬動態(tài)系統(tǒng)的運行過程。離散事件系統(tǒng)仿真的時間推進機制 固定步長時間推進制固定步長時間推進制（fixed-increment time advance mechanism） 下次事件時間推進機制下次事件時間推進機制（next event advance mechanism） 混合時間推進機制混合時間推進機制（mixed time advance mechanism）固定步長時間推進機制在仿真過程中仿真時鐘每次遞增一個固定的步長。該步長在仿真開始之前，根據(jù)模型特點確定，在仿真

8、過程中保持不變。該推進方式要求每次推進都要掃描所有正在執(zhí)行的活動，以 檢查此時間區(qū)間內(nèi)是否有事件發(fā)生。固定步長時間推進機制原理圖T:仿真時鐘t :步長仿真時鐘推進機制下次事件時間推進機制仿真時鐘按照下一個事件預計將要發(fā) 生的時刻，以不等的時間間隔向前推進以不等的時間間隔向前推進。即仿真時鐘每次都跳 躍性地推進到下一事件發(fā)生的時刻上去。該推進機制中，仿真時鐘的增量不定，取決于被仿真系統(tǒng)。固定步長時間推進機制的特點每次步長推進，都要進行事件檢查，占用計算和判斷的時間，影響仿真效率。步長步長t越小，越小，問題越嚴重問題越嚴重。該機制將發(fā)生在同一步長內(nèi)的事件都視為發(fā)生在該步長的末 尾，即認為它們是同步

9、的。由此產(chǎn)生誤差，影響仿真精度。步長步長t越大，誤差越大，誤差越嚴重越嚴重。下次事件時間推進機制原理圖結(jié)論固定步長時間推進機制固定步長時間推進機制可以通過調(diào)整步長來調(diào)整仿真的效率 和精確度，但存在著影響效率的多余計算和仿真精度誤差。下次事件時間推進機制下次事件時間推進機制不存在多余的計算，具有高的仿真精 度，但沒有調(diào)整仿真效率和仿真精確度的手段。固定步長時間推進機制固定步長時間推進機制適合于對事件的發(fā)生在時間軸上呈均 勻分布的系統(tǒng)的仿真；下次事件時間推進機制下次事件時間推進機制適合于事件發(fā)生數(shù)小的系統(tǒng)仿真。 事件調(diào)度法用事件的觀點分析真是系統(tǒng)，通過定義及每個事件引起系統(tǒng)狀態(tài)的變化，按時間順序確

10、定并執(zhí)行每個事件發(fā)生時有關的邏輯關系事件調(diào)度法的過程事件調(diào)度法仿真模型中總控程序的任務 活動掃描法以活動作為分析系統(tǒng)的基本 單元，認為仿真系統(tǒng)的運行是由若干活動構(gòu)成，每一活動對應一個活動處理模塊，處理與活動相關的事件。一個實體可以有幾個活動處理模塊。每一個進入系統(tǒng)的主動實體都處于某種活動的狀態(tài)?；顒拥募ぐl(fā)與終止都會形成新 的事件。活動掃描法的基本思想 用各實體時間元的最小值推進仿真時鐘；按優(yōu)先序執(zhí)行激活實體的活動處理，使測試通過的事件得以 發(fā)生； 改變系統(tǒng)狀態(tài)，確定相關事件的發(fā)生時間。活動掃描法仿真的基本過程時間元的取值的兩種方法 三段掃描法 借鑒事件調(diào)度法的某些思想，對活動掃描法進行改進，提

11、出的三段掃描法。兼有活動掃描法簡單和調(diào)度法高效的優(yōu)點。 進程交互法 進程交互法進程交互法的基本模型單元是進程進程。進程針對某類實體的生命周期而建立，一個進程包含了實體流動中發(fā)生的所有事件。以單服務臺排隊服務系統(tǒng)為例，顧客生命周期的進程為：進程交互法的特點：為每個實體建立一個進程，以反映某個實體從產(chǎn)生開始到結(jié)束為止的全部活動。顧客排隊進程模型模型說明模型說明： 服務員兩名， 隊列一條 “”表示某顧客產(chǎn)生的時刻，也為相應進程開始的時刻； “”表示某顧客離去的時刻，也為相應進程撤銷的時刻； 符號“X”表示排隊顧客開始接受服務的時刻； 虛線表示進程的排隊時間； 波紋線表示顧客得到服務的時間。進程交互法中實體的進程不斷推進，直到某些延遲發(fā)生后才暫停，延遲可分為：無條件無條件延遲延遲：實體停留在進程中的某點不再向前移動，直到預 先確定的延遲期滿。例如，顧客停留在服務通道中直到服務完 成。條件延遲：條件延遲：延遲期的長短與系統(tǒng)狀態(tài)有關，事先無