spanning tree & cpm 2.doc

LAPORAN RISET OPERASI Ke- 2“Minimum Spanning Tree & PERT-CPM”

OLEH NAMA : Tririn Delita Ayu NIM : 125090500111023

ASISTEN 1 : WAHYU CAHYANINGRUMASISTEN 2 : NUR ASFI ROYHAN

LABORATORIUM KOMPUTERJURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS BRAWIJAYA

2014

BAB IPENDAHULUAN

1.1. LATAR BELAKANG

Dalam kehidupan sehari-hari, apabila kita akan menuju suatu tempat dengan banyak jalur yang ada, kita akan membutuhkan biaya yang mahal untuk mencapai suatu tempat tersebut dengan jalur yang tidak optimal. Dengan adanya minimum spanning tree ini, kita dapat mengetahui jalur mana yang harus dilewati sehingga hanya memerlukan biaya yang murah, dan waktu yang lebih cepat.

Salah satu contohnya adalah perusahaan TV kabel yang memasang kabel ke lingkungan baru. Jika dibatasi untuk mengubur kabel hanya di sepanjang jalan tertentu, maka ada graf yang mewakili suatu jalur. Beberapa jalur tersebut mungkin akan lebih lama, karena memerlukan kabel yang akan dikubur lebih dalam, sehingga membutuhkan biaya yang lebih mahal. Dengan adanya minimum spanning tree, maka akan didapatkan total biaya yang lebih rendah.

Terlepas dari permasalahan minimum spanning tree, dalam menyelesaikan proyek juga diperlukan bgaimana untuk sebanyak mungkin mengurangi adanya penundaan, maupun gangguan produksi, serta mengkoordinasikan berbagai bagian suatu pekerjaan secara menyeluruh dan mempercepat selesainya proyek. Untuk mengatasi permasalahn-permasalahan tersebut digunakan teknik PERT.

Teknik ini memungkinkan dihasilannya suatu pekerjaan yang terkendali dan teratur, karena jadwal dan anggaran dari suatu pekerjaan telah ditentukan terlebih dahulu sebelum dilaksanakan.

Dalam metode PERT dan CPM masalah utamanya yaitu teknik untuk menentukan jadwal kegiatan beserta anggaran biaya dengan maksud pekerjaan pekerjaan yang telah dijadwalkan itu dapat diselesaikan secara tepat waktu serta tepat biaya.

Dalam praktikum ini akan dibahas bagaimana menyelesaikan permasalahan Minimum Spanning Tree dan PERT-CPM dengan software QM.

1.2. TUJUAN1.2.1 Mahasiswa dapat menentukan jalur kritis dan waktu mengambang.1.2.1 Mahasiswa dapat mempertimbangkan probabilitas dan penjadwalan

proyek dan biayanya.

BAB IITINJAUAN PUSTAKA

2.1 Minimum Spanning TreePohon rentang minimum (minimal spanning tree) adalah teknik

mencari jalan penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan sampai diperoleh jarak minimum. (Rahardiantoro, 2014)

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 titik dalam jaringan tersebut pada total jarak (panjang) minimum. (Rahardiantoro, 2014)

Minimum spanning tree adalah suatu pohon yang dapat didefinisikan dengan sebuah graf. Graf berarah dan graf tidak berarah adalah subgraf yang setiap node/simpulnya terkoneksi satu sama lain. Sebuah graf, dapat memberikan pohon rentang yang berbeda. Pada setiap ruas/edge, kita dapat memberikan suatu bobot untuk menentukan suatu nilai. Setiap bobot tersebut akan dibandingkan dengan bobot yang lain yang mengarah pada simpul berikutnya, selanjutnya akan dipilih bobot yang terkecil. Hal ini akan terus dilakukan sampai menuju simpul tujuan. Ini yang disebut dengan minimum spanning tree. (Citra, 2014)

Langkah-langkah dari pohon rentang minimum adalah :1. pilih secara arbitrer sebuah node dalam jaringan2. hubungkan node tersebut dengan node terdekat yang dapat

meminimalkan total jarak3. 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(Rahardiantoro, 2014)

2.2 PERT-CPMPERT adalah suatu alat manajemen proyek yang digunakan untuk

melakukan penjadwalan, mengatur dan mengkoordinasi bagian-bagian pekerjaan yang ada didalam suatu proyek. (Yusuf, 2014)

Manfaat PERT :1. Mengetahui ketergantungan dan keterhubungan tiap pekerjaan dalam

suatu proyek.

2. Dapat mengetahui implikasi dan waktu jika terjadi keterlambatan suatu pekerjaan.

3. Dapat mengetahui kemungkinan untuk mencari jalur alternatif lain yang lebih baik untuk kelancaran proyek.

4. Dapat mengetahui kemungkinan percepatan dari salah satu atau beberapa jalur kegiatan.

