CONSTRAINT SATISFACTION PROBLEM..

Assalamualaikum sahabat ku yang baik hatinya!

Kali ini saya akan membahas tentang Constraint Satisfaction Problem, apa sih CSP itu? Constraint Satisfaction Problem merupakan sebuah pendekatan untuk menyelesaikan suatu masalah dengan tujuan menemukan keadaan atau objek yang memenuhi sejumlah persyaratan atau kriteria.

Constraint Satisfaction Problem juga adalah suatu permasalahan seseorang harus mencari nilai untuk set variabel (finite) yang memenuhi set constraint (finite). Komponen-komponen yang terdapat pada Constraint Satisfaction Problem adalah Variabel yang merupakan penampung dapat diisi berbagai nilai, Constraint yang merupakan suatu aturan yang ditentukan untuk mengatur nilai boleh diisikan ke variabel, atau kombinasi variable, Domain yang merupakan kumpulan nilai legal dapat diisi ke variable, Solusi yang merupakan assignment nilai-nilai dari domain ke setiap variabel tidak ada constraint yang dilanggar.

Komponen-komponen yang ada di CSP: 

1. Set Variabel
Merupakan sesuatu yang memiliki nilai bervariasi, kemudian dapat juga didefiniskan sebagai hal yang berbeda beda dalam bahasa pemprograman yang diwakili oleh simbol untuk variasi nilai tertentu.

2. Set Domain
Merupakan kumpulan nilai legal yang dapat diisi ke variabel. 

3. Set Constraint/Batasan
Menspesifikan kombinasi nilai yang diperbolehkan.

Contoh permasalahan CSP ini adalah Penjadwalan Mata Kuliah.
Dalam proses penjadwalan mata kuliah ada beberapa hal yang harus diperhatikan:

• Pertama, terdapat jadwal-jadwal di mana dosen yang bersangkutan tidak bisa mengajar. 
• Kedua, distribusi jadwal perkuliahan diharapkan dapat merata tiap harinya untuk setiap kelas. 
• Ketiga, pekerjaan penjadwalan mata kuliah ini akan semakin berat jika melibatkan semakin banyak kelas per angkatannya. 
• Keempat, terdapat mata kuliah tertentu yang menggunakan ruang laboratorium yang harus dijadwalkan pada ruang laboratorium.

Solusi untuk memecahkan masalah tersebut adalah dengan Algoritma Genetika. Ciri-ciri permasalahan yang dapat dikerjakan dengan menggunakan Algoritma Genetika adalah masalah tersebut mempunyai fungsi tujuan optimalisasi non linear dengan banyak kendala non linear. Selanjutnya, masalah tersebut mempunyai kemungkinan solusi yang jumlahnya tak terhingga. Kombinasi dari mata kuliah, dosen, dan kelas memiliki kemungkinan yang sangat banyak sehingga algoritma genetika dapat digunakan dalam permasalahan ini. Terakhir, masalah tersebut mempunyai multi-objective dan multi-criteria, sehingga diperlukan solusi yang dapat secara bijak diterima oleh semua pihak.

Ada faktor-faktor yang berpengaruh dalam pembentukan jadwal antara lain:

-          Dosen

Seorang dosen tidak dapat mengajar beberapa mata kuliah pada jam yang sama. Selain itu, seorang dosen terkadang hanya dapat mengajar pada jam-jam dan hari-hari tertentu saja, sehingga perlu untuk memesan jadwal khusus yang tidak dapat diganggu mata kuliah yang lain.

-          Ruang

Mengingat jumlah ruang yang dimiliki terbatas, maka perlu diperhatikan ruang yang tersedia agar tidak menggangu jalannya perkuliahan. Jadwal harus hanya mengakomodasi ruang yang ada.

-          Waktu

Waktu merupakan batasan berapa menit yang diperlukan untuk satu sks mata kuliah. Selain itu, perkuliahan dibatasi dari hari Senin sampai hari Sabtu dan setiap harinya pun dibatasi mulai jam 07.30 sampai jam 22.00. Dengan batasan-batasan waktu ini, jadwal hanya akan berada pada waktu yang ditentukan.

