離散事件仿真

第4章離散事件仿真基礎(chǔ)離散事件系統(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ù)為解決這列問題提供了有效的手段。1計算機仿真技術(shù)基礎(chǔ)第4章離散事件仿真基礎(chǔ)4.1離散事件系統(tǒng)與模型4.2離散事件仿真4.3排隊系統(tǒng)的仿真4.4Petri網(wǎng)絡(luò)仿真2計算機仿真技術(shù)基礎(chǔ)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)度車輛和安排工序。3計算機仿真技術(shù)基礎(chǔ)連續(xù)系統(tǒng)與離散事件系統(tǒng)仿真的區(qū)別在連續(xù)系統(tǒng)數(shù)字仿真中，時間通常被分割成均等或非均等的時間間隔，并以一個基本的時間間隔計時。而離散事件仿真通常是面對事件的，時間指針不是固定增值推進，而是由事件的推動而隨機遞進。連續(xù)系統(tǒng)仿真中，系統(tǒng)的動力學模型是由表征系統(tǒng)變量之間的關(guān)系的方程來描述的，仿真的結(jié)果表現(xiàn)為系統(tǒng)變量隨時間變化的歷程。離散時間仿真中，系統(tǒng)變量是反映系統(tǒng)各部分相互作用的一些時間，而系統(tǒng)模型則是反映這些事件的集合，仿真結(jié)果是表現(xiàn)為這些事件的事件歷程。44.1離散事件系統(tǒng)與模型計算機仿真技術(shù)基礎(chǔ)4.1離散事件系統(tǒng)與模型離散事件研究背景離散事件的研究可以追溯到對排隊現(xiàn)象和排隊網(wǎng)絡(luò)的分析，排隊論最早有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ù)學規(guī)劃和調(diào)度排序等方法是解決這類問題的主要數(shù)學方法.離散事件的仿真技術(shù)研究，在國內(nèi)是近二十多年才開始的，受到計算機技術(shù)、信息處理技術(shù)、控制技術(shù)、人工智能技術(shù)等新技術(shù)的影響而發(fā)展。對于離散事件構(gòu)成的離散事件系統(tǒng)或連續(xù)-離散混合系統(tǒng)的研究，逐漸成為仿真技術(shù)應(yīng)用的一個重要分支領(lǐng)域。5計算機仿真技術(shù)基礎(chǔ)4.1.1離散事件系統(tǒng)的基本要素離散事件系統(tǒng)的一些基本要素包括：實體、活動、事件等.以超市購物系統(tǒng)為例：[例4.1]華聯(lián)超市濟南大學分店，共有10個服務(wù)臺供顧客結(jié)帳，營業(yè)時間為9：00–21：00，顧客選購?fù)晟唐返椒?wù)臺結(jié)帳的時間是隨機的，而且各自獨立，每位顧客接受服務(wù)的時間長短也是隨機的。描述該系統(tǒng)的狀態(tài)，可以是：服務(wù)臺的狀態(tài)：忙，閑顧客排隊等待的隊長：0，1，2，…6計算機仿真技術(shù)基礎(chǔ)臨時實體：只存在一段時間，由系統(tǒng)外部到達和進入系統(tǒng)。如超市系統(tǒng)里的顧客，該臨時實體隨機到達系統(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)生的.7服務(wù)員超市系統(tǒng)顧客進入系統(tǒng)顧客排隊接受服務(wù)的顧客顧客離開1.實體(Entity)臨時實體永久實體計算機仿真技術(shù)基礎(chǔ)引起系統(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)實體屬性等。8顧客到達事件顧客開始接受服務(wù)事件顧客服務(wù)完畢離去顧客離開超市系統(tǒng)顧客進入系統(tǒng)顧客排隊服務(wù)員接受服務(wù)的顧客臨時實體永久實體2.事件(Event)計算機仿真技術(shù)基礎(chǔ)離散事件中的活動，通常用于表示兩個可以區(qū)分的事件之間的過程，是實體在兩個事件之間保持某一個狀態(tài)的持續(xù)過程。

