Po Model Jaringan

of 37 /37
1 Penelitian Operasional Penelitian Operasional “Laporan Model Jaringan” Tugas Kelompok Tugas Ke-1 Untuk memenuhi tugas Penelitian Operasional Di Jurusan Teknik Informatika Disusun oleh : 0606086 Adry Muhamad 0606005 Randy Agithia 0606024 Irfan H Alawi 0605008 Willy Prima S.N Universitas Widyatama |

Embed Size (px)

Transcript of Po Model Jaringan

Page 1: Po Model Jaringan

1 Penelitian Operasional

Penelitian Operasional

“Laporan Model Jaringan”

Tugas Kelompok Tugas Ke-1

Untuk memenuhi tugas Penelitian Operasional

Di Jurusan Teknik Informatika

Disusun oleh :

0606086 Adry Muhamad0606005 Randy Agithia0606024 Irfan H Alawi0605008 Willy Prima S.N

Jurusan Teknik Informatika - Universitas WidyatamaBandung

2009

Universitas Widyatama |

Page 2: Po Model Jaringan

2 Penelitian Operasional

Universitas Widyatama |

Page 3: Po Model Jaringan

3 Penelitian Operasional

Analisa Jaringan Kerja

Pengelolaan proyek-proyek berskala besar yang berhasil memerlukan

perencanaan, penjadwalan, dan pengordinasian yang hati-hati dari berbagai aktivitas yang

saling berkaitan. Untuk itu kemudian dikembangkan prosedur-prosedur formal yang

didasarkan atas penggunaan jaringan kerja (network) dan teknik-teknik network.

Analisa jaringan kerja merupakan suatu perpaduan pemikiran yang logis,

digambarkan dengan suatu jaringan yang berisi lintasan-lintasan kegiatan dan

memungkinkan pengolahan secara analitis. Analisa jaringan kerja memungkinkan suatu

perencanaan yang efektif dari suatu rangkaian yang mempunyai interaktivitas.

Keuntungan dari penggunaan analisa jaringan kerja adalah:

1. Dapat merencanakan suatu proyek secara keseluruhan.

2. Penjadwalan pekerjaan dalam urutan yang praktis dan efisien.

3. Pengadaan pengawasan dan pembagian kerja maupun biaya.

4. Penjadwalan ulang untuk mengatasi hambatan dan keterlambatan.

5. Menentukan kemungkinan pertukaran antara waktu dan biaya.

Salah satu prosedur yang telah dikembangkan berdasarkan jaringan kerja untuk

mengatasi permasalahan pengelolaan suatu proyek adalah PERT (Program Evaluation

and Review Technique) dan CPM (Critical Path Method), yang sebenarnya di antara

keduanya terdapat perbedaan penting, yaitu:

1. CPM menggunakan satu jenis waktu untuk taksiran waktu kegiatan sedangkan

PERT menggunakan tiga jenis waktu, yaitu: prakiraan waktu teroptimis,

termungkin, dan terpesimis.

2. CPM digunakan kala taksiran waktu pengerjaan setiap aktivitas diketahui dengan

jelas dimana deviasi relatif kecil atau dapat diabaikan sedangkan PERT digunakan

saat taksiran waktu aktivitas tidak dapat dipastikan seperti aktivitas tersebut

belum pernah dilakukan atau bervariasi waktu yang besar.

Universitas Widyatama |

Page 4: Po Model Jaringan

4 Penelitian Operasional

3. CPM digunakan untuk memperkiraan waktu kegiatan suatu proyek dengan

pendekatan deterministik, sementara PERT direkayasa untuk menghadapi situasi

dengan kadar ketidakpastian yang tinggi pada aspek kurun waktu kegiatan..

Meskipun terdapat perbedaan-perbedaan seperti di atas, namun kecenderungan

dewasa ini adalah menggabungkan kedua pendekatan tersebut menjadi PERT-type

system.

PERT-type system dirancang untuk membantu dalam perencanaan dan

pengendalian, sehingga tidak langsung terlibat dalam dalam optimasi. Tujuan sistem ini

adalah:

1. Untuk menentukan probabilitas kemungkinan tercapainya batas waktu proyek.

2. Untuk menetapkan kegiatan mana (dari suatu proyek) yang merupakan

bottlenecks (menentukan waktu penyelesaian seluruh proyek) sehingga dapat

diketahui pada kegiatan mana kita harus bekerja keras agar jadwal terpenuhi.

3. Untuk mengevaluasi akibat dari perubahan-perubahan program.

4. Untuk mengevaluasi akibat dari terjadinya penyimpangan pada jadwal proyek.

