系統(tǒng)建模與仿真第四章_離散事件仿真基礎(chǔ)

1、濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)1 第四章 離散事件仿真基礎(chǔ) 前面所討論的系統(tǒng)，其狀態(tài)變量是連續(xù)變化的，這類 系統(tǒng)的仿真成為連續(xù)系統(tǒng)仿真. 離散事件系統(tǒng)受事件驅(qū)動，系統(tǒng)的遷移發(fā)生在一系列 離散事件點上，系統(tǒng)狀態(tài)是跳躍式變化的，在時間和 空間上都是離散的，與連續(xù)系統(tǒng)在性質(zhì)上完全不同. 比 如：生產(chǎn)調(diào)度管理、庫存系統(tǒng)、計算機通訊網(wǎng)絡(luò)等. 離散事件系統(tǒng)往往是隨機的，具有復(fù)雜的變化關(guān)系， 難于用常規(guī)的微分方程、差分方程等方程模型來描述， 一般只能用流程圖或網(wǎng)絡(luò)圖來描述，如果應(yīng)用理論分 析方法難于得到解析解，甚至無法解決，仿真技術(shù)為 解決這列問題提供了有效的手段. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算

2、機仿真技術(shù)2 第四章 離散事件仿真基礎(chǔ) 4.1 離散事件系統(tǒng)與模型 4.2 離散事件仿真 4.3 排隊系統(tǒng)的仿真 4.4 Petri網(wǎng)絡(luò)仿真 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)3 4.1 離散事件系統(tǒng)與模型 離散事件系統(tǒng)大量地存在與我們周圍，比如： 超級市場管理系統(tǒng)：顧客可以做出影響系統(tǒng)的“事件” 銀行服務(wù)系統(tǒng)：顧客 公交管理系統(tǒng)：上下車的旅客 車間加工調(diào)度系統(tǒng)：等待加工的零件 “事件”是在離散時刻隨機發(fā)生的，利用仿真技術(shù)進 行研究分析，可以了解它們的動態(tài)運行規(guī)律，從而幫 助人們做出決定，比如是否需要增加新的市場和銀行， 合理的調(diào)度車輛和安排工序. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技

3、術(shù)4 連續(xù)系統(tǒng)與離散事件系統(tǒng)仿真的 區(qū)別 在連續(xù)系統(tǒng)數(shù)字仿真中，時間通常被分割成均等或非 均等的時間間隔，并以一個基本的時間間隔計時. 而離散事件仿真通常是面對事件的，時間指針不是固 定增值推進，而是由事件的推動而隨機遞進. 連續(xù)系統(tǒng)仿真中，系統(tǒng)的動力學(xué)模型是由表征系統(tǒng)變 量之間的關(guān)系的方程來描述的，仿真的結(jié)果表現(xiàn)為系 統(tǒng)變量隨時間變化的歷程 離散時間仿真中，系統(tǒng)變量是反映系統(tǒng)各部分相互作 用的一些時間，而系統(tǒng)模型則是反映這些事件的集合， 仿真結(jié)果是表現(xiàn)為這些事件的事件歷程. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)5 離散事件研究背景 離散事件的研究可以追溯到對排隊現(xiàn)象和排隊網(wǎng)絡(luò)的 分析，排

4、隊論最早有A.K. Erlang在1918年提出，在管 理通信和各類服務(wù)系統(tǒng)中有著廣泛的應(yīng)用. 離散系統(tǒng)大量地存在與客觀現(xiàn)實中，如交通管理系統(tǒng)、 庫存管理系統(tǒng)、加工系統(tǒng)、能源規(guī)劃、電話通信網(wǎng)絡(luò)、 人口管理等，而排隊論、網(wǎng)絡(luò)分析、數(shù)學(xué)規(guī)劃和調(diào)度 排序等方法是解決這類問題的主要數(shù)學(xué)方法. 離散事件的仿真技術(shù)研究，在國內(nèi)是近二十多年才開 始的，受到計算機技術(shù)、信息處理技術(shù)、控制技術(shù)、 人工智能技術(shù)等新技術(shù)的影響而發(fā)展. 對于離散事件構(gòu)成的離散事件系統(tǒng)或連續(xù)-離散混合系 統(tǒng)的研究，逐漸成為仿真技術(shù)應(yīng)用的一個重要分支領(lǐng) 域. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)6 4.1.1 離散事件系統(tǒng)的基本要素

5、 離散事件系統(tǒng)的一些基本要素包括：實體、活動、事 件等. 以超市購物系統(tǒng)為例： 例4.1 華聯(lián)超市濟南大學(xué)分店，共有10個服務(wù)臺供顧客 結(jié)帳，營業(yè)時間為9：00 21：00，顧客選購?fù)晟唐返?服務(wù)臺結(jié)帳的時間是隨機的，而且各自獨立，每位顧客 接受服務(wù)的時間長短也是隨機的. 可以用于描述該系統(tǒng)的 狀態(tài)，可以是： 服務(wù)臺的狀態(tài)服務(wù)臺的狀態(tài)：忙，閑 顧客排隊等待的隊長顧客排隊等待的隊長：0，1，2， 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)7 服務(wù)員服務(wù)員 超市系統(tǒng) 顧客進入系統(tǒng) 顧客排隊 接受服務(wù)的顧客 顧客離開 臨時實體：只存在一段時間，由系統(tǒng)外部到達和進入系統(tǒng). 如超 市系統(tǒng)里的顧客，該臨時實

