DEFINISI-DEFINISI DASAR
2.1. TEORI BAG Teori bag merupakan perluasan yang murni. dari teori himpunan. Bag merupakan sekumpulanelemen dari domain tertentu. Tidak seperti himpunan, bag membolehkankemunculan yang lebih dari sekali dari setiap elemennya. Contoh : B1
=
{a, b, c}
B2
=
B3
=
{a} {a, p, c, c}
B4
D
=
{a, a, a}
ra
a, a, a, b, b, c, c, d, d, d, d}
-- --
Konsep dasar dari teori bag adalah fungsi jumlah kemunculan, sedangkan pada teori himpunan, konsep dasarnya adalah hubungan "adalah anggota dan"'. Fungsi jumlah I;cemunculanmendefinisikan jumlah kemunculan dari suatu elemen yang berada dalarn suatu bag. Untuk suatu elemen 'X dari suatu bag B, di notasikan jumlah kemunculan x di B sebagai # (x, B), di ucapkan sebagai jumlah x di B. Dengan basis konseptual ini, kita mendefinisikan dasar-dasar dari teori bag.
2.1.1 Keanggotaan Fungsi # (x, B) mendefinisikanjumlah kemunculan dari suatu elemen x di bag B. Karenanya, # (x, B) ~ 0 untuk semua x dan B. Suatu elemen x merupakan anggota dari suatu bag B jika # (x, B) > O. Hal ini' di notasikan sebagai x E B. -Dengancara yang sarnajika # (x, B) = 0, maka
x E B.
Didefinisikan suatu bag kosong atau { } atau 0 dimana untuk semua x, # (x, 0 ) = O. 8
2.1.2 Cardinality Cardinality I B I dari suatu bag B adalah jumlah ~e.munculantotal dari elemen-elemen dalam bag tersebut, sehingga : IB I=
L #(x,B) x
2.1.3 Inclusion dan Kesamaan Bag Suatubag A adalahsub bag dari suatubag B jika setiapelemen dari A juga merupakanelemendari B, paling sedikitbeberapakali : A c B jika dan hanya jika #(x, A) ::;;#(x, B) untuk semua x (A B) jikaJUx...A1-= # (x..B) untuls;semua x.
=
Dari kedua definisi diatas, dapat diperoleh : A
= B, jika
dan hanya jika A c B dan B c A
oc
B untuk semua bag B Jika A =B maka IAI+ IBI Jika A c B maka IAI ::;;IBI
Suatu bag A disebut Strictly Contained pada suatu bag B (A. c B) jika A c B dan A
* B.
Ingat bahwa jika # (x, A) < # (x, B) tidak selalu A c B, walaupun IAI< IBI
2.1.4
Operasi - operasi
Empat jenis operasi yang di detinisikan pada bag. Untuk bag A dan B, di detinisikan : a. Gabungan , dinotasikan sebagai A u B #(x, u B) = max (# (x, A), # (x, B)) 9
b.
Irisan,
dinotasikan sebagai A (1 B #(x, A (1 B)
c.
Penambahan,
= min
(# (x, A), # (x, B»
dinotasikan sebagai (A + B)
# (x, A + B) = # (x, A) + # (x, B) d.
Selisih, dinotasikan sebagai (A - B)
# (x, A - B) =# (x, A) - # (x, B). Operasi-operasi gabungan, irjsan, dan penambahan adalah komutatif
dan asosiatif. Pada operasi penambahan dapat disimpulkan
:
A(1BcAcAuB
A-BcAcAcA+B
Perbedaan ant3!a ~perasi gabungan dan operasi penambahan secara
jelas dinyatakanberikut ini. I Au
BI S; IAI +olBI
IA + BI = IAI +
2.1.5. Ruang
Dimensi
IBI
dari Bag
Di definisikan suatu Domain D sebagai himpunan dari elemen-elemen dalam mana bag-bag dibentuk. Ruang dari bag Dn adalah himpunan dari semua bag yang seluruh elemennya ada di D demikian sehingga tidak terdapat elemen yang muncullebih dari n kali. Jadi, untuk semua B E Do; a. Jika x E B maka xED b. # (x, B) S; n untuk semua x.
10
Himpunan D- adalah himpunan dari semua bag atau suatu domain D dimana tidak terdapat batas jumIah kemunculan dari suatu elemen yang berada dalam suatu bag.
2.1.6. Pemetaan Parikh Untuk suatu domain sehingga D
= {d"
~,
, dn}, terdapat suatu korespondensidiantarasetiapbag B atas D dan n - vektor,f =( fl' f2, , fn) yang di definisikan oleh
=#(d.,B)
f. I
I
Vektor ini dikenal sebagai pemetaan Parikh.
Contoh Ambil D berikut ini :
= {a, b,
c, d} sebagai suatu domain maka dari bag-bag A= {a, b} B = {a, a, b, c} C = {a, a, a, c, c}
diperoleh : IAI = 2 ICI
Au B A u C
=3
= { a, a, b, c}
= {a,
A f1 C
Bf1C=
a, a, b, c, c}
= {a} {a,a,c} 11
A +B
=
{a, a, a, b,
b,
c}
A-B=0 C
- A
=
{a, a, c, c}
C-B={a,c}
2.2.STRUKTUR
JARINGAN
PETRI
Jaringan Petri
terdiri dari 4 bagian, yaitu : himpunan dari place-place P, himpunan dari transisi-transisi T, fungsi input I, dan fungsi output O. Fungsi - fungsi input dan output menghubungkantransisi-transisidan placeplace. Fungsi input I merupakan pemetaan dari transisi tj ke sekumpulan places I(tj), yang di kenai sebagai input places dari transisi. Fungsi output o memetakan suatu transisi tj ke sekumpulan places O(tj) yang di kenai sebagai output places dari transisi. Struktur dari suatu Jaringan Petri di definisikan oleh places, transisi, fungsi input dan fungsi output adaIah berikut ini : Def;n;s; 2.1 Struktur laringan
Petri, C, merupakan 4
-
tupple C
= (P,
T, I, 0),
dimana:
= {P\P2""'Pn} merupakan himpunan berhingga dari place-place, n ;;::0; T = {tl' tz, tm} merupakan himpunan berhingga dari transisi-transisi, P
m;;::O;
Himpunan dari place-place dan transisi-transisi adalah disjoint atau P (\ T
=0.
I: T
P- adaIahfungsi input, pemetaan dari transisi-transisi ke bags dari
~
place-place.
o :T
~
P- adaIahfungsi
dari places. 12
output, pemetaan dari transisi-transisi ke bags
Kardinalitas dari himpunan P adalah n dan kardinalitas dari himpunan T adalahm. Notasidari satu elemeIidari P adalahPi' i = 1, 2, , n dan satu elemen dari T adalah t., J j = 1, ...,m. Contoh dari struktur J aringan Petri : a)
c P
= {P, T,
I, O}
= {Pl'P2,P3,P4'PS} T = {tl't2,t3,t4}
l(t1) = {PI}
0(t1) = { P2,P3'PS}
l(t2) = {P2,P3'PS}
0(t2) = {Ps} 0(t3) = {P4}
1(t3) = {P3}
0(t4) = {P2,P3}
1(t4) = {P4}
b)
c = {P, T, I, O} P = {Pl'P2,P3,P4PS,P6} T = {tl't2,t3,t4,tS}
I(tI) I(~)
= {PI} = {P3}
l(t3) = {P2'p3}
0(t2)
= { P2,P3} = {P3,P3'PS}
0(t3)
= {P2'P4}
O(tI)
1(t4)
= {p 4Ps,PS'Ps}
0(t4)
= {P4}
l(ts)
= {P2}
O(ts)
= {P6} 13
Suatu place Pi adalah suatu Place Input dari suatu transisi tj jika Pi E I(tj); Pi adalah suatu Place Output jika pi E O(tj). Input dan output dari suatu transisi merupakan bags dari place-place. Bag adalah generalisasi dari himpunan yang memperkenankanbanyak kemunculan dari satu elemen dalam suatu bag. Place Piadalah input place dari transisi tjjika PiE O(tj). Place Piadalah output place dari transisi tjjika Pi E O(tj). pemakaian bag untuk input dan output dari suatu transisi memperkenankan suatu place menjadi multiple input atau multiple output dari suatu transisi. Multiplicity dari suatu input place Piuntuk suatu transisi tj adalahjumlah kemunculan dari place tersebut pada input bag dari transisi atau # (Pi' I(tj)). Demikian juga untuk multiplicity dan suatu output place Pi untuk suatu transisi tj. # (Pi' O(tj)). Fungsi-fungsi input dan output dapat diperluas. yang bermanfaat untuk memetakanplace-placeke bag-bagdari transisi-transisi.Kita tentukanbahwa suatu transisi tj menjadi input dari suatu place Pijika Pi merupakan output dari tj' Transisi tj adalah output dari place Pi jika Pi merupakan input dari tj'
Definisi 2.2. Perluasan dari fungsi input I dan fungsi output 0 adalah sebagai berikut:
demikian sehingga
#(tj. I(p)) #(tj. O(p))
14
= # (Pi' O(tj))
=# (Pi' I(tj))
Contoh : Diberikan suatu struktur jaringan petri C = {P, T, I, O} P = {PI'PZ,P3,P4PS,P6} T = {tl'tZ,t3,t4,tS}
l(t)) = {PI}
OCt)) = { PZ,P3}
l(tz) = {P3}
O(tZ) = {P3,P3'PS}
l(t3) = {PZP3}
0(t3) = {PZ,P4}
l(t4) = {P4Ps,Ps'ps}
0(t4) = {P4}
l(ts) = {pz}
O(tS) = {P6)
.
KarenaPI E I (tl),
.
Karena Pz, P4 E 0 (tz), maka Pz dan P4 adalah output place dari transisi tz.
.
# (Ps'l(t4)= 3, artinyajumlahkemunculandariplacePspadainputbag dari transisi t4
maka pI adalah input place dari transisi t\.
=3
.
# (Ps' O(tz))
.
Perluasandari fungsiinput I dan fungsioutput 0 adalah :
=2, artinyajumlah kemunculan dari place Ps pada output bag dari transisi tz = 2. 1(t1) = {}
O(PI)
l(Pz) = {t I't3}
O(Pz)
= { tl}
=
= {t3,tS} 0(P3) = {tz,t3}
]](t4)
= {tZt4}
0(P4)
::
l(ps)
= {tz,tz}
O(ps)
= {t4,ti4}
1(P3) {tl ,t2}
1(P6)= {ts}
{t4)
O(p~ = {}
15
2.3. GRAPH DARI JARINGAN PETRI Representasi grafik suatu struktur Jaringan Petri sangat bermanfaat untuk mengilustrasikan konsep-konsep dari teori Jaringan Petri. Grafik suatu Jaringan Petri merupakan representasi suatu struktur Jaringan Petri sebagai suatu multigraf berarahbipartit. Struktursuatu Jadngan Petri terdiri dari himpunan place-place dan himpunan transisi-transisi. Bersesuaian dengan hal ini maka grafik suatu Jaringan Petri memiliki 2 jenis node : a. Lingkaran 0 menyatakan suatu place; b. gads vertikal I menyatakan suatu transisi. Arkus-arkus berarah yang menghubungkan place-place dan transisitransisi, dimana beberapa arkus berarah dad place-place ke transisi-transisi dan arkus-arkus berarah lainnya dari transisi-transisi ke place-place. Satu arkus berarah dari place pi ke transisi tj menyatakan bahwa place tersebut merupakan input dari transisi tj" Banyaknya input ke satu transisi ditunjukkan dengan banyaknya arkus dad suatu input place ke transisi tersebut. Satu output place ditunjukkan oleh satu arkus dad transisi ke place. Banyaknya output dinyatakan dengan banyaknya arkus. Jadngan Petri merupakan multi graph karena diperkenankan.terdapat banyak arkus dad satu node pada grafik ke node lainnya. Selain itu, karena arkus-arkus tersebut berarah maka disebut sebagai multi graph berarah. Karena node-node dad graph tersebut dapat dipartisi menjadi 2 himpunan (place-place dah transisi-transisi) demikian sehingga setiap arkus berarah dad satu elemen yang merupakan anggota dad himpunan place atau transisi ke suatu elemen yang menjadi anggota himpunan lainnya maka graph tersebut disebut sebagai multigraph berarah bifartit. Untuk singkatnya disebut Graph Jaringan Petri
16
Definisi 2.3
Graph Jaringan Petri G adalah multigraph berarah bipartit, G =(V, A), dimana V
= {vI' v2'
=
Vs) adalah himpunan verteks dan A {al' ~, ar) adalah bag dari arkus-arkus berarah, aj (vj, vk) dengan vj' VI' E V.
=
Himpunan V dapat dipartisi menjadi 2 himpunan saling lepas P dan T demikian sehingga V =PuT, P (J T =0, dan untuk setiap arkus berarah, aj E A, jika aj (vj, vk) maka vj E P dan vk E T atau Vj E T
=
dan vk E P.
Contoh : Diberikan struktur suatu Jaringan Petri : C = (P, T, I, 0) P = {PI' P2' P3' P4' PS' P6' P7' Pg, P9}
T
= {tt' S'
I(tt)
= {Pt}
O(tt)
I(S)
= {Pg}
0(t2)
I(t3)
= {P2' Ps}
0(t3)
I(t4) = {P3}
0(t4)
= {P6' P7}
O(ts)
I(t6) = {P4'P9}
0(t6)
I(ts)
a.
S, t4, ts' t6}
= {P2' P3} = {PI' P7} = {P6) = {P4) = {P9} = {Ps' Pg }
Perluasan dari fungsi input I dan furtgsi output 0 adalah :
I(pt) == {S}
O(pt) = {tl}
I(P2) = {tt}
0(P2) = {S} 17
= {t1} I(P4) = {t4}
I(P3)
0(P3) 0(P4)
= {t4} = {t6}
I(ps)
= {t6}
O(PS) = {S}
I(P6)
= {S}
0(P6)
= {tS}
0(P7)
= {tS}
= {S} I(ps) = {t6} I(P9) = {ts} I(P7)
O(PS)
0(P9)
= {S} = {t6}
b. Graph dari Jaringan Petri-nya digambarkan pada gambar 2-1. berikut 1m.
Gambar 2.1. Contoh penggambaran suatu Graph Jaringan Petri
Definisi 2.4 Ditentukan V
= PuT.
A adalah suatu bag dari arkus-arkus berarah
demikiansehinggauntuk semuap 1 E P dan ~E T # ((Pi' tj), A) # ((tj, Pi)' A) 18
=# (Pi' l(tj» = # (Pi' 0(9)
G
=(V, A) adalah graph Jaringan Petri yang ekivalen dengan struktur
JaringanPetri C = (P, T, I, 0).
Dual dari suatu Jaringan Petri C = (P, T, I, 0) adalah Jaringan Petri.
C =(T, P, I, 0) yang merupakanhasil dari salingmenukarkanplace-place dan transisi-transisi. Contoh : Diberikan suatu struktur Jaringan Petri : C
= (P, T, I, 0)
= {pI,
P
T I(tt)
= {Pt}
1(12)
= {Pz'
I(S)
= {P3}
l(t4)
= {p4}
Pz, P3' P4' Ps}
= {tl'
12, S, t4}
= {pz, P3' Ps} O(tz) = {Ps} 0(t3) = {P4) 0(t4) = {p2, p3)
O(tt) P3' Ps}
a. Dual dari Jaringan Petri dari C C
T
= (P, T,
I, 0) nya adalah :
= (T, P, I, 0)
= {tl' 12,S, t4, ts}
P = {PI' Pz, P3' P4} I(pt) = {tt}
O(Pt) = {1:z,t3, ts}
I(pz) = {1:z,S, ts}
O(Pz) = {ts}
I(P3) = {S}
0(P3) = {t4)
l(p4) = {t4}
0(P4) = {1:z,S)
19
b. Graph Jaringan Petri-nya digambarkan pada gambar 2-2, berikut ini.
Pl
Gambar 2-2. Graph dari Jaringan Petri contoh. c. Graph dual Jaringan Petri-nya adalah mengganti place menjadi transisi dan transisi menjadi place digambarkan pada gambar 2-3.
Gambar 2-3. Graph Dual Jaringan Petri dari contoh. 20
Inverse Jaringan Petri, - C, untuk suatu Jaringan Petri C =(P, T, I, 0) di detinisikan dengan saling menukarkan fungsi-fungsi input dan outputnya, - C (P, T, 0, I)
=
d. Inverse Jaringan Petri dari contoh
O(tl)
= {PI}
I(tl)
= {P2' P3' Ps}
0(t2)
= {P2' P3' Ps}
I(t2)
= Ips}
0(t3)
= {P3}
I(t3)
= {P4)
0(t4)
= {P4}
l(t4)
= {P2' P3)
2.4. MARKING JARINGAN PETRI Marking Jl adalah pemberian token-token ke place-place dari suatu Jaringan Petri. Jumlah dan posisi dari token-token dapat berubah selama eksekusi terhadap suatu Jaringan Petri. Token-token ini digunakan untuk mendetinisikan eksekusi dari suatu Jaringan Petri.
Definisi 2-5 Suatu marking Jl dari suatu JaringanPetri C
= (P, T, I, 0)
adalah fungsi dari himpunan place-place P ke bilangan Integer non negatif N. Jl:P-7N Marking Jl juga dapat didetinisikan sebagai suatu N-vektor, atau Jl = (Jll' ~, , Jln),dimana n = IPIatau setiap JliE N, i =1,2,3, , n. Jumlah token dalam place Pi adalah ~,
21
i = 1,2, ..., n. Definisi dari suatu marking sebagai suatu fungsi dan sebagai
suatu vektor dihubungkansecarajelas dengan J.l(Pi)= J.lj.
Suatu JaringanPetri bertandaM = (c, J.l)adalah suatu struktur Jaringan Petri C =(P, T, I, 0) dengansuatumarkingJ.l,dan ditulissebagaiM =(P, T, I, 0,. J.l). Pada graph suatu Jaringan Petri, token-token dinyatakan sebagai titiktitik yang berada dalam lingkaran-lingkaran yang menyatakan place-place dari suatu Jaringan Petri. Karena jumlah token yang dapat diberikan ke suatu place adalah tak terbatas maka terdapat suatu sifat ketidak berhinggaan dari marking-marking untuk suatu Jaringan Petri. Himpunan dari semua marking-marking untuk suatu Jaringan Petri dengan n place secara mudah dapat dinyatakan sebagai himpunan semua n-vektor, atau N°. Contoh : Suatu jaringan petri bertanda M C
P
= (P, T, I, 0,
J.l)
= (P, T, I, 0)
= {PI'
P2' P3' P4' ps}
T= {tl' S' t3, t4} I(ti) = {Pi}
O(ti) = {P2' P3' Ps}
I(S) = {P2' P3' Ps}
0(t2) = {Ps}
I(S) = {P3}
O(S) = lp4)
l(t4) = {P4}
0(t4) = {P2' P3)
Representasi graph dari Jaringan Petri bertanda ini digambarkan pada gambar 2-4 berikut ini
22
Gambar 2-4. Graph dari suatu Jaringan Petri bertanda. Representasi graph dari suatu Jaringan Petri.untuk menyatakan : .
Jumlah arkus berarah dari suatu transisi ke suatu place atau sebaliknya, jika banyak dapat dinyatakan seperti gambar 2-5 berikut ini.
Gambar 2-5.
.
Gambar untuk merepresentasikanjumlah arkus yang banyak pada suatu Jaringan Petri
Jumlah token yang terdapat pada suatu place jika banyak dapat dinyatakansepertigambar2-6, berikutini.
Gambar 2-6.
Gambar untuk merepresentasikan jumlah token yang banyak, misal n = 100. . 23
2.5.ATURAN-ATURAN EKSEKUSI JARINGAN PETRI Eksekusi dari suatu Jaringan Petri dikontrol oleh jumlah dan distribusi dari token-token yang terdapat pada Jaringan Petri tersebut. Suatu Jaringan Petri melakukan eksekusi dengan menembak (firing) transisi-transisi dari Jaringan Petri tersebut. Penembakan (firing) suatu transisi adalah' dengan cara "memindahkan" token-token dari place-place input dan "membuat" token-token bam yang disebarkan ke place-place outputnya. Suatu transisi dapat ditembak jika transisi tersebut Enabled. Suatu transisi adalah enabled jika setiap place inputnya paling sedikit merniliki token yang sarna banyaknya dengan arkus dari place ke transisi tersebut. Contoh : Jika input place ke transisi t4 adalah place-place PI dan P2 maka t4 dikatakan enabled apabila PI paling sedikit merniliki satu token dan paling sedikit P2 juga merniliki satu token, untuk transisi t7 dengan input bag {P6,P6,P6} maka place P6 paling sedikit hams merniliki 3 token untuk membuat transisi t1 enabled.
Definisi 2 - 6 Suatu transisi tj E T pada suatu Jaringan Petri bertanda M 0, Jl) adalah enabled jika untuk semua Pi E P.
=(P, T, I,
Jl (pi) ( # (pi, I(tj»
Token-token pada place-place input yang membuat suatu transisi enabled disebut sebagai enabling token. Suatu transisi ditembak dengan melakukan "pernindahan" token-token enabling dari place-place input dan kemudian mendepositokan ke setiap place output satu token untuk setiap arkus dari transisi tersebut ke place.
24
Contoh :
Suatu transisi S dengan l(t3) = {P2} dan 0(t3) = tJJ7'P13}adalah enable bilamana terdapat paling sedikit satu token di place P2' Transisi t3 ditembak dengan melakukan pemindahan satu token dari place P2,dan mendepositokan satu token di place P7 dan satu token di place P13' Suatu transisi t2 dengan l(t2)=P21,P23}dan O(t2)=P23,P2S,P2S} ditembak dengan melakukan pemindahan satu token dari P21 dan satu token dari P23 dan kemudian mendepositokan satu token ke P23 dan dua token ke P2S'
Penembakan suatu transisi secara umum akan merubah marking J.1 dari Jaringan Petri ke suatu marking barn, J.1'.
Definisi 2
-7
Suatu transisi tj pada suatu Jaringan Petri bertanda dengan marking J.1 dapat ditembak jika transisi tersebut enabled. Penembakan suatu transisi yang enabled t.J mengakibatkan suatu marking barn J.1'yang didefinisikan oleh.
J.1'(pi)
= J.1(pi)- # (pi, I(tj» + # (pi, O(tj»
Ilustrasi bagaimana marking dari suatu place berubah bila suatu transisi t.J o ditembak digambarkan pada gambar 2-6..
25
8
1l'(PI) = Il(PI)
Gambar 2-6.
I1ustrasi tentang perubahan marking dari suatu .place bila suatu transisi ditembak.
Terdapat 3 transisi yang enabled, yaitu tl' ~ dan t4. Transisi S tidak enabled karena tidak terdapat token pada place-place P2 dan P3' padahal I(S) = {P2' P3' P4}' Salah satu dari transisi yang enabled tl' t3 dan t4 dapat ditembak. Misalkan transisi t4 ditembak maka dilakukan pemindahan satu token di place Ps dan mendepositokan satu token ke place P3 dan satu token ke place P4sehingga menjadi 3 buah token. Jadi, marking barn yang merupakan
hasil penembakan
transisi
t4 adalah
J.l'
= (1,
0, 1, 3, 0).
Refresentasi graph dari Jaringan Petri bertanda dengan marking yang barn menunjukan bahwa hanya transisi-transisi tl dan ~ yang enabled. Dengan melakukan penembakan transisi tl' misalnya, maka akan diperoleh marking terbarn J.l" (0, 1, 2, 5, 0).
=
Penembakan terhadap transisi-transisi dapat dilanjutkan terus selama masih terdapat paling sedikit satu transisi yang enabled. Bila sudah tidak ada transisi yang enabled maka eksekusi dihentikan. 26
2.6. RUANG STATA DARI JARINGAN PETRI Stata dari suatu Jaringan Petri ditentukan oleh marking dari Jaringan Petri tersebut. Penembakan terhadap suatu transisi menyatakan satu perubahan pada stata dari Jaringan Petri tersebut dengan adanya perubahan marking dari Jaringan Petri. Ruang Stata dari suatu Jaringan Petri dengan n place adalah himpunan dari semua marking, yaitu Nn. Perubahan Stata yang diakibatkan oleh penembakan suatu transisi didefinisikan oleh suatu fungsi perubah yang disebut flmgsi next-stata, yaitu N1.
Bila diaplikasikanke suatumarking(stata)J.1 dan suatutransisit.maka J fungsi menghasilkan marking (stata) barn akibat dari penembakan transisi tj pada marking J.1.Karena tj' hanya dapat ditembak jika transisi tersebut enabled maka (J.1, 9 =J.1',dimana J.1'adalah marking yang merupakan hasil pemindahan token-token dari place input t.J dan penambahan token-token ke place-place output tj'
Definisi 2 - 8 Fungsinext-stataa: N°X T ~ N° untuk suatu Jaringan Petri C = (P, T, I, 0) dengan marking
J.1
dan transisi tj ( T terdefinisi jika dan hanya jika
9 terdefinisi maka 8(J.1, tj) =
untuk semua Pi ( P. Jika 8(J.1,
J.1'
dimana
untuk semua Pi E P.
J.10
Diberikan suatu Jaringan Petri C =(P, T, I, 0) dan suatu marking awal maka Jaringan Petri tersebut dapat dieksekusi dengan melakukan 27
penembakan terhadap transisi-transisi yang enabled. Penembakan suatu
transisi yang enabled tj pada penandaan awal
Jlo
menghasilkansuatu
penandaan barn Jl2=qJl', ~). Padamarkingyangbarn ini,dapatdilakukan penembakan terhadap suatu transisi yang baru dan enabled, sebut tk'
menghasilkansuatumarkingbarn Jl1 =0 (Jl0, 9 Hal ini berlangsungterns
hingga tidak terdapat sarna sekali transisi yang enabled pada marking yang terbarn.
Terdapat dua barisan yang mernpakanhasil dari eksekusi suatu Jaringan Petri, yaitu : a) barisan dari marking-marking (Jlo,Jll, Jl2,...)dan b) barisan dari transisi-transisi yang ditembak (tjO' ~l' tj2,... ). Kedua barisan dikaitkan dengan hubungan a(Jlk, tjk)
k
= 0,1,2, ...
= Jl k+1 untuk
Dengan diketahui suatu barisan transisi yang ditembak dan marking
awal
Jlo
maka dapat dicari barisan marking untuk eksekusi dari Jaringan
Petri tersebut.
Definisi 2 - 9 Untuk suatu Jaringan Petri bertanda M =(P, T, I, 0, Jl), suatu marking Jll segera dapat dicapai dari Jl jika terdapat suatu transisi tj E T demikian sehingga
d (Jl, tj)
= Jl1.
Jika Jl1segera dapat dicapai dari Jl dan Jl" segera dapat di capai dari Jl1maka Jl" dapat dicapai dari Jl. Suatu marking Jl1 E R(C, Jl) jika terdapat sebarisan transisi yang ditembak yang akan mengubah marking Jl menjadi marking Jl1.
Definisi 2 - 10 Himpunan ke-marnpu-capaian R(C, Jl) untuk suatu jaringan petri 28
bertanda M = (P, T, I, 0, J.l) adalah himpunan terkecil dari markingmarking yang didetinisikan oleh : 1) J.l ( R(C, J.l) 2) Jika J.l1E R(C, J.l)dan J.l"
=OXJ.ll' tj) untUk tj E T, maka J.l" E R(C,J.l)
Contoh representasi graph suatu Jaringan Petri bertanda, gambar 2-7..
{.
'0
PI
Gambar 2-7. Representasi Graph suatu Jaringan Petri Bertanda. Marking awalnya adalah J.l = (1, 0, 0). Terdapat 2 transisi yang dapat ditembak, yaitu t1 dan tr Dengan melakukan penembakan terhadap transisi t1 diperoleh marking (1, 0, 1). Jika t2 ditembak diperoleh marking (0, 1, 0).
Pada marking (0, 1, 0) tidak terdapat transisi yang enabled, karenanya tidak ada marking yang dapat dicapai. Pada marking (1, 0, 1) terdapat transisi t1 dan t2 yang dapat ditembak, yang secara berturutturut menghasilkan marking (1, 0, 2) dan (0, 1, 1). Hal ini dapat di lanjutkan terus dengan menggunakan tehnik pohon ke-mampu-capaian akan diperoleh himpunan kemampu-capaian R(C, J.l)yaitu : R(C, J.l) = {(1, 0, n), (0, 1, n) I ~ n ( O} Untuk sebarisan transisi t'l,t'2,t'3'''. .dan marking J.lmaka marking ) merupfuc~n hasil penembakan secara ber-turut.. d turut an tranSlsl-tranSlSl tjl'tj2'tj3'.... J.l1
= J(J.l,,JJ.l. t'l't'2,t'3''''
29
Definisi 2
- 11
Fungsi Next-Stata yang diperluas yang didefinisikan untuk suatu
marking f.1 dan sebarisantransisicr E T adalah E (f.1, tj cr)
= a( a(f.1,tj), cr )
a(f.1,A) = f.1
30
