Computation of the number of legal states for petri net-based deadlock prevention problems

Basit Öğe Kaydı
dc.authorid0000-0001-9625-5523
dc.authorid0000-0002-2780-3386
dc.contributor.authorGelen, Gokhan
dc.contributor.authorUzam, Murat
dc.date.accessioned2026-02-12T21:05:06Z
dc.date.available2026-02-12T21:05:06Z
dc.date.issued2023
dc.departmentBursa Teknik Üniversitesi
dc.description.abstractPetri net (PN) based prevention and control methods are widely studied in the literature to solve deadlock problems in flexible manufacturing systems (FMS). In PN models of FMS suffering from deadlocks, the reachability graph (RG) of the PN model can provide all reachable system states from the initial state, including all legal states, bad states, and deadlock states. A maximally permissive deadlock controller allows the system to reach all legal states exist within the live zone (LZ) that determines the optimal live behavior, while prohibits reaching bad and deadlock states exist within the dead zone. It is necessary to know the exact number of legal states that must be provided by a deadlock controller to determine the behavioral permissiveness of a control policy. Therefore, the number of legal states has been considered as a quality measure for deadlock prevention methods available in the literature. Unfortunately, to date for a given RG of a PN model of an FMS suffering from deadlocks, no study has been reported to provide the number of reachable legal states exist within the LZ of the given RG. In this paper, a method is proposed for the computation of the number of legal states that must be provided by an optimal deadlock prevention policy. The proposed method makes use of the reachability analysis of a given PN model of a deadlock-prone FMS together with the first strongly connected component (SCC) by using INA (Integrated Net Analyzer). The number of legal states computed from the first SCC that includes the initial marking represents the LZ of a RG. The proposed algorithm is implemented as an executable program. The number of legal states of a deadlock controller can easily and correctly be computed by using the proposed method and tool. Several well-known examples of FMS are considered to illustrate the applicability and the effectiveness of the proposed method.
dc.description.sponsorshipScientific and Technological Research Council of Turkey (Turkiye Bilimsel ve Teknolojik Arastirma Kurumu-TUEBITAK) [TUEBITAK 112M229]
dc.description.sponsorshipThis work was supported by the research grant of The Scientific and Technological Research Council of Turkey (Turkiye Bilimsel ve Teknolojik Arastirma Kurumu-TUEBITAK) under the project number TUEBITAK 112M229. The authors would like to thank the Editor and five anonymous referees whose comments and suggestions greatly helped us to improve the presentation and the quality of this paper.
dc.identifier.doi10.14744/sigma.2023.00056
dc.identifier.endpage502
dc.identifier.issn1304-7205
dc.identifier.issn1304-7191
dc.identifier.issue3
dc.identifier.scopus2-s2.0-85162926042
dc.identifier.scopusqualityQ4
dc.identifier.startpage493
dc.identifier.urihttps://doi.org/10.14744/sigma.2023.00056
dc.identifier.urihttps://hdl.handle.net/20.500.12885/6799
dc.identifier.volume41
dc.identifier.wosWOS:001008473000002
dc.identifier.wosqualityQ3
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakScopus
dc.language.isoen
dc.publisherYildiz Technical Univ
dc.relation.ispartofSigma Journal of Engineering and Natural Sciences-Sigma Muhendislik Ve Fen Bilimleri Dergisi
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/openAccess
dc.snmzKA_WoS_20260212
dc.subjectDiscrete Event Systems
dc.subjectPetri Nets
dc.subjectDeadlock Prevention
dc.subjectReachability Graph
dc.subjectStrongly Connected Components
dc.titleComputation of the number of legal states for petri net-based deadlock prevention problems
dc.typeArticle

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu