زنده بودن از S3PR گسترده

Most existing prevention methods tackle the deadlock issue arising in flexible manufacturing systems modeled with Petri nets by adding monitors and arcs. Instead, this paper presents a new one based on a characteristic structure of WS3PR, an extension of System of Simple Sequential Processes with Resources (S3PR) with weighted arcs. The numerical relationships among weights, and between weights and initial markings are investigated based on simple circuits of resource places, which are the simplest structure of circular wait, rather than siphons. A WS3PR satisfying a proposed restriction is inherently deadlock-free and live by configuring its initial markings. A set of polynomial algorithms are developed to implement the proposed method. Several examples are used to illustrate them.

As an important component of Computer Integrated Manufacturing, a Flexible Manufacturing System (FMS) is built with some amount of flexibility that allows it to react in the case of changes of production requirements, whether predicted or unpredicted. It mainly consists of robots, computer-controlled machines, and conveyors, all known as resources of a system. They are dynamically arranged according to varying specifications to meet the demand of high-mix-low-volume production. Several different raw workpieces are concurrently processed in it by various resources. Due to the concurrency and limited quantity of shared resources, one undesirable situation is the deadlock arising in a fully automated system (Zhou and DiCesare, 1993, Li and Zhou, 2009 and Wu and Zhou, 2010).

Compared with the structure of ordinary Petri nets, the role of weights of arcs in determining the liveness of generalized ones should not be neglected. Unlike all arcs’ weights being one in ordinary S3PR, weights of arcs in WS3PR mean the multiple use of resources by an operation, and the numerical relationship between weights of arcs connecting operation and resource places, and token counts in resource places restrict the allocation of system resources. Inspired by concepts of circular wait and circular blocking presented in Lewis et al. (1998), this work proposes the concept of weighted simple directed circuit (WSDC) that is a generalized structure of circular wait. Different from the circular wait that is a strongly connected component and may be composed of several non-disjoint simple resource circuits (Lewis et al., 1998), WSDC is a simple resource circuit. Thus a shared resource place may be competed by only two operations in such a circuit. It is important for us to study the numerical relationship between weights and initial marking. Hence, a new deadlock prevention method may be developed from the view point of WSDC rather than siphons. The effect of weights is also considered in defining the state of circular block for WSDC in this research. It is similar to the definition of insufficient marking for a siphon in a generalized net (Tricas & Martínez, 1995). A generalized version of Dinning Philosophers modeled by WS3PR is shown in Fig. 9. cW=t2p16t14p20t11p19t8p18t5p17t2cW=t2p16t14p20t11p19t8p18t5p17t2 is the only WSDC in this net. When it is in the state of CB under the current initial marking M0=30p1+30p4+30p7+30p10+30p13+2r1+1r2+2r3+7r4+4r5M0=30p1+30p4+30p7+30p10+30p13+2r1+1r2+2r3+7r4+4r5, all five part paths are dead, i.e., the entire system is deadlocked. In this case, there is one token trapped in p19p19 since the minimal weight of out-arcs is greater than the number of trapped tokens. Evidently, this undesirable state is a result of combined action of its net structure, weights, and initial marking.