Simplification Of Designing A Maximally Permissive Liveness-enforcing Supervisor

When the flexible manufacturing system works,multiple processes will use the shared re-source.If the resources are allocated incorrectly,a deadlock will occur.Deadlocks can prevent the system from functioning properly.It is of great engineering significance to solve the deadlock problem of manufacturing systems.Petri net is an effective modeling tool.Based on Petri net theory,many deadlock prevention strategies have been developed.Deadlock prevention policies based on the theory of regions generally design a maximally permissive liveness-enforcing supervisor for a system by forbidding all first-met bad mark-ings.However,if only first-met bad markings are considered to design the control place,some legal markings may be forbidden by the control place.Therefore,when designing a control place for a first-met bad marking,it is also necessary to consider reachability condi-tions to ensure that all legal markings are not forbidden.Since the number of legal markings in the Petri net is usually quite large,the number of the constraints needed for designing the control place for the first-met bad marking through integer linear programming problem is great.The study found that it is unnecessary to consider legal markings when forbidding some first-met bad markings.The computational complexity is simplified by classifying all first-met bad markings.The maximally permissive liveness-enforcing supervisor of the S~3PR(System of Simple Sequential Processes with Resources)is obtained,if such a super-visor exists.The vector covering approach is used to reduce the number of first-time bad markings that need to be forbidden.The main tasks are as follows:1.The bound marking is proposed.A first-met bad marking is a bound marking,if all the marked operation places in the first-met bad marking reach their bounds.According to the bound marking,all first-met bad markings are classified.If a first-met bad marking is the bound marking,no legal marking is forbidden when it is forbidden by a control place.Therefore,the computational complexity of the design control place can be simplified.2.If a first-met bad marking is not a bound marking,the control place designed by the for-bidding conditions may forbid some legal markings.Therefore,when designing a control place for the first-met bad marking,it is necessary to ensure that all legal markings are not forbidden.Through analysis,the definition of sum covering set is proposed to obtain the le-gal markings that need to be considered.An iterative method is given to design control place to forbid the first-met bad marking.First,control place is designed by forbidding condition.At each iteration,the forbidden legal markings are obtained by computed sum covering set.The reachability conditions are added to the integer linear programming problem.The prob-lem is solved and the control place is updated.This process is carried out until the resulting control place does not forbid any legal markings.3.For the Petri net that does not have a maximally permissive liveness-enforcing supervisor,analyze the reason why the legal markings are forbidden when the first-met bad marking is forbidden.The definition of contradiction marking is proposed,and an algorithm is given to get its sub-optimal supervisor.