它標志著系統(tǒng)狀態(tài)之間的轉(zhuǎn)移。“排隊活動”標志著排隊隊長發(fā)生變化，“接受服務(wù)活動”使隊長變化或服務(wù)員由“忙”到“閑”。9超市系統(tǒng)顧客進入系統(tǒng)顧客排隊服務(wù)員接受服務(wù)的顧客顧客離開3.活動(Activity)顧客到達事件顧客開始接受服務(wù)事件顧客服務(wù)完畢離去排隊活動接受服務(wù)活動臨時實體永久實體計算機仿真技術(shù)基礎(chǔ)進程是由若干個事件和若干個活動組成，它描述了事件及活動之間的相互邏輯關(guān)系及時序關(guān)系。10超市系統(tǒng)顧客進入系統(tǒng)顧客排隊服務(wù)員接受服務(wù)的顧客顧客離開4.進程(Process)顧客到達事件顧客開始接受服務(wù)事件顧客服務(wù)完畢離去排隊活動接受服務(wù)活動臨時實體永久實體顧客超市結(jié)帳服務(wù)進程計算機仿真技術(shù)基礎(chǔ)[例4.2]在一個有較大水位落差河段上的船閘運行系統(tǒng)，從上游新來的船只到達船閘時，進行排隊，排到時，船閘打開，船只過閘，最后船只離開船閘。

該系統(tǒng)的實體、事件、活動和進程，它們之間的關(guān)系？11實體：船只為臨時實體，船閘為永久實體.事件：船只到達事件，過閘服務(wù)開始事件，過閘服務(wù)結(jié)束事件(船只離開事件)活動：船只排隊活動，過閘服務(wù)活動進程：船只過閘服務(wù)進程船只到達事件過閘服務(wù)開始事件過閘服務(wù)結(jié)束事件船只過閘服務(wù)進程排隊活動過閘服務(wù)活動計算機仿真技術(shù)基礎(chǔ)125.仿真鐘(SimulatingClock)仿真鐘用于表示仿真時間的變化，在連續(xù)系統(tǒng)中，仿真時間的變化基于仿真步長的確定，可以是定步長或變步長。在離散事件系統(tǒng)中，引起系統(tǒng)狀態(tài)變化的事件發(fā)生時間是隨機的，因而仿真時鐘的步長也是隨機的。

從一個事件發(fā)生時刻推進到另一個事件發(fā)生時刻，具有跳躍性和隨機性。超市系統(tǒng)顧客進入系統(tǒng)顧客排隊服務(wù)員接受服務(wù)的顧客計算機仿真技術(shù)基礎(chǔ)136.統(tǒng)計計數(shù)器(StatisticCounter)離散事件的狀態(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)變量，得到相關(guān)的統(tǒng)計意義.超市系統(tǒng)顧客進入系統(tǒng)顧客排隊服務(wù)員接受服務(wù)的顧客計算機仿真技術(shù)基礎(chǔ)4.1.2離散事件系統(tǒng)模型的建立離散事件系統(tǒng)研究和仿真中最基本的問題就是系統(tǒng)的建模.20世紀80年代出，Y.C.Ho教授倡導(dǎo)對離散事件動態(tài)系統(tǒng)理論(DisctributedEventDynamicSystem,DEDS)進行研究，而后學多學者對這個問題從不同層次或用不同的數(shù)學工具進行了描述，形成了許多的方法體系，并出現(xiàn)了多種形式的DEDS模型設(shè)計方法。

例如，考慮對象演變過程的分析，根據(jù)事件發(fā)生的時間是否有必要納入研究范圍，可以劃為分：不帶時標的DEDS模型：有限狀態(tài)自動機模型、Petri網(wǎng)絡(luò)模型、過程代數(shù)模型、時序邏輯模型等。帶時標的DEDS模型：賦時Petri網(wǎng)絡(luò)模型、TIM/RTIL模型、雙子代數(shù)模型、排隊網(wǎng)絡(luò)模型、Markov鏈模型與CSMP模型等。14計算機仿真技術(shù)基礎(chǔ)4.1.2離散事件系統(tǒng)模型的建立還可以根據(jù)系統(tǒng)輸入信息及狀態(tài)演變的確定性/不確定性，分成確定性DEDS模型和隨機性DEDS模型。根據(jù)狀態(tài)變化的量化特征，分成邏輯（定性）模型與數(shù)量（定量）模型等。從現(xiàn)有各類的DEDS模型來看，尚沒有通用的、適合于各類研究對象的模型表示形式。

