OPTIMASI ALOKASI SUMBER DAYA DENGAN GENETIC ALGORITHMS

Media Teknik Sipil, Volume XI, Juli 2011 ISSN 1412-0976

OPTIMASI ALOKASI SUMBER DAYA DENGAN GENETIC ALGORITHMS Widi Hartono Dosen Program Studi Teknik Sipil, Fakultas Teknik, Universitas Atma Jaya Yogyakarta

Email : [email protected] Abstrak Penelitian ini merupakan penanganan masalah perataan sumber daya pada penjadwalan sebuah proyek. Masalah yang diteliti adalah bagaimana membuat model untuk meratakan sumber daya yang fluktuatif dengan menggunakan Genetic Algorithm. Tujuan utama penelitian ini adalah menghasilkan perangkat lunak yang dapat digunakan untuk meratakan sumber daya dengan Genetic Algorithm yang dapat diaplikasikan pada permasalahan pengalokasian sumber daya. Metode yang digunakan untuk menyelesaikan masalah tersebut adalah dengan menggunakan Genetic Algorithm dengan bantuan program komputer. Algoritma genetika dapat digunakan untuk mencari solusi optimal tanpa harus menggunakan dan mengetahui metode penyelesaiannya sendiri. Hasil perhitungan yang telah dilakukan menunjukkan bahwa terdapat perbaikan alokasi sumber daya yang ada. Hal ini ditunjukkan dengan menurunnya Levelling Index dari 69 menjadi 26 dan histogram yang lebih rata sebelum dioptimasi. Kata Kunci: Resource Leveling, Genetic Algorithm, mutasi, crossover

Abstract This study is the alignment of resources to address the problems in scheduling a project. The problem studied is how to create a model for the fluctuating resource leveling using genetic algorithm. The main purpose of this study is to produce software that can be used to flatten the resources with the genetic algorithm that can be applied to problems of resource allocation. The method used to solve such problems is by using a genetic algorithm with the aid of a computer program. Genetic algorithms can be used to find optimal solutions without having to use and find their own solution methods. Results of calculations have been done show that there is a better allocation of existing resources. This is indicated by the decline Levelling index of 69 to 26 and more flat histogram before optimizations.

Keywords: Resource Leveling, Genetic Algorithm, mutation, crossover

1. PENDAHULUAN Sejak tahun 1950 Critical Path Method (CPM) dan Program Evaluation and Review (PERT) telah banyak digunakan para praktisi untuk perencanaan dan kontroling proyek berskala besar dalam industri. Analisa CPM dan PERT secara tradisional adalah setiap aktivitas diasumsikan dimulai secepat mungkin. Dalam kenyataannya aktivitas-aktivitas lain dalam jaringan dapat digeser-geser dengan menggunakan waktu float yang ada untuk memperoleh profil sumber daya yang tetap. Dari pandangan manajemen proyek ada beberapa alasan untuk melakukan resource leveling. Pertama, kebutuhan untuk memanfaatan sumber daya yang terbatas. Kedua, untuk menghindari fluktuasi permintaan sumber daya dari waktu ke waktu, dan ketiga, kebutuhan untuk menjaga pemakaian sumber daya agar tetap rata. Tenaga kerja merupakan salah satu sumber daya yang penting seringkali penyediannya terbatas, baik karena faktor kualitas ataupun hal-hal lain. Merekrut, menyeleksi, dan melatih tenaga kerja memerlukan biaya yang mahal dan membutuhkan waktu lama sebelum mereka siap pakai. Setelah mereka bergabung dengan proyek, tidak mudah untuk melepas dan untuk memanggil kembali

