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

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

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

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

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

5、狀態(tài)：車上乘客數(shù)量（隨機(jī)變量）活動：兩站之間的行駛過程和時間（注意在行駛過程中狀態(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)。仿真時鐘：用來提供仿真時間的當(dāng)前時刻的變量，它描述了系統(tǒng)內(nèi)部的變化。時間表：在仿真過程中按時間順序所發(fā)生的事件類型和時間對應(yīng)的一張表。統(tǒng)計計數(shù)器：由于控制與儲存關(guān)于仿真過程中的結(jié)果的統(tǒng)計信息，在計算機(jī)仿真中經(jīng)常設(shè)計一些工作單位來進(jìn)行統(tǒng)計中的計數(shù)用，這些工作單元就叫做統(tǒng)計計數(shù)器。定時子程序：該

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

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

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

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

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

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