Open Access

ARTICLE

Siphon-Based Divide-and-Conquer Policy for Enforcing Liveness on Petri Net Models of FMS Suffering from Deadlocks or Livelocks

Murat Uzam¹, Bernard Berthomieu², Wei Wei^3,*, Yufeng Chen³, Mohammed El-Meligy^4,5, Mohamed Abdel Fattah Sharaf ⁶

1 Elektrik-Elektronik Mühendisliği Bölümü, Mühendislik-Mimarlık Fakültesi, Yozgat Bozok Üniversitesi, Yozgat, 66100, Türkiye
2 Laboratoire d’Analyse et d’Architecture des Systèmes of Centre National de la Recherche Scientifique (LAAS/CNRS) 7, avenue du Colonel Roche, Toulouse, 31077, France
3 School of Electro-Mechanical Engineering, Xidian University, Xi’an, 710071, China
4 Jadara University Research Center, Jadara University, P.O. Box 733, Irbid, 21110, Jordan
5 Applied Science Research Center, Applied Science Private University, Amman, 11931, Jordan
6 Department of Industrial Engineering, College of Engineering, King Saud University, Riyadh, 12372, Saudi Arabia

* Corresponding Author: Wei Wei. Email:

Computers, Materials & Continua 2026, 86(1), 1-30. https://doi.org/10.32604/cmc.2025.069502

Received 24 June 2025; Accepted 30 July 2025; Issue published 10 November 2025

Abstract

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.

---

Keywords

---