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

關(guān)鍵詞：自動制造系統(tǒng)；不可靠資源；極小虹吸；自適應(yīng)死鎖控制

中圖分類號：TP311"" 文獻標(biāo)志碼：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 引言

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

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

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

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

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

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

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

3 資源嚴(yán)格極小虹吸

本章提出資源嚴(yán)格極小虹吸概念，與傳統(tǒng)嚴(yán)格極小虹吸不同，資源嚴(yán)格極小虹吸深入研討多類型多數(shù)量不可靠資源引發(fā)死鎖的原因與其對死鎖的表征結(jié)構(gòu)。改進MIP方法，使其適應(yīng)U-S4PR模型結(jié)構(gòu)，避免虹吸枚舉遍歷產(chǎn)生指數(shù)型計算復(fù)雜度，并設(shè)計修復(fù)子網(wǎng)控制死鎖。

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

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

在定義13中，當(dāng)S∩H（RSmu）≠時，S=Smu，但B［S］≠B［Smu］。也就是說，嚴(yán)格極小虹吸SMS與資源嚴(yán)格極小虹吸Smu本質(zhì)上沒有差別，但是它們的補集不同，因此，在S4PR中可以利用Smu的可空狀態(tài)表征多類型資源的死鎖結(jié)構(gòu)。

例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}。

根據(jù)定義13可知，在存在多類型多數(shù)量不可靠資源的自動制造系統(tǒng)中，可空的資源嚴(yán)格極小虹吸Smu可以表征死鎖，因此，下面將根據(jù)Smu結(jié)構(gòu)特征改進混合整數(shù)規(guī)劃算法優(yōu)化可空Smu的計算效率。

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

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

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

定理1 設(shè)（N，M0）是一個標(biāo)記U-S4PR，由改進MIP得到的一個解對應(yīng)一個可排空Smu。

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

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

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

算法1 計算可空Smu

輸入：一個Petri網(wǎng)U-S4PR（N，M0）

輸出：標(biāo)記的可空Smu集合

a）αG=，tol=0//αG存儲標(biāo)記的可空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}//計算標(biāo)記處最大托肯數(shù)

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++，并標(biāo)記可空Smu

d）輸出αG

例3 以關(guān)鍵庫所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計算得到的標(biāo)記的可排空Smu集合，本文將利用修復(fù)子網(wǎng)控制其死鎖的發(fā)生?？紤]到多類型不可靠資源的存在，將修復(fù)子網(wǎng)分為共享資源部分和普通修復(fù)子網(wǎng)部分，下面定義改進的修復(fù)子網(wǎng)。

定義14 設(shè)（N，M0）是一個標(biāo)記U-S4PR，若ru∈PuR，則修復(fù)子網(wǎng)為（Nri，Mri0）=（{pi，pri，psi，ru}，{tAi，tri，tsi}，F(xiàn)ri，Wi，Mri0，Vi），當(dāng)且僅當(dāng)：

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

b）tAi表示分支變遷，連接修復(fù)庫所或者共享庫所；tri表示修復(fù)變遷，將失效托肯移入修復(fù)庫所；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。

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

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

定理2 設(shè)（N，M0）是一個標(biāo)記U-S4PR，若每個可排空Smu都添加修復(fù)子網(wǎng)（Nri，Mri0），則（N，M0）中不存在可排空Smu。

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

定理3 設(shè)（N，M0）是一個標(biāo)記U-S4PR，若每個可排空Smu都添加修復(fù)子網(wǎng)（Nri，Mri0），則（N，M0）是活的。

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

4 自適應(yīng)死鎖控制策略

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

4.1 控制器

當(dāng)不可靠資源發(fā)生資源故障時，修復(fù)子網(wǎng)不能夠完全控制死鎖的發(fā)生，考慮添加控制器。本節(jié)改進傳統(tǒng)控制器結(jié)構(gòu)，為避免添加冗余控制器以及產(chǎn)生不必要的非法標(biāo)識，設(shè)計開關(guān)控制器與復(fù)合控制器，添加觀察器實現(xiàn)自適應(yīng)控制。該方法目標(biāo)是：即使某些不可靠資源發(fā)生故障，也能確保系統(tǒng)的每種零件都能在其加工路徑中持續(xù)生產(chǎn)，確保系統(tǒng)穩(wěn)健性。

4.1.2 開關(guān)控制器

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

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

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

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

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。

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

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

定義16 設(shè)（N，M0）是一個標(biāo)記U-S4PR，若（N，M0）存在多個開關(guān)控制器，則稱該網(wǎng)為控制網(wǎng)，記作（NC，M0C）=（NCi，M0Ci）（N，M0）。

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

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

4.1.3 復(fù)合控制器

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

定義17 設(shè)（N，M0）是一個標(biāo)記U-S4PR，ru表第i類不可靠資源，T=TA∪TR，TA表示活動變遷，TR表示資源變遷，關(guān)鍵變遷ti∈TA＼（P·0∪·P0）∩Smu，則ti的復(fù)合控制器是一個五元組（Ncpi，M0cpi）=（Pcpi，Tcpi，F(xiàn)cpi，M0cip，Vcpi），當(dāng)且僅當(dāng)：

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進行故障修復(fù)，tfpi的使能將托肯從緩沖庫所pbi中移出，完成故障修復(fù)，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。

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

定義18 設(shè)（N，M0）是一個標(biāo)記U-S4PR，若（N，M0）中存在多個開關(guān)控制器和復(fù)合控制器，則稱該網(wǎng)為復(fù)合控制網(wǎng)，記作（NCP，M0CP）=（NC，M0C）（Ncpi，M0cpi）。

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

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

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

4.2 監(jiān)督器

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

定義20 設(shè)（N，M0）是一個標(biāo)記U-S4PR，Smu為可排空資源SMS。對于資源庫所r∈SmuR，若|λ（r）|gt;1，則稱（NSP，M0SP）復(fù)合監(jiān)督器，記作（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 設(shè)（NSP，M0SP）是復(fù)合監(jiān)督器，如果在標(biāo)記M∈R（NSP，M0SP）處，（NSP，M0SP）中每個開關(guān)控制器或復(fù)合控制器都保持激活狀態(tài)，則稱（NSP，M0SP）在標(biāo)記M處是激活狀態(tài)，否則（NSP，M0SP）是未激活狀態(tài)。

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

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

定理6 設(shè)（N，M0）是一個標(biāo)記U-S4PR，（NSP，M0SP）是復(fù)合監(jiān)督器，若多個（NSP，M0SP）組成可控網(wǎng)（NACP，M0ACP），則（NACP，M0ACP）是活的。

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

推論3 設(shè)（NSP，M0SP）是復(fù)合監(jiān)督器，若（NSP，M0SP）保持激活狀態(tài)，則所有活動變遷TA都是活的。

算法2 自適應(yīng)死鎖算法

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

輸出：一個可控網(wǎng)（NACP，M0ACP）。

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

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

c）Δ=Δ1∪Δ2。/*Δ1表示開關(guān)控制器集合，Δ2表示復(fù)合控制器集合*/

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

if （Smui∈Π1）

為每個Smu添加修復(fù)子網(wǎng)//根據(jù)定義14

else if （Smui∈Π2）

if （|r∈·tui|≤1）

為標(biāo)記Smu添加一個開關(guān)控制器Cci存儲激活狀態(tài)

Δ1=Δ1∪Cci

else為標(biāo)記Smu添加一個復(fù)合控制器Csi存儲激活狀態(tài)

Δ2=Δ2∪Csi

e）添加監(jiān)督器（NSP，M0SP）。//根據(jù)定義20

f）while （監(jiān)督器（NSP，M0SP）保持激活狀態(tài)） do

輸出可控網(wǎng)（NACP，M0ACP）

5 實驗與分析

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

5.1 仿真實驗

CNP tools仿真工具利用Petri網(wǎng)模擬AMS實際加工生產(chǎn)過程，本文使用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。系統(tǒng)無資源故障時，定義14為關(guān)鍵庫所p5、p7、p9、p10添加修復(fù)子網(wǎng)。以p9為例，圖2表示p9的修復(fù)子網(wǎng)，由于Smu3是可排空Smu，t10無法使能。添加修復(fù)子網(wǎng)后，r5中不可靠資源移入修復(fù)庫所pr9，tr9使能，使得p9存在至少一個托肯，所以t10使能。p5修復(fù)子網(wǎng)的添加同理，此時Smu3成為不可空Smu。該狀態(tài)下可達標(biāo)識為48個。

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

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

最終，U-S4PR（N，M0）經(jīng)過自適應(yīng)死鎖控制策略可生成穩(wěn)健的監(jiān)督器，共添加四個恢復(fù)子網(wǎng)、一個開關(guān)控制器以及一個復(fù)合控制器，在保證系統(tǒng)穩(wěn)健性的同時，允許更多可達標(biāo)記。為避免冗余控制器的生成，最終無法實現(xiàn)最大行為許可性。表1表示所添加控制器。

5.2 對比分析

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

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

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

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

6 結(jié)束語

針對多類型多數(shù)量不可靠資源，本文提出自適應(yīng)死鎖控制策略。在不考慮資源故障時，改進傳統(tǒng)MIP方法，證明可排空資源Smu表征U-S4PR死鎖結(jié)構(gòu)，這對確保系統(tǒng)活性具有重要意義?？紤]多類型不可靠資源故障時，為死鎖設(shè)計新的控制器，實現(xiàn)動態(tài)監(jiān)督，提高死鎖控制的高效性與自適應(yīng)性。本文提出的自適應(yīng)死鎖控制策略能夠允許更多可達標(biāo)記，確保系統(tǒng)穩(wěn)健性。該策略主要考慮可控可觀死鎖因素，在未來研究中添加不可控不可觀事件，優(yōu)化控制器結(jié)構(gòu)，實現(xiàn)最大行為許可性。

參考文獻：

[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網(wǎng)的循環(huán)選擇驅(qū)動循環(huán)結(jié)構(gòu)過程模型修復(fù)方法 [J]. 山東科技大學(xué)學(xué)報：自然科學(xué)版， 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網(wǎng)的混合系統(tǒng)建模與分析 [J]. 山東科技大學(xué)學(xué)報：自然科學(xué)版， 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]陳金棟， 劉偉， 馮新， 等. 基于邏輯工作流網(wǎng)的有限無死鎖組合 [J]. 山東科技大學(xué)學(xué)報：自然科學(xué)版， 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.