基于S4PR網的多類型不可靠資源AMS自適應死鎖控制策略

摘 要：自動制造系統（AMS）產生的死鎖為制造企業造成嚴重經濟損失，為解決死鎖問題，提出了更精確、有效的死鎖控制策略。該策略首先研究多類型不可靠資源對死鎖的影響，擴展S4PR網建模，提出新的網結構表征死鎖：資源嚴格極小虹吸，改進混合整數規劃（MIP）方法計算資源嚴格極小虹吸，添加修復子網保證AMS活性；其次考慮資源故障問題，設計控制器與監督器確保系統穩健性，添加觀察器，實現死鎖控制自適應性；最后通過仿真實驗驗證該策略允許更多可達標記，得到多項式復雜度，對比分析其有效性與優越性。該策略研究復雜死鎖與故障情況，為生產要求較高的制造過程提供穩健控制，在實際生產中實現高效化、智能化。

關鍵詞：自動制造系統；不可靠資源；極小虹吸；自適應死鎖控制

中圖分類號：TP311"" 文獻標志碼：A

文章編號：1001-3695（2024）12-035-3786-07

doi： 10.19734/j.issn.1001-3695.2024.04.0120

Adaptive deadlock control strategy for multi-type unreliable resource AMS based on S4PR

Sun Yating， Liu Wei

（College of Computer Science amp; Engineering， Shandong University of Science amp; Technology， Qingdao Shandong 266590， China）

Abstract：Due to the deadlocks generated by AMS causing serious economic losses to manufacturing enterprises， this paper proposed a more precise and effective deadlock control strategy to solve the deadlock problem. This strategy firstly investigated the impact of multiple types of unreliable resources on deadlocks， extended S4PR network modeling， and proposed a new network structure to characterize deadlocks： resource strict minimum siphon， improved MIP method to calculate resource strict minimum siphon， and added recovery subnets to ensure the activity of AMS. Secondly， it considered the issue of resource fai-lures， designed controllers and supervisors to ensure system robustness， added observers to achieve adaptive deadlock control. Finally， it conducted simulation experiments to verify that this strategy allows for more reachable markings and obtains polynomial complexity， and compared and analyzed its effectiveness and superiority. This strategy studied complex deadlocks and fault situations， providing robust control for manufacturing processes with high production requirements， and achieving efficiency and intelligence in actual production.

Key words：automated manufacturing system; unreliable resource; minimum siphon; adaptive deadlock control strategy

0 引言

自動制造系統（AMS）是一種零件加工或者零件組裝的自動化生產過程[1]。由于經濟成本和規模復雜度的限制，為AMS提供的資源是有限的，當資源分配不合理時，各個進程之間存在資源競爭，可能會出現錯誤狀態，引發死鎖[2]。在實際生產過程中，不可靠資源的意外故障會導致自動制造系統停滯，引起不必要的停機時間，給企業帶來經濟損失[3]。對于可能會發生資源故障的自動制造系統，即使在資源發生故障的情況下，不使用該故障資源的加工仍能正常進行加工生產，則稱系統是穩健的[4]。因此，為AMS提供穩健控制策略是十分必要的。

在AMS建模與控制中，Petri網是一種廣泛使用的數學工具，針對AMS中的死鎖控制，研究人員利用Petri網建模，提出重要的死鎖控制策略[5～11]。虹吸是一種Petri網結構，該結構中庫所的托肯數與死鎖的產生關系密切。當虹吸為可排空狀態時，即它的標記托肯數為零時，系統可能會出現資源循環等待。因此，研究人員基于結構分析中的可排空虹吸結構控制死鎖的產生。在結構分析中，相比最大完美回路法，虹吸法更聚焦資源分配與資源故障之間的聯系，側重考慮多類型資源對死鎖產生的影響。Li等人[5]首次提出基本虹吸與依賴虹吸概念，并分析可排空的嚴格極小虹吸與死鎖狀態之間的關系。基于基本虹吸，Hu等人[6]設計算法生成基本虹吸的最優集合，提出穩健控制方法。基本虹吸法雖初步解決死鎖定位問題，但容易獲得冗余虹吸，產生較高空間復雜度。Ezpeleta等人[7]首先采用枚舉法遍歷極小虹吸，隨著規模的增加，計算復雜度成指數增加。Zhang等人[8]提出強可控虹吸概念，利用整數線性規劃方法（ILP）計算虹吸。ILP避免虹吸遍歷枚舉，提升計算效率，但拒絕更多可達標記，禁止部分可行的生產路線。Al-Ahmari等人[9]利用顏色Petri網提出兩步法死鎖控制策略。Abubakar等人[10]不使用中央緩沖區控制不可靠資源，利用改進鄰域約束方法：單路鄰域方法，解決資源故障問題，該方法不能應用于同時需要多個資源單元的系統，無法適應復雜生產要求和提高生產效率。基于傳統MIP，Wang等人[11]創新MIP，使其適應可空極小虹吸結構。該方法雖然只研究可靠資源情況，沒有考慮現實資源故障，但該MIP方法能夠降低時間復雜度的同時允許更多可達標記，為本文研究提供新思路。近些年，研究人員提出自適應死鎖控制[12]概念，以在線方式實時監督死鎖狀態，增強生產高效性與穩健性。現階段自適應死鎖控制研究還在初期，大多研究沒有考慮多類型不可靠資源發生資源故障的復雜情況，并且多為基于傳統S3PR建模，沒有充分利用S4PR中共享資源。

