A petri net based divide and conquer method for the synthesis of liveness enforcing supervisors in FMS

Abstract

Esnek üretim sistemlerinde (Flexible Manufacturing Systems – FMS) kördüğümler paylaşılan kaynaklar nedeniyle ortaya çıkar ve feci sonuçlara yol açarlar. Petri ağları FMS' lerde kördüğüm problemlerini çalışmak için yaygın olarak kullanılan bir modelleme ve tasarım aracıdır. Bu yüksek lisans tezinde, FMS' lerde canlılık sağlayıcı denetçilerin sentezi (LES) için Petri ağı temelli bir böl ve kazan yöntemi önerilmiştir. Karmaşık bir Petri ağı modelinde (Petri net model – PNM) kördüğüm problemleriyle başa çıkmak için, ulaşılabilirlik grafı (RG) kullanımı mümkün değildir. Bu sorunun üstesinden gelmek için, bu tezde önerilen yöntemde, Petri ağı modeli, küçük bağlı alt ağları bölünür. Sonra, LES bu alt-ağları kullanarak orijinal Petri ağı modeliiçin hesaplanır. Her ne kadar önerilen yöntemin çevrim dışı (off-line) hesaplanması teorisi olarak üstel karmaşıklığa sahip olsa daönerilen yöntem uygulanabilir, çok etkili ve kolay anlaşılırdır. Önerilen yöntemin uygulanabilirliğini göstermek için bazı örnekler sunulmuştur.

In flexible manufacturing systems (FMS), deadlocks occur due to shared resources and lead to catastrophic results. Petri nets have been widely used as a modeling and design tool for the study of deadlock problems in FMSs. In this thesis, a Petri net based divide and conquer method is proposed for the synthesis of liveness enforcing supervisors (LES) in FMSs. To deal with deadlocks in a complex Petri net model (PNM), the use of reachability graph (RG) is unmanageable. To overcome this problem, in the method proposed in this thesis, the Petri net model is divided into small connected sub-nets. Then, a LES is computed for the original PNM by using these sub-nets. The proposed method is generally applicable, very effective and straight forward although its off-line computation is of exponential complexity in theory. Examples are provided to show the applicability of the proposed method.