3.1術語介紹系統(tǒng)——按照某些規(guī)律結合起來的，互相作 用、相互依存的所有元素的集合。實體——是對實際系統(tǒng)構成仿真模型所必須 的、不可略去的各種系統(tǒng)（元素）的抽象。（實體）屬性——能描述該實體狀態(tài)的一些量。它們可以是時間的函數(shù)，也可以不隨時 間變化。系統(tǒng)狀態(tài)——系統(tǒng)中全部實體的屬性在某時刻t 所取量值的集合S(t)定義為“系統(tǒng)狀態(tài)”。事件——當t在T上按某種序列{t1,t2,…}取值的過程中，系統(tǒng)狀態(tài)發(fā)生了變化，就定義系統(tǒng)發(fā)生了某一“事件”。并把此時的ti值定義為“事件時刻”?；顒印魏我鹣到y(tǒng)狀態(tài)改變的過程稱為“活動”。因此“活動”的結果使系統(tǒng)發(fā)生“事件”。而兩個相鄰“事件時刻”，可以看成是某一“活動”的過程。離散系統(tǒng)按照時間和事件關系的分類:時間離散——系統(tǒng)本身可能連續(xù)，但只在一些特定的時刻，即T={t1,t2,…}上被考察。通常為了方便，各時間間隔選定為整常數(shù)。S(t)S(t6)S(t1)0t1t2 t6t時間離散系統(tǒng)時間連續(xù)而有離散事件——這時，系統(tǒng)狀態(tài)的變化，即事件時刻是不連續(xù)的，跳躍式的。S(t)1（亮）

0t1t2t3 t4t5t6t人工控制的紅綠燈系統(tǒng)離散系統(tǒng)例子系統(tǒng)實體屬性事件急診室護士，病床，醫(yī)生，病人病情類型，護士和醫(yī)生的服務速度，病人的發(fā)病類型和發(fā)病率病人到達，離院，護士檢查結束，病人就診銀行出納員，計算機，顧客帳戶號，支票號，信用卡號，出納員的服務速度，顧客到達率，存/取/其它操作出納員服務，計算機查詢，顧客到達，離去不同實體可以分成兩類：靜態(tài)實體——這類實體在系統(tǒng)中往往處于被動地位。它們?yōu)閯討B(tài)實體提供服務。因而起設備作用。描述這類實體的最常見的屬性有：忙、閑、數(shù)量、地點、速度、設備號、服務時間等。動態(tài)實體——這類實體在系統(tǒng)中總是要求得到某些設備的服務。在系統(tǒng)的運行中，它們不斷得以某種到達率“生成”。當從某一設備得到服務后，又流向其他設備以求服務。系統(tǒng)環(huán)境——能對系統(tǒng)產(chǎn)生影響的，屬于系統(tǒng) 以外的元素集合。仿真目的——指仿真者希望通過仿真所獲取系 統(tǒng)的哪些性能，信息。仿真模型——由系統(tǒng)數(shù)學模型根據(jù)仿真工具（語言）的特點，進行必要的結構變換，建立的合適算法。 對同一系統(tǒng)，仿真的目的不同，所建的模型也將不同。3.2排隊系統(tǒng)

在日常生活中，人們常常會見到各種各樣的服務系統(tǒng)。例如：到食堂去買飯，炊事員和買飯人員構成一個服務系統(tǒng)；在公共汽車服務系統(tǒng)，由汽車、乘客和車站組成。服務系統(tǒng)的主要特征是出現(xiàn)排隊。因此也稱其為“排隊系統(tǒng)”。用于研究排隊系統(tǒng)的理論基礎是“排隊論”

排隊論最早由A.K.Erlang

于1918年提出,在管理通訊和各類服務系統(tǒng)中有著廣泛的應用,但是采用排隊論方法來為DEDS建模服務卻是近二十年來的事。以排隊論為基礎的網(wǎng)絡模型是離散事件系統(tǒng)仿真中最常用的模型。隨機排隊系統(tǒng)的三個組成部分：到達模式——指含個類型的動態(tài)實體按怎樣的規(guī)律到達。服務機構——指同一時刻有多少服務設備可以接納動態(tài)實體；對它們的服務需要多少時間。排隊規(guī)則——到達的動態(tài)實體將按怎樣的次序接受服務。離散仿真要解決的基本問題

如何通過已知的到達模式和服務時間的概率分布，研究排隊系統(tǒng)的隊列長度和服務設備“忙”或“閑”的程度，就是離散仿真要解決的基本問題。

