PENERAPAN ALJABAR MAX-PLUS BILANGAN KABUR PADA JARINGAN ANTRIAN DENGAN WAKTU AKTIFITAS KABUR

Prosiding Seminar Nasional Penelitian, Pendidikan dan Penerapan MIPA Fakultas MIPA, Universitas Negeri Yogyakarta, 16 Mei 2009

PENERAPAN ALJABAR MAX-PLUS BILANGAN KABUR PADA JARINGAN ANTRIAN DENGAN WAKTU AKTIFITAS KABUR 1

M. ANDY RUDHITO, 2SRI WAHYUNI, 3ARI SUPARWANTO, AND 4F. SUSILO

1

Mahasiswa S3 Matematika FMIPA UGM dan Staff Pengajar FKIP Universitas Sanata Dharma, Paingan Maguwoharjo Yogyakarta 2,3 Jurusan Matematika FMIPA Universitas Gadjah Mada, Sekip Utara Yogyakarta 4 Jurusan Matematika FST , Universitas Sanata Dharma, Paingan Maguwoharjo Yogyakarta Abstrak Makalah ini membahas tentang pemodelan dan waktu kabur sikel layanan jaringan antrian fork-join taksiklik kapasitas penyangga takhingga dengan waktu aktifitas kabur, dengan menggunakan aljabar max-plus bilangan kabur. Hasil pembahasan menunjukkan bahwa dinamika jaringan antrian fork-join taksiklik kapasitas penyangga takhingga dengan waktu aktifitas kabur dapat dimodelkan ke dalam suatu persamaan matriks atas aljabar max-plus bilangan kabur. Kata-kata kunci: aljabar max-plus bilangan kabur, nilai eigen max-plus bilangan kabur, jaringan antrian fork-join dan waktu aktifitas kabur..

PENDAHULUAN Dalam masalah pemodelan dan analisa suatu jaringan, kadang-kadang waktu aktifitasnya belum diketahui. Hal ini misalkan karena jaringan masih pada tahap perancangan, data-data mengenai waktu aktifitas belum diketahui secara pasti maupun distribusinya. Waktu aktifitas ini dapat diperkirakan berdasarkan pengalaman maupun pendapat dari para ahli maupun operator jaringan tersebut. Dalam situasi ini, waktu aktifitas jaringan dapat dimodelkan dalam suatu bilangan kabur (fuzzy number), yang selanjutnya di sebut waktu aktifitas kabur. Aljabar max-plus (himpunan semua bilangan real Rdilengkapi dengan operasi max dan plus) telah dapat digunakan dengan baik untuk memodelkan dan menganalisis secara aljabar masalahmasalah jaringan, seperti masalah: penjadwalan (proyek) dan sistem antrian, lebih detailnya dapat dilihat pada Bacelli, et al. (2001), Rudhito, A. (2003). Dalam Krivulin N.K. (1996a) dan Rudhito, A dan Suparwanto, A (2008) telah dibahas pemodelan dinamika jaringan antrian fork-join taksiklik dengan kapasitas penyangga takhingga ke dalam suatu persamaan matriks aljabar max-plus. Penyusunan model tersebut menggunakan suatu hasil dalam penyelesaian sistem persamaan linear iteratif max-plus. Konsep aljabar max-plus bilangan kabur yang merupakan perluasan konsep aljabar max-plus, di mana elemen-elemen yang dibicarakan berupa bilangan kabur telah dibahas dalam Rudhito, dkk (2008a). Pembahasan mengenai matriks atas aljabar max-plus bilangan kabur telah dibahas dalam Rudhito, dkk (2008a). Dalam Rudhito, dkk (2008b) telah dibahas eksistensi dan ketunggalan penyelesaian sistem persamaan linear iteratif max-plus bilangan kabur. Sejalan dengan cara pemodelan dan pembahasan waktu periodik layanan jaringan seperti dalam Rudhito, A dan Suparwanto, A (2008), dan dengan memperhatikan hasil-hasil pada aljabar maxplus bilangan kabur, makalah ini akan membahas pemodelan jaringan antrian fork-join taksiklik kapasitas penyangga takhingga dengan waktu aktifitas kabur, dengan menggunakan aljabar max-plus bilangan kabur. M-265

