More Web Proxy on the site http://driver.im/

research-article

Sequence Control of Essential Siphons for Deadlock Prevention in Petri Nets

Authors:

Weimin WuAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 12, Issue 1

Article No.: 8, Pages 1 - 22

https://doi.org/10.1145/2406336.2406344

Published: 01 January 2013 Publication History

Abstract

Deadlock prevention is crucial to the modeling of flexible manufacturing systems. In the Petri net framework, deadlock prevention is often addressed by siphon-based control (SC) policies. Recent research results show that SC methods can avoid full siphon enumeration by using mixed integer programming (MIP) to greatly increase the computational efficiency so that it can be applied in large systems in computable time. Besides, maximally permissive control solutions can be obtained by means of iterative siphon control (ISC) approaches and MIP. Then the remaining problems are redundancy and MIP iterations. Redundant controllers make the closed-loop system more complicated and each MIP iteration increases the total computational time. This article proposes a revised ISC deadlock prevention policy which can achieve better results than the other reported methods in terms of redundancy and MIP iterations while maintaining the maximal permissiveness. Several benchmark examples are provided to illustrate the proposed approach and to be compared with the other reported methods.

References

[1]

Banaszak, Z. A. and Krogh, B. H. 1990. Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows. IEEE Trans. Rob.Autom 6, 724--734.

[2]

Chao, D. Y. 2008. Technical note: Reducing MIP iterations for deadlock prevention of flexible manufacturing systems. Int. J. Adv. Manuf. Technol. 41, 3, 343--346.

[3]

Chao, D. Y. 2009. Direct minimal empty siphon computation using MIP. Int. J. Adv. Manuf. Technol. 45, 397--405.

[4]

Chu, F. and Xie, X. L. 1997. Deadlock analysis of Petri nets using siphons and mathematical programming. IEEE Trans Rob. Autom. 13, 793--804.

[5]

Ezpeleta, J., Colom, J. M., and Martinez, J. 1995. A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Trans. Rob. Autom. 11, 173--184.

[6]

Ezpeleta, J., Tricas, F., Garcia-Valles, F., and Colom, J. M. 2002. A bankers solution for deadlock avoidance in FMS with flexible routing and multiresource states. IEEE Trans. Rob. Autom. 18, 621--625.

[7]

Fanti, M. P. and Zhou, M. C. 2004. Deadlock control methods in automated manufacturing systems. IEEE Trans. Syst. Man Cybern. Part A 34, 5--22.

Digital Library

[8]

Ferrarini, L and Maroni, M. 1998. Deadlock avoidance control for manufacturing systems with capacity resources. Int. J. Adv. Manuf. Technol. 14, 729--736.

[9]

Huang, Y. S. 2006. Design of deadlock prevention supervisors using Petri nets. Int. J. Adv. Manuf. Technol. 35, 349--362.

[10]

Huang, Y. S., Jeng, M. D., Xie, X. L., and Chung, S. L. 2001. Deadlock prevention policy based on Petri nets and siphons. Int. J. Prod. Res. 39, 283--305.

[11]

Huang, Y. S., Jeng, M. D., Xie, X. L., and Chung, D. H. 2006. Deadlock prevention policy based on Petri nets and siphons. IEEE Trans. Syst. Man Cybern. Part A 36, 1248--1256.

Digital Library

[12]

Iordache, M., Moody, J., and Antsaklis, P. 2002. Synthesis of deadlock prevention supervisors using Petri nets. IEEE Trans. Rob. Autom. 18, 59--68.

[13]

Lawley, M., Reveliotis, S., and Ferrarini, P. 1997. Design guidelines for deadlock-handling strategies in flexible manufacturing systems. Int. J. Flex. Manuf. Syst. 9, 5--30.

[14]

Li, Z. W. and Liu, D. 2007. A correct minimal siphons extraction algorithm from a maximal unmarked siphon of a Petri net. Int. J. Prod. Res. 45, 2161--2165.

[15]

Li, Z. W. and Wei, N. 2007. Deadlock control of flexible manufacturing systems via invariant-controlled elementary siphons of Petri nets. Int. J. Adv. Manuf. Technol. 33, 24--35.

[16]

Li, Z. W. and Zhou, M. C. 2004. Elementary siphons of Petri nets and their applications to deadlock prevention in flexible manufacturing systems. IEEE Trans. Syst. Man Cybern. Part A 34, 38--51.

Digital Library

[17]

Li, Z. W. and Zhou, M. C. 2006. Two-Stage Method for Synthesizing Liveness-Enforcing Supervisors for Flexible Manufacturing Systems Using Petri Nets. IEEE Trans. Ind. Inf. 2, 313--325.