bekerja sesuai dengan fluktuasi pekerjaan yang tersedia. Sedangkan menahan mereka untuk stand-by akan menelan biaya yang tidak efisien. Untuk itu diusahakan jangan terjadi fluktuasi secara tajam [1]. Masalah resource leveling telah dipelajari dengan intensif dalam bidang konstruksi dan industri manufaktur karena kepraktisan dalam penggunaannya. Awalnya percobaan memecahkan permasalahan resource leveling dapat dibedakan menjadi dua kategori yaitu model analitik dan model heuristic [2]. Beberapa analitik atau heuristic model telah dikembangkan untuk memecahkan permasalahan resource leveling. Kelemahan utama dari model analitik adalah tidak dapat menyelesaikan permasalah yang besar dan komplex secara efisien. Model heuristic tergantung pada tiap permasalahan sehingga aturan penunjuk tidak bisa digunakan secara sama untuk semua kasus kontruksi yang lain. Lagi pula penyelesaian dari model heuristic secara umum kurang optimal [2]. Pendekatan baru dengan memanfaatkan genetic algorithms diharapkan akan dapat memecahkan permasalah pada dua metode penyelesaian masalah di atas. Dengan memanfaatkan algorima genetika diharapkan akan dapat mencapai tujuan yang dikehendaki yaitu meminimalisasi penggunaan project resource yang bervariasi sesuai dengan durasi proyek yang ada. 108

Widi Hartono, 2011, Optimasi Alokasi Sumber... Media Teknik Sipil, Vol. XI, No.2, Hal 108 - 114

Pemanfaatan sumber daya dalam proyek harus di kelola dengan baik. Dalam penyusunan jadwal pekerjaan sumber daya-sumber daya yang dibutuhkan dialokasikan menurut pekerjaannya masing-masing. Untuk mengalokasikan sumber daya agar tidak terjadi fluktuasi pemakaian sumber daya dalam proses pekerjaan maka sumber daya-sumber daya tersebut harus diatur sedemikian hingga fluktuasi pemakai sumber daya dapat dihindari atau dikenal dengan resource levelling. 2. KAJIAN PUSTAKA 2.1. Resource Leveling Tujuan dari resource leveling adalah untuk meratakan sumber daya dalam usaha untuk mencari alur yang rata dari penggunaan sumber daya dengan durasi proyek yang tetap. Teknik yang populer dari resource leveling dapat dikategorikan menjadi dua yaitu metode analitik dan metode heuristic. Pendekatan awal untuk menyelesaikan permasalahan resource leveling dengan metode analitik adalah menggunakan pendekatan model matematika, termasuk Integer Linear Programming dan enumerasi yang mendalam. Easa menggunakan teknik integer programming untuk menyelesaikan problem resource leveling. Ahuja memaparkan prosedure enumarasi yang mendalam yang dapat menghitung solusi yang optimum untuk problem resource leveling. Perlu dipahami bahwa problem resource leveling mempunyai fenomena ledakan kombinatorial terutama dalam problem berskala besar. Untuk menghindari ledakan kombinatorial, aturan heuristic paling banyak digunakan untuk menyelesaikan permasalahan [2]. Model PACK [3] dan model NASTRAT (Padilla, Carr, 1991) adalah contoh dari metode heuristic. Wiest dan Levy (1977), Antill dan Woodhead (1982)[4], Moder et.al. (1983)[5], dan beberapa lainnya juga mengembangkan metode heuristic untuk menyelesaikan problem resource leveling. Karena variasi struktur jaringan dan sumber daya, tidak ada satu metode heuristic dapat selalu menghasilkan penyelesaian yang baik untuk semua problem resource leveling. Berdasarkan dari paparan diatas, kelebihan dan kelemahan dari metode sebelumnya dapat disimpulkan sebagai berikut. Aturan heuristic mungkin menunjukkan perfoma yang baik dalam variasi permasalahan dan secara luas digunakan dalam kasus yang praktis karena bentuknya yang sederhana dan efisien dalam penggunaannya, tetapi penyelesaian yang optimal tidak dijamin. Model matematik mungkin dijamin dapat menyelesaikan permasalahan secara optimum dalam skala yang kecil. Hanya saja akan sangat sulit untuk membuat model matematik general dan usaha perhitungan

