55090離散系統(tǒng)仿真與優(yōu)化面向工業(yè)工程的應用電子課件chapter原理

離散系統(tǒng)建模與仿真面向工業(yè)工程的應用王謙博士/副教授南開大學商學院管理科學與工程系

Chapter2離散事件仿真原理2.1

離散事件仿真的術語和概念隨機性隨機性（randomness，stochastic），也稱不確定性（uncertainty），是指那些影響系統(tǒng)穩(wěn)定性表現(xiàn)的干擾因素，也稱噪聲一般情況下，系統(tǒng)的隨機性是由多個可知或不可知因素造成的，這些因素相互作用和影響的機制難以研究，并且隨機特征隨時間變化為簡化起見，我們將其作為一個整體影響因子去研究2.1

離散事件仿真的術語和概念系統(tǒng)system由眾多實體（entity）構成，例如顧客或者機器設備，實體之間相互作用、相互影響，系統(tǒng)狀態(tài)隨時間變化而可能發(fā)生變化，往往具有某種目的和目標模型model模型是對現(xiàn)實世界系統(tǒng)（realworldsystem）的邏輯抽象，模型在結構、邏輯、數(shù)學關系描述等方面與現(xiàn)實系統(tǒng)保持基本的一致（不一定完全一致，依賴于所研究的問題），模型所包含的指標和內(nèi)容有：系統(tǒng)狀態(tài)、實體及其屬性、集合、處理過程、事件、活動和時間延遲系統(tǒng)狀態(tài)systemstate模型中所有變量的所有可能的取值的集合，它包含了真實系統(tǒng)所有可能的狀態(tài)實體entity存在于系統(tǒng)中、可相互區(qū)別的具體的事物，例如顧客、服務員、自動柜員機、零件、車床、車輛，等等實體屬性entityattribute實體所具有的特征，例如類型、加工時間、優(yōu)先級、顏色、材質(zhì)、計量單位，等等2.1

離散事件仿真的術語和概念列表list列表有兩種含義，一是清單，例如實體名單、事件列表；二是隊列，例如排隊顧客所形成的隊列，且需要事先制訂排隊規(guī)則（先到先服務，優(yōu)先級，等等）事件event瞬間發(fā)生的、能夠改變系統(tǒng)狀態(tài)的那些事情（occurrence）事件預告eventnotice載有事件發(fā)生時刻、事件相關數(shù)據(jù)的記錄（record），例如記載事件類型和發(fā)生時間的信息記錄事件列表eventlist由事件預告組成的、記錄將要發(fā)生事件的列表，按照時間順序排列，也被稱為未來事件列表（futureeventlist）2.1

離散事件仿真的術語和概念活動activity

活動是一個過程，持續(xù)時間長度大體上是確定的，即適合于特定的統(tǒng)計分布和參數(shù)，比如汽車加油、零件加工、顧客購票等等，會有相關的實體參與。延遲delay

延遲也是一個過程，與活動不同，延遲時間長度是難以確定的，例如某一個顧客在隊列中的等待時間，就具有很大的隨機性，難以預知。需要說明的是，隊列中全部顧客的等待時間具有統(tǒng)計學規(guī)律，擁有特定的期望值（expectation）。時鐘CLOCK

用于仿真模型及其模擬過程，具有跳躍性和不連續(xù)性，與現(xiàn)實世界的時鐘不完全對應，采用大寫以示區(qū)別。2.1

離散事件仿真的術語和概念事件調(diào)度eventscheduling事件發(fā)生是有時間順序的，事件調(diào)度就是按照事件發(fā)生的時刻（instant）順序，建立未來事件列表（futureeventlist，F(xiàn)EL），仿真時鐘（simulationclock）僅按照事件列表中的事件時刻推進，跳過那些沒有事件和活動（activity）發(fā)生的時間段（duration）依賴的是特定事件的統(tǒng)計分布在DES中，仿真過程是面向事件的2.1

離散事件仿真的術語和概念未來事件列表futureeventlist，F(xiàn)EL不同事件依賴不同的、獨立的統(tǒng)計分布和參數(shù)，需要按照各類事件的統(tǒng)計分布及其參數(shù)生成其未來事件，這些不同類型的事件混合在一起，并按照時間順序排序（chronologically），這樣所形成的一個包含各類事件的列表，稱為未來事件列表（FEL）FEL主要包含未來事件的發(fā)生時間（timeofoccurrence）、事件編號（ID）等，理論上說，即使基于相同的統(tǒng)計分布和參數(shù)，每次仿真所獲得的FEL列表應該是不同的，這是由于所用隨機數(shù)流（randomstream）是不同的。但是實際上，為便于模型分析和方案比較，可以設定采用相同的隨機數(shù)流，此時FEL是相同的。FEL并不是一次性生成全部事件，主要是因為：避免事件取消而造成的FEL事件刪除操作減少計算機內(nèi)存的消耗2.1