-          Matakuliah

Mengingat setiap matakuliah memiliki semester mata kuliah itu diajarkan, maka perlu adanya aturan yang membatasi penjadwalan mata kuliah, agar mata kuliah itu sesuai dengan aturan-aturan penjadwalan.

Selain itu, ada beberapa aturan yang harus diperhatian dalam membuat jadwal meliputi:

- Satu ruang tidak boleh diisi oleh dua mata kuliah dalam satu waktu yang sama

- Satu dosen tidak boleh mengajar dua mata kuliah dalam satu waktu yang sama

Faktor-faktor yang menyebakan Algoritma Genetika menjadi metode alternatif sebagai solusi masalah penjadwalan tersebut adalah pemadatan waktu. Pagi hari merupakan waktu yang cukup berharga untuk menambah nilai fitness. Oleh karena itu, penjadwalan dilakukan semenjak pagi untuk menambah alternatif solusi optimum. Berikutnya adalah frekuensi mengajar dosen. Penjadwalan menginginkan agar tugas mengajar dosen merata setiap harinya. Tidak terlalu padat dan tidak juga terlalu lengang. Hal ini dapat mempengaruhi kinerja mengajar dosen yang bersangkutan.

Dengan Algoritma Genetika diharapkan dapat diperoleh penjadwalan mata kuliah yang optimal yaitu kondisi di mana terjadi kombinasi terbaik untuk pasangan mata kuliah dan dosen pengajar secara keseluruhan, tidak adanya permasalahan tabrakan jadwal baik pada sisi dosen, waktu maupun ketersediaan ruang yang cukup secara fasilitas untuk seluruh mata kuliah. Penjadwalan dapat memberikan solusi yang dapat digunakan oleh dosen, mahasiswa, ruangan, mata kuliah yang terlibat dalam kegiatan perkuliahan.

Dengan bantuan Algoritma Genetik penyusunan penjadwalan mata kuliah dapat dioptimalkan. Program dapat mencari solusi penjadwalan pada waktu yang dapat digunakan baik oleh dosen maupun ruangan yang terlibat dalam suatu mata kuliah. Di samping itu, program dapat meminimalkan tingginya frekuensi mengajar seorang dosen. Proses penjadwalan mata kuliah menggunakan Algoritma Genetik ini dapat diterapkan pada kasus-kasus penjadwalan dengan multi angkatan dan multi ruangan. Dengan menggunakan metode best fitness, maka Algoritma Genetik akan selalu menunjukkan kenaikan fitness atau dengan kata lain generasi selanjutnya lebih baik atau minimal sama dengan generasi sebelumnya.

Dalam kasus ini, Constraint Satisfaction Problem berfungsi sebagai pemberi batasan dalam penjadwalan yang dihasilkan oleh Algoritma Genetika. Metode Algoritma Genetika dipadukan dengan metode Constraint Satisfaction Problem karena kromosom yang dihasilkan pada metode Algoritma Genetika dapat diproses dengan metode Constraint Satisfaction Problem sehingga dapat ditemukan batasan-batasan pada penjadwalan yang harus dipenuhi dengan cepat dan akurat.

Tulisan ini dibuat untuk memenuhi tugas  mata kuliah Pengantar Kecerdasan Tiruan (AI) yang diampu oleh Mia Kamayani ST, MT . Prodi Teknik Informatika Fakultas Teknik UHAMKA.

Referensi:

1. lidya1859.blogspot.co.id/2011/10/algoritma-genetika-dan-metode.html
2. www.scribd.com/document/28430259/Penerapan-Algoritma-Backtracking
3. informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2005-2006/Makalah2006/MakalahStmik2006-47.pdf
4. staf.cs.ui.ac.id/WebKuliah/IKI30320/materi/iki30320_20070924_handout.pdf