無沖突Petri網系統活標識判定的結構化方法

摘要：為了有效求解無沖突Petri網系統活標識的判定及配置優化問題，提出無沖突Petri網系統活標識判定的一種結構化方法。該方法首先求取無沖突Petri網的各強連通分支；然后對每一含有元素個數大于2的強連通分支求取其無同步變遷庫所索引集合；最終得到無沖突Petri網系統的無前置庫所索引集合，基于該庫所元素集合即可實現對活標識的快速判定及配置優化。通過例子具體說明了該方法的實現及應用。分析結果表明，所提方法具有多項式時間復雜度，較易于操作和程序化實現。

關鍵詞：Petri網；無沖突；活標識；強連通分支

中圖分類號：TP391文獻標志碼：A文章編號：1001-3695（2023）05-025-1447-05doi：10.19734/j.issn.1001-3695.2022.09.0499

0引言

Petri網作為系統建模與分析的工具，已廣泛應用于柔性制造系統、離散事件系統等領域中的系統建模與問題分析［1～4］。無沖突Petri網［5］作為Petri網的一個子類，在網結構上僅要求每個庫所元素至多有一個后置變遷元素，因而其性質分析方法（與一般Petri網相比）相對容易。與實際系統的運行控制［6，7］和初始資源配置優化問題［8，9］相對應，無沖突Petri網系統的活性判定［5］及活標識配置問題［10］一直是對該類Petri網系統進行理論和應用方法研究的關鍵問題之一。文獻［5］基于無沖突Petri網系統的初始標識，通過判斷T-path的存在性得到無沖突Petri網結構活性判定的多項式時間算法；文獻［11］基于強連通P-子網活性得到無沖突Petri網的活標識滿足的一個充分條件；文獻［12～14］對無沖突Petri網的合成運算，可達圖和持續性等性質進行了研究。以上方法中對無沖突Petri網系統的活標識判定方法的研究與算法設計均是基于網系統的初始標識展開，多為定性及理論方法的研究，在判定方法的可操作性與可程序化方面需要進一步的研究和算法設計，較少涉及到操作可行的活標識優化配置策略［15］，以及極小活標識［16～18］配置方法。

與一般Petri網相比，顯然無沖突Petri網的結構相對簡單，因此本文的出發點為：是否可找到與無沖突Petri網系統活標識對應的某種結構（比如庫所元素子集合），并且該結構與網系統的標識無關，只需基于該結構便可實現Petri網系統活標識的判定及其配置問題的快速求解?；诖?，本文在無沖突Petri網結構活性判定已得到解決［19］的基礎上，從Petri網結構的連通性分析入手，依次研究強連通及具有多個強連通分支的無沖突Petri網系統活標識相關的充分必要條件，最終得到與網標識無關且與網系統活性相對應的庫所元素集合，基于該庫所元素集合可快速判斷一個標識是否為無沖突Petri網的活標識，并可方便地對網系統的活標識進行配置與優化。

基于算法1、定理5～7可知，算法2的正確性及可終止性顯然成立。

對算法2中各步驟的具體實現方法及時間復雜度依次分析如下：

步驟a）判斷無沖突網系統Σ的結構活性，即判斷網中是否存在源庫所元素，時間復雜度為O（mn）。

步驟b）求取網系統Σ的強連通分支，可利用Tarjan算法［22］實現，時間復雜度為O（m+n+f）。

步驟c1）對步驟b）求得的每一個強連通分支，利用算法1求取其無同步變遷庫所索引集合，Σ滿足|SCC|≥2的強連通分支數不超過（m+n）/2，結合算法1的時間復雜度，可知步驟c1）的時間復雜度不超過O（m2n2（m+n+f））。

步驟c2）求取Σ的無前置庫所索引集合。由定義10可知，通過查找和判斷一個無同步變遷庫所索引集合中各個庫所元素的前置變遷元素是否均在其所屬強連通分支中，即可判斷其是否為一個無前置庫所索引集合，每次可通過不超過n次查找即可得到結論，因此每個無同步變遷庫所索引集合所需時間復雜度不超過O（mn2），Σ中|SCC|≥2的強連通分支數不超過（m+n）/2，每一強連通分支中無同步變遷庫所索引集合數不超過m，因此步驟c2）的時間復雜度不超過O（m2n2（m+n））。

步驟d）可通過對每一個無前置庫所索引集合中檢索其中庫所元素在標識M0下是否得到標識進行，由性質1可知，Σ中無前置庫所索引集合個數不超過m，每個無前置庫所索引集合中庫所個數不超過m，因此步驟d）的時間復雜度不超過O（m2）。

綜合各步驟的時間復雜度可得算法2的時間復雜度不超過O（m2n2（m+n+f））。

