離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法

物流系統(tǒng)仿真

——從理論到實(shí)踐第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.1離散事件系統(tǒng)仿真建模方法3.1.1離散事件仿真模型的組成與構(gòu)造3.1.2實(shí)體流圖法3.1.3活動周期圖法3.1.4實(shí)體流圖與活動周期圖的比較3.2離散事件系統(tǒng)仿真實(shí)現(xiàn)的三種算法3.2.1事件調(diào)度法3.2.2活動掃描法3.2.3進(jìn)程交互法3.3離散事件系統(tǒng)仿真模型設(shè)計(jì)3.3.1面向事件的仿真模型3.3.2面向活動的仿真模型3.3.3面向進(jìn)程的仿真模型3.4離散事件系統(tǒng)仿真的基本要素3.4.1基本要素3.4.2仿真鐘3.5排隊(duì)系統(tǒng)與庫存系統(tǒng)3.5.1排隊(duì)系統(tǒng)3.5.2庫存系統(tǒng)3.5.3排隊(duì)系統(tǒng)與庫存系統(tǒng)仿真比較第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.1離散事件系統(tǒng)仿真建模方法離散事件仿真模型的組成與構(gòu)造仿真模型系統(tǒng)狀態(tài)

仿真鐘事件列表統(tǒng)計(jì)計(jì)數(shù)器初始化程序時(shí)間推進(jìn)程序事件發(fā)生程序隨機(jī)觀測生成程序庫報(bào)告生成器主程序第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.1離散事件系統(tǒng)仿真建模方法離散事件仿真模型的組成與構(gòu)造變步長時(shí)間推進(jìn)機(jī)制下的控制邏輯第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.1離散事件系統(tǒng)仿真建模方法離散事件仿真模型的組成與構(gòu)造實(shí)體流圖法

實(shí)體流程圖方法采用與計(jì)算機(jī)程序流程圖相類似的圖示符號和原理，建立表示臨時(shí)實(shí)體產(chǎn)生、在系統(tǒng)中流動、接受永久實(shí)體“服務(wù)”以及消失等過程的流程圖。借助實(shí)體流程圖、可以表示事件、狀態(tài)變化及實(shí)體間相互作用的邏輯關(guān)系。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.1離散事件系統(tǒng)仿真建模方法離散事件仿真模型的組成與構(gòu)造實(shí)體流圖法建?？梢园匆幌滤悸愤M(jìn)行：

（1）辨識組成系統(tǒng)的實(shí)體及屬性。（2）分析各種實(shí)體的狀態(tài)和活動，及其相互間的影響。（3）考察有哪些事情導(dǎo)致了活動的開始或結(jié)束，或者可以作為活動開始或結(jié)束的標(biāo)志，以確定引起實(shí)體狀態(tài)變化的事件，并合并條件事件。（4）分析各種事件發(fā)生時(shí)，實(shí)體狀態(tài)的變化規(guī)律。（5）在一定的服務(wù)流程下，分析與隊(duì)列實(shí)體有關(guān)的特殊操作(如換隊(duì)等)。（6）通過以上分析，以臨時(shí)實(shí)體的流動為主線，用約定的圖示符號畫出被仿真系統(tǒng)的實(shí)體流程圖。（7）給出模型參數(shù)的取值、參變量的計(jì)算方法及屬性描述變量的取值方法。（8）給出隊(duì)列的排隊(duì)規(guī)則。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.1離散事件系統(tǒng)仿真建模方法離散事件仿真模型的組成與構(gòu)造活動周期圖法

活動周期圖以直觀的方式顯示了實(shí)體的狀態(tài)變化歷程和各實(shí)體之間的交互作用關(guān)系，便于理解和分析?；顒又芷趫D可以充分反映各類實(shí)體的行為模式，并將系統(tǒng)的狀態(tài)變化以“個(gè)體”狀態(tài)變化的集合方式表示出來，因此可以更好地表達(dá)眾多實(shí)體的并發(fā)活動和實(shí)體之間的協(xié)同。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.1離散事件系統(tǒng)仿真建模方法離散事件仿真模型的組成與構(gòu)造活動周期圖法活動周期圖建模過程如下：（1）辨識組成系統(tǒng)的實(shí)體及屬性.（2）辨識組成系統(tǒng)的永久實(shí)體和臨時(shí)實(shí)體，隊(duì)列不作為實(shí)體考慮。（3）分別畫出各實(shí)體的活動周期圖。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.1離散事件系統(tǒng)仿真建模方法離散事件仿真模型的組成與構(gòu)造實(shí)體流程圖與活動周期圖比較哪些不同點(diǎn)？第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.2離散事件系統(tǒng)仿真實(shí)現(xiàn)的三種算法事件調(diào)度法