幾種常見的排隊系統(tǒng)的結構：動態(tài)實體服務設備動態(tài)實體到達 離去 一線一服務設備排隊系統(tǒng)結構動態(tài)實體服務設備1服務設備n動態(tài)實體到達 離去 ： ：

一線并聯(lián)服務設備排隊系統(tǒng)結構3.3到達模式確定型到達模式——顧客有規(guī)則地按照一定的間隔時間到達。泊松到達模式——滿足4個條件平穩(wěn)性：在[a,a+t]時間內(nèi)有k個顧客到來的概率與a無關，只與t,k有關。記此概率為：Vk(t)——在t時間間隔內(nèi)到達k個顧客的概率。(P(k,λt))無后效性：不相交區(qū)間內(nèi)到達的顧客數(shù)是相互獨立的。[t1,t2]到達數(shù)與[t0,t1]的到達數(shù)無關。普通性：令ψ(t)表示在長度為t的區(qū)間內(nèi)至少到達兩個顧客的概率，則ψ(t)=0當t->0；有限性：在任意有限時間區(qū)間內(nèi)到達有限個顧客的概率之和為1。

其中λ>0為常數(shù)。令第i個顧客到達的時刻為τi(I=1,2,…)，τ1=0，且ti=τi-τi-1（i=1,2,…），則顧客相繼到達的間隔t是相互獨立相同分布的。其到達間隔的分布為指數(shù)分布。指數(shù)分布：

泊松分布到達模式實際上是指：到達間隔時間為指數(shù)分布的到達模式。平均到達間隔時間Ta——在考慮模型的總時間 T中，共到達了n個“顧客”的情況下的比值 T/n。平均到達率λ——單位時間內(nèi)到達的“顧客” 數(shù)。λ=1/Ta。到達間隔的分布函數(shù)A0(t)——到達間隔時間大 于t的概率。

A0(t)1F(t)

A0(t)0 t3.2.2服務時間定長分布——這是最簡單的情況。對每個動態(tài)實體的服務時間都是常數(shù)a，其分布函數(shù)為：指數(shù)分布——當服務時間完全是隨機的情況，可以用指數(shù)分布來表示。其分布函數(shù)：正態(tài)分布——在服務時間近似于常數(shù)的情況下，因多種隨機因素的影響，使服務時間圍繞這些常數(shù)值隨機波動的情況。其中：σ>0，a——均值。F(x)記為：N(a,σ2)。當a=0，σ=1時，N(0,1)稱為“標準正態(tài)分布”。3.4排隊規(guī)則和隊列的度量排隊規(guī)則——動態(tài)實體應依一定的次序和規(guī)則接受服務。損失制——動態(tài)實體到達時，如所有的服務設備均被占，則該實體就自動消失，永不再來。等待制——動態(tài)實體到達時，如所有的服務設備均被占，則它們就排成隊伍，等待服務。服務次序可以采用下列各種規(guī)則：先到先服務先到后服務隨機服務優(yōu)先權服務排隊規(guī)則

在優(yōu)先權服務時，必須考慮當一個比現(xiàn)在正接受服務的實體具有更高優(yōu)先權級別的動態(tài)實體到達之后，系統(tǒng)將會做出怎樣的處理：優(yōu)先權僅決定動態(tài)實體的排隊先后。立即停止當前服務，為新到的高優(yōu)先權的實體服務。

排隊規(guī)則3.混合制——隊長有限制等待時間有限制逗留時間隊列的度量

設Ta為動態(tài)實體的平均到達間隔時間，λ=1/Ta為平均到達速度

Ts是設備的平均服務時間，μ=1/Ts是平均服務速度。定義：業(yè)務量強度——在已知平均到達速度λ和平均 服務速度μ，業(yè)務量強度：

u=λ/μ=Ts/Ta設備利用率——得到服務的動態(tài)實體的到達速 率λ’與服務速度之比：

ρ=λ’/μ對隊列進行度量通常考察兩個量：隊列長度排隊時間3.5設備利用率和服務質(zhì)量

對系統(tǒng)做假設：動態(tài)實體數(shù)量是無限的，其到達速率不受排隊長度的影響，并且所到達的實體不會中途離去；到達模式為泊松分布，服務設備利用率ρ<1時，服務系統(tǒng)的動態(tài)實體平均數(shù)(L)為:服務時間為常數(shù)分布

L=ρ(2-ρ)/(2(1-ρ))服務時間為指數(shù)分布

L=ρ/(1-ρ)隊列平均長度：