Simbol-simbol yang digunakan

Dalam menggambarkan suatu jaringan kerja digunakan tiga buah simbol sebagai

berikut:

1. Anak panah (arrow), menyatakan sebuah kegiatan atau aktivitas. Kegiatan di sini

didefinisikan sebagai hal yang memerlukan jangka waktu tertentu dalam

pemakaian sejumlah sumber daya (sumber tenaga, peralatan, material, biaya)

2. Lingkaran kecil (node), menyatakan sebuah kejadian atau peristiwa atau event.

Kejadian didefinisikan sebagai ujung atau pertemuan dari satu atau beberapa

kegiatan.

3. Anak panah terputus-putus, menyatakan kegiatan semu atau dummy . Dummy

tidak mempunyai jangka waktu tertentu, karena tidak memakai sejumlah sumber

daya.

Universitas Widyatama |

Page 5: Po Model Jaringan

5 Penelitian Operasional

Penggunaan simbol-simbol ini mengikuti aturan-aturan sebagai berikut:

1. Di antara dua event yang sama, hanya boleh digambarkan satu anak panah.

2. Nama suatu aktivitas dinyatakan dengan huruf atau nomor urut event.

3. Aktivitas harus mengalir dari event bernomor rendah ke event bernomor tinggi.

4. Diagram hanya memiliki sebuah initial evet dan sebuah terminal event.

Jalur Terpendek ( SHORTEST PATH )

Andaikan diberikan sebuah graph G dalam tiap garis (x,y) dihubungkan dengan titik a

x,y) mewakili panjang dari garis. Dalam beberapa hal, panjang sebenarnya mewakili

biaya atau beberapa nilai lainnya. Panjang dari lintasan adalah menentukan panjang

jumlah dari masing-masing garis yang terdiri dari lintasan. Untuk 2 verteks s dan t dalam

G, ada beberapa lintasan dari s ke t . Masalah lintasan terpendek meliputi pencarian

lintasan dari s ke t yang mempunyai lintasan terpendek dan biaya termurah.

a. Defnisi Jalur Terpendek

Jalur terpendek (Shortest Path) antara dua verteks dari s ke t dalam jaringan adalah

lintasan graph berarah sederhana dari s ke t dengan sifat dimana tidak ada lintasan lain

yang memiliki nilai terendah. Pada persoalan ini akan terdorong untuk menyelesaikan

suatu persoalan untuk menentukan jalur terpendek dan biaya termurah dalam suatu

jaringan dengan mengimplementasikannya ke dalam kasus travelling salesman problem

yang merupakan salah satu persoalan dalam Jaringan Syaraf Tiruan.

Setiap path dalam digraph mempunyai nilai yang dihubungkan dengan nilai path

tersebut, yang nilainya adalah jumlah dari nilai edge path tersebut. Dari ukuran dasar ini

dapat dirumuskan masalah seperti “ mencari lintasan terpendek antara dua vertek dan

meminimumkan biaya”.

Banyak bidang penerapan mensyaratkan untuk menentukan lintasan terpendek berarah

dari asal ke tujuan di dalam suatu distribusi aliran berarah. Algoritma yang diberikan

dapat dimodifikasi dengan mudah untuk menghadapi lintasan berarah pada setiap

Universitas Widyatama |

Page 6: Po Model Jaringan

6 Penelitian Operasional

iterasinya. Suatu versi yang lebih umum dari masalah lintasan terpendek adalah

menentukan lintasan terpendek dari sembarang verteks menuju ke setiap verteks lainnya.

Pilihan lain adalah membuang kendala tak negatif bagi “jarak”. Suatu kendala lain dapat

juga diberlakukan dalam suatu masalah lintasan terpendek.

Definisi 1.1. Lintasan terpendek antara dua verteks dari s ke t dalam jaringan adalah

lintasan graph berarah sederhana dari s ke t dengan sifat dimana tidak ada lintasan lain

yang memiliki nilai terendah.

Contoh 1.

Gambar 1.1. Shortest path (garis tebal)

Pada gambar 2.7. dapat dilihat bahwa setiap edge terletak pada path-path dari titik 1 ke

titik 5. Edge merepresentasikan saluran dengan kapasitas tertentu (contohnya, air) dapat

dialirkan melalui saluran. Sedangkan verteks merepresentasikan persimpangan saluran.

Air mengalir melalui verteks pada vertex yang dilalui Lintasan terpendek dari verteks

pada graph di atas adalah P = {1 – 4, 4 – 5} dengan kapasitas 4.

Universitas Widyatama |

1

5

3

4

2

2 X1

5X5

1 X6