事件調(diào)度法（EventScheduling）是面向事件的方法。仿真方法主要是研究系統(tǒng)狀態(tài)變化，有事件發(fā)生就會有狀態(tài)變化。事件調(diào)度法是通過定義事件，并按照時(shí)間順序處理所發(fā)生的一系列事件。由于事件都是預(yù)定的，狀態(tài)變化發(fā)生在明確的預(yù)定時(shí)刻，所以這種方法適合于活動持續(xù)時(shí)間比較確定的系統(tǒng)。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.2離散事件系統(tǒng)仿真實(shí)現(xiàn)的三種算法事件調(diào)度法事件調(diào)度法程序結(jié)構(gòu)第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.2離散事件系統(tǒng)仿真實(shí)現(xiàn)的三種算法事件調(diào)度法事件調(diào)度法的步驟是：（1）初始化：需要初始化的對象包括時(shí)間、事件表、系統(tǒng)初始時(shí)間和成分狀態(tài)。（2）將仿真鐘設(shè)置為系統(tǒng)初始事件的時(shí)間。（3）執(zhí)行事件子程序，修改事件表。（4）取出

的事件記錄，推進(jìn)仿真鐘

，修改事件表。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.2離散事件系統(tǒng)仿真實(shí)現(xiàn)的三種算法活動掃描法活動掃描法（ActivityScanning）是面向活動的?；顒娱_始和結(jié)束是系統(tǒng)狀態(tài)變化的標(biāo)志。而活動的開始與結(jié)束不僅取決于時(shí)間因素還取決于其他的因素?；顒訏呙璺ㄔ谟芰餍校钤绯霈F(xiàn)在1962年Buxton和Laski發(fā)布的CSL語言中。

活動掃描法建立在設(shè)立系統(tǒng)仿真鐘、成分仿真鐘和條件測試模塊的基礎(chǔ)之上。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.2離散事件系統(tǒng)仿真實(shí)現(xiàn)的三種算法活動掃描法三段掃描法的步驟是：（1）初始化①置仿真開始時(shí)間t0和結(jié)束時(shí)間tf；②置實(shí)體的初始狀態(tài)；③置初始B類活動例程及其調(diào)用時(shí)間ts；（2）仿真時(shí)鐘TIME=ts。（3）確定在當(dāng)前時(shí)鐘TIME下調(diào)用的B類活動例程

，i=1，2，···，n。（4）B類例程調(diào)用第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.2離散事件系統(tǒng)仿真實(shí)現(xiàn)的三種算法活動掃描法如果

，按優(yōu)先序執(zhí)行{ A1：執(zhí)行活動例程A1；

······An：執(zhí)行活動例程An。 Endcase}

否則，轉(zhuǎn)（7）。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.2離散事件系統(tǒng)仿真實(shí)現(xiàn)的三種算法活動掃描法（5）C類例程掃描 forj=1，m（優(yōu)先序從高到低）

執(zhí)行活動Aj；

若Aj的測試條件

，則 {退出當(dāng)前循環(huán)，重新開始掃描}； Endfor（6）推進(jìn)仿真時(shí)鐘TIME到下一最早B類例程調(diào)用時(shí)刻，轉(zhuǎn)（3）。（7）仿真結(jié)束。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.2離散事件系統(tǒng)仿真實(shí)現(xiàn)的三種算法進(jìn)程交互法

進(jìn)程交互法（ProcessInteraction）面向進(jìn)程。進(jìn)程交互法的基本模型單元是進(jìn)程。進(jìn)程與例程的概念有著本質(zhì)的區(qū)別，它是針對某類實(shí)體的生命周期而建立的，因此一個(gè)進(jìn)程中要處理實(shí)體流動中發(fā)生的所有事件(包括確定事件和條件事件)。進(jìn)程是由若干個(gè)有序的事件，以及由相鄰事件組成的若干活動組成的過程。一個(gè)成分進(jìn)入系統(tǒng)，完成各項(xiàng)活動的過程可以有一個(gè)進(jìn)程來描述。進(jìn)程交互法是事件調(diào)度法與活動掃描法的結(jié)合。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.2離散事件系統(tǒng)仿真實(shí)現(xiàn)的三種算法進(jìn)程交互法進(jìn)程交互法的處理過程如下：（1）推進(jìn)仿真時(shí)鐘TIME；（2）把滿足

