Model Petri Net dan Markov Chain
Tugas Fault Tolerant
Evi Andriani
I. Model Petri Net
Petri net merupakan suatu perangkat untuk pemodelan dan menganalisis sistem sehingga dapat diperoleh informasi tentang struktur dan perilaku dinamik dari sistem yang di modelkan [1]. Petri net dapat mendeskripsikan dengan jelas distribusi dan redistribusi energi yang terjadi pada sistem. Hasil analisis kemudian untk memperbaiki sistem yang ada. Siklus pemodelan dan analisis dengan Petri net dapat ditunjukkan oleh Gambar 1.
Gambar 1. Sistem Pemodelan dan analisis dengan Petri Net
Petri net menggunakan bahasa grafis dan matematis untuk pemodelan dan analisis sistem yang bersifat diskrit, di mana harga variable-variabel sistem hanya berada pada dua keadaan seperti on atau off maupun aktif atau tidak aktif. Representatif grafis dari Petri net membuat Petri net banyak digunakan diberbagai bidang seperti kontrol proses, jaringan komputer, sistem antrian, dan lain-lain. [2]
Penelitian yang pernah dilakukan antara lain : pemodelan dan simulasi jaringan traffic perkereta-apian menggunakan metode Coloured Petri Nets (CPN) sehingga kondisi deadlock dan trapping (terjebak) dapat dihindari dan keselamatan perjalanan serta overtaking (mendahului) dapat dipenuhi. [3]. Ada juga penelitian kinerja sistem interlock kompresor udara 101-J di Pusri-IB yang dimodelkan dan dianalisis menggunakan Petri net. Petri net dapat mendeskripsikan dengan jelas distribusi dan redistribusi energi yang terjadi pada sistem. Karena kegagalan komponen interlock dapat menyebabkan kompresor menjadi berhenti beroperasi. Sehingga meningkatkan kinerja sistem interlock kompresor udara 101-J. [4]
Petri net dibentuk oleh place dan transisi yang dihubungkan dengan panah. Place, yang digambarkan dengan lingkaran, merepresentasikan kondisi. Transisi, yang digambarkan dengan kotak persegi panjang atau garis lurus, merepresentasikan event atau kejadian. penandaan (marking) merupakan hubungan antara token dengan place. Token, digambarkan dengan titik kecil, berpindah-pindah dari satu place ke place lain ketika terjadi pemicuan transisi (firing).
Prilaku dinamik ditunjukkan aliran token pada jala serta diikuti dengan perubahan penandaan place. Aliran ini terjadi akibat proses pemicuan transisi yang memindahkan token dari satu place menuju place lainnya.
Secara umum Petri net didefinisikan sebagai berikut [5] :
Petri net N = (P, T, I, O, M_0), dengan :
P = {p1, p2,..., pm} adalah himpunan place-place,
T = { t1, t2,..., tn} adalah himpunan transisi-transisi, di mana
P∪T≠∅ dan P∩T≠∅,
I:(PxT)→N adalah fungsi input yang mendefinisikan busur dari place ke transisi,
di mana N bilangan bulat non negatif,
O:(PxT)→N adalah fungsi otput yang mendefinisikan busur dari transisi ke place,
M_0:P→N adalah penandaan awal.
Contoh Petri net sederhana ditunjukkan pada Gambar 2 di bawah ini :
Gambar 2. Petri Net sederhana
Eksekusi suatu Petri net dikontrol oleh jumlah dan distribusi token pada Petri net. Petri net dieksekusi dengan pemicuan transisi (firing transition). proses pemicuan transisi pada Petri net mengikuti aturan berikut [5] :
- Aturan siap terpicu (enabling rule)
- Aturan pemicuan (firing rule)
Sifat-sifat Petri Net yaitu :
- Ketercapaian (reachability)
- Keterbatasan (boundedness)
- Daya Hidup (liveness)
Model Petri net dapat menggunakan analisis stressor (terutama vibrasi) untuk analisis dan kalkulasi kehandalan yang membantu pemahaman lebih baik terhadap gejala kegagaln di dunia industri seperti pada penelitian Yugi Sukriana, dkk pada studi kasusu pompa 15-p-101 di Pertamina UP-VI, laju kegagalan (failure rate) pompa dengan coincidence lebih tinggi (reliability-nya lebih rendah) daripada asumsi kegagalan terjadi secara independent sehingga membantu dalam pengambilan keputusan sistem pemeliharaan karena pada umumnya sistem yang ada di industri dapat diperbaiki (repairable system).[6]
II Model Chain
Rantai markov (Markov Chain) adalah suatu model teoritis yang menjelaskan keadaan sebuah sistem pada suatu tahap tertentu. Model ini dapat memperkirakan perubahan- perubahan pada waktu yang akan datang dalam variabel-variabel dinamis pada waktu yang lalu. Teknik ini dapat juga digunakan untuk menganalisis kejadian-kejadian pada waktu mendatang secara sistematis. [7]
Penerapan rantai markov mula-mula digunakan untuk menganalisis dan memperkirakan perilaku partikel-partikel gas dalam suatu wadah tertutup serta meramalkan keadan cuaca. Sebagai suatu peralatan riset operasi dalam pengambilan keputusan manajerial. Proses markov telah banyak diterapkan untuk menganalisa tentang perpindahan merek (brands witching) dalam pemasaran, perhitungan rekening, jasa persewaan mobil, perencanaan penjualan, masalah-masalah persediaan, pemeliharaan mesin, antrian, perubahan harga pasar saham, dan administrasi rumah sakit.
Rantai markov ini dikenalkan oleh Andrei A. Markov, ahli matematika dari Rusia yang lahir tahun 1856. [8] Analisis markov menghasilkan suatu informasi probabilistik yang dapat digunakan untuk membantu pembuatan keputusan, jadi analisis ini bukan suatu teknik optimisasi melainkan suatu teknik deskriptif. Analisis markov merupakan suatu bentuk khusus dari model probabilistik yang lebih umum dinamakan dengan Stochastic process, yaitu proses perubahan perubahan probabilistik yang terjadi terus-menerus.
Untuk dapat menerapkan analisis rantai markov ke dalam suatu kasus, ada beberapa syarat yang harus dipenuhi :
- jumlah probabilitas transisi untuk suatu keadaan awal dari sistem sama dengan 1(satu),
- Probabilitas-probabilitas tersebut berlaku untuk semua partisipan dalam sistem,
- Probabilitas transisi konstan sepanjang waktu,
- Kondisi merupakan kondisi yang independent sepanjang waktu.
Sedangkan menurut Karlin dan Taylor [9] proses Markov adalah sebuah proses dengan sifat, diberikan nilai V(u) untuk setiap u
P(V(t+1)=V_(t+1)│V(1)=v_2,…,V(t-1)=v_(t-1),V(t)=v_t )=P(V(t+1)=v_(t+1)│V(t)=v_t )= P_(v_t,V_(t+1))^((t,t+1))
dengan s = t+1-1
Dalam realita, penerapan analisis markov biasa terbilang cukup terbatas karena sulit menemukan masalah yang memenuhi semua sifat yang diperlukan untuk analisis markov, terutama persyaratan bahwa probabilitas transisi harus konstan sepanjang waktu (probabilitas transisi adalah probabilitas yang terjadi dalam pergerakan perpindahan kondisi dalam sistem).
Salah satu penelitian yang menggunakan Markov Chains adalah penelitian dari Putu Rio Aditya Darma tentang pemodelan arima redaman hujan. Untuk menyelidiki fenomena gelombang propagasi pada tinggiya curah hujan diperlukan pengukuran dan pencatatan statistik mengenai data cuaca, curah hujan rata-rata (mm/h) beserta pemodelan redaman hujan sehingga dapat diketahui transisi antar model ARIMA redaman hujan dengan menggunakan model Markov Chains. Data yang digunakan adalah data pengukuran curah hujan yang dikonversi menjadi data redaman hujan berdasar metode Synthetic Storm Technique (SST) dengan frekuensi 28 Ghz untuk link sepanjang 2 km. Nilai redaman hujan kemudian dimodelkan dengan pendekatan ARIMA (p,d,q) dan diubah menjadi state dalam Markov Chains. Dari model Markov Chains akan diperoleh nilai probabilitas steady state, panjang interval pengukuran dan distribusi model ARIMA. Analisa data dilakukan dengan cara membandingkan kurva CCDF dan nilai Root Mean Square Error (RMSE) antara data hasil model dengan data pengukuran redaman hujan. Hasil penelitiannya menunjukkan bahwa pemakaian model Markov Chain pada model ARIMA redaman hujan menghasilkan nilai Akaike’s Information Criterion (AIC) yang kecil. [10]
Salah satu karakteristik utama suatu rantai Markov adalah peluang-peluang transisinya. Peluang transisi tersebut menggambarkan peluang perpindahan dari satu keadaan ke keadaan lainnya. Dengan kata lain, menggambarkan peluang proses berada di satu keadaan bila diketahui keadaan proses pada satu waktu sebelumnya. Secara matematis, peluang transisi tersebut dapat ditulis sebagai berikut,
〖P_ij=P(V〗_(t+1)=j|V_t=i
dengan i dan j masing-masing menyatakan keadaan proses saat t dan t+1
DAFTAR PUSTAKA
[1] Peterson, James L. 1981. Petri Net Theory and the Modelling of Systems. Ney Jersey, Prentice Hall Inc.
[2] Moody, John O., Panos J. Antsaklis. 1998. Supervisory Control of Discrete Event Systems Using Petri Nets. Norwell, Kluwer Academic Publishers.
[3] Sitepu, Suriantou. 2001. Pemodelan dan Simulasi Jaringan Traffic Perkereta-apian Menggunakan Metode Coloured Petri Nets (CPN). Tesis ITB Bandung.
[4] Sulaiman, M. Hamni. 2002. Studi Evaluasi Kinerja Sistem Interlock Kompresor Udara 101-J di Pusri-IB Berbasis Teknik Petri Net. Tesis ITB Bandung.
[5] Wang, Jiacun. 1998. Timed Petri Net : Theory and Aplication. Norwell, Kluwer Academic Publicers.
[6] Yugi Sukriana, Sonny Yuliar, Togar M.P. Manurung dan Persaulian Siregar. Kalkulasi Kehandalan Sistem Industrial, Kompleks Berbantukkan Petri Net Stikastik : Studi Kasus Pada Pompa 15-P di Pertamina UP-VI. Departemen Fisika, ITB.
[7] Anggriya, Nova. 2009. Aplikasi Rantai Markov Multivariat Pada Network Genetik. Skripsi Departemen Matematika FMIPA USU.
[8] Ching, W., dan Ng, M. 2006. Markov Chain: Models, Algorithms and Application. New York: Springer Science + Business Media, Inc.
[9] Karlin S dan Taylor, H. M. 1975. A First Course in Stochastic Process, New York : Academic Press.
[10] Darma, Putu Rio Aditya. 2011. Pemodelan ARIMA Redaman Hujan denga Menggunakan Markov Chains. Teknik Elektro ITS.
Evi Andriani
I. Model Petri Net
Petri net merupakan suatu perangkat untuk pemodelan dan menganalisis sistem sehingga dapat diperoleh informasi tentang struktur dan perilaku dinamik dari sistem yang di modelkan [1]. Petri net dapat mendeskripsikan dengan jelas distribusi dan redistribusi energi yang terjadi pada sistem. Hasil analisis kemudian untk memperbaiki sistem yang ada. Siklus pemodelan dan analisis dengan Petri net dapat ditunjukkan oleh Gambar 1.
Gambar 1. Sistem Pemodelan dan analisis dengan Petri Net
Petri net menggunakan bahasa grafis dan matematis untuk pemodelan dan analisis sistem yang bersifat diskrit, di mana harga variable-variabel sistem hanya berada pada dua keadaan seperti on atau off maupun aktif atau tidak aktif. Representatif grafis dari Petri net membuat Petri net banyak digunakan diberbagai bidang seperti kontrol proses, jaringan komputer, sistem antrian, dan lain-lain. [2]
Penelitian yang pernah dilakukan antara lain : pemodelan dan simulasi jaringan traffic perkereta-apian menggunakan metode Coloured Petri Nets (CPN) sehingga kondisi deadlock dan trapping (terjebak) dapat dihindari dan keselamatan perjalanan serta overtaking (mendahului) dapat dipenuhi. [3]. Ada juga penelitian kinerja sistem interlock kompresor udara 101-J di Pusri-IB yang dimodelkan dan dianalisis menggunakan Petri net. Petri net dapat mendeskripsikan dengan jelas distribusi dan redistribusi energi yang terjadi pada sistem. Karena kegagalan komponen interlock dapat menyebabkan kompresor menjadi berhenti beroperasi. Sehingga meningkatkan kinerja sistem interlock kompresor udara 101-J. [4]
Petri net dibentuk oleh place dan transisi yang dihubungkan dengan panah. Place, yang digambarkan dengan lingkaran, merepresentasikan kondisi. Transisi, yang digambarkan dengan kotak persegi panjang atau garis lurus, merepresentasikan event atau kejadian. penandaan (marking) merupakan hubungan antara token dengan place. Token, digambarkan dengan titik kecil, berpindah-pindah dari satu place ke place lain ketika terjadi pemicuan transisi (firing).
Prilaku dinamik ditunjukkan aliran token pada jala serta diikuti dengan perubahan penandaan place. Aliran ini terjadi akibat proses pemicuan transisi yang memindahkan token dari satu place menuju place lainnya.
Secara umum Petri net didefinisikan sebagai berikut [5] :
Petri net N = (P, T, I, O, M_0), dengan :
P = {p1, p2,..., pm} adalah himpunan place-place,
T = { t1, t2,..., tn} adalah himpunan transisi-transisi, di mana
P∪T≠∅ dan P∩T≠∅,
I:(PxT)→N adalah fungsi input yang mendefinisikan busur dari place ke transisi,
di mana N bilangan bulat non negatif,
O:(PxT)→N adalah fungsi otput yang mendefinisikan busur dari transisi ke place,
M_0:P→N adalah penandaan awal.
Contoh Petri net sederhana ditunjukkan pada Gambar 2 di bawah ini :
Gambar 2. Petri Net sederhana
Eksekusi suatu Petri net dikontrol oleh jumlah dan distribusi token pada Petri net. Petri net dieksekusi dengan pemicuan transisi (firing transition). proses pemicuan transisi pada Petri net mengikuti aturan berikut [5] :
- Aturan siap terpicu (enabling rule)
- Aturan pemicuan (firing rule)
Sifat-sifat Petri Net yaitu :
- Ketercapaian (reachability)
- Keterbatasan (boundedness)
- Daya Hidup (liveness)
Model Petri net dapat menggunakan analisis stressor (terutama vibrasi) untuk analisis dan kalkulasi kehandalan yang membantu pemahaman lebih baik terhadap gejala kegagaln di dunia industri seperti pada penelitian Yugi Sukriana, dkk pada studi kasusu pompa 15-p-101 di Pertamina UP-VI, laju kegagalan (failure rate) pompa dengan coincidence lebih tinggi (reliability-nya lebih rendah) daripada asumsi kegagalan terjadi secara independent sehingga membantu dalam pengambilan keputusan sistem pemeliharaan karena pada umumnya sistem yang ada di industri dapat diperbaiki (repairable system).[6]
II Model Chain
Rantai markov (Markov Chain) adalah suatu model teoritis yang menjelaskan keadaan sebuah sistem pada suatu tahap tertentu. Model ini dapat memperkirakan perubahan- perubahan pada waktu yang akan datang dalam variabel-variabel dinamis pada waktu yang lalu. Teknik ini dapat juga digunakan untuk menganalisis kejadian-kejadian pada waktu mendatang secara sistematis. [7]
Penerapan rantai markov mula-mula digunakan untuk menganalisis dan memperkirakan perilaku partikel-partikel gas dalam suatu wadah tertutup serta meramalkan keadan cuaca. Sebagai suatu peralatan riset operasi dalam pengambilan keputusan manajerial. Proses markov telah banyak diterapkan untuk menganalisa tentang perpindahan merek (brands witching) dalam pemasaran, perhitungan rekening, jasa persewaan mobil, perencanaan penjualan, masalah-masalah persediaan, pemeliharaan mesin, antrian, perubahan harga pasar saham, dan administrasi rumah sakit.
Rantai markov ini dikenalkan oleh Andrei A. Markov, ahli matematika dari Rusia yang lahir tahun 1856. [8] Analisis markov menghasilkan suatu informasi probabilistik yang dapat digunakan untuk membantu pembuatan keputusan, jadi analisis ini bukan suatu teknik optimisasi melainkan suatu teknik deskriptif. Analisis markov merupakan suatu bentuk khusus dari model probabilistik yang lebih umum dinamakan dengan Stochastic process, yaitu proses perubahan perubahan probabilistik yang terjadi terus-menerus.
Untuk dapat menerapkan analisis rantai markov ke dalam suatu kasus, ada beberapa syarat yang harus dipenuhi :
- jumlah probabilitas transisi untuk suatu keadaan awal dari sistem sama dengan 1(satu),
- Probabilitas-probabilitas tersebut berlaku untuk semua partisipan dalam sistem,
- Probabilitas transisi konstan sepanjang waktu,
- Kondisi merupakan kondisi yang independent sepanjang waktu.
Sedangkan menurut Karlin dan Taylor [9] proses Markov adalah sebuah proses dengan sifat, diberikan nilai V(u) untuk setiap u
P(V(t+1)=V_(t+1)│V(1)=v_2,…,V(t-1)=v_(t-1),V(t)=v_t )=P(V(t+1)=v_(t+1)│V(t)=v_t )= P_(v_t,V_(t+1))^((t,t+1))
dengan s = t+1-1
Dalam realita, penerapan analisis markov biasa terbilang cukup terbatas karena sulit menemukan masalah yang memenuhi semua sifat yang diperlukan untuk analisis markov, terutama persyaratan bahwa probabilitas transisi harus konstan sepanjang waktu (probabilitas transisi adalah probabilitas yang terjadi dalam pergerakan perpindahan kondisi dalam sistem).
Salah satu penelitian yang menggunakan Markov Chains adalah penelitian dari Putu Rio Aditya Darma tentang pemodelan arima redaman hujan. Untuk menyelidiki fenomena gelombang propagasi pada tinggiya curah hujan diperlukan pengukuran dan pencatatan statistik mengenai data cuaca, curah hujan rata-rata (mm/h) beserta pemodelan redaman hujan sehingga dapat diketahui transisi antar model ARIMA redaman hujan dengan menggunakan model Markov Chains. Data yang digunakan adalah data pengukuran curah hujan yang dikonversi menjadi data redaman hujan berdasar metode Synthetic Storm Technique (SST) dengan frekuensi 28 Ghz untuk link sepanjang 2 km. Nilai redaman hujan kemudian dimodelkan dengan pendekatan ARIMA (p,d,q) dan diubah menjadi state dalam Markov Chains. Dari model Markov Chains akan diperoleh nilai probabilitas steady state, panjang interval pengukuran dan distribusi model ARIMA. Analisa data dilakukan dengan cara membandingkan kurva CCDF dan nilai Root Mean Square Error (RMSE) antara data hasil model dengan data pengukuran redaman hujan. Hasil penelitiannya menunjukkan bahwa pemakaian model Markov Chain pada model ARIMA redaman hujan menghasilkan nilai Akaike’s Information Criterion (AIC) yang kecil. [10]
Salah satu karakteristik utama suatu rantai Markov adalah peluang-peluang transisinya. Peluang transisi tersebut menggambarkan peluang perpindahan dari satu keadaan ke keadaan lainnya. Dengan kata lain, menggambarkan peluang proses berada di satu keadaan bila diketahui keadaan proses pada satu waktu sebelumnya. Secara matematis, peluang transisi tersebut dapat ditulis sebagai berikut,
〖P_ij=P(V〗_(t+1)=j|V_t=i
dengan i dan j masing-masing menyatakan keadaan proses saat t dan t+1
DAFTAR PUSTAKA
[1] Peterson, James L. 1981. Petri Net Theory and the Modelling of Systems. Ney Jersey, Prentice Hall Inc.
[2] Moody, John O., Panos J. Antsaklis. 1998. Supervisory Control of Discrete Event Systems Using Petri Nets. Norwell, Kluwer Academic Publishers.
[3] Sitepu, Suriantou. 2001. Pemodelan dan Simulasi Jaringan Traffic Perkereta-apian Menggunakan Metode Coloured Petri Nets (CPN). Tesis ITB Bandung.
[4] Sulaiman, M. Hamni. 2002. Studi Evaluasi Kinerja Sistem Interlock Kompresor Udara 101-J di Pusri-IB Berbasis Teknik Petri Net. Tesis ITB Bandung.
[5] Wang, Jiacun. 1998. Timed Petri Net : Theory and Aplication. Norwell, Kluwer Academic Publicers.
[6] Yugi Sukriana, Sonny Yuliar, Togar M.P. Manurung dan Persaulian Siregar. Kalkulasi Kehandalan Sistem Industrial, Kompleks Berbantukkan Petri Net Stikastik : Studi Kasus Pada Pompa 15-P di Pertamina UP-VI. Departemen Fisika, ITB.
[7] Anggriya, Nova. 2009. Aplikasi Rantai Markov Multivariat Pada Network Genetik. Skripsi Departemen Matematika FMIPA USU.
[8] Ching, W., dan Ng, M. 2006. Markov Chain: Models, Algorithms and Application. New York: Springer Science + Business Media, Inc.
[9] Karlin S dan Taylor, H. M. 1975. A First Course in Stochastic Process, New York : Academic Press.
[10] Darma, Putu Rio Aditya. 2011. Pemodelan ARIMA Redaman Hujan denga Menggunakan Markov Chains. Teknik Elektro ITS.