隨著自動化技術高速發展，用戶對生產過程的高效性、高產性、精確性等要求越來越嚴格[13]。為滿足用戶多樣性需求，制造企業的生產規模與加工零件種類隨之增加，要求降低死鎖對系統產生的影響的同時，提高穩健性。因此本文基于S4PR研究多類型不可靠資源對死鎖影響與控制，實現系統穩健性與自適應性，通過動態調整資源配置優化資源利用率，使系統適應不同的生產加工環境，并且保證系統高效性與安全性。

本文主要貢獻是：a）擴展S4PR模型：U-S4PR模型，引入資源嚴格極小虹吸概念，證明可排空狀態表征死鎖，改進MIP方法，解決多類型多數量不可靠資源產生死鎖的復雜情況；b）考慮資源故障，對單一類型不可靠資源和多類型不可靠資源引發的資源故障提出兩種控制器定義：開關控制器和復合控制器，更高效判斷資源故障種類，精確修復故障；設計觀察器監督激活狀態，實現自適應控制，提出自適應死鎖控制算法；c）將U-S4PR模型進行仿真實驗，在計算復雜度、影響死鎖因素等方面進行實驗對比，驗證本文策略有效性。

定義11 設N=（P，T，F，W）是一個Petri網，若S∈P是非空庫所，且·SS·，則S稱為一個虹吸；若虹吸S不包含其他任何虹吸，則稱S為極小虹吸；若一個極小虹吸S不包含任何P-半流的支持，則稱S為嚴格極小虹吸（SMS）。若M（S）gt;0，則表示在標記M處，嚴格極小虹吸S被標記，否則，表示S未被標記。

定義12 設（N，M0）是一個標記U-S4PR，若M∈R（N，M0）使得在標記M處，嚴格極小虹吸S是未被標記的，則稱S為可空極小虹吸（EMS），否則，S是非空極小虹吸。

例1 U-S4PR中，S1 ={r1， r3，r4， p5， p10， p13}各元素都為非空庫所且形成自環結構，所以·S1S1·，S1中不包含其他完整虹吸和P-半流的支持，則S1是嚴格極小虹吸。同理S2 = {r5， r6， p7， p9}，S3 = {r2， r4， r5， r6， p5， p9}也是嚴格極小虹吸。

3 資源嚴格極小虹吸

本章提出資源嚴格極小虹吸概念，與傳統嚴格極小虹吸不同，資源嚴格極小虹吸深入研討多類型多數量不可靠資源引發死鎖的原因與其對死鎖的表征結構。改進MIP方法，使其適應U-S4PR模型結構，避免虹吸枚舉遍歷產生指數型計算復雜度，并設計修復子網控制死鎖。

由文獻[21]可知，嚴格極小虹吸S的可空狀態與S4PR模型的死鎖表征之間有充分必要的對應關系，因此，只要系統中存在可空極小虹吸，該網是非活性的。由于本章考慮多類型多數量不可靠資源對死鎖的影響，提出以下新定義。

定義13 設（N，M0）是一個標記U-S4PR，S是（N，M0）中一個SMS，如果S中包含多類型多數量的不可靠資源，那么稱S為資源SMS，記作Smu，稱RSmu為資源SMS的集合。設B［Smu］=B［S］∪（S∩H（RSmu）），其中B［Smu］，表示Smu的補集；并且B［S］=H（S∩PR）＼S，表示S的補集。

在定義13中，當S∩H（RSmu）≠時，S=Smu，但B［S］≠B［Smu］。也就是說，嚴格極小虹吸SMS與資源嚴格極小虹吸Smu本質上沒有差別，但是它們的補集不同，因此，在S4PR中可以利用Smu的可空狀態表征多類型資源的死鎖結構。

例2 圖1中Smu1 = S1 = {r1， r3， r4， p5， p10， p13}，M0（Smu1）=3，Smu2 = S2 = {r5， r6， p7， p9}，M0（Smu2）=2，Smu3 = S3 = {r2， r4， r5， r6， p5， p9}，M0（Smu3）=4。但是B[Smu1]={ p2， p3， p4， p5， p11， p12， p13}=B[S1]∪{p5， p13}，B[Smu2]={ p7， p9， p10}=B[S2]∪{p7， p9}，B[Smu3]={ p2， p3， p4， p5， p6， p9， p10， p11， p13}=B[S3]∪{p5， p9}。

根據定義13可知，在存在多類型多數量不可靠資源的自動制造系統中，可空的資源嚴格極小虹吸Smu可以表征死鎖，因此，下面將根據Smu結構特征改進混合整數規劃算法優化可空Smu的計算效率。