6、體隨機到達系統(tǒng)，經(jīng)過服務(wù)員的服務(wù)， 然后離開系統(tǒng). 那些已經(jīng)在超市選購但并未到服務(wù)臺結(jié)帳排隊的 不能稱為該系統(tǒng)的實體. 類似的還有：公交系統(tǒng)里的上下車顧客，生產(chǎn)加工系統(tǒng)里等待加 工的零件，計算機系統(tǒng)中等待處理的信息，電話交換系統(tǒng)中的電 話呼叫 永久實體：永久性的駐留在系統(tǒng)中的實體. 比如超市系統(tǒng)中的服 務(wù)員，以及售票員、加工設(shè)備、計算機設(shè)備、電話交換機 系統(tǒng)狀態(tài)的變化是由實體的狀態(tài)變化產(chǎn)生的. 1. 實體實體(Entity) 臨時實體臨時實體永久實體永久實體 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)8 顧客到達事件顧客開始接受 服務(wù)事件 顧客服務(wù)完畢 離去 顧客離開 超市系統(tǒng) 顧客進入系統(tǒng) 顧

7、客排隊 服務(wù)員服務(wù)員 接受服務(wù)的顧客 臨時實體臨時實體永久實體永久實體 2. 事件事件(Event) 引起系統(tǒng)狀態(tài)變化的行為稱為事件. “顧客到達事件”引起了系 統(tǒng)狀態(tài)變化：服務(wù)員由“閑”變?yōu)椤懊Α?，或排隊的隊長加1. 事 件是在某一時間點的瞬時行為，從某種意義上來說，系統(tǒng)是由事 件驅(qū)動的. 事件不僅用來協(xié)調(diào)兩個實體之間的同步活動，還用于 各個實體之間傳遞信息. 一個系統(tǒng)中往往有許多類事件，事件發(fā)生與某一實體相聯(lián)系，并 可能引起其它事件的發(fā)生. 仿真模型中必須建立事件表，記錄每 次發(fā)生的事件或?qū)⒁l(fā)生事件的類型、時間、相關(guān)實體屬性等. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)9 超市系統(tǒng) 顧客

8、進入系統(tǒng) 顧客排隊 服務(wù)員服務(wù)員 接受服務(wù)的顧客 顧客離開 3. 活動活動(Activity) 離散事件中的活動，通常用于表示兩個可以區(qū)分的事件之間的過 程，是實體在兩個事件之間保持某一個狀態(tài)的持續(xù)過程. 它標(biāo)志 著系統(tǒng)狀態(tài)之間的轉(zhuǎn)移. “排隊活動”標(biāo)志著排隊隊長發(fā)生變化，“接受服務(wù)活動”使隊長 變化或服務(wù)員由“忙”到“閑”. 顧客到達事件顧客開始接受 服務(wù)事件 顧客服務(wù)完畢 離去 排隊活動排隊活動接受服務(wù)活動接受服務(wù)活動 臨時實體臨時實體永久實體永久實體 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)10 超市系統(tǒng) 顧客進入系統(tǒng) 顧客排隊 服務(wù)員服務(wù)員 接受服務(wù)的顧客 顧客離開 4. 進程進程(P

9、rocess) 進程是由若干個事件和若干個活動組成，它描述了事件及活動之 間的相互邏輯關(guān)系及時序關(guān)系. 顧客到達事件顧客開始接受 服務(wù)事件 顧客服務(wù)完畢 離去 排隊活動排隊活動接受服務(wù)活動接受服務(wù)活動 臨時實體臨時實體永久實體永久實體 顧客超市結(jié)帳服務(wù)進顧客超市結(jié)帳服務(wù)進 程程 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)11 例4.2 在一個有較大水位落差河段上的船閘運行系統(tǒng)， 從上游新來的船只到達船閘時，進行排隊，排到時，船 閘打開，船只過閘，最后船只離開船閘. 該系統(tǒng)的實體、 事件、活動和進程，它們之間的關(guān)系？ 實體：船只為臨時實體，船閘為永久實體. 事件：船只到達事件，過閘服務(wù)開始事件，過

10、閘服務(wù)結(jié)束事件(船只 離開事件) 活動：船只排隊活動，過閘服務(wù)活動 進程：船只過閘服務(wù)進程 船只到達事件過閘服務(wù)開始 事件 過閘服務(wù)結(jié)束 事件 船只過閘服務(wù)進程船只過閘服務(wù)進程 排隊活動排隊活動過閘服務(wù)活動過閘服務(wù)活動 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)12 5. 仿真鐘仿真鐘(Simulating Clock) 仿真鐘用于表示仿真時間的變化，在連續(xù)系統(tǒng)中，仿真時間的變化 基于仿真步長的確定，可以是定步長或變步長. 在離散事件系統(tǒng)中，引起系統(tǒng)狀態(tài)變化的事件發(fā)生時間是隨機的， 因而仿真時鐘的步長也是隨機的. 從一個事件發(fā)生時刻推進到另一 個事件發(fā)生時刻，具有跳躍性和隨機性. 超市系統(tǒng) 顧客