[18]

Li, Z. W., Uzam, M., and Zhou, M. C. 2004. Comments on “Deadlock prevention policy based on Petri Nets and Siphons”. Int. J. Prod. Res. 42, 5253--5254.

[19]

Li, Z. W., Hu, H. S., and Wang, A. R. 2007. Design of liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE Trans. Syst. Man Cybern. Part C 37, 517--526.

Digital Library

[20]

Li, Z. W., Zhou, M. C., and Wu, N. Q. 2008. A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems. IEEE Trans. Syst. Man Cybern. Part C 38, 173--188.

Digital Library

[21]

Lindo System, Inc. Premier optimization modeling tools. http://www.lindo.com.

[22]

Murata, T. 1989. Petri nets: Properties, analysis and applications. Proc. IEEE 77, 541--580.

[23]

Park, J. and Reveliotis, S. A. 2001. Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings. IEEE Trans. Autom. Control 46, 1572--1583.

[24]

Piroddi, L., Cordone, R., and Fumagalli, I. 2008. Selective siphon control for deadlock prevention in Petri nets. IEEE Trans. Syst. Man Cybern. Part A 38, 1337--1348.

Digital Library

[25]

Piroddi, L., Cordone, R., and Fumagalli, I. 2009. Combined siphon and marking generation for deadlock prevention in Petri nets. IEEE Trans. Syst. Man Cybern. Part A 39, 650--661.

Digital Library

[26]

Shih, Y. Y. and Chao, D. Y. 2009. Sequence of control in S3PMR. Comput. J.

Digital Library

[27]

Starke, P. H. 1992. INA: Intergrated Net Analyzer. Handbuch.

[28]

Tricas, F., Garcia-Valles, F., Colom, J. M., and Ezpeleta, J. 1998. A structural approach to the problem of deadlock prevention in processes with resources. In Proceedings of the International Workshop on Discrete Event Systems (WODES’98). 273--278.

[29]

Tricas, F., Garcia-Valles, F., Colom, J. M., and Ezpeleta, J. 2000 An iterative method for deadlock prevention in FMS. In Discrete Event Systems, Analysis and Control, G. Stremersch Ed., 139--148.

[30]

Uzam, M. 2002. An optimal deadlock prevention policy for flexible manufacturing systems using Petri net model with resources and the theory of regions. Int. J. Adv. Manuf. Technol. 19, 192--208.

[31]

Uzam, M. 2004. The use of the Petri net reduction approach for an optimal deadlock prevention policy for flexible manufacturing systems. Int. J. Adv. Manuf. Technol. 23, 204--219.

[32]

Uzam, M. and Zhou, M. C. 2006. An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems. Int. J. Prod. Res. 44, 1987--2030.

[33]

Uzam, M. and Zhou, M. C. 2007. An iterative synthesis approach to Petri net-based deadlock prevention policy for flexible manufacturing systems. IEEE Trans. Syst. Man Cybern. Part A 37, 362--371.

Digital Library

[34]

Uzam, M., Li, Z. W., and Zhou, M. C. 2007. Identification and elimination of redundant control places in Petri net based liveness enforcing supervisors of FMS. Int. J. Adv. Manuf. Technol. 35, 150--168.

[35]

Viswandham, N., Narahari, Y., and Johnson, T. L. 1990. Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models. IEEE Trans. Rob. Autom. 6, 713--723.

[36]

Wang, A. R., Li, Z. W., Jia, J. Y., and Zhou, M. C. 2009. An effiective algorithm to find elementary siphons in a class of Petri nets. IEEE Trans. Syst. Man Cybern. Part A 39, 912--923.

Digital Library

[37]

Wu, N. Q. and Zhou, M. C. 2005. Modeling and deadlock avoidance of automated manufacturing systems with multiple automated guided vehicles. IEEE Trans. Syst. Man Cybern. Part B 35, 1193--1202.

Digital Library

[38]

Wysk, R. A., Yang, N. S., and Joshi, S. 1991. Detection of deadlocks in flexible manufacturing cells. IEEE Trans. Rob. Autom. 7, 853--859.

[39]

Xing, K. Y., Hu, B. S., and Chen, H. X. 1996. Deadlock avoidance policy for Petri-net modelling of flexible manufacturing systems with shared resources. IEEE Trans. Automat. Control 41, 289--295.

[40]

Yamalidou, K., Moody, J., Lemmon, M., and Antsaklis, P. 1996. Feedback control of Petri nets based on place invariants. Automatica 32, 15--28.

Digital Library

Cited By