如果一個SMS中不包含任何多類型的不可靠資源，那么利用傳統的混合整數規劃算法即可迭代式計算，公式如下[11]：

|∑p∈P（1－vp）·［N］（p，t）|≤1，t∈T（21）

其中：式（16）中的D表示一個足夠大的正數。與傳統混合整數規劃算法相比，本文在改進版本中添加不可靠資源的約束條件，在式（15）中，vr是一個二進制變量，當vr=0時，r∈Smu；當vr=1時，rSmu。在式（21）中，結合S4PR網結構的特征，將混合整數規劃算法擴展到S4PR。當公式G1有解時，說明系統中存在可空Smu，即系統中可能會發生死鎖，此時需要對該可空Smu進行標記，再次計算公式G1，以此不斷循環迭代計算公式G1，直到公式G1無解，說明此時系統中無可空Smu，所有的可空Smu都已經被標記。

定理1 設（N，M0）是一個標記U-S4PR，由改進MIP得到的一個解對應一個可排空Smu。

證明 與傳統MIP相比，改進MIP添加了式（15） （16） （21），其他公式不變。由文獻[21]可知，傳統MIP的一個解對應一個可排空SMS。在改進MIP中，由于U-S4PR（N，M0）存在多類型不可靠資源，所以式（15）針對不可靠資源vr添加限制條件，且r∈PuR與p∈PA相互獨立，互不影響。同樣，由于不可靠資源的影響，式（16）中活動庫所的判斷要考慮vr個數，并簡化為二進制vp。式（16）在本質上與式（7）是一樣的。由于傳統MIP應用于普通網，所以式（21）保證了U-S4PR是一個普通網。當U-S4PR是一個普通網，向量［N］（p，t）只能是1或-1，∑p∈P（1－vp）≤1，所以∑p∈P（1－vp）·［N］（p，t）一定是0或1。式（21）對vp的值無影響。并且，當S∩H（RSmu）≠時，S=Smu。因此，改進MIP的一個解對應一個可排空Smu。

推論1 設（N，M0）是一個標記U-S4PR，Smu是由改進MIP計算得到的虹吸。若X是非負數，且p∈{‖X‖－∩Smu}，都有maxp·=1，‖X‖+Smu且XT·M0gt;∑p∈SX（p）（maxp·－1），則Smu是最大控制的。

推論2 設（N，M0）是一個標記U-S4PR，Smu是由改進MIP計算得到的虹吸。若XT·M0gt;0，其中‖X‖+Smu，則Smu是被X最大控制的。

算法1 計算可空Smu

輸入：一個Petri網U-S4PR（N，M0）

輸出：標記的可空Smu集合

a）αG=，tol=0//αG存儲標記的可空Smu。

b）G=1

c）while（G=） do

if （zt≥∑p∈·tvp－|·t|+1）

if （vr+∑p∈H（r）vp≤|H（r）|）

if （vp≤1－（Πt∈p··∑r∈·t∩PRvr）/D） //判斷S是否為Smu

B（p）=max{M（p）|M=M0+［N］Y}//計算標記處最大托肯數

if （vp≥M（p）/B（p）amp;amp;|∑p∈P（1－vp）·［N］（p，t）|≤1） /*判斷Smu可排空性*/

G=Maximize（∑p∈PR|PA|·vp+∑p∈PAvp）

αG=αG∪G，tol++，并標記可空Smu

d）輸出αG

例3 以關鍵庫所p9為例。在U-S4PR中算法1迭代至S2={r5，r6，p7，p9}時，H（r5）={p9，p7}，H（r6）={p10}，t10≠S·1，p10S1，所以zt=1，vp=1，vr=0，滿足式（13）～（16）。B（p）=M0（S2）=2，M（S2）=2，滿足式（17）～（21），因此S2一定是G1的一個解。

針對改進MIP計算得到的標記的可排空Smu集合，本文將利用修復子網控制其死鎖的發生。考慮到多類型不可靠資源的存在，將修復子網分為共享資源部分和普通修復子網部分，下面定義改進的修復子網。

定義14 設（N，M0）是一個標記U-S4PR，若ru∈PuR，則修復子網為（Nri，Mri0）=（{pi，pri，psi，ru}，{tAi，tri，tsi}，Fri，Wi，Mri0，Vi），當且僅當：

a）pi表示活動庫所，pi∈H（ru）；pri表示修復庫所；psi表示共享庫所，存儲共享資源。

b）tAi表示分支變遷，連接修復庫所或者共享庫所；tri表示修復變遷，將失效托肯移入修復庫所；tsi表示共享變遷，將失效托肯移入共享庫所。

c）Fri={（pi，tAi），（tAi，pri），（pri，tri），（tri，pi），（ru，tri），（ti，psi），（psi，tsi），（tsi，pi）}，Mri0（pi）≥0，Mri0（pri）=Mri0（psi）=0。

