《制造系統(tǒng)建模與仿真》講義4

第四章離散事件系統(tǒng)仿真方法

outline

離散事件系統(tǒng)仿真策略

仿真時鐘推進機制

消息驅(qū)動的仿真機制混合系統(tǒng)仿真策略蒙特卡羅仿真方法1/14/20231SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略

事件、活動、進程是描述離散系統(tǒng)狀態(tài)變化的基本術語。

事件:

此外，仿真模型中還存在程序事件，即根據(jù)需要設定的事件。

事件是引起系統(tǒng)狀態(tài)轉(zhuǎn)變的行為和起因，是系統(tǒng)狀態(tài)變化的驅(qū)動力。例如：倉儲系統(tǒng)中物品的入庫到達是一個事件，物品的出庫離去是另一個事件。例如：在仿真過程中為了使仿真結(jié)束，專門定義一個事件，使其終止仿真。1/14/20232SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略例如：倉儲“物品到達”是一個事件，該事件的發(fā)生可能會使倉儲系統(tǒng)的貨位從“空閑”狀態(tài)變?yōu)椤胺强臻e”狀態(tài)。從“物品到達”事件直到“物品取出”，物品都處在貨位中存儲的狀態(tài)，即處于“存儲”活動中。因此，“存儲”活動的開始和結(jié)束標志著物品的到達和離去，標志著貨位的空閑與非空閑的轉(zhuǎn)變。

活動:

活動是事件與事件之間的過程，是系統(tǒng)狀態(tài)轉(zhuǎn)移的標志。1/14/20233SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略

進程是有序的事件與活動組成的過程，它描述了其中的事件、活動的相互邏輯關系和時序關系。

進程：例如：一種物品進入倉庫，經(jīng)過在貨位的存儲，直到從倉庫中出庫，物品經(jīng)歷了一個進程。事件、活動與進程之間的關系1/14/20234SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略

與事件、活動、進程相對應，離散事件系統(tǒng)的仿真策略可以分為：事件調(diào)度法、活動掃描法、進程交互法等。

仿真時鐘是離散系統(tǒng)系統(tǒng)仿真中的重要術語，它決定著仿真事件的推進機制、仿真精度和仿真效率。隨著面向?qū)ο蠹夹g的發(fā)展，基于消息驅(qū)動的仿真策略受到人們重視。1/14/20235SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略

從功能上，仿真模型可以分為：總控程序（仿真模型執(zhí)行機制）模型單元處理程序（系統(tǒng)實體、事件、狀態(tài)等之間的關系描述）公共子程序（隨機數(shù)、仿真結(jié)果分析…）1/14/20236SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略①事件調(diào)度法（eventscheduling）

事件調(diào)度法（eventscheduling）以事件為分析系統(tǒng)的基本單位，通過定義事件、事件發(fā)生的時間順序及其系統(tǒng)狀態(tài)的變化，并以事件來驅(qū)動仿真模型的運行。

事件（event）是離散事件系統(tǒng)的基本概念，事件的發(fā)生引起系統(tǒng)狀態(tài)的改變。仿真模型中的事件存放于“事件表”中，通過時間控制模塊從事件表中選擇最先發(fā)生的事件；重置仿真時鐘，并調(diào)用與該事件對應的事件處理模塊；更新系統(tǒng)狀態(tài)，決定未來將要發(fā)生的事件；當當前事件結(jié)束后，返回時間控制模塊；重復事件的選擇與處理，直到仿真結(jié)束。1/14/20237SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略

事件調(diào)度法的仿真過程：1/14/20238SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略事件調(diào)度法仿真模型中總控程序的任務：（2）事件辨識：辨識將要發(fā)生的事件（3）事件執(zhí)行：執(zhí)行當前發(fā)生的事件，將已發(fā)生的事件從事件表中移出1/14/20239SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略②活動掃描法（activityscanning）