M. Andy Rudhito/Penerapan Aljabar Max-Plus

PEMBAHASAN Aljabar Max-Plus Bilangan Kabur Pembahasan diawali dengan menyajikan beberapa definisi dan hasil dalam aljabar max-plus bilangan kabur dan sistem persamaan linear iteratif max-plus bilangan kabur. Definisi 1 Diberikan F(R) ε~ := F(R) ∪ { ε~ } dengan F(R) adalah himpunan semua bilangan kabur dan ε~ := {−∞} , dengan potongan-α-nya adalah ε α = [−∞,−∞] , ∀α ∈[0, 1]. Pada (F(R)) ε~ didefinisikan operasi

~ , b~ ∈ F(R) ~ dengan aα = [ aα , a α ] ∈ I(R)max dan bα = [ bα , b α ]∈ sebagai berikut. Untuk setiap a ε I(R)max, i)

~ ~ ~ a~ ⊕ b = max( a~ , b ) adalah bilangan kabur dengan potongan-α-nya α α (a ⊕ b)α := [ a ⊕ b , a α ⊕ b α ], untuk setiap α ∈ (0, 1]

~ ~ ~ ~ ~⊗ ii) a b = a + b adalah bilangan kabur dengan potongan-α-nya α

α

(a ⊗ b)α := [ a ⊗ b , a α ⊗ b α ], untuk setiap α ∈ (0, 1].

~

~

Dapat ditunjukkan bahwa F(R)max := (F(R)ε, ⊕ , ⊗ ) merupakan semiring idempoten komutatif, yang juga disebut aljabar max-plus bilangan kabur, yang selanjutnya cukup dituliskan dengan F(R)max . Definisi 2 ~ ~ ~ Didefinisikan F(R) mmax× n := { A = ( A ij) A ij ∈ F(R)max , untuk i = 1, 2, ..., m dan j = 1, 2, ..., n }. Matriks anggota F(R) mmax× n disebut matriks atas aljabar max-plus bilangan kabur, yang selanjutnya cukup disebut matriks bilangan kabur.

~

~

Operasi ⊕ dan ⊗ pada F(R)max dapat diperluas untuk operasi-operasi matriks bilangan kabur pada

~ ~