根據定義14，在給定U-S4PR（N，M0）中，ru表示不可靠資源，pi∈H（ru），當ru是空閑狀態或者占用狀態時，不可靠資源可能會失效。當不可靠資源在pi中失效時，分支變遷tAi的使能使得失效的托肯從活動庫所pi移出，移入到修復庫所pri中，同時，不同種類未失效的資源移入共享庫所中。如果在不可靠資源ru中有空閑的工作單元，那么移入共享庫所的托肯通過tsi的使能回到系統中。在修復庫所pri中完成修復的托肯，通過tri的使能回到活動庫所pi中，繼續完成生產加工階段，該過程能夠有效地將不同種類的不可靠資源進行修復，且未失效的多種類資源通過共享庫所psi可以繼續被所需零件占有。

例4 r5的占用導致不可靠資源在p9中失效，Smu2陷入循環等待。此時分支變遷ta9將失效托肯移出p9，并在pr9中修復，完成修復后回到p9，此時Smu2解除循環等代狀態。而未失效托肯在ps9始終保持加工狀態。為p9生成修復子網，如圖2所示。

定理2 設（N，M0）是一個標記U-S4PR，若每個可排空Smu都添加修復子網（Nri，Mri0），則（N，M0）中不存在可排空Smu。

證明 Smu可排空性使得ti∈·Smu無法使能，根據定義14，針對每個可排空Smu添加一個改進修復子網，將托肯移入修復庫所pri中，失效的不可靠資源完成修復后，tri的使能將托肯送回Smu中，最終ti∈·Smu是使能的。而未失效的資源進入共享庫所psi中，tsi回到系統中，使得托肯移入Smu中，此時Smu是不可排空的。因此，添加修復子網的標記U-S4PR（N，M0）中不存在可排空Smu。

定理3 設（N，M0）是一個標記U-S4PR，若每個可排空Smu都添加修復子網（Nri，Mri0），則（N，M0）是活的。

證明 只需證明添加修復子網的標記U-S4PR（N，M0）中，所有變遷t都是活的。通過定義14為系統所有可排空Smu添加改進修復子網，由定理2可得，標記U-S4PR（N，M0）是不存在可排空Smu的，并且也不會增添新的可排空Smu，這表明只要沒有新的資源失效，t∈T都是使能的，因此，（N，M0）是活的。

4 自適應死鎖控制策略

第3章討論了無資源故障情況，本章考慮不可靠資源發生故障情況，這使系統在高速加工過程中準確判斷死鎖與阻塞狀態。單一類型與多類型不可靠資源發生故障需要不同控制策略，因此設計兩種控制器解決局部資源阻塞狀態，并實現自適應性，通過監督器動態控制全局，確保資源故障時系統穩健性。

4.1 控制器

當不可靠資源發生資源故障時，修復子網不能夠完全控制死鎖的發生，考慮添加控制器。本節改進傳統控制器結構，為避免添加冗余控制器以及產生不必要的非法標識，設計開關控制器與復合控制器，添加觀察器實現自適應控制。該方法目標是：即使某些不可靠資源發生故障，也能確保系統的每種零件都能在其加工路徑中持續生產，確保系統穩健性。

4.1.2 開關控制器

當單一類型不可靠資源發生資源故障時，考慮為可排空Smu添加開關控制器，通過觀察器控制其激活狀態，自適應地控制死鎖，實現監督器的信息互連。下面具體定義開關控制器。

定義15 設（N，M0）是一個標記U-S4PR，ru表示單一類型不可靠資源，T=TA∪TR，TA表示活動變遷，TR表示資源變遷，關鍵變遷ti∈TA＼（P·0∪·P0）∩Smu，則ti的開關控制器是一個五元組（Nci，M0ci）=（Pci，Tci，Fci，M0ci，Vci），當且僅當：

a）Pci=Pcai∪Pcbi，其中，Pcai={p|p∈·ti}表示ti的輸入庫所集合；Pcbi={p|p∈t·i}表示ti的輸出庫所集合，添加緩沖庫所pbi和觀察庫所poi。

b）Tci=tci∪tfi，其中，tci表示托肯被移入緩沖庫所pbi進行故障修復，tfi表示托肯從緩沖庫所pbi移出，完成故障修復并回到系統中。

c）Fci={（pi，tci），（tci，pbi），（pbi，tfi），（tfi，rui），（rui，tci），（tci，poi），（poi，tci）}，其中，rui∈Pci＼PA。

d）M0ci（pi）≥0，M0ci（pbi）=0，M0ci（poi）=0。對于所有的p∈Pcai∪Pcbi，都有M0ci（p）=M0（p），M0ci（p）=M0ci（Smu）－1。

e）Vci（pbi）=Vci（poi）=Vci（pi）=V（pi），其中pi∈Pci。

根據定義15系統可以為關鍵變遷ti添加開關控制器。為保證系統能夠實時監控控制器的激活狀態，需要在觀察庫所中添加額外的弧{（poi，tai），（tsi，poi）}。其中，tai稱為激活變遷，當觀察庫所poi中至少含有一個托肯，tai是使能的，此時開關控制器保持激活狀態，并且tai與監督器相連，使得監督器能夠實時監控系統死鎖狀態。tsi稱為復原變遷，tsi的使能將托肯返回觀察庫所poi中，此時開關控制器回到未激活狀態。如圖3所示為關鍵變遷t6添加的開關控制器。

