aplikasi aljabar max

Modifikasi Penyelesain Sistem Persamaan Linier pada Analisis Jaringan Proyek PERT-CPM dengan Pendekatan Aljabar Max-Plus Oni Soesanto Abstrak: PERT-CPM telah dikenal sebagai metode untuk menganalisis jaringan kerja pada suatu proyek serta analisis lintasan kritisnya. Pada analisis jaringan PERT-CPM memuat masalah sinkronisasi dan masalah yang diperlukan ketersediaan beberapa sumber pada waktu yang bersamaan. Pada analisis listasan kritis meliputi waktu awal paling cepat (Earliest Start Time), waktu penyelesaian paling akhir (latest completion time) setiap titik pada jaringan dan waktu mengambang (float time). Pada Aljabar Max Plus penyelesaian menggunakan operasi matriks sebagai modifikasi sistem persamaan linier yang biasa dipakai pada linear programming. Untuk menggambarkan jaringan kerja lintasan kritisnya digunakan graph taksiklik. Pada makalah ini membahas suatu metode analisis lintasan kritis jaringan proyek dengan menggunakan pendekatan Aljabar Max-Plus. Kata kunci: Aljabar Max-Plus, PERT-CPM, analisis jaringan, lintasan kritis 1. Pendahuluan Analisis jaringan proyek adalah suatu teknik analisis yang digunakan pada manajemen proyek untuk melaksanakan tugas guna membuat perencanaan, mengatur jadwal pelaksanaan, melakukan pengawasan dan mengambil keputusan. Dalam bidang matematika secara khusus, analisis jaringan proyek dibahas dalam riset operasi, metode yang telah banyak dikenal dan banyak digunakan dalam menyelesaikan analisis jaringan proyek adalah metode CPM (Critical Path Method) dan PERT (Project Evaluation and Review Technique). Secara prinsip proses kedua metode tidak jauh berbeda, perbedaannya adalah pada CPM berlaku pada activity times yang umumnya diketahui, sedangkan pada PERT berlaku uncertain activity times yang meliputi tiga kondisi waktu yaitu optimistic time, most likely time dan pessimistic time. Jaringan proyek dapat dimodelkan sebagai suatu graph berarah yang diboboti. Dengan menggambar jaringan proyek maka akan diperoleh suatu gambaran tentang logika ketergantungan atau logika kegiatan proses produksi, mengetahui bahaya akan keterlambatan proses produksi, melihat kemungkinan perubahan jalur proses produksiTugas Mata Kuliah SED Oni Soesanto/120821013

1

yang lebih baik atau lebih ekonomis, mempelajari kemungkinan percepatan dari salah satu atau beberapa jalur kegiatan dan mengetahui batas waktu penyelesaian keseluruhan proses produksi. Aljabar Max-Plus (himpunan R{}, dengan R adalah himpunan semua bilangan real, yang dilengkapi dengan operasi maximum dan penjumlahan) telah digunakan untuk memodelkan dan menganalisis sistem produksi sederhana, dengan fokus analisa pada masalah input-output system. Pemodelan dan analisa suatu jaringan proyek dengan pendekatan ini dapat memberikan hasil analitis dan diharapkan lebih mudah pada komputasinya.

2. Aljabar Max-Plus dan notasinya Pada bagian ini akan dijelaskan secara singkat mengenai Aljabar Max-Plus terutama yang berkaitan dengan masalah yang akan dibahas pada bagian selanjutnya. Aljabar Max-Plus terdiri dari himpunan R = R{}, dimana R adalah himpunan bilangan real dan = yang dikaitkan dengan dua operasi maksimum (max) dan tambah (+), dengan notasi menyatakan operasi maksimum dan menyatakan operasi tambah. Sehingga untuk suatu operasi terhadap dua variabel a dan b yaitu a b berarti max(a,b) dan a b berarti a + b. Notasi dan pada Aljabar MaxPlus masingmasing mempunyai kemiripan dengan operasi tambah (+) dan kali (x) pada aljabar biasa. Untuk selanjutnya untuk operasi a = ab menyatakan perkalian a dan b dalam aljabar biasa. 3. Beberapa definisi dalam Aljabar Max-Plus Sebagaimana telah dibahas pada bagian sebelumnya, pada bagian ini akan diberikan disampaikan beberapa definisi yang terkait dengan Aljabar Max-Plus. Definisi 1: Diberikan R = R {} dengan = -, Pada R, a,b R didefinisikan sebagai operasi berikut: a b = max(a, b) dan a b = a+b i. (R, , ) merupakan semiring komutatif idempoten dengan elemen netral =- dan elemen satuan e = 0.b