×n didefinisikan (F(R) mmax× n . Khususnya untuk matriks A , B ∈ F(R) nmax

~ ~ ~

~ ~ ~

~ ~ ~

( A ⊕ B )ij = A ij ⊕ B ij dan ( A ⊗ B )ij =

n

~~ ⊕A

ik

~ ⊗ Bkj .

k =1

Definisi 3 Didefinisikan F(R) nmax := { ~ xn ]T | ~ xi ∈ F(R)max , i = 1, 2, ... , n }. Perhatikan bahwa x =[ ~ x1 , ~ x2 , ... , ~ ×1 F(R) nmax dapat dipandang sebagai F(R) nmax . Unsur-unsur dalam F(R) nmax disebut vektor bilangan kabur. Definisi 4 ~ ~ ~ * ∈ F(R) n disebut ×n dan b ∈ F(R) nmax . Vektor bilangan kabur x Diberikan A ∈ F(R) nmax max

~ ~ ~ ~ ~ ~ = A penyelesaian bilangan kabur sistem x ⊗ x ⊕ b jika x~ * memenuhi sistem tersebut. Teorema 1 ~ ~ ~ * ×n dan b ∈ F(R) nmax . Jika A semi-definit maka vektor bilangan kabur ~ Diberikan A ∈ F(R) nmax x * dengan ~ xi =

c~α di mana c~α adalah himpunan kabur dalam R dengan fungsi keanggotaan µ  α i

∈[0, 1]

i

c~α

(x) =

α χ ( A* ⊗b )α (x) , di mana χ ( A* ⊗b )α adalah fungsi karakteristik himpunan ( A* ⊗ b )αi , merupakan i i ~ ~ ~ ~ ~ ~ ~ = A penyelesai bilangan kabur sistem x ⊗ x ⊕ b . Lebih lanjut jika A definit, maka penyelesaian tersebut tunggal. M-266

Prosiding Seminar Nasional Penelitian, Pendidikan dan Penerapan MIPA Fakultas MIPA, Universitas Negeri Yogyakarta, 16 Mei 2009

Bukti : (dapat dilihat pada Rudhito, dkk., 2008b) Pemodelan Jaringan Antrian Diperhatikan suatu jaringan dengan n titik pelayan tunggal (single-server) dan pelanggan klas tunggal (single-class). Struktur jaringan antrian ini dapat dinyatakan dengan graf berarah tak siklik G = (N, A) dengan busur yang ditentukan oleh rute transisi pelanggan. Untuk setiap titik i ∈ N, didefinisikan himpunan pendahulu (predecessors) dan penerus (saccessors) titik i berturut-turut dengan P(i) = { j | (j, i) ∈ A ) dan S(i) = { j | (j, i) ∈ A ). Untuk setiap titik i ∈ N terdiri dari sebuah pelayan dan penyangga dengan kapasitas takhingga yang bekerja dengan prinsip First-In First-Out (FIFO). Pada waktu-awal jaringan bekerja diasumsikan bahwa pelayan bebas pelanggan, penyangga untuk semua titik i dengan P(i) ≠ ∅ dalam keadaan kosong, sedangkan penyangga titik yang tidak mempunyai pendahulu (P(i) = ∅) mempunyai takhingga banyak pelanggan. Operasi fork pada titik i diawali setiap kali layanan sebuah pelanggan selesai dan diperoleh beberapa pelanggan baru untuk antrian berikutnya. Banyaknya pelanggan baru yang muncul pada titik i sebanyak titik dalam S(i). Pelanggan-pelanggan baru ini secara serentak meninggalkan titik i dan menuju titik-titik j ∈ S(i) secara terpisah. Operasi join pada titik i terjadi saat pelanggan-pelanggan datang ke titik i , tidak hanya di menunggu di penyangga, tetapi juga menunggu sedikitnya satu pelanggan dari setiap titik j ∈ P(i) datang. Segera setelah pelanggan datang, bersama satu pelanggan dari setiap titik pendahulunya, mereka bersatu menjadi satu pelanggan dan masuk dalam penyangga dalam pelayan berikutnya. Dalam pengoperasian jaringan ini diasumsikan bahwa perpindahan pelanggan antar titik tidak memerlukan waktu. ~ (k) = waktu kabur kedatangan pelanggan ke-k pada titik i. Misalkan a i

~ d i (k) = waktu kabur keberangkatan pelanggan ke-k pada titik i. ~ tik = waktu kabur layanan untuk pelanggan ke-k pada pelayan i. ~ ~ ~ Diasumsikan jaringan mulai beroperasi pada nol waktu, yaitu d i (0) = 0 = 0 dan d i (k) = ε = ε~ untuk semua k < 0, i = 1, ..., n. Dinamika antrian pada titik i dapat dinyatakan dengan

~ ~ ~ ~ d i (k) = max( tik + a~i (k), tik + d i (k− 1))

(1)

~ max (d j (k )), jika P(i ) ≠ φ , ~ ai (k) =  j∈P (i )  ~ ε, jika P(i ) = φ .

(2)

Dengan notasi aljabar max-plus interval persamaan (1) dan (2) dapat dituliskan sebagai berikut

~ ~ ~ ~ d i (k) = ( ~ tik ⊗ a~i (k)) ⊕ ( ~ tik ⊗ d i (k−1))

(3)

~  ~ d j (k ), jika P(i ) ≠ φ , ⊕ a~i (k) =  j ∈ P (i )  ε~, , jika P(i ) = φ .

(4)

M-267

M. Andy Rudhito/Penerapan Aljabar Max-Plus

~ ~ ~ ~ ~ d (k) = [ d1 (k) , d 2 (k), ... , d n (k)]T , a~ (k) = [ a~1 (k) , a~2 (k), ... , a~n (k)]T dan Tk = ~ ε    . Persamaan (3) dan (4) di atas dapat dituliskan menjadi ~  tnk 

Misalkan

~  t1k    ~ ε

~ ~ ~ ~ ~ ~ ~ d (k) = ( Tk ⊗ a~ (k)) ⊕ ( Tk ⊗ d (k −1)).

(5)

~ ~ ~ a~ (k) = G ⊗ d (k),

(6)

~ 0 = 0 , jika j ∈ P(i ) ~ ~ dengan matriks G yang unsur-unsur adalah G ij =  . ~  ε = ε , untuk yang lain ~ Perhatikan bahwa G merupakan matriks adjesensi dari graf stuktur jaringan antrian. Dari persamaan (5) dan (6) dapat dituliskan persamaan

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ d (k) = ( Tk ⊗ G ⊗ d (k)) ⊕ ( Tk ⊗ d (k −1)).

(7)

Teorema 1. Diberikan jaringan antrian fork-join tak siklik dengan waktu aktifitas interval, dengan graf struktur jaringannya yang mempunyai panjang lintasan terpanjang p dan matriks adjesensi G. Persamaan state eksplisit jaringan tersebut adalah

~ ~ ~ ~ d (k) = A (k) ⊕ d (k −1),

(8)

~ ~ 0 ε  ~ ~ ~ ~ ~ ~ p~ ~ ~  dengan A (k) = ( E ⊕ ( Tk ⊗ G )) ⊗ Tk dan E =    ~ ~ 0 ε Bukti: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Dari persamaan (7) dapat dituliskan d (k) = ( Tk ⊗ G ) ⊗ d (k) ⊕ Tk ⊗ d (k −1)). Karena G adalah matriks adjesensi graf taksiklik dengan panjang lintasan p maka menurut hasil pada Rudhito, A dan