3X3

2

13

3

X5

X7

X2

X4

Page 7: Po Model Jaringan

7 Penelitian Operasional

Algoritma Lintasan-Terpendek

Dalam graf berbobot, kita sering kali ingin mencari sebuah lintasan terpendek (yakni,

sebuah lintasan yang mempunyai panjang minimum) antara dua verteks yang diketahui.

Untuk graf berbobot tersambung, teknik pencarian lintasan terpendek diberikan oleh

Algoritma Dijkstra. Algoritma Dijkstra melibatkan pemasangan label pada verteks. Kita

misalkan L(v) menyatakan label dari verteks v. Pada setiap pembahasan, beberapa

verteks mempunyai label sementara dan yang lain mempunyai label tetap. Kita misalkan

T menyatakan himpunan verteks yang mempunyai label sementara. Dalam

menggambarkan algoritma tersebut, kita akan melingkari verteks-verteks yang

mempunyai label tetap. Selanjutnya akan kita tunjukkan bahwa jika L(v) adalah label

tetap dari verteks v, maka L(v) merupakan panjang lintasan terpendek dari a ke v.

Sebelumnya semua verteks mempunyai label sementara. Setiap iterasi dari algoritma

tersebut mengubah status satu label dari sementara ke tetap; sehingga kita dapat

mengakhiri algoritma tersebut jika z menerima sebuah label tetap. Pada bagian ini L(z)

merupakan panjang lintasan terpendek dari a ke z.

Universitas Widyatama |

Page 8: Po Model Jaringan

8 Penelitian Operasional

Algoritma 10.1 : Algoritma DijkstraAlgoritma ini mencari panjang lintasan terpendek dari verteks a ke z dalam sebuah graf berbobot tersambung. Bobot dari rusuk (i,j) adalah w(i,j)>0 dan label verteks x adalah L(x). Hasilnya, L(z) merupakan panjang lintasan terpendek dari a ke z.

Masukan : Sebuah graf berbobot tersambung dengan bobot positif. Verteks a sampai z.Keluaran : L(z), panjang lintasan terpendek dari a ke z.

1. procedure dijkstra (w,a,z,L)2. L(a) := 03. for semua verteks x a do4. L(x) := 5. T := himpunan semua verteks6. // T adalah himpunan verteks yang panjang terpendeknya dari a belum ditemukan7. while z T do8. begin9. pilih v T dengan minimum L(v)10. T:=T-{v}11. for setiap x T di samping v do12. L(x):=min{L(x), L(v)+w(v,x)}13. end14. end dijkstra

Contoh 10.2 :Carilah panjang lintasan terpendek dari verteks a ke z dalam graf berbobot tersambung berikut.

Gambar 10.2

Universitas Widyatama |

a

b c

d e

f g

z

2

1

2

3

4

2

4

5

3

7

1

6

Page 9: Po Model Jaringan

9 Penelitian Operasional

Penyelesaian :

Kita akan menerapkan Algoritma Dijkstra. Hasil pelaksanaan baris 2-4 dari Algoritma

10.1 adalah L(a) = 0, L(b) = L(c) = L(d) = L(e) = L(f) = L(g) = L(z) = . Pada baris 7, z

tidak dilingkari. Kita lanjutkan ke baris 9, di mana kita memilih verteks a, verteks tak

dilingkari dengan label terkecil, dan melingkarinya. Pada baris 11 dan 12 kita perbarui

setiap verteks tak terlinkari, b dan f, yang berdekatan dengan a. Kita dapatlkan label-label

baru

L(b) = min{ , 0+2} = 2, L(f) = min{ , 0+1} = 1.

Sampai pada bagian ini, kita kembali ke baris 7.

Karena z tak dilingkari, kita lanjutkan ke baris 9, di mana kita memilih verteks f, verteks

tak dilingkari dengan label terkecil, dan melingkarinya. Pada baris 12 dan 13 kita

perbarui setiap label dari verteks tak dilingkari, d dan g, yang berdekatan dengan f. Kita

dapatkan label-label baru

L(d) = min{ , 1+3} = 4, L(f) = min{ , 1+5} = 6.

Sampai pada bagian ini, kita kembali ke baris 7. Demikian seterusnya dan pada akhir

algoritma, z dilabeli 5, menyatakan panjang lintasan terpendek dari a ke z adalah 5.

Sebuah lintasan terpendek diberikan oleh (a,b,c,z).

Universitas Widyatama |

Page 10: Po Model Jaringan

10 Penelitian Operasional

MINIMAL SPANNING TREE

Pohon rentang minimum (minimal spanning tree) adalah teknik mencari jalan

penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan

sampai diperoleh jarak minimum.

Masalah pohon rentang minimum serupa dengan masalah rute terpendek (shortest route),

kecuali bahwa tujuannya adalah untuk menghubungkan seluruh simpul dalam jaringan

sehingga total panjang cabang tersebut diminimisasi. Jaringan yang dihasilkan

merentangkan (menghubungkan) semua titikdalam jaringan tersebut pada total jarak

(panjang) minimum.

Langkah-langkah dari pohon rentang minimum adalah :

1. pilih secara arbitrer sebuah node dalam jaringan

2. hubungkan node tersebut dengan node terdekat yang dapat meminimalkan total

jarak

3. perhatikan semua node apakah terdapat node yang belum terhubung, temukan dan hubungkan node terdekat yang belum terhubung

4. ulangi langkah ketiga sampai seluruh node dapat terhubung

Sebagai contoh, gedung Istec Corporation yang baru memiliki beberapa ruangan dan

tiap ruangan membutuhkan 1 lubang aliran listrik (atau biasa disebut sebagai steker).

Teknisi listrik akan menyalurkan listrik dari ruang bagian depan sampai keseluruh

ruangan dengan total panjang kabel yang seefisien mungkin. Adapun jarak antar ruangan

dapat digambarkan dalam gambar jaringan berikut ini, sedangkan ruang bagian depan

digambarkan sebagai node-1.

Universitas Widyatama |

Page 11: Po Model Jaringan

11 Penelitian Operasional

Karena node-1 adalah ruangan terdepan yang menjadi sumber aliran listrik utama, maka

node-1 akan dijadikan sebagai patokan dalam jaringan. Node yang paling dekat dengan

node-1 adalah node dengan jarak 2 meter, sehingga kita hubungkan node 1 dengan node-

3.

Kemudian kita lihat node-node terdekat yang belum terhubung dengan node 1 dan 3,

yaitu node 7, 6 dan 2. Yang terdekat dengan node 3 adalah node 7 dengan jarak 3 meter.

Kemudian node 3 dan node 7 dapat dihubungkan.

Universitas Widyatama |

Page 12: Po Model Jaringan

12 Penelitian Operasional

Node yang belum terhubung terdekat dengan node 1, 3 dan 7 adalah node 6 dengan

panjang 2 meter.

Node yang belum terhubung dan dekat dengan node 1,3,7 dan 6 adalah 5 dan 2. Node 5

dapat terhubung dengan node 6 dengan jarak 3 meter, sedangkan node 3 dapat

dihubungkan dengan node-1 dengan jarak 3 meter.

Sisa node yang belum terhubung adalah node 8, 4 dan 9. Node 4 dapat dihubungkan

Universitas Widyatama |

Page 13: Po Model Jaringan

13 Penelitian Operasional

dengan node 5 dengan jarak 3 meter, dan untuk mencapai node 9 total jarak terdekat lebih

pendek jika ditempuh dari node 8 ke 9 dari pada melalui node 4.

Karena seluruh node telah terhubung atau telah terkait dalam satu jaringan, maka solusi

di atas telah optimum. Jadi teknisi listrik dapat memulai merentangkan kabelnya dengan

menghubungkan node 1 – 2, 1 – 3, 3 – 7, 6 – 7, 5 – 6, 4 – 5, 6 – 8, 8 – 9

Panjang kabel yang dibutuhkan adalah : 21 meter

Universitas Widyatama |

Page 14: Po Model Jaringan

14 Penelitian Operasional

ALGORITMA DIJKSTRA

Pada tahun 1959 sebuah tulisan sepanjang tiga halaman yang berjudul A Note on Two

Problems in Connexion with Graphs diterbitkan pada jurnal Numerische Mathematik.

Pada tulisan ini, Edsger W. Dijkstra – seorang ilmuwan computer berumur dua puluh

sembilan tahun -mengusulkan algoritma-algoritma untuk solusi dari duamasalah teoritis

graf dasar: the minimum weight Algoritma Dijkstra untuk masalah jalan terpendek adalah

satu dari algoritma-algoritma paling ternama pada ilmu komputer dan sebuah algoritma

paling popular pada oparasi pencarian(OR). Implementasi algoritma dijkstra

pada ilmu computer antara lain adalah pada link-state routing protocol, OSPF dan IS-IS.

Pada literatur tersebut, algoritma ini sering digambarkan sebagai sebuah algoritma yang

tamak. Contohnya, buku Algorithmics (Brassard and Bratley [1988, pp. 87-92])mengulas

ini pada bab tersebut dengan judul Greedy Algorithms. Encyclopedia of Operations