下面通過對制造系統領域中一個活塞桿機器人裝配單元的Petri網模型N1［8］（圖1）的活標識判定及配置問題的求解，具體說明本文方法的實現和應用方法。

可以看出，對于一個結構活的無沖突Petri網，基于算法2求出的無前置庫所索引集合，即可快速判斷某一標識是否為該網的一個活標識，并可方便地為其配置極小活標識。

相關方法比較：a）在無沖突Petri網系統的活標識（活性）判定問題方面，與文獻［5，11］中方法相比，本文方法從Petri網的網結構出發，求解得到無沖突Petri網的無前置庫所索引集合，基于該庫所集合即可實現判斷不同標識是否為活標識的問題，不需要重復求取該庫所集合，而文獻［5］中的方法需要對每一個初始標識均進行相應結構的確定和計算，文獻［11］僅給出了無沖突Petri網的活標識的一個充分條件；b）在結構活無沖突Petri網系統的極小活標識配置方法方面，與文獻［18］相比，本文方法無須進行Petri網系統可重復性［18，20］的判斷（需要判斷整系數線性方程組是否存在正整數解向量），從而可明顯節約計算量；c）在Petri網結構分解方法方面，與基于共享庫所（或變遷）元素［23］、基于極小P-不變量支撐集［24］以及基于庫所元素的索引函數［25］的Petri網結構分解策略分別不同，本文方法首先從強連通分支角度進行網結構的分解，進而在一個強連通分支內部以同步變遷為出發點進行網結構的分解。

4結束語

本文從無沖突Petri網的結構分析入手，研究和設計了一種無沖突Petri網系統活標識判定問題的結構化算法（算法2），本文方法只需從Petri網的網結構出發求解得到其無前置庫所索引集合，可用于實現對無沖突Petri網系統活標識的快速判定與配置。

進一步，如何將本文相關方法進行程序實現并應用于實際的制造系統和離散事件系統中活性控制與資源配置優化問題是本文下一步工作的主要方向。同時，本文研究結果表明，Petri網結構中的同步變遷及相關結構對網系統的活性性質有著重要的影響，而一般Petri網系統的活性判定問題目前尚無有效方法，可否將本文思路及方法應用于一般Petri網系統（尤其含有沖突結構的）的活性判定也是值得進一步拓展和深入研究的問題。

參考文獻：

［1］WenzelburgerP，AllgwerF.APetrinetmodelingframeworkforthecontrolofflexiblemanufacturingsystems［J］.IFAC-PapersOnLine，2019，52（13）：492-498.

［2］鄧明喜，黎良，劉斌.基于修正狀態類圖的標簽時間Petri網系統故障診斷［J］.計算機應用研究，2022，39（6）：1678-1682，1688.（DengMingxi，LiLiang，LiuBin.FaultdiagnosisoflabeledtimePetrinetsystemsbasedonmodifiedstateclassgraph［J］.ApplicationResearchofComputers，2022，39（6）：1678-1682，1688.）

［3］XiaChuanliang，LiChengdong.PropertypreservationofPetrisynthesisnetbasedrepresentationforembeddedsystems［J］.IEEE/CAAJournalofAutomaticaSinica，2021，8（4）：905-915.

［4］管夢真，劉偉，杜玉越.基于邏輯時延Petri網的停車預訂系統建模與分析［J］.計算機應用研究，2021，38（8）：2412-2417.（GuanMengzhen，LiuWei，DuYuyue.Modelingandanalysisofparkingre-servationsystembasedonlogicaltime-delayedPetrinet［J］.ApplicationResearchofComputers，2021，38（8）：2412-2417.）

［5］PaolaA，EstebanF，LuigiL，etal.Lineartimeanalysisofpropertiesofconflict-freeandgeneralPetrinets［J］.TheoreticalComputerScience，2011，412（4-5）：320-338.

［6］LiLiang，BasileF，LiZhiwu.Closed-loopdeadlock-freesupervisionforGMECsintimePetrinetsystems［J］.IEEETransonAutomaticControl，2021，66（11）：5326-5341.

［7］李大成，羅繼亮，孫莎莎，等.基于平行Petri網的制造系統調度與控制一體化方法［J/OL］.自動化學報.（2021-02-22）.https：//doi.org/10.16383/j.aas.c200842.（LiDacheng，LuoJiliang，SunShasha，etal.TheintegratedmethodofschedulingandcontrolformanufacturingsystemsbasedonparallelPetrinets［J/OL］.ActaAutomaticaSinica.（2021-02-22）.https：//doi.org/10.16383/j.aas.c200842.）

［8］郝晉淵，孫丹丹，郝真鳴，等.基于標簽Petri網的自動制造系統初始資源配置優化［J］.電子測量與儀器學報，2020，34（8）：30-36.（HaoJinyuan，SunDandan，HaoZhenming，etal.InitialresourceallocationoptimizationofautomatedmanufacturingsystemsusinglabeledPetrinets［J］.JournalofElectronicMeasurementandInstrumentation，2020，34（8）：30-36.）

