Resource-Oriented-Petri-Net-Based Deadlock Control And Optimization Of AMS

The design and implementation of an automated manufacturing system is quite com-plex.It is usually necessary to model the system clearly and accurately before it is put into operation.The constiuent components and characteristics of the system should be analyzed so that various problems in the system can be found and overcomed at the beginning of the design.How to design production planning and scheduling based on product information and system manufacturing capabilities,make the material flow arrangements in the manufac-turing system reasonable and effective,and improve the flexible performance and efficiency of the manufacturing process.First,it is necessary to ensure the continuity of the operation of the system,that is,non-blocking operation.Secondly,to optimize the dynamic behavior of the system.Petri net is an important mathematical tool for modeling and analysis of automated manufacturing systems.When using the regular Petri net—process-oriented Petri nets to model an automated manufacturing system,its modeling ability is powerful and applicable to deal with all types of manufacturi ng systems.It can also model intuitively the job flow and resource allocation as well as deallocation during working process.However,the process-oriented Petri net model has a large scale,a bit more information redundancy,complex net structure,and a little hard work to extract the key structure of Petri net(for example,to solve an integer programming in order to extract the "siphons")and many other inconveniences.The regular Petri net is extended to a resource-oriented Petri nets via augmentation of colors to its components(such as,places,transitions,arcs,et cetera)and limitation of the capacity of places in the regular Petri net.Formally,a resource-oriented Petri net can be viewed as a directed graph.Compared with the regular Petri net,the resource-oriented Petri net compresses some information of the processing process.Its size is small and its structrue is compact.The deadlock occurs if and only if a complete directed circuit is saturated.Algorithms related to directed graphs in Graph Theory can be translated to resource-oriented Petri nets.The resource-oriented Petri net can accurately model the special sub-category of the automated manufacturing system,i.e.,Disjunctive and Single-Unit resource allocation system,which is just the research object of this study.In this disertation,a combination of reachability graph analysis and structural analy-sis is employed to explore the "reasonable resource allocation and optimal scheduling" in automated manufacturing systems.Appropriate mathematical models are established and comprehensive and efficient control algorithms are developed,not only to ensure that the system has no global or local blocking,but also achieve optimized operation of system be-havior.Petri net reachability graph has "state-explosion problem",and the computation of reachability graph is NP-hard.Firstly,the size of the resource-oriented Petri net is re-duced by removing the components that are not related to deadlock,so that the number of reachability states is reduced dramatically.Secondly,the state space is identified as two disjoint subspaces,that is,a set of legal markings and a set of illegal markings.Then,the marking covering/covered technology is employed to further reduce states space need to be considered into,the identified data space is reduced to two smaller sets.Finally,an integer programming problem is constructed and solved to obtain the optimal control strategy of the system.Solving integer programming is not efficient till this time.A necessary and sufficient condition for the system(partial)deadlock is that there is a complete resource-transition cir-cuit that is saturated.By preventing the complete resource-transition circuit from saturation,it can ensure that the system has no instant deadlock,but the system may fall into a "restrict-ed" deadlock.If the capacity of the shared chain of any two complete resource-transition circuits is greater than 1,the maximally permissive control policy is obtained accordingly.In such a case,it is enough that avoiding all of the complete resource-transition circuits never to be in saturation.The resource-oriented Petri net is used to model the disjunctive and single unit resource allocation system.The capacity of shared chain has space 1 usually.To deal with such a case,based on the reachability analysis,the minimal covered set of illegal markings is divided into subclasses according to their structural features.Each subclass can be identified through the structural features and the complexity of identification is polynomial.Also,the maximally permissive deadlock prevention policy for those markings in such subclass is obtained in a easy way.Therefore,these methods are quite effecient.The residual markings that has not been identified by the structural analysis technique is solved by linear programming.Finally,it is proved by the well known examples in the literature that the proposed maximal deadlock control policies for deadlock prevention is effective and applicable.