11、進入系統(tǒng) 顧客排隊 服務(wù)員服務(wù)員 接受服務(wù)的顧客 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)13 6. 統(tǒng)計計數(shù)器統(tǒng)計計數(shù)器(Statistic Counter) 離散事件的狀態(tài)變量隨事件的不斷發(fā)生呈現(xiàn)出動態(tài)變化，這種變 化是隨機的，所以某一次運行是隨機過程的一次取樣，只有在統(tǒng) 計意義下才有參考價值. 如超市系統(tǒng)中，顧客到達的時間具有隨機性，服務(wù)員為每位顧客 服務(wù)的時間也是隨機的. 因此，在某一時刻，系統(tǒng)狀態(tài)：排隊隊長 或服務(wù)員的忙、閑狀態(tài)都是完全不確定的. 從系統(tǒng)分析來看，感興 趣的是系統(tǒng)的平均步長，顧客的平均等待時間，服務(wù)員的利用率 等. 在仿真模型中，需要一個統(tǒng)計計數(shù)器，來統(tǒng)計系統(tǒng)中的有關(guān)

12、變量， 來得到相關(guān)的統(tǒng)計意義. 超市系統(tǒng) 顧客進入系統(tǒng) 顧客排隊 服務(wù)員服務(wù)員 接受服務(wù)的顧客 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)14 4.1.2 離散事件系統(tǒng)模型的建立 離散事件系統(tǒng)研究和仿真中最基本的問題就是系統(tǒng)的建模. 20世 紀(jì)80年代出，Y.C. Ho教授倡導(dǎo)對離散事件動態(tài)系統(tǒng)理論 (Disctributed Event Dynamic System, DEDS)進行研究，而后學(xué) 多學(xué)者對這個問題從不同層次或用不同的數(shù)學(xué)工具進行了描述， 形成了許多的方法體系，并出現(xiàn)了多種形式的DEDS模型設(shè)計方 法. 例如，考慮對象演變過程的分析，根據(jù)事件發(fā)生的時間是否有必 要納入研究范圍，可

13、以劃為分： 不帶時標(biāo)的DEDS模型：有限狀態(tài)自動機模型、Petri網(wǎng)絡(luò)模型、 過程代數(shù)模型、時序邏輯模型等. 帶時標(biāo)的DEDS模型：賦時Petri網(wǎng)絡(luò)模型、TIM/RTIL模型、 雙子代數(shù)模型、排隊網(wǎng)絡(luò)模型、Markov鏈模型與CSMP模型 等. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)15 4.1.2 離散事件系統(tǒng)模型的建立 還可以根據(jù)系統(tǒng)輸入信息及狀態(tài)演變的確定性/不確定性，分成確 定性DEDS模型和隨機性DEDS模型. 根據(jù)狀態(tài)變化的量化特征，分成邏輯（定性）模型與數(shù)量（定量） 模型等. 從現(xiàn)有各類的DEDS模型來看，尚沒有通用的、適合于各類研究 對象的模型表示形式. 從現(xiàn)有模型的形成過

14、程來看，DEDS模型的 常用辦法主要有 排隊論方法 網(wǎng)絡(luò)圖或事件圖法 形式語言與自動機法 隨機過程描述法（如Markov過程和CSMP過程） 抽象代數(shù)法（如雙子代數(shù)、極小代數(shù)、極大代數(shù)） 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)16 離散事件建模的步驟 1. 明確仿真目的明確仿真目的 建模之前，必須根據(jù)仿真目的，確定所需要獲取的某 一事件或系統(tǒng)的信息、模型類型、資料及數(shù)據(jù). 目的 不同，所建立的模型也不同，衡量仿真結(jié)果的逼真性 準(zhǔn)則也就不同. 甚至對某一仿真目的，模型是有效的， 而對另一仿真目的，模型可能就是無效的. 比如，例4.2中的船閘運行系統(tǒng)中，如果仿真目的是 了解船閘服務(wù)時間長短對船閘

15、利用率的影響，這種情 況屬于排隊論模型. 如果還要分析閘門的開關(guān)控制和 動力學(xué)特性，以及注水放水過程特性，系統(tǒng)應(yīng)視為連 續(xù)-離散混合型系統(tǒng). 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)17 離散事件建模的步驟 2.正確描述系統(tǒng)正確描述系統(tǒng) 組成成分： 指對描述系統(tǒng)仿真目的有意義的實體，這些實體的行為往往是隨 機分布的. 如超市系統(tǒng)中的顧客、服務(wù)員是系統(tǒng)的實體，船閘運 行系統(tǒng)中的船只、船閘也是系統(tǒng)實體. 描述變量和參數(shù)： 指系統(tǒng)各實體的屬性. 描述變量包括內(nèi)部變量和外部變量，除了 輸入和輸出變量外，其余均為狀態(tài)變量. 參數(shù)可以在仿真前由用 戶設(shè)置或在仿真過程中根據(jù)用戶的命令加以改變. 比如，船閘運

