The disparity of Petri net models in the literature for the study of resource allocation problems in Flexible Manufacturing Systems (FMSs) is overwhelming. Paradoxically, those models often strongly overlap in terms of their modeling capability. Such clustering seems to be impelled by a mature knowledge of results which capsize liveness at the topological level of the FMS for families of models which comply with some properties of good behaviour. Not rarely, such properties are embraced at the expense of severe or inconsistent syntax restrictions paying slight regard to actual modelling requirements in the application domain of FMSs. In this paper, we promote a distillation of the current amalgam of subclasses and tangent results, proposing taxonomic categories that allow capturing the different capabilities of each kind of model and establishing a reference framework for past and future advances.

Deadlock states are undesirable situations in any system,. Their avoiding presents a major issue in control of resource allocation systems (RAS), a theoretical paradigm, used in construction of e.g. flexible manufacturing systems. In coordinating RAS with processes containing concurrent execution in their development, it has been proved, that deadlock avoidance policies developed, for sequential RAS are applicable. This requires, however, a, transformation of the RAS structure from, coordinating to sequential, what brings the exponential growth of the modelled system, size. In, this paper, we present a deadlock, avoidance method that allows using the original coordinating RAS with additional data structures calculated before the system, starts. It is an enhanced, version of the banker's algorithm, with, our proposed, data structures manipulation.

Siphons are related to the liveness properties of Petri net models. This relation is strong in the case of resource allocation systems (RASs). Siphons can be used in these systems in order to both characterize and prevent/avoid deadlock situations. However, the computation of these structural components can be very time consuming or, even, impossible. Moreover, if, in general, the complete enumeration of the set of minimal siphons must be avoided (there can exist an exponential number of such components), some deadlock prevention methods rely on its (complete or partial) computation and enumeration. The special syntactical constraints of some classes of RASs can help in developing specific algorithms to compute siphons in a more efficient way. In this work, a known method for siphon computation is adapted to get advantage of the special (syntactical) structure of a class of RASs; a parallel implementation is proposed and some experimental results are presented

A new method for the deadlock prevention problem in concurrent systems where a set of processes share a set of common resources in a conservative way is proposed. It can be applied to flexible manufacturing systems, modeled with Petri nets. In this paper, we present a set of important results related to the deadlock prevention problem in S4PR nets. First, a liveness characterization is introduced, establishing how deadlocks can be studied in terms of circular waits. Second, we show how a circular wait situation corresponds to a particular marking related to a siphon of the Petri net model. Finally, this last characterization is used to obtain an iterative method that successively forbids deadlock related states, synthesizing the control necessary to ensure a final live behavior. The method can be implemented by means of the solutions of a set of integer linear programming problems.

Siphons are related to liveness properties of Petri net models. This relation is strong in the case of resource allocation systems (RAS). Siphons can be used in these systems in order to both, characterize and prevent/avoid deadlock situations. However, the computation of these structural components can be very time consuming or, even, impossible. Moreover, if, in general, the complete enumeration of the set of minimal siphons must be avoided (there can exist an exponential number of such components), some deadlock prevention methods rely on its (complete or partial) computation and enumeration. In the paper we show how the special syntactical constraints of some classes of resource allocation systems (we concentrate on S/sup 4/PR) can help in developing specific implementations to compute siphons in a very efficient way.

Banker's-like approaches to deadlock avoidance are based on a decision procedure to grant active processes resources using information about the maximum needs of resources that a process can request in order to ensure termination. The paper presents an extension of the classical Banker's algorithm to a class of flexible manufacturing systems modeled by means of Petri nets. These systems have two interesting characteristics from the application point of view. First, flexible routing of parts is allowed, and second, a multiset of resources is allowed to be used at each processing step. The decision procedure introduced is polynomial in the Petri net model size.

The paper presents two methods for deadlock avoidance in concurrent systems. We apply the proposed approaches to flexible manufacturing systems, modeled by means of Petri nets. Both methods correspond to improvements of the classical Banker's algorithm, and are based on the knowledge of the process structure. The first one is polynomial in the size of the Petri net model. The second one depends strongly on the number of alternative paths for the processing of parts and can be of a non-polynomial cost.