KOMPLEKSITAS DAN DECIDABILITY
Pada bab sebelumnya kita telah membahas sejumlah masalah tertentu bagi jaringan petri Masalah-masalah ini konseern terhadap berbagai sifat dari struktur Jaringan Petri dan prilaku yang, dalam konteks yang tepat, akan menarik bagi para pemakai Jaringan Petri. Terdapat dua teknik penyelesaian yang dibicarakan: pendekatan Reachability Tree dan pendekatan persamaan Matriks. Kedua teknik ini berlaku untuk sifat-sifatsafeness, boundedness, conservation dan coverability. Juga, satu kondisi perlu untuk reachability telah ditentukan. Namun, semua teknik analisa ini tidaklah cukup untuk menyelesaikan beberapa masalah lain, khususnya liveness,reachability dan equivalence. Pada bab ini kita eksplorasi semua masalah ini untuk memdapatkan penyelesaian atau paling sedikit untuk mempelajari lebih lanjut tentang sifat-sifat dari Jaringan Petri.
5.1. KEMAMPU REDUKS/AN D/ANTARA MASALAH-MASALAH ANAL/SA. Satu konsep dasar yang kita pergunakan adalah Kemampureduksian, atau Reducibility. Penyelesaian satu masalah adalah dengan mereduksikan masalah tersebut kedalam masalah lain yang telah kita ketahui cara untuk menyelesaikannya. Sebagai contoh ,masalah untuk menentukan apakah suatu Jaringan Petri adalah conservative yaitu dengan mereduksikan masalah conservative menjadi masalah untuk mencari penyelesaian dari persamaan- persamaan tinier. Masalah untuk menyelesaikan himpunan-himpunan dari persamaanpersamaan linier ini direduksi lagi ke sederetan operasi-operasi aretmatik tertentu (penjumlahan, pengurangan, perkalian, pembagian dan pembadingan). Jadi, dikarenakan operasi-operasi aritmatika sederhana tersebut dapat dihitung maka conservation dapat ditentukan. Masalah lain yang menarik adalah masalah kesamaan (equality) dan subhimpunan dari himpunan-himpunan reachability.
Definisi 5.1. Masalah kesamaan. Diketahui dua Jaringan Petri Bertanda awal ~} dan. Jaringan Petri Bertanda C2
C}
= (PI'TI' 11' OJ) dengan marking
= (P2,T2'12,02) dengan marking awal
~. Apakah R(CI = R(C2,~) ?
Definisi 5.2. Masalah Subhimpunan. Diketahui dua Jaringan Petri Bertanda C} = (Pl,TI' 11' OJ) dengan marking awal ~' danJaringan Petri Bertanda C2 = (P2,T2' 12, 02) dengan marking awal
~. 124
Apakah
R(C} ,~}) ~ R(C2,~)
?
Kedua masalah diatas menjadi sangat penting jika Jaringan Petrinya dioptimalkan atau jika Jaringan Petd dari kedua sistem dibandingkan. Namun, ingat bahwa jika suatu penyelesaian terhadap masalah Subhimpunan dapat diketemukan maka masalah Equality juga dapat diselesa~an. Jika kita ingin menentukan Apakah R(C1 ,f.ll) = R(C2,f.l2)' maka pertama-tama digunakan algoritma masalah Subhimpunan untuk menentukan apakah R(C1 ,f.ll)k; R(C2,~), dan kemudian gunakan algoritma yang sarna untuk menentukan Apakah R(C1 ,f.ll) k; R(C2,~). R(C1 ,f.ll) = R(C2,~)jika dan hanya jika R(C1 ,f.ll) k; R(C2,~) dan R(C2 ,~) k; R(Cl'f.lI)' Jadi, kita dapat mereduksikan masalah kesamaan ke masalah subset. Pertimbangan-pertimbangan lain yang penting bila memandang masalahmasalah analisa dan reducibility. Pertama, dalam mencoba untuk menemukan suatu penyelesaian,kita harns memperhatikan kemungkinan bahwa suatu masalah tidak memiliki teknik penyelesaian, yang disebut undecidable atau tidak dapat diputuskan. Kedua, jika terdapat suatu teknik penyelesaian maka perlu untuk memperhatikan biayanya, yaitu berapa banyak waktu dan memory yang diperlukan? Agar Jaringan Petri dapat dipergunakan secara luas dan umum maka masalah-masalah analisa harns dapat diselesaikan oleh algoritma-algoritma yang tidak terlampau mahal dari sisi waktu dan memori. Reducibility berperan pada kedua masalah ini. Reducibilitydiantara masalahmasalah, umum'dipergunakan untuk membuktikan bahwa suatu masalah adalah decidable a~au undecidable. Pendekatan kita keteori decidability terntama didasarkan pada model komputasi yang disebut Mesin Turing. hal penting dari mesin turing ini adalah bahwa mesin terssebu't mernpakan suatu representasi yang layak dari suatu mesin komputasi yang terbatas dan dapat dibuktikan bahwa tidak terdapat algoritma yang dapat menyelesaikan masalah-masalahmesin turing tertentu, khususnya masalah halting. Berdasarkan hal ini maka sekumpulan undecidable telah dapat ditemukan. Kepentingan dari teori ini adalah tidaklah mungkin menghasilkan program komputer yang dapat menyelesaikan masalahmasalah ini. Jadi, untuk analisa secara praktis, masalah-masalah undecidable harns dihilangkan, atau pertanyaan-pertanyaan dari analisa tersebut tidak dapat dijawab. Perbedaan yang penting disini adalah bahwa masalah masalah undecidable menghasilkan pertanyaan-pertanyaan yang tidak mudah untuk tidak terjawab tetapi unaswerable. Beberapa pertanyaan dapat tidak terjawab hanya masih dapat .dijawab, hal ini berarti belum seorangpun telah menemukan suatu jawaban dari pertanyaan tersebut tetapi jawabannya ada. Contoh paling terkenal adalah Teorema da,ri 125
FERMATyang terahir. Apakah persamaan xn + yn = zn memilikipenyelesaian untuk n>2 dan interger nontrivial x, y dan z ? Pertanyaan ini hingga sekarang belum terjawab, tetapi sebenarnya memiliki jawab. Suatu cara untuk menjawab pertanyaan tersebut diatas adalah dengan menghasilkan bilangan-bilangan x, y dan z sertan yang memenuhi teorema.Cara yang lain adalah dengan membuktikan (mendeduksi secara logika) bahwa tidak ada nilai untuk x, y dan z serta n yang memenuhi. Hingga saat ini belum ada seorangpun yang melakukan hal seperti diatas. Asumsikan bahwa masalah tersebut adalah undecidable. Karenanya tidaklah mungkin untuk memutuskan bahwa nilai-nilai x, y dan z serta n ada sebagai jawaban dari persamaan. Hal ini berarti bahwa kita tidak dapat mendeduksikan secara logika ketidak-berada dari aksioma-aksioma matematika dan kita tidak dapat menghasilkan x, y, z dan n dari persamaan tersebut diatas. maka nilai-nilai tersebut harns tidak ada. Jika nilai-nilai tersebut ada maka kita tak dapat menset suatu komputer untuk mensearching mereka dan pada akhimya, kita dapat menemukannya. Akan tetapi jika X, y, z dan n tidak ada maka jawaban dari pertanyaan tersebut tidak ada, dan kita dapat memutuskannya. Hal ini kontrakdisi dengan asumsi kita bahwa pertanyaan tersebut, sehingga pertanyaan tersebut adalah decidable. Sekarang asumsikan bahwa terdapat suatu masalah yang dapat direduksikan ke masalah B: Suatu bentuk dari masalah A dapat ditransfopmasikan ke suatu bentuk masalah B. Jika masalah B adalah decidable maka masalah A decidable dan algoritma untuk masalah B dapat dipergunakan untuk menyelesaikan masalah A. Satu bentuk dari masalah A dapat diselesaikan dengan mentransformasikannya kesuatu bentuk dari masalah B dan menggunakan algoritma tersebut-ke masalah B untuk menentukan solusi tersebut. Jadi, jika masalah A dapat direduksikan ke masalah B dan masalah B decidable maka masalah A decidable. Kontra positinya juga benar : jika masalah A dapat direduksi ke masalah B dan masalah A undecidable maka masalah B undecidable: Jika masalah B undecidable maka prosedur diatas merupakan suatu teknik decision untuk masalah A, Kontradiksi dengan undecidability nya. Kedua fakta ini merupakan pusat bagi banyak teknik decidability. Untuk membuktikan bahwa suatu masalah adalah decidable maka reduksikan masalah tersebut ke suatu masalah yang diketahui sebagai decidable; untuk membuktikan bahwa suatu masalah undecidable maka reduksikan masalah tersebut ke suatu masalah yang diketahui sebagai undecidable. Kita akan menggunakan pendekatan yang baik ini untuk mereduksi jumlah pekerjaan yang harns dilakukan. Sebagai contoh, karena masalah equality untuk himpunan-himpunan reachability dapat direduksi kemasalah subhimpunan maka 126
kita berkeiginan untuk mengembangkan salah satu dari dua hal berikut ini: (1) prosedur penyelesaian untuk masalah subhimpunan tersebut, atau (2) bukti bahwa masalah kesamaan tersebut adalah undecidable. Jika kita dapat membuktikan (1) maka kita memiliki satu teknik solusi untuk kedua masalah, jika kita buktikan (2) maka kita tahu bahwa kedua masalah adalah undecidable. Pada banyak kasus, kita mungkin dapat melakukan yang lebih baik. Dua masalah adalah equivalen jika keduanya adalah mutually reducible, yaitu masalah A equivalen dengan masalah B jika masalah A dapat direduksi kemasalah B dan masalah B dapat direduksi ke masalah A. Dalam kasus ini, satu dari kedua masalah adalah decidable atau undecibable, dan kita dapat bekerja dengan salah satu cara. Pertimbangan kedua untuk menginvestigasi masalah-masalah analisa adalah jika suatu teknik solusi ada maka teknik tersebut harus cukup efisien. Hal ini berarti bahwa jumlah waktu dan memori yang dibutuhkan oleh suatu algoritma untuk menyelesaikan suatu bentuk masalah tidaklah berlebihan. Study tentang biaya eksekusi suatu algoritma merupakan bagian dari teori kompleksitas. Teori ini membicarakan tentang jumlah waktu dan memori yang dibutuhkan untuk menyelesaikan suatu masalah. Jelas bahwa jumlah waktu dan memori tidaklah konstan tetapi akan berbeda-beda sesuai dengan ukuran dari masalah yang akan diselesaikan. Untuk Jaringan Petri, waktu dan memori kebutuhanya mungkin merupakan suatu fungsi dari jumlah place dan transisinya. Faktor- faktor lain yang dapat mempengaruhi adalah jumlah token pada marking awal atau jumlah input dan output untuk setiaptransisidan place(jumlaharkus dalam graph tersebut). Waktu dan memeori yang dibutuhkan akan berbeda-beda sesuai dengan bentuk masalah yang akan diselesaikan. Karenanya, hasil dari kompleksitas dapat berbentuk suatu kasus terbaik(batas bawah) atau suatu kasus terjelek(batas atas) untuk suatu algorima. Karena kita tidak dapat menerka apakah suatu bentuk adalah kasus terjelek atau kasus terbaik maka kasus terjeleklah yang umum diasumsikan, dan kompleksitas dari suatu algoritma adalah kebutuhan waktu dan memorinya tergolong kasus terjelek, sebagai suatu "fungsi dari ukuran input. Analisa kompleksitas terutama menggaris-bawahi masalah kompleksitas dan tidak tertarik dengan implementasi secara rinci dari suatu algoritma khusus. Jadi, teori kompleksitas menggabaikan faktor-faktor konstan. Kompleksitas dari suatu masalah berukuran n ditentukan menjadi berorder n2 atau e2 atau n log n yang membolehkan suku-suku terkecil dan faktor-faktor konstan. Secara khusus dua 127
kelas yang umum dari algoritma adalah penting: algoritma dengan kompleksitas polinomial (n, n2, n log n, n8, dan sebagainya) dan kompleksitas nonpolinomial (khusus eksponensial, 2n, dan faktorial n ) Analisa kompleksitas umumnya dipakai ke algoritma-algoritmakhusus tetapi juga dapat dipakai ke masalah-masalah umum. Pada kasus ini, suatu batas bawah pada kompleksitas dari semua algoritmauntuk menyelesaikanmasalah ditentukan. Hal ini memberikan suatu kompleksitasyang bebas algoritma. Ini juga bermanfaat dalam membuktikan bahwa suatu algoritma khusus adalah optimal dan bila dikerjakan lebih lanjut akan menghasilkan suatu algoritma yang arnat baik untuk menyelesaikan suatu masalah. Sebagai contoh, telah diketahui dengan baik bahwa sorting n bilangan kompleksitasnya adalah n log n. Jadi algoritma dengan kompleksitas n log n tidak dapat dibuktikan secara berarti. Reducability dapat bermanfaat dalam menentukan kompleksitas. Jika suatu masalah A dapat direduksi kesuatu masalah B dan B memiliki kompleksitas fB(n),maka kompleksitasdari A paling besar adalah kompleksitasdari B ditarnbah dengan biaya mentransformasikan A ke B. Kompleksitas dari transfomasitransformasi umumnya adalah konstan atau linier sehingga sering diabaikan. Jadi mereduksi masalah A ke masalah B memberikan suatu batas atas untuk kompleksitas dari A (jika kompleksitas dari B diketahui), atau suatu batas bawah untuk kompleksitas dari B (jika kompleksitasdari A diketahui). Sekali lagi dengan menggunakan suatu contoh masalah-masalahkesarnaan dan subhimpunan,jumlah pekerjaan yang dibutuhkan untuk menyelesaikan masalah kesarnaan tidak lebih besar dua kali jumlah pekerjaan untuk masalah subhimpunan. Karena ini adalah suatu faktor konstan maka kompleksitas dari masalah subset harns sarna seperti kompleksitas dari masalah kesamaan. Kedua sifat dari sifat-sifat analisa Jaringan Petri - decedability dan kompleksitas merupakan perhatian utama untuk penggunaan dari Jaringan Petri. Pada bab ini kita berikan beberapa hasil yang telah dipeoleh. Salah satu teknik yang digunakan adalah dengan mereduksi masalah Jaringan Petri ke masalah lain.
5.2. MASALAH REACHABILITY Masalah reachability merupakan 'salah satu masalah yang sangat penting untuk analisa- analisa Jaringan Petri. 128
Definisi 5-3. Masalah Reachability. Diketahui ~', apakah ~' E R(C,~) ?
Definisi 5-4. Masalah Reachability Submarking Untuk Suatu himpunan bagian P' ~ P dan suatU marking ~' , Apakah terdapat
~" E R(C,~) demikian sehingga ~"(Pt) = ~(Pt)untuk semua Pt E P' ?
Definisi 5-5. Masalah Zero-Reachability Apakah ~" E R(C,~) dengan ~"(Pt) = 0 untuk semua Pt E P ? [ Apakah 0 E R(C,~)?]?
Definisi 5-6. Masalah Zero-Reachabilitypada Single place Diketahui suatu place Pt E P, apakah terdapat ~' E R(C,~) dengan ~'(Pt)
= O?
Masalah Reachability submarking membatasi masalah Reachability dangan hanya memperhatikan suatu subhimpunan dari place-place dan tidak memperdulikan marking-marking dari place-place lainnya. Masalah ZeroReachability menanyakan apakah marking tertentu dimana token token berharga nol pada semua place dapat dicapai. Masalah zero-reachability pada single place menanyakan jika dimungkinkan untuk mengosongkan semua token-token kecuali pada suatu place tertentu. Walaupun semua dari empat masalah tersebut adalah berbeda-beda tetapi semuanya ekivalen. Masalah Zero-reachability dapat direduksi kedalam masalah reachability, dengan mudah kita set ~'=O untuk masalah reachability tersebut. Dengan cara yang sarna Masalah Reachability dapat direduksi menjadi masalah Reachability submarking, dengan menset himpunan bagian P' = P. Masalah Zero-Reachability Single-Place dapat direduksi menjadi Masalah Reachability Submarking dengan menset P' = {Pi} dan ~' = O. Yang lebih sulit adalaJi membuktikan bahwa Masalah Reachability Submarking dapat direduksi menjadi Masalah Zero-Reachability dan bahwa Masalah Zero-Reachability tersebut dapat 129
direduksi menjadi Masalah Zero-Reachability Single-Place. Seluruh himpunan dari hubungan-hubungan ini dapat digambarkan pada gambar 5-1.
Masalah Reachability
Masalah Zero-Reachability
Masalah Reachability Submarking
Masalah Zero-Reachability
Single Place
Gambar 5-1. Reducibility Diantara masalah-masalah Reachability. Suatu arkus dari suatu masalah ke masalah yang lain menunjukan bahwa yang pertama dapat direduksi ke yang kedua. Pertama, kita buktikan bahwa masalah Masalah Reachability Submarking dapat direduksi menjadi Masalah Zero-Reachability. Asumsikan bahwa d.iketabui C) = (PI'TI' II' 0) dengan marking awal ~)' suatu subhimpunan dari place-place P' !;; PI' dan suatu marking ~'. Kita ingin tabu apakah terdapat ~" e (CI'~I') dengan ~'(Pt)=~"(Pi)untuk semua Pt e P'.
suatu Jaringan Petri
Pendekatan kita adalah menciptakan suatu Jaringan Petri bam C2
= (P2,T2, 12,
02) dengan marking awal ~ demikian sehingga terdapat~" e R(C),~I') dengan ~'(p)=~"(Pi) untuk semua Pt e P' jika dan hanya jika 0 e R(C2, ~2)' Pembentukan C2 dari C) cukup mudah. Kita mulai dengan C2 yang sarna dengan C) Untuk membolehkan suatu place Pi' yang tidak ada di P', agar menjadi kosong maka kita tambahkansuatu transisi ti' dengan input {Pi} dan output kosong. Transisi ini dapat ditembak bilamana terdapat suatu token di Pi untuk men"drain off' token-token yang bisa berada diplace ini. Hal ini membolehkan kita untuk mengabaikan place-place ini, dengan memastikan bahwa mereka selalu dapat mencapai suatu marking DOl. 130
Untuk place-place Pi di P', kita harns memastikan bahwa secara tepat J,1'(Pi) token berada di place Pi' Untuk memastikan ini, kita menciptakan suatu place barn pi' untuk setiap Pi E P' dengan suatu marking awal J,1'(Pi)token dan satu transisi p/ dengan input {Pi' Pi'} dan output kosong. Jika secara tepat terdapat J,1'(Pi)token di Pi' maka transisi ini secara tepat dapat ditembak J,1'(Pi)kali, mereduksi marking-marking dari pi dan Pi' ke nol. Jika jumlah dari token-token di pi tidak sarna dengan di J,1'(Pi)maka transisi ti' hanya dapat ditembak minimum dari dua marking tersebut, sehingga token akan tersisa Pi dan Pi', dengan mencegah marking nol menjadi tercapai. Garnbar 5-2 mengilustrasikan kedua jenis transisi yang dibicarakan diatas. Secara formal kita defmisikan C2 sebagai :
Orilinal Petri net
Gambar 5-2.
P"P'
Suatu Jaringan Petri yang menunjukan bahwa masalah Reachability Submarking dapat direduksi ke masalah ZeroReachability. Subhimpunan dari place-place P' akan memiliki marking J.1 pada Jaringan Petri aslijika dan hanya jika Zero marking dapat dicapai pada Jaringan Petri seperti yang dimodifikasi disini. 131
Secara formal kita defmisikan C2 sebagai :
P2
= PI U {P'i I Pi E P'}
T2
= T1 U {t' i I Pi E PI}
12(9
= 11(9
untuk tj e T1
Ilt/)
=
{Pi}
untuk Pi E P'
=
{Pi,Pi} untuk Pi E P'
°2(9
°l9
= ° 1(tj) untuk tj E T1 = {} untuk Pi E PI
dengan marking awal :
~(Pi) ~(P/)
= III (Pi)' Pi E PI = III '(Pi),Pl E P'
Teorema 5-1. Masalah Reachability Submarking dapat direduksi ke Masalah ZeroReachability
Buld; : Kita buktikan bahwa untuk jaringan Petri C2 diatas terbentuk dari C1, 0 E R(C, Il) jika dan hanya jika Il" E R(Cl' Ill) dengan 1l"(Pi)= Il'(Pi) untuk semua Pi E P'. Untuk membuktikan bahwa 0 E R(C2, ~) jika dan hanya jika terdapat suatu Il" E R(Cl' Ill) dengan 1l"(Pi)
=Il '(Pi)
untuk semua Pi E P', pe.rtarna-tama
asumsikanbahwa Il" ada di R(C1,Ill). Kemudianpada C2kita juga dapat mencapai marking Il" pada place-place Pi E PI dengan hanya menembak transisi-transisi dari T1. Sekarang untuk setiap Pi E P', kita dapat menembak t/ secara tepat (re(pi) kali mereduksi pi dan pi' ke no1. Kemudian kita dapat fire ti' untuk setiap Pi E P' sejumlah yang diperlukan untuk menjadikan jumlah tokennya sarna dengan nol, sehingga 0 E R(C2, ~). 132
Sekarang asumsikan 0 E R(C2, ~) ; maka terdapat satu barisan dari transisitransisi yang ditembak cr yang berasal dari ~ ke o. Barisan ini secara tepat akan berisi 1l'(Pi) penembakan dari ti' untuk Pi E P'(untuk menghilangkan tokentoken dari Pi') dan beberapa kali penembakan ti' untuk Pi E P'. Ingat bahwa transisi- transisi ini ditembakan hanya menghilangkan token-token dari CI, dan
9
karena ~(Il', t) didefinisikan bila ~(Il', terdefinisi untuk 11' ;::: 11, barisan cr dengan semua penembakan t/ yang dihilangkan juga legal dan akan membawa ke suatu marking 11"secaratepat 1l'(Pj) token di Pi untuk Pi E P'. Jadi, jika 0 E R(C2, ~), maka 11" E R(CI, IlI).dengan 1l"(Pi) = 1l"(Pi) untuk semua Pi E P'. Tugas kita berikutnya adalah membuktikan apakah Masalah Zero-Reachability dapat direduksi menjadi Masalah Zero-Reachability Single-Place. Pembuktiari
ini sekali lagi melibatkan pembentukan. Diketahui suatu aringan Petri CI = (PI'TI,lI,OI) dengan marking awallll' kita ingin menentukan apakah 0 E R(CI' Ill).. Dari Cl' kita bentuk suatu Jaringan Petri barn C2 dengan place tambahan s (P2= PI U {s}) sedemikian sehingga terdapat suatu marking 11' E R(C2, ~). deng.an Il'(s)
= 0 jika
dan hanya jika 0 E R(CI' Ill).
Pembentukan dari C2 mendefinisikan s sehingga pada setiap saat jumlah token di s sarna dengan penjumlahan dari token-token di place-place dari CI. Jadi jika 1l1(s) = 0 maka terdapat token-token nol pada semua place di CI dan sebaliknya. Kita definisikan marking awal f.12sebagai berikut : ~(Pi) ~(s)
= ll(Pi) untuk =
L
Pi E PI
III (Pi)
pieR
1
Sekarang untuk setiap transisi E T I transisi yang sarna berada di C2 tetapi ditambah dengan arkus-arkus ke place-place s. didefinisikan :
d. J
= ~£..
#(p.,O(t.) - #(p.,l(t.» 1 J 1J
pieR
Maka dj adalah perubahan jumlah token yang merupakan hasil dari penembakan transisi t.. Sekarang jika dj > 0 maka dj token harns ditambahkan ke place s, sehingga kita tambahkan dj arkus dari tj ke s ; jika dj < 0 maka kita hilangkan
- dj
token dari
s dengan
- dj
arkus dari s ke tj"
133
Jika dj > 0, maka #(s, I(tj» = 0 ; # (s, O(tj)) = dj" Jika dj < 0, maka #(s, I(tj)) = - tj ; # (s, OCt})
= O.
Jika dj = 0, maka #(s, I(tj))= 0 ; # (s, O(tj))= O. Dengan pembentukan ini, suatu barisan dari transisi-transisi yang ditembak yang membawa C1 ke marking 0 akan membawa C2 ke suatu marking J,l' dengan J,l'(s) = 0 [u'(Pj)= 0 juga] dan sebaliknya.
Teorema 5-2. Masalah Zero-Reachability Reachability Single-Place.
dapat direduksi menjadi Masalah Zero-
Untuk pembuktiannya diserahkan kepada para pembaca. Dengan kedua teorema ini, kita dapat simpulkan berikut ini:
Teorema 5-3. Masalah-masalah Reachability berikut ini adalah Ekivalen; 1.
Masalah Reachability
2.
Masalah Zero-Reachability
3.
Masalah Submarking-Reachability
4.
Masalah Zero-Reachability Single-Place
5-3. LIVENESS DAN REACHABILITY Reachability merupakan masalah penting, akan tetapi bukan hanya satusatunya masalah yang terdapat pada Jaringan Petri. Disamping itu, terdapat juga masalah lainnya, yaitu Liveness, yang menjadi perhatian dari beberapa literatur tentang Jaringan I:'etri.Seperti yang telah diterangkan sebelumnya bahwa Liveness berkaitan dengan masalah Deadclock. Dua masalah liveness untuk suatu Jaringan 134
Petri C = (P, T, I, 0) dengan marking awal (yang akan dibicarakan disini. Suatu Jaringan Petri adalah live jika setiap transisinya adalah live. Suatu transisi tj adalah live pada suatu marking ~,jika untuk setiap ~' E R(C, ~) terdapat sebarisan a demikian sehingga tj enabled d.i O(~', a). Suatu transisi tj adalah dead pada suatu marking ~ jika tidak terdapat suatu marking yang dapat dicapai pada mana transisi tersebut dapat tire.
Definisi 5-7. Masalah liveness. Untuk semua transisi tj E T, apakah tj adalah live?
Definisi 5-8. Masalah liveness pada transisi-tunggal. Diketahui tj E T, apakah tj adalah live?
Masalah liveness jelas dapat direduksi kedalam masalah liveness transisitunggal. Untuk menyelesaikan masalah liveness ini, dengan mudah kita menyelesaikan
masalah
liveness
transisi-tunggal
untuk setiap tj E T; jika ITI
=
m maka kita harns menyelesaikan m masalah livene.ss-transisitunggal. Masalah Reachabilityjuga dapat direduksikan kedalam masalah liveness, karena bermacam masalah reachability adalah ekuivalen, maka kita gun~an masalah Masalah Zero-Reachability Single-Place. Jika kita memilih satu dari masalah~masalah reachability yang lain, maka masalah-masalahtersebut dapat direduksi ke masalah Zero-Reachability Single-Placeseperti yang ditunjukan pada bagian 5-2. Sekarang jika kita ingin menentukan apakah place pi bisa nol pada suatu marking yang dapat dicapai untuk suatu Jaringan Petri CI
= (PI'
TI' 11' °1) dengan
marking
awal ~I' kita bentuk suatu Jaringan Petri CI = (PI' TI' II' °1) dengan marking awalll2, yang adalah live jika dan hanya jika marking nol tidak dapat dicapai dari ~I' Jaringan Petri Cz dibentuk dari Jaringan Petri CI dengan penambahan dua place, rl dan rz' dan tiga transisi sl' Sz dan s3' Pertama-tama kita moditikasi semua transisi dari TI untuk mencakup rI sebagai suatu input dan suatu uotput. Marking awal ~2 akan mencakup satu token di rl . Place r I merupakan suatu place "run"; sepanjangtokentersebuttetapberadadi rI ' transisi dari T l' dapat ditembak secara normal. Jadi suatu marking yang dapat dicapai pada place-place dari PI di CI juga dapt dicapai di Cz. Transisj sl didetinisikan untuk memiliki 135
rl sebagai inputnya dan satu uotput kosong. lni membolehkan token di rl untuk
dihilangkan,mendisablesemuatransisi-transisidi T1 dan membekukanmarking dari PI' (Ingat bahwa semua transisi dari T1 adalah konflik dan, tidak lebih dari satu transisi dapat ditembak pada satu saat). Place rl dan transisi sl membolehkan Jaringan Petri CI untuk mencapai suatu marking yang dapat dicapai dan kemudian untuk sl untuk ditembak dan membekukan Jaringan Petri pada marking tersebut. Sekarang kita perlu untuk melihat apakah place p.1 adalah nol. Kita perkenalkan satu place baru r2 dan satu . transisi s2 yang memiliki Pi sebagai inputnya dan r2 sebagai outputnya. Jika Pi dapat menjadi nol, maka transisi ini tidak live; kenyataannya seluruh Jaringan Petri adalah dead jika transisi sl ditembak pada marking tersebut. Disini jika Pi dapat menjadi nol maka s2 selalu dapat ditembak, dengan meletakkan satu token di r2. Pada kasus ini kita harns meletakan satu token kembali pada rl dan menjarnin bahwa semua transisi di C2 adalah live, kita harns pasti bahwa C2 adalah live walaupun jika CI tidak live. lni diselesaikan pada satu transisi s3 yang membanjiri Jaringan Petri C2 dengan beberapa token, menjamin bahwa setiap transisi adalah live jika satu token tidak pemah diletakan di r2.. Transisi s3 memiliki r2 sebagai inputnya dan setiap place dari C2 (semua Pi di CI dan rl dan r2) sebagai output. Pembentukan ini diilustrasikan pada gambar 5-6. Sekarang, jika suatu marking Il dapat dicapai di R(CI, Ill) dengan Il(pi) = 0, maka Jaringan Petri C2 juga dapat mencapai marking ini pada placedari PI dengan mengeksekusi barisan yang sarna dari transisi-transisi yang ditembak. Kemudian sl dapat ditembak dan membekukan subhimpunan CI karena Il(Pi)= 0, transisi s2tidak dapat ditembak dan C2adalah mati. Jadi, jika pi dapat menjadi nol maka C2 adalah tidak live. Sebaliknya, jika C2 tidak live maka suatu marking Il harns dapat dicapai dalam mana ll(r2) =° dan tidakada statayangdapatdicapaidiman~r2memiliki satu token. {jika r2 memiliki satu token, s3 enabled dan s3 dapat ditembak secara berulang seperlunyauntuk mengenablekansatu atau semua transisi sehingga Jaringan Petri live }. Jika r2 tidak memiliki token dan tidak dapat meng;ambil satupun maka marking dari Pi juga harns nol. Jadi, jika C2 tidak live maka satu marking dapat dicapai dimana marking dari Pi adalah nol. Berdasarkan pembentukan ini, kita dapat memiliki berikut ini.
136
Teorema 5-5. Masalah reachability dapat direduksi menjadi masalah liveness Sekarang kita perlu buktikan berikut ini.
Teorema 5-6. Masalah Liveness transisi-tunggal dapat direduksikan menjadi masalah Reachability
.
Bukti bahwa masalah liveness transisi tunggal dapat direduksi menjadi masalah reachability tinggal menguji reachability dari suatu himpunan berhingga dari submarking-submarking tj - dead yang maksimal. Suatu Jaringan Petri
tidakliveuntuksuatutransisi~ jlka dan hanyajikabeberapamarkingyangdapat dicapai dalam mana transisi tj tldak dapat ditembak dan tidak akan dapat ditembak. Marking yang seperti ini disebut sebagai tj - dead. Untuk suatu marking J.Lkita dapat menguji apakah marking tersebut merupakan tj - dead dengan membentuk pohon reachabilitynya dengan J.Lsebagai root dan menguji apakah transisi tj dapat ditembak dimana saja pada pohon terseut. Jika tidak dapat maka J.Ladalah 1.- dead. Kemudian pemeriksaan terhadap liveness dari tj hany~ dilakukan dengan ti.emeriksa apakah marking tj - dead dapat dicapai.
Sebagai contoh, perhatikan Jaringan Petri pada ganbar 5-3. Markipg-marking (2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (0, 3),
adalah
~ - dead,
tetapi marking-
marking tersebut dapat dinyatakkan secara berhingga oleh himpunan {(2,0), (1, 0), (0, ro}.
Gambar 5-3.
Suatu Jaringan Petri untuk Illengilustrasikanmarking-marking t.J - dead. 137
Hack [1974c ; 1975c]telah membuktikan bahwa untuk suatu Jaringan Petri C terdapat suatu himpunan berhingga Dt dari marking-marking sehingga C adalah live jika dan hanya jika tidak ada marking di Dt yang dapat dicapai. Jika
suatumarkingdari Dt berisi co, makasubmarkingyangdapatdicapaiterlaksana. Lebih lanjut, Dt secara efektif dapat dihitung. Kar~na Dt adalah berhingga maka komponen non-codari marking-marking memiliki satu batas atas b. Batas b ini dicirikan sebagai nilai terkecil demikian sehingga untuk suatu marking ~ dengan ~(Pi) =:;b + 1 untuk semua pi, jika ~ adalah tj - dead maka submarking ~' dengan ~'(Pi) = ~(Pi) j~a ~(Pi) =:;b dan ~'(Pi) = cojika ~'(Pi) = b + I, adalah tj - dead. Denag karakterisitikdari b ini kita dapat membentukDt berikutini. 1. Menghitung b. Mulai dengan b = 0, dan menaikkan b hingga b yang pertama ditemukan yang memenuhi karakterisasi dari batas yang didefinisikan diatas. Pengujian untuk b membutuhkan pemeriksaan semua (b + 2n)n marking dengan komponen-komp(:menyang lebih kecil atau sarna dengan b + I. 2.
Menghitung Dt dengan menguji semua marking dan submarking yang komponen-komponennya lebih kecil atau sarna dengan b atau sarna dengan co.Dt adalah himpunan marking-marking tj -dead dari himpunan (b + 2n)0.
Setelah kita membentukDt' kita kemudian menggunakanmasalah reachability submarking untuk setiap elemen dari Dt' Jika suatu elemen dari Dt dapat dicapai dari marking awal, maka Jaringan Petri tersebut adalah tidak live; jika tidak ada elemen di Dt yang'dapat dicapai maka Jaringan Petri tersebut adalah, live. Dari kedua teorema, 5-5 dan 5-6, diatas kita memperoleh berikut ini.
Teorema 5-7. I. MasalahReachability. 2. Masalahliveness. 3. Masalahlivenesstransisitunggal.
138