Research and Management Science (Gass and Harris [1996, pp. 166-167])

menggambarkan algoritma ini sebagai sebuah "node labelling greedy algorithm " dan

sebuah algoritma yang tamak digambarkan sebagai "a heuristic algorithm that at every

step selects the best choice available at that step without regard to future consequences "

(Gass and Harris [1996, p. 264]).

1.1 Definisi Algoritma Dijkstra

Pada dasarnya, algoritma ini merupakan salah satu bentuk algoritma greedy. Algoritma

ini termasuk algoritma pencarian graf yang digunakan untuk menyelesaikan masalah

lintasan terpendek dengan satu sumber pada sebuah graf yang tidak memiliki cost sisi

negatif, dan menghasilkan sebuah pohon lintasan terpendek. Algoritma ini sering

digunakan pada routing Algoritma dijkstra mencari lintasan terpendek dalam sejumlah

langkah. Algoritma ini menggunakan strategi greedy sebagai berikut :

Untuk setiap simpul sumber(source) dalam graf, algortima ini akan mencari jalur dengna

cost minimum antara simpul tersebut dengan simpul lainnya. Algoritma juga dapat

digunakan untuk mencari total biaya(cost) dari lintasan terpendek yang dibentuk dari

sebuah simpul ke sebuah simpul tujuan. Sebagai contoh, bila simpul pada graf

merepresentasikan kota dan bobot sisi merepresentasikan jarak antara 2 kota yang

Universitas Widyatama |

Page 15: Po Model Jaringan

15 Penelitian Operasional

mengapitnya, maka algoritma dijkstra dapat digunakan untuk mencari rute terpendek

antara sebuah kota dengan kota lainnya.

1.2 Skema Umum Algoritma Dijkstra

Berikut adalah skema umum dari algoritma dijkstra pada pencarian shortest path :

1. Buatlah 3 buah list, yaitu list jarak(list 1), list simpul-simpul sebelumnya(list 2),

dan list simpul yang sudah dikunjungi(list 3), serta sebuah variable yang

menampung simpul saat ini(current vertex).

2. Isi semua nilai dalam list jarak dengan tak hingga, kecuali simpul awal yang diisi

dengan0.

3. Isi semua nilai dalam list 2 dengan false

4. Isi semua nilai dalam list 3 dengan null

5. Current Vertex diisi dengan simpul awal(start).

6. Tandai current vertex sebagai simpul yang telah dikunjungi.

7. Update list 1 dan 2 berdasarkan simpul-simpul yang dapat langsung dicapai dari

current vertex

8. Update current vertex dengan simpul yang paling dekat dengan simpul awal.

9. Ulangi langkah 6 sampai semua simpul sudah dikunjungi.

Universitas Widyatama |

Page 16: Po Model Jaringan

16 Penelitian Operasional

MAXIMUM FLOW PROBLEM

Network Flow

c Jumlah arus yang mengalir pada tiap sisi harus lebih kecil atau sama dengan kapasitas

sisi tersebut.Pada aplikasinya, sebuah graf berarah sering disebut dengan network. Setiap

arus(flow) yang ada dalam network, harus memenuhi sebuah batasan yaitu arus yang

masuk pada suatu simpul harus sama dengan arus yang keluar pada simpul tersebut,

kecuali pada source, yang

arus keluarnya lebih besar dari arus masuk, dan sink, yang arus masuknya lebih besar dari

arus keluar.

Sebuah network biasanya digunakan untuk memodelkan sistem lalulintas, saluran pipa,

sirkuit elektrik, dsb.

PENYELESAIAN MAXIMUM FLOW PROBLEM DENGAN ALGORITMA DIJKSTRA

Langkah PenyelesaianUntuk menyelesaikan Maximum Flow Problem dengan algoritma Dijkstra, maka kita

harus melakukan sedikit modifikasi dari algoritma ini. Secara garis besar, skema dari

algoritma yang akan dijelaskan adalah sebagai berikut:

1. Cari sebuah lintasan yang belum dipilih yang menghubungkan simpul awal

dengan simpul

1. tujuan.

2. Pada lintasan yang dipilih, carilah sebuah sisi dengan kapasitas sisa minimum.

3. Kapasitas sisa minimum didapat dari kapasitas sisi tersebut dikurangi arus yang

sudah mengalir pada sisi itu(c -f). Bila kapasitas minimum sisa sama dengan 0,

langsung ke langkah 4.

4. Alirkan arus sejumlah kapasitas minimum sisa pada lintasan yang dipilih.