16、 行系統(tǒng)中，船只到達間隔時間、船閘服務(wù)過程時間、隊列長度就 是描述變量. 相互關(guān)系 相互關(guān)系規(guī)定了系統(tǒng)中不同變量的相互關(guān)聯(lián)，指影響系統(tǒng)變化的 各實體、變量和參數(shù)之間的連接關(guān)系和作用關(guān)系. 相互關(guān)系大部 分反映在各成分的活動之中，而活動又由事件所引發(fā)，所以弄清 事件、活動的關(guān)系是系統(tǒng)描述中極為重要的. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)18 如，船閘運行系統(tǒng)中的事件：船只到達、船閘開始服務(wù)、船閘結(jié) 束服務(wù)、船只離開. 活動有：排隊活動、過閘服務(wù)等. 按仿真目 的表示出這些事件發(fā)生的順序、活動持續(xù)過程，以便描述出系統(tǒng) 間的相互關(guān)系，由此可以進一步畫出系統(tǒng)的流程圖和網(wǎng)絡(luò)圖. 船只到達 查詢船閘

17、空閑狀態(tài)？ 船閘服務(wù) 船只離開 置船閘為閑 Y 排隊等候 N 船閘服務(wù)系統(tǒng)流船閘服務(wù)系統(tǒng)流 程圖：程圖： 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)19 離散事件建模的步驟 3. 仿真模型的建立仿真模型的建立 流程圖僅能表明整個過程中發(fā)生的“事件”表，要仿 真這樣一系列“事件”，必須知道確切的時間表，這 就是仿真系統(tǒng)建模. 假設(shè)船閘服務(wù)系統(tǒng)中，船只到達的時間間隔是平均值 為70分鐘，變化范圍為正負(fù)14分鐘的均勻分布的隨機 數(shù)，船閘服務(wù)時間是平均值為60分鐘，變化范圍為正 負(fù)7分鐘的均勻分布的隨機數(shù). 則可以得到系統(tǒng)的含有 隨機概率模型的仿真系統(tǒng)模型. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)20

18、 船只到達 查詢船閘空閑狀態(tài)？ 船閘服務(wù) 船只離開 置船閘為閑 Y 排隊等候 N 開始 置仿真開始和結(jié)束時間 船只到達時間 間隔70分鐘 船閘服務(wù)系統(tǒng)流程圖：船閘服務(wù)系統(tǒng)流程圖：船閘服務(wù)系統(tǒng)仿真模型圖：船閘服務(wù)系統(tǒng)仿真模型圖： 系統(tǒng)流程 大于結(jié)束時間？ 結(jié)束 Y N 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)21 離散事件建模的步驟 4. 輸出函數(shù)的確定輸出函數(shù)的確定 在建立了系統(tǒng)模型的基礎(chǔ)上，還需要確定輸出函數(shù). 根據(jù)仿真目的統(tǒng)計計算出反應(yīng)系統(tǒng)性能的數(shù)據(jù)，這些 數(shù)據(jù)就是系統(tǒng)的輸出. 如船閘服務(wù)系統(tǒng)中，可以求出船只的平均等待時間、 最大隊列長度和船閘利用率. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真

19、技術(shù)22 4.2 離散事件仿真 4.2.1 離散事件系統(tǒng)的仿真模型離散事件系統(tǒng)的仿真模型 離散事件系統(tǒng)仿真建模的目的，是要建立與系統(tǒng)模型 有同構(gòu)或同態(tài)關(guān)系的能在數(shù)字機上試驗的模型，模型 中有對隨機變量概率分布的函數(shù). 連續(xù)系統(tǒng)仿真建模需要通過各種算法將系統(tǒng)離散化， 而與連續(xù)系統(tǒng)不同，從描述形式來看，離散事件系統(tǒng) 模型為直接用于仿真創(chuàng)造了條件. 為了正確的進行離散事件系統(tǒng)的仿真建模，還需弄清 楚離散事件仿真程序的主要組成成分、流程管理及相 關(guān)的概念. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)23 1. 仿真程序的主要成分：仿真程序的主要成分： 采用步長法仿真的程序主要由以下部分組成： 仿真時鐘：

20、提供仿真時間的當(dāng)前值 事件表：由策劃和事件調(diào)度生成事件名稱、時間的二維表， 即有關(guān)未來事件的表 系統(tǒng)的狀態(tài)變量：描述系統(tǒng)狀態(tài)的變量 初始化子程序：用于模型初始化 事件子程序：每一類事件的服務(wù)子程序 調(diào)度子程序：將未來事件插入事件表的子程序 時鐘推進子程序：根據(jù)事件表決定下次的事件，將仿真時鐘 推進到事件發(fā)生時刻 隨機數(shù)產(chǎn)生子程序：產(chǎn)生給定分布隨機數(shù)的子程序 輸出函數(shù)子程序：用于系統(tǒng)性能分析的子程序 統(tǒng)計計數(shù)器：用來存放與系統(tǒng)性能分析有關(guān)的統(tǒng)計數(shù)據(jù)的各 個變量值 主程序：調(diào)用上述各子程序并完成仿真任務(wù)全過程 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)24 2. 仿真程序的流程管理：仿真程序的流程管

