Algoritma Genetika untuk Penjadwalan Proyek Berkendala

Abstract

Penjadwalan merupakan masalah yang sulit, dipandang dari segi teknis maupun implementasi. Salah satu metode yang potensial untuk menyelesaikan masalah optimasi penjadwalan proyek berkendala adalah Algoritma Genetika (AG). AG merupakan suatu teknik pencarian stokastik dan optimasi yang cara kerjanya meniru prinsip evolusi (seleksi dan genetika alami). AG adalah bagian dari komputasi evolusioner dan mampu beradaptasi terhadap masalah yang dipecahkannya. AG bekerja secara probabilistik pada sekumpulan solusi fisibel yang dikodekan (kromosom), yang disebut populasi. Pada implementasinya, AG secara langsung hanya memanfaatkan informasi fungsi objektif. Ada berbagai jenis teknik pengodcan solusi, operator genetika, dan transformasi fungsi objektif ke dalam fungsi fitness (ukuran kualitas kromosom) dalam AG. Setiap teknik yang akan dipakai, disesuaikan dengan karakteristik permasalahannya. Pemilihan teknik dan operator genetika yang tepat sangat menentukan kesuksesan AG. Parameter-parameter AG seperti ukuran populasi, kriteria penghentian, tingkat penyilangan, dan tingkat mutasi juga harus ditentukan. Representasi urutan pengerjaan aktivitas berupa suatu vektor, penggunaan PMX (partially mapped crossover), mutasi A-optimum, dan kombinasi seleksi rolet dan elitis, cukup efektif untuk memecahkan masalah optimasi penjadwalan proyek berkendala. AG lebih baik dibandingkan metode heuristik Kusiak (1990) dalam menyelesaikan masalah tersebut. Namun demikian AG memerlukan waktu komputasi yang relatif lama. Karena AG bersifat stokastik, maka setiap kali AG dicksekusi, solusi yang dihasilkannya bisa berbeda-beda. Dengan demikian sebaiknya AG dicksekusi beberapa kali, lalu pilih satu solusi yang terbaik. Ukuran populasi yang lebih besar dan jumlah generasi yang lebih banyak, besar kemungkinan menghasilkan populasi (kandidat solusi) awal yang kualitasnya lebih baik. Semakin banyak aktivitas yang akan dijadwalkan dalam suatu proyck, semakin besar pula ukuran populasi dan/atau jumlah generasi yang diperlukan pada AG agar memperoleh solusi yang baik. Perbaikan solusi lebih banyak terjadi pada saat awal eksekusi AG (generasi-generasi awal), tetapi lebih sedikit atau bahkan tidak ada perbaikan solusi pada saat akhir eksekusi AG.