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

關(guān)鍵詞：Petri網(wǎng)；無沖突；活標(biāo)識(shí)；強(qiáng)連通分支

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1001-3695（2023）05-025-1447-05doi：10.19734/j.issn.1001-3695.2022.09.0499

0引言

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

與一般Petri網(wǎng)相比，顯然無沖突Petri網(wǎng)的結(jié)構(gòu)相對簡單，因此本文的出發(fā)點(diǎn)為：是否可找到與無沖突Petri網(wǎng)系統(tǒng)活標(biāo)識(shí)對應(yīng)的某種結(jié)構(gòu)（比如庫所元素子集合），并且該結(jié)構(gòu)與網(wǎng)系統(tǒng)的標(biāo)識(shí)無關(guān)，只需基于該結(jié)構(gòu)便可實(shí)現(xiàn)Petri網(wǎng)系統(tǒng)活標(biāo)識(shí)的判定及其配置問題的快速求解?；诖耍疚脑跓o沖突Petri網(wǎng)結(jié)構(gòu)活性判定已得到解決［19］的基礎(chǔ)上，從Petri網(wǎng)結(jié)構(gòu)的連通性分析入手，依次研究強(qiáng)連通及具有多個(gè)強(qiáng)連通分支的無沖突Petri網(wǎng)系統(tǒng)活標(biāo)識(shí)相關(guān)的充分必要條件，最終得到與網(wǎng)標(biāo)識(shí)無關(guān)且與網(wǎng)系統(tǒng)活性相對應(yīng)的庫所元素集合，基于該庫所元素集合可快速判斷一個(gè)標(biāo)識(shí)是否為無沖突Petri網(wǎng)的活標(biāo)識(shí)，并可方便地對網(wǎng)系統(tǒng)的活標(biāo)識(shí)進(jìn)行配置與優(yōu)化。

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

對算法2中各步驟的具體實(shí)現(xiàn)方法及時(shí)間復(fù)雜度依次分析如下：

步驟a）判斷無沖突網(wǎng)系統(tǒng)Σ的結(jié)構(gòu)活性，即判斷網(wǎng)中是否存在源庫所元素，時(shí)間復(fù)雜度為O（mn）。

步驟b）求取網(wǎng)系統(tǒng)Σ的強(qiáng)連通分支，可利用Tarjan算法［22］實(shí)現(xiàn)，時(shí)間復(fù)雜度為O（m+n+f）。

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

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

步驟d）可通過對每一個(gè)無前置庫所索引集合中檢索其中庫所元素在標(biāo)識(shí)M0下是否得到標(biāo)識(shí)進(jìn)行，由性質(zhì)1可知，Σ中無前置庫所索引集合個(gè)數(shù)不超過m，每個(gè)無前置庫所索引集合中庫所個(gè)數(shù)不超過m，因此步驟d）的時(shí)間復(fù)雜度不超過O（m2）。

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

下面通過對制造系統(tǒng)領(lǐng)域中一個(gè)活塞桿機(jī)器人裝配單元的Petri網(wǎng)模型N1［8］（圖1）的活標(biāo)識(shí)判定及配置問題的求解，具體說明本文方法的實(shí)現(xiàn)和應(yīng)用方法。

可以看出，對于一個(gè)結(jié)構(gòu)活的無沖突Petri網(wǎng)，基于算法2求出的無前置庫所索引集合，即可快速判斷某一標(biāo)識(shí)是否為該網(wǎng)的一個(gè)活標(biāo)識(shí)，并可方便地為其配置極小活標(biāo)識(shí)。

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

4結(jié)束語

本文從無沖突Petri網(wǎng)的結(jié)構(gòu)分析入手，研究和設(shè)計(jì)了一種無沖突Petri網(wǎng)系統(tǒng)活標(biāo)識(shí)判定問題的結(jié)構(gòu)化算法（算法2），本文方法只需從Petri網(wǎng)的網(wǎng)結(jié)構(gòu)出發(fā)求解得到其無前置庫所索引集合，可用于實(shí)現(xiàn)對無沖突Petri網(wǎng)系統(tǒng)活標(biāo)識(shí)的快速判定與配置。