21、理： 仿真流程管理（即仿真調(diào)度）是仿真建模的核心. (1) 仿真時鐘仿真時鐘 離散事件系統(tǒng)仿真中時間的變化是用一個邏輯時鐘的時間數(shù)來表 示. 仿真時間與所有實體的活動及所有事件的調(diào)度有關(guān)系，仿真 時間與真實時間可以通過選定的時間的比例尺相關(guān)聯(lián). 每一事件 通過被調(diào)度事件時間與仿真時鐘相關(guān)聯(lián)，當(dāng)對應(yīng)的物理事件發(fā)生 時，這個事件時間就對應(yīng)于實際系統(tǒng)的真實時間. 仿真時鐘一般有兩種推進方式： 時間步長法：時間步長法： 在進行系統(tǒng)仿真的同時，可以把整個仿真過程分成許多相等的時間 間隔，時間步長的長度可根據(jù)實際問題分別取秒、分、小時等，程 序中按此步長前進的時鐘就是仿真時鐘. 選取系統(tǒng)的一個初始狀態(tài)作為

22、仿真時鐘的零點，仿真時鐘每步進一 次，就對系統(tǒng)的所有實體、屬性和活動進行一次全面的掃描考察， 按照預(yù)定的計劃和目標(biāo)進行分析、計算和記錄系統(tǒng)狀態(tài)的變化，這 個過程一直進行到仿真時鐘結(jié)束為止. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)25 事件步長法：事件步長法： 以事件發(fā)生的時間為增量，按照時間的進展，一步一步地對系統(tǒng)的 行為進行仿真，知道預(yù)定的仿真時間結(jié)束為止. 事件步長法和時間步長法的主要區(qū)別：事件步長法和時間步長法的主要區(qū)別： 兩者都是以時間為增量來考察系統(tǒng)狀態(tài)的變化的. 但在時 間步長法中，仿真時鐘以等步長前進，而在事件步長法中， 仿真時鐘步長取決與事件的時間間隔. 時間步長法在一個步長

23、內(nèi)，認(rèn)為系統(tǒng)所處的狀態(tài)相同，因 而所選的步長大小將影響系統(tǒng)的精度. 而在事件步長法中，每 個事件的發(fā)生均有確切的時刻，不需要認(rèn)為地選取步長，步 長的大小對仿真的精度影響較小. 時間步長法每步都要對系統(tǒng)進行一次全面的考察，即使系 統(tǒng)狀態(tài)沒有發(fā)生變化. 事件步長法只在事件發(fā)生時才進行掃描. 一般來說，當(dāng)事件數(shù)目較大或事件變化呈周期性特點時，用 時間步長法可以節(jié)省用機時間. 而當(dāng)相繼兩個事件出現(xiàn)的平均 間隔較長時，更適合于采用事件步長法. 如上所述，事件進程管理有面向事件的，為變步長法，也有面向 時間間隔的，為定步長法. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)26 2. 仿真程序的流程管理：仿真程

24、序的流程管理： (2) 事件表事件表 為了使仿真程序能如實地模擬實際系統(tǒng)的變化，在某些離散事件 的仿真鐘，采用事件表的形式進行調(diào)度. 事件表一般是一個有序 的記錄表，每個記錄包括發(fā)生的時間、事件的類型等一些內(nèi)容. 事件步長法中常用到的事件表法的主要思想是將系統(tǒng)的仿真過程 看成是一個事件點序列，根據(jù)事件出現(xiàn)的時序，用一個稱之為事 件表的表格來調(diào)度事件執(zhí)行的順序. 對于當(dāng)前需要處理的事件，列入事件表中，從中取出最接近的事 件進行處理，處理完畢后自動推出事件表. 在處理當(dāng)前事件的過 程中，往往會產(chǎn)生一個后繼事件，因此，必須預(yù)測出此后繼事件 的出現(xiàn)時刻，并將其列入事件表中. 這樣，事件表好像一本記事簿

25、，完成一件事情后將它從記事簿中 消除，把新的要完成的工作再列入記事簿中，按照這樣的方式， 將系統(tǒng)仿真進行下去. 這種方法要求對系統(tǒng)的各種事件進行詳細(xì)的描述，當(dāng)事件之間沒 有太多相互作用或事件數(shù)目不多時，事件表法比較有效. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)27 2. 仿真程序的流程管理：仿真程序的流程管理： (3) 同時事件管理同時事件管理 同類同時事件管理： 發(fā)生在同一時刻并且隸屬于同一類型的幾個事件叫同類同時事件. 它會導(dǎo)致模型的下一狀態(tài)出現(xiàn)多種可能值，即可能出現(xiàn)集中排隊 順序. 為此，我們需要先定好條件，使?fàn)顟B(tài)取值為唯一，也就是 規(guī)定一種排隊規(guī)則來管理這些同類同時事件. 例如，先進

26、先出 （先到先服務(wù)）規(guī)則、后進先出（后到先服務(wù)）原則、隨機規(guī)則、 優(yōu)先服務(wù)原則. 混合同時事件管理： 發(fā)生在同一時刻但不屬于同一類型的幾個事件叫混合同時事件. 確定這些混合同時事件所造成的狀態(tài)的變化，通常有一步法與解 結(jié)法. 一步法就是直接確定混合同時事件所形成的結(jié)果狀態(tài)，解結(jié)法是 把幾個同時事件分解成多個單獨事件的序列進行處理. 對于簡單的情況，一步法與解結(jié)法將會得到相同的結(jié)果. 但一步 法不易寫成通用形式，且比較復(fù)雜，而解結(jié)模型簡單，通用性好 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)28 4.2.2 離散事件系統(tǒng)仿真策略 因為模型類型不同，仿真方法也會不同. 我們主要介紹最常用的 排隊網(wǎng)絡(luò)