離散事件仿真的術語和概念例2.1銀行系統(tǒng)的事件調(diào)度和未來事件列表2.1

離散事件仿真的術語和概念內(nèi)生事件endogenousevent模型內(nèi)部活動所引起的狀態(tài)變化而產(chǎn)生的事件，源于系統(tǒng)內(nèi)部行為，不受系統(tǒng)外因素的影響例如，顧客離去事件、銀行柜員午休，等等外生事件exogenousevent該事件的產(chǎn)生是由系統(tǒng)外部因素引起的，系統(tǒng)只能承載事件的結果而不能影響事件的發(fā)生顧客到達事件、訂單到達事件，等等FEL包含內(nèi)生事件和外生事件2.1

離散事件仿真的術語和概念時間推進機制timeadvancedmechanism在DES中，仿真時鐘是面向事件的，即“踩著”事件發(fā)生的時刻跳躍前進，是一個離散的過程，而不是按照自然時間連續(xù)平滑推進，這樣可以提高仿真效率DES的時鐘推進機制有兩種模式：后續(xù)事件時間推進模式（Next-EventTimeAdvance，NETA），固定步長時間推進模式（Fixed-IncrementTimeAdvance，F(xiàn)ITA）2.2

列表處理列表處理listprocessing未來事件列表、隊列和實體列表，需要借助列表處理（listprocessing）方式進行管理列表是由記錄（record）構成的可變對象，列表中的記錄經(jīng)過排序，按順序鏈接在一起列表內(nèi)容可以修改，主要涉及記錄的添加、刪除和移動每個記錄代表一個實體（entity）或者一個事件預告（eventnotice）。由實體組成的列表稱為實體列表，由事件預告組成的列表就是FEL列表由排序的記錄組成，因此列表具有首記錄（toporhead）和尾記錄（bottomortail）為了實現(xiàn)遍歷的要求，通常使用指針，這個指針實現(xiàn)列表中記錄的定位2.2

列表處理順序存儲處理方式將所有記錄按照一定的順序?qū)懙綌?shù)組中，其物理順序就是邏輯順序，比如隊列中的顧客，就可以按照其到達時間的先后記錄在數(shù)組中，這樣顧客之間的前后位置就固定了，如果按照先到先服務的排隊規(guī)則（firstcomefirstserve，F(xiàn)CFS），則只需要從數(shù)組起始位置順序讀取記錄即可，效率較高按照FCFS原則排序2.2

列表處理索引存儲處理方式索引存儲方式，是在順序存儲的方式上，新增一個維度（屬性），用于存儲索引值，該屬性值記錄后序記錄（nextrecord）的邏輯位置。由此，新增記錄仍可以順序?qū)懭?，然后通過排隊規(guī)則建立索引，將索引值寫入對應屬性考慮VIP顧客優(yōu)先級的排序2.2

列表處理動態(tài)鏈接存儲方式動態(tài)鏈接存儲方式，是在順序存儲的基礎上，增加了兩個屬性，建立特定記錄與前后記錄的邏輯順序關系，我們稱之為前向指針（forwardpointer）和后向指針（backwardpointer）。前向指針與后向指針配合使用，可實現(xiàn)隊列的定位和雙向搜尋，這種方式具有最高的綜合性能和靈活性考慮VIP顧客優(yōu)先級的排序2.2

列表處理基于NETA機制的DES仿真軟件控制流圖（摘自AverillLAW2015）2.2

列表處理使用手工仿真—單服務臺系統(tǒng)（AverillLaw2015）2.2

列表處理使用手工仿真—單服務臺系統(tǒng)（AverillLaw2015）圖2.7單服務臺排隊系統(tǒng)顧客隊列狀態(tài)2.2

列表處理使用手工仿真—單服務臺系統(tǒng)（AverillLaw2015）圖2.8單服務臺排隊系統(tǒng)服務臺繁忙狀態(tài)2.2

列表處理使用手工仿真—單服務臺系統(tǒng)（AverillLaw2015）使用手工方式進行