黃鎮(zhèn)謹(jǐn)，陳 波，歐陽浩

（ 廣西工學(xué)院 計(jì)算機(jī)工程系，柳州 545006）

0 引言

傳統(tǒng)的離散事件仿真方法要求在仿真過程中獲得系統(tǒng)的精確信息，如系統(tǒng)中各隨機(jī)變量的概率分布和參數(shù)等。實(shí)際中這些信息往往難以精確的獲得。經(jīng)典的隨機(jī)服務(wù)系統(tǒng)中一般假設(shè)顧客到達(dá)時間及服務(wù)時間服從特定的分布函數(shù)。實(shí)際應(yīng)用中要獲得參數(shù)的分布特性，需要對系統(tǒng)參數(shù)進(jìn)行大量的數(shù)據(jù)采樣并采用擬合的方式獲得其分布規(guī)律，這不僅費(fèi)時費(fèi)力，而且很多時候得到的結(jié)果與理論上的分布函數(shù)具有比較大的偏差。利用這些具有一定偏差的分布函數(shù)對系統(tǒng)進(jìn)行分析雖然能夠帶來解析處理的方便，但在一定程度上犧牲了系統(tǒng)的真實(shí)性和實(shí)際應(yīng)用價(jià)值。因此，需要另外的手段處理這些不精確的信息。采用模糊數(shù)描述信息的不精確性是一種可行辦法。

離散事件仿真的核心是對事件與其仿真時鐘的處理[1]。事件以事件列表的形式存在，時間的推進(jìn)與其狀態(tài)的更新取決于下一個事件的發(fā)生時間。事件列表的更新隨著系統(tǒng)狀態(tài)的演化不斷進(jìn)行。當(dāng)前仿真時間由仿真時鐘維護(hù)，在每一個事件發(fā)生時更新系統(tǒng)仿真時鐘。引入模糊數(shù)后，事件的發(fā)生與其仿真時鐘的更新時間不再是精確的數(shù)值，而是一個區(qū)間值，區(qū)間中的每一個數(shù)值具有相應(yīng)的隸屬度。參數(shù)模糊化后的離散事件仿真中，事件的選擇與其仿真時鐘的更新比基于概率分布仿真復(fù)雜，多個模糊數(shù)之間的排序結(jié)果可能并不唯一。因此一個好的模糊仿真模型應(yīng)該具有以下兩個屬性[2]：首先模型應(yīng)該能夠再現(xiàn)每一種可能的狀態(tài)演化，其次，模型不能引入實(shí)際運(yùn)行中不可達(dá)狀態(tài)。

離散事件仿真中引入模糊數(shù)據(jù)后由于事件的發(fā)生時間具有模糊的值，因此需要對后續(xù)的可選擇事件集進(jìn)行排序，然后從中選擇符合要求的事件作為下一個將要發(fā)生的事件。雖然把模糊數(shù)學(xué)引入離散事件系統(tǒng)仿真的概念并不難想到，但是由于處理模糊信息的方法和過程與處理精確信息有較大的不同，因此這個領(lǐng)域中提出的方法還比較有限。文獻(xiàn)[3]提出了基于積分值的模糊仿真方法。在文獻(xiàn)[4]中，一種基于預(yù)期存在度量(expected existence measure EEM)的模糊排序方法被應(yīng)用于離散事件仿真中，在此基礎(chǔ)上，Grieco等提出了一種對模糊事件進(jìn)行切割以調(diào)整該問題的方法[5]，文獻(xiàn)[6]利用模糊數(shù)與上下確界的距離來確定其大小。在這四種方法中，前三種方法都不能同時滿足離散事件仿真的兩個屬性，最后一種方法其待定參數(shù)的確定比較復(fù)雜。文獻(xiàn)[7]從可能性空間及區(qū)間分析的角度探討具有模糊輸入?yún)?shù)的離散事件系統(tǒng)仿真問題，該方法模糊化的對象是分布函數(shù)中的參數(shù)而不是輸入?yún)?shù)本身，因此仍然面臨需要大量的數(shù)據(jù)采樣并擬合分布函數(shù)的問題。