27、模型所使用的仿真方法. 在離散事件模型里，實體活動、進行都是以事件為基礎(chǔ)構(gòu)成的， 所以從事件、活動、進程三個層次來組織事件構(gòu)成了處理離散事 件模型的三種典型方法： 事件調(diào)度法事件調(diào)度法(Event Scheduling) 這種方法有一個時間控制程序，從事件表中選擇具有最早發(fā)生時 間的事件，并將仿真時鐘改到該事件發(fā)生的時刻，再調(diào)用與該事 件相應(yīng)的程序模塊，對事件進行處理，該事件處理完畢后，返回 時間控制程序. 這樣，事件的選擇和處理不斷交替進行，直到仿 真終止的程序發(fā)生. 在這種方法中，任何條件的測試均在相應(yīng)的事件模塊中進行，顯 然是一種面向事件的仿真方法. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真

28、技術(shù)29 活動掃描法活動掃描法(Activity Scanning) 系統(tǒng)由部件（對應(yīng)與實體）組成，而部件包含有活動，該活動是 否發(fā)生取決與規(guī)定的條件，有一個專門的模塊來確定激活條件， 若條件滿足，則激活相應(yīng)部件的活動模塊. 時間控制程序較其它 的條件有更高的優(yōu)先級，即在判斷激活條件時首先判斷該活動發(fā) 生的時間是否滿足，然后再判斷其它條件. 若所有條件滿足，則 執(zhí)行該部件的活動模塊，然后再對其它部件掃描，對所有部件掃 描一遍后，按同樣順序進行循環(huán)掃描，知道仿真終止. 進程交互法進程交互法(Process Interaction) 這種方法綜合了事件調(diào)度法和活動掃描法的特點，采用兩張事件 表，即

29、當(dāng)前事件表（CEL）和將來事件表（FEL）. 首先按一定的分布產(chǎn)生到達實體并置于FEL中，實體進入排隊等待； 然后對CEL進行活動掃描，判斷各種條件是否滿足； 再將滿足條件的活動進行處理，仿真鐘推進到服務(wù)結(jié)束并將相應(yīng)的 實體從系統(tǒng)中清除； 最后將FEL中最早發(fā)生的當(dāng)前事件實體移到CEL中，繼續(xù)推進仿真時 鐘，對CEL進行活動掃描，直到仿真結(jié)束. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)30 4.2.3 離散事件仿真研究的一般 步驟 1.系統(tǒng)建模 模型模型一般用流程圖來描述. 模型包含有隨機變量，其分布類型和特 征是十分重要的 2.確定仿真算法 一是如何產(chǎn)生所需要的隨機變量 二是仿真建模策略：

30、事件調(diào)度法：按事件的觀點建立仿真策 略 活動掃描法：用活動來描述事件之間的 過程，面向活動建模 進程交互法：進程作為建模的基本單元 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)31 3.建立仿真模型 數(shù)學(xué)模型中最廣泛的類型是狀態(tài)空 間模型，首先要定義系統(tǒng)的狀態(tài)變量. 離散事件系統(tǒng)中，狀態(tài)的變化由事 件引起，因此，除了定義系統(tǒng)狀態(tài)，還 要定義系統(tǒng)事件及其相關(guān)屬性. 比如事件調(diào)度法：事件類型、發(fā)生 時間以及對事件的處理規(guī)則都是要定義 的屬性. 在活動掃描法和進程交互法中，還 要定義活動和進程. 4.設(shè)計仿真程序 運行仿真程序 仿真模型檢驗及改進 由于離散事件系統(tǒng)固有的隨機性，所以每 次仿真運行的結(jié)果僅

31、僅是隨機變量的一次 取樣，那么，仿真結(jié)果的可信性如何？如 何提高仿真結(jié)果的置信度？這些都是十分 重要和有待解決的關(guān)鍵問題. 5.仿真結(jié)果處理分析 可以采用通用的或?qū)Ｓ玫母呒壵Z言編寫算 法 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)32 4.3 排隊系統(tǒng)的仿真 排隊系統(tǒng)是日常生活、工業(yè)生產(chǎn)、交通和電信網(wǎng)絡(luò)中常見的現(xiàn)象， 比如： 病人到醫(yī)院看病，顧客到銀行取款，乘客到售票處買票 交通堵塞，電信業(yè)務(wù)，自動生產(chǎn)線加工零件，計算機網(wǎng)絡(luò)數(shù)據(jù)包等 待傳送 一般來說，當(dāng)某個時候要求服務(wù)的數(shù)量超過服務(wù)機構(gòu)的容量，就 會出現(xiàn)排隊現(xiàn)象. 在排隊現(xiàn)象中，服務(wù)對象可以是人，也可以是 物，還可以是某種信息. 在各種排隊系統(tǒng)

32、中，由于對象到達的時刻與接受服務(wù)的時間都是 不確定的，隨著不同的時間及條件而變化，所以排隊系統(tǒng)在某個 時刻的狀態(tài)也是隨機的. 排隊越長，浪費的時間就越多，系統(tǒng)的效率低下，但盲目增加服 務(wù)設(shè)備，會增加投資或發(fā)生空閑浪費，反而不能提高效率. 因此， 要考慮如何在兩者之間取得平衡，提高服務(wù)質(zhì)量并降低成本. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)33 4.3 排隊系統(tǒng)的仿真 排隊問題實質(zhì)上是一個平衡等待時間和服務(wù)臺空閑時 間的問題，也就是如何確定一個排隊系統(tǒng)，使實體 （等待服務(wù)的人、物和信息）和服務(wù)臺兩者都有利， 排隊論就是解決這類問題的一門學(xué)科，又稱隨機服務(wù) 理論，因為實體到達和接受服務(wù)的時間常常

33、是某種概 率分布的隨機變量. 4.3.1 排隊論的基本概念 4.3.2 到達時間間隔和服務(wù)時間的分布 4.3.3 排隊系統(tǒng)分析 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)34 4.3.1 排隊論的基本概念 1. 排隊系統(tǒng)的組成排隊系統(tǒng)的組成 到達模式：指動態(tài)實體按什么樣的規(guī)則到達，描寫實體到達的 統(tǒng)計特性 服務(wù)機構(gòu)：指同一時間有多少服務(wù)臺可以接納動態(tài)實體，他們 的服務(wù)需要多少時間，服從什么樣的分布 服務(wù)規(guī)則：指對下一個實體服務(wù)的選擇原則. 動態(tài)實體排隊服務(wù)機構(gòu) 到達 接受服務(wù) 如何通過已知的到達模式和服務(wù)時間的概率分布，來研究排隊系統(tǒng)的隊 伍長度和服務(wù)機構(gòu)“忙”或“閑”的程度，就是離散事件仿真所

34、要解決 的問題. 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)35 2. 到達模式到達模式 平均到達時間間隔Ta 假設(shè)在仿真總時間T內(nèi)一共到達了n個“顧客”，則平均到達時間 間隔為： Ta=T/n 平均到達速率 定義單位時間內(nèi)到達的“顧客”數(shù)為平均到達速率，即 =1/Ta=n/T 到達時間間隔分布函數(shù)A0(t) 定義為到達時間間隔大于t的概率. 設(shè)累計分布函數(shù)F(t)是到達時間 間隔小于t的概率，則 A0(t)=1-F(t) 顯然，t=0時，A0(t)=1，隨著t增加，A0(t)減小. 動態(tài)實體排隊服務(wù)機構(gòu) 到達 接受服務(wù) 排隊系統(tǒng)排隊系統(tǒng) 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)36 到達時間變

35、化系數(shù) 定義為到達時間間隔的標(biāo)準(zhǔn)差Sa與平均到達時間間隔Ta的比值 Sa/Ta，它是一個無量綱的系數(shù)，描述了數(shù)據(jù)圍繞平均值的分散 程度. 指數(shù)分布的平均值與標(biāo)準(zhǔn)差相同，所以其變化系數(shù)為1. 如果觀測 到的變化系數(shù)接近與1，則用指數(shù)分布去擬合這些數(shù)據(jù)是合理的. 當(dāng)變化系數(shù)比1小得多時，經(jīng)常應(yīng)用愛爾朗分布. 顧客的到達模式如果按顧客到達的方式來劃分，可能是一個一個 的，也可能是成批的；如果按相繼到達的時間間隔劃分，則可能 是確定型的或隨機型的；如果按到達的過程劃分，那么可以是平 穩(wěn)的，或非平穩(wěn)的. 動態(tài)實體排隊服務(wù)機構(gòu) 到達 接受服務(wù) 排隊系統(tǒng)排隊系統(tǒng) 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)37

36、 3. 服務(wù)機構(gòu)服務(wù)機構(gòu) 同到達時間一樣，首先定義Ta為平均服務(wù)時間，為平均服務(wù)速 率，S0(t)為服務(wù)時間大于t的概率. 服務(wù)機構(gòu)按機構(gòu)形式可以分為無服務(wù)臺、只有一個服務(wù)臺或有多 個服務(wù)臺的情況. 在有多個服務(wù)臺的情形中， 它們可以是平行排列（并列）的，也可以是前后排列（串列）的， 也可以是混合的； 按服務(wù)方式可以是對單個顧客進行，也可以是對成批顧客進行； 按服務(wù)時間可以是確定型的，也可以是隨機型的； 按服務(wù)過程可以是平穩(wěn)的，也可以是非平穩(wěn)的. 因為非平穩(wěn)情形處理 起來十分復(fù)雜，所以同到達過程一樣，服務(wù)時間的分布都假定是平 穩(wěn)的. 動態(tài)實體排隊服務(wù)機構(gòu) 到達 接受服務(wù) 排隊系統(tǒng)排隊系統(tǒng) 濟南

37、大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)38 4. 排隊規(guī)則排隊規(guī)則 排隊規(guī)則是指顧客按一定的次序接受服務(wù). 服務(wù)次序可以采用下 列規(guī)則： 先到先服務(wù) 即按到達次序接受服務(wù)，這是最常見的情形. 后到先服務(wù) 如乘電梯的乘客通常是后到先出的. 倉庫中堆放的大件物品也是后到 先出. 情報系統(tǒng)中，最后到達的信息往往最具有價值. 隨機服務(wù) 當(dāng)服務(wù)臺空時，從等待的顧客中隨機選取一名進行服務(wù) 優(yōu)先權(quán)服務(wù) 醫(yī)院中的急診病人，機場頭等艙客戶 多個服務(wù)臺情形 假設(shè)n個服務(wù)臺，顧客排成n隊，當(dāng)某個顧客到達時，以概率Pi進入 第i隊. 動態(tài)實體排隊服務(wù)機構(gòu) 到達 接受服務(wù) 排隊系統(tǒng)排隊系統(tǒng) n i i P 1 1 濟南大

38、學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)39 5. 隊列的度量隊列的度量 已知平均到達速率和平均服務(wù)速率，定義業(yè)務(wù)量強度為： =/ 定義有n個服務(wù)臺，服務(wù)設(shè)備利用率為得到服務(wù)的動態(tài)實體的到 達速率與服務(wù)速率之比： =/ n 顯然，服務(wù)臺越少，服務(wù)設(shè)備的利用率就越高，正常情況是1， 這樣每個動態(tài)實體才有希望得到即使服務(wù). 利用率越高，則動態(tài) 實體的排隊等待時間越長. 因此，設(shè)計系統(tǒng)的設(shè)備利用率是一個 權(quán)衡過程，可以通過多次反復(fù)的仿真實驗加以合理解決. 對于隊列的度量，通?？疾靸蓚€量：隊列的長度和排隊的時間. 這兩個量都是變量，不同的隊列長度也不相同，不同的動態(tài)實體 排隊時間不同. 在仿真實驗中，對這兩

39、個量的變化進行統(tǒng)計，以 求出其數(shù)字特征：如均差、方差、最大值、最小值等，這些數(shù)字 特征反應(yīng)了一個服務(wù)系統(tǒng)的重要特性. 動態(tài)實體排隊服務(wù)機構(gòu) 到達 接受服務(wù) 排隊系統(tǒng)排隊系統(tǒng) 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)40 6. 排隊模型的分類排隊模型的分類 肯德爾（Kendall）對并列服務(wù)臺的情形提出了一個分類方法，其 符號形式是：X / Y / Z，其中 X：相繼到達的時間間隔分布 Y：服務(wù)時間的分布 Z：并列的服務(wù)臺數(shù)目 常用的表示相繼到達的時間間隔和服務(wù)時間的概率分布符號是： M：負(fù)指數(shù)分布（M指Markov性） D：確定性（Deterministic） Ek：k階愛爾朗（Erlang）

40、分布 GI：一般相互獨立的隨機分布 G：一般隨機分布 例如，M/M/1表示相繼到達的時間間隔為負(fù)指數(shù)分布，服務(wù)時間 為負(fù)指數(shù)分布，單服務(wù)臺模型；D/M/2表示確定的到達時間間隔， 服務(wù)時間為負(fù)指數(shù)分布，兩個平行服務(wù)臺模型. 動態(tài)實體排隊服務(wù)機構(gòu) 到達 接受服務(wù) 排隊系統(tǒng)排隊系統(tǒng) 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)41 4.3.2 到達時間間隔和服務(wù)時間 的分布 解決排隊問題首先要根據(jù)先驗知識做出顧客到達時間間隔和服務(wù) 時間的經(jīng)驗分布，然后再利用統(tǒng)計學(xué)的方法確定其相應(yīng)的理論分 布，并估計其參數(shù)值. 下面列出幾種常用的理論分布. 1. 定長分布定長分布 這是最簡單的情形，每個動態(tài)實體在恒定的

41、時間間隔內(nèi)到達，或 者是每個動態(tài)實體接受服務(wù)的時間是常數(shù). bt bt tS at at tTPtA 1 0 )( 1 0 )( 0 0 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)42 2. 泊松（泊松（Poisson）分布）分布 到達時間間隔滿足下面四個條件的分布即泊送分布. 平穩(wěn)性 在區(qū)間a, a+t內(nèi)有k個顧客到來的概率與a無關(guān)，至于t，k有關(guān)， 將此概率記為Pk(t). 無后效性 不相交區(qū)間內(nèi)顧客數(shù)是相互獨立的. 普通性 另(t)為時間t內(nèi)至少有兩個顧客到達的概率，則 0)(lim 0 t t 有限性 任意區(qū)間內(nèi)到達有限個顧客的概率之和為1，即 k R R k tP 0 1)(lim 如

42、果顧客到達時間滿足泊松分布，則在時間t內(nèi)到達k個顧客的概 率為 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)43 2. 泊松（泊松（Poisson）分布）分布 ,2, 1, ! )( k k t etP k t k 其中為泊松分布常數(shù). 令第i個顧客到達的時刻為i(i=1,2,)，并令0=0，那么顧客相繼到 達的時間間隔 ti=i i-1 是獨立分布的，其分布函數(shù)為負(fù)指數(shù)分布： 01 0 )( 0 t te tTPtA t 泊松分布中，顧客到達的時間完全是隨機的，僅僅受到給定的平均 速率的限制. 許多排隊系統(tǒng)的到達模式都屬于泊松分布. 因為平均速率=1/Ta. 可求得數(shù)學(xué)期望和方差為： 2 /1)(,/1)(TDTE 濟南大學(xué)控制科學(xué)與工程學(xué)院計算機仿真技術(shù)44 3. 愛爾朗（愛爾朗（Erlang）分布