Tugas Mata Kuliah SED Oni Soesanto/120821013

2

ii. (R, , ) merupakan semifield, yaitu bahwa (R, , ) merupakan semiring komutatif di mana untuk setiap a R terdapat -a sehingga berlaku a (-a)= 0. Untuk selanjutnya (R, , )disebut dengan Aljabar Max-Plus, yang dinotasikan dengan Rmax. Relasi yang didefinisikan pada Rmax sebagai berikut x m y jika x y = y, merupakan urutan parsial pada Rmax. Lebih lanjut relasi ini m merupakan urutan total pada Rmax. Pangkat k dari elemen x R dilambangkan dengank x didefinisikan x = 0, x = x x

0

k

k 1

.

Definisi 2: Operasi dan pada Rmax dapat diperluas untuk operasi-operasi matriks dalammxn mxn mxn Rmax , di mana Rmax = {A = (Aij)|Aij Rmax , untuk i = 1, 2,..., m dan j = 1, 2,...,

n}sehingga: i. ii. iii. iv.mxn Untuk A, B Rmax didefinisikan A B, dengan (A B)ij = Aij Bij .

Untuk A Rmax , B Rmax didefinisikan A B, dengan (A B)ij = (aij bkj )mxp pxn

p

k =1

0 , jika i = j nxn Matriks E Rmax dengan (E)ij = , jika i jmxn Matriks Rmax dengan ()ij = , i,j

4. Definisi Graph dalam Aljabar Max-Plus Diberikan graph berarah G = (V, A) dengan V adalah suatu himpunan berhingga tak kosong yang anggotanya disebut titik dan A adalah suatu himpunan pasangan terurut titik-titik pada garis V. Suatu lintasan dalam graph berarah G adalah suatu barisan berhingga garis (i1, i2), (i2, i3), ... , (il-1, il) dengan (ik, ik+1)A untuk suatu lN , di mana N = himpunan semua bilangan asli, dan k = 1, 2, ... , l-1. Titik i1 disebut titik awal lintasan dan titik il disebut titik akhir lintasan. Suatu lintasan disebut sirkuit jika titik awal dan titik akhirnya sama. Suatu graph berarah G = (V, A) dengan V = {1, 2, , ... , n} dikatakan strongly connected jika untuk setiap i, jV, ij , terdapat suatu lintasan dari i ke j.


3

Suatu graph yang memuat sirkuit disebut graph siklik, sedangkan suatu graph yang tidak memuat sirkuit disebut graph taksiklik. Graph berarah G dikatakan berbobot jika setiap garis (j, i) A dikawankan dengan suatu bilangan real Aij. Bilangan real Aij disebut bobot garis (j, i), dilambangkannxn dengan w(j, i). Graph preseden dari matriks A Rmax adalah graph berarah berbobot

G(A) = (V, A) dengan V = {1, 2, ... , n}, A = {( j, i ) | w( i, j ) = A ij , i, j }. Sebaliknya untuk setiap graph berarah berbobot G = (V, A) selalu dapat didefinisikan wij , jika (i , j ) A nxn suatu matriks A Rmax dengan Aij = , yang disebut matriks bobot , jika (i , j ) A graph G. 5. Analisis Lintasan Kritis Pada bagian ini akan dibahas beberapa pengertian dasar, definisi dan teorema pada analisis jaringan PERT-CPM serta pendekatan dan penyelesaian masalah dengan Aljabar Max-Plus. Suatu jaringan proyek S adalah suatu graph berarah berbobot strongly connected taksiklik S = (V, A), dengan V = {1, 2, , ... , n} yang memenuhi : jika (i, j) A, maka i < j, dimana garis menyatakan suatu aktivitas sedangkan bobot menyatakan waktu aktivitas. a. Waktu Awal Paling Cepat (Earlies Start Time) Untuk menentukan waktu awal paling cepat (earlies start time) untuk setiap aktivitas yang berasal dari titik i. Dengan perhitungan maju (forward) pada PERTCPM, maka dengan menggunakan Aljabar Max-Plus.

