Pemodelan dan penyelesaian masalah pembagian mata kuliah menggunakan maximum - flow

Abstract

Salah satu waktu yang penting sebelum semester baru dimulai adalah saat para mahasiswa harus menentukan mata kuliah apa saja yang akan mereka ambil untuk semester tersebut. Tidak jarang mahasiswa tidak berhasil mendapatkan mata kuliah yang mereka inginkan karena keterbatasan tempat dan kemungkinan jadwal yang bentrok. Untuk memberikan solusi terhadap permasalahan tersebut, penelitian ini akan fokus melakukan pembagian mata kuliah pilihan secara optimal. Optimal yang dimaksud di sini adalah sebanyak mungkin mahasiswa mendapatkan mata kuliah sesuai dengan pilihannya masing-masing. Pilihan-pilihan mata kuliah mahasiswa dapat dimodelkan menjadi sebuah graf yang biasa disebut flow network. Pada pemodelan tersebut, algoritma Edmonds-Karp yang telah dimodifikasi dengan kombinasi dan pengecekan jadwal diterapkan. Model dan algoritma diimplementasikan menggunakan bahasa pemrograman Java. Implementasi program diuji menggunakan beberapa kasus yang telah dihitung manual maupun kasus acak. Sebagian hasil pengujian implementasi program merupakan solusi yang optimal, tetapi sebagian lagi tidak. Solusi yang tidak optimal disebabkan oleh jadwal kuliah yang bentrok dan urutan pembagian mata kuliah.