從現(xiàn)有模型的形成過程來看，DEDS模型的常用辦法主要有排隊論方法網(wǎng)絡(luò)圖或事件圖法形式語言與自動機法隨機過程描述法（如Markov過程和CSMP過程）抽象代數(shù)法（如雙子代數(shù)、極小代數(shù)、極大代數(shù)）15計算機仿真技術(shù)基礎(chǔ)離散事件建模的步驟明確仿真目的 建模之前，必須根據(jù)仿真目的，確定所需要獲取的某一事件或系統(tǒng)的信息、模型類型、資料及數(shù)據(jù)。目的不同，所建立的模型也不同，衡量仿真結(jié)果的逼真性準則也就不同。

甚至對某一仿真目的，模型是有效的，而對另一仿真目的，模型可能就是無效的。

比如，[例4.2]中的船閘運行系統(tǒng)中，如果仿真目的是了解船閘服務(wù)時間長短對船閘利用率的影響，這種情況屬于排隊論模型。如果還要分析閘門的開關(guān)控制和動力學特性，以及注水放水過程特性，系統(tǒng)應(yīng)視為連續(xù)-離散混合型系統(tǒng)。

16計算機仿真技術(shù)基礎(chǔ)離散事件建模的步驟2. 正確描述系統(tǒng)組成成分： 指對描述系統(tǒng)仿真目的有意義的實體，這些實體的行為往往是隨機分布的。

如超市系統(tǒng)中的顧客、服務(wù)員是系統(tǒng)的實體，船閘運行系統(tǒng)中的船只、船閘也是系統(tǒng)實體。描述變量和參數(shù)： 指系統(tǒng)各實體的屬性。

描述變量包括內(nèi)部變量和外部變量，除了輸入和輸出變量外，其余均為狀態(tài)變量。參數(shù)可以在仿真前由用戶設(shè)置或在仿真過程中根據(jù)用戶的命令加以改變。比如，船閘運行系統(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)描述中極為重要的。

17計算機仿真技術(shù)基礎(chǔ) 如，船閘運行系統(tǒng)中的事件：船只到達、船閘開始服務(wù)、船閘結(jié)束服務(wù)、船只離開?；顒佑校号抨牷顒?、過閘服務(wù)等。按仿真目的表示出這些事件發(fā)生的順序、活動持續(xù)過程，以便描述出系統(tǒng)間的相互關(guān)系，由此可以進一步畫出系統(tǒng)的流程圖和網(wǎng)絡(luò)圖。18船只到達查詢船閘空閑狀態(tài)？船閘服務(wù)船只離開置船閘為閑Y排隊等候N船閘服務(wù)系統(tǒng)流程圖：計算機仿真技術(shù)基礎(chǔ)離散事件建模的步驟3. 仿真模型的建立 流程圖僅能表明整個過程中發(fā)生的“事件”表，要仿真這樣一系列“事件”，必須知道確切的時間表，這就是仿真系統(tǒng)建模。 假設(shè)船閘服務(wù)系統(tǒng)中，船只到達的時間間隔是平均值為70分鐘，變化范圍為正負14分鐘的均勻分布的隨機數(shù)，船閘服務(wù)時間是平均值為60分鐘，變化范圍為正負7分鐘的均勻分布的隨機數(shù)。則可以得到系統(tǒng)的含有隨機概率模型的仿真系統(tǒng)模型。19計算機仿真技術(shù)基礎(chǔ)20船只到達查詢船閘空閑狀態(tài)？船閘服務(wù)船只離開置船閘為閑Y排隊等候N開始置仿真開始和結(jié)束時間船只到達時間間隔70分鐘船閘服務(wù)系統(tǒng)流程圖：船閘服務(wù)系統(tǒng)仿真模型圖：系統(tǒng)流程大于結(jié)束時間？結(jié)束YN計算機仿真技術(shù)基礎(chǔ)離散事件建模的步驟4. 輸出函數(shù)的確定 在建立了系統(tǒng)模型的基礎(chǔ)上，還需要確定輸出函數(shù)。根據(jù)仿真目的統(tǒng)計計算出反應(yīng)系統(tǒng)性能的數(shù)據(jù)，這些數(shù)據(jù)就是系統(tǒng)的輸出。 如船閘服務(wù)系統(tǒng)中，可以求出船只的平均等待時間、最大隊列長度和船閘利用率。21計算機仿真技術(shù)基礎(chǔ)4.2離散事件仿真4.2.1離散事件系統(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)的概念。