~ ε ε~ ~ q ~  untuk semua q  Suparwanto, A (2008) dan Rudhito, dkk (2008b), diperoleh G ⊗ = =     ~ ε~  ε

ε

> p.

ε~

~

~

Akibatnya ( Tk ⊗ G ))q = untuk semua q > p. Selanjutnya menurut hasil pada Rudhito, A dan Suparwanto, A (2008) dan Rudhito, dkk (2008b), persamaan di atas mempunyai penyelesaian

~ ~ ~ ~ ~ ~ ~ d (k) = ( E ⊕ ( Tk ⊗ G ))p ⊗ ( Tk ⊗ d (k −1)) ~

~

~

~ ~ ~

= (( E ⊕ ( Tk ⊗ G ))p ⊗ Tk ) ⊗ d (k −1))

M-268

■

Prosiding Seminar Nasional Penelitian, Pendidikan dan Penerapan MIPA Fakultas MIPA, Universitas Negeri Yogyakarta, 16 Mei 2009

Berikut diberikan contoh perhitungan pada jaringan antrian dengan mengambil waktu kabur ~, layanan yang berupa bilangan kabur segitiga (triangular fuzzy number). Bilangan kabur segitiga a dilambangkan dengan BKS(a1, a, a2), yang kadang cukup dituliskan (a1, a, a2), adalah suatu bilangan kabur dengan fungsi keanggotaan

 x − a1  a − a , a1 ≤ x ≤ a 1   a2 − x , a ≤ x ≤ a2 . µ a~ (x) =  a a −  2 lainnya  0,  ~ di atas adalah interval terbuka (a , a ) dan potongan-α-nya adalah aα = Pendukung (support) a 1 2

[(a − a1 )α + a1 ,−(a2 − a)α + a2 ] , α ∈ (0,1 ] .  ,α = 0  [a1 , a2 ] Contoh 1. Jaringan antrian fork-join taksiklik dengan n = 5 diperlihatkan dalam Gambar 1 berikut.

Gambar 1.

ε ε  ~ Matriks adjesensi dari graf pada jaringan di atas adalah G =  0  0 ε

ε ε ε ε ε ε ε ε  ε ε ε ε  . Nampak bahwa  0 ε ε ε ε 0 0 ε  ~ panjang lintasan terpanjangnya adalah p = 2. Dari persamaan (8) diperoleh persamaan state d (k) = ~ ~ ~ A (k) ⊕ d (k −1), dengan ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ A (k) = ( E ⊕ ( Tk ⊗ G ))2 ⊗ Tk = ( E ⊕ ( Tk ⊗ G ) ⊕ ( Tk ⊗ G )2) ⊗ Tk ~ t1k   ~ ε =  ~ ~  t1k ⊗ ~ t3k  ~~ ~ t1k ⊗ t4 k  ~ ~ ~~ ~~ ~  t1k ⊗ ( t3k ⊕ t4 k ) ⊗ t5 k

