Alfa algoritması - Alpha algorithm

α algoritması kullanılan bir algoritmadır süreç madenciliği, bir dizi nedenselliği yeniden inşa etmeyi amaçlamaktadır. olay dizileri. Tarafından ortaya atıldı. van der Aalst, Weijters ve Măruşter.^[1] O zamandan beri, aşağıda listelenecek olan çeşitli uzantıları veya modifikasyonları sunulmuştur.

Oluşturur P / T ağları özel özelliklere sahip (iş akışı ağları ) olay günlüklerinden (bir ERP sistemi). Ağdaki her geçiş, gözlemlenen bir göreve karşılık gelir.

Kısa Açıklama

Algoritma bir iş akışı günlüğü alır ${ displaystyle W subseteq T ^ {*}}$ girdi olarak ve bir iş akışı ağının oluşturulmasına neden olur.

Bunu, görevler arasında gözlemlenen nedensel ilişkileri inceleyerek yapar. Örneğin, her yürütme izlemesinde belirli bir görev her zaman başka bir belirli görevden önce gelebilir ve bu da yararlı bilgiler olabilir.

Kullanılan tanımlar

• Bir iş akışı izleme veya yürütme izi bir dizi bir alfabe ${ displaystyle T}$ nın-nin görevler.
• Bir iş akışı günlüğü bir dizi iş akışı izlemesidir.

Açıklama

Algoritma açıklayıcı olarak şu şekilde sunulabilir. 3 görev grubu belirlenir:

• ${ displaystyle T_ {W}}$ en az bir izlemede gerçekleşen tüm görevlerin kümesidir
• ${ displaystyle T_ {I}}$ başlangıçta gerçekleşen tüm görevler kümesidir
• ${ displaystyle T_ {O}}$ iz-terminal olarak gerçekleşen tüm görevler kümesidir

Temel sipariş ilişkileri belirlenir (${ displaystyle succ _ {W}}$ birincisi, son üçü buradan inşa edilebilir)

• ${ displaystyle a succ _ {W} b}$ iff ${ displaystyle a}$ doğrudan önce gelir ${ displaystyle b}$ bazı izlerde
• ${ displaystyle a rightarrow _ {W} b}$ iff ${ displaystyle a succ _ {W} b wedge b not succ _ {W} a}$
• ${ displaystyle a # {} _ {W} b}$ iff ${ displaystyle a not succ _ {W} b wedge b not succ _ {W} a}$
• ${ displaystyle a Vert _ {W} b}$ iff ${ displaystyle a succ _ {W} b wedge b succ _ {W} a}$

Yerler keşfedildi. Her yer bir çift setleri yer sayısını düşük tutmak için görevler.

• ${ displaystyle Y_ {W}}$ tüm çiftlerin kümesidir ${ displaystyle (A, B)}$ maksimal görev kümelerinin
  • Hiçbiri ${ displaystyle A times A}$ ve ${ displaystyle B times B}$ herhangi bir üyesini içerir ${ displaystyle succ _ {W}}$ ve
  • ${ displaystyle A times B}$ alt kümesidir ${ displaystyle rightarrow _ {W}}$
• ${ displaystyle P_ {W}}$ bir yer içerir ${ displaystyle p _ {(A, B)}}$ her üyesi için ${ displaystyle Y_ {W}}$artı giriş yeri ${ displaystyle i_ {W}}$ ve çıkış yeri ${ displaystyle o_ {W}}$

Akış ilişkisi ${ displaystyle F_ {W}}$ aşağıdakilerin birleşimidir:

• ${ displaystyle {(a, p _ {(C, B)}) | (A, B) in Y_ {W} kama a A }}$
• ${ displaystyle {(p _ {(A, B)}, b) | (A, B) in Y_ {W} kama b B }}$
• ${ displaystyle {(i_ {W}, t) | t T_ {I} }} içinde$
• ${ displaystyle {(t, i_ {O}) | t içinde T_ {O} }}$

Sonuç

• a Petri ağı yapı ${ displaystyle alpha (W) = (P_ {W}, T_ {W}, F_ {W})}$
• tek giriş yeri ile ${ displaystyle i_ {W}}$ ve bir çıkış yeri ${ displaystyle o_ {W}}$
• çünkü her geçiş ${ displaystyle T_ {W}}$ üzerinde ${ displaystyle F_ {W}}$-den yol ${ displaystyle i_ {W}}$ -e ${ displaystyle o_ {W}}$gerçekten bir iş akışı ağıdır.

Özellikleri

Gösterilebilir ^[2] tarafından oluşturulan eksiksiz bir iş akışı günlüğü olması durumunda ses SWF ağı onu oluşturan ağ yeniden inşa edilebilir. Komple demek, ${ displaystyle succ _ {W}}$ ilişki maksimaldir. Bu değil tüm olası izlerin mevcut olmasını gerektirdi (döngü içeren bir ağ için sayılabilir bir şekilde sonsuz olacaktır).

Sınırlamalar

Genel iş akışı ağları birkaç tür yapı içerebilir ^[3] α-algoritmasının yeniden keşfedemediği.

Bu bölüm genişlemeye ihtiyacı var. Yardımcı olabilirsiniz ona eklemek. (Mayıs 2010)

İnşaat ${ displaystyle Y_ {W}}$ görev sayısında üstel zaman alır, çünkü ${ displaystyle succ _ {W}}$ kısıtlı değildir ve keyfi alt kümeleri ${ displaystyle T_ {W}}$ dikkate alınmalıdır.

Uzantılar

Bu bölüm genişlemeye ihtiyacı var. Yardımcı olabilirsiniz ona eklemek. (Mayıs 2010)

Örneğin ^[4][5]

Referanslar