22計算機仿真技術(shù)基礎(chǔ)仿真程序的主要成分：采用步長法仿真的程序主要由以下部分組成：①仿真時鐘：提供仿真時間的當前值②事件表：由策劃和事件調(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ù)全過程23計算機仿真技術(shù)基礎(chǔ)2. 仿真程序的流程管理：仿真流程管理（即仿真調(diào)度）是仿真建模的核心.(1)仿真時鐘 離散事件系統(tǒng)仿真中時間的變化是用一個邏輯時鐘的時間數(shù)來表示。

仿真時間與所有實體的活動及所有事件的調(diào)度有關(guān)系，仿真時間與真實時間可以通過選定的時間的比例尺相關(guān)聯(lián)。每一事件通過被調(diào)度事件時間與仿真時鐘相關(guān)聯(lián)，當對應(yīng)的物理事件發(fā)生時，這個事件時間就對應(yīng)于實際系統(tǒng)的真實時間。 仿真時鐘一般有兩種推進方式：時間步長法： 在進行系統(tǒng)仿真的同時，可以把整個仿真過程分成許多相等的時間間隔，時間步長的長度可根據(jù)實際問題分別取秒、分、小時等，程序中按此步長前進的時鐘就是仿真時鐘。

選取系統(tǒng)的一個初始狀態(tài)作為仿真時鐘的零點，仿真時鐘每步進一次，就對系統(tǒng)的所有實體、屬性和活動進行一次全面的掃描考察，按照預(yù)定的計劃和目標進行分析、計算和記錄系統(tǒng)狀態(tài)的變化，這個過程一直進行到仿真時鐘結(jié)束為止

24計算機仿真技術(shù)基礎(chǔ)事件步長法： 以事件發(fā)生的時間為增量，按照時間的進展，一步一步地對系統(tǒng)的行為進行仿真，知道預(yù)定的仿真時間結(jié)束為止。事件步長法和時間步長法的主要區(qū)別：

①兩者都是以時間為增量來考察系統(tǒng)狀態(tài)的變化的。

但在時間步長法中，仿真時鐘以等步長前進，而在事件步長法中，仿真時鐘步長取決與事件的時間間隔。 ②時間步長法在一個步長內(nèi)，認為系統(tǒng)所處的狀態(tài)相同，因而所選的步長大小將影響系統(tǒng)的精度.而在事件步長法中，每個事件的發(fā)生均有確切的時刻，不需要認為地選取步長，步長的大小對仿真的精度影響較小。 ③時間步長法每步都要對系統(tǒng)進行一次全面的考察，即使系統(tǒng)狀態(tài)沒有發(fā)生變化。

事件步長法只在事件發(fā)生時才進行掃描。

一般來說，當事件數(shù)目較大或事件變化呈周期性特點時，用時間步長法可以節(jié)省用機時間。而當相繼兩個事件出現(xiàn)的平均間隔較長時，更適合于采用事件步長法。 如上所述，事件進程管理有面向事件的，為變步長法，也有面向時間間隔的，為定步長法。25計算機仿真技術(shù)基礎(chǔ)(2)事件表 為了使仿真程序能如實地模擬實際系統(tǒng)的變化，在某些離散事件的仿真鐘，采用事件表的形式進行調(diào)度。事件表一般是一個有序的記錄表，每個記錄包括發(fā)生的時間、事件的類型等一些內(nèi)容。 事件步長法中常用到的事件表法的主要思想是將系統(tǒng)的仿真過程看成是一個事件點序列，根據(jù)事件出現(xiàn)的時序，用一個稱之為事件表的表格來調(diào)度事件執(zhí)行的順序。

對于當前需要處理的事件，列入事件表中，從中取出最接近的事件進行處理，處理完畢后自動推出事件表。

在處理當前事件的過程中，往往會產(chǎn)生一個后繼事件。因此，必須預(yù)測出此后繼事件的出現(xiàn)時刻，并將其列入事件表中。

這樣，事件表好像一本記事簿，完成一件事情后將它從記事簿中消除，把新的要完成的工作再列入記事簿中，按照這樣的方式，將系統(tǒng)仿真進行下去。 這種方法要求對系統(tǒng)的各種事件進行詳細的描述，當事件之間沒有太多相互作用或事件數(shù)目不多時，事件表法比較有效。26計算機仿真技術(shù)基礎(chǔ)(3)同時事件管理