yang luas yang dibutuhkan untuk permasalahan yang besar. [2], [3], [5]. Dari hasil penilaian kondisi penelitian sebelumnya, dibutuhkan suatu algoritma yang efisien untuk memperoleh hasil yang baik dan mendekati yang optimum untuk keperluan praktis proyek konstruksi. Dalam penelitian ini, berdasarkan uraian di atas peneliti ingin menggunakan pendekatan baru dalam menyelesaikan permasalahan resource leveling yaitu dengan menggunakan genetic algorithms. 2.2. Latar Belakang Biologi Semua makhluk hidup terdiri dari sel. Di dalam setiap sel terdapat kumpulan kromosom. Kromosom adalah rangkaian DNA dan akan membentuk model makhluk hidup secara keseluruhan. Sebuah kromosom mengandung gen-gen dimana setiap gen tersebut mempunyai posisi tertentu di dalam kromosom yang disebut dengan locus. Setiap gen mengkodekan suatu karakter tertentu (a trait), sebagai contohnya adalah warna mata. Alleles adalah istilah untuk semua kemungkinan dari suatu karakter. Contohnya adalah untuk warna mata allelesnya adalah hitam, coklat, biru, dan sebagainya. Di dalam Algoritma Genetika sebuah kromosom disimbolkan sebagai sebuah individu atau solusi. Sedangkan gen disimbolkan sebagai bit (0 atau 1). Allelesnya adalah 0 dan 1. Locus dipakai untuk menentukan posisi bit di dalam individu. 2.3. Genetic Algorithms Algoritma Genetika adalah algoritma yang digunakan untuk mancari solusi dengan menggunakan teknik seleksi alam dan genetika. Algoritma ini dimulai dengan kumpulan solusi yang disebut dengan populasi. Solusisolusi dari sebuah populasi diambil dan digunakan untuk membentuk populasi yang baru. Hal ini dimotivasi dengan harapan bahwa populasi yang baru dibentuk tersebut akan lebih baik daripada yang lama. Solusi-solusi yang dipilih untuk membentuk solusisolusi yang baru dipilih sesuai dengan fitness mereka masing-masing. Semakin bagus atau sesuai fitness dari sebuah solusi maka solusi tersebut mempunyai peluang besar untuk dipilih. Proses ini dilakukan berulang sampai kondisi tertentu dipenuhi, sebagai contohnya jumlah populasi atau solusi optimal sudah diperoleh. Berikut ini adalah dasar dari Algoritma Genetika 1. [Start] Generate populasi pertama secara random sebanyak n individu. 2. [Fitness] Evaluasi nilai fitness f(x) dari setiap individu x di dalam populasi. 3. [New population] Bentuk populasi baru dengan melakukan pengulangan langkah langkah di bawah ini sehingga didapatkan populasi baru. 109


a.

[Selection] Pilih 2 individu sebagai orang tua dari sebuah populasi sesuai dengan fitness mereka (semakin baik fitness mereka, maka semakin besar peluang mereka untuk dipilih).

b. [Crossover] Lakukan persilangan antara kedua orangtua sesuai dengan probabilitas crossover untuk membentuk keturunan yang baru. Jika tidak terjadi persilangan maka keturunan yang dihasilkan akan sama persis dengan orangtuanya. c.

[Mutation] Mutasi setiap keturunan yang baru sesuai dengan probabilitas mutation di setiap locus.

d. [Accepting] Tempatkan keturunan yang baru sebagai populasi yang baru.

paling baik hilang. Oleh karena itu metode ini sebagai tahap awal memasukkan kromosom dengan nilai fitness yang paling baik atau beberapa kromosom dengan nilai fitness yang tinggi atau cukup tinggi dari generasi yang lama ke dalam generasi yang baru. Kemudian sisa kromosom dalam generasi yang baru diperoleh dengan cara reproduksi biasa. 3. Roulette Wheel Selection Kromosom dipilih berdasarkan nilai fitness, semakin besar nilai fitnessnya maka kromosom tersebut mempunyai peluang untuk dipilih beberapa kali. 2.6. Operator Dalam Algoritma Genetika Dua operator yang paling penting dalam Algoritma Genetika adalah crossover dan mutation. 1. Crossover

4. [Replace] Gunakan populasi yang baru dibentuk untuk menjalankan algoritma.

Persilangan antara gen-gen dari menciptakan keturunan yang baru.

5. [Test] Jika kondisi akhir dipenuhi maka berhenti dan tampilkan solusi dari populasi.

a. One point crossover

