Structural Analysis Of Petri Nets Based On Linear Program

Flexible manufacturing systems can automatically produce various kinds of products by using shared resources.Deadlocks may occur in an FMS due to the competition for limited shared resources.Once a deadlock occurs,a system is blocked and its efficiency or productivity is reduced.Hence,the deadlock problem must be considered in designing and controlling a flexible manufacturing system.Petri nets are suitable to model and control flexible manufacturing systems.Based on Petri nets,structural analysis plays an important role in the deadlock control of them.Siphons and resource transition circuits are two special substructures of a Petri net,which have great relationship with deadlocks.The number of siphons and resource transition circuits are exponentially related to the size of a Petri net.Effective calculation of all minimal siphons and resource transition circuits has become an urgent problem in scientific research.This thesis presents an approach to compute all minimal siphons and all resource transition circuits by using integer linear programming methods.Petri net analysis based on reachability graph can generally achieve optimal deadlock control.However,it needs to compute all reachable states of a net model,which always suffers from the state explosion problem.In order to avoide calculating all reachable states of Petri nets,by combining theory of siphons and reachability graph,an approach is proposed to compute all dead-zone markings in ordinary Petri nets in this thesis.The main contents of this paper are as follows:First,this paper presents an approach to compute all minimal siphons and all resource transition circuits of a Petri net model by using integer linear programming methods.According to their definitions,we design constraints for each place to satisfy conditions.By summarizing the constraints for all places,we formulate an integer linear programming method to find a minimal siphon or resource transition circuits.Then,a constraint is added in the integer linear programming method to exclude the obtained result.The process carries out until all minimal siphons or resource transition circuits are obtained.A number of examples are provided to demonstrate the proposed approaches.Secondly,an approach to compute dead zone is proposed by combining brach-and-bound method and integer programming in this paper.Then,an approach is proposed to compute dead zone markings for ordinary Petri nets.The approach presented in this thesis only searches a part of a reachable graph and successfully avoids computing all reachable states in models.Hence,it is efficient to generate the deadlock zone of a Petri net model.Thirdly,markings in deadlock zone can be used to compute the set of first-met bad marking.By using a vector covering approach,we can obtain the minimal covering set of the first-met bad markings.Experimental results show that the proposed method can obtain the same minimal covering set of first-met bad marking as the traditional approach.