針對以上問題，在文獻(xiàn)[4]的基礎(chǔ)上，本文提出一種新的方法，根據(jù)前一個事件結(jié)束時的當(dāng)前時刻與其另一個待定參數(shù)確定下一個將要發(fā)生的事件 (two independent parameters TIP，以下簡稱TIP法)。該方法避免了概率方法的數(shù)據(jù)采集和擬合分布函數(shù)問題，通過模糊數(shù)的預(yù)選擇降低了模糊數(shù)排序的復(fù)雜度，與現(xiàn)有模糊離散事件仿真方法相比，在不引入不可達(dá)狀態(tài)情況下能再現(xiàn)系統(tǒng)演化的所有狀態(tài)。

1 積分值法和EEM法

基于積分值和EEM的方法都是將具有一定區(qū)間取值的模糊集或模糊數(shù)的比較轉(zhuǎn)換成確切值后再進(jìn)行比較，采用一個待定參數(shù)確定模糊數(shù)的大小順序。由于本文給出的方法中與這兩者有關(guān)，下面簡要介紹這兩種方法。設(shè)事件E發(fā)生時間為符合隸屬度函數(shù)μ(x)的模糊集F(x),令gL(x), gR(x)為 μL(x), uR(x)的反函數(shù)，積分值定義如下[3]：

令 EEM(t)=r，給定 r∈ [0,1]，t=EEM-1(r)，根據(jù)t值的大小對模糊集F(x)進(jìn)行排序。圖1給出了兩個具有重疊關(guān)系的梯形模糊集F1(a1,b1,c1,d1)、F2(a2,b2,c2,d2)的積分值和EEM。

在圖1中，模糊集F1有可能大于或小于模糊集F2，采用前述兩種方法進(jìn)行排序時，對于r∈[0,1],都有F1＜F2，因此基于積分值和EEM的方法不能再現(xiàn)系統(tǒng)的每一種可能的演化狀態(tài)。令b=c，則可以采用同樣的方式處理三角形模糊數(shù)。

圖1 積分值法和EEM法

2 TIP方法

2.1 模糊數(shù)預(yù)選擇

事件的處理和仿真時鐘的更新是離散事件仿真中兩個關(guān)鍵的問題，實(shí)際上，對仿真時鐘的更新是與事件的處理相關(guān)的。例如，令模糊數(shù)Tnow表示當(dāng)前的仿真時刻，事件E為下一個將要發(fā)生的事件，與E相對應(yīng)的活動延遲時間為模糊數(shù)TE，處理完前一個事件后，仿真時鐘被推進(jìn)到Tnext=TnowTE處。因此如何選擇下一個將要發(fā)生的事件是離散系統(tǒng)仿真中的核心。模糊仿真中，時間標(biāo)記不再是確定的，而是具有一定區(qū)間的模糊數(shù)。通過對模糊數(shù)進(jìn)行排序確定大小從而選取下一個要發(fā)生的事件。

在排序過程中，并非所有的后續(xù)事件都要參與排序。因此需要從事件列表E中選取用于排序的模糊數(shù)集Fcomp。設(shè)事件E1,E2…Ei對應(yīng)的模糊集為F1,F2…Fi，由模糊集的定義知，若sup(Fi)

圖2 選取可比模糊數(shù)集合

令當(dāng)前事件Ek對應(yīng)的模糊集為Fk，t=sup(Fk)，從事件列表中選取Fi={Fj│EEMFj(t)＜1},令c=min(sup(Fi))， 則當(dāng)inf(Fi)＜c 時有Fi∈Fcomp，其中Fcomp為將要進(jìn)行排序的模糊數(shù)集合。如圖2中，由于inf(F5)＞sup(F1),因此F5Fcomp，F(xiàn)comp=(F1,F2, F3, F4)。

2.2 模糊事件選取

當(dāng)前事件結(jié)束時，需要從模糊數(shù)集Fcomp中選擇下一個將要發(fā)生的事件。本文采用兩個獨(dú)立的參數(shù)來確定下一個要發(fā)生的事件，第一個為前一個事件的結(jié)束時刻Tnow，Tnow為一模糊數(shù)，其確定下一個事件將要發(fā)生的時間范圍。設(shè)F1, F2, …Fk∈Fcomp，ai=inf(Fi),ci=sup(Fi),由上節(jié)中對Fcomp的選取可知，Tnow＜min(sup(Fi))，因此對下一個事件的選取取決于當(dāng)前時刻Tnow所處的位置。在Fcomp中，有inf(F1)＜ inf(F2)＜…＜ inf(Fk)，令I(lǐng)i=[inf(Fi)，inf(Fi+1)](1 ≤ i＜ k)，Ik=[inf(Fk)，sup(F1)]， 如圖3所示，Ii(1≤i≤k)將[inf(F1)，min(sup(Fi))]之間分隔成k個區(qū)間。出于方便，設(shè)Ii=[ai，ci]，mamum=min(sup(Fi))，則：

