Petri ağı

Bir petri ağı (yer/geçiş ağı, yerleşim/geçiş ağı veya Y/G ağı olarak da bilinir) sistemlerin incelenmesi için kullanılabilecek bir araçtır. Petri ağları, sistemin matematiksel bir modelle modellenebilmesine izin verir. Bir Petri ağı, geçiş ve yerleşim düğümlerinden oluşan tek yönlü iki parçalı graf olarak da tanımlanabilir. Ok şeklinde gösterilen yönlü eğriler, bir geçişten önce ve sonra hangi yerlerin olduğunu tanımlarlar.

Bazı kaynaklar Petri ağlarının 1939 Ağustos'unda, henüz 13 yaşında olan Carl Adam Petri tarafından, kimyasal prosesleri tarif etmek amacıyla bulunduğunu belirtirler.

Petri ağları, UML, BPMN ve EPC gibi endüstri standartlarına benzer şekilde seçim, tekrarlama, eşzamanlı çalışma gerektiren adımlı prosesler için bir grafiksel notasyon sunar. Ancak bu standartların ötesinde, proses analizi için geliştirilmiş matematiksel teorisiyle ilgili proseslerin çalışmasını matematiksel bir kesinlikte modelleyebilir.

Bir petri ağı yerler, geçişler ve eğrilerden oluşur. Yerler ve geçişler, graf teorisindeki düğümler ve kenarlar ile eşdeğerdir. Eğriler bir yerden bir geçişe veya bir geçişten bir yere doğru koşarlar. İki yer arasında veya iki geçiş arasında bir eğri olamaz. Geçişe giriş yapan eğri hangi yerden çıkış yaptıysa, bu yere geçişin giriş yeri; Geçişten çıkış yapan eğri hangi yere giriş yaptıysa, bu yere geçişin çıkış yeri denir.

Grafiksel olarak bir Petri ağındaki bir yer ayrık sayıdaki işaretler içerebilir. Bu işaretler jeton olarak adlandırılır. Jetonların herhangi bir anda yerler üzerindeki dağılımı işaretleme, jeton dağılımı veya konfigürasyon olarak adlandırılır.

Etkinleştirilmiş bir diğer ifade ile, tetiklenebilir bir geçiş tetiklendiğinde, giriş yerlerinden ihtiyaç duyulan miktarda jeton tüketir ve çıkış yerlerinde üretilmesi gereken miktarda jeton üretilir. Bu 'gereken' miktarlar, ilgili geçişin ağırlığı, ayrık sistemler için özelleştirirsek geçişin üzerinde yazan rakam, ile gösterilir.

Bir çalışma kuralı tanımlanmadığı sürece, Petri ağlarının çalışması deterministik değildir. Aynı anda birden fazla geçiş tetiklendiğinde, hangisinin tetikleneceği bilinemez ya da bir başka deyişle, geçişlerin herhangi birisi tetiklenebilir.

Tetikleme deterministik olmadığından ve ağda herhangi bir yerde birden fazla sayıda jeton bulunabileceğinden, Petri ağları dağıtılmış sistemlerin eşzamanlı davranışını modellemek için uygundur.

Tanım 2. Verilen bir N = (P, T, F ) ağındaki bir konfigürasyon C kümesiyle gösterilir, öyle ki  C ⊆ P.

M : P → Z Z'nin sayılabilir küme olduğu bir yerler çoklu kümesidir. M(not:marking), konfigürasyon konseptini genişletir ve Petri ağlarında genellikle işaretleme(jeton dağılımı) olarak tanımlanır.

W : F → Z bir eğri çoklu kümesidir. Öyle ki, W(not: weight) her eğrinin üzerindeki sayı(yahut eğrinin ağırlığı) eğri katsayısının/çarpanının bir ölçüsüdür.

Bir Petri ağı diyagramında yerler genellikle çember işareti ile, geçişler ise uzunca ve dar dikdörtgenler tarafından, eğriler yerlerden geçişlere yahut geçişlerden yerlere bağlantıları gösteren tek yönlü oklar tarafından modellenir.

Eğer diyagram basit bir ağa ait olsaydı, yerler yine çemberler tarafından gösterilecekti. Ancak bu defa, her bir çember bir jeton içerebilecekti. Yukarıda sağda gözüken Petri ağı ise birden fazla jeton içermektedir. Tüm Petri ağına dağıtılmış jeton konfigürasyonuna, işaretleme adı verilir.