Teorema 1 Diberikan suatu jaringan proyek dengan n titik dan A adalah matriks bobot graph berarah berbobot jaringan tersebut. Vektor ESi diberikan oleh x e = A* b e = (E A A n 1 ) b e di mana be = [0, , ... , ]T.e Misalkan ESi = xi menyatakan waktu awal paling cepat yang berasal dari titik i ,


4

waktu aktivitas dari titik j ke titik i, jika ( j , i ) A A = , jika ( j , i ) A (= ), Dengan asumsi bahwa aktivitas jaringan dimulai pada titik i=1 pada waktu sama dengan nol, yaitu x1e = 0, sehingga persamaan dapat ditulis: 0 , jika i = 1 xie = max ( A + x e ) , jika i > 1 j 1 j n ij Dengan menggunakan notasi pada aljabar max plus dapat dituliskan 0 , jika i = 1 x = ( A x e ) , jika i > 1 j 1 j n ij e i

Misalkan A adalah matriks yang bersesuaian dengan graph berarah berbobot jaringan tersebut, xe = [ x1 , x 2 , ... x n ]T dan be = [0, , ... , ]T, persamaan dapat dituliskan ke dalam suatu sistem persamaan linear max-plus berikut x e= A x e b e Karena jaringan proyek merupakan graph berarah taksiklik, maka tidak terdapat sirkuit, sehingga semua sirkuit dalam jaringan mempunyai bobot takpositif. Dengan demikian x e = A* b e Karena jumlah titik dalam jaringan proyek ini adalah n, maka panjang lintasan terpanjangnya tidak akan melebihi n -1. Dengan demikian dalam hal ini persamaan dapat ditulis menjadi x e = A* b e = (E A A n 1 ) b e yang merupakan vektor waktu paling awal setiap titik i dapat mulai aktif. Dalam hal ini (A*)n1 merupakan bobot maksimum lintasan dari titik awal hingga titik akhir proyek, sehingga merupakan waktu penyelesaian proyek. b. Waktu Penyelesaian Paling Akhir (Latest Completion Time) Untuk menentukan waktu penyelesaian paling akhir (latest completion time) pada setiap yang datang ke titik i, dilakukan teknik perhitungan mundur (backward) seperti pada PERT-CPM, dengan menggunakan pendekatan aljabar-max-plus.e e e

Teorema 2


5

Diberikan suatu jaringan proyek dengan n titik dan A adalah matriks bobot graph berarah berbobot jaringan tersebut. Vektor LCi diberikan oleh xl = - ((AT)* b l ) di mana bl = [, , , x1l ]T.l Misalkan LCi = xi menyatakan waktu penyelesaian paling akhir untuk semua kegiatan

yang menuju titik i , waktu aktivitas dari titik i ke titik j , jika ( j , i ) A Bij = , jika ( j , i ) A (= ), Dengan asumsi bahwa aktivitas jaringan dimulai pada titik i=1 pada waktu sama dengan nol, yaitu yn = xn, sehingga persamaan dapat ditulis: x n , jika i = n xil = min ( B + x l ) , jika i < 1 ij j 1 j n Dengan menggunakan notasi pada aljabar Max-Plus dapat dituliskan x n , jika i = n xil = l max ( Bij x j ) , jika i < 1 1 j n Dalam hal ini B=AT , dengan A adalah matriks bobot graph berarah.e Misalkan z = [z1, z2, ,zn]T = -xl = [ x1 , x 2 ,..., x n ]T dan bl = [, , , x1 ]Tl l l

Didapatkan z = AT z b l Sehingga dihasilkan z = (AT )* b l Dengan demikian maka xl = -z b. Waktu Mengambang Setelah menghitung waktu awal paling lambat (latest start/LS) dan waktu penyelesaian paling cepat (earliest completion/EC), langkah berikutnya adalah mencari lintasan kritis jaringan. Untuk mengetahui lintasan kritis pada suatu jaringan proyek, maka harus dihitung waktu mengambang pada jaringan tersebut, yaitu waktu mengambang total (total float) dan waktu mengambang bebas (free float) untuk setiap aktifitas (i, j) dalam jaringan. Definisi 3


