Abstract
As a structural object of Petri nets, siphons play a key role in the development of deadlock prevention policies for resource allocation systems. Elementary siphons are a novel concept in net theory. Based on graph theory, this paper proposes an effective algorithm with polynomial complexity to find a set of elementary siphons for a linear system of simple sequential processes with resources (LS3PR), a subclass of Petri nets, which can model many flexible manufacturing systems. The algorithm is established through the use of a resource directed graph and complementary sets of strict minimal siphons (SMS) of the net. The upper bound of the number of SMS in such a net is identified. A running example is used to demonstrate the proposed method.
Original language | English (US) |
---|---|
Pages (from-to) | 912-923 |
Number of pages | 12 |
Journal | IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans |
Volume | 39 |
Issue number | 4 |
DOIs | |
State | Published - 2009 |
All Science Journal Classification (ASJC) codes
- Software
- Information Systems
- Human-Computer Interaction
- Electrical and Electronic Engineering
- Control and Systems Engineering
- Computer Science Applications
Keywords
- Automated manufacturing system
- Digraph
- Discrete event system
- Elementary siphon
- Flexible manufacturing system
- Petri net