Deadlock Prevention Policy with Behavioral Optimality or Suboptimality Achieved by the Redundancy Identification of Constraints and the Rearrangement of Monitors
This work develops an iterative deadlock prevention method for a special class of Petri nets that can well model a variety of flexible manufacturing systems. A deadlock detection technique, called mixed integer programming (MIP), is used to find a strict minimal siphon (SMS) in a plant model without...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2015-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2015/579623 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832562925966983168 |
|---|---|
| author | Liang Hong YiFan Hou JunFeng Jing AnRong Wang Dmitry A. Litvin |
| author_facet | Liang Hong YiFan Hou JunFeng Jing AnRong Wang Dmitry A. Litvin |
| author_sort | Liang Hong |
| collection | DOAJ |
| description | This work develops an iterative deadlock prevention method for a special class of Petri nets that can well model a variety of flexible manufacturing systems. A deadlock detection technique, called mixed integer programming (MIP), is used to find a strict minimal siphon (SMS) in a plant model without a complete enumeration of siphons. The policy consists of two phases. At the first phase, SMSs are obtained by MIP technique iteratively and monitors are added to the complementary sets of the SMSs. For the possible existence of new siphons generated after the first phase, we add monitors with their output arcs first pointed to source transitions at the second phase to avoid new siphons generating and then rearrange the output arcs step by step on condition that liveness is preserved. In addition, an algorithm is proposed to remove the redundant constraints of the MIP problem in this paper. The policy improves the behavioral permissiveness of the resulting net and greatly enhances the structural simplicity of the supervisor. Theoretical analysis and experimental results verify the effectiveness of the proposed method. |
| format | Article |
| id | doaj-art-112bc1ef436b4975ad7981f5e662435b |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2015-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-112bc1ef436b4975ad7981f5e662435b2025-02-03T01:21:21ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2015-01-01201510.1155/2015/579623579623Deadlock Prevention Policy with Behavioral Optimality or Suboptimality Achieved by the Redundancy Identification of Constraints and the Rearrangement of MonitorsLiang Hong0YiFan Hou1JunFeng Jing2AnRong Wang3Dmitry A. Litvin4College of Electronics and Information, Xi’an Polytechnic University, No. 19 South Jinhua Road, Xi’an 710048, ChinaSchool of Electro-Mechanical Engineering, Xidian University, No. 2 South Taibai Road, Xi’an 710071, ChinaCollege of Electronics and Information, Xi’an Polytechnic University, No. 19 South Jinhua Road, Xi’an 710048, ChinaSchool of Electro-Mechanical Engineering, Xidian University, No. 2 South Taibai Road, Xi’an 710071, ChinaFaculty of Telecommunication Networks, Odessa National Academy of Telecommunications Named after A.S. Popov, Koval’ska Street 1, Odessa 65029, UkraineThis work develops an iterative deadlock prevention method for a special class of Petri nets that can well model a variety of flexible manufacturing systems. A deadlock detection technique, called mixed integer programming (MIP), is used to find a strict minimal siphon (SMS) in a plant model without a complete enumeration of siphons. The policy consists of two phases. At the first phase, SMSs are obtained by MIP technique iteratively and monitors are added to the complementary sets of the SMSs. For the possible existence of new siphons generated after the first phase, we add monitors with their output arcs first pointed to source transitions at the second phase to avoid new siphons generating and then rearrange the output arcs step by step on condition that liveness is preserved. In addition, an algorithm is proposed to remove the redundant constraints of the MIP problem in this paper. The policy improves the behavioral permissiveness of the resulting net and greatly enhances the structural simplicity of the supervisor. Theoretical analysis and experimental results verify the effectiveness of the proposed method.http://dx.doi.org/10.1155/2015/579623 |
| spellingShingle | Liang Hong YiFan Hou JunFeng Jing AnRong Wang Dmitry A. Litvin Deadlock Prevention Policy with Behavioral Optimality or Suboptimality Achieved by the Redundancy Identification of Constraints and the Rearrangement of Monitors Discrete Dynamics in Nature and Society |
| title | Deadlock Prevention Policy with Behavioral Optimality or Suboptimality Achieved by the Redundancy Identification of Constraints and the Rearrangement of Monitors |
| title_full | Deadlock Prevention Policy with Behavioral Optimality or Suboptimality Achieved by the Redundancy Identification of Constraints and the Rearrangement of Monitors |
| title_fullStr | Deadlock Prevention Policy with Behavioral Optimality or Suboptimality Achieved by the Redundancy Identification of Constraints and the Rearrangement of Monitors |
| title_full_unstemmed | Deadlock Prevention Policy with Behavioral Optimality or Suboptimality Achieved by the Redundancy Identification of Constraints and the Rearrangement of Monitors |
| title_short | Deadlock Prevention Policy with Behavioral Optimality or Suboptimality Achieved by the Redundancy Identification of Constraints and the Rearrangement of Monitors |
| title_sort | deadlock prevention policy with behavioral optimality or suboptimality achieved by the redundancy identification of constraints and the rearrangement of monitors |
| url | http://dx.doi.org/10.1155/2015/579623 |
| work_keys_str_mv | AT lianghong deadlockpreventionpolicywithbehavioraloptimalityorsuboptimalityachievedbytheredundancyidentificationofconstraintsandtherearrangementofmonitors AT yifanhou deadlockpreventionpolicywithbehavioraloptimalityorsuboptimalityachievedbytheredundancyidentificationofconstraintsandtherearrangementofmonitors AT junfengjing deadlockpreventionpolicywithbehavioraloptimalityorsuboptimalityachievedbytheredundancyidentificationofconstraintsandtherearrangementofmonitors AT anrongwang deadlockpreventionpolicywithbehavioraloptimalityorsuboptimalityachievedbytheredundancyidentificationofconstraintsandtherearrangementofmonitors AT dmitryalitvin deadlockpreventionpolicywithbehavioraloptimalityorsuboptimalityachievedbytheredundancyidentificationofconstraintsandtherearrangementofmonitors |