University Course Timetabling Problem (UTCP): Penjadwalan Matakuliah

University course timetabling problem (UCTP) adalah salah satu model kombinatorik optimisasi yang terkenal dan mempunyai batasan-batasan di bidang riset operasi dan kecerdasan buatan (Artificial intelligence). UCTP adalah suatu masalah penjadwalan matakuliah dengan memperhatikan sumberdaya yang ada seperti timeslot, jumlah kelas, jumlah mata kuliah, jumlah dosen, jumlah mahasiswa dan lain sebagainya. Dalam hal penyelesain penjadwalan optimum, UCTP adalah masuk dalam kelas NP-Hard dan NP-complete problem karena waktu komputasi untuk menyelesaikan masalah penjadwalan matakuliah tersebut bertambah secara eksponensial seiring dengan bertambahnya ukuran dari model UCTP.

Penyelesaian UCTP adalah penjadwalan lengkap suatu periode (hari dan waktu) dengan menggunakan ruang kelas tertentu untuk pengajaran setiap matakuliah dengan memperhatikan batasan-batasan yang ditetapkan. Secara umum, batasan-batasan di UCTP dapat dibedakan menjadi dua bagian yaitu hard constraints (H) dan soft constraints (S). Hard constraints adalah batasan-batasan yang harus dipenuhi pada setiap waktu karena batasan-batasan tersebut menjamin tidak ada konflik dalam penggunaan sumberdaya yang ada dan mendapatkan feasible penjadwalan matakuliah. Sementara itu, soft constraints adalah batasan-batasan yang digunakan untuk meningkatkan kualitas dari penjadwalan matakuliah tersebut. Sehingga secara umum, optimisasi dari model UCTP yang mempunyai k hard constraints dan l soft constraints dapat dinyatakan sebagai berikut:

sedemikan hingga memenuhi suatu set batasan sumberdaya yang ada.