6. [Loop] Kembali ke nomer 2. 2.4. Pengkodean Bentuk pengkodean untuk kromosom yang paling sering digunakan adalah pengkodean dengan menggunakan string biner (bit 0 atau 1).

orangtua

dan

Sebuah titik crossover dipilih , selanjutnya string biner mulai dari awal kromosom sampai dengan titik tersebut disalin dari salah satu orangtua ke keturunannya, kemudian sisa bit keturunan disalin dari orangtua yang kedua. b. Two point crossover

Setiap kromosom mempunyai sebuah string biner. Setiap bit di dalam string mewakili karakter dari solusi dan string biner secara keseluruhan mewakili suatu bilangan.

Dua titik crossover dipilih, selanjutnya string biner mulai dari awal kromosom sampai dengan titik crossover pertama disalin dari salah satu orangtua ke keturunannya kemudian mulai dari titik crossover pertama sampai dengan titik kedua disalin dari orangtua kedua. Sisanya disalin dari orangtua pertama.

2.5. Seleksi

2. Mutasi

Setiap kromosom yang terdapat dalam populasi akan melalui proses seleksi untuk dipilih menjadi orangtua. Sesuai dengan teori evolusi Darwin maka kromosom yang baik akan bertahan dan menghasilkan keturunan yang baru untuk generasi selanjutnya. Ada beberapa metode seleksi, yaitu:

Setelah crossover dilakukan, proses reproduksi dilanjutkan dengan mutasi. Hal ini dilakukan untuk menghindari solusi-solusi dalam populasi mempunyai nilai lokal optimum. Mutasi adalah proses mengubah gen dari keturunan secara random. Untuk kode biner maka mutasi mengubah bit 0 menjadi bit 1 dan bit 1 menjadi bit 0.

1. Steady-State Selection Pemikiran utama dari metode seleksi ini adalah sebagian kromosom dari generasi lama tetap bertahan atau berada di generasi selanjutnya. Algoritma Genetika menerapkan pemikiran tersebut dengan cara di dalam setiap generasi sejumlah kromosom yang mempunyai nilai fitness tinggi dipilih untuk diproses sehingga menghasilkan keturunan yang baru sedangkan kromosom dengan nilai fitness rendah dibuang. 2. Elitism Ketika membentuk populasi baru dengan crossover dan mutasi ada kemungkinan kromosom yang

2.7. Parameter Dalam Algoritma Genetika Dua parameter dasar dalam Algoritma Genetika adalah probabilitas crossover dan probabilitas mutation. 1. Probabilitas crossover Menunjukkan kemungkinan crossover terjadi antara 2 kromosom. Jika tidak terjadi crossover maka keturunannya akan sama persis dengan kromosom orangtua, tetapi tidak berarti generasi yang baru akan sama persis dengan generasi yang lama. Jika probabilitas crossover 100% maka semua keturunannya dihasilkan dari crossover. Crossover dilakukan dengan harapan bahwa kromosom yang baru akan lebih baik. 110


2. Probabilitas mutasi Menunjukkan kemungkinan mutasi terjadi pada gen-gen yang menyusun sebuah kromosom. Jika tidak terjadi mutasi maka keturunan yang dihasilkan setelah crossover tidak berubah. Jika terjadi mutasi bagian kromosom akan berubah. Parameter lain dalam Algoritma Genetika 3. Jumlah individu Menunjukkan jumlah kromosom yang terdapat dalam populasi (dalam satu generasi). Jika hanya sedikit kromosom dalam populasi maka Algoritma Genetika akan mempunyai sedikit variasi kemungkinan untuk melakukan crossover antara orangtua karena hanya sebagian kecil dari search space yang dipakai. Sebaliknya jika terlalu banyak maka Algoritma Genetika akan berjalan lambat.

Bentuk terminasi dari metode Genetic Algorithm adalah dengan membatasasi populasi maksimal. Proses berulang hingga berakhir pada saat populasi mencapai batas populasi maksimal. Data dari hasil analisa pada langkah sebelumnya dimodifikasi dengan menggunakan teknik crossover dan mutasi untuk mendapatkan individu baru, kemudian langkah berulang dengan docoding dan berulang hingga kondisi terminasi di penuhi. Dengan berhentinya proses evolusi yang dilakukan diharapkan akan dapat didapat invidu yang baik yang dapat bertahan hidup. Berdasarkan individu yang terbaik tersebut maka dilakukan desain terakhir untuk memperoleh desain yang optimal.

