Analisis dan Penerapan Algoritma Particle Swarm Optimization (PSO) pada Optimasi Penjadwalan Sumber Daya Proyek
Analysis and Implementation of Particle Swarm Optimization (PSO) Algorithm on the Optimization of Project Resource Scheduling Tugas Akhir
Diajukan untuk memenuhi sebagian dari syarat untuk memperoleh gelar Sarjana Teknik Departemen Teknik Informatika IT TELKOM
Evi Ria Zerda 113078029
Departemen Teknik Informatika Institut Teknologi Telkom Bandung 2009
Lembar Pernyataan Dengan ini saya menyatakan bahwa Tugas Akhir dengan judul “Analisis dan Penerapan Algoritma Particle Swarm Optimization (PSO) pada Optimasi Penjadwalan Sumber Daya Proyek” beserta seluruh isinya adalah benar-benar karya saya sendiri dan saya tidak melakukan penjiplakan atau pengutipan dengan cara-cara yang tidak sesuai dengan etika kei1muan yang berlaku dalam masyarakat keilmuan. Atas pernyataan ini, saya siap menanggung resiko/sanksi yang dijatuhkan kepada saya apabila kemudian ditemukan adanya pelanggaran terhadap etika keilmuan dalam karya saya ini, atau ada k1aim dari pihak lain terhadap keaslian karya saya ini.
Bandung, 23 Juni 2009 Yang membuat pernyataan,
(Evi Ria Zerda)
Lembar Pengesahan Analisis dan Penerapan Algoritma Particle Swarm Optimization (PSO) pada Optimasi Penjadwalan Sumber Daya Proyek
Analysis and Implementation of Particle Swarm Optimization (PSO) Algorithm on the Optimization of Project Resource Scheduling
Evi Ria Zerda 113078029
Tugas Akhir ini telah diterima dan disahkan untuk memenuhi sebagian dari syarat untuk memperoleh gelar Sarjana Teknik Departemen Teknik Informatika IT TELKOM
Bandung, 23 Juni 2009
Menyetujui
Pembimbing
Suyanto, ST, MSc. NIP: 99740178-1
Abstrak Penjadwalan sumber daya (resource scheduling) merupakan salah satu perencanaan operasional proyek yang didalamnya terdapat proses mengidentifikasi jenis dan jumlah sumber daya sesuai dengan jadwal keperluan yang telah ditetapkan. Kebutuhan sumber daya untuk masing-masing satuan waktu bisa berbeda, sehingga ada kemungkinan terjadi fluktuasi kebutuhan sumber daya. Oleh karena itu, fluktuasi yang tinggi selama perjalanan proyek harus dihindari, dengan kata lain diperlukan perataan penggunaan sumber daya (resource leveling) sepanjang waktu proyek. Permasalahan optimasi perataan penggunaan sumber daya merupakan masalah yang sudah umum dan telah dipelajari dalam waktu yang lama, namun perlu dicari metodologi atau pendekatan teknis yang memadai dan sampai saat ini telah berkembang beberapa solusi alternatif yang ditawarkan. Pada Tugas Akhir ini, dibahas penerapan algoritma particle swarm optimization (PSO), pada optimasi penjadwalan sumber daya proyek. Hasil penelitian menunjukkan bahwa algoritma particle swarm optimization dapat diterapkan pada permasalahan optimasi perataan penggunaan sumber daya. Keefektifan algoritma ini didemonstrasikan dengan beberapa studi kasus. Dari test yang telah dilakukan menunjukkan bahwa pendekatan ini dapat memberikan solusi yang bagus dengan fluktuasi yang minimal. Kata kunci: penjadwalan sumber daya proyek, fluktuasi, Resource Leveling, PSO
i
Abstract Resource scheduling is one of project operational planning which there is have process identifies resources amount and type according to the activity that scheduled. Requirements of resources for each times can different, so maybe there is fluctuation of need resources. So, a high of fluctuation during project tour must be avoid, i.e.needed resource leveling during project time. The problem of resource leveling optimization is a common problem in have studied at long time, but must be search a new methodology or several heuristic in order to produce the optimal solutions of the problem. In this final assignment, we discuss an implementation of the particle swarm optimization (PSO), on the optimization of project resource scheduling. Final result shows that particle swarm optimization can be implement on the optimization of resource leveling problem. The effectiveness of this heuristic is demonstrated with case studies. Preliminary test shows that this approach can give a good solution with minimal fluctuation. Keywords: project resource scheduling, fluctuation, resource leveling, PSO
ii
Lembar Persembahan
“ Sesungguhnya sesudah kesulitan itu ada kemudahan ” (A Lam Nasyrah [94] : 6)
Buku ini kupersembahkan untuk : Mama dan Papa, atas segala yang telah diberikan terutama do’a yang tidak pernah terputus. Adikku satu-satunya yang tersayang Novri Ria Zerda. Ini merupakan hal kecil yang bisa Evi persembahkan pada saat ini, semoga hal ini bisa membuat semuanya bahagia dan bangga kepada Evi.
iii
Ucapan Terima Kasih Î Rasa syukur selalu terpanjatkan kepada Allah SWT atas semua bimbinganNya dalam menjalani hidup ini, fase TA ini bisa terlewati dengan baik atas semua kehendak-Nya. Î Mamaku tersayang atas segalanya terutama kepercayaan yang besar atas semua yang Evi lakukan, Papaku tercinta atas segala kesabarannya dengerin semua keluh kesahku. Î Adekku tersayang Novri Ria Zerda, Mari kita lakukan yang terbaik buat mama dan papa. Makasih atas semuanya. Î Om Mahmud dan Tek Ufix, makasih atas semuanya serta Puput dan Dwi, kalian selalu buat Evi ingin pulang kerumah. Semua keluargaku disana, kalian penyemangat terbesar dalam hidupku. Î Almarhum kakekku Agus, Evi sudah S1 sekarang. Nenekku, makasih atas do’anya dan nasehat yang selalu diberikan untuk Evi. Î Bapak Suyanto, ST, MSc. Selaku pembimbing tunggal, makasih atas segala ilmu yang telah diberikan buat penyelesaian Tugas Akhir ini. Î Keluarga LAB MASTA yang tercinta, K2 arif, Mbak Ayu, Ri, Eka, Fula, Na, Narno, Teguh, Risna, Nofy, Henny, Miza. I Love U All. Î Temen-temen di D3IF-28-01 dan IFX-31-01, terima kasih atas semangat yang telah diberikan selama ini dan kalian adalah keluarga baruku disini. Î Semua mahasiswa IT Telkom atas doa dan support-nya selama ini. Terakhir kami minta maaf jika ada salah-salah kata yang menyakiti hati. Î Seluruh dosen yang ada di IT Telkom. Terima kasih ilmunya. Î Teman-teman kepanitian dan organisasi Evi selama ini. PDKT 2005 terutama DC, PDKT 2006 terutama DC, LDKO 2006 terutama AMS, LDKO 2007 terutama SC, HMIF 2005/2006 terutama BPH, SETJEN
iv
2006/2007 terutama PusMeong, BEM 2007/2008 terutama Keuangan. Maafkanlah jika selama ini Evi belum memberikan yang terbaik buat kalian semua tapi yakinlah bahwa kalian semua adalah keluarga baru Evi disini. Semoga silahturahmi ini akan tetap terus dijaga. Î Temen-temen curhatku tiap minggu, makasih atas semuanya. Î Temen-temen kos-an di Gedong 4. Î Ulfa dan Rie atas persahabatan yang hampir 5 tahun ini, maafkan Evi bila belum menjadi sahabat terbaik kalian dan membuat kesal kalian, makasih atas semuanya dari mulai surprise ulang tahunnya, nonton bareng, makan bareng, jalan bareng ampe ide gila yang belum sempet kita lakukan. Devi dan Dana. Î Nurul, atas kesabarannya menghadapi diriku yang sering menyusahkanmu baik disaat Evi sakit dan butuh temen untuk cerita. Ery dan Nisa. Î Diar atas persahabatan yang singkat ini tapi unik, kapan kita main bombom car lagi ??? Î Mbak Nana Chan atas curhat TA-nya di Perpus, pinjeman buku dan semua sharing ilmunya. Moga kita melakukan hal yang ingin kita lakukan selama ini. Mbak Leni dan Olin. Î K2 Andik atas bantuan Activity.slack = Activity.LFT - Activity.EFT PDKT, MABIM, LDKO, Kuliah, Ngulang, TP, Masteran, Praktikum, Kerja Lab, Tugas Besar, Quis, Tugas Kuliah, UTS, UAS, Seminar, Sidang TA, Revisi TA. Semuanya telah dilewati di bangku kuliah yang hampir 5 tahun ini, banyak hal yang diambil dari perjalanan ini semuanya dan semoga itu menjadi bekal buat kehidupan selanjutnya.
Bandung, 18 Februari 2009 1:55 AM
v
Kata Pengantar Segala puji dan syukur atas segala anugerah nikmat dan rahmat Allah SWT penulis dapat menyelesaikan Tugas Akhir ini, dengan judul “Analisis dan Penerapan Algoritma Particle Swarm Optimization (PSO) pada Optimasi Penjadwalan Sumber Daya Proyek”. Bermula dari membaca tawaran judul Tugas Akhir dari dosen serta mencari studi kasus yang cocok untuk penerapan algoritma tersebut maka muncullah ide untuk membuat Tugas Akhir dengan judul diatas. Tugas Akhir ini telah memberi banyak pengalaman kepada penulis mengenai banyak hal mulai dari mempelajari manajemen proyek lebih detail, memahami setiap notasi matematika yang ada serta memahami diri ini sendiri dengan lebih banyak. Tugas Akhir ini merupakan salah satu hal yang dapat dilakukan penulis pada saat ini tapi mudah-mudahan ini menjadi jembatan untuk berkarya lebih baik lagi. Penulis mengucapkan banyak terima kasih kepada semua pihak yang terkait dalam pembuatan Tugas Akhir ini. Pada akhirnya, harapan akan adanya suatu perbaikan pada tugas akhir ini tentu selalu ada dikarenakan keterbatasan penulis, sehingga sangat diharapkan adanya kritik dan saran yang membangun untuk pencapaian yang lebih baik. Terima kasih. Bandung, 23 Juni 2009
Evi Ria Zerda
vi
Daftar Isi ABSTRAK ........................................................................................................................................... I ABSTRACT .......................................................................................................................................II LEMBAR PERSEMBAHAN ......................................................................................................... III UCAPAN TERIMA KASIH .......................................................................................................... IV KATA PENGANTAR ..................................................................................................................... VI DAFTAR ISI ................................................................................................................................... VII DAFTAR GAMBAR ....................................................................................................................... IX DAFTAR TABEL .............................................................................................................................. X DAFTAR ISTILAH......................................................................................................................... XI 1
2
PENDAHULUAN ....................................................................................................................... 1 1.1
LATAR BELAKANG ................................................................................................................ 1
1.2
PERUMUSAN MASALAH ......................................................................................................... 2
1.3
TUJUAN ................................................................................................................................. 3
1.4
METODOLOGI PENYELESAIAN MASALAH .............................................................................. 3
DASAR TEORI .......................................................................................................................... 5 2.1
OPTIMASI .............................................................................................................................. 5
2.1.1
Definisi Optimasi ......................................................................................................... 5
2.1.2
Definisi Nilai Optimal .................................................................................................. 5
2.2
MANAJEMEN PROYEK ........................................................................................................... 5
2.2.1
Penjadwalan Sumber Daya Proyek ............................................................................. 6
2.2.2
Slack ............................................................................................................................. 6
2.2.3
Resource Leveling ........................................................................................................ 7
2.3 ALGORITMA PARTICLE SWARM OPTIMIZATION ......................................................................... 7 2.3.1
Proses Algoritma Particle Swarm Optimization ......................................................... 8
2.3.2
Parameter Algoritma Particle Swarm Optimization .................................................. 9
3. ANALISA DAN PERANCANGAN ....................................................................................... 11 3.1
DESKRIPSI UMUM SISTEM .................................................................................................. 11
3.2
REPRESENTASI VEKTOR POSISI PARTICLE, RUANG SOLUSI DAN KECEPATAN.................. 11
3.3
FUNGSI FLUKTUASI............................................................................................................. 12
3.4
ANALISA KEBUTUHAN SISTEM ........................................................................................... 14
3.4.1 Spesifikasi Perangkat Keras ............................................................................................. 14 3.4.2 Spesifikasi Perangkat Lunak............................................................................................. 14 3.5
PERANCANGAN ................................................................................................................... 14
3.5.1 Struktur Tabel Basis Data................................................................................................. 14 3.5.2 Gambaran Keseluruhan Sistem ........................................................................................ 15
vii
3.5.3 Diagram Use case ............................................................................................................. 16 3.5.4 Diagram Sekuensial : PSO Optimization ......................................................................... 17 3.5.5 Diagram Sekuensial : Set PSO’s Parameters .................................................................. 18 3.5.6 Diagram Sekuensial : Load Project ................................................................................. 19 3.5.7 Diagram Kelas .................................................................................................................. 20 4. ANALISIS HASIL PERCOBAAN......................................................................................... 25 4.1 PENGUJIAN SISTEM ................................................................................................................... 25 4.1.1 Tujuan Pengujian .............................................................................................................. 25 4.1.2 Skenario Pengujian ........................................................................................................... 25 4.1.3 Parameter Pengujian ........................................................................................................ 26 4.1.4 Kasus Uji yang Digunakan ............................................................................................... 26 4.2 PELAKSANAAN UJI COBA TERHADAP PARAMETER ALGORITMA PSO ..................................... 26 4.3 ANALISIS HASIL OPTIMASI PENJADWALAN SUMBER DAYA PROYEK ...................................... 29 4.3.1 Proyek Qureshi.................................................................................................................. 29 4.3.2 Proyek LOGON ................................................................................................................. 31 4.3.3 Proyek Building ................................................................................................................. 32 4.4
PERBANDINGAN DENGAN ALGORITMA RANK BASED ANT SYSTEM (ASRANK) ................... 34
4.4.1 Proyek Qureshi.................................................................................................................. 34 4.4.2 Proyek LOGON ................................................................................................................. 35 4.4.3 Proyek Building ................................................................................................................. 35 4.5
HASIL RE-OPTIMIZE ........................................................................................................... 36
5. KESIMPULAN DAN SARAN ................................................................................................ 37 5.1 KESIMPULAN ............................................................................................................................. 37 5.2 SARAN ....................................................................................................................................... 37 DAFTAR PUSTAKA ....................................................................................................................... 38 LAMPIRAN A : ................................................................................................................................ 40 LAMPIRAN B : ................................................................................................................................ 42
viii
Daftar Gambar GAMBAR 1-1 CONTOH GRAFIK SUMBER DAYA PROYEK (A) SEBELUM DAN (B) SETELAH DIRATAKAN .................................................................................................................................. 1 GAMBAR 1-2 ILUSTRASI ALGORITMA PARTICLE SWARM OPTIMIZATION............................................ 2 GAMBAR 1-3 FLOW CHART SISTEM OPTIMASI PENJADWALAN SUMBER DAYA PROYEK DENGAN ALGORITMA PARTICLE SWARM OPTIMIZATION ........................................................................... 4 GAMBAR 2-1 GRAFIK-GRAFIK IDEAL SUMBER DAYA ......................................................................... 7 GAMBAR 2-2 ILUSTRASI PERUBAHAN KECEPATAN .............................................................................. 8 GAMBAR 2-3 ILUSTRASI PERUBAHAN POSISI ....................................................................................... 9 GAMBAR 3-1 GRAFIK YANG TIDAK QUASI CONCAVE ......................................................................... 12 GAMBAR 3-2 GRAFIK YANG QUASI CONCAVE .................................................................................... 13 GAMBAR 3-3 GRAFIK DENGAN SEJUMLAH SUMBER DAYA YANG TIDAK DIGUNAKAN ..................... 13 GAMBAR 3-4 DIAGRAM BASIS DATA ................................................................................................. 14 GAMBAR 3-5 GAMBARAN KESELURUHAN SISTEM OPTIMASI PENJADWALAN SUMBER DAYA PROYEK ....................................................................................................................................... 15 GAMBAR 3-6 DIAGRAM USE CASE ..................................................................................................... 16 GAMBAR 3-7 DIAGRAM SEKUENSIAL: PSO OPTIMIZATION ............................................................... 17 GAMBAR 3-8 DIAGRAM SEKUENSIAL: SET PSO’S PARAMETERS ....................................................... 18 GAMBAR 3-9 DIAGRAM SEKUENSIAL: LOAD DATA ........................................................................... 19 GAMBAR 3-10 DIAGRAM KELAS ........................................................................................................ 21 GAMBAR 4-1 GRAFIK PENGUJIAN PARAMETER .................................................................................. 27 GAMBAR 4-2 GRAFIK SUMBER DAYA PROYEK QURESHI SEBELUM DIOPTIMASI .............................. 29 GAMBAR 4-3 GRAFIK SUMBER DAYA PROYEK QURESHI SETELAH DIOPTIMASI ............................... 30 GAMBAR 4-4 GRAFIK SUMBER DAYA PROYEK LOGON SEBELUM DIOPTIMASI .............................. 31 GAMBAR 4-5 GRAFIK SUMBER DAYA PROYEK LOGON SETELAH DIOPTIMASI ............................... 32 GAMBAR 4-6 GRAFIK SUMBER DAYA PROYEK BUILDING SEBELUM DIOPTIMASI ............................ 32 GAMBAR 4-7 GRAFIK SUMBER DAYA PROYEK BUILDING SETELAH DIOPTIMASI ............................. 33 GAMBAR 4-8 GRAFIK SUMBER DAYA PROYEK QURESHI SETELAH DIOPTIMASI DENGAN ALGORITMA RANK BASED ANT SYSTEM (ASRANK) .......................................................................................... 34 GAMBAR 4-9 GRAFIK SUMBER DAYA PROYEK LOGON SETELAH DIOPTIMASI DENGAN ALGORITMA RANK BASED ANT SYSTEM (ASRANK) .......................................................................................... 35 GAMBAR 4-10 GRAFIK SUMBER DAYA PROYEK BUILDING SETELAH DIOPTIMASI DENGAN ALGORITMA RANK BASED ANT SYSTEM (ASRANK) ..................................................................... 35
ix
Daftar Tabel TABEL 4-1 NILAI FLUCT UNTUK M=60 DAN NC=1000........................................................................ 27 TABEL 4-2 NILAI FLUCT UNTUK M=100 DAN NC=600........................................................................ 28 TABEL 4-3 PARAMETER TERBAIK UNTUK PROYEK LOGON .............................................................. 30 TABEL 4-4 PERBANDINGAN GRAFIK SUMBER DAYA PROYEK QURESHI............................................ 30 TABEL 4-5 PARAMETER TERBAIK UNTUK PROYEK LOGON .............................................................. 31 TABEL 4-6 PERBANDINGAN GRAFIK SUMBER DAYA PROYEK LOGON ............................................ 32 TABEL 4-7 PARAMETER TERBAIK UNTUK PROYEK LOGON .............................................................. 33 TABEL 4-8 PERBANDINGAN GRAFIK SUMBER DAYA PROYEK BUILDING ......................................... 33 TABEL 4-9 PERBANDINGAN GRAFIK SUMBER DAYA PROYEK QURESHI SETELAH DIOPTIMASI ANTARA ALGORITMA ASRANK DAN ALGORITMA PSO ................................................................. 34 TABEL 4-10 PERBANDINGAN GRAFIK SUMBER DAYA PROYEK LOGON SETELAH DIOPTIMASI ANTARA ALGORITMA ASRANK DAN ALGORITMA PSO ................................................................. 35 TABEL 4-11 PERBANDINGAN GRAFIK SUMBER DAYA PROYEK BUILDING SETELAH DIOPTIMASI ANTARA ALGORITMA ASRANK DAN ALGORITMA PSO ................................................................. 36 TABEL 5-1 PARAMETER TERBAIK UNTUK KASUS UJI LOGON ......................................................... 37
x
Daftar Istilah Aktivitas Algoritma particle swarm optimization
Constraint Critical Path Critis Time C1 C2 Durasi EFT EST Fluktuasi Inertia Weight LFT LST Kecepatan Posisi Predecessor Proyek
Resource Leveling
Slack
Stagnasi Start Time Successor
Kegiatan yang mendukung diselesaikannya suatu proyek. Teknik optimasi berbasis stochastic yang diinspirasi oleh tingkah laku sosial sekawanan burung atau sekumpulan ikan yang pertama kali dikenalkan oleh Dr. Eberhart dan Dr. Kennedy ditahun 1995 Batasan-batasan yang tidak boleh dilanggar oleh semua solusi yang ditemukan. Jalur kritis, predikat yang melekat pada aktivitas yang memiliki slack = 0. Waktu minimal untuk dapat menyelesaikan suatu proyek. Faktor learning untuk particle. Faktor learning untuk swarm. Lamanya suatu kegiatan dilaksanakan. Earliest Finish Time. Waktu paling awal diselesaikannya suatu aktivitas. Earliest Start Time. Waktu paling awal dimulainya suatu aktivitas. Naik turunnya kebutuhan sumber daya. Parameter penurunan kecepatan untuk menghindari stagnasi particle di lokal optimum. Latest Finish Time. Waktu paling akhir diselesaikannya suatu aktivitas. Latest Start Time. Waktu paling akhir dimulainya suatu aktivitas. Nilai perubahan jarak dari seluruh aktivitas untuk mendapatkan posisi baru. Waktu mulai (start time) dari seluruh aktivitas. suatu aktivitas yang harus dimulai dan selesai sebelum aktivitas yang bersangkutan dimulai. Suatu kegiatan manufaktur atau jasa yang di dalamnya terdapat serangkaian aktivitas yang mendukung terwujudnya suatu produk akhir. Proses mengusahakan penjadwalan aktifitas agar menggunakan sumber daya secara merata sepanjang proyek. Jumlah waktu yang diperkenankan suatu aktivitas boleh ditunda, tanpa mempengaruhi jadwal penyelesaian proyek secara keseluruhan. Kondisi dimana semua particle telah melalui jalur yang sama. Waktu dimana suatu aktivitas dimulai suatu aktivitas yang baru dapat dimulai setelah aktivitas yang bersangkutan diselesaikan.
xi
1
Pendahuluan
1.1 Latar belakang Setiap proyek memiliki tujuan khusus yang akan dicapai. Didalam proses mencapai tujuan tersebut, ada batasan yang harus dipenuhi yaitu besar biaya (anggaran) yang dialokasikan, jadwal, serta mutu yang harus dipenuhi [19]. Dikarenakan adanya keterbatasan jadwal yang ada (proyek harus dikerjakan sesuai dengan kurun waktu dan tanggal akhir yang telah ditentukan) maka diperlukan suatu perencanaan operasional proyek tersebut [19]. Salah satu perencanaan operasional proyek tersebut adalah penjadwalan sumber daya (resource scheduling) yang didalamnya terdapat proses mengidentifikasi jenis dan jumlah sumber daya sesuai dengan jadwal keperluan yang telah ditetapkan. Aspek lain yang perlu diperhatikan dalam hubungan antara jadwal dan sumber daya adalah usaha pemakaian secara efisien. Kebutuhan sumber daya untuk masing-masing satuan waktu bisa berbeda, sehingga ada kemungkinan terjadi fluktuasi kebutuhan sumber daya. Fluktuasi ini berpengaruh terhadap anggaran, karena adanya waktu dimana sumber daya tidak diberdayakan sedangkan biaya tetap keluar atau adanya penambahan intensitas perekrutan dan pemberhentian sumber daya yang cukup membutuhkan biaya. Oleh karena itu, fluktuasi yang tinggi selama perjalanan proyek harus dihindari, dengan kata lain diperlukan perataan penggunaan sumber daya (resource leveling) sepanjang waktu proyek agar perencanaan anggaran dapat diminimalkan. Proses perataan diilustrasikan pada gambar di bawah ini.
Gambar 1-1 Contoh Grafik Sumber Daya Proyek (a) Sebelum dan (b) Setelah Diratakan Pada dasarnya resource leveling menunda aktivitas tidak kritis dengan menggunakan slack positif untuk mengurangi permintaan puncak dan mengisi permintaan yang rendah. Perataan sumber daya dilakukan dengan cara menggeser setiap kegiatan yang memiliki slack. Slack dari satu kegiatan dapat digunakan untuk menghitung banyaknya kemungkinan kegiatan itu bisa digeser. Jika dalam jadwal suatu proyek ada banyak kegiatan yang memiliki slack maka kombinasi antar kegiatan akan menghasilkan jadwal yang banyak. Masalah penjadwalan sumber daya merupakan masalah kombinatorial yang besar, bahkan untuk
1
jaringan proyek ukuran sedang dengan hanya sedikit jenis sumber daya, dapat membuat ribuan solusi yang mungkin. Beberapa peneliti sudah menunjukkan solusi matematika optimum untuk alokasi masalah sumber daya, tetapi hanya untuk jaringan kecil dan sangat sedikit jenis sumber daya. Sebuah pendekatan alternative untuk masalah tersebut adalah penggunaan metode heuristik untuk memecahkan masalah kombinatorial besar. Secara umum, penyelesaian masalah optimasi dapat dilakukan dengan menggunakan dua metode, yaitu metode konvensional dan metode heuristik. Metode konvensional diterapkan dengan perhitungan matematis biasa, sedangkan metode heuristik diterapkan dengan perhitungan kecerdasan buatan. Ada beberapa algoritma pada metode heuristik yang biasa digunakan dalam permasalahan optimasi. Sedangkan pada tugas akhir ini digunakan algoritma particle swarm optimization untuk melakukan optimasi.
Gambar 1-2 Ilustrasi Algoritma Particle Swarm Optimization Salah satu konsep yang unik dari algoritma particle swarm optimization adalah menerbangkan solusi yang potensial ke “hyperspace”, ini berarti mempercepat ke solusi yang terbaik [11]. Algoritma particle swarm optimization diinisialisasi dengan sekumpulan particle secara random (setiap particle merepresentasikan solusi yang mungkin untuk masalah optimasi) dan kemudian mencari solusi terbaik dengan mengupdate generasi. Setiap particle memiliki vektor posisi dan kecepatan, keduanya diinisialisasi secara random diawal, kemudian particle “fly” ke target tujuannya dengan dipandu oleh nilai swarm yang terbaik (global best) Pgd dan nilai mereka sendiri yang terbaik (local best) Pid untuk setiap particle, posisi dievaluasi dengan menggunakan fungsi fluktuasi.
1.2 Perumusan masalah Perumusan masalah dalam tugas akhir ini adalah sebagai berikut : 1. Bagaimana mendapatkan fluktuasi sumber daya yang minimal pada penjadwalan sumber daya proyek.
2
2. Bagaimana menerapkan algoritma particle swarm optimization pada masalah optimasi penjadwalan sumber daya proyek. Batasan masalah dalam tugas akhir ini, yaitu: 1. Sumber daya tidak dapat digunakan oleh dua atau lebih kegiatan dalam waktu yang bersamaan. 2. Optimasi penjadwalan sumber daya proyek dilakukan dengan Resource Leveling dan tidak mempercepat waktu kegiatan proyek. 3. Sumber daya yang digunakan berupa orang.
1.3 Tujuan Tujuan yang akan dicapai adalah: 1. Mengimplementasikan algoritma particle swarm optimization pada kasus penjadwalan sumber daya proyek untuk mendapatkan fluktuasi penjadwalan sumber daya proyek yang minimal. 2. Menganalisis parameter-parameter terbaik pada algoritma particle swarm optimization untuk melakukan optimasi penjadwalan sumber daya proyek, yaitu , dan W.
1.4 Metodologi penyelesaian masalah Metodologi yang digunakan dalam penulisan tugas akhir ini adalah: 1. Studi Literatur Mempelajari teori-teori dasar mengenai konsep perataan sumber daya proyek (resource leveling) dan algoritma particle swarm optimization dari berbagai sumber. 2. Analisa dan Perancangan Menganalisa dan merancang penerapan algoritma particle swarm optimization ke dalam sistem aplikasi optimasi penjadwalan sumber daya proyek yang akan dibangun seperti disajikan pada gambar di bawah ini.
3
Gambar 1-3 Flow Chart Sistem Optimasi Penjadwalan Sumber Daya Proyek dengan Algoritma Particle Swarm Optimization 3. Implementasi Mengimplementasikan perancangan ke dalam pemrograman komputer. 4. Pengujian Aplikasi Menguji terhadap hasil implementasi. 5. Analisis Hasil Pengujian Data yang didapat dari hasil pengujian dianalisa untuk memperoleh kesimpulan. 6. Kesimpulan Mengambil kesimpulan dari hasil analisis.
4
2 2.1
Dasar Teori
Optimasi
Optimasi sangat berguna dihampir segala bidang dalam rangka melakukan usaha secara efektif dan efisien untuk mencapai target hasil yang ingin dicapai. Tentunya hal ini akan sangat sesuai dengan prinsip ekonomi yang berorientasikan untuk senantiasa menekan pengeluaran untuk menghasilkan outputan yang maksimal. Optimasi ini juga penting karena persaingan saat ini sudah benar-benar ketat. Seperti yang dikatakan diawal, bahwasanya optimasi sangat berguna hampir diseluruh bidang yang ada, maka berikut ini adalah contoh-contoh bidang yang sangat terbantu dengan adanya teknik optimasi tersebut. Bidang tersebut antara lain : arsitektur, data mining, jaringan komputer, signal dan image processing, telekomunikasi, ekonomi, transportasi, perdagangan, perikanan, pertanian, perkebunan, perhutanan dan sebagainya. Teknik optimasi secara umum dapat dibagi menjadi dua bagian, yang pertama adalah mathematical programming dan yang kedua adalah combinatorial optimization. Optimasi untuk kasus penjadwalan sumber daya proyek dapat diselesaikan dengan meminimumkan fluktuasi sumber daya proyek selama perjalanan proyek [21]. 2.1.1 Definisi Optimasi Optimasi merupakan aktivitas untuk mendapatkan hasil yang terbaik atau optimal (nilai efektif yang dapat dicapai) dari pilihan yang tersedia. Tujuan dari setiap keputusan adalah untuk meminimumkan usaha yang dilakukan atau memaksimumkan keuntungan yang diperoleh. Usaha atau keuntungan tersebut secara praktek dinyatakan sebagai fungsi dengan variabel keputusan yang akan dicari nilai optimumnya. 2.1.2 Definisi Nilai Optimal Nilai optimal adalah nilai yang didapat dengan melalui suatu solusi jawaban yang paling baik dari semua solusi yang ada. Nilai optimal dapat dicari dengan dua cara, yaitu: 1) Cara konvensional, yaitu mencoba semua kemungkinan yang ada dengan mencatat nilai yang didapat. Cara ini kurang efektif karena optimasi akan berjalan secara lambat. 2) Cara kedua adalah dengan menggunakan suatu rumus atau gambar sehingga nilai optimal dapat diperkirakan dengan cepat dan tepat.
2.2
Manajemen Proyek
Proyek merupakan kegiatan yang memiliki sasaran yang jelas, mengkonsumsi sumber daya, memiliki batas waktu (ada waktu mulai dan waktu selesai) dan menghasilkan perubahan [3]. Sifat dan karakteristik proyek yang perlu diperhatikan dalam kaitannya dengan manajemen penyelenggaraan proyek antara lain yaitu bahwa proyek adalah : 1) Bersifat Kompleks
5
Pada umumnya proyek tersusun dari banyak kegiatan yang memiliki korelasi yang ketat dan masing-masing memerlukan sumber daya manusia dengan keahlian khusus. Perubahan atau keterlambatan suatu kegiatan akan berpengaruh terhadap kegiatan lain. 2) Bersifat Dinamis Ciri khas proyek a) Kegiatan proyek tidak berulang. b) Pergantian dari satu kegiatan ke kegiatan yang lain berlangsung cepat. Keadaan yang dinamis dengan tingkat intensitas yang berbeda menuntut ketepatan perencanaan penyediaan sumber daya, dan sensitifitas sistem monitoring. Oleh karena proyek memiliki sifat yang spesifik seperti yang telah dijelaskan di atas, maka untuk menjamin keberhasilan penyelenggaraannya, dituntut penerapan manajemen yang khusus. Manajemen khusus tersebut sekarang telah menampilkan wujudnya tersendiri sebagai Manajemen Proyek. Manajemen proyek merupakan seni dan ilmu dalam mengkoordinasikan manusia, peralatan, material, uang dan jadwal untuk menyelesaikan suatu proyek tertentu tepat waktu dan dalam batas biaya yang disetujui (Garold D. Oberlender). Sehingga manajemen penyelenggaraan proyek dinilai berhasil jika sasaran proyek dapat dicapai: 1) Dengan mutu yang memenuhi persyaratan yang ditetapkan 2) Dalam batas biaya yang dianggarkan 3) Dalam kurun waktu yang ditentukan 4) Dengan penggunaan sumber daya yang efektif dan efisien. 2.2.1 Penjadwalan Sumber Daya Proyek Penjadwalan sumber daya proyek merupakan tahap yang sangat penting untuk menyelesaikan suatu proyek dengan sukses. Sumber daya adalah orang, peralatan dan material yang dapat diperoleh untuk memenuhi atau menyelesaikan sesuatu [4]. Didalam proyek, ketersediaan atau tidak tersedianya sumber daya akan sering mempengaruhi cara proyek dikelola. Tahap penjadwalan sumber daya proyek adalah sebagai berikut [5] : 1) Resource Definition 2) Resource Allocation 3) Resource Aggregation 4) Resource Leveling 2.2.2 Slack Slack merupakan waktu yang dapat digunakan untuk menggeser-geser kegiatan tanpa mempengaruhi waktu penyelesaian keseluruhan. Slack (S) dapat dimodelkan sebagai berikut : S = LFT – EST – d
(2.1)
LFT (Latest Finish Time) merupakan waktu paling akhir dimulainya suatu kegiatan, EST (Earliest Start Time) merupakan waktu paling awal dilaksanakannya suatu kegiatan, d merupakan durasi durasi dari kegiatan tersebut.
6
2.2.3 Resource Leveling Proses mengusahakan penjadwalan aktivitas agar menggunakan sumber daya secara merata sepanjang proyek disebut resource leveling (perataan sumber daya). Untuk mendapatkan grafik penjadwalan sumber daya yang baik, kita dapat mengatur atau menyesuaikan kembali jadwal kegiatan. Kegiatan yang berada pada jalur kritis jangan diganggu karena akan menyebabkan bertambahnya waktu akhir proyek. Penyesuaian hanya dilakukan pada kegiatan tidak kritis, itu pun dengan hanya memundurkan atau memajukan sesuai dengan slack. Slack itulah yang menentukan derajat fleksibilitas yang dapat dimanfaatkan perencana dalam usaha meratakan penggunaan sumber daya. Grafik Penjadwalan sumber daya yang baik dapat direpresentasikan dalam 4 macam grafik [12], yaitu: 1) Meningkat dari awal proyek. 2) Rata dari awal sampai akhir proyek. 3) Menurun dari awal proyek. 4) Semula meningkat pada awal proyek, kemudian turun sampai akhir proyek.
Gambar 2-1 Grafik-Grafik Ideal Sumber Daya
2.3 Algoritma Particle Swarm Optimization Algoritma particle swarm optimization pertama kali dikenalkan oleh Dr. Eberhart dan Dr. Kennedy ditahun 1995 dalam sebuah konferensi jaringan syaraf di Perth, Australia [9]. Algoritma particle swarm optimization merupakan teknik optimasi berbasis stochastic yang diinspirasi oleh tingkah laku sosial sekawanan burung atau sekumpulan ikan [8]. Algoritma particle swarm optimization mensimulasikan tingkah laku sosial sekawanan burung, berikut ini analoginya : Sekolompok burung secara random mencari makanan disuatu area. Diarea tersebut hanya ada sepotong makanan yang akan dicari. Seluruh burung tidak mengetahui dimana makanan tersebut. Tetapi mereka mengetahui jarak makanan tersebut disetiap iterasi. Jadi strategi apa yang terbaik untuk menemukan makanan
7
tersebut ? salah satu yang efektif yaitu mengikuti burung yang lebih dekat dengan makanan. Algoritma particle swarm optimization adalah metode pencarian yang didasarkan populasi dan merupakan algoritma optimasi global yang dihubungkan dengan masalah yang mana solusi terbaik dapat direpresentasikan sebagai titik atau surface diarea n-dimensional [7]. 2.3.1 Proses Algoritma Particle Swarm Optimization Proses algoritma particle swarm optimization yaitu sebagai berikut : 1) Inisialisasi sekumpulan particle secara random (setiap particle merepresentasikan solusi yang mungkin untuk masalah optimasi). 2) Inisialisasi posisi dari setiap particle (Xi) dan kecepatan dari setiap particle (Vi). 3) Hitung nilai fluktuasi dari setiap particle Fi berdasarkan formula dan model yang telah ditentukan sesuai dengan masalah optimasinya. 4) Untuk setiap particle, bandingkan nilai fluktuasi Fi dengan nilai terbaiknya yang telah dicapai Pid (local best), jika Fi < Pid , maka Pid diganti dengan Fi. 5) Untuk setiap particle, bandingkan nilai fluktuasi Fi dengan Nilai terbaik yang dicapai dalam populasi Pgd (global best), jika Fi < Pgd , maka Pgd diganti dengan Fi. 6) Berdasarkan persamaaan 4 dan 5 , kecepatan (Vi) dan posisi dari particle (Xi) diubah. Rumus perubahan kecepatan (Vi) : (2.2) Ilustrasinya sebagai berikut :
Gambar 2-2 Ilustrasi Perubahan Kecepatan
8
Rumus perubahan posisi (Xi) : (2.3) Ilustrasinya sebagai berikut :
Gambar 2-3 Ilustrasi Perubahan Posisi 7) Jika telah mencapai kondisi akhir (mencapai nilai iterasi maksimum atau perulangan telah mencapai nilai optimum) maka perulangan berhenti dan nilai optimumnya didapatkan namun jika belum maka diulangi pada nomor 3. 2.3.2 Parameter Algoritma Particle Swarm Optimization Adapun dua langkah utama ketika menerapkan algoritma particle swarm optimization pada masalah optimasi, yaitu : a) Representasi solusi b) Fungsi fitnessnya Tidak terlalu banyak parameter yang dibutuhkan pada algoritma particle swarm optimization, ini beberapa parameternya : a) Jumlah particle Rangenya 20 - 40. Sebenarnya dalam sebagian besar masalah 10 particle cukup besar untuk mendapatkan hasil yang bagus. Untuk masalah yang sangat sulit atau khusus, bagus untuk mencoba 100 atau 200 particle [8]. b) Dimensi dari particle Ini ditentukan dari masalah yang akan dioptimasi. c) Range dari particle Ini juga ditentukan dari masalah yang akan dioptimasi. Dapat menspesifikasikan range yang berbeda untuk dimensi yang berbeda dari particle.
9
d)
(faktor learning untuk particle), (faktor learning untuk swarm) dan biasanya sama yaitu 2. Tetapi biasanya dan berada diantara range [0, 4] [8]. e) Kondisi berhenti Mencapai nilai iterasi maksimum, perulangan telah mencapai nilai optimum atau minimum error yang diinginkan. f) Inertia weight (w) Di algoritma particle swarm optimization keseimbangan antara kemampuan eksplorasi global dan local secara utama di kontrol oleh inertia weight [17] dan merupakan parameter penurunan kecepatan untuk menghindari stagnasi particle di lokal optimum.
10
3. 3.1
Analisa dan Perancangan
Deskripsi Umum Sistem
Sistem yang akan dibangun pada tugas akhir ini adalah sistem optimasi penjadwalan sumber daya proyek. Aplikasi ini merupakan alat bantu untuk proses perataan sumber daya (resource leveling). Tujuan dari aplikasi ini adalah meminimalkan fluktuasi dengan batas waktu pengerjaan proyek tertentu. Jumlah sumber daya diasumsikan tidak terbatas.
3.2 Representasi Vektor Posisi Particle, Ruang Solusi dan Kecepatan Tujuan dari resource leveling yaitu untuk menemukan rencana jaringan, yang parameternya adalah waktu mulai (start time) yang membuat penggunaan sumber daya mencapai keadaan yang seimbang, yakni membuat nilai fluktuasi dari penggunaan sumber daya menjadi kecil. Untuk itu, posisi particle dapat dilihat sebagai waktu mulai dari seluruh aktivitas, dan ruang solusi adalah sekumpulan waktu mulai dari seluruh aktivitas. Particle swarm optimizaton diinisialisasi dengan populasi dari M particle secara random dan kemudian mencari posisi terbaik (solusi atau optimum) dengan mengupdate generasi sampai mencapai posisi yang mantap secara relatip atau mencapai batas iterasi maksimum (T). Di setiap iterasi atau generasi, local best dan global diputuskan melalui evaluasi nilai fluktuasi pada particle dipopulasi sekarang. Setiap particle diperlakukan sebagai titik di ruang N-dimensional dimana N merupakan jumlah aktivitas dari suatu proyek. Dua faktor yang menyatakan status particle di area pencarian yaitu posisi dan kecepatan. Posisi pada N-dimensional untuk i particle pada t generasi (disebut iterasi) dapat ditunjukkan sebagai berikut : .
(3.1)
Sama juga untuk kecepatan (perubahan jarak) pada vektor N-dimensional untuk i particle pada t generasi dapat ditunjukkan sebagai berikut : (3.2) Proses ini (3.3) (3.4) Dapat merepresentasikan pengupdatean dari status particle dipopulasi dari pertama sampai generasi terakhir selama proses pencarian. Persamaan (3.3) untuk menghitung kecepatan yang baru dari particle berdasarkan kecepatan sebelumnya dan jarak posisi sekarang dari posisi atau nilai terbaiknya sendiri (local best) dan dari posisi atau nilai terbaik seluruhnya (global
11
best) kemudian particle terbang menuju posisi yang baru berdasarkan persamaan (3.4). Particle hanya mengeksplorasi Start Time yang feasible, yaitu diantara Earliest Start Time (EST) dan Latest Start Time (LST) aktivitas tersebut, yang berarti particle tidak boleh terbang melebihi LST. Dimana : • Jumlah Particle • Jumlah Iterasi • N = Jumlah aktivitas • merepresentasikan local best (solusi atau posisi) dari i particle yang dihubungkan dengan nilai fluktuasi terbaik setelah iterasi t-1. • • • •
3.3
merepresentasikan global best yang dicapai sejauh ini dari seluruh populasi. dan adalah konstanta positif (disebut dengan learning factor). adalah angka random antara nilai 0 dan 1. w(t) adalah inertia weight = digunakan untuk mengontrol pengaruh kecepatan sebelumnya dikecepatan sekarang, mempengaruhi trade-off kemampuan exploration (menjelajahi) local dan global selama proses pencarian.
Fungsi Fluktuasi
Kebutuhan sumber daya yang diharapkan pada setiap harinya adalah konstan sepanjang berjalannya proyek. Sebagai contoh, apabila jenis sumber daya adalah pekerja, biaya untuk memperkerjakan atau memberhentikan akan cukup signifikan. Penulis menggunakan definisi fluktuasi yang digunakan oleh Szendroi [21]. Yaitu bahwa grafik yang berfluktuasi adalah grafik yang tidak quasi concave. Perbedaan antara grafik yang quasi concave dan yang tidak ditunjukkan pada gambar di bawah ini : Ut 5 4 3 2 1 1
2
3
4
5
6
7
8
9
t
Gambar 3-1 Grafik yang tidak quasi concave
12
Ut 5 4 3 2 1 1
2
3
4
5
6
7
8
9
10
t
Gambar 3-2 Grafik yang quasi concave Sebuah grafik dikatakan quasi-concave apabila nilai t0 (level puncak), untuk setiap nilai t < t0, nilai Ut tidak pernah menurun, sedangkan untuk setiap t > t0, nilai Ut tidak pernah menaik. Maka fluktuasi pada grafik sumber daya proyek adalah sejumlah sumber daya yang tidak digunakan setiap waktunya. Hal tersebut seperti ditunjukkan pada gambar di bawah ini:
Gambar 3-3 Grafik dengan Sejumlah Sumber Daya yang Tidak Digunakan Namun, dengan informasi quasi concave saja tidak cukup untuk mendapatkan grafik yang paling optimal. Sehingga penulis juga menambahkan informasi level puncak kebutuhan sumber daya. Hal lain yang perlu diperhatikan adalah jika suatu proyek membutuhkan lebih dari satu jenis sumber daya, maka fluktuasi merupakan penjumlahannya. Sehingga fungsi fluktuasi adalah akumulasi dari pemborosan sumber daya dan level puncak kebutuhan sumber daya, yang dapat dirumuskan sebagai berikut: (3.5)
13
dimana R adalah himpunan jenis sumber daya, T adalah batas waktu pengerjaan proyek, x adalah sumber daya yang quasi concave dan y adalah kebutuhan sumber adalah pemborosan sumber daya sesuai yang telah dijadwalkan. Maka adalah level puncak kebutuhan sumber daya. daya, dan
3.4
Analisa Kebutuhan Sistem
3.4.1 Spesifikasi Perangkat Keras Berikut adalah spesifikasi kebutuhan perangkat keras sistem: a. Processor P-IV 1.83 GHz b. RAM 256 c. Hard disk 20 GB 3.4.2 Spesifikasi Perangkat Lunak Berikut adalah spesifikasi kebutuhan perangkat lunak sistem: a. Sistem Operasi Windows XP b. NetBeans 5.5 c. JDK 1.6 d. MySQL e. Rational Rose 2000
3.5
Perancangan
3.5.1 Struktur Tabel Basis Data Diagram basis data aplikasi ini dapat digambarkan sebagai berikut:
Gambar 3-4 Diagram Basis Data
14
3.5.2
Gambaran Keseluruhan Sistem
Gambar 3-5 Gambaran Keseluruhan Sistem Optimasi Penjadwalan Sumber Daya Proyek
15
3.5.3
Diagram Use case
<< include >> Load Project << include >>
User
PSO Optimization Set PSO's Parameters
Gambar 3-6 Diagram Use Case Use Case ini digunakan oleh user untuk memasukkan data inputan ke dalam sistem dan melihat hasil optimasi yang dilakukan oleh sistem. Semua user bisa masuk ke dalam sistem tanpa adanya hak akses yang khusus. Use Case Deskripsi
: :
PSO Optimization User memulai proses PSO dimana jalannya proses ini ditentukan oleh parameter masukan yang diinputkan user. Respon sistem disini melakukan inisialisasi posisi dan kecepatan particle, menghitung fluktuasi dari solusi dan mengupdate posisi dan kecepatan particle sampai kondisi berhenti ditemukan. Kemudian menampilkan grafik sumber daya proyek setelah dioptimasi.
Use Case Deskripsi
: :
Load Project Sistem melakukan perhitungan Earlies Start Time, Latest Start Time, Earliest Finish Time, Latest Finish Time, Slack dan Critis Time proyek yang bersangkutan. Kemudian menampilkan grafik sumber daya proyek sebelum dioptimasi.
Use Case Deskripsi
: :
Set PSO’s Parameters User memasukkan parameter-parameter PSO yang dibutuhkan untuk melakukan optimasi dengan PSO.
16
3.5.4 Diagram Sekuensial : PSO Optimization
: (FormUtama)
: Project
: Partikel
: PartikelManager
: (User)
BtnOptimize( )
Project( ) isiListActivity( )
setPredesesorActivity( ) setEarliest( ) setCritisTime( ) setLastest( ) setSlack( ) getListActivity( )
Partikel( )
PartikelManager( ) setListPartikel( ) evaluasiFitness( )
getGlobalBestPart( ) getGlobalBestFitness( ) getTotalWaktu( ) Chart( ) setProj( ) HitungFitnessAwal( )
Gambar 3-7 Diagram Sekuensial: PSO Optimization Setelah user memasukkan parameter PSO dan sistem menghitung Critis Time, user dapat menggunakan sistem untuk menghasilkan penjadwalan sumber daya proyek yang baik. Operasi-operasi yang ada dalam use case ini adalah: • • • • •
BtnOptimize : berfungsi untuk menangani event disaat user menekan tombol Optimize. Project : berfungsi sebagai constructor. isiListActivity : berfungsi untuk mengisi data ke constructor Activity. setPredesesorActivity : berfungsi untuk mengolah data yang ada dari basis data menjadi data predesesor dan successor pada kelas Activity. setEarliest : berfungsi untuk memperoleh nilai Earliest Start Time dan Earliest Finish Time setiap aktivitas.
17
• • • • • • • • • • • • • •
setCritisTime : berfungsi untuk memperoleh nilai Earliest Finish Time yang paling maksimum yang sebenarnya merupakan nilai Critis Time proyek tersebut. setLastest : berfungsi untuk memperoleh nilai Latest Start Time dan Latest Finish Time setiap aktivitas. setSlack : berfungsi untuk memperoleh nilai slack setiap aktivitas. getListActivity : berfungsi untuk memperoleh himpunan aktivitas. Partikel : berfungsi sebagai constructor. PartikelManager : berfungsi sebagai constructor untuk menentukan nilai parameter-parameter yang dibutuhkan PartikelManager untuk melakukan optimasi. setListPartikel : berfungsi untuk mengeset himpunan particle yang akan melakukan optimasi. evaluasiFitness : berfungsi untuk mendapatkan posisi terbaik dengan melakukan pengupdatean posisi dan kecepatan dari setiap particle disetiap iterasi. getGlobalBestFitness : berfungsi untuk mendapatkan nilai fluktuasi yang terbaik. getGlobalBestPart : berfungsi untuk mendapatkan posisi terbaik (start time terbaik). getTotalWaktu : berfungsi untuk mendapatkan waktu proses sistem yang diperlukan oleh algoritma PSO untuk menemukan solusi. Chart : berfungsi untuk menampilkan grafik sumber daya proyek setelah dioptimasi. setProj : berfungsi untuk memperoleh himpunan aktivitas. HitungFitnessAwal : berfungsi untuk mendapatkan nilai fluktuasi sumber daya proyek sebelum dioptimasi.
3.5.5 Diagram Sekuensial : Set PSO’s Parameters
: FormUtama
: PartikelManager
: User
BtnOptimize( ) PartikelManager( )
Gambar 3-8 Diagram Sekuensial: Set PSO’s Parameters
18
User dapat memasukkan parameter-parameter ACO melalui antarmuka yang disediakan. Operasi yang ada dalam use case ini adalah: • •
BtnOptimize() : berfungsi untuk menangani event disaat user menekan tombol Optimize. PartikelManager(): berfungsi untuk menentukan nilai parameterparameter yang dibutuhkan PartikelManager untuk melakukan optimasi.
3.5.6 Diagram Sekuensial : Load Project
: (User)
: (FormUtama)
BtnOpen( )
: Project
: Activity
: Partikel
Project( ) isiListActivity( )
setPredesesorActivity( ) setEarliest( )
addActPredesesor( ) addActSuksesor( )
setCritisTime( ) setLastest( ) setSlack( ) getListActivity( ) Partikel( ) setProj( ) ChartSebelumOptimasi( )
Gambar 3-9 Diagram Sekuensial: Load Data Sistem melakukan perhitungan untuk mendapatkan Critis Time, kemudian menampilkan grafik sumber daya sebelum dioptimasi. Operasi-operasi yang ada dalam use case ini adalah: • • • •
BtnOpen(): berfungsi untuk menangani suatu event disaat user menekan tombol Open. Project : berfungsi sebagai constructor. SetPredesesorActivity(): berfungsi untuk mengolah data yang ada dari basis data menjadi data predesesor dan successor pada kelas Activity. isiListActivity : berfungsi untuk mengisi data ke constructor Activity.
19
• • • • • • • • • •
addActPredesesor(): berfungsi untuk menambah predecessor aktivitas. addActSuksesor(): berfungsi untuk menambah successor aktivitas. setEarliest(): berfungsi untuk memperoleh nilai Earliest Start Time dan Earliest Finish Time setiap aktivitas. setCritisTime(): berfungsi untuk memperoleh nilai Earliest Finish Time yang paling maksimum yang sebenarnya merupakan nilai Critis Time proyek tersebut. setLastest(): berfungsi untuk memperoleh nilai Latest Start Time dan Latest Finish Time setiap aktivitas. setSlack : berfungsi untuk memperoleh nilai slack setiap aktivitas. getListActivity : berfungsi untuk memperoleh himpunan aktivitas. Partikel : berfungsi sebagai constructor. setProj : berfungsi untuk memperoleh himpunan aktivitas. ChartSebelumOptimasi : berfungsi untuk menampilkan grafik sumber daya proyek sebelum dioptimasi.
3.5.7 Diagram Kelas Diagram kelas untuk sistem yang melakukan optimasi penjadwalan sumber daya proyek dengan algoritma particle swarm optimization ini adalah :
20
Activity
Project IDProject : Integer name : String time : String critisTime : Integer listActivity : Activity Project() isiListActivity() 1 setPredesesorActivity() setEarliest() setCritisTime() setLastest() setSlack() getListActivity()
idActivity : Integer name : String description : String duration : Integer EST : Integer LST : Integer EFT : ineteger LFT : Integer slack : Integer predecessor : String actPredesesor : Activity 1..* actSuksesor : Activity resource : Resource posisi : Double kecepatan : Double idProject : Integer
Resource
1
0..*
name : String idResource : String units : Integer label : String type : String Resource()
addActPredesesor() addActSuksesor() Activity() 1..*
PartikelManager numPartikel : Integer numTrial : Integer weight : Double c1 : Double c2 : Double listPart : Partikel wmin : Double totalwaktu : Long globalBestFitness : Double globalBestPart : Partikel 1 PartikelManager() evaluasiFitness() setListPartikel() getGlobalBestFitness() getGlobalBestPart() getTotalWaktu()
1 Partikel proj : Project listActivity : Activity lbest : Double fitness : Double critisTime : Integer HitungFitness()
1..* inisialisasiXV() Partikel() setProj() Chart() ChartSebelumOptimasi() HitungFitnessAwal()
Gambar 3-10 Diagram Kelas •
Kelas Project Kelas ini merupakan proyek yang akan dioptimasi oleh PSO. Kelas Project memiliki atribut : - IDProject : ID suatu proyek. - name : nama suatu proyek. - time : representasi waktu suatu aktivitas. - critisTime : waktu minimal untuk dapat menyelesaikan suatu proyek. - listActivity : himpunan aktivitas.
21
Kelas Project memiliki operasi : - Project : berfungsi sebagai constructor. - isiListActivity : berfungsi untuk mengisi data ke constructor Activity. - setPredesesorActivity : berfungsi untuk mengolah data yang ada dari basis data menjadi data predesesor dan successor pada kelas Activity. - setEarliest : berfungsi untuk memperoleh nilai Earliest Start Time dan Earliest Finish Time setiap aktivitas. - setCritisTime : berfungsi untuk memperoleh nilai Earliest Finish Time yang paling maksimum yang sebenarnya merupakan nilai Critis Time proyek tersebut. - setLastest : berfungsi untuk memperoleh nilai Latest Start Time dan Latest Finish Time setiap aktivitas. - setSlack : berfungsi untuk memperoleh nilai slack setiap aktivitas. - getListActivity : berfungsi untuk memperoleh himpunan aktivitas. •
Kelas Activity Kelas ini merupakan aktivitas dari proyek yang bersangkutan. Kelas Activity memiliki atribut : - idProject : ID suatu proyek. - idActivity : ID suatu aktivitas. - name : nama suatu aktivitas. - description: deskripsi kegiatan suatu aktivitas. - duration: waktu yang dibutuhkan untuk menyelesaikan suatu aktivitas. - EST : waktu paling awal dimulainya suatu aktivitas. - EFT : waktu paling awal diselesaikannya suatu aktivitas. - LST : waktu paling akhir dimulainya suatu aktivitas. - LFT : waktu paling akhir diselesaikannya suatu aktivitas. - slack : jumlah waktu yang diperkenankan suatu aktivitas boleh ditunda, tanpa mempengaruhi jadwal penyelesaian proyek secara keseluruhan. - resource : sumber daya yang dibutuhkan aktivitas. - posisi : waktu mulai (start time) dari seluruh aktivitas. - kecepatan : nilai perubahan jarak dari seluruh aktivitas untuk mendapatkan posisi baru. - actPredesesor, predecessor : suatu aktivitas yang harus dimulai dan selesai sebelum aktivitas yang bersangkutan dimulai. - actSuksesor : suatu aktivitas yang baru dapat dimulai setelah aktivitas yang bersangkutan diselesaikan. Kelas Activity memiliki operasi : - addActPredesesor : berfungsi untuk menambah predecessor aktivitas. - addActSuksesor : berfungsi untuk menambah successor aktivitas. - Activity : berfungsi sebagai constructor.
22
•
Kelas Resource Kelas ini merupakan sumber daya yang digunakan oleh setiap aktivitas. Kelas Resource memiliki atribut : - idResource : ID sumber daya. - name : nama sumber daya. - label : label sumber daya. - type : tipe sumber daya. - units : jumlah sumber daya yang dibutuhkan. Kelas Resource memiliki operasi : - Resource : berfungsi sebagai constructor.
•
Kelas PartikelManager Kelas ini merupakan pengatur particle dalam melakukan pencarian solusi. Kelas PartikelManager memiliki atribut : - numPartikel : jumlah particle. - numTrial : jumlah iterasi maksimum. - weight : parameter penurunan kecepatan untuk menghindari stagnasi particle di lokal optimum. - C1 : faktor learning untuk particle. - C2 : faktor learning untuk swarm. - listPart : himpunan particle yang akan melakukan optimasi. - wmin : nilai minimum inertia weight. - totalwaktu : waktu proses sistem. - globalBestPart : posisi terbaik (start time terbaik). - globalBestFitness : nilai fluktuasi yang terbaik. Kelas PartikelManager memiliki operasi : - PartikelManager : berfungsi sebagai constructor untuk menentukan nilai parameter-parameter yang dibutuhkan PartikelManager untuk melakukan optimasi. - evaluasiFitness : berfungsi untuk mendapatkan posisi terbaik dengan melakukan pengupdatean posisi dan kecepatan dari setiap particle disetiap iterasi. - setListPartikel : berfungsi untuk mengeset himpunan particle yang akan melakukan optimasi. - getGlobalBestFitness : berfungsi untuk mendapatkan nilai fluktuasi yang terbaik. - getGlobalBestPart : berfungsi untuk mendapatkan posisi terbaik (start time terbaik). - getTotalWaktu : berfungsi untuk mendapatkan waktu proses sistem yang diperlukan oleh algoritma PSO untuk menemukan solusi.
•
Kelas Partikel Kelas ini merupakan particle yang mengkonstruksi solusi atau dalam hal ini penjadwalan sumber daya proyek. Kelas Partikel memiliki atribut : - proj : himpunan proyek. - listActivity : himpunan aktivitas.
23
Kelas -
lbest : nilai fluktuasi terbaik yang dimiliki oleh setiap particle pada setiap iterasi. fitness : nilai fluktuasi dari solusi yang dimiliki oleh setiap particle, merepresentasikan baik atau buruknya suatu solusi. critisTime : waktu minimal untuk dapat menyelesaikan suatu proyek. Partikel memiliki operasi : Partikel : berfungsi sebagai constructor. inisialisasiXV : berfungsi untuk inisialisasi nilai posisi dan kecepatan setiap particle diawal. HitungFitness : berfungsi untuk menghitung tingkat fluktuasi dari solusi yang dihasilkan oleh particle. setProj : berfungsi untuk memperoleh himpunan aktivitas. Chart : berfungsi untuk menampilkan grafik sumber daya proyek setelah dioptimasi. ChartSebelumOptimasi : berfungsi untuk menampilkan grafik sumber daya proyek sebelum dioptimasi. HitungFitnessAwal : berfungsi untuk mendapatkan nilai fluktuasi sumber daya proyek sebelum dioptimasi.
24
4.
Analisis Hasil Percobaan
4.1 Pengujian Sistem Pada bab ini dilakukan pengukuran kinerja dari sistem optimasi penjadwalan sumber daya proyek yang telah diimplementasikan. Tetapi sebelumnya didefinisikan tujuan pengujian, skenario pengujian, parameter yang dibutuhkan dalam pengujian ini, dan kasus uji yang digunakan. Setelah menjalankan pengujian, hasil pengujian dianalisis untuk menentukan parameterparameter yang berpengaruh terhadap algoritma particle swarm optimization sebagai proses optimasi penjadwalan penjadwalan sumber daya proyek. 4.1.1 Tujuan Pengujian Berikut adalah tujuan dari pengujian yang dilakukan : 1. Menganalisis parameter algoritma particle swarm optimization yaitu C1 (faktor learning untuk particle), C2 (faktor learning untuk swarm) dan inertia weight (parameter penurunan kecepatan untuk menghindari stagnasi particle di lokal optimum) 2. Menganalisis hasil optimasi penjadwalan sumber daya proyek untuk setiap kasus uji. 3. Menganalisis perbandingan hasil optimasi antara Algoritma Rank Based Ant System (ASrank) dengan algoritma particle swarm optimization untuk setiap kasus uji. 4.1.2 Skenario Pengujian Berikut adalah skenario dari pengujian yang dilakukan : 1. Skenario pengujian parameter algoritma particle swarm optimization Parameter-Parameter yang digunakan yaitu : ¾ m : jumlah particle dan nc : jumlah iterasi maksimum Nilai m dan nc yang diuji-cobakan adalah { 60, 1000 } dan { 100, 600 } ¾ C1 : faktor learning untuk particle Nilai C1 yang diuji-cobakan adalah C1 = { 0.5, 1, 1.5, 2, 4 } ¾ C2 : faktor learning untuk swarm Nilai C2 yang diuji-cobakan adalah C2 = { 0.5, 1, 1.5, 2, 4 } ¾ W (inertia weight) : parameter penurunan kecepatan untuk menghindari stagnasi particle di lokal optimum Nilai W yang diuji-cobakan adalah W = { 1.2, 1.1, 1, 0.9, 0.8 } Pengujian dilakukan dengan melihat kombinasi antara : ¾ Jumlah particle dan jumlah iterasi maksimum { 60, 1000 } dengan nilai C1, C2 dan W sehingga didapat 125 kombinasi ¾ Jumlah particle dan jumlah iterasi maksimum { 100, 600 } dengan nilai C1, C2 dan W sehingga didapat 125 kombinasi Nilai kombinasi dapat dilihat dilampiran A. 2. Skenario pengujian optimasi penjadwalan sumber daya proyek untuk setiap kasus uji Berdasarkan skenario pengujian pertama, maka didapat parameter terbaik untuk nilai m, nc, C1, C2 dan W dimana nilai tersebut digunakan untuk melakukan optimasi penjadwalan sumber daya proyek untuk setiap kasus uji.
25
Kemudian dilihat nilai fluktuasinya baik sebelum optimasi maupun sesudah optimasi. 3. Skenario pengujian perbandingan hasil optimasi antara Algoritma Rank Based Ant System (ASrank) dengan algoritma particle swarm optimization Membandingkan nilai fluktuasi sesudah optimasi antara Algoritma Rank Based Ant System (ASrank) dengan algoritma particle swarm optimization untuk setiap kasus uji. 4.1.3 Parameter Pengujian Pengamatan dan pencatatan perubahan ditujukan pada: 1. Tingkat Fluktuasi Merupakan nilai fluktuasi yang terjadi pada jadwal sumber daya yang dihasilkan. Semakin tinggi nilainya, maka semakin buruk solusi yang dihasilkan. Pada tabel-tabel percobaan berikut, rata-rata tingkat fluktuasi disebut dengan Fluct. 4.1.4 Kasus Uji yang Digunakan Kasus-kasus uji yang digunakan untuk melakukan percobaan adalah sebagai berikut: 1. Proyek Qureshi [16] Kasus ini memiliki 11 aktivitas dan 2 jenis sumber daya. Dari 11 aktivitas, 3 aktivitas merupakan aktivitas yang berada pada jalur kritis, berarti ada 8 aktivitas yang memiliki slack. Batas waktu pengerjaan proyek ini adalah 15 minggu. 2. Proyek LOGON [14] Kasus ini memiliki 19 aktivitas dan 1 jenis sumber daya. Dari 19 aktivitas, 8 aktivitas merupakan aktivitas yang berada pada jalur kritis, berarti ada 11 aktivitas yang memiliki slack. Batas waktu pengerjaan proyek ini adalah 47 minggu. 3. Proyek Building [20] Kasus ini memiliki 36 aktivitas dan 5 jenis sumber daya. Dari 36 aktivitas, 12 aktivitas merupakan aktivitas yang berada pada jalur kritis, berarti ada 24 aktivitas yang memiliki slack. Batas waktu pengerjaan proyek ini adalah 205 hari.
4.2 Pelaksanaan Uji Coba terhadap Parameter Algoritma PSO Untuk melihat kelakuan sistem akibat perubahan setiap parameter, maka uji coba dilakukan dengan mengubah-ubah parameter sistem. Setiap uji coba dilakukan dengan 30 kali pengulangan dan mengambil nilai rata-rata dari seluruh percobaan tersebut. Hasil pengujian terhadap parameter algoritma PSO dapat dilihat dari grafik dibawah ini :
26
Gambar 4-1 Grafik Pengujian Parameter Tabel 4-1 Nilai Fluct untuk m=60 dan nc=1000 Kombinasi 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
Fluct 36.07 32.93 31.03 30.40 33.03 37.23 34.33 35.90 36.33 36.67 34.23 38.57 38.17 39.00 39.00 39.77 40.27 41.90 39.43 43.43 41.43 42.80 47.03 44.73 45.93 31.40 29.40 28.63
Kombinasi 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
Fluct 30.33 32.83 30.63 33.70 32.63 34.90 35.03 33.77 35.37 35.10 35.23 36.20 38.57 37.90 38.20 41.53 41.57 45.53 29.13 28.27 27.93 28.43 28.37 30.03 29.83 29.33 29.53 29.33
Kombinasi 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
Fluct 31.27 32.93 33.33 32.27 32.00 33.17 35.23 37.83 37.73 39.33 39.83 28.20 27.27 27.83 28.20 27.73 29.33 28.47 29.43 28.83 28.73 30.47 30.00 29.37 30.30 30.47 31.97 32.47
Kombinasi 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
Fluct 34.77 36.33 36.53 36.00 37.70 27.53 27.40 27.93 27.50 28.10 28.10 28.43 28.23 28.33 28.40 29.13 28.83 28.80 28.73 29.63 30.30 29.30 29.87 29.57 29.53 33.53 31.97 32.27
27
29 30 31 32
28.83 29.67 32.60 31.50
61 62 63 64
31.17 32.03 31.40 31.77
93 94 95
31.10 31.47 31.77
124 125
33.67 34.77
Kombinasi 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
Fluct 31.90 32.83 34.57 34.33 36.10 27.70 27.57 27.67 27.77 28.07 27.93 27.83 28.30 28.47 28.23 28.70 28.60 28.43 28.63 28.90 28.97 28.70 29.20 28.50 28.73 31.67 31.90 32.60 32.83 32.23
Tabel 4-2 Nilai Fluct untuk m=100 dan nc=600 Kombinasi 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Fluct 35.23 30.73 30.70 30.93 31.50 34.80 34.53 32.33 32.67 35.00 35.73 36.67 37.30 40.03 38.07 37.63 37.67 37.77 40.47 40.53 43.80 43.40 42.73 42.40 44.37 31.57 29.40 29.13 28.07 29.13 30.83 29.83
Kombinasi 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
Fluct 29.73 30.07 31.53 32.37 31.73 31.90 34.03 32.33 35.37 33.40 31.70 34.50 35.77 37.00 36.50 38.03 39.20 41.30 28.60 28.23 28.00 28.27 28.00 29.37 29.17 29.13 29.03 29.43 30.43 29.50 30.47 30.10
Kombinasi 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
Fluct 30.80 31.70 31.07 32.70 31.27 32.20 35.57 34.37 36.17 39.97 36.20 28.03 27.83 27.27 27.67 28.30 28.73 29.03 29.07 29.03 28.83 30.33 29.03 28.63 29.30 28.97 30.10 29.70 30.50 30.83 31.03
Berdasarkan hasil pengujian untuk m=60 dan nc=1000 didapat parameter C1, C2 dan W yaitu { 2, 0.5, 0.9 } dengan nilai fluct 27.27 sedangkan hasil pengujian untuk m=100 dan nc=600 didapat parameter C1, C2 dan W yaitu { 2, 0.5, 1 } dengan nilai fluct 27.27. C1 dan C2 merupakan faktor learning yang menyatakan seberapa besar particle itu dihubungkan kearah solusi yang potensial dari ruang solusi. C1 (cognitive) dan C2 (swarm) itu mempengaruhi seberapa besar personal best (local best) particle dan global best tersebut mempengaruhi perpindahan particle tersebut.
28
Inertia weight digunakan untuk mengontrol pengaruh kecepatan sebelumnya dikecepatan sekarang dan menjaga keseimbangan antara kemampuan eksplorasi global dan local selama proses pencarian serta merupakan parameter penurunan kecepatan untuk menghindari stagnasi particle di lokal optimum. Bila nilai inertia weight terlalu besar maka sistem akan selalu mengeksplorasi area baru dan konsekuensinya kemampuan untuk mengeksplorasi nilai local semakin berkurang sehingga gagal untuk menemukan solusi dan bila nilai inertia weight terlalu kecil maka bisa terjebak dilocal optimum. Berdasarkan hasil pengujian nilai inertia weight yang digunakan dalam percobaan ini dimulai dengan nilai yang besar yaitu { 1, 0.9 } untuk mengeksplor nilai global kemudian secara dinamis menurun sampai kenilai inertia weight minimum yaitu 0.4 untuk mengeksplor nilai local selama proses optimasi. Bila nilai C1 dan C2 besar maka akan mempercepat ke solusi yang potensial tetapi kekurangannya adalah bisa terjebak dilokal optimum sedangkan bila diset rendah maka akan berputar-putar diarea solusi potensial dan secara lambat akan mencapai solusi yang potensial tersebut. Berdasarkan hasil pengujian nilai C1 = 2 dan C2 = 0.5 yang berarti mempercepat kearah konvergen dan mengurangi local optimum. Dalam hal ini, lebih baik memilih nilai C1 lebih besar daripada nilai C2 [1].
4.3 Analisis Hasil Optimasi Penjadwalan Sumber Daya Proyek Pada sub bab ini akan dibahas mengenai hasil optimasi pada setiap kasus studi untuk membuktikan apakah algoritma particle swarm optimization yang digunakan benar-benar memberikan solusi yang optimal. Setiap studi kasus diuji kembali dengan parameter terbaik yang diperoleh dari hasil analisa sub bab sebelumnya. 4.3.1 Proyek Qureshi
Gambar 4-2 Grafik Sumber Daya Proyek Qureshi Sebelum Dioptimasi dengan Start Time=EST
29
Tabel 4-3 Parameter terbaik untuk Proyek LOGON m 60
nc 1000
c1 2
c2 0.5
w 0.9
Dari parameter yang didapat untuk proyek LOGON diatas maka diterapkan untuk proyek Qureshi, dari 30 kali percobaan, algoritma PSO selalu menemukan solusi paling optimal, yaitu penjadwalan sumber daya proyek Qureshi dengan fluktuasi 19. Grafik sumber daya setelah dioptimasi ditunjukkan seperti di bawah ini :
Gambar 4-3 Grafik Sumber Daya Proyek Qureshi Setelah Dioptimasi Tabel 4-4 Perbandingan Grafik Sumber Daya Proyek Qureshi Level Puncak Pemborosan Fluktuasi
Start Time=EST 14 dan 8 16 38
Setelah dioptimasi 9 dan 6 4 19
30
4.3.2 Proyek LOGON
Gambar 4-4 Grafik Sumber Daya Proyek LOGON Sebelum Dioptimasi dengan Start Time=EST Tabel 4-5 Parameter terbaik untuk Proyek LOGON m 60
nc 1000
c1 2
c2 0.5
w 0.9
Dengan parameter di atas, dari 30 kali percobaan, algoritma PSO selalu menemukan solusi paling optimal, yaitu penjadwalan sumber daya proyek LOGON dengan fluktuasi 26. Grafik sumber daya setelah dioptimasi ditunjukkan seperti di bawah ini :
31
Gambar 4-5 Grafik Sumber Daya Proyek LOGON Setelah Dioptimasi Tabel 4-6 Perbandingan Grafik Sumber Daya Proyek LOGON Level Puncak Pemborosan Fluktuasi
Start Time=EST 23 81 104
Setelah dioptimasi 17 9 26
4.3.3 Proyek Building
Gambar 4-6 Grafik Sumber Daya Proyek Building Sebelum Dioptimasi dengan Start Time=EST
32
Tabel 4-7 Parameter terbaik untuk Proyek LOGON m 60
nc 1000
c1 2
c2 0.5
w 0.9
Dari parameter yang didapat untuk proyek LOGON diatas maka diterapkan untuk proyek Building, dari 30 kali percobaan, algoritma PSO selalu menemukan solusi paling optimal, yaitu penjadwalan sumber daya proyek Building dengan fluktuasi 7705. Grafik sumber daya setelah dioptimasi ditunjukkan seperti di bawah ini :
Gambar 4-7 Grafik Sumber Daya Proyek Building Setelah Dioptimasi Tabel 4-8 Perbandingan Grafik Sumber Daya Proyek Building Level Puncak Pemborosan Fluktuasi
Start Time=EST 75, 60, 60, 175, dan 125 18425 18920
Setelah dioptimasi 75, 60, 60, 160, dan 125 7225 7705
Dengan demikian dapat dilihat dari data-data pengujian di atas bahwa algoritma ini dapat menghasilkan solusi yang baik, yaitu meminimalkan fluktuasi. Untuk proyek Qureshi fluktuasi berkurang hingga 50%, untuk proyek LOGON fluktuasi berkurang hingga 75%, dan untuk proyek Building fluktuasi berkurang hingga 59.3%. Dengan meminimalkan fluktuasi, grafik sumber daya memiliki level puncak yang lebih kecil dan pemborosannya bisa dikurangi.
33
4.4 Perbandingan dengan Algoritma Rank Based Ant System (ASrank) 4.4.1 Proyek Qureshi
Gambar 4-8 Grafik Sumber Daya Proyek Qureshi Setelah Dioptimasi dengan Algoritma Rank Based Ant System (ASrank)
Tabel 4-9 Perbandingan Grafik Sumber Daya Proyek Qureshi Setelah Dioptimasi Antara Algoritma ASrank dan Algoritma PSO Level Puncak Pemborosan Fluktuasi
Algoritma ASrank 9 dan 6 10 25
Algoritma PSO 9 dan 6 4 19
34
4.4.2 Proyek LOGON
Gambar 4-9 Grafik Sumber Daya Proyek LOGON Setelah Dioptimasi dengan Algoritma Rank Based Ant System (ASrank) Tabel 4-10 Perbandingan Grafik Sumber Daya Proyek LOGON Setelah Dioptimasi Antara Algoritma ASrank dan Algoritma PSO Level Puncak Pemborosan Fluktuasi
Algoritma ASrank 17 9 26
Algoritma PSO 17 9 26
4.4.3 Proyek Building
Gambar 4-10 Grafik Sumber Daya Proyek Building Setelah Dioptimasi dengan Algoritma Rank Based Ant System (ASrank)
35
Tabel 4-11 Perbandingan Grafik Sumber Daya Proyek Building Setelah Dioptimasi Antara Algoritma ASrank dan Algoritma PSO Level Puncak Pemborosan Fluktuasi
Algoritma ASrank 130, 160, 60, 75 dan 60 7800 8285
Algoritma PSO 75, 60, 60, 160, dan 125 7225 7705
Berdasarkan ketiga proyek diatas, hanya proyek LOGON yang memiliki nilai fluktuasi yang sama antara algoritma ASrank dan algoritma PSO. Sedangkan, untuk proyek Qureshi dan Building algoritma PSO memiliki nilai fluktuasi yang lebih kecil bila dibandingkan dengan algoritma ASrank. Jadi, algoritma Particle Swarm Optimization (PSO) menghasilkan solusi yang paling optimal bila dibandingkan dengan algoritma Rank Based Ant System (ASrank) karena algoritma PSO memiliki memori sendiri untuk menyimpan nilai local best dan global best dimana hal ini penting dalam pengupdatean posisi sedangkan di algoritma Rank Based Ant System (ASrank) mengurutkan semut berdasarkan tingkat fluktuasi solusi yang telah mereka temukan sebelumnya. Saat melakukan update pheromone hanya (w-1) semut terbaik dan semut yang memiliki best-so-far solusi yang diperbolehkan meninggalkan pheromone. Jadi, hal tersebut bisa membuat node-node yang sebenarnya tidak terbaik menjadi lebih baik karena telah dikunjungi oleh ant yang terbaik yang berarti terjebak kedalam local optimum.
4.5 Hasil Re-Optimize Setelah dilakukan optimasi kembali dengan inputan hasil optimasi yang terdapat pada sub bab 4.3 untuk semua kasus uji dan dilakukan selama 30 kali percobaan hasilnya menunjukkan bahwa nilai optimasi yang didapat tetap seperti pada sub bab 4.3 yaitu : Qureshi (nilai fluktuasi) = 19, LOGON (nilai fluktuasi) = 26, Building (nilai fluktuasi) = 7705. Hal ini menunjukkan bahwa setelah dilakukan optimasi kembali nilai tersebut paling optimal. Dengan demikian, algoritma particle swarm optimization (PSO) mampu menghasilkan solusi yang optimal dikarenakan algoritma ini dapat menyeimbangkan antara eksploitasi dan eksplorasi. Eksploitasi yang dimaksud adalah pencarian solusi selanjutnya dilakukan pada ruang solusi terbaik yang sebelumnya sudah ditemukan. Sedangkan eksplorasi adalah mencari pada ruang solusi yang belum tersentuh.
36
5.
Kesimpulan dan Saran
5.1 Kesimpulan Kesimpulan yang dapat diambil dari Tugas Akhir ini adalah : 1. Dari hasil pengujian terhadap setiap proyek yang menjadi kasus uji, seperti dijabarkan pada sub bab 4.3, dapat disimpulkan bahwa algoritma Particle Swarm Optimization (PSO) dapat digunakan untuk mendapatkan solusi yang optimal dari permasalahan optimasi penjadwalan sumber daya proyek. 2. Dari hasil pengujian terhadap setiap parameter algoritma PSO, seperti dijabarkan pada sub bab 4.2, diperoleh nilai parameter-parameter yang menghasilkan hasil yang optimal pada masing-masing kasus uji pada penerapan algoritma PSO dalam pemecahan masalah penjadwalan sumber daya proyek, yaitu : Tabel 5-1 Parameter Terbaik untuk Kasus Uji LOGON
LOGON
m 60
nc 1000
c1 2
c2 0.5
w 0.9
3. Berdasarkan sub bab 4.4, algoritma Particle Swarm Optimization (PSO) menghasilkan solusi yang paling optimal bila dibandingkan dengan algoritma Rank Based Ant System (ASrank). 4. Konsep algoritma Particle Swarm Optimization (PSO) yang unik yaitu menerbangkan solusi yang potensial ke hyperspace berarti mempercepat kesolusi yang terbaik.
5.2 Saran Saran yang dapat digunakan untuk perkembangan selanjutnya : 1. Lebih baik jika user dapat menentukan prioritas sumber daya mana yang lebih penting untuk dilakukan resource leveling.
37
Daftar Pustaka [1] A. Carlisle dan G. Dozier. 2001. An Off-The-Shelf PSO. In Proceedings of the Particle Swarm OptimizationWorkshop, pages 1–6. [2] Clerc, M. 1999. The swarm and the queen: towards a deterministic and adaptive particle swarm optimization. Proceedings, 1999 ICEC, Washington, DC, pp 1951-1957. [3] Departemen dalam negeri. 2007. Modul 1 Pengertian Dasar Manajemen Proyek. Lembaga Administrasi Negara. [4] Gray, Clifford f dan Erik W. 2006. Manajemen Proyek Proses Manajerial. Yogyakarta : Penerbit Andi. [5] https://courses.worldcampus.psu.edu/welcome/pmangt/samplecontent/520les son08/lesson08_01.html diakses tanggal 16 Januari 2009 [6] http://en.wikipedia.org/wiki/Particle_swarm_optimization.html diakses tanggal 13 Januari 2009 [7] http://en.wikipedia.org/wiki/Swarm_intelligence.html diakses tanggal 13 Januari 2009 [8] http://www.swarmintelligence.org/tutorials.php diakses tanggal 14 Januari 2009 [9] Hasan, Rania. 2004. Particle Swarm Optimization : Method and Application. Engineering Systems Division - Massachusetts Institute of Technology. [10] Hong Zhang, Xiadong Li, Heng Li and Fulai Huang, Particle swarm optimization for resource-constrained project scheduling, Automation in Construction, pp. 393-404, 2004. [11] Kennedy, J. and Eberhart, R. (1995). Particle Swarm Optimization, IEEE International Conference on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, IV: 1942-1948. [12] Luthan, Putri Lyanna A. dan Syafriandi. 2005. Aplikasi Microsoft Project untuk Penjadwalan Kerja Proyek Teknik Sipil. Penerbit Andi. Yogyakarta. [13] Muslim, Irfan. 113027263. Optimasi Penjadwalan Sumber Daya Proyek Menggunakan Algoritma Genetik. 2005. Bandung : Sekolah Tinggi Teknologi Telekomunikasi. [14] Nicholas, John M. 1990. Managing Business and Engineering Projects : Concepts and Implementation. New Jersey : Prentice-Hall. [15] Priyanto, Aruna Anggayasti. 113040076. Penerapan Algoritma Ant Colony Optimization (ACO) pada Optimasi Penjadwalan Sumber Daya Proyek. 2008. Bandung : Institut Teknologi Telekomunikasi. [16] Qureshi, Liaqat Ali. 2007. Resource Allocation & Leveling. UET Taxila. [17] Shi, Y. H., Eberhart, R. C., (1998). A Modified Particle Swarm Optimizer, IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, May 4-9, 1998. [18] Shi, Y. H., Eberhart, R. C., (1998). Parameter Selection in Particle Swarm Optimization, The 7th Annual Conference on Evolutionary Programming, San Diego, USA. [19] Soeharto, Iman. 1990. Manajemen Proyek (Dari Konseptual Sampai Operasional). Jakarta : Penerbit Erlangga.
38
[20] Spinner, M. Pete. 1992. Elements of Project Management: Plan, Schedule and Control. New Jersey. Prentice Hall. [21] Szendroi, Etelka. 2006. A Resource Leveling MILP Model For Multi-Mode Projects Based On Global Measure. University of Pecks Pollack Mihaly Faculty of Engineering. [22] Xing-mei, Li, Zhang Li-hui, QI Jian-xun dan Zhang su-fang. 2008. An extended particle swarm optimization algorithm based on coarse-grained and fine-grained criteria and its application. China.
39
Lampiran A : Kombinasi Pengujian No
C1
C2
W
No
C1
C2
W
1
0.5
0.5
0.8
64
1.5
1.5
1.1
2
0.5
0.5
0.9
65
1.5
1.5
1.2
3
0.5
0.5
1
66
1.5
2
0.8
4
0.5
0.5
1.1
67
1.5
2
0.9
5
0.5
0.5
1.2
68
1.5
2
1
6
0.5
1
0.8
69
1.5
2
1.1
7
0.5
1
0.9
70
1.5
2
1.2
8
0.5
1
1
71
1.5
4
0.8
9
0.5
1
1.1
72
1.5
4
0.9
10
0.5
1
1.2
73
1.5
4
1
11
0.5
1.5
0.8
74
1.5
4
1.1
12
0.5
1.5
0.9
75
1.5
4
1.2
13
0.5
1.5
1
76
2
0.5
0.8
14
0.5
1.5
1.1
77
2
0.5
0.9
15
0.5
1.5
1.2
78
2
0.5
1
16
0.5
2
0.8
79
2
0.5
1.1
17
0.5
2
0.9
80
2
0.5
1.2
18
0.5
2
1
81
2
1
0.8
19
0.5
2
1.1
82
2
1
0.9
20
0.5
2
1.2
83
2
1
1
21
0.5
4
0.8
84
2
1
1.1
22
0.5
4
0.9
85
2
1
1.2
23
0.5
4
1
86
2
1.5
0.8
24
0.5
4
1.1
87
2
1.5
0.9
25
0.5
4
1.2
88
2
1.5
1
26
1
0.5
0.8
89
2
1.5
1.1
27
1
0.5
0.9
90
2
1.5
1.2
28
1
0.5
1
91
2
2
0.8
29
1
0.5
1.1
92
2
2
0.9
30
1
0.5
1.2
93
2
2
1
31
1
1
0.8
94
2
2
1.1
32
1
1
0.9
95
2
2
1.2
33
1
1
1
96
2
4
0.8
34
1
1
1.1
97
2
4
0.9
40
35
1
1
1.2
98
2
4
1
36
1
1.5
0.8
99
2
4
1.1
37
1
1.5
0.9
100
2
4
1.2
38
1
1.5
1
101
4
0.5
0.8
39
1
1.5
1.1
102
4
0.5
0.9
40
1
1.5
1.2
103
4
0.5
1
41
1
2
0.8
104
4
0.5
1.1
42
1
2
0.9
105
4
0.5
1.2
43
1
2
1
106
4
1
0.8
44
1
2
1.1
107
4
1
0.9
45
1
2
1.2
108
4
1
1
46
1
4
0.8
109
4
1
1.1
47
1
4
0.9
110
4
1
1.2
48
1
4
1
111
4
1.5
0.8
49
1
4
1.1
112
4
1.5
0.9
50
1
4
1.2
113
4
1.5
1
51
1.5
0.5
0.8
114
4
1.5
1.1
52
1.5
0.5
0.9
115
4
1.5
1.2
53
1.5
0.5
1
116
4
2
0.8
54
1.5
0.5
1.1
117
4
2
0.9
55
1.5
0.5
1.2
118
4
2
1
56
1.5
1
0.8
119
4
2
1.1
57
1.5
1
0.9
120
4
2
1.2
58
1.5
1
1
121
4
4
0.8
59
1.5
1
1.1
122
4
4
0.9
60
1.5
1
1.2
123
4
4
1
61
1.5
1.5
0.8
124
4
4
1.1
62
1.5
1.5
0.9
125
4
4
1.2
63
1.5
1.5
1
41
Lampiran B : Data Pengujian
42
Proyek LOGON
Nama Aktivitas
Durasi
H I J K L M N O P Q R S T U V W X Y Z
10 8 6 4 2 4 4 5 5 5 5 3 3 1 5 2 3 8 6
Sumber Daya Labor (people) 5 4 8 2 6 3 2 5 6 2 0 0 0 9 14 6 6 14 5
Predecessor H H J J J I I I,J L M N Q O,S K,R U V W,X T,Y
1
Proyek Qureshi Nama Aktivitas
Durasi
A B C D E F G H I J K
2 2 1 4 5 8 3 1 4 5 3
Sumber Daya L (people) 3 6 3 0 0 4 5 4 2 2 0
Predecessor M (people) 0 0 0 2 2 4 0 0 0 0 5
A B B C D E F,G H,I
2
Proyek Building Nama
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Deskripsi
Excavate Prepare Reinforcing Steel Place Reinforcing Steel Tie Reinforcing Steel Build floor forms Erect Forms Ship Structural Steel Start Floor Electrical Start Installing Plumbing Finish Installing Plumbing Build Wall Frames Finish Floor Electrical Check Forms Place Floor Concrete Remove Forms Check Floor Start Masonry Finish Masonry Cement Finish Start Erecting Structural Steel Finish Erecting Structural Steel Start Roof & Decking
Durasi (days) 15 10 10 10 10 15 25 15 15 10 20 25 5 10 10 5 20 20 10 10 10 10
Sumber Daya Carpenter Laborer (people) (people) 0 90 0 0 0 10 0 20 30 30 30 45 0 0 0 15 0 15 0 20 20 80 0 25 5 0 20 40 20 40 5 0 0 80 0 40 0 20 0 0 0 0 0 40
Predecessor Ironworker (people) 0 40 40 40 0 0 0 0 0 0 0 0 5 0 0 5 0 0 0 40 40 30
Electrician (people) 0 0 0 0 0 0 0 0 0 0 0 75 5 0 0 5 0 0 0 0 0 0
Equipment Operator (people) 30 0 10 10 0 15 0 0 0 0 20 0 0 0 0 0 0 0 0 10 10 10
1,2 3 1,5 1 1 9 1,5 8 4,6,12,10 4,6,12,10 14 13,14 15,16,7,11 17 18 15,16,7,11 20 18
3
23 24 25 26 27 28 29 30 31 32 33 34 35 36
Finish Roof & Decking Start Wall Electrical Finish Wall Electrical Install Ceiling Electrical Strat Framework Finish Framework Finish Woodwork Start Paint Check Walls Start Installing Ceiling Finish Installing Ceiling Finish Paint Final Approval Clean Site
20 20 15 10 20 15 30 10 5 20 20 20 5 20
0 0 0 0 60 30 120 0 5 40 40 0 5 0
80 20 15 10 40 60 60 10 0 80 80 20 0 80
60 0 0 0 0 0 0 0 0 0 0 0 0 0
0 60 30 20 0 0 0 0 5 0 0 0 0 0
40 0 0 0 20 15 0 0 0 20 20 0 0 20
22 15,16,7,11 24 25 15,16,7,11 27 21,28 29 21,28 29 31,19,32 23,33,26,30 34 23,33,26,30
4