Lw=1-ρ通過改變ρ來控制系統(tǒng)性能的方法：改變動態(tài)實體的到達速度改變服務設備的服務速度改變服務設備的數(shù)量系統(tǒng)的服務質(zhì)量的衡量標準：能夠立即得到服務的動態(tài)實體占到達實體總數(shù)的百分比。等待時間小于等于一個給定值T的動態(tài)實體占到達實體總數(shù)的百分比。用Pw(t)表示等待時間大于一時間長度(t)的概率。對泊松到達，指數(shù)服務的單服務設備系統(tǒng)有：

其中：t——指定的時間長度，ρ——設備利用率，μ平均服務速度。例：對某個系統(tǒng)，平均服務時間為10秒，規(guī)定服務質(zhì)量：在4個請求中至少有一個請求應立即給予響應而且等待時間超過30秒的請求不應超過請求總數(shù)的20%。分析：對第一個要求

Pw(0)=0.75=>ρ≤0.75

對第二個要求 如平均服務時間為10秒=>μ=1/10=0.1

Pw(t)

1.00.8

ρ=0.80.6

ρ=0.60.4

ρ=0.40.2

ρ=0.2

0123456μt

t=30秒=>μt=3。查曲線得Pw(3)≤0.2=>ρ≤0.6

如果用更小的利用率ρ，則會得到更低的概率。所以要求ρ≤0.6。綜合兩個要求，可取ρ≤0.6。為了使ρ=0.6就要求顧客的平均到達時間Ta=Ts/ρ=10/0.6=16.7（秒）。同樣：對給定了到達間隔時間Ta時，也可求得Ts以達到滿意的服務質(zhì)量。

3.6排隊系統(tǒng)建模（1）以排隊論方法為基礎的仿真模型設計技術主要適用于帶時標的隨機DEDS系統(tǒng)。 對排隊系統(tǒng)來說，它只有兩個基本的操作：“入隊”和“離隊”操作。排隊模型的確切形式取決于服務設備的數(shù)量和排隊線的數(shù)量。開始對到達的動態(tài)實體做相關記錄服務設備忙將實體掛在排隊線上排隊線長度加1設置服務設備為“忙”狀態(tài)確定（此次）服務時間調(diào)度服務完成事件結束

Y N

（時間）

入隊操作

設置服務設備為“空”狀態(tài)排隊線“空”按排隊規(guī)則從隊列中選出一個實體記錄，讓設備為它服務；累計等待時間確定（此次）服務時間；隊列統(tǒng)計記錄，隊長度減1調(diào)度服務完成事件結束開始

Y N

離隊操作(2)Petri網(wǎng)絡模型

Petri網(wǎng)模型最早在1962年

CarlAdamPetri的博士論文中提出來，主要特性是具有較強的對并行、不確定性、異步和分布的描述能力和分析能力。

Petri網(wǎng)是一個模型化的工具，它是設想來用于模型化某一類問題：即有同時平行事件的離散事件的系統(tǒng)的問題。Petri網(wǎng)模型化了系統(tǒng)，特別是系統(tǒng)的兩個方面（事件和條件）及它們之間的關系。(3)有限狀態(tài)自動機模型

離散事件系統(tǒng)自動機及形式語言理論最早是由P.J.Ramadge

和W.M.Wonbarn

等人八十年代中期提出的,現(xiàn)已成為DEDS研究的重要方法之一。 有限狀態(tài)自動機模型描述方法主要適用于邏輯定性模型和無時標確定性模型的建模。建立有限狀態(tài)自動機模型的關鍵是,基于適當?shù)姆抡娌呗赃x用相應狀態(tài)集合,建立正確的轉(zhuǎn)移關系函數(shù)和輸出關系函數(shù)。4.離散事件仿真策略與結構模型

仿真過程的運行調(diào)度控制（特別是在用高級語言編程時），是通過所謂的“仿真策略”來實現(xiàn)的。 例：對一個含有一些出納員，一些顧客和對應每個出納員的銀行（多）排隊線的系統(tǒng)。 設：出納員數(shù)量 5服務速度N(3,1)

顧客 到達 [0.2,0.8]

統(tǒng)計 隊列長度（平均，最大，最小，方差） 出納員利用率（平均，最大，最小，方差） 顧客在銀行的時間（平均，最大，最小，方差）

可以畫出仿真程序的結構框圖如下：預定仿真時間TIME=0預定第一個顧客到達時間開始TIME<仿真預定時間有顧客到達選擇排隊線將顧客插入排隊線*調(diào)度下一個顧客的到達時間輸出統(tǒng)計結果結束在這一段時間內(nèi)有事務處理完（出納空）顧客離去選擇排隊線上的顧客給予服務*調(diào)度為該顧客服務的完成時間TIME=TIME+1N

YN 到達事件

Y

N

Y