例5 在U-S4PR中r2存在單一類型不可靠資源，且資源故障時p6陷入阻塞狀態。此時需要為關鍵變遷t6添加開關控制器。添加tc6使失效的托肯在pb6中修復，完成修復回到r2中， p6中資源保持穩健加工。利用激活變遷ta6實現動態監督，當pb6需要修復資源時，激活ta6，控制局部資源分配狀態。

定義16 設（N，M0）是一個標記U-S4PR，若（N，M0）存在多個開關控制器，則稱該網為控制網，記作（NC，M0C）=（NCi，M0Ci）（N，M0）。

定理4 設（N，M0）是一個標記U-S4PR，若關鍵變遷ti∈TA＼（P·0∪·P0）∩Smu，為每個ti添加開關控制器得到控制網（NC，M0C），則（NC，M0C）中可達標記保留原始網（N，M0）中所有可達標記。

證明 由定義15可得，對于所有的p∈Pcai∪Pcbi，都有M0ci（p）=M0（p），同時，控制網（NC，M0C）在原始網的結構中添加了控制器結構，所以p∈P＼Pci，M0ci（p）=M0（p）。因此，原始網中所有的可達標記在控制網中也是可達的。

4.1.3 復合控制器

當不可靠資源存在多種類型時，資源分配方案更加復雜。例如，某一類型的資源被其他庫所占用時，該庫所占用的其他資源也無法釋放，此時，系統陷入循環等待狀態。由于資源類型的限制，與單一類型不可靠資源的系統停滯相比，該系統停滯的時間增長，可達標記減少。只考慮單一類型不可靠資源時，開關控制器可以有效地解決故障資源的修復和資源循環等待現象，但開關控制器在修復過程中無法判斷資源的種類，因此，本文設計復合控制器控制系統死鎖。

定義17 設（N，M0）是一個標記U-S4PR，ru表第i類不可靠資源，T=TA∪TR，TA表示活動變遷，TR表示資源變遷，關鍵變遷ti∈TA＼（P·0∪·P0）∩Smu，則ti的復合控制器是一個五元組（Ncpi，M0cpi）=（Pcpi，Tcpi，Fcpi，M0cip，Vcpi），當且僅當：

a）Pcpi=Pcpai∪Pcpbi∪PuR，Pcpai={p|p∈·ti}表示變遷ti的輸入庫所集合；Pcpbi={p|p∈t·i}表示變遷ti的輸出庫所集合，rui∈PuR，添加緩沖庫所pbi和觀察庫所poi。

b） Tcpi=tcpi∪tfpi∪tui，tcpi的使能推動托肯進入緩沖庫所pbi進行故障修復，tfpi的使能將托肯從緩沖庫所pbi中移出，完成故障修復，tui表示多類型不可靠資源的分類。

c）Fcpi={（tcpi，pbi），（pbi，tfpi），（tfpi，rui），（rui，tcpi），（tcpi，poi），（poi，tcpi）（rui，tui）}，其中rui∈PuR，tui與各不可靠資源相連。

d）M0cpi（pi）≥0，M0cpi（pbi）=0，M0cpi（poi）=0。對于所有的庫所p∈Pcpai∪Pcpbi∪PuR，都滿足M0cpi（p）=M0（p），M0cpi（p）=M0cpi（Smu）－1。

e）Vcpi（pbi）=Vcpi（poi）=Vcpi（pi）=V（pi），Vcpi（rui）=V（ru）其中pi∈pcpi，rui∈PuR。

根據定義17，系統可以為關鍵變遷ti添加相應的復合控制器。與開關控制器類似，為保證系統的自適應性，復合控制器也需要在觀察庫所種添加額外的弧{（poi，tpai），（tpsi，poi）}。tpai稱為激活變遷，tpai的使能表示復合控制器的激活狀態；tpsi稱為復原變遷，tpsi的使能表示復合控制器恢復到未激活狀態。如圖4所示，為t10添加復合控制器。

定義18 設（N，M0）是一個標記U-S4PR，若（N，M0）中存在多個開關控制器和復合控制器，則稱該網為復合控制網，記作（NCP，M0CP）=（NC，M0C）（Ncpi，M0cpi）。

定理5 設（N，M0）是一個標記U-S4PR，如果關鍵變遷ti∈TA＼（P·0∪·P0）∩Smu，為每個ti添加開關控制器和復合控制器得到復合控制網（NCP，M0CP），則（NCP，M0CP）中可達標記保留原始網（N，M0）中所有可達標記。

證明 復合控制網（NCP，M0CP）是在控制網基礎上添加了復合控制器，根據定理4可知（NC，M0C）中可達標記保留著原始網（N，M0）中所有可達標記，所以p∈P＼Pcpi，M0cpi（p）=M0（p）。由定義17可得，對于所有p∈Pcpai∪Pcpbi∪PuR，都有M0cpi（p）=M0（p）。因此復合控制網保留原始網所有可達標記。