事件調(diào)度法是一種預定事件發(fā)生時間的策略，仿真模型中必須預定系統(tǒng)中最先發(fā)生的事件，以便啟動仿真進程。此外，事件處理子程序中除要修改系統(tǒng)狀態(tài)外，還要預定本類事件的下一事件將要發(fā)生的時間。因此，該方法對活動持續(xù)時間確定的系統(tǒng)較為方便。當事件的發(fā)生不僅與時間有關，并且只有在滿足某些條件才發(fā)生的系統(tǒng)而言，由于系統(tǒng)活動的持續(xù)時間不確定，無法預定活動的開始或終止時間，事件調(diào)度法就存在不足。1/14/202310SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略

活動掃描法（activityscanning）以“活動”作為分析系統(tǒng)的基本單元，認為仿真系統(tǒng)的運行是由若干活動構(gòu)成，每一活動對應一個活動處理模塊，處理與活動相關的事件。一個活動可以由“開始（激發(fā)）”和“結(jié)束（終止）”兩個事件表示，每一事件都有相應的活動處理模塊。處理中的操作能否進行取決于時間及系統(tǒng)狀態(tài)。一個實體可以有幾個活動處理模塊。每一個進入系統(tǒng)的主動實體都處于某種活動的狀態(tài)?；顒拥募ぐl(fā)與終止都會形成新的事件。1/14/202311SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略用各實體時間元的最小值推進仿真時鐘；按優(yōu)先序執(zhí)行激活實體的活動處理，使測試通過的事件得以發(fā)生；改變系統(tǒng)狀態(tài)，確定相關事件的發(fā)生時間。

“活動處理”是活動掃描法的基本處理單元。

活動掃描法的基本思想：活動掃描法不斷掃描系統(tǒng)，檢驗哪些活動可以激發(fā)，哪些活動繼續(xù)保持，哪些活動可以終止。1/14/202312SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略

活動掃描法仿真的基本過程：1/14/202313SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略1/14/202314SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略1/14/202315SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略面向活動仿真模型總控程序的算法結(jié)構(gòu)包括：①時間掃描②活動例程掃描

由于事件直接影響系統(tǒng)狀態(tài)，活動掃描要反復進行，包括確定事件和條件事件。1/14/202316SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略③進程交互法（ProcessInteraction）事件調(diào)度法和活動掃描法的基本模型單元分別是事件處理和

活動處理。它們都針對具體事件而建立，各處理相對獨立。

進程交互法的基本模型單元是進程。進程針對某類實體的生命周期而建立，一個進程包含了實體流動中發(fā)生的所有事件。以單服務臺排隊服務系統(tǒng)為例，顧客生命周期的進程為：1/14/202317SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略1/14/202318SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略為每個實體建立一個進程，以反映某個實體從產(chǎn)生開始到結(jié)束為止的全部活動。

進程交互法的特點：1/14/202319SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略顧客排隊進程模型模型說明：服務員兩名，隊列一條“?”表示某顧客產(chǎn)生的時刻，也為相應進程開始的時刻；“?”表示某顧客離去的時刻，也為相應進程撤銷的時刻；符號“X”表示排隊顧客開始接受服務的時刻；虛線表示進程的排隊時間；波紋線表示顧客得到服務的時間。1/14/202320SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略進程交互法中實體的進程不斷推進，直到某些延遲發(fā)生后才暫停。延遲可以分為：

進程中的復活點表示延遲結(jié)束后實體所到達的位置，即進程繼續(xù)推進的起點。條件延遲：延遲期的長短與系統(tǒng)狀態(tài)有關，事先無法確定。條件延遲發(fā)生后，實體停留在進程中的某點，直到條件得以滿足后才繼續(xù)向前移動。例如，隊列中的顧客一直在排隊，直到服務臺空閑且己處于隊首時才能離開隊列接受服務。

無條件延遲：實體停留在進程中的某點不再向前移動，直到預先確定的延遲期滿。例如，顧客停留在服務通道中直到服務完成。1/14/202321SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略通過所有進程中時間值最小的無條件延遲復活點來推進仿真時鐘；當時鐘推進到一個新的時刻點后，如果某一實體在進程中解鎖，就將該實體從當前復活點一直推進到下一次延遲發(fā)生為止。