同類同時事件管理： 發(fā)生在同一時刻并且隸屬于同一類型的幾個事件叫同類同時事件。它會導(dǎo)致模型的下一狀態(tài)出現(xiàn)多種可能值，即可能出現(xiàn)集中排隊順序。為此，我們需要先定好條件，使狀態(tài)取值為唯一，也就是規(guī)定一種排隊規(guī)則來管理這些同類同時事件。例如，先進先出（先到先服務(wù)）規(guī)則、后進先出（后到先服務(wù)）原則、隨機規(guī)則、優(yōu)先服務(wù)原則.

混合同時事件管理： 發(fā)生在同一時刻但不屬于同一類型的幾個事件叫混合同時事件。

確定這些混合同時事件所造成的狀態(tài)的變化，通常有一步法與解結(jié)法。 一步法就是直接確定混合同時事件所形成的結(jié)果狀態(tài)，解結(jié)法是把幾個同時事件分解成多個單獨事件的序列進行處理.。 對于簡單的情況，一步法與解結(jié)法將會得到相同的結(jié)果。但一步法不易寫成通用形式，且比較復(fù)雜，而解結(jié)模型簡單，通用性好。27計算機仿真技術(shù)基礎(chǔ)4.2.2離散事件系統(tǒng)仿真策略因為模型類型不同，仿真方法也會不同。我們主要介紹最常用的排隊網(wǎng)絡(luò)模型所使用的仿真方法。在離散事件模型里，實體活動、進行都是以事件為基礎(chǔ)構(gòu)成的，所以從事件、活動、進程三個層次來組織事件構(gòu)成了處理離散事件模型的三種典型方法：事件調(diào)度法(EventScheduling)

這種方法有一個時間控制程序，從事件表中選擇具有最早發(fā)生時間的事件，并將仿真時鐘改到該事件發(fā)生的時刻，再調(diào)用與該事件相應(yīng)的程序模塊，對事件進行處理，該事件處理完畢后，返回時間控制程序。這樣，事件的選擇和處理不斷交替進行，直到仿真終止的程序發(fā)生。

在這種方法中，任何條件的測試均在相應(yīng)的事件模塊中進行，顯然是一種面向事件的仿真方法。

28計算機仿真技術(shù)基礎(chǔ)活動掃描法(ActivityScanning)

系統(tǒng)由部件（對應(yīng)與實體）組成，而部件包含有活動，該活動是否發(fā)生取決于規(guī)定的條件，有一個專門的模塊來確定激活條件，若條件滿足，則激活相應(yīng)部件的活動模塊。時間控制程序較其它的條件有更高的優(yōu)先級，即在判斷激活條件時首先判斷該活動發(fā)生的時間是否滿足，然后再判斷其它條件。

若所有條件滿足，則執(zhí)行該部件的活動模塊，然后再對其它部件掃描，對所有部件掃描一遍后，按同樣順序進行循環(huán)掃描，知道仿真終止。進程交互法(ProcessInteraction)