例6 r6存儲多類型不可靠資源，其中發生資源故障時，p10陷入資源阻塞狀態，此時需要為關鍵變遷t10添加復合控制器。tcp10引導故障資源進入pb10修復，完成修復回到r6。與開關控制器不同的是，未失效的多類型資源可以通過tu10進行分類，保持加工狀態，確保系統穩健。

4.2 監督器

定義19 設（N，M0）是一個標記U-S4PR，Smu為可排空資源SMS，T=TA∪TR，TA表示活動變遷，TR表示資源變遷。令SmuR=S∩PR，表示Smu的資源庫所集合，令SmuA=S＼SmuR，表示Smu的活動庫所集合。

定義20 設（N，M0）是一個標記U-S4PR，Smu為可排空資源SMS。對于資源庫所r∈SmuR，若|λ（r）|gt;1，則稱（NSP，M0SP）復合監督器，記作（NSP，M0SP）=ti∈λ（r）（NC，M0C）∪（NCP，M0CP）；若|λ（r）|≤1，記作（NSP，M0SP）=（NC，M0C）∪（NCP，M0CP）。其中，λ（r）={ti|ti∈p·∩TA，p∈H（r）＼Smu}，表示為每個活動變遷分配資源庫所。

定義21 設（NSP，M0SP）是復合監督器，如果在標記M∈R（NSP，M0SP）處，（NSP，M0SP）中每個開關控制器或復合控制器都保持激活狀態，則稱（NSP，M0SP）在標記M處是激活狀態，否則（NSP，M0SP）是未激活狀態。

根據定義21可知，如果復合監督器是激活狀態，說明該標記下復合監督器中所有控制器都是激活狀態，換句話說，如果復合監督器在可達標記處激活，其每個控制器中的觀察庫所都至少存在一個托肯。

在U-S4PR（N，M0）中允許存在多個（NSP，M0SP），組成U-S4PR可控網系統（圖5），記作（NACP，M0ACP）。

定理6 設（N，M0）是一個標記U-S4PR，（NSP，M0SP）是復合監督器，若多個（NSP，M0SP）組成可控網（NACP，M0ACP），則（NACP，M0ACP）是活的。

證明 該方法將死鎖控制分為兩種獨立情況，一種是無資源故障，由定理3可得，為可排空Smu添加修復子網的標記U-S4PR（N，M0）是活的。另一種是發生資源故障時，為每個可排空Smu添加控制器，當觀察庫所poi中有至少一個托肯時，控制器開啟激活狀態，此時，緩沖庫所pbi能夠進行資源故障修復，保證系統中無可排空Smu，即可保證系統活性。因此，最終得到的可控網（NACP，M0ACP）是活的。

推論3 設（NSP，M0SP）是復合監督器，若（NSP，M0SP）保持激活狀態，則所有活動變遷TA都是活的。

算法2 自適應死鎖算法

輸入：一個U-S4PR（N，M0）。

輸出：一個可控網（NACP，M0ACP）。

a）Π={Smui|Smui∈S}。 /*Π1表示不發生資源故障時Smu集合，Π2表示發生資源故障時Smu集合*/

b） Π=Π∪αG。//αG由算法1可得

c）Δ=Δ1∪Δ2。/*Δ1表示開關控制器集合，Δ2表示復合控制器集合*/

d）for （i=0;ilt;tol;i++）

if （Smui∈Π1）

為每個Smu添加修復子網//根據定義14

else if （Smui∈Π2）

if （|r∈·tui|≤1）

為標記Smu添加一個開關控制器Cci存儲激活狀態

Δ1=Δ1∪Cci

else為標記Smu添加一個復合控制器Csi存儲激活狀態

Δ2=Δ2∪Csi

e）添加監督器（NSP，M0SP）。//根據定義20

f）while （監督器（NSP，M0SP）保持激活狀態） do

輸出可控網（NACP，M0ACP）

5 實驗與分析

本章將提出自適應死鎖策略進行仿真實驗，并與其他相關文獻對比，驗證其有效性。

5.1 仿真實驗

CNP tools仿真工具利用Petri網模擬AMS實際加工生產過程，本文使用CNP tools對圖1中U-S4PR模型進行仿真實驗。

U-S4PR中，r2、r5和r6是不可靠資源庫所，共有三個Smu：Smu1={r1，r3，r4，p5，p10，p13}，Smu2={r5，r6，p7，p9}，Smu3={r2，r4，r5，，r6，，p5，p9}。由算法1得到Smu1和Smu3為可排空Smu。系統無資源故障時，定義14為關鍵庫所p5、p7、p9、p10添加修復子網。以p9為例，圖2表示p9的修復子網，由于Smu3是可排空Smu，t10無法使能。添加修復子網后，r5中不可靠資源移入修復庫所pr9，tr9使能，使得p9存在至少一個托肯，所以t10使能。p5修復子網的添加同理，此時Smu3成為不可空Smu。該狀態下可達標識為48個。