進程交互法的基本思想：1/14/202322SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略1/14/202323SuChun,SoutheastUniversity離散事件系統(tǒng)仿真策略進程交互法兼有事件調(diào)度法和活動掃描法的特點，但其算法比兩者更為復雜。根據(jù)進程交互法建立的仿真模型稱為面向進程的仿真模型。面向進程仿真模型總控程序設計采用兩個事件表：

未來事件表（FutureEventList，F(xiàn)EL）

當前事件表（CurrentEventList，CEL）面向進程仿真模型總控程序步驟：未來事件表掃描。從FEL的實體記錄中檢出復活時間最小的實體，并將仿真時鐘推進到該實體的復活時間；移動記錄。將FEL中當前時間復活的實體記錄移至CEL中；當前事件表掃描。1/14/202324SuChun,SoutheastUniversity仿真時鐘推進機制

仿真時間推進機制（timeadvancemechanism）是指在仿真進程中將仿真時間從一個時刻推進到另一個時刻的方法，以便模擬動態(tài)系統(tǒng)的運行過程。仿真時間推進機制的種類、仿真時間單位所代表的實際時間的長短，直接影響仿真效率和仿真結(jié)果的有效性。離散事件系統(tǒng)仿真的時間推進機制：

固定步長時間推進制（fixed-incrementtimeadvancemechanism）

下次事件時間推進機制（nexteventadvancemechanism）

混合時間推進機制（mixedtimeadvancemechanism）1/14/202325SuChun,SoutheastUniversity仿真時鐘推進機制

固定步長時間推進機制：在仿真過程中仿真時鐘每次遞增一個固定的步長。該步長在仿真開始之前，根據(jù)模型特點確定，在仿真過程中保持不變。該推進方式要求每次推進都要掃描所有正在執(zhí)行的活動，以檢查此時間區(qū)間內(nèi)是否有事件發(fā)生。1/14/202326SuChun,SoutheastUniversity仿真時鐘推進機制T：仿真時鐘?t：步長固定步長時間推進機制原理框圖1/14/202327SuChun,SoutheastUniversity仿真時鐘推進機制1/14/202328SuChun,SoutheastUniversity仿真時鐘推進機制

固定步長時間推進機制的特點：

每次步長推進，都要進行事件檢查，占用計算和判斷的時間，影響仿真效率。步長?t越小，問題越嚴重。

該機制將發(fā)生在同一步長內(nèi)的事件都視為發(fā)生在該步長的末尾，即認為它們是同步的。由此產(chǎn)生誤差，影響仿真精度。步長?t越大，誤差越嚴重。合理確定?t，是固定步長時間推進機制中的重要問題。1/14/202329SuChun,SoutheastUniversity仿真時鐘推進機制

下次事件時間推進機制：仿真時鐘按照下一個事件預計將要發(fā)生的時刻，以不等的時間間隔向前推進。即仿真時鐘每次都跳躍性地推進到下一事件發(fā)生的時刻上去。該推進機制中，仿真時鐘的增量不定，取決于被仿真系統(tǒng)。仿真時，需將事件按發(fā)生時間的先后次序排列，仿真時鐘時間則按事件順序發(fā)生的時刻推進。當某一事件發(fā)生時，需立即計算出下一事件發(fā)生的時刻，以便推進仿真時鐘，直到仿真運行結(jié)束。1/14/202330SuChun,SoutheastUniversity仿真時鐘推進機制下次事件時間推進機制原理框圖1/14/202331SuChun,SoutheastUniversity仿真時鐘推進機制

下次事件時間推進機制能在事件發(fā)生的時刻捕捉到發(fā)生的事件，不會導致虛假的并發(fā)事件，精度高。下次事件時間推進機制取消了不必要的計算和判斷，有利于提高仿真的效率。