Mulai Pengumpulan Data

4. Jumlah populasi Menentukan jumlah populasi yang digunakan sebagai batas akhir proses seleksi, crossover, dan mutasi.

Pembuatan model Pembuatan algoritma dan diagram alir

3. METODE

Coding dan Pembuatan User Interface

Penelitian ini mempunyai tujuan untuk meratakan kebutuhan sumber daya dengan menggunakan metode Genetic Algorithm (GA). Sebelum melangkah lebih lanjut dalam melakukan penelitian, semua bahan-bahan dan literatur-literatur yang berhubungan dengan resource leveling dan Genetic Algorithm distudi terlebih dahulu. Kemudian mengumpulkan permasalahan-permasalahan yang berhubungan dengan resource leveling yang menggunakan metode Genetic Algorithm, kemudian dibuat pemodelan matematik dan pemodelan optimasi dengan Genetic Algorithm. Bentuk dari pemodelan tersebut berupa desain variabel dan skema penyelesaian, penurunan fungsi tujuan yang akan dioptimasi dan pembentukan fungsi-fungsi kendala yang akan mendukung optimasi fungsi tujuan. Dengan menggunakan metode Genetic Algorithm, dibuat suatu penggenerasian awal data yang dapat menggambarkan penyelesaian resource leveling. Hasil dari generasi tersebut dengan cara random dipilih dan dijadikan individu baru yang digunakan untuk desain awal optimasi. Data-data dari desain awal yang masih berupa kode-kode diubah kedalam bentuk numerik yang menunjukkan nilai tertentu, untuk itu perlu adanya decoding untuk merubah kode-kode tersebut. Hasil dari decoding dianalisa dengan menggunakan parameter matematik yang sudah dibuat sebelumnya, yaitu berupa fungsi tujuan dan fungsi kendala.

Pengujian dan debugging program Implementasi program Dokumentasi dan laporan Selesai

Gambar 1. Diagram alir penelitian 4. HASIL DAN PEMBAHASAN Dalam penggunaan Genetic Algorithm bentuk penggunaan kode-kode dari kromosome tergantung pada permasalahan yang dihadapi. Ada dua bentuk dasar untuk menyajikan kromosome dalam Genetic Algorithm yaitu binary (atau bentuk numerik) dan bentuk berurutan. Sehingga bentuk dari operator crossover dan mutasi juga tergantung dari permasalahan pengkodean tersebut. Sebagai contoh gambar 1 bentuk kromosome dan opertor Genetic Algorithm yang digunakan adalah sebagai berikut. Ketika menggunakan Genetic Algorithm untuk menyelesaikan permasalaha resorce levelling, karakter yang digunakan berupa string (kromosome) 111


menunjukkan kemungkinan saat paling awal kegiatan dimulai. Operator crossover adalah onecut-point (one-point) crossover dan mutasi yang digunakan uniform mutation.

2 A 2

Untuk mengevaluasi dalam penyelekseian dan model penyelesaian menggunakan resources levelling index seperti rumusan di bawah ini:

0 ST 0

4 B 1

1 C 4

( )

T     RLI = ∑  ∑ riq −  ∑ ri d i  /T  q =1  all i  all i  

dengan ti-ESi
4 D 4

1 H 0

3 E 2

4 J 2

6 F 4

6 G 6

1 L 2

5 K 1

Gambar 1. Network diagram yang digunakan Tabel 1. Perhitungan floating pada masing-masing kegiatan Aktivitas 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 J 10 K 11 L

Durasi 2 4 1 4 3 6 6 1 4 5 1

ES 0 0 0 2 4 4 1 7 7 10 15

EF 2 4 1 6 7 10 7 8 11 15 16

LS 6 0 3 10 8 4 4 14 11 10 15

LF 8 4 4 14 11 10 10 15 15 15 16

TF 6 0 3 8 4 0 3 7 4 0 0

