University Course Timetabling Problem (UCTP) adalah salah satu dari
permasalahan penjadwalan yang terdapat pada institusi perguruan tinggi. Setiap
institusi memiliki batasan-batasan (constraints) yang unik dan menjadikan UCTP
sebagai salah satu permasalahan penjadwalan yang rumit. Batasan tersebut
dibagi atas dua kategori yaitu hard constraint dan soft constraint. Pada Program
Studi Teknik Industri Universitas Atma Jaya Yogyakarta (UAJY), penjadwalan
mata kuliah dilakukan secara mandiri sehingga membutuhkan waktu yang lama
untuk memenuhi semua batasan yang ada pada sistem.
UCTP dapat diselesaikan dengan berbagai pendekatan. Seiring dengan
bertambahnya penelitian terhadap kasus ini, pendekatan yang pada mulanya
berbentuk linear programming mulai berkembang menjadi bentuk heuristik seperti
Graph Coloring, hingga pendekatan metaheuristik seperti Ant Colony Optimization
(ACO). Pemilihan pendekatan tersebut disesuaikan dengan karakteristik dan
sistem yang ada sehingga pemodelan masalah dapat dilakukan secara akurat.
Pada penelitian ini, digunakan pendekatan hybrid untuk menyelesaikan UCTP
pada Program Studi Teknik Industri UAJY. Algoritma yang diusung adalah
Modified Hybrid Genetic Algorithm (MHGA) yang terdiri dari dua fase: konstruksi
dan optimasi. Fase konstruksi menggunakan algoritma heuristik Least Color
Degree (LCD) yang selanjutnya akan digunakan ke dalam Algoritma Genetika
pada fase optimasi. Selain pemenuhan constraints, fungsi objektif yang hendak
dicapai adalah maksimasi utilitas ruangan.
Hasil simulasi menunjukkan parameter terbaik untuk melaksanakan MHGA
berkaitan erat dengan dataset yang digunakan. Algoritma yang diusung terbukti
mampu menghasilkan jadwal yang tidak melanggar seluruh constraint dengan nilai
fungsi objektif yang terbaik pada generasinya. Sistem penjadwalan yang dibangun
telah divalidasi dan diakui mampu membantu proses penjadwalan mata kuliah
pada Program Studi Teknik Industri UAJY.