Prosiding Seminar Nasional FMIPA Universitas Negeri Surabaya ISBN : 978-602-17146-0-7 Surabaya 24 November 2012
Penjadwalan Pelayanan di PLN dengan Menggunakan Petri Net dan Aljabar Max-Plus 1
Dwina Nur Widayanti, 2Subiono Mahasiswa Pascasarjana Matematika ITS Surabaya 2 Matematika FMIPA ITS Surabaya 1 Email:
[email protected],
[email protected] 1
Abstrak Pelanggan yang ingin melakukan pasang baru banyak yang tidak mengetahui berapa lama proses pelayanan yang diberikan pihak PLN dari pendaftaran pelanggan tersebut sampai terpasang listrik baru. Pada makalah ini dibangun alur pelayanan dengan menggunakan Petri Net dan dari alur pelayanan tersebut dibangun model penjadwalan pelayanan dengan menggunakan Aljabar Max-Plus. Hasil dari penelitian ini menunjukkan tidak adanya deadlock dari antrian pelayanan pelanggan sehingga terjadi looping pada alur Petri Net. Waktu mulai pelayanan dapat dipilih secara acak sehingga waktu akhir pelayanan ditentukan dengan lamanya pelayanan dari awal hingga akhir. Kata kunci: penjadwalan pelayanan, Petri Net, Aljabar Max-Plus, looping, deadlock dapat kemudian dianalisa penjadwalan pelayanan di PLN.
I.
Pendahuluan Listrik merupakan salah satu kebutuhan penting dalam kehidupan sehari-hari baik untuk kebutuhan rumah tangga maupun kebutuhan non rumah tangga seperti penerangan jalan raya, penerangan taman dan lain-lain. Pembangunan fasilitasfasilitas umum yang baru itu pasti memerlukan adanya aliran listrik. Selain pembangunan fasilitas-fasilitas umum yang baru, masih banyak pula rumah tangga yang belum mendapatkan aliran listrik sehingga memerlukan pemasangan listrik baru. Mayoritas pelanggan yang menggunakan pelayanan di PLN tidak mengetahui dengan jelas alur dari proses pelayanan, sehingga mereka hanya menebak lamanya waktu pelayanan dari awal pendaftaran hingga selesainya pelayanan (terpasangnya listrik baru). Pada penelitian ini, ditentukan alur petri net proses pelayanan di PLN kemudian dibangun sebuah model penjadwalan pelayanan di PLN dengan menggunakan Aljabar Max-Plus. Dari model yang di
waktu
II. Aljabar Max-Plus Diberikan ℝℰ ≝ ℝ ∪ { } dengan ℝ adalah himpunan semua bilangan real dan ≝ −∞. Pada ℝℰ didefinisikan operasi berikut: ∀ , ∈ ℝℰ ⊕ ≝ max{ , } (1) ⊗ ≝ + Selanjutnya ditunjukkan (ℝℰ ,⊕,⊗) merupakan semiring dengan elemen netral ℰ dan elemen satuan = 0, karena untuk setiap , , ∈ ℝℰ berlaku: i.
⊕
= max { , } = max{ , } =
⊕
( ⊕ )⊕
= max {max{ , } , } = max{ , , } = max{ , max{ , }} = ⊕( ⊕ ) ⊕ ℰ = max{ , −∞} = max{−∞, } =ℰ⊕
ii. ( ⊗ ) ⊗ = ( + ) + =
B - 33
=
⊗( ⊗ )
+( + )
Prosiding Seminar Nasional FMIPA Universitas Negeri Surabaya ISBN : 978-602-17146-0-7 Surabaya 24 November 2012
⊗ = +0= 0+ = ⊗ = iii. ⊗ ℰ = + (−∞) = −∞ + = ℰ ⊗ iv. ( ⊕ ) ⊗
adalah contoh dari sebuah petri net sederhana
= max{ , } + = max{ + , + } =( ⊗ )⊕( ⊗ )
⊗ ( ⊕ ) = + max{ , } = max{ + , + } =( ⊗ )⊕( ⊗ )
Pangkat dalam Aljabar Max-Plus biasa diperkenalkan dengan menggunakan sifat assosiatif. Himpunan bilangan asli digabung dengan bilangan nol dinotasikan oleh ℕ dan didefinisikan untuk ∈ ℝ dan untuk semua ∈ ℕ dengan ≠ 0 [2] ⨂
≝
⊗ ⊗ …⊗
=
+
Misalkan berukuran ⊗
+⋯+
=
×
Gb1. Petri Net sederhana IV. Deadlock
Sebuah keadaan dikatakan deadlocks ketika transisi tertentu atau himpunan transisi tertentu pada Petri Net tidak dapat difire. Deadlock dapat disebabkan persaingan mendapatkan token. Ketika semua place tidak mendapatkan token maka akan terjadi deadlock Sebuah petri net dengan keadaan awal disebut live jika terdapat beberapa sample path sedemikian hingga sehingga selalu terdapat transisi yang dapat difire untuk setiap keadaan yang dapat dicapai dari [3].
(2)
adalah matriks persegi × maka dapat ditulis
⊗…⊗
=
⨂
(3)
III. Petri Net
Untuk mengetahui deadlock atau tidak maka harus dicari matriks backward ( ) dan matriks foward ( ). Elemen-elemen yang
Pada Petri net sebuah event berkaitan dengan transisi. Agar sebuah event dapat terjadi, beberapa keadaan harus dipenuhi terlebih dahulu. Informasi mengenai event dan keadaan ini masing-masing dinyatakan dengan transisi dan place. Petri Net adalah 4-tuple ( , , , ) dengan [2]: : Himpunan berhingga place, = ( , ,…, ) : Himpunan berhingga transisi, = ( , ,…, ) : Himpunan arc, ⊆( × )∪( × ) : fungsi bobot, ∶ → {1,2,3, … } Grafik Petri net terdiri dari dua macam titik atau node yaitu diasumsikan dengan lingkaran dan persegi. Lingkaran mewakili sebuah place sedangkan persegi mewakili sebuah transisi. Arc disimbolkan dengan panah yang menghubungkan place ke transisi maupun transisi ke place. Berikut
menyusun matriks foward merupakan ada atau tidaknya garis penghubung yang menghubungkan transisi ke place ( ), sedangkan elemenelemen penyusunnya backward merupakan ada atau tidaknyanya garis penghubung dari place ( ) ke transisi Jika terdapat garis penghubung maka bernilai satu tetapi jika tidak terdapat garis maka bernilai nol. Dari matrik backward dan foward, didapat: = − (4) Penentuan letak token pertama ( ) akan mempengaruhi transisi mana yang dapat difire sehingga juga akan mempengaruhi letak token selanjutnya ( + 1) atau dapat ditulis: ( + 1) = ( ) + (5) dimana merupakan transisi enable yang akan difire. B - 34
Prosiding Seminar Nasional FMIPA Universitas Negeri Surabaya ISBN : 978-602-17146-0-7 Surabaya 24 November 2012
Sebuah alur petri net dikatakan tidak deadlock atau live ketika ada sebuah ( + 1) yang elemen pada matriks bernilai satu. Jika semua elemen dari matriks ( + 1) bernilai nol maka alur petri net dikatakan deadlock.
VII. Hasil Penelitian Dari alur pelayanan pelanggan pada Gb2, jika dibuat alur petri netnya adalah sebagai berikut:
V. Alur Pelayanan Pelanggan Pelanggan
Web
Call Center
PP
No. Reg
No. Reg
Bayar di Bank
Layak
K. Tempat
Layak
Bayar di PP
K. Teknis
unlayak
unlayak
ttd Perjanjanjian
Perintah Kerja
Pemasangan instalasi
Update Data
Gb2. Alur Pelayanan Pelanggan VI. Metode Pertama-tama harus dicari dahulu alur petri net dari alur pelayana pelanggan. Setelah mendapatkan alur petri net selanjutnya dilakukan uji deadlock atau live dari alur petri net tersebut. Setelah mendapatkan hasil yang live atau tidak deadlock selanjutnya dibangun model penjadwalan pelayanan dengan menggunakan Aljabar Max-Plus. Hasil akhir yang di dapat adalah sebuah matriks model penjadwalan pelayanan.
Gb3. Alur Petri Net Pelayanan Pelanggan Dari alur petri net pelayanan pelanggan seperti Gb3, dapat dibentuk matrik foward, matriks backward dan matriks ( ). Matriks
berukuran (11 × 16), yaitu:
foward 0 ⎡1 ⎢ 0 ⎢ ⎢0 ⎢0 = ⎢0 ⎢0 ⎢0 ⎢0 ⎢0 ⎣0
B - 35
0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0
1 0⎤ ⎥ 0 ⎥ 0⎥ 0⎥ 0⎥ ; 0⎥ 0⎥ 0⎥ 0⎥ 0⎦
Prosiding Seminar Nasional FMIPA Universitas Negeri Surabaya ISBN : 978-602-17146-0-7 Surabaya 24 November 2012
Begitu juga matriks backward berukuran (11 × 16), yaitu: 1 ⎡0 ⎢ 0 ⎢ ⎢0 ⎢0 = ⎢0 ⎢0 ⎢0 ⎢0 ⎢0 ⎣0
1 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 1
Selanjutnya, jika dipilih transisi yang akan difire maka akan didapat (2) 0 ⎡0⎤ ⎢0⎥ ⎢ ⎥ ⎢0⎥ ⎢1⎥ = ⎢0⎥ (7) 0 ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎣0⎦
0 0⎤ ⎥ 0 ⎥ 0⎥ 0⎥ 0⎥ 0⎥ 0⎥ 0⎥ 0⎥ 0⎦
dan ( ) = [1 0 0 0 0 0 0 0 0 0 0] Sehingga dari persamaan (4) di dapat matriks dengan ukuran (11 × 16) dimana semua elemen penyusun matriks adalah nol kecuali pada , ; , ; , ; ; ; ; ; ; ; , , , , , , , ; bernilai −1 dan , ; , ; , ; , pada , ; , ; , ; , ; , ; , ; , ; , ; , ; , ; , ; , ; , ; ; ; bernilai 1 , , ,
Jika dilakukan secara berulang-ulang maka persamaan (6), persamaan (7) dapat digabungankan dan dibuat coverability tree yaitu [4]:
1 ⎡0⎤ ⎢0⎥ ⎢ ⎥ 0 ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎣0⎦
Alur petri net pada Gb3 terlihat ada tiga transisi yang bewarna merah artinya ketiga transisi yang berwarna merah tersebut merupakan transisi yang enable dan siap untuk difire. Pemilihan transisi yang akan difire hanya dapat dilakukan sekali. Misalkan dipilih transisi yang akan difire, sehingga didapat adalah = [1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] . Selanjutnya dengan menggabungkan matriks ( ), matriks , dan matriks ke persamaan (5) serta dengan memilih = 0 didapat: 0 ⎡1⎤ ⎢0⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ (1) = ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎣0⎦
0 ⎡1⎤ ⎢0⎥ ⎢ ⎥ 0 ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎣0⎦
0 ⎡0⎤ ⎢0⎥ ⎢ ⎥ 0 ⎢ ⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎣0⎦
0 ⎡0⎤ ⎢0⎥ ⎢ ⎥ 0 ⎢ ⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎣0⎦
0 ⎡0⎤ ⎢0⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎣1⎦
0 ⎡0⎤ ⎢0⎥ ⎢ ⎥ 0 ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎣0⎦
0 ⎡0⎤ ⎢0⎥ ⎢ ⎥ 0 ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥ ⎣0⎦
0 ⎡0⎤ ⎢0⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎣0⎦
0 ⎡0⎤ ⎢0⎥ ⎢ ⎥ 0 ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎣0⎦
Gb4. Coverability Tree Selanjutnya sebelum dibangun model penjadwalan pelayanan, pertama diberikan alur petri net pelayanan pelanggan dengan menggunakan waktu. Alur petri net pelayanan pelanggan yang dihubungkan dengan waktu sama seperti Gb3. Tetapi pada masing-masing transisi diberikan
(6)
B - 36
Prosiding Seminar Nasional FMIPA Universitas Negeri Surabaya ISBN : 978-602-17146-0-7 Surabaya 24 November 2012
urutan pelayanan ( ) sehingga masingmasing transisi yang tadinya hanya menjadi ( ). Selain itu pada masingmasing transisi diberikan lamanya waktu pelayanan Peletakkan lamanya , . waktu pelayanan disesuaikan dengan transisi masing-masing, sehingga diperoleh data sebagai berikut:
Jika diasumsikan tidak ada uji teknik di gudang dan uji teknik di rumah pelanggan yang tidak layak, maka: ( − 1) = 0 ( − 1) = 0
(21)
Sehingga dari persamaan (8), (20) dan persamaan (21) dapat dibuat bentuk matriks dari model Aljabar Max-Plus dari Petri Net sistem pelayanan yang dikaitkan dengan waktu yaitu:
( )= ( − 1) (8) , + ( ) = max { ( ), ( − 1), ( − 1), ( − 1)} (9) ( )= ( ) + , (10) ( )= ( ) + , (11) ( )= ( ) + , (12) ( )= ( ) + , (13) ( )= ( )+ , (14) ( ) = ( )+ , (15) ( )= ( ) + (16) , ( )= ( ) + (17) , ( )= ( ) + (18) , ( )= ( ) + (19) ,
⎡ ⎢ ⎢ ⎣
( ( ( (
) ⎤ ) ⎥= )⎥ )⎦
,
0 0
0 0
0 0
( ( ( (
⎡ ⨂⎢ 0 ⎢ 0 ⎣
− 1) ⎤ − 1)⎥ − 1) ⎥ − 1) ⎦
(22) dimana =
+
,
+
,
+ +
,
+
,
+
,
, ,
+
,
+
,
dan =
, + , + , + + + + , , , serta dipilih agar
,
⨁ =
Selanjutnya dengan menggabungkan semua persamaan (8) – (19) didapatkan:
⨂
( − 1) ⨁
⨂
,
+
,
( − 1)
⨂ ( − 1) ⨁ ⨂ ( − 1) ( − 1) , ⨂
(0) = (0) = dengan keadaan awal 0 Jika waktu yang dibutuhkan pelanggan untuk memulai melakukan pendaftaran adalah 5 menit, waktu yang , dibutuhkan pelanggan untuk melakukan pendaftaran melalui web atau call center ( , ) diperkirakan 15 menit, waktu yang dibutuhkan pelanggan untuk melakukan pembayaran biaya pemasangan di bank ( , ) diperkirakan 24 × 60 = 1440 , waktu yang dibutuhkan petugas untuk melakukan uji teknik di gudang ( , ) diperkirakan 10 menit, waktu yang dibutuhkan petugas untuk melakukan uji teknik ke rumah pelanggan
( ) = max {( , + , + , + , + , + + + , , , ( + + − 1)), ( , , + , + , + , + , + + + , , , + ( − 1)) , ( , + , + , + , + , + , ( + + + − 1)) , , , ( , + , + , + , + , ( − 1))} + , + , + ,
(20)
B - 37
Prosiding Seminar Nasional FMIPA Universitas Negeri Surabaya ISBN : 978-602-17146-0-7 Surabaya 24 November 2012
diperkirakan 24 × 60 = 1440 , waktu yang dibutuhkan petugas untuk membuat surat perintah kerja pemasangan instalasi ke rumah pelangga ( , ) diperkirakan 10 menit, waktu yang dibutuhkan petugas untuk melakukan pemasangan instalasi ke rumah pelanggan diperkirakan 2 × , 60 = 120 , waktu yang dibutuhkan petugas untuk melakukan update data pasca pemasangan instalasi ke rumah pelanggan ( , ) diperkirakan 10 menit dan waktu yang dibutuhkan pelanggan untuk meninggalkan sistem pelayanan diperkirakan 30 menit , maka didapat: = 2880 ; = 2875 (23) Sehingga persamaan (22) menjadi ,
⎡ ⎢ ⎢ ⎣
( ( ( (
) 5 ⎤ ) ⎥ = 2880 )⎥ 0 0 )⎦
2875 0 0
2875 0 0
⎡ 2875 ⨂⎢ 0 ⎢ 0 ⎣
( ( ( (
X. Daftar Pustaka [1] Subiono, Aljabar Maxplus dan Terapannya, Buku Ajar Kuliah Pilihan Pasca Sarjana Matematika, ITS, Surabaya, 2012. [2] Adzkiya Dieky, Membangun Model Petri Net Lampu Lalu Lintas dan Simulasinya, Tesis Magister, ITS, Surabaya, 2008. [3] Wetjen. D, Discrete Event System Analysis Using the Max-Plus-Algebra, Magister’s Thesis, Eindhoven of Technology, Eindhoven, (2004). [4] Bobbio Andrea, System Modelling with Petri Net, Istituto Elettrotecnico Nazionale Galileo Ferraris Strada delle Cacce 91, 10135 Torino, Italy, 1990.
− 1) ⎤ − 1) ⎥ − 1) ⎥ − 1) ⎦
VIII. Kesimpulan Kesimpulan yang dapat diambil dari penelitian ini adalah: 1. Pembuatan alur petri net pada sebuah sistem harus dipertimbangkan deadlock dan live-nya. 2. Misalkan pelanggan pertama (0) pada melakukan pendaftaran pukul 07.00 hari Kamis 1-11-2012 maka proses pelayanan total berakhir pada 2880 menit kemudian yaitu pada hari Sabtu 3-11-2012 pukul 07.00 IX. Ucapan Terima Kasih Ucapan terima kasih pertama diberikan kepada kakak penulis yang bekerja di PLN karena telah memberikan alur pelayanan di PLN yang sebenarnya. Kedua diberikan kepada Bapak Dr. Subiono, MS sebagai dosen pembimbing tesis penulis atas batuan beliau dalam mengarahkan dan membimbing penulis. Dan yang ketiga diberikan kepada Bapak Dieky Adzkiya, S.Si, M.Si karena beliau telah memberikan berbagai referensi buku dan makalah tentang Petri Net. B - 38
