Computationally Improved Optimal Deadlock Prevention Policy for Linear Programming Problems of Flexible Manufacturing Systems

Deadlock prevention policies are used to solve the deadlock problems of flexible manufacturing systems. Theory of regions is the efficient method for obtaining optimal (i.e. maximally permissive) controllers. All legal and live maximal behavior can be preserved by using marking/transition-separation instances (MTSIs) or event-state-separation-problem (ESSP) methods. However, solving all sets of inequalities is very time-consuming. Moreover, the number of linear programming problems (LPPs) of all legal markings is also exponential with net size. In this paper, a novel methodology is proposed to reduce the number of MTSIs/ESSPs and LPPs. Preciously, one new concept called critical ones of crucial marking/transition-separation instances (COCMTSI) is developed and used in this deadlock prevention policy that allows designers to employ few MTSIs to deal with deadlocks.