一種具有模糊時間參數的離散事件仿真方法

黃鎮謹，陳 波，歐陽浩

（ 廣西工學院 計算機工程系，柳州 545006）

0 引言

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

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

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

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

1 積分值法和EEM法

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

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

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

圖1 積分值法和EEM法

2 TIP方法

2.1 模糊數預選擇

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

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

圖2 選取可比模糊數集合

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

2.2 模糊事件選取

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

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

2）當Tnow∈Ii時，令 S0=0

設當前時刻為Tnow，有Tnow＜inf(F1)或Tnow∈Ii，任取第二個參數λ∈[0,1]，在區域Ii若λ∈[Sj-1, Sj]，則取Ei作為下一個發生的事件。如圖3中，Tnow∈I3，F3為選取的模糊數，其對應的事件E3將為第一個要發生的事件。

圖3 模糊數排序示例

2.3 隸屬度函數更新

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

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

其中

通過對仿真事件發生時間相應隸屬度函數的調整，避免系統在仿真演化的過程中陷入一些不可能再現的狀態中。

圖4 模糊區間更新

3 實驗及結果分析

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

表1 工件到達時間與加工時間

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

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

表2 仿真結果

圖5 分割法示例

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

圖6 工件加工完成時間

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

4 結論

具有模糊參數的仿真可以表達系統的不確定性。針對離散事件系統中事件發生時間的不確定性，本文提出了一種新的模糊離散事件仿真方法，

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

[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] 魏世豪. 具有模糊參數的離散事件系統仿真與輸出分析研究[D]. 北京: 清華大學, 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.