這種方法綜合了事件調(diào)度法和活動掃描法的特點，采用兩張事件表，即當前事件表（CEL）和將來事件表（FEL）。首先按一定的分布產(chǎn)生到達實體并置于FEL中，實體進入排隊等待；然后對CEL進行活動掃描，判斷各種條件是否滿足；再將滿足條件的活動進行處理，仿真鐘推進到服務(wù)結(jié)束并將相應(yīng)的實體從系統(tǒng)中清除；最后將FEL中最早發(fā)生的當前事件實體移到CEL中，繼續(xù)推進仿真時鐘，對CEL進行活動掃描，直到仿真結(jié)束。29計算機仿真技術(shù)基礎(chǔ)4.2.3離散事件仿真研究的一般步驟301.系統(tǒng)建模模型一般用流程圖來描述。模型包含有隨機變量，其分布類型和特征是十分重要的。2.確定仿真算法一是如何產(chǎn)生所需要的隨機變量二是仿真建模策略：事件調(diào)度法：按事件的觀點建立仿真策略活動掃描法：用活動來描述事件之間的過程，面向活動建模進程交互法：進程作為建模的基本單元計算機仿真技術(shù)基礎(chǔ)313.建立仿真模型數(shù)學模型中最廣泛的類型是狀態(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é)果僅僅是隨機變量的一次取樣，那么，仿真結(jié)果的可信性如何？如何提高仿真結(jié)果的置信度？這些都是十分重要和有待解決的關(guān)鍵問題。5.仿真結(jié)果處理分析可以采用通用的或?qū)Ｓ玫母呒壵Z言編寫算法。計算機仿真技術(shù)基礎(chǔ)4.3排隊系統(tǒng)的仿真排隊系統(tǒng)是日常生活、工業(yè)生產(chǎn)、交通和電信網(wǎng)絡(luò)中常見的現(xiàn)象，比如：病人到醫(yī)院看病，顧客到銀行取款，乘客到售票處買票交通堵塞，電信業(yè)務(wù)，自動生產(chǎn)線加工零件，計算機網(wǎng)絡(luò)數(shù)據(jù)包等待傳送…一般來說，當某個時候要求服務(wù)的數(shù)量超過服務(wù)機構(gòu)的容量，就會出現(xiàn)排隊現(xiàn)象。在排隊現(xiàn)象中，服務(wù)對象可以是人，也可以是物，還可以是某種信息。在各種排隊系統(tǒng)中，由于對象到達的時刻與接受服務(wù)的時間都是不確定的，隨著不同的時間及條件而變化，所以排隊系統(tǒng)在某個時刻的狀態(tài)也是隨機的。排隊越長，浪費的時間就越多，系統(tǒng)的效率低下，但盲目增加服務(wù)設(shè)備，會增加投資或發(fā)生空閑浪費，反而不能提高效率。因此，要考慮如何在兩者之間取得平衡，提高服務(wù)質(zhì)量并降低成本。32計算機仿真技術(shù)基礎(chǔ)4.3排隊系統(tǒng)的仿真排隊問題實質(zhì)上是一個平衡等待時間和服務(wù)臺空閑時間的問題，也就是如何確定一個排隊系統(tǒng)，使實體（等待服務(wù)的人、物和信息）和服務(wù)臺兩者都有利，排隊論就是解決這類問題的一門學科，又稱隨機服務(wù)理論，因為實體到達和接受服務(wù)的時間常常是某種概率分布的隨機變量。4.3.1排隊論的基本概念4.3.2到達時間間隔和服務(wù)時間的分布4.3.3排隊系統(tǒng)分析33計算機仿真技術(shù)基礎(chǔ)4.3.1排隊論的基本概念1. 排隊系統(tǒng)的組成

①到達模式：指動態(tài)實體按什么樣的規(guī)則到達，描寫實體到達的統(tǒng)計特性 ②服務(wù)機構(gòu)：指同一時間有多少服務(wù)臺可以接納動態(tài)實體，他們的服務(wù)需要多少時間，服從什么樣的分布 ③服務(wù)規(guī)則：指對下一個實體服務(wù)的選擇原則.

34動態(tài)實體排隊服務(wù)機構(gòu)到達接受服務(wù)如何通過已知的到達模式和服務(wù)時間的概率分布，來研究排隊系統(tǒng)的隊伍長度和服務(wù)機構(gòu)“忙”或“閑”的程度，就是離散事件仿真所要解決的問題.計算機仿真技術(shù)基礎(chǔ)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)減小.35動態(tài)實體排隊服務(wù)機構(gòu)到達接受服務(wù)排隊系統(tǒng)計算機仿真技術(shù)基礎(chǔ)

④到達時間變化系數(shù) 定義為到達時間間隔的標準差Sa與平均到達時間間隔Ta的比值Sa/Ta，它是一個無量綱的系數(shù)，描述了數(shù)據(jù)圍繞平均值的分散程度。 指數(shù)分布的平均值與標準差相同，所以其變化系數(shù)為1。

如果觀測到的變化系數(shù)接近與1，則用指數(shù)分布去擬合這些數(shù)據(jù)是合理的。

當變化系數(shù)比1小得多時，經(jīng)常應(yīng)用愛爾朗分布。

顧客的到達模式如果按顧客到達的方式來劃分，可能是一個一個的，也可能是成批的；如果按相繼到達的時間間隔劃分，則可能是確定型的或隨機型的；如果按到達的過程劃分，那么可以是平穩(wěn)的，或非平穩(wěn)的。36動態(tài)實體排隊服務(wù)機構(gòu)到達接受服務(wù)排隊系統(tǒng)計算機仿真技術(shù)基礎(chǔ)3. 服務(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)的。37動態(tài)實體排隊服務(wù)機構(gòu)到達接受服務(wù)排隊系統(tǒng)計算機仿真技術(shù)基礎(chǔ)4. 排隊規(guī)則

