Deadlock prevention problem is an important issue in essence for flexible manufacturing systems (FMS). Many works make efforts in the issue. Theory of regions is recognized as one of the powerful deadlock prevention method for obtaining maximally permissive controllers. All legal and live maximal behavior of Petri net models can be preserved by using marking/transition-separation instance (MTSI) or event-state-separation-problem (ESSP) methods. However, solving all sets of inequalities are an extremely time consuming problem since all MTSIs and ESSPs need to be considered in the reachability graph of a deadlock FMS. In our previous work, we propose crucial MTSI (CMTSI) method to improve computational difficulty successfully. In this work, we further enhance the computational efficiency of CMTSI by combining critical markings and CMTSI methods. Experimental results reveal that this approach is more practical than the conventional methods.