An Algebraic Method To Enumerate The Reachable States Of A Class Of Petri Nets Modeling Flexible Manufacturing Systems

Deadlock control is a significant issue in modeling and control for flexible manufacturing systems(FMSs)due to the existence of shared resources.Structural analysis and reachability analysis are two popular techniques for deadlock prevention based on Petri nets.Siphons and resource-transition circuits(RT-circuits)are two special structures used in structural analy-sis.Based on structural analysis,a supervisor can be generally computed with low structural and computational complexity.However,most of controlled nets using this approach are usually of suboptimal permissiveness.A reachability graph is used in reachability analysis which provides all information of a plant net.Through this approach,a maximally permis-sive supervisor can always be obtained,but it suffers from highly computational complexity.Based on the aforementioned techniques,we propose an algebraic method for systems of simple sequential processes of resources(S~3PRs)with one?-resource.This method can provide the total number and information of reachable states.It is capable of reachability analysis and reduces the computation complexity.Moreover,we propose a method to classify S~3PRs into two distinguishing structural net-s.A maximally permissive supervisor can always be obtained for a class of S~3PRs.Two structural objects:siphons and RT-circuits are developed to analyze a plant net and design its controller.Based on RT-circuits,a resource digraph is used to describe a structure of resource places and transitions.After characterizing the net,a controlled net with a siphon-based supervisor is always maximally permissive.Finally,a marking shadow approach is extended to a generalized Petri net.First,a reacha-bility graph is computed and reachable states are divided into two zones:live-zone(LZ)and dead-zone(DZ).Then,a strict minimal shadow set of first-met bad markings(FBMs)and a strict minimal root set of legal markings are obtained.A place invariant(PI)is developed to design a supervisor which should forbid all FBMs and guarantee all legal markings to be reached.Hence,an optimal supervisor can be obtained for a generalized Petri net whenever such a supervisor exists.