6

Suatu aktifitas (i, j) A dalam jaringan proyek S disebut aktifitas kritis jika TSij = 0. Suatu lintasan dalam jaringan proyek S disebut lintasan kritis jika semua aktifitas yang menyusunnya merupakan aktifitas kritis. Misalkan diberikan waktu awal paling lambat (latest start/LS) dan waktu penyelesaian paling cepat (earliest completion/EC) untuk setiap aktifitas (i, j) dalam jaringan dengan persamaan: LSij = LCj - Aij dan ECij = ESi + Aij maka : Waktu mengambang total (total float) untuk setiap aktivitas (i, j) A adalah: TFij = x lj - xie - Aij. Jika dituliskan dalam bentuk matriks akan diperoleh waktu mengambang total TF = Lj- Ei - A dengan Lj adalah matriks dengan semua kolomnya adalah vektor xl dan Ei adalah matriks dengan semua barisnya adalah vektor baris (xe)T. Waktu mengambang bebas (free float) untuk setiap aktivitas (i, j) A adalah: FFij = x e - xie - Aij. j Jika dituliskan dalam bentuk matriks akan diperoleh waktu mengambang total FF= Lj- Ei - A dengan Lj adalah matriks dengan semua kolomnya adalah vektor xe dan Ei adalah matriks dengan semua barisnya adalah vektor baris (xe)T 6. Penyelesaian Masalah Jaringan Proyek Pada bagian ini akan dibahas penyelesaian masalah jaringan proyek menggunakan PERT-CPM dengan pendekatan Aljabar Max Plus, untuk penyelesainnya akan digunakan alat Bantu software Toolbox Maxplus Scilab 5.03. Sebagai contoh, misalkan diberikan rangkaian kegiatan suatu proyek sebagai berikut: Tabel 1. Tabel Aktivitas proyek No 1 2 3 4 5 6 Aktivitas A B C D E F Aktivitas yang mendahului B A A E Waktu (hari) 3 2 2 3 2 7


7

7 8 9 10

G H I J

C,D C,D F,G E

3 2 6 5

Berdasarkan Tabel 1, aktivitas (kegiatan) tersebut dapat digambarkan model graphnya sebagai berikut: 2 A 1 2 B C 2 E 2 5 F 3 D Dummy G 3 3 4 7 6 5 J I 2 H 6 7

3

Gambar 1. Graph awal Dari graph tersebut kemudian didapatkan matriks bobot sebagai berikut:

A=

2323 2037256

Selanjutnya dapat dihitung waktu awal paling cepat/ES (earliest start time) dengan persamaan: x e = A* b e = (E A A n 1 ) b e dimana be = [0, , , , , , ]T A* yang merupakan bobot maksimum lintasan dari titik 1 ke titik 7. Untuk menghitung xe dengan Toolbox Maxplus Scilab 5.03 dilakukan langkah-langkah sebagai berikut: 1. Inisialisasi nilai , matriks bobot A, dan nilai be-->e=-%inf;


8

-->A=[e e e e e e e;2 e e e e e e;3 e e e e e e;e 2 3 e e e e;e e 2 0 e e e;e e e 3 7 e e;e e e 2 5 6 e]; -->b=[0 e e e e e e]';

2. Menghitung matriks A*-->As=maxplusstar(A) As = 0. 2. 3. 6. 6. 13. 19. -Inf 0. -Inf 2. 2. 9. 15. -Inf -Inf 0. 3. 3. 10. 16. -Inf -Inf -Inf 0. 0. 7. 13. -Inf -Inf -Inf -Inf 0. 7. 13. -Inf -Inf -Inf -Inf -Inf 0. 6. -Inf -Inf -Inf -Inf -Inf -Inf 0.

3. Mengitung nilai xe-->Xe=maxplusotimes(As,b) Xe = 0. 2. 3. 6. 6. 13. 19.