(Yusuf, 2014)

Langkah-langkah dalam melakukan perencanaan dengan PERT yaitu :1. Mengidentifikasi aktivitas (activity) dan titik tempuhnya (milestone).2. Menetapkan urutan pengerjaan dari aktivitas-aktivitas yang telah

direncanakan.3. Membuat suatu diagram jaringan (network diagram).

(Yusuf, 2014)

Critical Path Method (CPM) atau Metode Jalur Kritis merupakan model kegiatan proyek yang digambarkan dalam bentuk jaringan. Kegiatan yang digambarkan sebagai titik pada jaringan dan peristiwa yang menandakan awal atau akhir dari kegiatan digambarkan sebagai busur atau garis antara titik. (Yusuf, 2014)

Manfaat CPM : Memberikan tampilan grafis dari alur kegiatan sebuah proyek, Memprediksi waktu yang dibutuhkan untuk menyelesaikan sebuah

proyek, Menunjukkan alur kegiatan mana saja yang penting diperhatikan

dalam menjaga jadwal penyelesaian proyek(Yusuf, 2014)

Perbedaan PERT dan CPM yaitu : CPM menggunakan satu jenis waktu untuk perkiraan waktu

penyelesaian setiap kegiatan sedangkan PERT menggunakan tiga jenis waktu, yaitu : prakiraan waktu optimis, waktu paling mungkin, dan waktu pesimis.

CPM digunakan jika waktu penyelesaian setiap kegiatan diketahui dengan pasti, di mana tingkat deviasi realisasi penyelesaian disbanding rencana relatif minim atau bahkan dapat diabaikan.Sedangkan PERT digunakan pada kegiatan yang waktu penyelesaiannya tidak dapat dipastikan karena belum pernah dilakukan sebelumnya atau kegiatan tersebut memiliki variasi waktu perkiraan penyelesaian yang lebar.

(Yusuf, 2014)

BAB IIIMETODOLOGI

3.1 Minimum Spanning Tree

Langkah-langkah penyelesaian pada software QM :

1. Klik Module Network

2. Klik File New Minimum Spanning Tree

3. Akan muncul di layar seperti tampilan berikut :

Set data dengan mengisi :Title : Panjang Kabel Minimum (kondisional)Number of Brances : 8 (sesuai dengan jumlah arc)Row name : pilih salah satu

4. Klik OK. Akan tampak tabel data seperti gambar berikut :

Mengisi tabel data :Misal Branch 1 (i,j) Start node : i ; End node : j ; Distance : panjang archCost : panjang busur / arch

5. Klik Solve

3.2 PERT - CPMLangkah-langkah penyelesaian dengan software QM :1. Klik Module Project Management (PERT / CPM)

2. Klik File New Crashing

3. Akan muncul di layar seperti tampilan berikut :

Set data dengan mengisi :

Title : Pembangunan Rumah (kondisional)Number of Task : 7 (sesuai dengan jumlah aktivitas)Table Structure : pilih salah satuRow name : pilih salah satu

4. Klik OK. Akan tampak tabel data seperti gambar berikut :

Pada tabel diisi :Start node : initial nodeEnd node : terminal nodeActivity time : lama aktivitas

5. Klik Solve

BAB IV

HASIL DAN PEMBAHASAN

1. Jarak (dalam mil) antara kecamatan-kecamatn Klojen, Blimbing, Sukun, Lowokwaru, dan Kedungkandang dapat dilihat di tabel dibawah. Pemerintah Kota Malang ingin membangun sistem jalan yang menghubungkan semua kecamatan-kecamatan tersebut. Asumsikan, karena alasan politik, tidak boleh ada jalan yang menghubungkan Klojen dan Blimbing dan tidak boleh ada jalan yang menghubungkan Kedungkandang dan Sukun. Berapa panjang jalan minimum yang diperlukan.

Klojen Blimbing Sukun Lowokwaru Kedung kandang

Klojen - 155 240 187 81Blimbing 155 - 313 224 102

Sukun 240 313 - 136 326Lowokwaru 187 224 136 - 219

Kedungdandang 81 102 326 219 -

2. Perhatikan daftar kegiatan dan predesesornya yang berkaitan dengan pembangunan rumah pada tabel berikut

Kegiatan Deskripsi Immediate Predecessor

Durasi (hari)

Pengurangan maksimum durasi kegiatan (hari)

A Membangun pondasi - 7 4B Membangun dinding A 10 5C Membangun atap B 12 3D Pengkabelan listrik B 7 4E Memasang jendela B 6 4F Memasang peneduh E 8 5G Mengecat C, F 5 3

Penyelesaian1. Panjang jalan antar kecamatan :

Kedungkandang 102 81

219

187 224 Klojen Lowokwaru Blimbing

240 136 313

Sukun

Output Minimum Spanning Tree dari software QM :

