PENINGKATAN EFISIENSI SISTEM PENJADWALAN UJIAN MENGGUNAKAN ANSWER SET PROGRAMMING
PAULUS BANGUN KURNIANTO
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
PENINGKATAN EFISIENSI SISTEM PENJADWALAN UJIAN MENGGUNAKAN ANSWER SET PROGRAMMING
PAULUS BANGUN KURNIANTO
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Departemen Ilmu Komputer
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
ABSTRACT PAULUS BANGUN KURNIANTO. Efficiency Improvement of Exam Scheduling System Using Answer Set Programming. Supervised by MUSHTHOFA. Scheduling tasks has been known to be computationally expensive and some of this problem has been shown to be NP-complete. Previous research has been done to build a system that applied Answer Set Programming (ASP) to solve the problem of exam scheduling for the undergraduate Major-Minor System in Bogor Agricultural University. The results showed that the system is capable of generating exam schedule in acceptable time for relatively small-sized datasets, but not for biggersized datasets. The purpose of this research is to improve the performance of the exam scheduling system. In this research, we used clingo, a part of Potassco, as the ASP solver. The results of this system showed that there were efficiency improvements in the process time by 33,72% and the space used during the process by 51,93%. This system is also capable of generating exam schedule for bigger-sized data than the previous system. Keywords: answer set programming, clingo, Potassco, scheduling
Judul Skripsi : Peningkatan Efisiensi Sistem Penjadwalan Ujian Menggunakan Answer Set Programming Nama : Paulus Bangun Kurnianto NIM : G64070099
Menyetujui: Pembimbing
Mushthofa, S.Kom, M.Sc NIP. 19820325 200912 1 003
Mengetahui: Ketua Departemen,
Dr. Ir. Agus Buono, M.Si., M.Kom. NIP. 19660702 199302 1 001
Tanggal Lulus:
KATA PENGANTAR Pujian dan syukur kepada Tuhan Yesus atas karunia dan penyertaan-Nya sehingga karya tugas akhir ini dapat terselesaikan dengan baik. Penulis menyampaikan terima kasih kepada: 1 Kedua orang tua, atas doa, nasihat, kesempatan, dan dukungan sehingga penulis dapat menyelesaikan karya ini, 2 Bapak Mushthofa, S.Kom, M.Sc yang telah membimbing hingga terselesaikannya karya ini. Terima kasih atas bimbingan, saran, nasihat, motivasi, dan pelajaran yang diberikan sehingga penulis dapat mencapai tahap ini, 3 Sahabat-sahabat penulis dari Pink House, Wisma Galih, Sigap, rekan Dota, terima kasih atas tawa-canda-cerita, kebersamaan, dan saran selama proses penyelesaian karya ini, 4 Teman-teman seperjuangan Ilkom 44, 5 Segenap dosen dan staf pendukung Departemen Ilmu Komputer, dan 6 Semua pihak yang telah memberikan doa, semangat, dan bantuan dalam penyelesaian karya ini. Penulis menyadari bahwa karya ini masih terdapat kekurangan. Penulis berharap semoga hasil karya dan penelitian ini dapat berguna dan memberikan manfaat.
Bogor, September 2012
Paulus Bangun Kurnianto
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 1 September 1989 dan merupakan bungsu dari tiga bersaudara yang terlahir dari pasangan Basuki dan Muryani. Penulis lulus dari Sekolah Menengah Atas Katolik Ricci II Tangerang di tahun 2007. Di tahun yang sama, Penulis melanjutkan pendidikan di Institut Pertanian Bogor melalui Seleksi Penerimaan Mahasiswa Baru sebagai mahasiswa Departemen Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam IPB. Selama kuliah, Penulis berkesempatan menjadi asisten Mata kuliah Pengantar Pengolahan Citra Digital, berpartisipasi dalam kegiatan IT Today, dan melaksanakan Praktik Kerja Lapangan di PT Pertamina Refinery Unit VI Balongan Indramayu.
DAFTAR ISI Halaman DAFTAR TABEL....................................................................................................................... vi DAFTAR GAMBAR .................................................................................................................. vi DAFTAR LAMPIRAN ............................................................................................................... vi PENDAHULUAN ....................................................................................................................... 1 Latar Belakang ........................................................................................................................ 1 Tujuan ..................................................................................................................................... 1 Ruang Lingkup ........................................................................................................................ 1 Manfaat Penelitian ................................................................................................................... 1 TINJAUAN PUSTAKA ............................................................................................................... 1 Logic Programming ................................................................................................................. 1 Answer Set Programming......................................................................................................... 2 Answer Set Programming Syntax.............................................................................................. 2 Answer Set Programming Semantics ........................................................................................ 2 Answer Set Solver .................................................................................................................... 4 METODE PENELITIAN ............................................................................................................. 5 Analisis Permasalahan ............................................................................................................. 5 Praproses Data ......................................................................................................................... 5 Representasi dengan ASP......................................................................................................... 5 Pengembangan Sistem ............................................................................................................. 5 Pengujian Penjadwalan ............................................................................................................ 6 Evaluasi ................................................................................................................................... 6 HASIL DAN PEMBAHASAN..................................................................................................... 6 Permasalahan Penjadwalan Ujian ............................................................................................. 6 Praproses data .......................................................................................................................... 6 Representasi dengan ASP......................................................................................................... 7 Pengembangan Sistem ........................................................................................................... 11 Pengujian Penjadwalan .......................................................................................................... 12 Evaluasi ................................................................................................................................. 12 KESIMPULAN DAN SARAN................................................................................................... 15 Kesimpulan ........................................................................................................................... 15 Saran ..................................................................................................................................... 15 DAFTAR PUSTAKA ................................................................................................................ 15 LAMPIRAN .............................................................................................................................. 17
v
DAFTAR TABEL Halaman 1 2 3 4 5 6 7
Daftar tabel dan deskripsi tabel pada database ..................................................................... 6 Pembagian slot waktu .......................................................................................................... 8 Keterangan gabungan fakultas-fakultas pada dataset kelompok II ...................................... 12 Hasil penjadwalan dataset kelompok I oleh kedua sistem ................................................... 12 Pemakaian memori maksimal setiap dataset kelompok I oleh kedua sistem ........................ 13 Hasil penjadwalan dataset kelompok II oleh kedua sistem.................................................. 14 Pemakaian memori maksimal setiap dataset kelompok II oleh kedua sistem ....................... 14
DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Problem solving dalam ASP. ............................................................................................... 2 Semua interpretasi terhadap program . ............................................................................. 3 Graph dengan 6 nodes dan 17 edges .................................................................................... 4 Ilustrasi answer set dari graph. ............................................................................................ 4 Tahapan metode penelitian .................................................................................................. 5 Diagram alir Sistem Penjadwalan Ujian IPB. ....................................................................... 5 Pengelompokkan data mahasiswa ........................................................................................ 7 Persebaran jadwal................................................................................................................ 8 Grafik jadwal waktu setelah aturan pemerataan .................................................................... 9 Arsitektur Sistem Penjadwalan .......................................................................................... 11 Grafik waktu penjadwalan dataset kelompok I oleh kedua sistem ....................................... 13 Grafik pemakaian memori dataset kelompok I oleh kedua sistem ....................................... 13 Grafik waktu penjadwalan dataset kelompok II oleh kedua sistem...................................... 14 Grafik pemakaian memori dataset kelompok II oleh kedua sistem ...................................... 15
DAFTAR LAMPIRAN Halaman 1 2 3 4 5 6 7
Kode ASP fakta pengambilan oleh grup mahasiswa ........................................................... 18 Kode ASP fakta mata kuliah .............................................................................................. 19 Kode ASP fakta paralel ..................................................................................................... 20 Kode ASP fakta ruangan.................................................................................................... 21 Data ukuran data KRS, banyak mahasiswa, jumlah mata kuliah serta paralel dataset kelompok I ........................................................................................................................ 22 Data ukuran data KRS, banyak mahasiswa, jumlah mata kuliah serta paralel dataset kelompok II....................................................................................................................... 23 Hasil Penjadwalan ............................................................................................................. 24
vi
1
PENDAHULUAN Latar Belakang Penjadwalan adalah sebuah permasalahan komputasional yang banyak terdapat pada institusi, salah satunya adalah IPB. Penjadwalan yang dilakukan di IPB, dalam kasus ini penjadwalan ujian, masih dilakukan secara manual. Hal ini sendiri bukan merupakan hal yang mudah dan hasil yang didapat pun masih kurang baik karena masih terdapat bentrokan waktu pelaksanaan ujian. Bentrokan waktu pelaksanaan ujian adalah ketika terdapat satu atau lebih mahasiswa yang mendapat jadwal ujian untuk dua atau lebih mata kuliah yang berbeda, dan biasanya akan sulit mencari jadwal pengganti dari mata kuliah tersebut. IPB menerapkan sistem Mayor-Minor yang membuat setiap mahasiswa dapat mengambil mata kuliah di luar departemen utamanya (Mayor) melalui program Minor dan Supporting Course. Menurut buku panduan program sarjana IPB edisi 2007, terdapat 36 mayor dan 70 minor di IPB yang membuat semakin beragamnya pengambilan mata kuliah oleh mahasiswa. Hal ini menambah kerumitan dalam pembuatan jadwal ujian. Answer set programming merupakan teknik pemrograman berparadigma deklaratif yang cenderung lebih cepat untuk mendapatkan solusi dari suatu permasalahan dibandingkan dengan pemrograman imperatif (Lifschitz 2008). Pemrograman berparadigma deklaratif bekerja dengan pernyataan-pernyataan logika berupa aturan-aturan dan fakta-fakta untuk mendapatkan solusi dari suatu permasalahan, sedangkan pemrograman berparadigma imperatif bekerja dengan perintah-perintah komputasi yang harus dilakukan oleh komputer untuk permasalahan yang sama. Answer set programming menjadi metode yang sering digunakan untuk penyelesaian masalah secara deklaratif di bidang Knowledge Representation and Reasoning karena kemudahannya dalam pemodelan dan performa yang tinggi dalam penyelesaian permasalahan. Potassco adalah kumpulan tool untuk answer set programming yang dikembangkan di University of Potsdam. Potassco memiliki performa yang baik dan merupakan pemenang dalam The Second Answer Set Programming Competition dengan skor paling tinggi di antara sistem-sistem ASP yang dipertandingkan (Denecker et al. 2009). Penelitian memodelkan
Hunt (2010) berhasil permasalahan penjadwalan
perkuliahan menggunakan Answer Set Programming. Pada penelitian tersebut dilakukan pendaftaran mahasiswa terhadap mata kuliah dan kemudian ditempatkan dengan jadwal yang sesuai. Penelitian sebelumnya oleh Zulkaryanto (2011) telah mengembangkan model penyelesaian permasalahan penjadwalan ujian Program Studi S1 Sistem Mayor-Minor Institut Pertanian Bogor beserta prototipe sistemnya. Penelitian tersebut masih memiliki beberapa kekurangan, yaitu belum adanya mekanisme penjadwalan untuk kelas paralel dan belum mampu menjadwalkan seluruh data KRS. Oleh karena itu, penelitian ini akan memperbaiki representasi logika penjadwalan pada penelitian Zulkaryanto (2011) dengan menambahkan mekanisme penjadwalan untuk kelas paralel serta memperbaiki efisiensi agar dapat menjadwalkan menggunakan data yang lebih besar. Tujuan Tujuan penelitian ini ialah: memperbaiki representasi logika penjadwalan pada penelitian sebelumnya dengan menambahkan mekanisme penjadwalan untuk kelas paralel. memperbaiki efisiensi penjadwalan pada penelitian sebelumnya agar dapat menjadwalkan menggunakan data yang lebih besar. Ruang Lingkup Ruang lingkup dari penelitian ini ialah: Penjadwalan ujian hanya untuk Program Studi S1 Sistem Mayor-Minor Institut Pertanian Bogor pada satu masa ujian semester. Pengembangan sistem terbatas pada pembentukan representasi logika, belum pengembangan sistem informasi lengkap. Manfaat Penelitian Penelitian ini diharapkan dapat menjadi referensi untuk pemodelan dan pengembangan sistem penjadwalan ujian di IPB lebih lanjut.
TINJAUAN PUSTAKA Logic Programming Logic programming adalah sebuah teknik pemrograman dengan paradigma deklaratif yang dikodekan dalam bentuk aturan (rule) dan fakta (fact). Kowalski (1979) menyatakan bahwa sebuah algoritme A terdiri atas
2
komponen logika L dan komponen kontrol C. Komponen logika L merupakan komponen yang menjelaskan logika algoritme dan komponen kontrol C merupakan komponen yang menentukan cara yang digunakan. Secara simbolis ditulis dengan persamaan berikut:
Kowalski (1979) menambahkan bahwa efisiensi dari sebuah algoritme dapat ditingkatkan dengan meningkatkan efisiensi dari komponen kontrol tanpa mengganti komponen logika dan tanpa mengubah arti algoritme tersebut. Answer Set Programming Answer set programming (ASP) merupakan sebuah pemrograman berparadigma deklaratif yang ditujukan untuk permasalahan pencarian yang sulit, seperti NP-hard. Dalam ASP, masalah pencarian direduksi dengan melakukan komputasi stable model dan dengan answer set solver, sebuah program untuk membangkitkan stable model, digunakan untuk melakukan pencarian (Lifschitz 2008). Pada pemrograman menggunakan ASP, algoritme untuk memecahkan sebuah permasalahan tidak perlu dituliskan seperti halnya pada pemrograman imperatif. Hal yang haruslah dilakukan ialah menuliskan aturanaturan yang bersesuaian untuk mendapatkan solusi dari masalah yang dikerjakan. Karena seperti yang telah dikemukakan oleh Kowalski (1979), Algoritme = Logika + Kontrol. Langkah kerja ASP ditunjukkan pada Gambar 1 .
Answer Set Programming Syntax Sintaks dari answer set programming adalah himpunan aturan yang berbentuk: A0 A1, …., Am, Am+1, …, not Am+1, …, not An, dengan n≥ m ≥0, dan setiap Ai (0 ≤ i ≤ n) adalah atom. Sintaks terdiri atas simbol-simbol konstanta dan variabel, simbol predikat, atom, head, dan body. Head bisa terdiri atas disjungsi fakta atau atom. Bagian sebelah kanan adalah body. Body terdiri atas dua jenis yaitu body+ dan body-. Untuk penulisannya dapat diasumsikan bahwa setiap simbol konstanta dan simbol predikat baik string yang dimulai dengan huruf kecil atau kutip dua(“) contohnya: a,b,c. Di sisi lain, simbol variabel boleh string yang dimulai dengan huruf besar, contohnya: X, Y, Z. Berikut adalah contoh dari sebuah sintaks: a V b c, d, not e. Notasi: Head adalah {a,b}, body+ adalah {c,d}, body- adalah {e}. Sebuah model dikatakan safe jika semua yang ada di body+ ada pada head dan semua yang ada di body- tidak ada pada head. Contoh model untuk sintaks di atas adalah: { }, {a}, {a,c}. Bentuk aturan tanpa head disebut integrity constraint atau hard constraint. Aturan dengan minimal satu buah head disebut normal rule. Bentuk aturan dengan head > 1 disebut disjunctive rule. Jika bagian body kosong ( ), aturan disebut fakta. Dalam penulisan, simbol “ ” biasanya dihilangkan. Himpunan dari aturan-aturan tersebut disebut dengan extended disjunctive logic program (EDLP) atau biasa disebut program . Answer Set Programming Semantics
Gambar 1 Problem Solving dalam ASP. Pemrograman pada ASP umumnya menggunakan metode generate-and-test. Program ASP terdiri atas dua bagian utama, yaitu: aturan-aturan untuk membangkitkan solusi-solusi yang mungkin terjadi dan aturanaturan untuk melakukan pengecekan terhadap semua solusi yang terbentuk, apakah memenuhi persyaratan dari permasalahan yang dihadapi. Semua solusi yang berhasil melewati pengecekan adalah jawaban dari permasalahan tersebut atau yang disebut answer set (Lifschitz 2008).
Semantik dari program logika didefinisikan untuk program yang telah bebas dari variabel. Program yang sudah tidak mengandung variabel dapat dikatakan sebagai program ground. Dengan demikian, pertama kali dilakukan ground instantiation pada program , yaitu menghilangkan semua variabel di dalam program . Herbrand Universe dari program dinotasikan dengan merupakan himpunan semua simbol konstanta yang muncul di . Jika tidak terdapat simbol kontanta di , dengan merupakan simbol konstanta yang diambil semena-mena dari , dengan adalah himpunan semua konstanta. Herbrand Base
3
( ) dari program adalah himpunan semua literal ground yang dibangun dari simbol predikat yang muncul di dan simbol konstanta di . Sebuah ground instance pada aturan , dinotasikan dengan yang diperoleh dengan mengganti variabel yang terjadi di dengan simbol konstanta di . Himpunan semua ground instance dari aturan dinotasikan dengan Semantik dari program harus mempertimbangkan program ground positif. Sebuah himpunan dari literal dikatakan konsisten jika dan hanya jika setiap atom memenuhi . Sebuah interpretasi pada program adalah sebuah himpunan bagian konsisten dari . Sebuah himpunan dari literal memenuhi sebuah aturan jika dan hanya jika dengan dan Sebuah himpunan memenuhi program jika dan hanya jika literal memenuhi semua aturanaturan di dalam . Sebuah model dari program merupakan sebuah interpretasi dengan memenuhi . Sebuah answer set dari program ground positif merupakan merupakan minimal model dari . Untuk memperluas definisi semantik pada program dengan negasi, dikenal transformasi Gelfond-Lifschitz (transformasi GL) untuk membebaskan negasi pada program . Pada transformasi GL dari program P, interpretasi I adalah atom dari program P. Transformasi GL yang dilakukan ini dilambangkan dengan dengan: a Menghapus semua aturan r yang mempunyai literal negatif pada tubuh aturan tersebut dengan b Menghapus semua literal negatif dari semua aturan yang tersisa Sebuah answer set dari program adalah (dengan ) jika adalah answer set dari . Semua himpunan answer set dari program dinotasikan dengan Program dikatakan konsisten jika mempunyai paling tidak satu answer set ( ) dan selainnya dikatakan tidak konsisten. Pada kasus khusus untuk program definite Horn ( ) diketahui hanya memiliki satu answer set yang dapat ditemukan dengan mencari fixpoint terhadap program . Fixpoint terhadap disebut juga immediate consequence dan dinotasikan dengan .
didefinisikan sebagai interpretasi dari program definite Horn. Operator immediate consequence didefinisikan sebagai | . Selanjutnya , dengan didefinisikan sebagai dan . monoton dan mempunyai satu least fixpoint, dinotasikan dengan . Sebagai contoh, di bawah ini adalah sebuah program : a b c c
p, not b p, not a a b p
Kemungkinan model-model yang sesuai untuk program di atas dapat dilihat dari interpretasi pada Gambar 2. a, b, c, p
a,b,c
a,b
a,b,p
a,c
a,c,p
a,p
a
b,c
b
c
b,c,p
b,p
c,p
p
Ø
Gambar 2 Semua interpretasi terhadap program . Dari program tersebut diketahui bahwa berupa fakta dan selalu bernilai benar serta harus selalu muncul dalam setiap model. Untuk menentukan stable model dilakukan transformasi GL dan menentukan apakah interpretasi atau dinotasikan . Selanjutnya dipilih , , , , , , dan . Pada , dilakukan transformasi GL terhadap program sehingga diperoleh : a b c c
p p a b p
Fixpoint dari ( {a,b,c,p} sehingga diperoleh
) adalah . Hal
4
ini berarti bahwa bukan merupakan stable model, sedangkan untuk diperoleh :
buah node yang tersusun dalam sebuah graph seperti pada Gambar 3.
p a b
a c c p
Kemudian, diperoleh sehingga Jadi, merupakan stable model. Dengan cara yang sama untuk semua interpretasi diperoleh dan sebagai stable model dari program dan juga merupakan answer set dari program . Answer Set Solver Answer set solver adalah perangkat yang dikembangkan untuk mengevaluasi input pemrograman logika berbasis ASP. Beberapa answer set solver yang telah dikembangkan adalah Lparse (Gelfond & Lifschitz 1991), DLV (Eiter et al. 2006), Potassco (Gebser et al. 2011), SMODELS (Simons et al. 2002), dan ASSAT (Lin & Zao 2002). Penelitian ini menggunakan Clingo sebagai answer set solver dalam pengembangan sistem. Potassco, singkatan dari Potsdam Answer Set Solving Collection, adalah sebuah proyek open-source yang terdiri atas kumpulan tool untuk answer set programming dan dikembangkan di University of Potsdam. Clingo sendiri adalah gabungan dua tool utama pada Potassco, yaitu grounder Gringo dan solver Clasp. Hal ini membuat Clingo memiliki semua fitur yang terdapat pada Gringo dan Clasp (Gebser et al. 2011). Clasp mendukung beberapa perluasan bahasa seperti aturan cardinality constraint dan condition. Cardinality constraint berbentuk: l {A1, … , Am} u
Gambar 3 Graph dengan 6 nodes dan 17 edges. Graph tersebut direpresentasikan dengan fakta-fakta berikut: % Nodes node(1..6). % Edges edge(1,2;3;4). edge(2,4;5;6). edge(3,1;4;5). edge(4,1;2). edge(5,3;4;6). edge(6,2;3;5). Graph 3-Coloring menggunakan metode generate and test direpresentasikan dengan aturan-aturan berikut: % Generate color(X,1) v color(X,2) v color(X,3) :- node(X). % Test :- edge(X,Y), color(X,C),color(Y,C). Salah satu answer set yang terbentuk adalah sebagai berikut: Answer: 1 color(1,2) color(2,1) color(3,1) color(4,3) color(5,2) color(6,3) Answer set tersebut diilustrasikan dengan Gambar 4.
yang bermakna untuk setiap model pada answer set, terdapat atom-atom dari {A1, … , Am} sejumlah minimal l dan maksimal u. Condition berbentuk: {A1 : B1, . . . , Am : Bm} dengan B1, … , Bm digunakan untuk membatasi pembentukan variabel yang muncul di A1, …, Am. Berikut diberikan contoh penyelesaian sebuah permasalahan menggunakan ASP. Permasalahan yang digunakan adalah Graph 3Coloring (Johnson 1979). Misalkan terdapat 6
Gambar 4 Ilustrasi answer set dari graph.
5
METODE PENELITIAN Penelitian akan dilakukan dalam beberapa tahap. Gambar 5 menunjukkan tahapan dari metode penelitian.
penjadwalan waktu, akan dilakukan pemerataan jumlah jadwal ujian per harinya di setiap set jadwal yang akan dibentuk. Pengembangan Sistem Pada tahap ini dilakukan perancangan sistem dengan bahasa pemrograman imperatif yang diintegrasikan dengan ASP. Sistem akan melakukan pengolahan data dari pengguna, menuliskan aturan-aturan logika, melakukan penjadwalan, dan menampilkan jadwal yang terbentuk. Sistem penjadwalan secara garis besar digambarkan dengan diagram alir pada Gambar 6.
Gambar 5 Tahapan metode penelitian. Analisis Permasalahan Pada tahap ini dilakukan analisis permasalahan ujian di IPB, data yang digunakan, dan kebutuhan perangkat lunak. Setelah dilakukan analisis akan diketahui persyaratan-persyaratan pada penjadwalan ujian di IPB, pengolahan data yang digunakan, serta sistem yang akan dibuat. Praproses Data Pada tahap ini dilakukan analisis terhadap data yang digunakan, yaitu data semester genap tahun ajaran 2010-2011. Tabel-tabel data yang diperlukan untuk melakukan penjadwalan dibuat. Representasi dengan ASP Pada tahap ini dilakukan penulisan permasalahan penjadwalan secara logika. Penjadwalan akan dibagi menjadi dua tahap, yaitu tahap penjadwalan waktu dan dilanjutkan dengan tahap penjadwalan ruangan. Pada tahap
Gambar 6 Diagram alir Sistem Penjadwalan Ujian IPB. Lingkungan perangkat pengembangan sistem adalah:
lunak
dalam
Sistem operasi: Windows 7 Home Premium 64-Bit. IDE: Visual Studio 2010 Professional. Bahasa pemrograman: C# .Net. Answer Set Solver: Potassco. Office Tools: Microsoft Excel 2010. DBMS: Microsoft Access 2010. Lingkungan perangkat pengembangan sistem adalah:
keras
dalam
Prosesor: Intel Core2 Duo P8700 @ 2.53 GHz. RAM: 4 GB. HDD: 320 GB.
6
Pengujian Penjadwalan Pada tahap ini dilakukan penjadwalan menggunakan sistem dan dataset dengan banyak pengambilan yang bervariasi. Pada tahap ini dilakukan juga penjadwalan menggunakan sistem yang telah dibuat pada penelitian sebelumnya oleh Zulkaryanto (2011). Evaluasi Hasil penjadwalan akan dievaluasi apakah setiap paralel mata kuliah telah terakomodasi dalam jadwal yang terbentuk dan bagaimana distribusi mata kuliah per harinya serta dilakukan pencatatan durasi proses penjadwalan untuk setiap dataset sampai menghasilkan answer set atau tidak. Proses dinyatakan time out jika durasi proses melebihi dua jam. Pada penelitian ini juga dilakukan pencatatan memori maksimum yang digunakan saat pemrosesan kode ASP oleh Potassco.
HASIL DAN PEMBAHASAN Permasalahan Penjadwalan Ujian Permasalahan yang kerap ditemui dalam penjadwalan ujian di IPB adalah adanya bentrokan. Ada dua macam bentrokan, yaitu bentrokan waktu dan ruangan. Bentrokan waktu terjadi apabila seseorang atau sekelompok mahasiswa mendapatkan jadwal pelaksanaan ujian untuk dua atau lebih mata kuliah yang berbeda, di hari dan waktu yang sama. Bentrokan ruangan adalah terdapat jadwal pelaksanaan ujian di suatu ruangan, untuk dua atau lebih mata kuliah yang berbeda, di hari dan waktu yang sama. Beberapa persyaratan yang harus dipenuhi dalam permasalahan penjadwalan ujian pada Sistem Mayor-Minor IPB ialah: 1 Hanya ada satu ujian yang dapat berlangsung dalam satu ruangan dalam satu waktu tertentu. 2 Satu kelompok mahasiswa hanya mengikuti satu ujian dalam satu waktu tertentu. 3 Pelaksanaan ujian kelas-kelas paralel suatu mata kuliah berlangsung serentak tetapi dengan ruangan pelaksanaan yang berbeda. 4 Setiap ruangan memiliki keterbatasan kapasitas daya tampung mahasiswa. 5 Waktu pelaksanaan ujian selama dua belas hari. Praproses data Pada penelitian ini, data sumber yang digunakan adalah data KRS semester genap
tahun ajaran 2010-2011. Pada penelitian ini juga dibuat sebuah database yang berisi tabel-tabel data yang diperlukan sistem untuk melakukan penjadwalan. Daftar tabel beserta deskripsinya dapat dilihat pada Tabel 1. Tabel 1 Daftar tabel dan deskripsi tabel pada database Nama Tabel
Deskripsi
Atribut
Menyimpan data asli pengambilan nrp, kode_mk mata kuliah, krs (P), kelas kuliah kelaskuliah (paralel), dan nrp mahasiswa Menyimpan mk_tpb data mata kode_mk (P) kuliah TPB Menyimpan data mata kuliah yang mk_tdk_ujian kode_mk (P) tidak melakukan ujian Menyimpan data mata mk_ujian kuliah yang kode_mk (P) melakukan ujian Menyimpan data pengambilan mata kuliah nrp, kode_mk mk_krs_ujian yang (P) diujiankan dan nrp mahasiswa Menyimpan data jumlah data_ruangan, peserta tiap mk_peserta paralel (P), mata kuliah peserta dan paralelnya Menyimpan data kode koderuang (P), ruangan, namaruang, data_ruangan nama lokasi, ruangan, kapasitas lokasi dan kapasitasnya Tabel mk_krs_ujian didapat dari data KRS dengan mata kuliah sama dengan mata kuliah pada tabel mk_ujian. Tabel mk_peserta
7
didapatkan dari data KRS dan tabel mk_krs_ujian dengan menghitung banyaknya mata kuliah dengan paralel yang mata kuliahnya sama dengan mata kuliah pada tabel mk_krs_ujian.
Predikat am menyatakan pengambilan suatu mata kuliah, yang dinyatakan dengan kode, oleh suatu grup. Maka, pernyataan di atas bermakna grup pengambilan g7 mengambil mata kuliah kom333.
Data pengambilan mata kuliah oleh mahasiswa yang didapat dari tabel mk_krs_ujian dibentuk menjadi kelompokkelompok berdasarkan pengambilan mata kuliah yang sama dan setiap mahasiswa dapat menjadi anggota dari banyak kelompok. Contohnya, kelompok G1 berisi semua mahasiswa yang mengambil mata kuliah MK001 dan MK002, kelompok G2 berisi semua mahasiswa yang mengambil mata kuliah MK002 dan MK003, dan kelompok G3 berisi semua mahasiswa yang mengambil MK003. Contoh ini diilustrasikan pada Gambar 7. Tujuan pembentukan data pengambilan ini adalah untuk memperkecil ukuran data.
Fakta mata kuliah berisi mata kuliah dan dimodelkan dengan bentuk: mk(bik304). Pernyataan di atas bermakna kode bik304 adalah mata kuliah yang diujiankan. Fakta paralel berisi mata kuliah dengan paralel dan jumlah peserta dan dimodelkan dengan bentuk: mk(bio222,1399,104). Pernyataan di atas bermakna terdapat mata kuliah bio222, paralel bernomor 1399 dengan jumlah peserta sebanyak 104 mahasiswa. Fakta ruangan berisi kode ruangan dan kapasitas yang dimodelkan dengan bentuk: ruang(a00000b1,60). Pernyataan di atas bermakna terdapat ruangan dengan kode a00000b1 yang mempunyai kapasitas peserta sebesar 60 orang. 2 Representasi penjadwalan
Gambar 7 Pengelompokkan data mahasiswa. Data kelompok mahasiswa yang telah terbentuk disebut sebagai data pengambilan dan data dari tabel mk_peserta dan tabel ruangan akan digunakan oleh sistem untuk membentuk fakta-fakta yang digunakan pada penjadwalan. Representasi dengan ASP Representasi dengan ASP terbagi menjadi dua bagian, yaitu representasi input dan representasi penjadwalan. Representasi input adalah pembentukan kode ASP untuk faktafakta dari data dan representasi penjadwalan adalah pembentukan kode ASP untuk aturanaturan dan persyaratan penjadwalan. 1 Representasi input Fakta-fakta (facts) yang dibentuk terdiri atas pengambilan, mata kuliah, paralel, dan ruangan. Fakta kelompok pengambilan didapat dari pengelompokkan data mahasiswa dan dimodelkan dengan bentuk: am(g7,kom333).
Representasi penjadwalan terdiri atas pembentukan kode ASP untuk kendala-kendala (constraints) dan aturan-aturan (rules). Aturan-aturan penjadwalan adalah kode ASP yang digunakan untuk membangkitkan set jadwal, yang terbagi menjadi dua bagian, yaitu aturan-aturan untuk menjadwalkan waktu ujian dan ruangan ujian. Pada aturan penjadwalan waktu, akan dibentuk kumpulan jadwal yang terdiri atas semua mata kuliah, waktu, dan hari pelaksanaan. Untuk setiap jadwal yang terbentuk, setiap mata kuliah mendapat jadwal waktu dan hari tepat satu kali. Tidak ada jadwal untuk dua atau lebih mata kuliah yang sama. Pada pembentukan jadwal, suatu mata kuliah akan diberikan suatu slot waktu dan hari pelaksanaan. Banyak hari yang digunakan ialah 12 hari dan setiap harinya akan dibagi menjadi empat slot waktu. Penelitian ini menggunakan 4 slot waktu dalam satu hari dengan lama ujian adalah 2 jam. Pembagian slot waktu dapat dilihat pada Tabel 2. Hasil dari tahap penjadwalan waktu ini akan digunakan sebagai input pada tahap penjadwalan ruangan. Hasil dari penjadwalan ruangan adalah jadwal lengkap setiap mata kuliah dan paralel yang telah memiliki waktu, hari, dan ruangan.
8
Tabel 2 Pembagian slot waktu Waktu 08.00 – 10.00 10.00 – 12.00 13.00 – 15.00 15.00 – 17.00
Slot 1 2 3 4
Berikut adalah aturan untuk membentuk jadwal: 1 { ja(M, 1..4, 1..12) } 1 :- mk(M). Predikat ja menyatakan set jadwal ujian untuk mata kuliah yang dibangkitkan dan predikat mk menyatakan fakta mata kuliah yang akan dijadwalkan. Pernyataan tersebut bermakna jika terdapat mata kuliah M, buat jadwal ke dalam suatu slot waktu dan hari. Slot waktu dinyatakan melalui pernyataan 1..4 yang berarti terdapat satu hingga empat kemungkinan slot. Slot hari dinyatakan melalui pernyataan 1..12 yang berarti terdapat satu hingga dua belas kemungkinan slot. Aturan tersebut akan menghasilkan banyak jadwal waktu. Beberapa jadwal pertama yang dihasilkan oleh aturan tersebut memiliki karakteristik jadwal yang jumlah mata kuliahnya tidak merata disetiap hari ujian. Sebagai contoh, jadwal pertama yang jika digambarkan dalam grafik terlihat seperti pada Gambar 8.
Jadwal waktu yang memiliki persebaran jumlah mata kuliah tidak merata seperti pada Gambar 8 akan sangat sulit pada tahap penjadwalan ruangan untuk menghasilkan sebuah jadwal yang lengkap. Untuk menghasilkan jadwal lengkap pada tahap penjadwalan ruangan dibutuhkan set jadwal waktu yang memiliki persebaran cukup merata. Oleh karena itu, perlu ditambahkan suatu aturan khusus yang berguna untuk memeratakan jumlah mata kuliah per harinya. Pada dasarnya, untuk mendapatkan jadwal waktu yang merata, tanpa menggunakan aturan-aturan tertentu pun dapat dilakukan, tetapi hal tersebut akan membutuhkan waktu lebih. Pemerataan jumlah mata kuliah per harinya dilakukan dengan menentukan jumlah maksimal mata kuliah per harinya pada suatu batas. Batas tersebut ditentukan dengan membagi jumlah seluruh mata kuliah yang melakukan ujian dengan banyaknya hari pelaksanaan ujian dan dilakukan pembulatan ke atas. Formulanya sebagai berikut:
⌈ ⌉ dengan
B : banyak mata kuliah per hari. M : jumlah mata kuliah yang diujiankan. H : jumlah hari ujian.
Gambar 8 Persebaran jadwal.
9
Pada aturan pemerataan, set-set jadwal yang telah dibentuk pada aturan pembentukan jadwal akan diperiksa jumlah mata kuliah per harinya. Apabila melebihi batas, buang set jadwal tersebut. Sebagai contoh, berikut ini akan diberikan aturan-aturan pemerataan yang dibentuk dengan ketentuan jumlah mata kuliah yang diujiankan sebanyak 398 buah dan jumlah hari ujiannya sebanyak 12 hari. Dari formula yang telah disebutkan sebelumnya, perhitungan banyak mata kuliah per harinya adalah 398 dibagi dengan 12. Didapatkan angka 33.1667, lalu dilakukan pembulatan ke atas sehingga banyak mata kuliah per harinya sebesar 34 buah. Lalu, batas yang digunakan dalam aturan ialah 35 karena batas maksimal jumlah mata kuliah per harinya ialah 34. Aturan pemerataan akan bekerja dengan cara jika pada suatu set jadwal yang terbentuk terdapat 35 atau lebih jadwal mata kuliah pada suatu hari yang sama, buang set jadwal tersebut. Dari penggunaan aturan pemerataan tersebut, akan terbentuk set jadwal yang jumlah mata kuliah per harinya maksimal 34 atau kurang. Berikut ini adalah aturan-aturan untuk pemerataan jadwal ujian perharinya: :::::::::-
35 35 35 35 35 35 35 35 35
{ { { { { { { { {
ja(_,_,1) ja(_,_,2) ja(_,_,3) ja(_,_,4) ja(_,_,5) ja(_,_,6) ja(_,_,7) ja(_,_,8) ja(_,_,9)
}. }. }. }. }. }. }. }. }.
:- 35 { ja(_,_,10) }. :- 35 { ja(_,_,11) }. :- 35 { ja(_,_,12) }. Pernyataan-pernyataan tersebut, yang merupakan aturan-aturan yang berbentuk cardinality constraint, digunakan untuk memeriksa set jadwal yang dibangkitkan pada hari tertentu. Pernyataan-pernyataan tersebut bekerja dengan cara menghitung banyak predikat dengan atribut yang sama pada set jadwal yang terbentuk dan membuang set jadwal tersebut jika kondisi batas terpenuhi. Gambar 9 merupakan grafik yang menggambarkan sebuah jadwal waktu yang telah menggunakan aturan pemerataan. Pada gambar terlihat jadwal waktu yang terbentuk tidak sepenuhnya memiliki jumlah mata kuliah yang sama per harinya. Hal ini dapat disebabkan oleh jumlah mata kuliah itu sendiri tidak sebanyak slot jadwal yang disediakan, dalam hal ini 34 per harinya selama 12 hari. Jadwal waktu yang telah merata selanjutnya akan digabungkan dengan data pengambilan yang merupakan salah satu input. Setelah digabungkan dengan pengambilan, dilakukan pembuangan variabel grup dan penyaringan agar dapat dilakukan pemeriksaan dengan kendala penjadwalan waktu. Aturan-aturannya sebagai berikut: jw(G,M,J,H) :- ja(M,J,H),am(G,M). jw1(M,J,H) :- jw(_,M,J,H). #hide. #show jw1/3.
Gambar 9 Grafik jadwal waktu setelah aturan pemerataan.
10
Predikat jw menyatakan set mata kuliah yang telah terjadwal dengan grup pengambilan yang berkaitan, predikat ja menyatakan mata kuliah yang telah terjadwal, dan predikat am menyatakan fakta pengambilan mata kuliah oleh grup. Pernyataan pada baris 1 merupakan aturan untuk menggabungkan set jadwal yang telah terbentuk dengan fakta pengambilan untuk diperiksa dengan persyaratan penjadwalan yang pertama. Predikat jw1 menyatakan mata kuliah yang telah terjadwal dan telah memenuhi persyaratan penjadwalan yang pertama. Pernyataan pada baris 2 melakukan pengubahan dari predikat jw ke predikat jw1 dan membuang variabel G. Set jadwal yang sudah memenuhi persyaratan akan disaring menggunakan aturan pada baris 3 dan 4 sehingga hanya predikat jw1 yang akan ditampilkan dan disimpan sebagai fakta untuk melakukan penjadwalan ruangan.
Penempatan ruangan saat pembangkitan memperhatikan kapasitas ruangan dan jumlah peserta ujian dari setiap paralel mata kuliah. Sebagai contoh, jika kapasitas ruangan A melebihi jumlah peserta suatu mata kuliah dengan paralel X, paralel X tersebut dapat ditempatkan di ruangan A. Hal ini dinyatakan pada aturan menggunakan kondisi Kap > P.
Pada aturan untuk menjadwalkan ruangan, hasil jadwal waktu yang telah dihasilkan oleh aturan penjadwalan waktu akan dibentuk jadwal ruangan yang terdiri atas mata kuliah, kelas paralel, jumlah peserta, kode ruangan, dan kapasitas ruangan. Mata kuliah yang telah memiliki waktu dan hari pelaksanaan ujian dengan setiap kelas paralelnya akan diberikan suatu slot ruangan yang kapasitas ruangan tersebut melebihi banyak peserta dalam kelas paralel mata kuliah tersebut.
Predikat jd menyatakan suatu mata kuliah dan paralel yang telah terjadwal pada suatu ruangan, jam, dan hari. Pernyataan pada baris 2 menggabungkan set mata kuliah dan ruangan yang sudah terbentuk dengan set jadwal waktu dari tahap sebelumnya untuk diperiksa dengan persyaratan penjadwalan kedua. Penggunaan predikat jw1 akan mengakibatkan set jadwal yang terbentuk, untuk setiap paralel berbeda tetapi memiliki mata kuliah yang sama, memiliki waktu dan hari ujian bersamaan. Pernyataan pada baris 3 dan 4 akan menyaring hasil penjadwalan sehingga hanya predikat jd yang digunakan oleh sistem untuk ditampilkan sebagai jadwal lengkap.
Aturannya sebagai berikut: 1
1 { jr(M,Par,P,Kr,Kap) : ruang(Kr,Kap) : Kap > P } 1 :- mk(M,Par,P), jw1(M,_,_).
Predikat jr menyatakan set jadwal mata kuliah dan ruangan yang dibangkitkan, predikat mk adalah fakta berisi mata kuliah, paralel dan jumlah pesertanya, predikat ruang adalah fakta berisi kode ruangan dan kapasitasnya. Variabel Par adalah paralel suatu mata kuliah, variabel P adalah jumlah peserta pada paralel tersebut, variabel Kr adalah suatu kode ruangan, dan Kap adalah kapasitas ruangan tersebut. Pernyataan tersebut digunakan untuk membangkitkan set jadwal ruangan dengan jadwal ruangan adalah jadwal ujian untuk setiap kelas paralel mata kuliah yang telah memiliki ruangan, waktu dan hari ujian. Pernyataan tersebut menggunakan perluasan bahasa condition dan bermakna untuk setiap mata kuliah yang telah memiliki jadwal waktu, tempatkan setiap paralel mata kuliah tersebut ke dalam ruangan yang terdapat pada fakta ruang dan memiliki kapasitas melebihi jumlah peserta.
Jadwal ruangan yang telah terbentuk selanjutnya akan digabungkan dengan jadwal waktu menjadi jadwal lengkap dan selanjutnya dilakukan penyaringan agar dapat dilakukan pemeriksaan dengan kendala penjadwalan ruangan. Aturan-aturannya adalah sebagai berikut: 2 3 4
jd(M,Par,P,Kr,J,H) :jr(M,Par,P,Kr,_), jw1(M,J,H). #hide. #show jd/6.
Kendala-kendala adalah kode yang akan memeriksa jadwal yang dibentuk berdasarkan persyaratan penjadwalan ujian. Ada beberapa kendala yang dibentuk untuk persyaratan penjadwalan, yaitu: 1 Kendala yang menyatakan tidak boleh ada suatu grup pengambilan yang mendapat jadwal waktu dan hari yang sama untuk dua atau lebih mata kuliah yang berbeda. Kendala tersebut dimodelkan sebagai berikut: :- jw(G,M1,J,H),jw(G,M2,J,H), M1 != M2. Predikat jw menyatakan jadwal yang telah dibangkitkan pada tahap penjadwalan waktu ujian dan pernyataan tersebut dapat bermakna suatu mata kuliah yang diambil oleh suatu grup yang dijadwalkan pada suatu jam dan hari. Variabel G menyatakan grup pengambilan, variabel M1 dan M2 menyatakan mata kuliah, variabel J menyatakan jam/waktu ujian, dan
11
variabel H menyatakan hari ujian. Penyataan kendala tersebut bermakna untuk set jadwal waktu yang terbentuk, jika terdapat dua atau lebih mata kuliah yang berbeda pada jam dan hari yang sama serta diambil oleh grup yang sama, buang set jadwal tersebut. 2 Kendala yang menyatakan tidak boleh terdapat dua atau lebih mata kuliah yang berbeda terjadwalkan pada satu ruangan di waktu dan hari yang sama serta kendala yang menyatakan tidak boleh terdapat paralel berbeda dari mata kuliah yang sama terjadwalkan di satu ruangan yang sama. Kendala ini dimodelkan sebagai berikut: 1
:- jd(M1,_,_,Kr,J,H), jd(M2,_,_,Kr,J,H), M1 != M2.
2
:- jd(M,Par1,_,Kr,_,_), jd(M,Par2,_,Kr,_,_), Par1 != Par2.
Predikat jd menyatakan jadwal yang telah dibangkitkan pada tahap penjadwalan ruangan. Variabel M, M1, dan M2 menyatakan mata kuliah, variabel Kr menyatakan kode ruangan, variabel J menyatakan jam/waktu ujian, variabel H menyatakan hari ujian, dan variabel Par1, Par2 menyatakan paralel suatu mata kuliah.
Penyataan pada baris 1 dapat bermakna untuk set jadwal ruangan yang terbentuk, jika terdapat dua atau lebih mata kuliah yang berbeda terjadwal pada ruangan, waktu dan hari ujian yang sama, buang set jadwal tersebut. Pernyataan pada baris 2 dapat bermakna untuk set jadwal ruangan yang terbentuk, jika terdapat dua atau lebih paralel berbeda dari mata kuliah yang sama, terjadwal pada suatu ruangan yang sama, buang set jadwal tersebut. Pengembangan Sistem Pada penelitian ini telah dibuat prototipe sistem penjadwalan ujian yang berbasis ASP dan C# .Net. Pada antarmuka sistem, pengguna dapat memberikan input berupa data KRS, menentukan tanggal mulai dan berakhir ujian, serta menentukan banyak jadwal yang akan dibuat. Hasil dari sistem penjadwalan ujian tersebut berupa tabel jadwal ujian yang ditampilkan pada antarmuka sistem. Pada penelitian ini, bagian input data, pengolahan data, pembentukan kode ASP, eksekusi kode ASP, dan output berupa jadwal ditangani oleh sistem dengan bahasa C# .Net. Arsitektur sistem penjadwalan dapat dilihat pada Gambar 10.
Gambar 10 Arsitektur Sistem Penjadwalan.
12
Pengujian Penjadwalan Pada penelitian dataset untuk Kelompok I berisi dan kelompok II beberapa fakultas.
ini dibentuk dua kelompok pengujian penjadwalan. data setiap fakultas di IPB berisi data gabungan dari
Setiap dataset mengandung pengambilan mata kuliah oleh mahasiswa dan kelas kuliah (paralel). Keterangan gabungan fakultasfakultas pada dataset kelompok II dapat dilihat pada Tabel 3 dan untuk ukuran data KRS, banyak mahasiswa, jumlah mata kuliah, serta paralel dataset kelompok I dapat dilihat pada Lampiran 5 dan dataset kelompok II pada Lampiran 6. Tabel 3 Keterangan gabungan fakultas-fakultas pada dataset kelompok II Nomor gabungan
Fakultas
1
FAPERTA, FMIPA FAPERTA, FMIPA, FEM FKH, FAPET FKH, FAPET, FAHUTAN FPIK, FMIPA FPIK, FMIPA, FEM FAPET, FKH, FEMA FAPET, FKH, FEMA, FEM FAHUTAN, FEM FATETA, FMIPA FATETA, FMIPA, FEM
2 3 4 5 6 7 8 9 10 11 12
FMIPA, FEM
13
FEM, FEMA Seluruh fakultas di IPB
semua
jadwal, waktu proses, dan pemakaian memori saat melakukan proses. Pada penelitian ini, dilakukan juga penjadwalan menggunakan sistem penjadwalan yang telah dibuat pada penelitian sebelumnya oleh Zulkaryanto (2011), menggunakan kedua kelompok dataset yang sama. Hal ini dilakukan untuk melihat perbandingan sistem penjadwalan yang dibuat pada penelitian kali ini dengan sistem penjadwalan sebelumnya, dalam hal waktu pemrosesan dan pemakaian memori pada lingkungan yang sama. Proses penjadwalan dilakukan sebanyak tiga kali untuk kedua kelompok dataset, dan dilakukan pencatatan lama proses yang diperlukan serta berhasil tidaknya pembuatan jadwal. Sistem dikatakan berhasil jika sistem menghasilkan jadwal ujian terhadap dataset yang diproses dan tidak berhasil jika sistem tidak menghasilkan jadwal ujian atau melebihi batas waktu (time out). Berikut ini adalah data hasil penjadwalan dari kedua kelompok dataset dari segi durasi proses saat melakukan penjadwalan, keberhasilan pembuatan jadwal, dan pemakaian memori. Rataan lama proses merupakan ratarata lama pemrosesan sistem dalam mengeksekusi kode ASP dan dilakukan sebanyak tiga kali. Rataan pemakaian memori maksimal merupakan rata-rata pemakaian memori maksimal dalam mengeksekusi kode ASP oleh sistem dan dilakukan sebanyak tiga kali. Data hasil penjadwalan dataset kelompok I dapat dilihat pada Tabel 4 dan data pemakaian memori pada Tabel 5. Grafik untuk Tabel 4 ditunjukkan pada Gambar 11 dan grafik untuk Tabel 5 ditunjukkan pada Gambar 12.
Tabel 4 Hasil penjadwalan dataset kelompok I oleh kedua sistem Sistem
Evaluasi Pada penelitian ini, hasil penjadwalan oleh sistem dan kinerja sistem dievaluasi. Evaluasi hasil penjadwalan memperhatikan dua hal, yaitu penjadwalan untuk setiap paralel mata kuliah dan persebaran jumlah jadwal ujian mata kuliah perharinya. Hasil penjadwalan untuk kedua dataset yang digunakan telah berhasil mengakomodasi paralel mata kuliah dalam jadwal yang terbentuk. Hasil penjadwalan yang dibuat dari salah satu dataset dapat dilihat pada Lampiran 7. Untuk evaluasi kinerja sistem, aspek-aspek yang diperhatikan adalah keberhasilan membuat
Fakultas
FAPERTA FKH FPIK FAPET FAHUTAN FATETA FMIPA FEM FEMA
Rataan lama proses (menit) 0.0124 0.0171 0.0281 0.0095 0.0271 0.0190 0.0411 0.0471 0.0253
Suk -ses Ya Ya Ya Ya Ya Ya Ya Ya Ya
Sistem Zulkaryanto (2011) Rataan lama Sukproses ses (menit) 1.3221 Ya 0.5206 Ya 8.9280 Ya 0.1657 Ya 14.2990 Ya 2.0830 Ya 12.1394 Ya 1.7631 Tidak 1.7706 Ya
13
Tabel 5 Pemakaian memori maksimal setiap dataset kelompok I oleh kedua sistem
Fakultas
FAPERTA FKH FPIK FAPET FAHUTAN FATETA FMIPA FEM FEMA
Rataan pemakaian memori maks. (MB) Sistem Sistem Zulkaryanto (2011) 18.767 235.544 23.239 144.999 42.801 648.170 17.363 90.630 35.246 1130.00 21.245 356.388 68.791 1013.735 60.000 1609.824 25.083 348.069
Dari data tersebut, terlihat bahwa untuk penjadwalan dataset kelompok I, terjadi peningkatan efisiensi dari segi waktu pemrosesan dan pemakaian memori. Rata-rata efisiensi yang dilakukan sistem untuk waktu pemrosesan sebesar 98.23% dan rata-rata efisiensi untuk pemakaian memori oleh sistem sebesar 91.49%. Data hasil penjadwalan dataset kelompok II dapat dilihat pada Tabel 6 dan data pemakaian memori pada Tabel 7. Grafik untuk Tabel 6 ditunjukkan pada Gambar 13 dan grafik untuk Tabel 7 ditunjukkan pada Gambar 14.
Gambar 11 Grafik waktu penjadwalan dataset kelompok I oleh kedua sistem.
Gambar 12 Grafik pemakaian memori dataset kelompok I oleh kedua sistem.
14
Tabel 6 Hasil penjadwalan dataset kelompok II oleh kedua sistem
Gabung -an Fakultas
1 2 3 4 5 6 7 8 9 10 11 12 13 semua
Sistem Rataan lama proses (menit) 0.0613 0.1555 0.0260 0.0524 0.0863 0.1880 0.0547 0.1501 0.0893 0.0807 0.1406 0.1167 0.1053 0.7337
Sukses
Ya Ya Ya Ya Ya Ya Ya Ya Ya Ya Ya Ya Ya Ya
Sistem Zulkaryanto (2011) Rataan lama Sukproses ses (menit) 1.8061 Tidak 0.7870 Tidak 1.2624 Ya 22.382 Ya 1.7935 Tidak 0.8360 Tidak 5.8145 Ya 1.1216 Tidak 1.0552 Tidak 22.916 Ya 4.2480 Tidak 1.1070 Tidak 1.0380 Tidak 4.0621 Tidak
Dari data tersebut, untuk penjadwalan data gabungan semua fakultas, terjadi peningkatan efisiensi untuk waktu pemrosesan sebesar 33.72% dan pemakaian memori sebesar 51.93%. Sistem juga berhasil menghasilkan jadwal untuk setiap dataset, sedangkan sistem Zulkaryanto (2011) dapat menemukan jadwal
sebanyak 4 dari 14 dataset di kelompok II. Peningkatan efisiensi tersebut terjadi karena pembagian penjadwalan menjadi dua tahap penjadwalan. Pembagian tersebut menurunkan kompleksitas dari permasalahan penjadwalan ujian ini. Tabel 7 Pemakaian memori maksimal setiap dataset kelompok II oleh kedua sistem
Gabungan Fakultas 1 2 3 4 5 6 7 8 9 10 11 12 13 semua
Rataan pemakaian memori maks. (MB) Sistem Sistem Zulkaryanto (2011) 66.485 1779.154 192.822 1941.463 32.865 279.519 76.586 1478.881 92.868 1292.566 240.345 1882.329 76.635 714.625 185.535 1733.382 126.663 1692.430 124.271 1696.690 199.000 1695.379 170.400 1730.613 136.050 1601.208 818.760 1703.378
Gambar 13 Grafik waktu penjadwalan dataset kelompok II oleh kedua sistem.
15
Gambar 14 Grafik pemakaian memori dataset kelompok II oleh kedua sistem.
KESIMPULAN DAN SARAN Kesimpulan Penelitian ini telah berhasil memperbaiki representasi logika penjadwalan pada penelitian sebelumnya dengan adanya penambahan mekanisme penjadwalan kelas paralel pada permasalahan penjadwalan ujian Program Studi S1 Sistem Mayor-Minor Institut Pertanian Bogor. Penelitian ini juga telah berhasil memperbaiki efisiensi penjadwalan pada penelitian sebelumnya dengan adanya peningkatan efisiensi waktu pemrosesan dan pemakain memori. Rata-rata peningkatan efisiensi waktu sebesar 98.23% dan rata-rata efisiensi pemakaian memori sebesar 91.49% untuk penjadwalan data per fakultas, sedangkan peningkatan efisiensi waktu dan pemakaian memori untuk penjadwalan gabungan seluruh fakultas sebesar 33.72% dan 51.93%. Sistem juga telah berhasil menghasilkan jadwal untuk data seluruh fakultas. Saran Sistem yang dibuat pada penelitian kali ini masih berfokus pada representasi logika penjadwalan dan masih memiliki kekurangan pada segi antarmuka sistem sehingga masih sulit digunakan bagi pengguna untuk menjalankan sistem juga untuk melakukan modifikasi pada input dan output jadwal yang terbentuk. Penelitian selanjutnya dapat mengembangkan sistem penjadwalan yang dapat digunakan secara nyata oleh pengguna
seperti adanya fitur yang membuat pengguna dapat melakukan modifikasi terhadap input dan output pada sistem serta mencetak output ke berbagai format.
DAFTAR PUSTAKA Denecker M, Vennekens J, Bond S, Gebser M, Truszcyński M. 2009. The Second Answer Set Programming Competition. Proceeding LPNMR '09 Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning; Potsdam, 14-19 Sep 2009. Berlin:Springer. hlm 637-654. Eiter T, Faber W, Gottlob G, Leone N, Perri S, Pfeifer G, Scarcello F. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7(3): 499-562. Gebser M, Kaminski R, Kaufmann B, Ostrowski M, Schaub T, Schneider M. 2011. Potassco: the Potsdam answer set solving collection. AI Communications 24(2): 105124. Gelfond M, Lifschitz V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9(3/4): 365 – 385. Hunt G. 2010. A case study of scheduling in answer set programming. [tesis] Texas: Graduate Faculty, Texas Tech University.
16
Kowalski RA. (1979). Logic for Problem Solving. New York: North-Holland/Elsevier. Lifschitz V. 2008. What is answer set programming? Di dalam: Fox D, Gomes CP, editor. Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence; Chicago, 13-17 Juli 2008. AAAI Press. hlm 1594 – 1597. Lin F, Zhao Y. 2002. ASSAT: Computing Answer Sets of A Logic Program By SAT Solvers. Artificial Intelligence 157(1-2): 115-137. Simons P, Niemelä I, Soininen T. 2002. Extending and implementing the stable model semantics. Artificial Intelligent. 138(1-2):181-234. Zulkaryanto E. 2011. Sistem penjadwalan ujian menggunakan answer set programming [skripsi]. Bogor: Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor.
LAMPIRAN
18
Lampiran 1 Kode ASP fakta pengambilan oleh grup mahasiswa am(g1,tsl220). am(g2,tsl220). am(g3,tsl220). am(g4,tsl220). am(g5,tsl220). am(g6,tsl220). am(g7,tsl220). am(g8,tsl220). am(g9,tsl220). am(g10,tsl220). am(g11,tsl331). am(g12,tsl331).
am(g13,tsl331). am(g14,tsl331). am(g15,tsl331). am(g16,tsl331). am(g17,tsl331). am(g18,tsl331). am(g19,tsl331). am(g20,tsl331). am(g21,tsl331). am(g982,ksh315). am(g1434,ksh315).
am(g1435,ksh315). am(g1436,ksh315). am(g1437,ksh315). am(g1438,ksh315). am(g435,ksh315). am(g983,ksh315). am(g984,ksh315). am(g1439,ksh315). am(g985,ksh315). am(g698,ksh315). am(g436,ksh315).
am(g699,ksh315). am(g1440,ksh315). am(g1441,ksh315). am(g1442,ksh315). am(g1443,ksh315).
. . . am(g1998,kom312).
19
Lampiran 2 Kode ASP fakta mata kuliah mk(aff214). mk(aff215). mk(aff221). mk(aff222).
mk(aff332). mk(agb202). mk(agb203). mk(agb221). mk(agb222). mk(itp322). mk(itp332). mk(kom208). mk(kom312). mk(kom323). mk(kom331).
mk(kom332). mk(kom333). mk(kom334). mk(kom335). mk(kom412). mk(kpm210). mk(kpm212). mk(kpm213). mk(kpm214). mk(kpm220). mk(kpm221). mk(kpm230). mk(kpm231). mk(kpm233). mk(kpm310). mk(kpm311). mk(kpm323).
mk(kpm331). mk(kpm333). mk(kpm334). mk(kpm403). mk(krp312). mk(krp321). mk(krp322). . . . mk(tep220).
20
Lampiran 3 Kode ASP fakta paralel mk(aff214,683,55). mk(aff214,682,109). mk(aff215,684,173). mk(aff221,688,59). mk(aff221,689,60). mk(aff221,690,49). mk(aff222,691,60). mk(aff222,692,64). mk(aff222,693,48). mk(aff332,1961,88). mk(aff332,1962,58). mk(agb100,11,2).
mk(agb100,17,1). mk(agb100,10,1). mk(agb100,25,1). mk(agb202,1642,111). mk(agb203,1637,110). mk(agb221,1624,107). mk(agb221,1650,92). mk(agb221,1868,119). mk(bio242,1966,65). mk(bio242,510,65). mk(bio242,518,125). mk(bio242,594,96). mk(bio242,629,64). mk(bio252,1404,96). mk(bio262,1410,99). mk(bio302,1411,104). mk(gfm315,1371,54). mk(gfm316,1380,55). . . . mk(hht332,1070,83).
21
Lampiran 4 Kode ASP fakta ruangan ruang(a00000b1,60). ruang(a00000bd,143). ruang(a0003b21,60). ruang(a0003b22,60). ruang(a0004b11,60). ruang(a0004b12,60). ruang(a000b1c1,60). ruang(a000b1c2,60). ruang(a000b1c3,60).
ruang(a000ckb1,30). ruang(a000ckb2,30). ruang(a000gmkl,88). ruang(a000gmsk,125). ruang(a000labp,25). ruang(a000lkp1,40). ruang(a000lkp3,33). ruang(a011gm11,45). ruang(a011gm12,45). ruang(b051farm,30). ruang(b051hlab,30). ruang(b051lfif,30). ruang(b062kesm,30). ruang(b062pkit,30). ruang(b072rkpt,30). ruang(c132rgam,50). ruang(c162rp21,60). ruang(c162rp22,30). ruang(c162rp23,30). ruang(c162rp24,30). ruang(d11002401,50). .
. . ruang(a0440404,40).
22
Lampiran 5 Data ukuran data KRS, banyak mahasiswa, jumlah mata kuliah serta paralel dataset kelompok I Fakultas
Ukuran data KRS
Banyak mahasiswa
Jumlah mata kuliah
Jumlah mata kuliah dengan paralel
FAPERTA
4236
1505
29
48
FKH
3990
704
29
52
FPIK
5384
1512
50
65
FAPET
3226
876
18
33
FAHUTAN
6307
1716
37
64
FATETA
6557
1557
52
64
FMIPA
11726
3667
92
142
FEM
8415
2884
45
79
FEMA
5198
2013
39
64
23
Lampiran 6 Data ukuran data KRS, banyak mahasiswa, jumlah mata kuliah serta paralel dataset kelompok II Fakultas
Ukuran data KRS
Banyak mahasiswa
Jumlah mata kuliah
Jumlah mata kuliah dengan paralel
1
15962
4477
121
302
2
24377
6276
166
405
3
7216
1201
47
94
4
13523
2795
84
173
5
17110
4752
142
317
6
25525
6525
187
420
7
12414
3058
86
179
8
20829
5148
131
282
9
14722
4282
82
182
10
18283
4728
144
316
11
23481
5855
183
401
12
20141
5649
137
345
13
13613
4200
84
188
semua
56123
10157
398
850
24
Lampiran 7 Hasil Penjadwalan MataKuliah
Paralel
AFF214 AFF214 AFF215 AFF221 AFF221 AFF221 AFF222 AFF222 AFF222 AFF332 AFF332 AGB202 AGB203 AGB221 AGB221 AGB221 AGB221 AGB222 AGB222 AGB222 AGB222 AGB223 AGB303 AGB313 AGB313 AGB321 AGB321 AGB322 AGB333 AGB334 AGB334 AGB336 AGB336 AGB336 AGH211 AGH211 AGH211 AGH211 AGH240 AGH240 AGH240 AGH241 AGH241 AGH250 AGH250 AGH250
683 682 684 688 689 690 691 692 693 1961 1962 1642 1637 1624 1650 1868 2034 1 1638 1665 1996 1674 1974 1616 1866 1663 1671 1662 1648 1655 1656 1 1651 1666 563 568 570 638 2027 571 573 558 583 589 584 559
Jumlah Peserta 55 109 173 59 60 49 60 64 48 88 58 111 110 107 92 119 78 1 55 135 66 158 121 124 147 53 111 108 120 131 64 1 107 55 72 24 65 77 44 109 79 82 84 124 50 57
Ruangan
Jam
X_AMARI1 X0000GWW X0000GWW X_AMARI1 X0000GWW A011GM13 X000MASJ X0000GWW A011GM13 X000MASJ X0000GWW X0000GWW X0000GWW X000AGI3 X000AGI4 X000MASJ X0000GWW A00000B1 X_AMARI1 X000MASJ X0000GWW X000MASJ X000AGI4 X000MASJ X0000GWW IPBW0401 X0000GWW X0000GWW X0000GWW X000MASJ X0000GWW A011GM13 X000MASJ X0000GWW X000AGI3 A011GM13 X000AGI4 X000ALSI A011GM13 X000AGI4 X000MASJ X000MASJ X0000GWW A00000BD X000MASJ X0000GWW
15.00 - 17.00 15.00 - 17.00 10.00 - 12.00 10.00 - 12.00 10.00 - 12.00 10.00 - 12.00 08.00 - 10.00 08.00 - 10.00 08.00 - 10.00 10.00 - 12.00 10.00 - 12.00 13.00 - 15.00 08.00 - 10.00 15.00 - 17.00 15.00 - 17.00 15.00 - 17.00 15.00 - 17.00 15.00 - 17.00 15.00 - 17.00 15.00 - 17.00 15.00 - 17.00 15.00 - 17.00 15.00 - 17.00 08.00 - 10.00 08.00 - 10.00 08.00 - 10.00 08.00 - 10.00 08.00 - 10.00 08.00 - 10.00 13.00 - 15.00 13.00 - 15.00 08.00 - 10.00 08.00 - 10.00 08.00 - 10.00 13.00 - 15.00 13.00 - 15.00 13.00 - 15.00 13.00 - 15.00 08.00 - 10.00 08.00 - 10.00 08.00 - 10.00 13.00 - 15.00 13.00 - 15.00 15.00 - 17.00 15.00 - 17.00 15.00 - 17.00
Tanggal Rabu, 18-7-2012 Rabu, 18-7-2012 Selasa, 17-7-2012 Rabu, 18-7-2012 Rabu, 18-7-2012 Rabu, 18-7-2012 Selasa, 17-7-2012 Selasa, 17-7-2012 Selasa, 17-7-2012 Senin, 16-7-2012 Senin, 16-7-2012 Selasa, 17-7-2012 Rabu, 18-7-2012 Senin, 16-7-2012 Senin, 16-7-2012 Senin, 16-7-2012 Senin, 16-7-2012 Kamis, 12-7-2012 Kamis, 12-7-2012 Kamis, 12-7-2012 Kamis, 12-7-2012 Rabu, 18-7-2012 Rabu, 18-7-2012 Senin, 9-7-2012 Senin, 9-7-2012 Selasa, 3-7-2012 Selasa, 3-7-2012 Senin, 16-7-2012 Jumat, 13-7-2012 Rabu, 18-7-2012 Rabu, 18-7-2012 Rabu, 11-7-2012 Rabu, 11-7-2012 Rabu, 11-7-2012 Rabu, 18-7-2012 Rabu, 18-7-2012 Rabu, 18-7-2012 Rabu, 18-7-2012 Selasa, 3-7-2012 Selasa, 3-7-2012 Selasa, 3-7-2012 Senin, 16-7-2012 Senin, 16-7-2012 Selasa, 17-7-2012 Selasa, 17-7-2012 Selasa, 17-7-2012
Hasil penjadwalan yang ditampilkan hanya 47 baris pertama, karena akan terlalu panjang untuk ditampilkan secara keseluruhan.