采用下次事件時間推進機制時，仿真效率主要取決于要發(fā)生的事件數(shù)，即取決于被仿真的系統(tǒng)，用戶無法控制調(diào)整。事件數(shù)越多，發(fā)生得越頻繁，仿真效率就越低。

對于仿真時間內(nèi)事件大量發(fā)生的系統(tǒng)，下次事件時間推進機制的仿真效率有可能比固定步長時間推進機制的仿真效率還低。對長時間內(nèi)只發(fā)生少量事件的系統(tǒng)仿真，采用下次事件時間推進機制能獲得高效率。1/14/202332SuChun,SoutheastUniversity仿真時鐘推進機制

固定步長時間推進機制可以通過調(diào)整步長來調(diào)整仿真的效率和精確度，但存在著影響效率的多余計算和仿真精度誤差。結(jié)論：

下次事件時間推進機制不存在多余的計算，具有高的仿真精度，但沒有調(diào)整仿真效率和仿真精確度的手段。

固定步長時間推進機制適合于對事件的發(fā)生在時間軸上呈均勻分布的系統(tǒng)的仿真；下次事件時間推進機制適合于事件發(fā)生數(shù)小的系統(tǒng)仿真。1/14/202333SuChun,SoutheastUniversity仿真時鐘推進機制混合時間推進機制：固定步長時間推進機制和下次事件時間推進機制的結(jié)合體。仿真時鐘每次推進一個固定時間步長的整數(shù)倍(n?t，n≥1)。步長?t可以在仿真前確定，并能在仿真過程中調(diào)整以獲得必要的仿真精度和仿真效率。與下次事件時間推進機制相似，混合時間推進機制可以跳過沒有事件發(fā)生的時間，避免多余的計算和判斷。

n取決于下次事件的發(fā)生時間，即取決于仿真系統(tǒng)的狀態(tài)。1/14/202334SuChun,SoutheastUniversity仿真時鐘推進機制

混合時間推進機制的原理：1/14/202335SuChun,SoutheastUniversity仿真時鐘推進機制

仿真效率與仿真精度：

仿真精度是指仿真結(jié)果與實際系統(tǒng)行為結(jié)果的接近程度。仿真結(jié)果與實際結(jié)果越接近，仿真精度越高。

仿真效率是指對同一系統(tǒng)在同樣一段時間的行為進行一次仿真時，所耗費計算機機時的多少。費時少則效率高，費時多則效率低。對同一系統(tǒng)而言，仿真效率和仿真精度均與仿真模型、仿真算法及時間推進機制有關。1/14/202336SuChun,SoutheastUniversity仿真時鐘推進機制

固定步長時間推進機制的效率完全取決于步長，步長越長則效率越高，步長越短則效率越低。若要完全消除因步長而造成的誤差則步長需趨于0，機時趨于無窮大。

下次事件時間推進機制的效率完全取決于在仿真時間內(nèi)發(fā)生的事件數(shù)，用戶無法改變仿真效率。

混合時間推進機制的效率不僅與步長有關，而且與事件的時間分布有關。步長越長，事件在時間軸上的分布越不均勻，效率就越高，反之越低，1/14/202337SuChun,SoutheastUniversity仿真時鐘推進機制

在同樣的仿真精度下，采用混合時間推進機制的效率不低于采用固定步長時間推進機制的效率。

對同一實際系統(tǒng)進行仿真時，采用混合時間推進機制的效率不低于采用下次事件時間推進機制的效率。1/14/202338SuChun,SoutheastUniversity消息驅(qū)動的仿真機制（message-driving）的仿真機制是面向?qū)ο螅╫bject-oriented）

程序設計方法在系統(tǒng)仿真中的應用。以面向?qū)ο蟮挠^點，制造系統(tǒng)S是由對象（如加工設備、生產(chǎn)計劃等）以及對象之間的關系組成。在數(shù)學上，系統(tǒng)S可以表示為：

S=（O，R）式中：O={Oi}是系統(tǒng)中對象的集合。其中：Oi表示系統(tǒng)中的對象i，i=1，2，…，n；n為系統(tǒng)中對象的數(shù)目。