5. Kembali ke langkah 1 sampai semua lintasan diperiksa. Contoh implementasinya

adalah sebagai berikut :

Universitas Widyatama |

Page 17: Po Model Jaringan

17 Penelitian Operasional

Dalam network gambar 2 bisa kita lihat terdapat 5 lintasan yang menghubungkan simpul

awal (S) dan simpul tujuan (F).

Langkah 1 : Pilih lintasan S-A-D-F. Pada lintasan ini nilai kapasitas minimum sisanya

adalah 2. Alirkan arus sejumlah 2 satuan.

Langkah 2 :

Pilih lintasan S-B-D-F. nilai kapasitas sisa minimum pada lintasan ini adalah 2. Alirkan arus sebanyak 2

satuan.

Universitas Widyatama |

Page 18: Po Model Jaringan

18 Penelitian Operasional

Langkah 3 :

pilih lintasan S-B-E-F. lintasan ini sudah tidak dapat dialiri arus lagi karena nilai

kapasitasa sisa minimumnya 0.

Langkah 4 :

pilih lintasan S-C-B-E-F. Nilai kapasitas sisa minimum pada lintasan ini adalah 1.

Alirkan arus sebanyak 1 satuan.

Langkah 5 :

Universitas Widyatama |

Page 19: Po Model Jaringan

19 Penelitian Operasional

pilih lintasan terakhir yaitu S-C-F. Nilai kapasitas sisa minimum lintasan ini adalah 2.

Gambar 6 merupakan solusi dari masalah maximumflow pada network pada gambar 2.

Dari gambar 6 ini dapat dilihat bahwa jumlah arus maksimum yang dapat mengalir dari

network tersebut adalah 7, yaitu jumlah arus yang meninggalkan simpul awal atau jumlah

arus yang masuk ke simpul tujuan.

3.2 Analisis

Algoritma dijkstra yang digunakan di atas, atau terkadang disebut Priority First

Search(PFS), mampu memberikan solusi optimal untuk kebanyakan kasus, dalam hal ini

Maximum Flow Problem. Akan tetapi, sama halnya seperti algoritma greedy pada

umumnya, terdapat beberapa kasus dimana algoritma dijkstra tidak memberikan solusi

maksimum. Hal ini biasanya merupakan akibat dari pemilihan

urutan lintasan yang kurang tepat. Karena itu, pemilihan urutan lintasan akan sangat

menentukan solusi dari permasalahan ini. Sama seperti algoritma greedy, kita dapat menentukan

fungsi prioritas untuk menentukan urutan lintasan yang akan diproses. Biasanya, prioritas

utama dalam maximum flow problem ini adalah lintasan yang memiliki kapasitas

tertinggi. Akan tetapi, dengan fungsi prioritas ini –pun masih ada kasus yang tidak

memberikan hasil optimal, misalnya :

Universitas Widyatama |

Page 20: Po Model Jaringan

20 Penelitian Operasional

Solusi yang terdapat pada gambar 8 merupakan solusi Maximum Flow Problem dengan

menggunakan algoritma Ford – Fulkerson, algoritma yang paling sering digunakan untuk

menyelesaikan masalah maksimum flow. Algoritma ini ternyata memang lebih baik

daripada algoritma dijkstra dalam mencari solusi optimal pada maximum flow problem

karena algoritma ini memang dirancang untuk menyelesaikan masalah ini, tidak seperti

algoritma dijkstra yang dirancang untuk menyelesaikan masalah shortest

path secara global.

Universitas Widyatama |

Page 21: Po Model Jaringan

21 Penelitian Operasional

PENGERTIAN PERT DAN CPM

PERT merupakan singkatan dari Program Evaluation and Review Technique (teknik

menilai dan meninjau kembali program), sedangkan CPM adalah singkatan dari Critical

Path Method (metode jalur kritis) dimana keduanya merupakan suatu teknik manajemen.

Teknik PERT adalah suatu metode yang bertujuan untuk sebanyak mungkin mengurangi

adanya penundaan, maupun gangguan produksi, serta mengkoordinasikan berbagai

bagian suatu pekerjaan secara menyeluruh dan mempercepat selesainya proyek. Teknik

ini memungkinkan dihasilkannya suatu pekerjaan yang terkendali dan teratur, karena

jadwal dan anggaran dari suatu pekerjaan telah ditentukan terlebih dahulu sebelum

dilaksanakan.

Tujuan dari PERT adalah pencapaian suatu taraf tertentu dimana waktu merupakan dasar

penting dari PERT dalam penyelesaian kegiatan-kegiatan bagi suatu proyek. Dalam

