PEMBANGUNAN SISTEM PENJADWALAN KULIAH DI PROGRAM STUDI ILMU KOMPUTER DENGAN GRAPH COLOURING Drs.-, M.T. 1, Eddy Prasetyo Nugroho, M.T. 2, Yudi Wibisono, M.T. 3, Rani Megasari, S.Kom.4 1 )2)3)4)
PROGRAM STUDI ILMU KOMPUTER FPMIPA UNIVERSITAS PENDIDIKAN INDONESIA 1
[email protected],
[email protected], 3
[email protected],
[email protected] Abstrak Penjadwalan kuliah merupakan pekerjaan rutin dalam sistem akademik di Perguruan Tinggi yang dilakukan setiap menghadapi semester baru. Pada pelaksanaannya, seringkali jadwal yang telah dikeluarkan masih mengandung kesalahan berupa jadwal yang masih bentrok ataupun berupa pembatalan kelas perkuliahan sehingga membutuhkan adanya penjadwalan ulang. Hal ini mengakibatkan tidak efektifnya perkuliahan di awal semester karena harus melakukan penyesuaian jadwal dengan keadaan real setelah jadwal dikeluarkan. Penjadwalan kuliah menjadi suatu pekerjaan yang tidak mudah karena harus mempertimbangkan banyak constraint atau batasan yang merupakan permasalahan kombinatorial. Keterbatasan manusia untuk dapat menyusun semua constraint yang ada mengakibatkan faktor human error sulit untuk dihindari. Oleh karena it, dibutuhkan sebuah sistem penjadwalan kuliah dengan memanfaatkan komputasi dan teknologi komputer yang dapat melakukan perhitungan dan pengecekan bentrok sehingga dapat memudahkan petugas dalam melakukan penjadwalan kuliah. Implementasi Graph Colouring yang dapat melakukan pengecekan bentrok sampai ke level mahasiswa menjadi suatu fitur terpenting yang akan dikaji dalam penelitian ini. Kata kunci: Constraint, Graph Colouring, Permasalahan Kombinatorial.
1
1. Pendahuluan Di lingkungan akademik Perguruan Tinggi, penjadwalan kuliah menjadi suatu pekerjaan rutin setiap menghadapi semester baru. Permasalahan yang sering terjadi di awal semester adalah hasil penjadwalan yang belum tentu sesuai dengan kegiatan perkuliahan sehingga perlu dilakukan penjadwalan ulang. Tak jarang hal ini terjadi sampai berkali-kali sehingga cukup memangkas waktu efektif perkuliahan. Masalah lain yang juga timbul adalah kesesuaian antara jumlah peserta perkuliahan dengan kapasitas ruang. Belum lagi jika ada kesalahan karena faktor human error dalam menjadwalkan dosen, mahasiswa, dan ruang sehingga mengakibatkan bentrok dari segi waktu. Demikian rumitnya proses penjadwalan kuliah disebabkan oleh keterbatasan manusia dalam memperhitungkan semua constraint atau batasan dalam melakukan penjadwalan kuliah. Jika tugas ini dilakukan dengan memanfaatkan teknologi komputer, maka permasalahan akan dapat teratasi sehingga efektifitas perkuliahan akan dapat tercapai dengan lebih optimal. 2. Graph Colouring Permasalahan penjadwalan kuliah terkait erat dengan masalah optimasi. Dalam kajian ilmu di Matematika Diskrit, teori graf memberi solusi untuk permasalahan ini melalui bahasannya tentang pewarnaan graf. Model pewarnaan graf (graph coloring) banyak dipakai untuk permasalahan schedulling (penjadwalan) terkait dengan terbatasnya sumber daya yang ada sedangkan akses untuk menggunakan sumber daya cukup banyak. Optimasi dari pewarnaan graf terletak pada bilangan kromatiknya. Bilangan kromatik Graf G (χ(G)) adalah jumlah warna minimum yang dapat digunakan untuk mewarnai simpul (verteks / V). Pada prinsipnya, simpul yang bertetangga harus diwarnai dengan warna yang berbeda. Semakin sedikit warna yang digunakan (bilangan kromatik kecil), maka semakin padat pula kegiatan dapat dijadwalkan. Kegiatan yang berbeda warna dapat dijadwalkan dalam waktu bersamaan tanpa harus ‘bentrok’ dengan kegiatan lainnya. 3. Metodologi Pembangunan sistem penjadwalan kuliah ini melalui tahap pengembangan sistem seperti pada gambar di bawah ini:
Adapun pendekatan yang digunakan adalah pendekatan berorientasi objek dengan notasi UML. Unified Modelling Language (UML) dengan model proses prototype.
4. Hasil Kerumitan dalam menjadwalkan perkuliahan terletak pada sifat dari permasalahan ini yang merupakan permasalahan kombinatorial. Dalam menyelesaikan permasalahan ini dilakukan pemecahan penyelesaian permasalahan berdasarkan sifat constraint-nya. 2
a) Hardconstraint Untuk semua kasus penjadwalan, yang menjadi hardconstraintnya adalah penempatan komponen (mata kuliah, dosen dan mahasiswa) di dalam slot pemakaian resource (ruang dan waktu) yang tidak bentrok. Hal ini diselesaikan dengan Graph Coloring. yang sangat banyak dan mata kuliah yang dipilihnya sangat bervariasi. b) Softconstraint Setiap universitas memiliki constraint yang berbeda untuk softconstraint ini. Prioritas pemenuhannya pun tidak bisa disamakan. Umumnya, yang menjadi softconstraint dalam penjadwalan kuliah adalah sebagai berikut: • Penggunaan ruang yang sesuai antara jumlah peserta kuliah dan kapasitas ruangan. • Prioritas terhadap waktu kesediaan dosen. • Kebutuhan untuk menjadwalkan kuliah tambahan atau pengganti di tengah semester berjalan. 5. Penutup Dengan sistem penjadwalan kuliah berbasis komputer dengan graph colouring ini, jadwal yang dihasilkan menjadi bebas bentrok, dapat memprioritaskan penjadwalan berdasarkan ruang dan waktu yang tepat, melakukan pencarian slot secara cepat dan mudah, sekaligus sebagai indikator keterpakaian sumber daya perkuliahan. Pemanfaatan teknologi dan sains dalam sistem ini membantu menyelesaikan permasalahan dalam penjadwalan kuliah. Penelitian ini masih terbatas pada pembangunan sistem penjadwalan kuliah yang lebih memudahkan petugas dalam menghindari bentrok jadwal dibandingkan penjadwalan secara manual. Sistem ini membutuhkan integrasi dengan sistem praregistrasi yang dapat memberikan data valid, sehingga jadwal yang dihasilkan pun akan efektif. Berikutnya, dapat dikembangkan sebuah sistem penjadwalan kuliah yang lebih otomatis dalam memproses penjadwalan kuliah, sehingga petugas hanya berkonsentrasi pada input data dan pelayanan jadwal. Sistem yang dimaksud adalah sistem penjadwalan kuliah yang sudah mengintegrasikan kecerdasan buatan di dalamnya. Kelak sistem ini dapat dibuat generic dalam menyelesaikan berbagai permasalahan penjadwalan. 5. Referensi [1] Rong Al Fatta, Hanif.( 2007). Analisis dan Perancangan Sistem Informasi. Yogyakarta: Andi. [2] Al-Omari, Hussein & Khair Eddin Sabri. (2006). New Graf Coloring Algorithms [Online]. Tersedia: www.scipub.org/fulltext/jms2/jms224739-741.pdf, Diakses tanggal 15 Maret 2010. [3] Budi, Faizal. (1990). Sistem Bantu Penjadwalan Kuliah. Penelitian tidak terpublikasi. Bandung: Jurusan Teknik Informatika, Institut Teknologi Bandung (ITB). [4]
Budiman, Hengky. Penerapan Graph Colouring untuk Merencanakan Jadwal [Online]. Tersedia: http://www.informatika.org/~rinaldi/Matdis/2007/2008/Makalah/MakalahIF2153-0708025.pdf 3
Diakses tanggal 14 September 2010. [5] Munir, Rinaldi. (2005). Matematika Diskrit. Bandung: Informatika. [6]
Pressman, Roger.(1992). Software Engineering a Practitioner’s Approach. McGrawHill,Inc: Singapore
[7] Redl, Timothy A. University Timetabling via Graf Coloring: An Alternative Approach [Online]. Tersedia: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.3879. Diakses tanggal 15 Oktober 2009. [8] Setiadi, Robert. (2001). Pemecahan Masalah Penjadwalan Kuliah dengan Menggunakan Teknik Intelligent Search [Online]. Tersedia: http://www.robertsetiadi.net/articles/snkk.htm [12 Oktober 2009]. [9]
Tamsir, Udin. (2008). Sistem Informasi Akademik di Universitas Surakarta [Online].Tersedia:http://one.indopenelitian.com/judul-penelitian/teknik-informatika/sisteminformasi-akademik-di-universitas-surakarta,2008. Diakses tanggal 12 Oktober 2010.
4
5
