基于隨機Petri網的流通加工系統建模研究

李小鵬，李孝忠

(天津科技大學計算機科學與信息工程學院，天津 300222)

流通加工系統是庫存系統的一個關鍵環節，所謂流通加工，就是物品從生產到使用的過程中，根據客戶需要所施加的組裝、包裝、分割、計量、分揀、貼標簽、分裝等簡單作業的總稱，是對生產加工的一種補充．常見的流通加工有冷凍加工、分選加工、精制加工、分裝加工、組裝加工．本文研究的是精制加工，主要包括產品的清洗、加工、包裝等步驟．

Petri網的圖形表示和描述異步并發的能力為系統的建模提供了強有力的幫助．隨機 Petri網(stochastic Petri net，SPN)[1]是在 P/T 網的基礎上，對每個變遷相關聯一個服從指數分布的實施速率，它是用來描述動態行為同構于連續時間馬爾科夫鏈(Markov chain，MC)的離散動態系統的，并被廣泛應用于通信、同步等問題[2]，然而相關研究所處理的系統大多是精確系統，有一定的局限性．

流通加工系統是一個動態離散系統，為了得到更精確的數值解，使系統的性能分析結果更符合實際，本文將 SPN與模糊理論結合，提出一種新的建模與分析方法，即基于模糊參數的 SPN(stochastic Petri net with fuzzy parameter，SPNFP)，并以三華農副產品加工基地農副產品的一次流通加工為研究背景，建立流通加工系統的 SPN模型，對該系統進行了有效性分析(定性分析)和性能分析(定量分析)．有效性分析是基于 T_不變量和馬爾科夫過程的分析；性能分析是基于模糊參數的 SPN的分析，其基本思想是給SPN模型中的每個競爭變遷分配一個模糊算子，對變遷實施速率模糊化，借助于連續時間的 SPN同構于連續時間馬爾科夫鏈的特點得到系統的穩定狀態概率方程組[3–4]，然后利用三角形隸屬模糊數的運算規則得到穩定概率的信任區間，再用區域中心法得到精確解，最后對其進行性能分析．

1 基于模糊參數的隨機Petri網

定義1 基于模糊參數的SPN是一個八元組

模糊引發率iλ?可由三角形隸屬函數[5]中三元組的最大隸屬度，即來定義，其中參數2ia給出了參數1ia和3ia給出模糊數據的最小和最大限．

2 基于SPN的流通加工系統的實例建模

2.1 流通加工的流程

產品的流通加工過程是從農副產品進入系統開始的，主要包括衛生指標檢測、清洗、加工、質量驗收、包裝5個步驟[6-7]，具體流程見圖1．

圖1 流通加工系統的流程圖Fig.1 Flow chart of circulation processing system

2.2 建模

對圖1所示的流通加工系統進行建模，其SPN模型如圖2所示．模型中庫所和變遷的含義如下：1P為農副產品到達倉庫，準備加工；2P為產品的衛生檢測完成；3P為產品等待清洗；4P為產品的清洗完成；5P為產品等待加工；6P為產品的加工完成；7P為產品等待質量驗收；8P為產品的質量驗收完成；9P為產品等待包裝；10P為產品的包裝完成；11P為產品的流通加工完成，等待后序工作；1T為按標準對產品進行衛生質量檢測；2T為將不符合衛生指標的產品搬運至退貨區；3T為將符合衛生指標的產品搬運至清洗區；4T為對產品進行清洗；5T為將清洗后的產品搬運至加工區；6T為對產品進行加工；7T為將加工后的產品搬運至驗收區；8T為對產品進行質量驗收；9T為將質量驗收不合格的產品再次搬運至加工區；10T為將質量驗收合格的產品搬運至包裝區；11T為對產品進行包裝；12T為將包裝好的產品搬運至發貨區，等待發貨；為產品的流通加工全過程結束及信息反饋工作．

