Journal of Guangdong University of Technology ›› 2019, Vol. 36 ›› Issue (04): 1-9.doi: 10.12052/gdutxb.190038

    Next Articles

Maximally Permissive Supervisor Design Based on Reachablity and Structural Analysis of Petri Net

Chen He-feng, Wu Nai-qi   

  1. School of Electromechanical Engineering, Guangdong University of Technology, Guangzhou 510006, China
  • Received:2019-03-12 Online:2019-06-18 Published:2019-05-31

HTML

PDF (PC)

2739

Abstract: Automated manufacturing systems belonging to resource allocation are prone to deadlock during operation. Controllers need to be designed for automated manufacturing systems to avoid deadlocks. Further, the controlled system should have the maximal permissive behavior. For ease of implementation, the controllers are typically expressed in a comprehensive manner by linear constraints. In the existing work, based on the reachability analysis, the markings to be forbidden are reduced to a small set, and only a few reachable illegal markings are included. Then, construct a mixed integer linear programming problem for each marking and solve it. This strategy is computationally expensive due to the inherent NP-hard feature of integer programming. This paper studies the design of the prevention controllers for deadlocks. On the basis of the reachable graph analysis, combined with the structural characteristics of the identified markings, the illegal marking recognition is classified, the algebraic condition is established, and the linear constraint is constructed to ensure the maximal permissiveness of the behavior. Furthermore, the polynomial algorithm is designed such that the computational complexity is significantly reduced. For some specific Petri net, structural analysis is used to obtain the maximally permissively controlled system. In addition, for those markings that could not be processed via the structural analysis, a linear programming solution was proposed. The results show that, for the Petri net subclass considered, the problem of solving mixed integer linear programming is avoided. This scheme has obvious advantages in sense of computational complexity. Finally, the effectiveness of the method is verified by two examples.

Key words: automated manufacturing system, Petri net, deadlock prevention, maximal permissiveness

CLC Number: 

  • TP301
