Pemecahan Masalah Penjadwalan Kuliah
dengan Menggunakan Teknik Intelligent Search

Author : Robert Setiadi, S.Kom, M.SoftSysEng dan Dr. Anbulagan, DEA

Abstrak

Masalah penjadwalan kuliah merupakan masalah sangat kompleks yang hingga saat ini masih merupakan sebuah topik yang banyak dibahas dalam berbagai thesis, desertasi, dan karya ilmiah di seluruh penjuru dunia. Inti dari penjadwalan kuliah adalah bagaimana menjadwalkan sejumlah komponen yang terdiri atas mahasiswa, dosen, ruang, dan waktu dengan sejumlah batasan dan syarat (constraint) tertentu. Tulisan ilmiah ini akan mencoba membahas pemecahan masalah penjadwalan kuliah dengan pendekatan ilmu Intelegensia Semu (Artificial Intelligence), yakni dengan menggunakan Constraint Satisfaction Problem. Penulis telah merancang dan menguji sebuah teknik baru yang merupakan pengembangan lebih lanjut dari teknik pencarian solusi dengan heuristic search yang dikombinasikan dengan teknik Smart Backtracking dan Look Ahead untuk menghasilkan algoritma baru yang dinamakan Intelligent Search.

Masalah dari problem penjadwalan kuliah sendiri memiliki banyak sekali variasi sesuai dengan kebijakan lembaga perguruan tinggi tempat jadwal kuliah tersebut akan digunakan. Sebagai studi kasus, kami menggunakan masalah penjadwalan kuliah yang dihadapi di Universitas Bina Nusantara. Constraint yang harus dipenuhi memiliki sejumlah kekhususan dikarenakan adanya sistem paket kuliah hingga semester 5. Keberadaan paket ini menyebabkan kelas-kelas perkuliahan mahasiswa tidak dapat lagi dianggap sebagai sebuah kesatuan yang mandiri. Pengalokasian dosen, waktu, dan ruang terhadap sebuah kelas akan sangat berpengaruh pada kelas-kelas lainnya menjadi sebuah rantai yang panjang dan sulit dipecahkan.

Berdasarkan jumlah dan jenis constraint yang ada, penulis menggunakan pendekatan heuristic untuk memecahkan masalah. Kombinasi Kelas - Matakuliah ditetapkan sebagai variabel yang harus diisi dengan nilai-nilai dosen, waktu, dan ruang. Untuk dosen terdapat sejumlah parameter yang harus diperhatikan dalam pengalokasian jadwal, yaitu waktu kesediaan dosen untuk mengajar (tersimpan dalam sebuah tabel yang didapat dari isian dosen itu sendiri), jatah SKS yang merupakan batas maksimum dosen tersebut mengajar dalam 1 minggu (ditentukan oleh ketua jurusan), dan matakuliah yang dapat diajar oleh dosen tersebut. Baik dosen maupun mahasiswa paket diusahakan mendapat jadwal kuliah maksimal 3 pertemuan dan minimal 2 pertemuan per hari dengan jam pertemuan yang berurut di lokasi kampus yang sama. Masalah masih bertambah kompleks dengan adanya sejumlah matakuliah yang harus dialokasikan di ruangan tertentu yang memiliki kriteria tersendiri.

Ide dasar dari heuristic yang kami kembangkan adalah melakukan pencarian dengan urutan dosen - waktu - ruang. Pasangan kelas - matakuliah telah terlebih dahulu diurutkan sesuai dengan jumlah conflict possibility yang ada. Tiap kelas dipasangkan dengan sejumlah dosen yang dapat mengajar matakuliah tersebut, kemudian sejumlah perhitungan heuristic dilakukan untuk mencari waktu kuliah yang memenuhi constraint dosen dan constraint mahasiswa kelas paket seperti yang telah dijelaskan di atas. Terakhir, dilakukan pencarian apakah pada waktu yang telah dihitung sebelumnya masih tersedia ruangan yang kosong.

Proses perhitungan di atas dirancang untuk sedapat mungkin menghindari terjadinya backtracking yang akan memperlambat proses. Pada setiap langkah percabangan, dilakukan proses breadth first search untuk mengambil waktu yang terbaik untuk diproses terlebih dahulu. Kemudian langkah selanjutnya merupakan proses depth first search dengan pencarian isi variabel pada level di bawahnya.

Meskipun telah diupayakan untuk tidak terjadi, kemungkinan terjadinya backtracking tetap masih ada. Untuk itu digunakan sebuah algoritma yang tidak secara otomatis naik satu level seperti yang terjadi pada search tree pada umumnya, akan tetapi program akan mencari pasangan Kelas - Matakuliah yang memiliki intersection dosen, paket, atau matakuliah dengan variabel yang menyebabkan terjadinya backtracking. Algoritma ini merupakan sebuah bentuk baru dari Intelligent Backtracking yang sudah dikenal sebelumnya dalam dunia Intelegensia Semu.

Banyaknya jumlah dan tingkat kompleksitas constraint yang ada membuat kami harus melakukan klasifikasi constraint tersebut dalam kategori hard constraint (harus terpenuhi) dan soft constraint (diupayakan untuk terpenuhi). Adapun yang kami kategorikan sebagai hard constraint adalah tidak boleh adanya bentrok waktu dan ruang mengajar dosen dan perkuliahan mahasiswa. Jumlah jam mengajar dosen per hari (sebanyak 3 x 100 menit), metakuliah dengan ruangan khusus, serta jatah SKS dosen juga kami masukkan ke dalam hard constraint.

Urutan jam kuliah dan lokasi kampus kami kategorikan sebagai soft constraint yang tingkat toleransi kesalahannya dapat diatur oleh pengguna algoritma secara bebas. Hal ini didasarkan pada eksperimen yang menunjukkan bahwa pencarian jadwal kuliah yang baik, urut, dan tidak berpindah kampus dengan tingkat kebenaran 100% akan memperlambat proses hingga mencapai waktu eksponensial berbanding jumlah kelas yang ada.

Algoritma yang kami kembangkan ini telah dicoba dengan sejumlah study case berskala kecil dan menghasilkan output yang cukup baik. Percobaan dengan real data (1198 dosen, 1457 matakuliah, 2311 kelas, 122 ruang, 40 jam perkuliahan tiap minggu, dan lebih dari 20000 mahasiswa) telah menghasilkan solusi yang baik, meskipun tidak dapat mencapai angka kebenaran 100%. Sejumlah constraint, terutama yang berkaitan dengan dosen dan mahasiswa kelas paket seringkali sulit dipenuhi karena adanya sejumlah kelas yang merupakan gabungan dari beberapa paket (dapat mencapai 12).

Dari penelitian ini kami berkesimpulan bahwa algoritma heuristic dengan smart backtracking yang tengah kami kembangkan dapat menangani dengan baik masalah penjadwalan kuliah di Universitas Bina Nusantara. Dalam beberapa hal algoritma ini masih memerlukan penyempurnaan seperti efisiensi waktu (menghindari peningkatan process time yang eksponensial), dan usaha memenuhi soft constraint dengan lebih baik. Bagaimanapun, kami sungguh berharap bahwa perkembangan yang telah kami capai ini dapat memberikan sumbangan yang berarti bagi dunia ilmu pengetahuan dunia, khususnya Indonesia.

Indonesian Society on Computer and Information Sciences :
http://www.icis.or.id/journal/j-II-01-mei02-list.html

Any comments, questions, or suggestions can be sent to robertsetiadi@gmail.com.

Note : I can NOT send you the complete paper of this research. If you are interested in studying this case, please contact Bina Nusantara University for documentation about my research.