的所有事件從FEL移至CEL中；（3）取出CEL中的每一個(gè)事件，判斷其所屬的進(jìn)程及在進(jìn)程中的位置；（4）判斷該事件發(fā)生的條件是否滿足；（5）如果條件允許該進(jìn)程盡可能連續(xù)推進(jìn)，直到進(jìn)程結(jié)束，該成分離開系統(tǒng)；（6）該進(jìn)程推進(jìn)過程中，遇到條件不滿足時(shí)，記錄下進(jìn)程的位置，并退出該進(jìn)程；（7）重復(fù)3~6，CEL中的事件處理完畢；（8）重復(fù)1~7，直到仿真結(jié)束。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.2離散事件系統(tǒng)仿真實(shí)現(xiàn)的三種算法進(jìn)程交互法第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.2離散事件系統(tǒng)仿真實(shí)現(xiàn)的三種算法三種算法的比較時(shí)間調(diào)度法活動掃描法進(jìn)程交互法系統(tǒng)描述主動成分可施加作用主動成分、被動成分均可施加作用主動成分、被動成分均可施加作用建模要點(diǎn)對事件建模，事件子程序?qū)顒咏?，條件子程序進(jìn)程分步，條件測試于執(zhí)行活動仿真鐘推進(jìn)系統(tǒng)仿真鐘系統(tǒng)仿真鐘，成分仿真鐘依據(jù)CEL，最早發(fā)生的事件時(shí)間執(zhí)行活動執(zhí)行控制選擇最早發(fā)生的時(shí)間記錄掃描全部活動，執(zhí)行可激活成分掃描CEL，執(zhí)行Da(S)=true記錄斷點(diǎn)第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.3離散事件系統(tǒng)仿真模型設(shè)計(jì)面向事件的仿真模型使用事件表后，面向事件仿真模型總控程序的算法結(jié)構(gòu)如下：（1）時(shí)間掃描①掃描事件表，確定下一事件發(fā)生時(shí)間；②推進(jìn)仿真時(shí)鐘至下一事件發(fā)生時(shí)間；③從事件表中產(chǎn)生當(dāng)前事件表CEL，CEL中包含了所有當(dāng)前發(fā)生事件的事件記錄。（2）事件執(zhí)行

依序安排CEL中的各個(gè)時(shí)間的發(fā)生，調(diào)用相應(yīng)的事件例程。某一時(shí)間一旦發(fā)生，將其事件記錄從當(dāng)前事件表中移出。

上述兩個(gè)步驟反復(fù)進(jìn)行，直到仿真結(jié)束。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.3離散事件系統(tǒng)仿真模型設(shè)計(jì)面向活動的仿真模型面向活動的仿真模型中，每一活動例程都由兩部分構(gòu)成：（1）探測頭：活動例程中所帶的測試條件（2）動作序列：活動例程所要完成的具體操作，只有在測試通過后才被執(zhí)行。時(shí)間元的取值方法有兩種：（1）絕對時(shí)間法。將時(shí)間元的時(shí)鐘值設(shè)定在相應(yīng)實(shí)體的確定事件發(fā)生時(shí)刻。（2）相對世間法。將時(shí)間元的時(shí)鐘值設(shè)定在相應(yīng)實(shí)體確定事件發(fā)生的時(shí)間間隔上。面向活動仿真模型總控程序的算法結(jié)構(gòu)包括：（1）時(shí)間掃描；（2）活動例程掃描。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.3離散事件系統(tǒng)仿真模型設(shè)計(jì)面向進(jìn)程的仿真模型面向進(jìn)程仿真模型的總控程序包含三個(gè)步驟：（1）將來事件表掃描：從FEL的實(shí)體記錄中檢出復(fù)活時(shí)間最小的實(shí)體，并將仿真時(shí)間推進(jìn)到該實(shí)體的復(fù)活時(shí)間。（2）移動記錄：將FEL中當(dāng)前時(shí)間復(fù)活的實(shí)體記錄移至CEL中。（3）當(dāng)前事件表掃描。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.4離散事件系統(tǒng)仿真的基本要素基本要素

系統(tǒng)由某些相互關(guān)聯(lián)或相互作用的要素組成，離散系統(tǒng)仿真模型是對真實(shí)系統(tǒng)關(guān)鍵要素的抽象和組合，抽象和組合的過程必須遵循一定的規(guī)律進(jìn)行。任何一個(gè)系統(tǒng)都可以分為個(gè)體、活動、資源與控制等要素。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.4離散事件系統(tǒng)仿真的基本要素基本要素事件、活動與進(jìn)程的關(guān)系進(jìn)程活動1活動2活動3事件1事件2事件n-1事件n·······第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.4離散事件系統(tǒng)仿真的基本要素仿真鐘