[1] LI Z W, WU N Q, ZHOU M C. Deadlock control of automated manufacturing systems based on Petri nets-A literature review[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, 2012, 42(4):437-462
[2] EVELIOTIS S A. Real-time management of resource allocation system:A disceret event systems appproach[M]. New York:Springer, 2006.
[3] WU N Q, ZHOU M C, LI Z W. Resource-oriented Petri net for deadlock avoidance in flexible assembly systems[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A:Systems and Humans, 2008, 38(1):56-69
[4] WU N Q. System modeling and control with resource-oriented Petri nets[M]. CRC Press, Taylor & Francis Group, 2009.
[5] 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
[6] LI Z W, ZHOU M C. Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 2004, 34(1):38-51
[7] CHEN H F, WW N Q, LI Z W, et al. On a maximally permissive deadlock prevention policy for automated manufacturing systems by using resource-oriented Petri nets[J]. ISA Transactions, in press, 2018
[8] CHEN H F, WU N Q, ZHOU M C. A novel method for deadlock prevention of AMS by using resource-oriented Petri nets[J]. Information Sciences, 2016, 363:178-189
[9] CHEN H F, WU N Q, LI Z W, et al. Liveness of disjunctive and strict single-type automated manufacturing system:An ROPN approach[J]. IEEE Access, 2019, 7:17760-17771
[10] NAZEEM A, REVELIOTIS S, WANG Y, et al. Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory:the linear case[J]. IEEE Transactions on Automatic Control, 2011, 56(8):1818-1833
[11] REVELIOTIS S, NAZEEM, A. Deadlock avoidance policies for automated manufacturing systems using finite state automata. in Formal Methods in Manufacturing[M], CRC Press/Taylor & Francis, 2014.
[12] CHEN Y F, LI Z W, KHALIGUI M, et al. Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems[J]. Automatica, 2011, 47(5):1028-1034
[13] CHEN H F, WU N Q, ZHOU M C. Resource-oriented Petri net-based approach to deadlock prevention of AMSs[C]//In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, HongKong:IEEE, 2015.
[14] LAWLEY M, REVELIOTIS S. Deadlock avoidance for sequential resource allocation systems:Hard and easy cases[J]. International Journal of Flexible Manufacturing Systems, 2001, 13(4):385-404
[15] BARKAOUI K, ABDALLAH I B. A deadlock prevention method for a class of FMS[J]. IEEE International Conference on Systems, Man and Cybernetics, 1995, 5:4119-4124
[16] REVELIOTIS S, LAWLEY M, FERREIRA P. Structural control of large-scale flexibly automated manufacturing systems[M]//Cornelius T L. Computer-aided design, engineering and manufacturing. Boca Raton:CRC Press, 2000.
[17] NAZEEM A, REVELIOTIS S. Optimal linear separation of the safe and unsafe subspaces of sequential resource allocation systems as a set-covering problem:Algorithmic procedures and geometric insights[J]. Siam Journal on Control and Optimization, 2013, 51(2):1707-1726
[18] NAZEEM A, REVELIOTIS S. Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory:The nonlinear case[J]. IEEE Transactions on Automatic Control, 2012, 57(7):1670-1684
[19] 石聪聪, 刘富春. 模糊离散事件系统基于模式的故障诊断[J]. 广东工业大学学报, 2019, 36(1):35-41 SHI C C, LIU F C. A pattern-based failure diagnosis of fuzzy discrete-event systems[J]. Journal of Guangdong University of Technology, 2019, 36(1):35-41
[20] 叶彬彬, 刘富春. 随机离散事件系统的故障预测[J]. 广东工业大学学报, 2018, 35(6):83-89 YE B B, LIU F C. Failure predictability of stochastic discrete event systems[J]. Journal of Guangdong University of Technology, 2018, 35(6):83-89
[21] MURATA T. Petri nets:Properties, analysis, and applications[J]. Proceedings of the IEEE, 1989, 77(4):541-580
[22] WU N Q, ZHOU M C. Modeling, analysis and control of dual-arm cluster tools with residency time constraint and activity time variation based on Petri nets[J]. IEEE Transactions on Automation Science and Engineering, 2012, 9(2):446-454
[23] BAI L P, WU N Q, LI Z W, et al. Optimal one-wafer cyclic scheduling and buffer space configuration for single-arm multicluster tools with linear topology[J]. IEEE Transactions on Systems Man and Cybernetics Systems, 2016, 46(10):1456-1467
[24] UZAM M. An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions[J]. International Journal of Advanced Manufacturing Technology, 2002, 19(3):192-208
[25] CHEN Y F, LI Z W. On structural minimality of optimal supervisors for flexible manufacturing systems[J]. Automatica, 2012, 48(10):2647-2656
[1] Zhang Rui, Lyu Jun. Single-channel Speech Separation Based on Separated SI-SNR Regression Estimation and Adaptive Frequency Modulation Network [J]. Journal of Guangdong University of Technology, 2023, 40(02): 45-54.
[2] Liu Dong-ning, Wang Zi-qi, Zeng Yan-jiao, Wen Fu-yan, Wang Yang. Prediction Method of Gene Methylation Sites Based on LSTM with Compound Coding Characteristics [J]. Journal of Guangdong University of Technology, 2023, 40(01): 1-9.
[3] Xu Wei-feng, Cai Shu-ting, Xiong Xiao-ming. Visual Inertial Odometry Based on Deep Features [J]. Journal of Guangdong University of Technology, 2023, 40(01): 56-60,76.
[4] Liu Dong-ning, Zheng Chu-chu. Task Allocation under Cool Down Time Constraints via the Many to Many Assignment [J]. Journal of Guangdong University of Technology, 2021, 38(05): 10-15.
[5] Zhang Wei, Tong Ru, Wu Shi-jue, Wang Zi-qi, Teng Shao-hua. Group Role Assignment Based on KD45 Closure [J]. Journal of Guangdong University of Technology, 2021, 38(04): 26-34.
[6] Lyu Shu-yuan, Liu Fu-chun, Zhao Rui, Deng Xiu-qin, Cui Hong-gang. A Research on Patterns Fault Prediction of Decentralized Discrete Event Systems [J]. Journal of Guangdong University of Technology, 2021, 38(01): 54-63.
[7] Hao Zhi-feng, Li Yi-ting, Cai Rui-chu, Zeng Yan, Qiao Jie. A Research on Users’ Shopping Behaviors in Social Network Based on Causal Model [J]. Journal of Guangdong University of Technology, 2020, 37(03): 1-8.
[8] Hong Ying-han, Hao Zhi-feng, Mai Gui-zhen, Chen Ping-hua. Learning Causal Skeleton by Using Lower Order Conditional Independent Tests [J]. Journal of Guangdong University of Technology, 2019, 36(05): 14-19.
[9] Lei Rui-sheng, Ling Bingo Wing-Kuen. A Heart Rate Variability Analysis via Modified Multi-time Scale Permutation Entropy [J]. Journal of Guangdong University of Technology, 2019, 36(03): 32-38.
[10] Shi Cong-cong, Liu Fu-chun. A Pattern-Based Failure Diagnosis of Fuzzy Discrete-Event Systems [J]. Journal of Guangdong University of Technology, 2019, 36(01): 35-41.
[11] Huang Tian-an, Cheng Liang-lun, Huang Si-meng. A Research of Fluctuation Analysis Method on Process Flow of Production Process Based on Internet of Manufacturing Things [J]. Journal of Guangdong University of Technology, 2019, 36(01): 57-62.
[12] Liu Dong-ning, Liu Tong-wu, Song Jing-jing, Hou Yan. Multiple Assignment in Task Allocation of Communication Base Stations [J]. Journal of Guangdong University of Technology, 2018, 35(06): 69-76.
[13] Ye Bin-bin, Liu Fu-chun. Failure Predictability of Stochastic Discrete Event Systems [J]. Journal of Guangdong University of Technology, 2018, 35(06): 83-89.
[14] Zheng San-qiang, Han Xiao-zhuo. A Simulation of Cellular Automata Based on the SIR Infectious Disease Model with Multifactorial Constraints [J]. Journal of Guangdong University of Technology, 2018, 35(05): 51-59.
[15] Zhou Yi-lu, Wang Zhen-you, Li Ye-zi, Li Feng. A Quadratic Scalarizing Function in MOEA/D and its Performance on Multi and Many-Objective Optimization [J]. Journal of Guangdong University of Technology, 2018, 35(04): 37-44.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © 2017 Journal of Guangdong University of Technology
Add：729 East Dongfeng RD., Guangzhou PRC. Postcode: 510090
Tel：020-37626653,020-37626139,020-37626396
Email：xbzrb@gdut.edu.cn
Supported:Beijing Magtech