~ ε ~ t2 k ~ ε ~~ ~ t2 k ⊗ t4 k ~ ~ ~ t2 k ⊗ ~ t4 k ⊗ ~ t5 k

~ ε ~ ε ~ t

3k

~ ε ~~ ~ t3k ⊗ t5 k

~ ε ~ ε ~ ε ~ t4 k ~ ~ t4 k ⊗ ~ t5 k

~ ε  ~ ε . ~ ε  ~ ε ~ t5 k  M-269

M. Andy Rudhito/Penerapan Aljabar Max-Plus

~

Misalkan lama waktu layanan untuk pelanggan ke-k pada pelayan i adalah sebagai berikut: t1k = (2, 3,

~

~

~

~

4), t2 k = (3, 4, 5), t3k = (5, 6, 6), t3k = (4, 4, 5), t5 k = (3, 5, 6),

ε~ ε~ ε~ ε~   (2,3,4)  ε~ (3,4,5) ε~ ε~ ε~   ~ maka diperoleh A (k)=  (7,9,10) (5,6,6) ε~ ε~ ε~  . Sehingga untuk k =   (7,8,10) ε~ (4,4,5) ε~   (6,7,9) (10,14,16) (10,13,16) (8,11,12) (7,9,11) (3,5,6) 1, 2 diperoleh ~ ε~ ε~ ε~ ε~  (0,0,0)  (2,3,4)   d1 (1)   (2,3,4)   (0,0,0)  ~ ~ ~ ~ ~   ε ε ε ε  (3,4,5)   (3,4,5)   d 2 (1)  ε~ ε~ ε~  ⊗ (0,0,0) =  (7,9,10)  , (5,6,6)  d~ (1)  =  (7,9,10)      ~3    ε~ ε~  (7,8,10) (4,4,5) d 4 (1)  (6,7,9) (0,0,0)  (7,8,10)   d~ (1)  (10,14,16) (10,13,16) (8,11,12) (7,9,11) (3,5,6) (0,0,0) (10,14,16)  5  ~ ε~ ε~ ε~ ε~   d1 (2)   (2,3,4)   ~ ε~ ε~ ε~ ε~  (3,4,5) d 2 (2) =  ε~ ε~ ε~  (5,6,6)  d~ (2)   (7,9,10) 3    ~ ε~ ε~  (7,8,10) (4,4,5) d 4 (2)  (6,7,9)  d~ (2)  (10,14,16) (10,13,16) (8,11,12) (7,9,11) (3,5,6)  5 

⊗

 (2,3,4)   (4,6,8)   (3,4,5)   (6,8,10)  = .   (7,9,10)  (12,15,16)      (7,8,10)   (11,12,15)  (10,14,16) (15,2022) 

DAFTAR PUSTAKA Bacelli, F., et al. 2001. Synchronization and Linearity. New York: John Wiley & Sons. Krivulin, N.K., 1996a. The Max-Plus Algebra Approach in Modelling of Queueing Networks Proc. 1996 SCS Summer Computer Simulation Conference (SCSC-96), Jaly 21-25, The Society for Computer Simulation, 485-490. Rudhito, Andy. 2003. Sistem Linear Max-Plus Waktu-Invariant. Tesis: Program Pascasarjana Universitas Gadjah Mada. Yogyakarta. Rudhito, Andy dan Suparwanto, Ari 2008. “Pemodelan Aljabar Max-Plus dan Evaluasi Kinerja Jaringan Antrian Fork-Join Taksiklik dengan Kapasitas Penyangga Takhingga”. Prosiding Seminar Nasional Sains dan Pendidikan Sains, UKSW. Salatiga. 12 Januari 2008. Rudhito, Andy, dkk. 2008a. “Sistem Persamaan Linear Max-Plus Bilangan Kabur”. Prosiding Konferensi Nasional Matematika XIV FMIPA UNSRI Palembang 24 – 27 Juli 2008. Rudhito MA, Wahyuni S, Suparwanto A, and Susilo F, 2008b, Iterative System of Fuzzy Number MaxPlus Linear Equations. Proceeding on the International Conference on Mathematics and Natural Sciences 2008, ITB, Bandung, Indonesia, October 28 - 30, 2008.

M-270