Putut Putri Siliwangi Jabar, 080312695 (2008) Algoritma Genetika untuk Menyelesaikan Masalah Max-Min Matching dengan Penugasan Dibatasi. Skripsi thesis, UNIVERSITAS AIRLANGGA.

Preview

Text (ABSTRAK) gdlhub-gdl-s1-2011-jabarputut-13029-abstrak-a.pdf Download (692kB) | Preview

Abstract

Skripsi ini bertujuan untuk menyelesaikan masalah max-min matching dengan penugasan dibatasi menggunakan algoritma genetika. Masalah max-min matching ini memiliki dua kriteria pengoptimalan, kedua kriteria ini merupakan pasangan atribut dalam matching pemroses-pekerjaan. Diasumsikan sebuah pekerjaan hanya dapat dilakukan oleh sebuah pemroses, tetapi setiap pemroses dapat mengerjakan beberapa pekerjaan dengan batas bawah dan batas atas jumlah pekerjaan yang dapat dilakukan. Dua kriteria yang akan dibahas adalah kardinalitas matching dan rating (misalnya tingkat keahlian atau kecepatan), dengan tujuan utama adalah mencari kardinalitas matching yang maksimal dan tujuan kedua adalah memaksimalkan rating yang minimal atas himpunan bagian dari matchings yang mempunyai kardinalitas maksimal tersebut. Algoritma genetika diawali dengan membangkitkan kromosom secara acak dengan kode permutasi sebanyak ukuran populasi. Kromosom-kromosom dalam populasi akan berevolusi dalam suatu proses iterasi yang berkelanjutan yang disebut generasi. Pada setiap generasi, kromosom dievaluasi berdasarkan suatu fungsi evaluasi dan dilakukan pelestarian kromosom. Melalui operator-operator genetika, yaitu seleksi, crossover, dan mutasi akan dihasilkan kromosom yang dianggap terbaik, yang diharapkan mendekati solusi optimal. Proses diulangi sampai maksimum generasi yang diinginkan. Skripsi ini menggunakan sebuah data 3 pemroses dan 8 pekerjaan yang dikutip dari (Dondeti dan Emmons, 1996). Data terdiri dari batas bawah dan atas pemroses, serta rating pemroses dalam melakukan suatu pekerjaan. Has ii yang diperoleh dari program C++ Builder untuk data ini dengan popSi-e = 30, pc = 0.6, pm = 0.01, dan maksimum generasi = 10 adalah kardinalitas matching maksimal berjumlah 7 dengan nilai rating minimal dari kardinalitas matching tersebut adalah 3.

Actions (login required)

View Item