Berikutnya akan dihitung waktu penyelesaian paling akhir LC (latest completion time) dengan persamaan : xl = - ((AT)* b l ) di mana bl = [, , , , , , ,-19]T. dan dilakukan langkah-langkah sebagai berikut: 1. Inisialisasi matriks bobot AT, dan nilai bl-->AT=A'; -->bl=[e e e e e e -19]';

2. Menghitung matriks AT*-->ATs=maxplusstar(AT) ATs = 0. -Inf -Inf -Inf -Inf -Inf -Inf 2. 0. -Inf -Inf -Inf -Inf -Inf 3. -Inf 0. -Inf -Inf -Inf -Inf 6. 2. 3. 0. -Inf -Inf -Inf 6. 2. 3. 0. 0. -Inf -Inf 13. 9. 10. 7. 7. 0. -Inf 19. 15. 16. 13. 13. 6. 0.

3. Mengitung nilai xl

-->xl=-maxplusotimes(ATs,bl) xl =


9

0. 4. 3. 6. 6. 13. 19.

Berdasarkan nilai xe dan xl selanjutnya akan dihitung waktu mengambang total (TF) dan waktu mengambang bebas (FF) sebagaimana disajikan dalam tabel berikut: Tabel 2. Tabel Aktivitas Kritis i 1 1 2 3 3 4 4 4 5 5 6 j 2 3 4 4 5 5 6 7 6 7 7 Aji 2 3 2 3 2 0 3 2 7 5 6 ESi 0 0 2 3 3 6 6 6 6 6 13 ECij 2 3 4 6 5 6 9 8 13 11 19 LSij 2 0 4 3 4 6 10 17 6 14 13 LCj 4 3 6 6 6 6 13 19 13 19 19 TFij 2 0 2 0 1 0 4 11 0 8 0 FFij 0 0 2 0 1 0 4 11 0 8 0 Aktivitas Kritis * * * * *

Dari Tabel 2. aktivitas kritis dapat diperoleh lintasan kritis yaitu: (1, 3), (3, 4), (4, 5), (5, 6), (6, 7), sehingga jika digambarkan dalam bentuk graphnya adalah: 2 A 1 2 B C 2 E 2 5 F 3 D Dummy G 3 3 4 7 6 5 J I 2 H 6 7

3

Gambar 2. Graph lintasan kritis


10

Dari hasil perhitungan secara iteratif dengan pendekatan Aljabar Max-Plus menggunakan ToolBox Maxplus Scilab 5.03 jika dibandingkan dengan hasil perhitungan Linear Programming menggunakan program Aplikasi Quantitative Methods (QM) 2.0 dihasilkan hasil yang sama. Hal ini dapat kita lihat pada Gambar 3 dan Gambar 4. Gambar 3. Aktivitas jaringan

Gambar 3. Hasil perhitungan lintasan kritis


11

Kesimpulan 1. Pendekatan Aljabar Max Plus dapat digunakan dalam penyelesaian analisis jaringan proyek PERT CPM dengan modifikasi sistem persamaan linier dengan operasi matriks. 2. Untuk menentukan waktu awal paling cepat (earlies start time) dan waktu penyelesaian paling akhir (latest completion time), dilakukan dengan modifikasi perhitungan maju/forward dan mundur/backward dengan suatu matriks bobot yang dilakukan secara iteratif. 3. Penentuan lintasan kritis dilakukan dengan menghitung waktu mengambang total (Total Float ) dan waktu mengambang bebas (Free Float) yang sama dengan nol. Saran dan Pembahasan Lebih Lanjut: Pembahasan pada makalah ini hanya pada certain time (single time) sehingga metode yang dipakai cukup dengan CPM, sedangkan jika dengan menggunakan uncertain time (triple times) yaitu yaitu optimistic time, most likely time dan pessimistic time digunakan PERT. Untuk itu perlu digunakan perubahan expected time dengan menggunakan persamaan: te = to + 4 tm + t p 6 tO tm tp : Optimistic/Shortest time : Most Likely/Best Estimate time : Pessimistic/Longest time

dimana :


12

Standar Deviasi dari expected time untuk setiap aktivitas

=

t P to 6

Standar Deviasi dari expected time untuk suatu path adalah

path = 2


13

aplikasi aljabar max

Documents