Interpretasi :Panjang jalan minimum yang dibutuhkan Pemerintah Kota Malang untuk membangun sistem jalan yang menghubungkan semua kecamatan-kecamatan tersebut adalah 506 mil. Jalur yang dibangun untuk sistem jalan tersebut yaitu dari Klojen ke Kedungkandang sepanjang 81 mil, dari Kedungkandang ke Blimbing

22

1111

55

44

33

sepanjang 102 mil, dari Klojen ke Lowokwaru sepanjang 187 mil, Lowokwaru ke Sukun sepanjang 136 mil.

2. Jalur proyek pembangunan rumah : F G

C Dummy

A B E

D

Output dari software QM :

Interpretasi :Pembangunan rumah dapat diselesaikan dalam waktu 36 hari (Normal time), dapat dipercepat dalam waktu 21 hari (Crash time).

1111

5151

2121

7171

6161

4141

3131

8181

Interpretasi : Membangun pondasi, membangun dinding, membangun atap,

memasang jendela, memasang peneduh dapat dipercepat secara bersamaan pada hari ke 21, namun mengecat dapat dipercepat selama 2 hari.

Membangun pondasi, membangun dinding, membangun atap, memasang jendela, memasang peneduh dapat dipercepat secara bersamaan pada hari ke 22, namun untuk mengecat dapat dipercepat selama 1 hari.

Membangun pondasi, membangun dinding, memasang jendela dapat dipercepat secara bersamaan pada hari ke 23, namun membangun atap dapat dipercepat selama 3 hari, dan memasang peneduh dapat dipercepat selama 3 hari.

Membangun pondasi, membangun dinding, memasang jendela dapat dipercepat secara bersamaan pada hari ke 24, namun membangun atap dapat dipercepat selama 2 hari, dan memasang peneduh dapat dipercepat selama 2 hari.

Membangun pondasi, membangun dinding, memasang jendela dapat dipercepat secara bersamaan pada hari ke 25, namun membangun atap dapat dipercepat selama 1hari, dan memasang peneduh dapat dipercepat selama 1 hari.

Membangun pondasi dan memasang jendela dapat dipercepat secara bersamaan pada hari ke 26, namun membangun dinding dapat dipercepat selama 5 hari.

Membangun pondasi dan memasang jendela dapat dipercepat secara bersamaan pada hari ke 27, namun membangun dinding dapat dipercepat selama 4 hari.

Membangun pondasi dan memasang jendela dapat dipercepat secara bersamaan pada hari ke 28, namun membangun dinding dapat dipercepat selama 3 hari.

Membangun pondasi dan memasang jendela dapat dipercepat secara bersamaan pada hari ke 29, namun membangun dinding dapat dipercepat selama 2 hari.

Membangun pondasi dan memasang jendela dapat dipercepat secara bersamaan pada hari ke 30, namun membangun dinding dapat dipercepat selama 1hari.

Memasang jendela dapat dipercepat secara bersamaan pada hari ke 31, namun membangun pondasi dapat dipercepat selama 3 hari.

Memasang jendela dapat dipercepat secara bersamaan pada hari ke 32, namun membangun pondasi dapat dipercepat selama 2 hari.

Memasang jendela dapat dipercepat secara bersamaan pada hari ke 33, namun membangun pondasi dapat dipercepat selama 1 hari.

Memasang jendela dapat dipercepat secara bersamaan pada hari ke 34.

Memasang jendela dapat dipercepat secara bersamaan pada hari ke 35.

Memasang jendela dapat dipercepat selama 2 hari. Untuk pengkabelan listrik tidak dapat dipercepat secara bersamaan

maupun sendiri.

BAB VPENUTUP

5.1 KESIMPULAN 5.1.1 Agar panjang jalan minimum, Pemerintah Kota Malang harus

membangun system jalan dari kecamatan Klojen ke Kedungkandang sepanjang 81 mil, dari Kedungkandang ke Blimbing sepanjang 102 mil, dari Klojen ke Lowokwaru sepanjang 187 mil, dan dari Lowokwaru ke Sukun sepanjang 136 mil.

5.1.2 Pembangunan rumah dapat diselesaikan dalam waktu 36 hari (Normal time), dapat dipercepat dalam waktu 21 hari (Crash time).

5.2 SARANDalam menyelesaikan permasalahan Minimum Spanning Tree dan PERT-CPM lebih mudah membuat suatu diagram jaringan terlebih dahulu sebelum memasukkan data ke software QM. Selain itu juga harus mengerti bagaimana menginterpretasi hasil output yang diperoleh dari software QM

DAFTAR PUSTAKA

http://adithacitra.blogspot.com/2010/05/minimum-spanning-tree.htm

http://dickyrahardi.blogspot.com/2008/05/minimal-spanning-tree.html

http://maulana-ysf.blogspot.com/2013/11/pengertian-wbs-pert-cpm.html