A Multistep Look-Ahead Deadlock Avoidance Policy for Automated Manufacturing Systems
For an automated manufacturing system (AMS), it is a computationally intractable problem to find a maximally permissive deadlock avoidance policy (DAP) in a general case, since the decision on the safety of a reachable state is NP-hard. This paper focuses on the deadlock avoidance problem for system...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2017-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2017/8687035 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832552339003670528 |
|---|---|
| author | Chao Gu Zhiwu Li Abdulrahman Al-Ahmari |
| author_facet | Chao Gu Zhiwu Li Abdulrahman Al-Ahmari |
| author_sort | Chao Gu |
| collection | DOAJ |
| description | For an automated manufacturing system (AMS), it is a computationally intractable problem to find a maximally permissive deadlock avoidance policy (DAP) in a general case, since the decision on the safety of a reachable state is NP-hard. This paper focuses on the deadlock avoidance problem for systems of simple sequential processes with resources (S3PR) by using Petri nets structural analysis theory. Inspired by the one-step look-ahead DAP that is an established result, which is of polynomial complexity, for an S3PR without one-unit-capacity resources shared by two or more resource-transition circuits (in the Petri net model) that do not include each other, this research explores a multiple-step look-ahead deadlock avoidance policy for a system modeled with an S3PR that contains a shared one-unit-capacity resource in resource-transition circuits. It is shown that the development of an optimal DAP for the considered class of Petri nets is also of polynomial complexity. It is indicated that the steps needed to look ahead in a DAP depend on the structure of the net model. A number of examples are used to illustrate the proposed method. |
| format | Article |
| id | doaj-art-0a8005156afe45faba5d8321eb3cc9a3 |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2017-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-0a8005156afe45faba5d8321eb3cc9a32025-02-03T05:58:51ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2017-01-01201710.1155/2017/86870358687035A Multistep Look-Ahead Deadlock Avoidance Policy for Automated Manufacturing SystemsChao Gu0Zhiwu Li1Abdulrahman Al-Ahmari2School of Electro-Mechanical Engineering, Xidian University, Xi’an 710071, ChinaSchool of Electro-Mechanical Engineering, Xidian University, Xi’an 710071, ChinaAdvanced Manufacturing Institute, King Saud University, Riyadh 11421, Saudi ArabiaFor an automated manufacturing system (AMS), it is a computationally intractable problem to find a maximally permissive deadlock avoidance policy (DAP) in a general case, since the decision on the safety of a reachable state is NP-hard. This paper focuses on the deadlock avoidance problem for systems of simple sequential processes with resources (S3PR) by using Petri nets structural analysis theory. Inspired by the one-step look-ahead DAP that is an established result, which is of polynomial complexity, for an S3PR without one-unit-capacity resources shared by two or more resource-transition circuits (in the Petri net model) that do not include each other, this research explores a multiple-step look-ahead deadlock avoidance policy for a system modeled with an S3PR that contains a shared one-unit-capacity resource in resource-transition circuits. It is shown that the development of an optimal DAP for the considered class of Petri nets is also of polynomial complexity. It is indicated that the steps needed to look ahead in a DAP depend on the structure of the net model. A number of examples are used to illustrate the proposed method.http://dx.doi.org/10.1155/2017/8687035 |
| spellingShingle | Chao Gu Zhiwu Li Abdulrahman Al-Ahmari A Multistep Look-Ahead Deadlock Avoidance Policy for Automated Manufacturing Systems Discrete Dynamics in Nature and Society |
| title | A Multistep Look-Ahead Deadlock Avoidance Policy for Automated Manufacturing Systems |
| title_full | A Multistep Look-Ahead Deadlock Avoidance Policy for Automated Manufacturing Systems |
| title_fullStr | A Multistep Look-Ahead Deadlock Avoidance Policy for Automated Manufacturing Systems |
| title_full_unstemmed | A Multistep Look-Ahead Deadlock Avoidance Policy for Automated Manufacturing Systems |
| title_short | A Multistep Look-Ahead Deadlock Avoidance Policy for Automated Manufacturing Systems |
| title_sort | multistep look ahead deadlock avoidance policy for automated manufacturing systems |
| url | http://dx.doi.org/10.1155/2017/8687035 |
| work_keys_str_mv | AT chaogu amultisteplookaheaddeadlockavoidancepolicyforautomatedmanufacturingsystems AT zhiwuli amultisteplookaheaddeadlockavoidancepolicyforautomatedmanufacturingsystems AT abdulrahmanalahmari amultisteplookaheaddeadlockavoidancepolicyforautomatedmanufacturingsystems AT chaogu multisteplookaheaddeadlockavoidancepolicyforautomatedmanufacturingsystems AT zhiwuli multisteplookaheaddeadlockavoidancepolicyforautomatedmanufacturingsystems AT abdulrahmanalahmari multisteplookaheaddeadlockavoidancepolicyforautomatedmanufacturingsystems |