R={Rij}是系統(tǒng)中對象之間關系的集合。其中：i，j=1，2，…，n，且i≠j；Rij表示對象i與j之間的關系。1/14/202339SuChun,SoutheastUniversity消息驅(qū)動的仿真機制消息驅(qū)動的仿真機制提供了自然、能反映現(xiàn)實世界的開發(fā)環(huán)境。它將被仿真的系統(tǒng)視為實體（entity）的集合，實體之間通過消息（message）進行通信，系統(tǒng)中的事件即是實體之間消息的傳遞。對象（類）具有用屬性（attribute）、狀態(tài)（state）以及方法（method）表示的自身行為特性。對象之間的聯(lián)系用消息（

message）來描述。系統(tǒng)的動態(tài)過程就是由對象的方法以及對象之間相互聯(lián)系的消息組成。

消息驅(qū)動的仿真中，實體（entity）有兩個形式：活動、等待。如果實體當前正在執(zhí)行動作，則是“活動”的；否則，實體狀態(tài)為“等待”。只有當一個體接收到一個消息而滿足了等待條件或它的等待時間期滿時，它才能由等待狀態(tài)轉(zhuǎn)為活動狀態(tài)。1/14/202340SuChun,SoutheastUniversity消息驅(qū)動的仿真機制

實體（entity）

消息體（message）Create短語：創(chuàng)建新的實體

Free短語：終結(jié)實體

Sendmessage短語：實體之間發(fā)送消息

Wait短語：用于定義實體等待一段時間或等待接收消息…消息驅(qū)動的仿真模型的基本要素：1/14/202341SuChun,SoutheastUniversity混合系統(tǒng)仿真策略1/14/202342SuChun,SoutheastUniversity蒙特卡羅仿真方法蒙特卡羅（MonteCarlo）法亦稱為隨機仿真（randomsimulation）方法、隨機抽樣（randomsampling）技術或統(tǒng)計試驗（statisticaltesting）方法。

20世紀40年代，MonteCarlo仿真首先應用于核武器研制。

美國“曼哈頓計劃”的主持人之一數(shù)學家馮·諾依曼首先采用數(shù)學方法直接模擬裂變物質(zhì)的中子隨機擴散，并以位于摩納哥國的世界聞名賭城蒙特卡羅作為秘密代號。用賭城名比喻隨機仿真，風趣貼切，該方法很快得到接受。此后，人們便把這種計算機隨機仿真方法稱為蒙特卡羅方法目前，蒙特卡羅方法已經(jīng)在物理、工程技術、經(jīng)濟、金融、社會、決策等領域得到廣泛應用。1/14/202343SuChun,SoutheastUniversity蒙特卡羅仿真方法蒙特卡羅方法以統(tǒng)計抽樣理論為基礎，根據(jù)實際系統(tǒng)抽象出概率模型或隨機過程，產(chǎn)生隨機數(shù)，并通過對隨機變量統(tǒng)計、抽樣實驗或隨機模擬，以統(tǒng)計特征量作為待解問題的數(shù)值解。

蒙特卡羅方法的基本原理：①根據(jù)實際問題建立概率統(tǒng)計模型，所構(gòu)造模型的主要特征參量要與實際問題或系統(tǒng)相一致；②建立隨機變量的抽樣方法，包括產(chǎn)生偽隨機數(shù)及各種分布隨機變量抽樣序列的方法；④分析仿真試驗結(jié)果，給出問題的概率解或解的精度估計。③按照所建立的模型進行仿真試驗、計算，求出問題的隨機解。1/14/202344SuChun,SoutheastUniversity蒙特卡羅仿真方法

蒙特卡羅方法的優(yōu)點：①收斂速度、計算的復雜性與問題維數(shù)無關，計算時間僅與維數(shù)成比例。④在某些領域（如粒子物理等），該方法具有其他數(shù)值計算方法不能替代的作用。②受問題條件的限制的影響較小。③程序結(jié)構(gòu)簡單、清晰，便于編制和調(diào)試。1