Yukarıda sağdaki resimde, p1 yeri, t geçişinin giriş yeridir; p2 yeri ise aynı geçişin çıkış yeridir. Üst resimde bulunan PN0 Petri ağı, M0 işaretlemesi ile alt resimde bulunan PN1 ağı ise M1 işaretlemesi ile konfigüre edilmiş(yahut işaretlenmiş) olsun. PN0'ın konfigürasyonu, tüm giriş yerleri yeteri kadar sayıda jeton (resimlerde noktalar olarak gösteriliyor) içerdiği için t geçişini etkinleştirir. bir yerin "yeteri kadar jeton" içermesi demek, o yerden geçişe giden eğrinin ağırlığına eşit veya daha fazla sayıda jetona sahip olması demektir. Bir geçiş, sadece ve sadece etkinleştirilmiş ise, tetiklenebilir. Bu örnekte, t 'nin tetiklenmesi(ateşlenmesi) M0' konfigürasyonundan M1 konfigürasyonuna bir geçiş yapılmasını sağlar ve PN1 Petri ağına ulaşılması ile sonuçlanır (sağ üstte, alttaki resim).

Hatırlatma 1. "büyük veya eşittir" tabirinin kesin anlamı, tetikleme kuralındaki toplama işleminin cebirsel kesinliğine bağlıdır. Cebirsel özelliklerdeki farklı varyasyonlar bizi farklı Petri ağı sınıflarına götürebilir. Örneğin: Cebirsel Petri Ağları.

Akış ilişkisi eğrilerin bir kümesidir: . Birçok kitap, eğrilerin ağırlığının yalnızca 1 olabileceğini yazar. Bu yazılar genellikle Petri ağlarını W yerine F' ile tanımlarlar. Bu yaklaşım kullanıldığında, bir Petri ağı iki parçalı multigraf haline dönüşür.

Bir geçişin girdi kümesi(preset) t, o geçişe ait giriş yerlerinin kümesidir: ; Geçişin çıktı kümesi(postset) geçişe ait çıkış yerlerinin kümesidir: . yerlerin girdi çıktı kümelerinin tanımları benzerdir (analoji).

Bir Petri ağının(grafının) işaretlemesi onun yerlerinin bir multisetidir.Yeni, . adreslemesi için, işaretleme her yere belirli sayılarda jeton ataması yapar deriz. .

M işaretlemesindeki(konfigürasyonundaki) bir geçiş için, sadece ve sadece koşulu sağlanıyorsa, yani geçişin giriş yerlerinde tüketim için yeterli jeton varsa geçiş etkinleştirilmiştir (tetiklenebilir/ateşlenebilir).

N'nin ulaşılabilirlik grafı , onun ulaşılabilir işaretlemeleri ile sınırlanmış geçiş ilişkileridir . Bu, ağın durum uzayıdır. (özetle, ağın alabileceği tüm durumları gösteren kümedir)G grafına ve' 'ilk durumuna sahip bir Petri ağındaki ateşleme sekansı (ya da sıralı ateşleme kümesi)' 'ile gösterilir. Öyle ki;'. Burada tetikleme sekanslarının kümesi ile gösterilmiştir.

Daha önce de belirtildiği gibi, tanım farklılıklarının en genel olanı, eğri ağırlıklarını göz ardı etmek ve W ile gösterilen eğriler multisetini, ile gösterilen ve akış ilişkisi olarak adlandırılan bir basit küme ile değiştirmektir. Bu ifade gücünü (expressive power) sınırlandırmaz, her ikisi de birbirleri yerine kullanılabilir.

Genel olarak kullanılan bir diğer farklılık da, Desel ve Juhás (2001)'ın da kullandığı üzere, kapasitelerin yerler üzerinde tanımlanmış olmasına izin verilmesidir. Aşağıda ekler bölümünde bu konu tartışılmıştır.

, 'ye ait bir ateşleme sekansı'dır..w'''nin bir ateşleme sekansı olması gerektiğine dikkat edin; geçişlerin rastgele tetiklenmesine izin vermek, genellikle daha büyük bir küme oluşturur.