［9］郝真鳴，孫丹丹，郝晉淵，等.基于Petri網的離散事件系統初始資源優化配置［J］.河北大學學報：自然科學版，2020，40（2）：212-217.（HaoZhenming，SunDandan，HaoJinyuan，etal.InitialresourceoptimizationallocationofdiscreteeventsystemsusingPetrinets［J］.JournalofHebeiUniversity：NaturalScienceEdition，2020，40（2）：212-217.）

［10］HeZhou，LiuMiao，MaZiyue，etal.Animprovedapproachformar-kingoptimizationoftimedweightedmarkedgraphs［J］.DiscreteEventDynamicSystems-Theoryandapplications，2019，29（2）：127-143.

［11］HujsaT，DelosmeJM，Munier-KordonA.Polynomialsufficientconditionsofwell-behavednessandhomemarkingsinsubclassesofweightedPetrinets［J］.ACMTransonEmbeddedComputingSystems，2014，13（4s）：articleID141.

［12］BestE，DevillersR，SchlachterU.Boundedchoice-freePetrinetsynthesis：algorithmicissues［J］.ActaInformatica，2018，55（7）：575-611.

［13］WimmelH.Presynthesisofboundedchoice-freeorfork-attributionnets［J］.InformationandComputation，2020，271：104482.

［14］DevillersR，ErofeevE，HujsaT.Efficientsynthesisofweightedmarkedgraphswithcircularreachabilitygraph，andbeyond［M］//KoutnyM，KordonF，PomelloL.TransactionsonPetriNetsandOtherModelsofConcurrencyXV.Berlin：Springer，2021：75-100.

［15］MaZiyue，ZhuGuanghui，LiZhiwu，etal.Computationofadmissiblemarkingsetsinweightedsynchronization-freePetrinetsbydynamicprogramming［J］.IEEETransonAutomaticControl，2020，65（6）：2662-2669.

［16］葉劍虹，葉雙.帶抑制弧Petri網極小活標識的配置［J］.華僑大學學報：自然科學版，2011，32（5）：525-528.（YeJianhong，YeShuang.AssignmentofminimallivemarkingforPetrinetwithinhibitorarcs［J］.JournalofHuaqiaoUniversity：NaturalScienceEdition，2011，32（5）：525-528.）

［17］徐淑琳，周廣瑞，岳昊.標注Petri網中的最小初始標識估計［J］.計算機工程，2021，47（4）：285-290，297.（XuShulin，ZhouGuang-rui，YueHao.EstimationofminimuminitialmarkinginlabeledPetrinets［J］.ComputerEngineering，2021，47（4）：285-290，297.）

［18］許安國，趙義軍.無沖突可重復網極小活標識的配置［J］.系統仿真學報，2003，15（S1）：35-39.（XuAnguo，ZhaoYijun.Theassignmentofminimallivemarkingforchoice-freerepetitivePetrinet［J］.JournalofSystemSimulation，2003，15（S1）：35-39.）

［19］徐穎蕾，馬炳先.無沖突Petri網的結構活性判定研究［J］.計算機工程，2021，47（7）：296-300.（XuYinglei，MaBingxian.Researchonstructurallivenessdeterminationofconflict-freePetrinet［J］.ComputerEngineering，2021，47（7）：296-300.）

［20］吳哲輝.Petri網導論［M］.北京：機械工業出版社，2006.（WuZhehui.AnintroductiontoPetrinets［M］.Beijing：ChinaMachinePress，2006.）

［21］嚴蔚敏，吳偉民.數據結構（C語言版）［M］.北京：清華大學出版社，2007.（YanWeimin，WuWeimin.Datastructure（Clanguageversion）［M］.Beijing：TsinghuaUniversityPress，2007.）

［22］PearceDJ.Aspace-efficientalgorithmforfindingstronglyconnectedcomponents［J］.InformationProcessingLetters，2016，116（1）：47-52.

［23］ZhongChunfu，HeWenlong，LiZhiwu，etal.DeadlockanalysisandcontrolusingPetrinetdecompositiontechniques［J］.InformationSciences，2019，482：440-456.

［24］Wis＇niewskiR，KaratkevichA，Stefanowicz，etal.DecompositionofdistributededgesystemsbasedonthePetrinetsandlinearalgebratechnique［J］.JournalofSystemsArchitecture，2019，96：20-31.

［25］ZhouKaiqing，MoLiping，ChenChangfeng，etal.AdecompositionalgorithmofPetrinetutilizingindexfunction［J］.Filomat，2020，34（15）：5085-5094.