這是種“面向時間”的時鐘(TIME)處理。通過多次運行程序（試驗）統(tǒng)計得到結果。程序每做一次循環(huán)，就增加一個時間單位。此時不論系統(tǒng)是否有時間發(fā)生，程序總是要查詢系統(tǒng)狀態(tài)，如發(fā)現(xiàn)沒有時間發(fā)生就跳過該事件的處理程序。 這種方法的特點是：能和連續(xù)模型（進行時間離散）混合仿真。當事件子程序均能在一個時間單位內(nèi)處理完成，則TIME的+1操作可以在機器硬件時鐘的控制下執(zhí)行，即仿真程序可以實時的（與機器時鐘同步）運行。 缺點是：計算機做了很多不必要的空操作。因為在兩個相鄰事件時刻之間，系統(tǒng)沒有活動需要計算機處理。目前很少使用此方法。 人們在研究了各種（離散）仿真調(diào)度方法的基礎上，總結出三種通用的仿真策略，即：事件預定，活動掃描和進程互配。4.1面向事件結構模型

面向事件結構模型是按事件獨立預定策略組建成的。對上述的銀行系統(tǒng)為例，其仿真程序結構框圖：

TIME<仿真時間開始調(diào)度第一次到達事件從事件表中選出最先要執(zhí)行的事件作為當前事件將時間TIME撥到當前事件的發(fā)生時刻按當前事件類型分支選擇排隊線將顧客插入該排隊線調(diào)度下一次到達事件的產(chǎn)生時刻顧客離去選排隊線上某顧客接受服務或“空閑”出納員調(diào)度本次服務完成（時間）輸出統(tǒng)計結果結束

產(chǎn)生第一個顧客到達，填入事件表

N Y

到達事件 …… 事務完成事件表結構：序號事件發(fā)生時間事件類型實體號:i100到達10i+1111接受服務8:k’201離去8k210到達11k+1面向事件結構模型

在這里，仿真時鐘TIME是根據(jù)當前事件的發(fā)生時刻進行離散變化的。 “事件預定策略”強調(diào)：預定全部事件。事件將按顯式調(diào)度?！笆录δ堋庇墒录绦?qū)崿F(xiàn)。事件的調(diào)度是通過把事件按“事件標志”放在事件表中的方法來達到的。4.2活動掃描結構模型

當事件的發(fā)生不僅與時間有關，而且與其它條件也有關，即：只有在滿足某些條件時發(fā)生。在這種情況下，由于活動持續(xù)時間的不確定性，無法預定活動的開始或終止時間。所以不易采用面向事件的結構模型。而活動掃描結構模型就是針對具有這種特點的系統(tǒng)的?；顒訏呙杞Y構模型

活動掃描結構要求對事件隱式調(diào)度。在這里，狀態(tài)的轉(zhuǎn)換被表示成一組稱之為“活動”的函數(shù)。 每次轉(zhuǎn)換，由一個活動條件和一個動作組成。在每個（由預定事件生成時刻確定的）時間上，按某種（總體狀態(tài)的）順序掃描這些條件，如果出現(xiàn)一個條件是真，則立即執(zhí)行與它聯(lián)系的“動作”段；繼續(xù)掃描，測試和執(zhí)行，直到滿足條件的活動都進行完。這是再按下一預定事件生成時刻向前推進模型的時鐘?；顒訏呙杞Y構模型

按某種（總體狀態(tài)）順序掃描這些任務（包括檢測小于當前時間應發(fā)生，但因條件未滿足而延時發(fā)生的“以前”事件）。 在使用活動掃描策略時，需要借助事件預定策略進行時間（鐘）管理。 事件預定策略不但要按預定事件的生成時刻向前推進仿真時鐘，而且還按預定生成時刻激發(fā)事件（條件將在處理中測試）

活動掃描表結構：序號事件發(fā)生時間事件類型實體號條件函數(shù):i100到達10Ti+1111接受服務8F:k’201離去8Fk210到達11Tk+14.3進程互配模型結構

進程是一系列互相排斥的活動互配（在一個進程中，一次只能激活一個活動，進程中的活動間的連接關系：一個活動的結束，可以使該進程中的另一個活動的開始。不同的進程間會有重疊。（一個進程的活動需要取決于另一個進程中的活動的結束）。進程互配方法強調(diào)了這些進程之間的相互關系。進程到達等待離去 事件：

顧客4 排隊 服務 離去 等待 顧客3 排隊 服務 到達 顧客2 服務 活動：

排隊顧客1

服務 空閑 出納2 空閑

空閑 忙 空閑 出納1

E1E2E3E4E5E7E9E10時間（t）