A novel siphon-based divide-and-conquer(SbDaC)policy is presented in this paper for the synthesis of Petri net(PN)based liveness-enforcing supervisors(LES)for flexible manufacturing systems(FMS)prone to deadlocks or l...A novel siphon-based divide-and-conquer(SbDaC)policy is presented in this paper for the synthesis of Petri net(PN)based liveness-enforcing supervisors(LES)for flexible manufacturing systems(FMS)prone to deadlocks or livelocks.The proposed method takes an uncontrolled and bounded PN model(UPNM)of the FMS.Firstly,the reduced PNM(RPNM)is obtained from the UPNM by using PN reduction rules to reduce the computation burden.Then,the set of strict minimal siphons(SMSs)of the RPNM is computed.Next,the complementary set of SMSs is computed from the set of SMSs.By the union of these two sets,the superset of SMSs is computed.Finally,the set of subnets of the RPNM is obtained by applying the PN reduction rules to the superset of SMSs.All these subnets suffer from deadlocks.These subnets are then ordered from the smallest one to the largest one based on a criterion.To enforce liveness on these subnets,a set of control places(CPs)is computed starting from the smallest subnet to the largest one.Once all subnets are live,this process provides the LES,consisting of a set of CPs to be used for the UPNM.The live controlled PN model(CPNM)is constructed by merging the LES with the UPNM.The SbDaC policy is applicable to all classes of PNs related to FMS prone to deadlocks or livelocks.Several FMS examples are considered from the literature to highlight the applicability of the SbDaC policy.In particular,three examples are utilized to emphasize the importance,applicability and effectiveness of the SbDaC policy to realistic FMS with very large state spaces.展开更多
Livelocks, like deadlocks, can result in serious results in running process of flexible manufacturing systems(FMSs). Current deadlock control policies(DCPs) based on mixed integer programming(MIP) cannot detect siphon...Livelocks, like deadlocks, can result in serious results in running process of flexible manufacturing systems(FMSs). Current deadlock control policies(DCPs) based on mixed integer programming(MIP) cannot detect siphons that cause and cope with livelocks in Petri nets. This study proposes a revised mixed integer programming(RMIP) method to directly solve the new smart siphons(NSSs) associated with livelocks in a system of sequential systems with shared resources(S^4 R), a typical subclass of generalized Petri net models. Accordingly,the solved NSSs are max'-controlled by adding the corresponding control places(CPs). As a result, an original S^4 R system with livelocks can be converted into the live controlled Petri net system. The related theoretical analysis and an example are given to demonstrate the proposed RMIP and the corresponding control algorithm(CA).展开更多
基金The authors extend their appreciation to King Saud University,Saudi Arabia for funding this work through the Ongoing Research Funding Program(ORF-2025-704),King Saud University,Riyadh,Saudi Arabia.
文摘A novel siphon-based divide-and-conquer(SbDaC)policy is presented in this paper for the synthesis of Petri net(PN)based liveness-enforcing supervisors(LES)for flexible manufacturing systems(FMS)prone to deadlocks or livelocks.The proposed method takes an uncontrolled and bounded PN model(UPNM)of the FMS.Firstly,the reduced PNM(RPNM)is obtained from the UPNM by using PN reduction rules to reduce the computation burden.Then,the set of strict minimal siphons(SMSs)of the RPNM is computed.Next,the complementary set of SMSs is computed from the set of SMSs.By the union of these two sets,the superset of SMSs is computed.Finally,the set of subnets of the RPNM is obtained by applying the PN reduction rules to the superset of SMSs.All these subnets suffer from deadlocks.These subnets are then ordered from the smallest one to the largest one based on a criterion.To enforce liveness on these subnets,a set of control places(CPs)is computed starting from the smallest subnet to the largest one.Once all subnets are live,this process provides the LES,consisting of a set of CPs to be used for the UPNM.The live controlled PN model(CPNM)is constructed by merging the LES with the UPNM.The SbDaC policy is applicable to all classes of PNs related to FMS prone to deadlocks or livelocks.Several FMS examples are considered from the literature to highlight the applicability of the SbDaC policy.In particular,three examples are utilized to emphasize the importance,applicability and effectiveness of the SbDaC policy to realistic FMS with very large state spaces.
基金the National Natural Science Foundation of China(No.61364004)the Chinese Visiting Scholars to Study Overseas Program supported by China Scholarship Council Foundation(No.[2014]5049,201408625045)+1 种基金the Doctoral Research Funds of Lanzhou University of Technology(No.04-237)the Alumni Foundation of Civil Engineering 77,Lanzhou University of Technology(No.TM-QK-1301)
文摘Livelocks, like deadlocks, can result in serious results in running process of flexible manufacturing systems(FMSs). Current deadlock control policies(DCPs) based on mixed integer programming(MIP) cannot detect siphons that cause and cope with livelocks in Petri nets. This study proposes a revised mixed integer programming(RMIP) method to directly solve the new smart siphons(NSSs) associated with livelocks in a system of sequential systems with shared resources(S^4 R), a typical subclass of generalized Petri net models. Accordingly,the solved NSSs are max'-controlled by adding the corresponding control places(CPs). As a result, an original S^4 R system with livelocks can be converted into the live controlled Petri net system. The related theoretical analysis and an example are given to demonstrate the proposed RMIP and the corresponding control algorithm(CA).