我們把一個(gè)仿真模型中用來記錄仿真當(dāng)前時(shí)刻的變量稱為仿真鐘。

仿真鐘是用于表示仿真時(shí)間變化的時(shí)間標(biāo)識。仿真鐘所記錄的時(shí)間，和我們運(yùn)行模型所耗費(fèi)的計(jì)算機(jī)運(yùn)行時(shí)間沒有必然的相關(guān)關(guān)系。第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.4離散事件系統(tǒng)仿真的基本要素仿真鐘

在仿真模型運(yùn)行過程中，仿真時(shí)鐘從0逐步增大到仿真結(jié)束時(shí)間，離散事件系統(tǒng)仿真的仿真時(shí)鐘推進(jìn)方法有兩種。（1）面向時(shí)間間隔的仿真時(shí)鐘推進(jìn)（2）面向事件的仿真時(shí)鐘推進(jìn)（仿真鐘）(a)面向時(shí)間間隔的仿真時(shí)鐘推進(jìn)(b)面向事件的仿真時(shí)鐘推進(jìn)第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.5排隊(duì)系統(tǒng)與庫存系統(tǒng)排隊(duì)系統(tǒng)

排隊(duì)系統(tǒng)式離散事件系統(tǒng)仿真應(yīng)用的一類經(jīng)典系統(tǒng)。排隊(duì)系統(tǒng)是指物、人及信息等流量元素在流動過程中，由于服務(wù)臺不足而不能及時(shí)為每個(gè)顧客服務(wù)，產(chǎn)生需要排隊(duì)等待服務(wù)（加工）的一類系統(tǒng)。排隊(duì)系統(tǒng)的基本參數(shù)顧客源服務(wù)臺服務(wù)臺服務(wù)臺服務(wù)臺隊(duì)列離去排隊(duì)系統(tǒng)的結(jié)構(gòu)第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.5排隊(duì)系統(tǒng)與庫存系統(tǒng)排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)的性能指標(biāo)平均等待時(shí)間服務(wù)臺利用率平均逗留時(shí)間平均隊(duì)長系統(tǒng)中平均顧客數(shù)忙期（閑期）第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.5排隊(duì)系統(tǒng)與庫存系統(tǒng)庫存系統(tǒng)

庫存系統(tǒng)也是物流系統(tǒng)中常見的一類系統(tǒng)。在日常的生產(chǎn)和經(jīng)營活動中，不論工廠對它生產(chǎn)所需的原材料、半成品、成品倉庫庫存，還是商場對所需的商品庫存，都需要進(jìn)行嚴(yán)格的控制和管理。庫存過多會造成資金積壓，過少會影響生產(chǎn)和銷售。庫存系統(tǒng)的特征①補(bǔ)給模式②需求模式③成本代價(jià)第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.5排隊(duì)系統(tǒng)與庫存系統(tǒng)庫存系統(tǒng)庫存系統(tǒng)常用的輸出參數(shù)①保管費(fèi)②訂貨費(fèi)③缺貨損失費(fèi)第三章離散事件仿真模型設(shè)計(jì)與實(shí)現(xiàn)算法3.5排隊(duì)系統(tǒng)與庫存系統(tǒng)排隊(duì)系統(tǒng)與庫存系統(tǒng)仿真比較

排隊(duì)系統(tǒng)與庫存系統(tǒng)在進(jìn)行仿真時(shí)，存在一定的差異，具體表現(xiàn)在要素、目標(biāo)、主要性能指標(biāo)、評價(jià)等幾個(gè)方面。排隊(duì)系統(tǒng)的要素是服務(wù)臺和顧客，而庫存系統(tǒng)主要處理的是訂貨和需求；排隊(duì)系統(tǒng)的目標(biāo)是提高服務(wù)臺、顧客效率，以最少的資源服務(wù)于最多的顧客，既提高客戶滿意度也能降低成本。庫存系統(tǒng)的目標(biāo)是保證供應(yīng)的前提下降低庫存，庫存雖然是生產(chǎn)銷售必不可少的，但卻占壓大量的資金，所以，要把庫存水平維持在一個(gè)較合理的位置。排隊(duì)系統(tǒng)的主要性能指標(biāo)是排隊(duì)隊(duì)長