模型中的變遷2T和3T及9T和10T 均屬于競爭關系[8]，根據該企業以往的統計資料可知，產品衛生指標檢測合格的概率約為99.5%，產品加工質量合格的概率約為 99.9%．因此，對變遷3T賦予模糊算子為μ2,3=99.5%，對變遷T2賦予模糊算子為μ2,11=1?99.5%=0.5%；對變遷T10賦予模糊算子為μ8,9=99.9%，對變遷 T9賦予模糊算子為 μ8,5=1 ? 9 9.9%=0.1%．

圖2 流通加工系統的SPN模型Fig.2 SPN model of circulation processing system

3 模型的有效性分析和性能分析

3.1 模型有效性分析

3.1.1 基于T_不變量的模型有效性分析

首先得到模型的關聯矩陣

由0×=CX得到T_不變量：

當分量為1時表示此變遷被觸發，分量為0時表

由關聯矩陣及T_不變量可得出如下結論：

(1)此過程中沒有一個變遷(任務)沒有輸入條件或沒有輸出條件，它們都有各自的輸入和輸出庫所，表明任何流通加工任務的完成都需要一定的條件.

(2)沒有死任務，即沒有永遠不能執行的任務，競爭變遷2T和3T及9T和10T 是根據實際情況來判斷的，其他結構均是順序結構，這說明流通加工系統的各個子任務都會發生，這是流通加工工作可以順利完成的前提．

3.1.2 基于馬爾科夫過程的模型有效性分析

根據連續時間的 SPN同構于連續時間馬爾科夫鏈的特點，可得到與SPN模型同構的馬爾科夫鏈，如圖 3所示．其中，馬爾科夫鏈中的狀態可達標識見表1，數字“1”表示庫所中的托肯數(即庫所中的標記數)為1，數字“0”表示庫所中的托肯數為0．

表1 Petri網的狀態可達標識Tab.1 State reachable marking of Petri net

圖3 模型的MCFig.3 MC of the model

由模型的 MC可知：(1)整個流程沒有發生堵塞，托肯的流動是流暢的，流通加工過程最重要的因素仍然是時間因素．(2)整個流程中各個庫所都至多有一個托肯，說明流程不會產生瓶頸．(3)不存在某種狀態iM沒有任何變遷可達，即沒有一個狀態永遠不會發生，模型中不存在死鎖．因此，所建模型是合理的．

3.2 模型性能分析

根據已有 MC可以得到馬爾科夫過程的轉移速率矩陣：

取穩定概率之和“1”的模糊數為(0.9,1,1.1)，令α為 0～1，步長為 0.1，利用三角形隸屬模糊數的運算規則[5]，則可以計算出穩定概率的信任區間，結果見表2．

從而求得

利用區域中心法[10]進行解模糊得：10.098138 x= ，

由此可以得到穩定概率如下：

P[M0]＝0.098,138

P[M1]＝0.039,375

P[M2]＝0.019,745

P[M3]＝P[M9]＝0.097,660

P[M4]＝P[M10]＝0.039,165

P[M5]＝0.392,924

P[M6]＝P[M8]＝0.039,210

P[M7]＝0.097,749

根據求得的穩定概率可以計算出系統性能的指標，包括庫所繁忙的概率、系統變遷的利用率、系統平均延時時間、流入系統的標記流速．

表2 穩定概率的信任區間Tab.2 Confidence interval of stable probability

3.2.1 庫所繁忙的概率

庫所繁忙的概率就是各流通實體所處于忙碌狀態的概率，經計算得

P[M(P1)＝1]＝P[M0]＝0.098,138

P[M(P2)＝1]＝P[M1]＝0.039,375

P[M(P3)＝1]＝P[M3]＝0.097,660

P[M(P4)＝1]＝P[M4]＝0.039,165

P[M(P5)＝1]＝P[M5]＝0.392,924

P[M(P6)＝1]＝P[M6]＝0.039,210

P[M(P7)＝1]＝P[M7]＝0.097,749

P[M(P8)＝1]＝P[M8]＝0.039,210

P[M(P9)＝1]＝P[M9]＝0.097,660

P[M(P10)＝1]＝P[M10]＝0.039,165

P[M(P11)＝1]＝P[M2]＝0.019,745

由此可知，狀態5P的庫所繁忙概率比較大，即產品的等待加工環節最容易產生信息的堆積，因此，可將加工環節作為優化的重點．

3.2.2 系統變遷的利用率

系統變遷的利用率，是使變遷可實施的所有標識的穩定概率之和．經計算得

U(T1)＝P[M0]＝0.098,138

U(T2)＝U(T3)＝P[M1]＝0.039,375

U(T4)＝P[M3]＝0.097,660

U(T5)＝P[M4]＝0.039,165

U(T6)＝P[M5]＝0.392,924

U(T7)＝P[M6]＝0.039,210

U(T8)＝P[M7]＝0.097,749

U(T9)＝U(T10)＝P[M8]＝0.039,210

U(T11)＝P[M9]＝0.097,660

U(T12)＝P[M10]＝0.039,165

U(T13)＝P[M2]＝0.019,745

從計算結果可知，變遷6T的利用率相對較高，即產品的加工過程相對耗時．因此，對加工環節的優化可以有效的提高整個流通加工系統的效率．

3.2.3 系統平均延時時間

根據 SPN 的簡化規則[11]，可得整個流通加工系統的平均實施速率為

即系統平均工作時間為 2.291,359,h．這里的系統平均工作時間考慮了需要流通加工和不需要流通加工兩種情況，而這兩種情況是不可能同時發生的，但從系統分析角度計算時需要將兩種情況同時考慮，所以實際流通加工時間應該小于系統平均工作時間，但仍可作為性能評價的依據．

3.2.4 流入系統的標記流速

每小時流入流通加工系統的平均標記數為0.392,552，即有一個標記數流入流通加工系統需要2.547,433,h．對比系統平均工作時間 2.291,359,h可知，流入系統的標記流速還應適當加快，這樣可以提高流通加工系統的效率．

4 結 語

本文以三華農副產品加工基地農副產品的一次流通加工為研究背景，利用 SPN及模糊相關理論對流通加工系統進行了定性分析和定量分析，驗證了模型的有效性，并指出了流通加工過程中需要重點強化及完善的環節．

實際的流通加工過程中有多種農副產品，本文沒有考慮不同農副產品的分揀過程，直接默認已經分揀好，考慮的是單一農副產品流通加工過程，以后需進一步研究不同農副產品的分揀過程，使加工基地的所有農副產品的流通加工都能順利有序地進行．

［1］ 林闖. 隨機 Petri網和系統性能評價[M]. 2版. 北京：清華大學出版社，2005.

［2］ 顧明甲，張偉，周青. 一種基于 Petri網的安全協議驗證方法[J]. 微計算機信息，2010，26(5-3)：78–80.

［3］ Balbo G. Introduction to Stochastic Petri Nets[M].Berlin：Springer-Verlag，2001：84–155.

［4］ Chen S M. Weighted fuzzy reasoning using weighted fuzzy Petri nets[J]. IEEE Transactions on Knowledge and Data Engineering，2002，14(2)：386–397.

［5］ 楊綸標，高英儀，凌衛星. 模糊數學原理及應用[M]. 5版. 廣州：華南理工大學出版社，2011.

［6］ 張春娜. 基于Petri網的物流倉儲系統建模與仿真[D].南京：南京林業大學，2007：31–37.

［7］ 吳冰. 基于Petri網的物流中心庫存建模和預測仿真的研究和實現[D]. 上海：上海交通大學，2008：15–21.

［8］ Colombo A G，Saiz de Bustamante A. Systems Reliability Assessment[C]. Dordrecht，the Netherlands：Kluwer Academic Publishs，1990：125–130.

［9］ 艾厚文. 基于隨機Petri網的鐵路應急預案流程化研究[D]. 北京：北京交通大學，2008：50.

［10］ 原菊梅，侯朝楨，王小藝，等. 基于隨機 Petri網的可修系統可用性模糊評價[J]. 計算機工程，2007，33(8)：17–19.

［11］ 王偉，劉文菊，蘇迪. 基于 Petri網的物流倉儲系統的建模研究[J]. 2010，21(11)：95–98.