A study on the structural complexity reduction of petri net based liveness-enforcing supervisors in flexible manufacturing systems

Abstract

Esnek üretim sistemlerinde (Flexible Manufacturing Systems – FMS) kördüğümün önlenmesi (canlılık-yürürlüğe koymak) amacıyla şu ana kadar pek çok çalışma yapılmıştır. Petri ağları FMS'te kördüğüm oluşumlarını imkansız hale getirmek için canlılık sağlamak üzere kullanılan bir araçtır. FMS'lerde canlılık-sağlayan bir Petri net denetçisinin performansını değerlendirmek için kullanılan üç kriter davranışsal serbestlik, hesaplama karmaşıklığı ve yapısal karmaşıklıktır. Yapısal karmaşıklığı azaltma, canlılık-uygulayıcı denetçilerdeki kontrol mevkilerinin (monitörlerin) sayısının azaltılmasını içerir. Şu anda bu sorunu çözmek için literatürde bazı önemli sonuçlar vardır. Ancak, yapısal olarak basit monitörler elde etmek için yüksek hesaplama bedeli ödemek zorunludur. Mevki değişmezleri arasında doğrusal ilişkiler kurulması yoluyla makul bir hesaplama çabasıyla yapısal olarak basit monitörler elde etmek için bu çalışmada yeni bir yöntem önerilmiştir. Burada önerilen yöntem ile elde edilen yapısal olarak basit monitörler, optimum veya optimuma yakın davranış serbestliği sağlarlar. Önerilen yaklaşımın farklı Petri ağı sınıflarına uygulanabilirliği çeşitli örneklerle gösterilmiştir.

Many works have been carried out for the study on deadlock prevention (liveness-enforcing) in flexible manufacturing systems (FMS). Petri nets have been used as a tool to enforce liveness in FMS so as to make deadlocks impossible to occur. Behavioral permissiveness, computational complexity and structural complexity are three criteria to evaluate the performance of a liveness-enforcing Petri net supervisor for FMSs. The reduction of structural complexity involves the reduction of the number of control places (monitors) in liveness-enforcing supervisors. Currently there are some important results in the literature to solve this problem. However, to obtain structurally simple monitors, one has to pay a high computational price. In this study a new method is proposed for obtaining structurally simple monitors with a reasonable computational effort via establishing linear relationships that exist between the place invariants. Structurally simple monitors obtained by the method proposed here provide optimal or near optimal behavioral permissiveness. The applicability of the proposed approach is shown by means of several examples for different classes of Petri nets.