• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      ?

      S3PR網(wǎng)的嚴(yán)格極小信標(biāo)計(jì)算方法

      2014-07-11 01:25:58吳文慧王壽光
      關(guān)鍵詞:庫所子網(wǎng)信標(biāo)

      尤 丹, 劉 苗, 吳文慧, 王壽光

      (1. 浙江工商大學(xué) 信息與電子工程學(xué)院,浙江 杭州 310018;2. 西安電子科技大學(xué) 機(jī)電工程學(xué)院,陜西 西安 710071)

      作為一個(gè)數(shù)學(xué)建模工具,Petri[1]網(wǎng)能夠描述資源共享、沖突、互斥、并發(fā)和不確定性,而且能幫助研究者發(fā)現(xiàn)系統(tǒng)潛在的死鎖,并使用相應(yīng)的控制策略來防止死鎖,因而被廣泛地應(yīng)用于柔性制造系統(tǒng)死鎖的分析與控制.在眾多Petri 模型中,S3PR 網(wǎng)[2]是學(xué)者們研究柔性制造系統(tǒng)死鎖問題時(shí)較常用的模型.目前許多學(xué)者致力于極小信標(biāo)相關(guān)理論的研究[3-8],并提出了計(jì)算極小信標(biāo)的算法,但這些算法的計(jì)算效率不高.現(xiàn)今,基于信標(biāo)的死鎖控制問題[9-10],針對(duì)普通Petri網(wǎng)比較成熟,但相對(duì)較為復(fù)雜的一般Petri網(wǎng)而言,信標(biāo)研究還處于初期階段.資源環(huán)法是目前計(jì)算S3PR 網(wǎng)嚴(yán)格極小信標(biāo)最有效的方法之一.針對(duì)S3PR 網(wǎng),文獻(xiàn)[5]提出了基于計(jì)算資源環(huán)的算法并提出環(huán)資源子集的概念以克服資源環(huán)法的不足.同時(shí),還提出環(huán)資源子集的計(jì)算算法以及環(huán)資源子集對(duì)應(yīng)的信標(biāo)是嚴(yán)格極小信標(biāo)的充分必要條件,在此基礎(chǔ)上提出一種快速計(jì)算嚴(yán)格極小信標(biāo)的算法.但是文獻(xiàn)[5]沒有分析S3PR網(wǎng)中一類特殊庫所與嚴(yán)格極小信標(biāo)的關(guān)系,筆者針對(duì)這類特殊庫所進(jìn)行研究,提出基于環(huán)資源計(jì)算嚴(yán)格極小信標(biāo)的方法.由于該方法避免環(huán)資源子集特征資源子網(wǎng)[5]強(qiáng)連通的判斷,所以與環(huán)資源子集法[5]相比,有更高的計(jì)算效率.

      1 計(jì)算嚴(yán)格極小信標(biāo)

      Peri網(wǎng)、S3PR網(wǎng)以及資源環(huán)的基本定義和相關(guān)符號(hào)說明參見文獻(xiàn)[1-2, 5].

      在這一部分,筆者針對(duì)S3PR網(wǎng)中一類特殊操作庫所和特殊資源庫所進(jìn)行定義與分析.

      在下面的討論中,用Ω來表示S3PR網(wǎng)N=(PA∪P0∪PR,T,F(xiàn))的一個(gè)資源子集,其中Ω= {r1,r2,…,rm}?PR(m≥2).

      定義1 令N=(PA∪P0∪PR,T,F(xiàn)),是一個(gè)S3PR網(wǎng),Ωi和Ωj是N的資源子集.稱Ωi和Ωj是可組合的,當(dāng)且僅當(dāng)Ωi∩Ωj≠?,Ωi?Ωj,Ωj?Ωi.對(duì)資源子集Ωi和Ωj的組合操作“°”定義如下:

      (1) 若Ωi和Ωj是可組合的,則Ωi°Ωj=Ωi∪Ωj;

      (2) 若Ωi和Ωj是不可組合的,則Ωi°Ωj=?.

      在下面的討論中,如果Ωi和Ωj是可組合的,用Ωi,j來表示Ωi°Ωj.顯然,Ωi°Ωi=?.

      定義3 稱資源子集Ω為組合環(huán)資源子集,如果?Ω1,Ω2,…,Ωn∈Θ,使得Ω=Ω1°Ω2° …°Ωn=Ω1∪Ω2∪ …∪Ωn(n≥2).用Ξ表示N中所有組合環(huán)資源子集的集合.

      由定義2和定義3得到以下定理.

      定理1 在S3PR網(wǎng)N中,?Ω∈,Ω∪(·Ω∩Ω·)從N中導(dǎo)出的子網(wǎng)是強(qiáng)連通的.

      定理2 令N=(PA∪P0∪PR,T,F(xiàn)),是一個(gè)S3PR網(wǎng),Ω= {r1,r2,…,rm}?PR(m≥2) ,是N的資源子集,則SΩ=Ω∪A(·ΩΩ·),是一個(gè)信標(biāo)[5].

      定理3SΩ是嚴(yán)格極小信標(biāo)SMS當(dāng)且僅當(dāng)Ω是環(huán)資源子集,且它的特征資源子網(wǎng)NΩ是強(qiáng)連通的[5].

      圖1 S3PR網(wǎng)(N, M0)圖2 S3PR網(wǎng)(N, M0)

      推論1 若Ω是L-S3PR網(wǎng)N的環(huán)資源子集,則SΩ=Ω∪A(·ΩΩ·) 是嚴(yán)格極小信標(biāo)SMS.

      證明 在L-S3PR中,不存在特殊操作庫所,同樣也不存在特殊資源庫所,由引理1或定理4即可得出此推論.

      圖3 一個(gè)柔性制造系統(tǒng)的Petri網(wǎng)模型

      2 實(shí)驗(yàn)結(jié)果

      下面用一個(gè)經(jīng)典的柔性制造系統(tǒng)實(shí)例[2]來說明通過特殊庫所判斷嚴(yán)格極小信標(biāo)的應(yīng)用.圖3為該柔性制造系統(tǒng)的S3PR網(wǎng)模型.

      圖3的簡單環(huán)資源子集如表1所示,組合環(huán)資源子集如表2所示.圖3共有25個(gè)環(huán)資源子集,這些環(huán)資源子集對(duì)應(yīng)25個(gè)信標(biāo),但其中有些信標(biāo)可能不是嚴(yán)格極小的.下面通過定理4~6來判斷信標(biāo)是否為嚴(yán)格極小信標(biāo).

      表1 圖3中的簡單環(huán)資源子集

      根據(jù)定義6~8,可知圖3中操作庫所p6是特殊操作庫所,資源庫所p20是特殊資源庫所,資源庫所p23、p25是特殊資源庫所p20的特殊輸入資源庫所.

      根據(jù)定理4可得,簡單環(huán)資源子集Ω2,Ω4,Ω5,Ω6和組合環(huán)資源子集Ω2,4,Ω2,5,Ω4,5,Ω5,6,Ω2,4,5,Ω2,5,6,Ω4,5,6,Ω2,4,5,6所形成的信標(biāo)中不包含任何特殊資源庫所p20,則這些環(huán)資源子集一定可以形成嚴(yán)格極小信標(biāo)SMS.

      根據(jù)定理5可得,簡單環(huán)資源子集Ω3和組合環(huán)資源子集Ω3,4,Ω3,5,Ω3,4,5,Ω3,5,6,Ω3,4,5,6所形成的信標(biāo)中包含所有特殊輸入資源庫所p23和p25,則這些環(huán)資源子集一定可以形成嚴(yán)格極小信標(biāo)SMS.

      根據(jù)定理6可得,簡單環(huán)資源子集Ω1和組合環(huán)資源子集Ω1,2,Ω1,2,4,Ω1,2,5,Ω1,2,4,5,Ω1,2,5,6,Ω1,2,4,5,6所形成的信標(biāo)中包含一個(gè)特殊輸入資源庫所p23或p25,則這些環(huán)資源子集一定不可以形成嚴(yán)格極小信標(biāo)SMS.

      綜上所述,可求出圖3所有的嚴(yán)格極小信標(biāo),共18個(gè).

      表2 圖3中的組合環(huán)資源子集

      3 結(jié) 束 語

      對(duì)于S3PR網(wǎng),筆者首先定義了特殊操作庫所和特殊資源庫所,通過對(duì)其分析,提出通過特殊庫所判定信標(biāo)是否為嚴(yán)格極小信標(biāo)的判定定理,基于判定定理有效求解出嚴(yán)格極小信標(biāo).實(shí)驗(yàn)結(jié)果表明,采用筆者所提出的方法,可以快速地計(jì)算出S3PR網(wǎng)中的嚴(yán)格極小信標(biāo).與文獻(xiàn)[5]提出的方法相比,筆者提出的基于特殊庫所求解嚴(yán)格極小信標(biāo)的方法避免了對(duì)環(huán)資源子集特征資源子網(wǎng)是否是強(qiáng)連通的判斷,進(jìn)而也避免了通過資源子集求其特征資源子網(wǎng).因此筆者提出的方法將提高計(jì)算效率.由于該方法只適用于一類S3PR網(wǎng),把該方法應(yīng)用到更大類型網(wǎng)將是以后研究的方向.

      [1] Murata T. Petri Nets: Properties, Analysis, and Applications[J]. Proceeding of the IEEE, 1989, 77(4): 541-580.

      [2] Ezpeleta J, Colom J M, Martinez J. A Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems[J]. IEEE Transactions on Robotics and Automation, 1995, 11(2): 173-184.

      [3] 王安榮, 李志武. 基本信標(biāo)計(jì)算的一種快速算法[J]. 西安電子科技大學(xué)學(xué)報(bào), 2008, 35(4): 632-638.

      Wang Anrong, Li Zhiwu. Effective Algorithm for Obtaining a Set of Elementary Siphons[J]. Journal of Xidian University, 2008, 35(4): 632-638.

      [4] Wang Shouguang, Zhou Mengchu, Wang Chengying. Extracting All Minimal Siphons from Maximal Unmarked Siphons in Manufacturing-oriented Petri Nets [C]//IEEE International Conference on Automation Science and Engineering. Piscataway: IEEE, 2011: 399-404.

      [5] Wang Shouguang, Wang Chengying, Zhou Mengchu. A Method to Compute Strict Minimal Siphons in S3PR Based on Loop Resource Subsets [J]. IEEE Transactions on Systems, Man, and Cybernetics Systems, 2012, 42(1): 226-237.

      [6] Wang Shouguang, Li Yue, Wang Chengying, et al. Computation of All Minimal Siphons in Petri Nets[C]//Proceedings of 9th IEEE Conference on Networking, Sensing and Control. Piscataway: IEEE, 2012: 4651

      [7] Liu Xiangling, Wang Anrong, Li Zhiwu. A Fast Algorithm to Find a Set of Elementary Siphons for a Class of Petri Nets[C]//Proceedings of IEEE International Conference on Automation Science and Engineering. Piscataway: IEEE, 2006: 399-404.

      [8] Xing Keyi, Zhou Mengchu, Wang Feng, et al. Resource Transition Circuits and Siphons for Deadlock Control of Automated Manufacturing Systems[J]. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans, 2011, 41(1): 74-84.

      [9] Li Zhiwu, Zhou Mengchu. Control of Elementary and Dependent Siphons in Petri Nets and Their Application[J]. IEEE Transactions on System, Man, and Cybernetics Part A: Systems and Humans, 2008, 38(1): 133-148.

      [10] Li Zhiwu, Zhao Mi. On Controllability of Dependent Siphons for Deadlock Prevention in Generalized Petri Nets [J]. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans, 2008, 38(2): 369-384.

      猜你喜歡
      庫所子網(wǎng)信標(biāo)
      一種簡單子網(wǎng)劃分方法及教學(xué)案例*
      基于FPGA 的有色Petri 網(wǎng)仿真系統(tǒng)設(shè)計(jì)*
      電子器件(2021年1期)2021-03-23 09:24:02
      子網(wǎng)劃分問題研究及應(yīng)用
      RFID電子信標(biāo)在車-地聯(lián)動(dòng)控制系統(tǒng)中的應(yīng)用
      子網(wǎng)劃分的簡易方法
      基于信標(biāo)的多Agent系統(tǒng)的移動(dòng)位置研究
      無姿態(tài)補(bǔ)償?shù)乃滦艠?biāo)絕對(duì)位置傳遞研究
      水道港口(2015年1期)2015-02-06 01:25:45
      利用Petri網(wǎng)特征結(jié)構(gòu)的故障診斷方法
      一種遞歸π演算向Petri網(wǎng)的轉(zhuǎn)換方法
      基于安全協(xié)議的虛擬專用子網(wǎng)研究
      河南科技(2014年16期)2014-02-27 14:13:04
      文安县| 平乐县| 山西省| 七台河市| 东光县| 明光市| 平昌县| 民勤县| 绥棱县| 晋城| 盈江县| 福海县| 安新县| 响水县| 玉门市| 响水县| 拉孜县| 咸阳市| 双鸭山市| 定南县| 静安区| 临洮县| 仁化县| 遵义市| 贵定县| 凭祥市| 成安县| 泰顺县| 新化县| 新平| 资中县| 铜川市| 开封市| 东方市| 连江县| 铜梁县| 宜阳县| 三台县| 沙雅县| 托克逊县| 万年县|