metode PERT dan CPM masalah utama yaitu teknik untuk menentukan jadwal kegiatan

beserta anggaran biayanya dengan maksud pekerjaan-pekerjaan yang telah dijadwalkan

itu dapat diselesaikan secara tepat waktu serta tepat biaya.

CPM adalah suatu metode perencanaan dan pengendalian proyek-proyek yang

merupakan sistem yang paling banyak digunakan diantara semua sistem yang memakai

prinsip pembentukan jaringan. Dengan CPM, jumlah waktu yang dibutuhkan untuk

menyelesaikan berbagai tahap suatu proyek dianggap diketahui dengan pasti, demikian

pula hubungan antara sumber yang digunakan dan waktu yang diperlukan untuk

menyelesaikan proyek. Jadi CPM merupakan analisa jaringan kerja yang berusaha

mengoptimalkan biaya total proyek melalui pengurangan waktu penyelesaian total

proyek yang bersangkutan.

Teknik penyusunan jaringan kerja yang terdapat pada CPM, sama dengan yang

digunakan pada PERT. Perbedaan yang terlihat adalah bahwa PERT menggunakan

activity oriented, sedangkan dalam CPM menggunakan event oriented. Pada activity

oriented anak-panah menunjukkan activity atau pekerjaan dengan beberapa keterangan

aktivitasnya, sedang event oriented pada peristiwalah yang merupakan pokok perhatian

Universitas Widyatama |

Page 22: Po Model Jaringan

22 Penelitian Operasional

dari suatu aktivitas. Pengertian PERT dan CPM seperti yang dikemukakan oleh para ahli

dikutipkan seperti berikut :

“Teknik PERT adalah suatu metode yang bertujuan untuk sebanyak mungkin mengurangi

adanya penundaan maupun konflik dan gangguan produksi, serta mengkoordinasikan dan

mengsingkronisasikan berbagai bagian dari keseluruhan pekerjaan dan mempercepat

selesainya proyek. Sedangkan CPM adalah suatu teknik perencanaan dan pengendalian

yang dipergunakan dalam proyek berdasarkan pada data biaya dari masa lampau (past

cost data)”.

T. Hari Handoko (1993 hal. : 401) mengemukakan bahwa : “PERT adalah suatu metode

analisis yang dirancang untuk membantu dalam penjadwalan dan pengendalian proyek-

proyek yang kompleks, yang menuntut bahwa masalah utama yang dibahas yaitu masalah

teknik untuk menentukan jadwal kegiatan beserta anggaran biayanya sehingga dapat

diselesaikan secara tepat waktu dan biaya, sedangkan CPM adalah suatu metode yang

dirancang untuk mengoptimalkan biaya proyek dimana dapat ditentukan kapan

pertukaran biaya dan waktu harus dilakukan untuk memenuhi jadwal penyelesaian

proyek dengan biaya seminimal mungkin”

Perbedaan PERT dan CPM

Pada prinsipnya yang menyangkut perbedaan PERT dan CPM adalah sebagai berikut :

a. PERT digunakan pada perencanaan dan pengendalian proyek yang belum pernah

dikerjakan, sedangkan CPM digunakan untuk menjadwalkan dan mengendalikan

aktivitas yang sudah pernah dikerjakan sehingga data, waktu dan biaya setiap unsur

kegiatan telah diketahui oleh evaluator.

b. Pada PERT digunakan tiga jenis waktu pengerjaan yaitu yang tercepat, terlama serta

terlayak, sedangkan pada CPM hanya memiliki satu jenis informasi waktu pengerjaan

yaitu waktu yang paling tepat dan layak untuk menyelesaikan suatu proyek.

c. Pada PERT yang ditekankan tepat waktu, sebab dengan penyingkatan waktu maka

biaya proyek turut mengecil, sedangkan pada CPM menekankan tepat biaya.

Universitas Widyatama |

Page 23: Po Model Jaringan

23 Penelitian Operasional

d. Dalam PERT anak panah menunjukkan tata urutan (hubungan presidentil), sedangkan

pada CPM tanda panah adalah kegiatan.

PENJADWALAN PROYEK PERANGKAT LUNAK

Penjadwalan proyek meliputi kegiatan menetapkan jangka waktu kegiatan proyek

yang harus diselesaikan, bahan baku, tenaga kerja serta waktu yang dibutuhkan oleh

setiap aktivitas. Pendekatan yang lazim digunakan adalah digram Gantt Chart, PERT

(Project Evaluation and Review Technique), dan CPM (Critical Path Method).

Penjadwalan dibutuhkan untuk membantu:

Menunjukkan hubungan tiap kegiatan lainnya dan terhadap keseluruhan proyek.