排隊規(guī)則是指顧客按一定的次序接受服務(wù)。服務(wù)次序可以采用下列規(guī)則：先到先服務(wù)：即按到達次序接受服務(wù)，這是最常見的情形。后到先服務(wù)：如乘電梯的乘客通常是后到先出的。倉庫中堆放的大件物品也是后到先出。

情報系統(tǒng)中，最后到達的信息往往最具有價值。隨機服務(wù)：當服務(wù)臺空時，從等待的顧客中隨機選取一名進行服務(wù)。優(yōu)先權(quán)服務(wù)：醫(yī)院中的急診病人，機場頭等艙客戶。多個服務(wù)臺情形：假設(shè)n個服務(wù)臺，顧客排成n隊，當某個顧客到達時，以概率Pi進入第i隊。38動態(tài)實體排隊服務(wù)機構(gòu)到達接受服務(wù)排隊系統(tǒng)計算機仿真技術(shù)基礎(chǔ)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)實體排隊時間不同。在仿真實驗中，對這兩個量的變化進行統(tǒng)計，以求出其數(shù)字特征：如均差、方差、最大值、最小值等，這些數(shù)字特征反應(yīng)了一個服務(wù)系統(tǒng)的重要特性。39動態(tài)實體排隊服務(wù)機構(gòu)到達接受服務(wù)排隊系統(tǒng)計算機仿真技術(shù)基礎(chǔ)6. 排隊模型的分類

肯德爾（Kendall）對并列服務(wù)臺的情形提出了一個分類方法，其符號形式是：X/Y/Z，其中

X：相繼到達的時間間隔分布/Y：服務(wù)時間的分布/Z：并列的服務(wù)臺數(shù)目

常用的表示相繼到達的時間間隔和服務(wù)時間的概率分布符號是：

M：負指數(shù)分布（M指Markov性）/D：確定性（Deterministic）/Ek：k階愛爾朗（Erlang）分布/GI：一般相互獨立的隨機分布/G：一般隨機分布 例如，M/M/1表示相繼到達的時間間隔為負指數(shù)分布，服務(wù)時間為負指數(shù)分布，單服務(wù)臺模型；D/M/2表示確定的到達時間間隔，服務(wù)時間為負指數(shù)分布，兩個平行服務(wù)臺模型.40動態(tài)實體排隊服務(wù)機構(gòu)到達接受服務(wù)排隊系統(tǒng)計算機仿真技術(shù)基礎(chǔ)4.3.2到達時間間隔和服務(wù)時間的分布解決排隊問題首先要根據(jù)先驗知識做出顧客到達時間間隔和服務(wù)時間的經(jīng)驗分布，然后再利用統(tǒng)計學的方法確定其相應(yīng)的理論分布，并估計其參數(shù)值.下面列出幾種常用的理論分布.1.定長分布 這是最簡單的情形，每個動態(tài)實體在恒定的時間間隔內(nèi)到達，或者是每個動態(tài)實體接受服務(wù)的時間是常數(shù).41計算機仿真技術(shù)基礎(chǔ)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)至少有兩個顧客到達的概率，則42 ④有限性。 任意區(qū)間內(nèi)到達有限個顧客的概率之和為1，即

如果顧客到達時間滿足泊松分布，則在時間t內(nèi)到達k個顧客的概率為計算機仿真技術(shù)基礎(chǔ)2.泊松（Poisson）分布43

其中λ為泊松分布常數(shù).

令第i個顧客到達的時刻為τi(i=1,2,…)，并令τ0=0，那么顧客相繼到達的時間間隔ti=τi–τi-1

是獨立分布的，其分布函數(shù)為負指數(shù)分布：

泊松分布中，顧客到達的時間完全是隨機的，僅僅受到給定的平均速率λ的限制.許多排隊系統(tǒng)的到達模式都屬于泊松分布.

因為平均速率λ=1/Ta.可求得數(shù)學期望和方差為：計算機仿真技術(shù)基礎(chǔ)3.愛爾朗（Erlang）分布44

設(shè)