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

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

Chapter2離散事件仿真原理2.1

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

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

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

離散事件仿真的術(shù)語(yǔ)和概念活動(dòng)activity

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

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

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

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

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

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

離散事件仿真的術(shù)語(yǔ)和概念內(nèi)生事件endogenousevent模型內(nèi)部活動(dòng)所引起的狀態(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ù)語(yǔ)和概念時(shí)間推進(jìn)機(jī)制timeadvancedmechanism在DES中，仿真時(shí)鐘是面向事件的，即“踩著”事件發(fā)生的時(shí)刻跳躍前進(jìn)，是一個(gè)離散的過(guò)程，而不是按照自然時(shí)間連續(xù)平滑推進(jìn)，這樣可以提高仿真效率DES的時(shí)鐘推進(jìn)機(jī)制有兩種模式：后續(xù)事件時(shí)間推進(jìn)模式（Next-EventTimeAdvance，NETA），固定步長(zhǎng)時(shí)間推進(jìn)模式（Fixed-IncrementTimeAdvance，F(xiàn)ITA）2.2

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

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

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

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

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

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

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

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

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