進(jìn)一步，如何將本文相關(guān)方法進(jìn)行程序?qū)崿F(xiàn)并應(yīng)用于實(shí)際的制造系統(tǒng)和離散事件系統(tǒng)中活性控制與資源配置優(yōu)化問題是本文下一步工作的主要方向。同時(shí)，本文研究結(jié)果表明，Petri網(wǎng)結(jié)構(gòu)中的同步變遷及相關(guān)結(jié)構(gòu)對網(wǎng)系統(tǒng)的活性性質(zhì)有著重要的影響，而一般Petri網(wǎng)系統(tǒng)的活性判定問題目前尚無有效方法，可否將本文思路及方法應(yīng)用于一般Petri網(wǎng)系統(tǒng)（尤其含有沖突結(jié)構(gòu)的）的活性判定也是值得進(jìn)一步拓展和深入研究的問題。

參考文獻(xiàn)：

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

［2］鄧明喜，黎良，劉斌.基于修正狀態(tài)類圖的標(biāo)簽時(shí)間Petri網(wǎng)系統(tǒng)故障診斷［J］.計(jì)算機(jī)應(yīng)用研究，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］管夢真，劉偉，杜玉越.基于邏輯時(shí)延Petri網(wǎng)的停車預(yù)訂系統(tǒng)建模與分析［J］.計(jì)算機(jī)應(yīng)用研究，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網(wǎng)的制造系統(tǒng)調(diào)度與控制一體化方法［J/OL］.自動(dòng)化學(xué)報(bào).（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］郝晉淵，孫丹丹，郝真鳴，等.基于標(biāo)簽Petri網(wǎng)的自動(dòng)制造系統(tǒng)初始資源配置優(yōu)化［J］.電子測量與儀器學(xué)報(bào)，2020，34（8）：30-36.（HaoJinyuan，SunDandan，HaoZhenming，etal.InitialresourceallocationoptimizationofautomatedmanufacturingsystemsusinglabeledPetrinets［J］.JournalofElectronicMeasurementandInstrumentation，2020，34（8）：30-36.）

［9］郝真鳴，孫丹丹，郝晉淵，等.基于Petri網(wǎng)的離散事件系統(tǒng)初始資源優(yōu)化配置［J］.河北大學(xué)學(xué)報(bào)：自然科學(xué)版，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網(wǎng)極小活標(biāo)識(shí)的配置［J］.華僑大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，32（5）：525-528.（YeJianhong，YeShuang.AssignmentofminimallivemarkingforPetrinetwithinhibitorarcs［J］.JournalofHuaqiaoUniversity：NaturalScienceEdition，2011，32（5）：525-528.）

［17］徐淑琳，周廣瑞，岳昊.標(biāo)注Petri網(wǎng)中的最小初始標(biāo)識(shí)估計(jì)［J］.計(jì)算機(jī)工程，2021，47（4）：285-290，297.（XuShulin，ZhouGuang-rui，YueHao.EstimationofminimuminitialmarkinginlabeledPetrinets［J］.ComputerEngineering，2021，47（4）：285-290，297.）

［18］許安國，趙義軍.無沖突可重復(fù)網(wǎng)極小活標(biāo)識(shí)的配置［J］.系統(tǒng)仿真學(xué)報(bào)，2003，15（S1）：35-39.（XuAnguo，ZhaoYijun.Theassignmentofminimallivemarkingforchoice-freerepetitivePetrinet［J］.JournalofSystemSimulation，2003，15（S1）：35-39.）

［19］徐穎蕾，馬炳先.無沖突Petri網(wǎng)的結(jié)構(gòu)活性判定研究［J］.計(jì)算機(jī)工程，2021，47（7）：296-300.（XuYinglei，MaBingxian.Researchonstructurallivenessdeterminationofconflict-freePetrinet［J］.ComputerEngineering，2021，47（7）：296-300.）

［20］吳哲輝.Petri網(wǎng)導(dǎo)論［M］.北京：機(jī)械工業(yè)出版社，2006.（WuZhehui.AnintroductiontoPetrinets［M］.Beijing：ChinaMachinePress，2006.）

［21］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）［M］.北京：清華大學(xué)出版社，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.