1）當(dāng)Tnow＜inf(F1)時，令S0=0

2）當(dāng)Tnow∈Ii時，令 S0=0

設(shè)當(dāng)前時刻為Tnow，有Tnow＜inf(F1)或Tnow∈Ii，任取第二個參數(shù)λ∈[0,1]，在區(qū)域Ii若λ∈[Sj-1, Sj]，則取Ei作為下一個發(fā)生的事件。如圖3中，Tnow∈I3，F(xiàn)3為選取的模糊數(shù)，其對應(yīng)的事件E3將為第一個要發(fā)生的事件。

圖3 模糊數(shù)排序示例

2.3 隸屬度函數(shù)更新

仿真開始時由用戶指定好參數(shù)λ的值，該值在仿真過程中保持不變，由此再現(xiàn)系統(tǒng)的一個演化過程。排序過程中，一旦確定了下一個要仿真的事件，則需要對模糊數(shù)集Fcomp中各個模糊數(shù)的支集進(jìn)行調(diào)整。如圖4 ，若指定λ排序后有F1＜F2，則仿真時鐘將更新到F1，由于仿真時鐘是一維的遞增變量，因此模糊集F1的上界應(yīng)該小于模糊集F2的上界。

設(shè)F1，F(xiàn)2，…Fk∈Fcomp，相應(yīng)的隸屬度函數(shù)分別為 μ1(x), μ2(x),…μk(x)，F(xiàn)p=min(F1, F2, …Fk)則 Fp為經(jīng)排序后選定的下一個將要發(fā)生事件對應(yīng)的模糊數(shù)。設(shè) α=inf(x │ μp(x)＞0)，β=min(supSj│ j=1,2,…,k)，則模糊集Fi按如下公式調(diào)整其隸屬度函數(shù)：

其中

通過對仿真事件發(fā)生時間相應(yīng)隸屬度函數(shù)的調(diào)整，避免系統(tǒng)在仿真演化的過程中陷入一些不可能再現(xiàn)的狀態(tài)中。

圖4 模糊區(qū)間更新

3 實(shí)驗(yàn)及結(jié)果分析

下面將本文所述方法應(yīng)用于一個生產(chǎn)加工系統(tǒng)[8]，并將其結(jié)果與基于概率分布的方法和其他文獻(xiàn)中基于模糊仿真的方法所獲結(jié)果進(jìn)行比較分析。設(shè)有生產(chǎn)系統(tǒng)S，系統(tǒng)中只有一臺機(jī)器且只加工一類零件，加工時間及工件進(jìn)入系統(tǒng)的時間為非確定的值，選取工件加工完成時間作為衡量系統(tǒng)性能的指標(biāo)。測試數(shù)據(jù)如表1所示。

表1 工件到達(dá)時間與加工時間

仿真過程中，基于概率分布的方法采用與三角形模糊數(shù)相對應(yīng)的三角形分布來處理不確定性。其中，第i+1個工件加工完成時間的概率分布等于前一個工件加工完成時間的概率分布與加工時間概率分布的卷積，因此利用卷積理論，可以由第一個工件逐步推導(dǎo)出最后一個工件加工完成時間的概率分布。以加工完成時間為衡量指標(biāo)，各種方法下加工4個工件的仿真結(jié)果如表2所示。

由表2可知，理論上第4個工件的加工完成時間處于區(qū)間[15.9, 21.1]中，基于積分值和EEM的模糊排序方法工件加工完成時間均為三角形模糊數(shù)[12.9, 17, 21.1]，由于這兩種方法最小值小于15.9，因此仿真的結(jié)果有可能處于理論上不可達(dá)的狀態(tài)中。這違反了前文所講的模糊仿真應(yīng)該滿足的第二個屬性。雖然分割法和本文提出的方法仿真結(jié)果符合理論值，對于分割法，當(dāng)參數(shù)γ確定后，則對應(yīng)的下一個要發(fā)生的事件是唯一的，如圖5所示，當(dāng)γ=γ0時，取F2。實(shí)際上，對于任意 的 γ， 使t=EEM-1M(γ)∈ [a2, c1]， 有 F1＜F2或F1＞F2。因此基于分割法的模糊仿真在某些情形下不能演化系統(tǒng)中的所有可能出現(xiàn)的狀態(tài)，而本文的方法可以再現(xiàn)系統(tǒng)中的所有狀態(tài)。