Sun BKloda TGarcia SGracioli GCaccamo M(2024)Minimizing cache usage with fixed-priority and earliest deadline first schedulingReal-Time Systems10.1007/s11241-024-09423-760:4(625-664)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s11241-024-09423-7
Lu WGuo SSong TLi Y(2022)Analysis of Multi-AGVs Management System and Key Issues: A ReviewComputer Modeling in Engineering & Sciences10.32604/cmes.2022.019770131:3(1197-1227)Online publication date: 2022
https://doi.org/10.32604/cmes.2022.019770
Mello BWainer G(2022)Integrating I-DEVS and schedulability methods for analyzing real-time systems constraintsSimulation10.1177/0037549722109954898:12(1143-1159)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1177/00375497221099548
Show More Cited By

Index Terms

Sequence Control of Essential Siphons for Deadlock Prevention in Petri Nets
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Software system models
        Petri nets

Recommendations

Computation of Elementary Siphons in Petri Nets For Deadlock Control

When designing liveness-enforcing Petri net supervisors, unlike other techniques, Li et al. added control places and arcs to a plant net model for its elementary siphons only, greatly reducing the structural complexity of the controlled system. Their ...
Design of a Petri Net Based Deadlock Prevention Policy Supervisor for S3PR
ISMS '15: Proceedings of the 2015 6th International Conference on Intelligent Systems, Modelling and Simulation

Siphons can be used to characterize deadlock states to solve deadlock problems in a class of Petri nets that represent models of flexible manufacturing system (FMS). This paper presents a deadlock prevention method for a class of FMS, where the unmarked ...
An iterative method for synthesizing non-blocking supervisors for a class of generalized Petri nets using mathematical programming

This paper presents a novel and computational deadlock prevention policy for a class of generalized Petri nets, namely G-systems, which allows multiple resource acquisitions and flexible routings with machining, assembly and disassembly operations. In ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 12, Issue 1

Special Issue on Modeling and Verification of Discrete Event Systems

January 2013

350 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/2406336

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 January 2013

Accepted: 01 June 2010

Received: 01 March 2010

Published in TECS Volume 12, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
284
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sun BKloda TGarcia SGracioli GCaccamo M(2024)Minimizing cache usage with fixed-priority and earliest deadline first schedulingReal-Time Systems10.1007/s11241-024-09423-760:4(625-664)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s11241-024-09423-7
Lu WGuo SSong TLi Y(2022)Analysis of Multi-AGVs Management System and Key Issues: A ReviewComputer Modeling in Engineering & Sciences10.32604/cmes.2022.019770131:3(1197-1227)Online publication date: 2022
https://doi.org/10.32604/cmes.2022.019770
Mello BWainer G(2022)Integrating I-DEVS and schedulability methods for analyzing real-time systems constraintsSimulation10.1177/0037549722109954898:12(1143-1159)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1177/00375497221099548
Huang BZhou M(2020)ReferencesSupervisory Control and Scheduling of Resource Allocation Systems10.1002/9781119619727.refs(235-252)Online publication date: 29-Jun-2020
https://doi.org/10.1002/9781119619727.refs
Huang BZhou MZhang PYang J(2018)Speedup Techniques for Multiobjective Integer Programs in Designing Optimal and Structurally Simple Supervisors of AMSIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2016.258767148:1(77-88)Online publication date: Jan-2018
https://doi.org/10.1109/TSMC.2016.2587671
Gan MWang SDing ZZhou MWu W(2018) An Improved Mixed-Integer Programming Method to Compute Emptiable Minimal Siphons in S 3 PR Nets IEEE Transactions on Control Systems Technology10.1109/TCST.2017.275498226:6(2135-2140)Online publication date: Nov-2018
https://doi.org/10.1109/TCST.2017.2754982
Li FWan JZhang PLi DZhang DZhou K(2016)Usage-Specific Semantic Integration for Cyber-Physical Robot SystemsACM Transactions on Embedded Computing Systems10.1145/287305715:3(1-20)Online publication date: 23-May-2016
https://dl.acm.org/doi/10.1145/2873057
Dong LChi TZhu CYin J(2014)Mixed Integer Programming-Based Liveness Test for FMS with Full Routing FlexibilityJournal of Applied Mathematics10.1155/2014/3192812014(1-12)Online publication date: 2014
https://doi.org/10.1155/2014/319281
Díaz-de-Cerio UUribe JHarbour MPalencia JJan MBen Hedia BGoossens JMaiza C(2014)Adding Precedence Relations to the Response-Time Analysis of EDF Distributed Real-Time SystemsProceedings of the 22nd International Conference on Real-Time Networks and Systems10.1145/2659787.2659802(129-138)Online publication date: 8-Oct-2014
https://dl.acm.org/doi/10.1145/2659787.2659802

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents