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

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

Chapter2離散事件仿真原理2.1

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

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

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

離散事件仿真的術(shù)語和概念活動activity

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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