Parameter Genetic Algorithm yang digunakan adalah probabilitas crossover 0.75 dan probabilitas mutasi 0.05 dan parameter-parameter lain seperti terlihat pada gambar 2. Hasil eksekusi menunjukkan resource levelling index sebelum dilakukan perataan sebesar 69 dan setelah resource levelling dengan Genetic Algorthm hasilnya menjadi 26. Bentuk bar chart dari masing-masing kondisi sebelum dan sesudah dilakukan levelling dapat dilihat pada gambar 4. dan gambar 5. Dari gambar terlihat bahwa setelah dilakukan levelling permintaan sumber daya menjadi lebih rata dan fluktuasinya tidak begitu tajam dibandingkan sebelum diratakan. Durasi pekerjaan setelah diratakan tidak mengalami perubahan karena disini perataan yang digunakan memanfaatkan float yang ada pada masing-masing kegiatan.

112


Gambar 5. bar chart dan sumber daya yang digunakan sesudah levelling 5. SIMPULAN Algoritma genetika dapat digunakan untuk mencari solusi optimal tanpa harus menggunakan dan mengetahui metode penyelesaiannya sendiri. Hasil perhitungan yang telah dilakukan menunjukkan bahwa terdapat perbaikan alokasi sumber daya yang ada. Hal ini ditunjukkan dengan menurunnya Levelling Index dari 69 menjadi 26 dan histogram yang lebih rata sebelum dioptimasi. Gambar 2. Pengaturan parameter-parameter dalam Genetic Algorithm

6. SARAN 1. Untuk lebih menambahkan kecepatan dan ketelian dalam optimasi ini perlu dikaji lagi tentang metode seleksi yang digunakan dalam Algorima Genetika 2. Perlu dicoba digabungkan dengan teknologi artificial intelegance untuk memperoleh hasil yang lebih optimal. 7. UCAPAN TARIMA KASIH Penelitian ini dibiayai oleh Direktorat Pembinaan Penelitian dan Pengabdian Kepada Masyarakat, Direktorat Jenderal Pendidikan Tinggi melalui program penelitian Dosen Muda dengan nomor kontrak: 033/SPPP/PP-PM/DP3M/IV/2005 tanggal 11 April 2005. 8. DAFTAR PUSTAKA [1] Harris, R. B., 1978, Precedence and Arrow Networking Techniques for Construction, Wiley, New York

Gambar 3. Running penyelesaian problem resource levelling dengan indikator fitness kromosom dari tiap-tiap generasi

[2] Easa, S. M., 1989, Resource Leveling in Construction by Optimization, Journal of Construction Engineering and Management, ASCE 115 (2) [3] Harris, R. B., 1990, Packing Method for Resource Leveling (PACK), Journal of Construction Engineering and Management, ASCE 116 (2) [4] Antill, J. M., and Woodhead, R. W., 1982, Critical Path Method in Construction Practice, 3rd Edition, Wiley, New York

Gambar 4. bar chart dan sumber daya yang digunakan sebelum levelling

[5] Moder, J., Philips, C. R., Davis, E. W., 1983, Project Management with CPM, PERT, and Precedence Diagramming, 3rd edn., Von NostrandReinhold, Ney York

113


Davis, L., 1991, Handbook of Genetic Algorthm, Von Nostrand-Reinhold, Ney York Gen, M., Cheng, R., 1997, Genetic Algorithm & Engineering Design, John Willey & Sons, New York Goldberg, D. E., 1989, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Willey, Reading, Massachusetts Kurniadi, A., 1999, Pemrograman Bahasa Komputer Dengan Visual Basic 6.0, Elexmedia Komputindo, Jakarta

Michacevicz, Z., 1996, Genetic Algorithm + Data Structure = Evolution Programs, SpringerVerlag, Ney York Moder, J., Phillips, C. R., 1989, Project Manajement with CPM and PERT, Van Nostrand Reinhold Co., New York Ahuja, H., 1976, Construction Performance Control by Network, Wiley, New York

114

OPTIMASI ALOKASI SUMBER DAYA DENGAN GENETIC ALGORITHMS

Recommend Documents