當存在資源故障時，不考慮多類型不可靠資源條件，根據改進MIP方法計算可得Smu1和Smu3為可排空Smu，并且r2是不可靠資源，此時t7無法使能，定義15為關鍵變遷t6添加開關控制器。p6的托肯移入緩沖庫pb6所進行故障資源修復，不可靠資源完成修復后返回資源庫所。為了保證控制器的自適應性，tc6的使能確保觀察庫所po6中含有至少一個托肯，并觸發激活變遷ta6，使得該開關控制器保持激活狀態，與其相連的監督器可接收激活信息。該狀態下系統含有87個可達標記。

當系統發生資源故障時，考慮多類型不可靠資源條件，由于系統中只有r6含有多類型不可靠資源，由算法1得可排空Smu：Smu1和Smu3。定義17為關鍵變遷t10添加復合控制器。p10與r6中不可靠資源移入緩沖庫所pb10，故障資源完成修復后回到資源庫所r6，tu10使能，進行不可靠資源不同種類劃分，以便后續需要不同種類不可靠資源的零件進行加工生產。為了保證復合控制器的自適應性，當且僅當觀察庫所po10中至少含有一個托肯，激活變遷tpa10使能，確保復合控制器保持激活狀態。此時狀態下系統含有68個可達標記。

最終，U-S4PR（N，M0）經過自適應死鎖控制策略可生成穩健的監督器，共添加四個恢復子網、一個開關控制器以及一個復合控制器，在保證系統穩健性的同時，允許更多可達標記。為避免冗余控制器的生成，最終無法實現最大行為許可性。表1表示所添加控制器。

5.2 對比分析

本節將本文策略進行性能分析與相關工作對比。設U-S4PR模型中庫所數為m，變遷數為n，資源庫所數為w（w≤m），弧的條數為l。文獻[7]中傳統枚舉法最多計算得到2n個極小虹吸（包含冗余虹吸），最壞時間復雜度為O（nλ2n）。而本文策略只需計算Smu，最多得到wn個虹吸，最壞時間復雜度為O（λwn2），算法2中包含迭代過程，因此最終最壞時間復雜度為O（λn+λwn2），得到分布式時間復雜度，有效降低時間復雜度。在實際生產中的時間復雜度會更小，因為在添加控制器之前，修復子網迅速減小極小虹吸數量。新的控制器的生成導致系統空間復雜度增加。由于該策略主要應用于零件種類繁雜、生產要求多樣、加工成本高的制造環境，在初始生產規模較大的系統中，控制器的添加對整體空間復雜度變化影響較小，而時間復雜度影響較大。因此該策略整體降低計算復雜度的優勢有效。

在研究內容方面，本文策略與相關文獻進行對比。如表2所示，文獻[7，11]未考慮不可靠資源對死鎖的影響，文獻[8、9，14]只考慮單一類型不可靠資源。雖然文獻[13]考慮了多類型不可靠資源，但沒有考慮資源故障的情況，而資源故障的隨機性與偶然性也是導致自動制造系統死鎖的重要因素。文獻[15]將上述兩種情況都考慮到，但采用計算最大完美變遷回路的方法標記死鎖。文獻[7]采用枚舉虹吸的傳統方法，計算效率低，空間復雜度高，并不適用于大規模自動制造系統。本文策略考慮多類型不可靠資源對死鎖的影響，改進MIP方法，避免虹吸枚舉，降低計算復雜度，為資源故障產生的死鎖設計控制器，實現自適應動態監督。

表3為本文改進MIP方法與文獻[11]中MIP方法性能對比結果。由表3可知，本文MIP方法降低運行時間和迭代次數，計算效率提升。由于多類型不可靠資源的添加，計算過程中占用變遷與庫所數增加，內存消耗增多，與計算效率成倍提升相比，空間復雜度的增加影響較小。

綜上所述，本文策略不僅在性能方面實現分布式復雜度，而且在適用性、和穩健性中都有較好效果。

6 結束語

針對多類型多數量不可靠資源，本文提出自適應死鎖控制策略。在不考慮資源故障時，改進傳統MIP方法，證明可排空資源Smu表征U-S4PR死鎖結構，這對確保系統活性具有重要意義。考慮多類型不可靠資源故障時，為死鎖設計新的控制器，實現動態監督，提高死鎖控制的高效性與自適應性。本文提出的自適應死鎖控制策略能夠允許更多可達標記，確保系統穩健性。該策略主要考慮可控可觀死鎖因素，在未來研究中添加不可控不可觀事件，優化控制器結構，實現最大行為許可性。

參考文獻：

[1]Du Nan， Hu Hesuan， Zhou Mengchu. Robust deadlock avoidance and control of automated manufacturing systems with assembly operations using Petri nets [J]. IEEE Trans on Automation Science and Engineering， 2020， 17 （4）： 1961-1975.