Mengidentifikasikan hubungan yang harus didahulukan di antara kegiatan.

Menunjukkan perkiraan biaya dan waktu yang realistis untuk tiap kegiatan.

Membantu penggunaan tenaga kerja, uang dan sumber daya lainnya dengan cara

hal-hal kritis pada proyek

Faktor-faktor yang harus dipertimbangkan dalam membuat jadwal pelaksanaan

proyek :

1. kebutuhan dan fungsi proyek tersebut. Dengan selesainya proyek itu proyek

diharapkan dapat dimanfaatkan sesuai dengan waktu yang sudah ditentukan.

2. keterkaitannya dengan proyek berikutnya ataupun kelanjutan dari proyek

selanjutnya.

3. alasan social politis lainnya, apabila proyek tersebut milik pemerintah.

4. kondisi alam dan lokasi proyek.

5. keterjangkauan lokasi proyek ditinjau dari fasilitas perhubungannya.

6. ketersediaan dan keterkaitan sumber daya material, peralatan, dan material

pelengkap lainnya yang menunjang terwujudnya proyek tersebut.

7. kapasitas atau daya tampung area kerja proyek terhadap sumber daya yang

dipergunakan selama operasional pelaksanaan berlangsung.

Universitas Widyatama |

Page 24: Po Model Jaringan

24 Penelitian Operasional

8. produktivitas sumber daya, peralatan proyek dan tenaga kerja proyek, selama

operasional berlangsung dengan referensi dan perhitungan yang memenuhi aturan

teknis.

9. cuaca, musim dan gejala alam lainnya.

10. referensi hari kerja efektif.

Gantt Chart

Gantt chart adalah suatu alat yang bernilai khususnya untuk proyek-proyek

dengan jumlah anggota tim yang sedikit, proyek mendekati penyelesaian dan beberapa

kendala proyek.

1. Gantt chart secara luas dikenal sebagai alat fundamental dan mudah diterapkan

oleh para manajer proyek untuk memungkinkan seseorang melihat dengan mudah

waktu dimulai dan selesainya tugas-tugas dan sub- sub tugas dari proyek.

2. Semakin banyak tugas-tugas dalam proyek dan semkin penting urutan antara

tugas-tugas maka semakin besar kecenderungan dan keinginan untuk

memodifikasi gantt chart.

3. Gantt chart membantu menjawab pertanyaan-pertanyaan “what if” saat melihat

kesempatan-kesempatan untuk membuat perubahan terlebih dahulu terhadap

kebutuhan.

Keuntungan menggunakan Gantt chart :

Sederhana, mudah dibuat dan dipahami, sehingga sangat bermanfaat sebagai alat

komunikasi dalam penyelenggaraan proyek.

Dapat menggambarkan jadwal suatu kegiatan dan kenyataan kemajuan

sesungguhnya pada saat pelaporan

Bila digabungkan dengan metoda lain dapat dipakai pada saat pelaporan

Kelemahan Gantt Chart :

Tidak menunjukkan secara spesifik hubungan ketergantungan antara satu kegiatan

dan kegiatan yang lain, sehingga sulit untuk mengetahui dampak yang

diakibatkan oleh keterlambatan satu kegiatan terhadap jadwal keseluruhan

proyek.

Universitas Widyatama |

Page 25: Po Model Jaringan

25 Penelitian Operasional

Sulit mengadakan penyesuaian atau perbaikan/pembaharuan bila diperlukan,

karena pada umumnya ini berarti membuat bagan balok baru.

Berikut ini adalah bentuk sederhana dari PERT :

a. 1 jalur kritis, 2 orang dalam 1 tim proyek

b. 3 jalur kritis, 3 orang dalam 1 tim proyek

c. 10 jalur kritis, 5 orang dalam 1 tim proyek

Contoh Kasus:

Diketahui aktivitas sebuah proyek sebagi berikut:

Dari kasus tersebut diselesaikan dengan menggunakan POM for Windows

Universitas Widyatama |

Page 26: Po Model Jaringan

26 Penelitian Operasional

Dari table tersebut dapat dilihat waktu yang diperlukan melalui jalur kritis yaitu 19

Gantt chart

Dari Gantt Chart tersebut jalur yang berwarna merah adalah jalur kritis, yaitu jalur

dengan waktu penyelesaian proyek terlama. Ada 2 jalur kritis yaitu:

A - C - G dan B – E – G .

Diagram PERT

Jalurnya adalah:

A – C – G : 6 + 3 + 10 = 19

B – E – G : 5 + 4 + 10 = 19

Universitas Widyatama |