Research On Deadlock Prevention Method Of Flexiable Manufacturing System Based On MIP

With the development of science and technology,the traditional mechanical manufacturing system,characterized by producing large-scale and single-variety productions is being replaced by the flexible manufacturing system(FMS),which can also be adapted to the dynamic requirement changes of the market.A flexible manufacturing system often has several parallel processing processes,resources are shared among them.When processes are competing for shared resources,deadlock occurs because they wait for the other to release resources they are waiting on.Deadlock will lead to the stopage of the partial or the whole production in FMS,which seriously affects the production efficiency of machinery manufacturing enterprises.Therefore,the description,analysis and control of deadlocks are crucial for normal operation of such systems.Petri nets are considered to be among the best graphical mathematical modeling tools for modeling and deadlock analysis of FMS.In Petri nets,a special structural object named siphon is closely related to the occurrence of deadlock states,many deadlock prevention policies of FMS based on Petri nets are developed on the basis of it.The performance of a deadlock prevention strategy can be evaluated on the basis of three important factors,namely behavioral permissiveness of the controlled system,computational efficiency of the algorithm,and structural complexity of the supervisor.The structural complexity of the supervisor determines the additional cost of system verfications,validations and implementations,the behavioral permissiveness of the controlled system has a direct influence on the flexibility and efficiency of the system,and the computational efficiency of the algorithm determines whether the control strategy can be applied to large-scale manufacturing systems.In order to optimize the performance of these three factors,this dissertation uses Petri nets to model FMSs and proposes several deadlock prevention strategies based on mixed integer programming(MIP),the main results of these researches as follows:1.For generalized petri nets of FMS,a more general condition named max~#-controlled is introduced by studing the limitation of existing controllability conditions for siphons.According to the definition of max~#-controlled,a deadlock detection method based on MIP for more types of Petri nets are proposed,it can be a theoretical support for dealing with the structural complexity problems of liveness-enforcing supervisor in large scale of FMSs.2.For a class of Petri nets called systems of sequential systems with shared resources(S~4PR),after studing the relationship between the liveness of S~4PR and the existence of bad siphons,the MIP-based extraction algorithm for minimal bad siphons and related bad marking are improved,and then an iterative deadlock prevention policy for controlling minimal bad siphons is proposed.The experimental results showed that the controlled system resulting from the proposed policy has more permissive reachable states and optimal liveness-enforcing supervisors can be obtained for certain S~4PR nets.Meanwhile,the policy possesses low computational complexity because it avoids the classical complete states and siphon enumerations.3.It is found that in the iterative deadlock prevention strategies based on siphons,the structural complexity of the supervisor and the behavioral permissiveness of the controlled system are impacted by the order in which siphons are controlled.Therefore,on the basis of previous results,three kinds of deadlock prevention policies for selecting controlled siphons based on MIP are proposed.In each iteration,the first policy is to control the minimal bad siphons with minimal number of places,in which the number of resource places is the least.When the numbers of resource places in those siphons are the same,the second method is to control the minimal bad siphons with minimal number of places,in which the number of complementary set of those siphons is the largest.The third stragegy is to priority control of M-controled siphons in minimal bad ones.The main purpose of the first and second policies is to simplify the structural complexity of supervisiors.The third aims to improve the behavioral permissiveness of the controlled system.Experiments show that these three methods are very effective for deadlock control of some Petri nets of FMSs.4.At present,most of deadlock prevention policies cope with deadlocks by adding control places in Petri nets of FMS,redundant control places are ubiquitous.A structure simplification method of the liveness-enforcing supervisor for S~4PR nets based on the detection of bad siphons is proposed.A control place is redundant if bad siphons exist in the controlled system after removing it from the net.By using this method,the structure complexity of the supervisor is reduced greatly,and the behavior permissibility of the controlled system is improved too.Meanwhile,the proposed method has low computational complexity because the detection of bad siphons is based on MIP.