表2 仿真結(jié)果

圖5 分割法示例

基于模糊排序的仿真方法描述系統(tǒng)事件的演化時，系統(tǒng)輸出參數(shù)是非確定性的模糊數(shù)。而對于基于概率分布的仿真方法來說，輸出結(jié)果表示成以一定概率表示的統(tǒng)計(jì)分布。為了分析和比較這兩種方法的輸出結(jié)果，對概率分布進(jìn)行正規(guī)化處理，將每一個輸出結(jié)果的概率分布值除以最大的輸出概率值。經(jīng)過正規(guī)化處理后的概率分布與其模糊仿真結(jié)果如圖6所示。

圖6 工件加工完成時間

考慮到每次仿真結(jié)果的隨機(jī)性，采用概率方法時需要對系統(tǒng)進(jìn)行多次的仿真，仿真的次數(shù)將會影響輸出參數(shù)結(jié)果，而且對于該方法來說，采用不同的分布函數(shù)和參數(shù)表達(dá)系統(tǒng)的不確定性，其輸出結(jié)果也會存在一定的差別。由圖6可知，基于概率分布仿真方法的輸出結(jié)果包含于基于模糊數(shù)描述的輸出結(jié)果中。因此，基于模糊數(shù)的仿真方法比基于概率分布的方法能夠更好的表達(dá)系統(tǒng)演化過程的不確定性。

4 結(jié)論

具有模糊參數(shù)的仿真可以表達(dá)系統(tǒng)的不確定性。針對離散事件系統(tǒng)中事件發(fā)生時間的不確定性，本文提出了一種新的模糊離散事件仿真方法，

該方法根據(jù)前一個事件結(jié)束時的當(dāng)前時刻與其另一個待定參數(shù)確定下一個將要發(fā)生的事件。實(shí)驗(yàn)結(jié)果表明，與過去文獻(xiàn)所提的方法相比，該方法能夠滿足離散事件仿真中的兩個屬性，同時，相對于基于概率分布的仿真方法，基于模糊的仿真方法能夠更好的表達(dá)系統(tǒng)的不確定性。后續(xù)的工作主要研究不同的模糊數(shù)表示下仿真結(jié)果的關(guān)系與其分析不同分布函數(shù)和參數(shù)下基于概率分布的仿真方法和采用不同的參數(shù)下基于模糊集的仿真方法之間的定量關(guān)系。

[1] FISHMAN G S. Principles of Discrete Event Simulation[M].New York, John Wiley & Sons, 1978.

[2] RIYADHR M, ABDULAZIZ A, HAKIM K. New fuzzy ranking algorithm for discrete event simulation[C]. // 12th IEEE International Conference on Electronics, Circuits and Systems, Gammarth, Tunisia, ICECS 2005.

[3] LIOU T, WANG MAO JIUN. Ranking fuzzy numbers with integral value[J]. Fuzzy Sets and Systems, 1992,50(3): 247-252.

[4] NGUYEN Q, LE T. A Fuzzy Discrete-Event Simulation Model[C].// Australia-Pacific Forum on Intelligent Processing and Manufacturing of Materials, Golds Coast, Queenland,Australia, July. 1997: 125-134.

[5] ANGLANI A, GRIECO A, NUCCI F, et al. Representation and use of uncertainty in discrete event simulation models[C].[S.1.]: [S.n.], 1998: 717-731.

[6] ZHANG Hong, TAM C.M, LI Heng. Modeling uncertain activity duration by fuzzy number and discrete-event simulation[J]. European Journal of Operational Research,2005, 164(4): 715-729.

[7] 魏世豪. 具有模糊參數(shù)的離散事件系統(tǒng)仿真與輸出分析研究[D]. 北京: 清華大學(xué), 2008.

[8] GRIECO A, NUCCI F, ANGLANI A. Representation of fuzzy time variable in discrete event simulation[J]. Integrated Computer-aided Engineering, 2003, 10(4): 305-318.