[2]Luo Jianchao， Liu Zhiqiang， Wang Shougang，et al.Robust deadlock avoidance policy for automated manufacturing system with multiple unreliable resources [J]. IEEE/CAA Journal of Automatica Sinica， 2020， 7 （3）： 812-821.

[3]Fan Xing， Hu Hesuan， Yang Benyuan，et al.Event circuit structures for deadlock avoidance in flexible manufacturing systems [J]. IEEE Trans on Automation Science and Engineering， 2023， 20 （1）： 597-610.

[4]Wang Xiaojun， Hu Hesuan. A robust control approach to automated manufacturing systems allowing multitype and multiquantity of resources with Petri nets [J]. IEEE Trans on Systems Man and Cybernetics： Systems， 2020， 50 （10）： 3499-3514.

[5]Li Zhiwu， Zhou Mengchu. Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems [J]. IEEE Trans on Systems Man and Cybernetics： Systems， 2004， 34（1）： 38-51.

[6]Hu Hesuan， Li Zhiwu， Wang Anrong. On the optimal set of elementary siphons in Petri nets for deadlock control in FMS [C]// Proc of IEEE International Conference on Networking， Sensing and Control.Piscataway，NJ：IEEE Press， 2006： 244-247.

[7]Ezpeleta J， Colom J M， Martinez J. A Petri net based deadlock prevention policy for flexible manufacturing systems [J]. IEEE Trans on Robotics and Automation， 1995， 11（2）： 173-184.

[8]Zhang Ziliang， Liu Gaiyun， Sun Yu. Design of robust optimization Petri Net controller for automated manufacturing systems with unreliable resources [C]// Proc of the 18th IEEE International Conference on Automation Science and Engineering.Piscataway，NJ：IEEE Press， 2022： 1640-1645.

[9]Al-Ahmari A， Kaid H， Li Zhiwu，et al.Strict minimal siphon-based colored Petri net supervisor synthesis for automated manufacturing systems with unreliable resources [J]. IEEE Access， 2020， 8： 22411-22424.

[10]Abubakar U S， Liu Gaiyun， Uzam M. Petri net-based robust supervisory control of automated manufacturing systems with multiple unreliable resources [J]. EEE Access， 2021， 9： 100264-100278.

[11]Wang Shouguang， Duo Wenli， Guo Xin，et al.Computation of an emptiable minimal siphon in a subclass of Petri nets using mixed-integer programming [J]. IEEE/CAA Journal of Automatica Sinica， 2021， 8 （1）： 219-226.

[12]Zhang Ziliang， Liu Gaiyun， Barkaoui K，et al.Adaptive deadlock control for a class of Petri nets with unreliable resources [J]. IEEE Trans on Systems Man and Cybernetics： Systems， 2022， 52 （5）： 3113-3125.

[13]Liu Huixia， Wu Weimin， Yang Hongyong. Strong controllable siphon basis-based robust deadlock control for manufacturing systems with multiple unreliable resources [J]. IEEE Access， 2020， 8： 269-277.

[14]Elsayed M S， Kafrawy P E， Wu Naiqi. Modeling and deadlock control of reconfigurable multi-unit resource systems [J]. IEEE Access， 2020， 8： 133605-133621.

[15]Liu Huixia， Feng Yanxiang， Li Junhong，et al.Robust Petri net controllers for flexible manufacturing systems with multitype and multiunit unreliable resources [J]. IEEE Trans on Systems Man and Cybernetics： Systems， 2023， 53 （3）： 1431-1444.

[16]劉偉， 薄玉娟， 杜玉越， 等. 基于邏輯Petri網的循環選擇驅動循環結構過程模型修復方法 [J]. 山東科技大學學報：自然科學版， 2023， 42 （6）： 75-84. （Liu Wei， Bo Yujuan， Du Yuyue， et al.Repair method for process model of loop-choice-driven loop structure based on logic Petri nets [J]. Journal of Shandong University of Science and Technology： Natural Science， 2023， 42 （6）： 75-84）

[17]劉偉， 史曉浩， 孫紅偉. 基于邏輯混合Petri網的混合系統建模與分析 [J]. 山東科技大學學報：自然科學版， 2021， 40 （4）： 65-75. （Liu Wei， Shi Xiaohao， Sun Hongwei. Modeling and analysis of hybrid systems based on logic hybrid Petri nets [J]. Journal of Shandong University of Science and Technology： Natural Science， 2021， 40 （4）： 65-75.）

[18]陳金棟， 劉偉， 馮新， 等. 基于邏輯工作流網的有限無死鎖組合 [J]. 山東科技大學學報：自然科學版， 2020， 39 （5）： 89-97. （Chen Jindong， Liu Wei， Feng Xin， et al.Finite deadlock-free combination based on logical workflow network [J]. Journal of Shandong University of Science and Techonology： Natural Science， 2020， 39 （5）： 89-97.）

[19]Du Nan， Hu Hesuan，Zhou Mengchu. A survey on robust deadlock control policies for automated manufacturing systems with unreliable resources [J]. IEEE Trans on Automation Science and Engineering， 2020， 17 （1）： 389-406.