SISTEM PENJADWALAN UJIAN MENGGUNAKAN ANSWER SET PROGRAMMING EKO ZULKARYANTO

SISTEM PENJADWALAN UJIAN MENGGUNAKAN ANSWER SET PROGRAMMING

EKO ZULKARYANTO

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2011 i

ABSTRACT

EKO ZULKARYANTO. Exam Scheduling System Using Answer Set Programming. Supervised by MUSHTHOFA. Scheduling tasks have been known to be computationally expensive. Several scheduling problems have been shown to be NP-complete. This research deals with the problem of scheduling exams for the undergraduate Major-Minor System in Bogor Agricultural University. We employ Answer Set Programming (ASP) to tackle this problem. ASP has been, in the last decade, the subject of active research in the field of logic programming, knowledge representation, and reasoning. ASP allows for an intuitive representation of computationally hard problems as well as efficient solving using stateof-the-art solvers, such as DLV. In this research, a representation of scheduling problem in the context of undergraduate Major-Minor System in Bogor Agricultural University has been formulated and a prototype application system written using C# .Net and DLV has also been implemented. Experimental results show that the system is capable of generating feasible exam scheduling in acceptable time for smaller-sized datasets, but still needs performance improvement for bigger-sized datasets. Keywords: stable model, answer set programming, DLV, scheduling

iii

SISTEM PENJADWALAN UJIAN MENGGUNAKAN ANSWER SET PROGRAMMING

EKO ZULKARYANTO

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 2011

ii

Judul Penelitian : Sistem Penjadwalan Ujian Menggunakan Answer Set Programming Nama

: Eko Zulkaryanto

NRP

: G64062250

Menyetujui:

Pembimbing,

Mushthofa, S.Kom, M.Sc NIP. 19820325 200912 1 003

Mengetahui:

Ketua Departemen Ilmu Komputer,

Dr. Ir. Sri Nurdiati, M.Sc NIP. 19601126 198601 2 001

Tanggal Lulus:

iv

RIWAYAT HIDUP Penulis dilahirkan di Lampung Tengah pada Tanggal 15 Juli 1988 dari ayah Akhmad Sutrisno dan ibu Sumarni. Penulis merupakan anak pertama dari tujuh bersaudara, kakak dari Dwi Khoirianto, Trio Pambudi, Ahmad Fauzan, Alvin Fauzi, Arif Ramadhan, dan Desti Rahma Rohima. Tahun 2006 penulis lulus dari SMA Tri Sukses Natar Lampung Selatan dan pada tahun yang sama diterima di Institut Pertanian Bogor melalui jalur Beasiswa Utusan Daerah (BUD) Kementrian Agama Republik Indonesia. Tahun 2007 penulis diterima di Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama masa perkuliahan, penulis aktif di Komunitas .Net dan Komunitas Java, Himpunan Mahasiswa Ilmu Komputer (HIMALKOM) IPB. Tahun 2009 penulis melakukan Praktik Kerja Lapangan di PT Microsoft Indonesia dengan bidang kajian Penambahan Fitur-Fitur pada Community Server 2007 dalam Pengembangan Student Portal Indonesia, http://students.netindonesia.net. Pada tahun yang sama penulis menjadi asisten dosen untuk mata kuliah Pengembangan Sistem Berorientasi Objek dan juga penulis ditunjuk sebagai Microsoft Student Partners (MSP) oleh kepala bagian Academic Developer Evangelist, PT Microsoft Indonesia.

v

KATA PENGANTAR Puji dan syukur penulis panjatkan kepada Allah SWT atas segala curahan rahmat dan karuniaNya sehingga skripsi ini dapat diselesaikan. Skripsi yang berjudul Sistem Penjadalan Ujian Menggunakan Answer Set Programming ini merupakan hasil penelitian yang dilakukan oleh penulis yang dimulai dari Bulan September 2010 sampai Bulan Juli 2011. Penulis mengucapkan terima kasih kepada Bapak Mushthofa, S.Kom, M.Sc sebagai pembimbing yang telah memberi saran, masukan, dan ide-ide kepada penulis dalam menyusun skripsi ini. Penulis juga mengucapkan terima kasih kepada seluruh staf pengajar Departemen Ilmu Komputer atas ilmu yang telah diberikan, serta tidak lupa kepada staf tata usaha yang membantu administrasi selama kuliah di Institut Pertanian Bogor. Penulis juga tidak lupa mengucapkan terima kepada Kemenag RI dan staf Direktorat Kerjasama IPB yang telah memberikan dukungan selama penulis kuliah di IPB. Penulis berterima kasih setulus-tulusnya kepada orang tua dan adik yang telah memberikan kasih sayang, perhatian, doa, dan semangat selama kuliah di IPB, serta dukungannya dalam bentuk moral maupun meteril. Terima kasih yang sebesar-besarnya kepada teman-teman terbaik dari Ilkomerz 43 yang memberikan dukungan, bantuan, dan saran kepada penulis selama kuliah sampai penulis menyusun skripsi. Kepada teman-teman Pondok Asad, Wisma Cemara, dan CSS MoRA IPB juga tidak lupa saya ucapkan terima kasih. Kepada semua pihak lainnya yang telah memberikan kontribusi yang besar selama pengerjaan penelitian ini yang tidak dapat disebutkan satu per satu, penulis ucapkan terima kasih banyak. Semoga penelitian ini dapat memberikan manfaat kepada pembaca sebagai referensi penelitian lanjutan dan pengembangan ilmu pengetahuan.

Bogor, 16 Agustus 2011

Eko Zulkaryanto

vi

DAFTAR ISI Halaman DAFTAR TABEL ................................................................................................................................. vi DAFTAR GAMBAR ............................................................................................................................. vi DAFTAR LAMPIRAN .......................................................................................................................... vi PENDAHULUAN .................................................................................................................................. 1 Latar Belakang .................................................................................................................................. 1 Tujuan ............................................................................................................................................... 1 Ruang Lingkup .................................................................................................................................. 1 Manfaat ............................................................................................................................................. 1 TINJAUAN PUSTAKA ......................................................................................................................... 1 Logic Programming .......................................................................................................................... 1 Answer Set Programming.................................................................................................................. 1 METODE PENELITIAN ....................................................................................................................... 5 Analisis Permasalahan ...................................................................................................................... 5 Pembentukan Data ............................................................................................................................ 6 Pengembangan Sistem ...................................................................................................................... 8 Pembentukan Kode DLV .................................................................................................................. 8 Evaluasi ........................................................................................................................................... 10 HASIL DAN PEMBAHASAN............................................................................................................. 10 KESIMPULAN DAN SARAN............................................................................................................. 14 Kesimpulan ..................................................................................................................................... 14 Saran ............................................................................................................................................... 14 DAFTAR PUSTAKA ........................................................................................................................... 14 LAMPIRAN ......................................................................................................................................... 16

v

DAFTAR TABEL Halaman 1 Dataset dengan banyak pengambilan per fakultas ............................................................................... 6 2 Dataset kelompok I .............................................................................................................................. 6 3 Dataset kelompok II ............................................................................................................................ 7 4 Dataset kelompok III ........................................................................................................................... 7 5 Pembagian slot waktu .......................................................................................................................... 9 6 Ketentuan pembagian shift ................................................................................................................... 9 7 Hasil pengolahan dataset kelompok I ................................................................................................ 11 8 Pemakaian memori oleh masing-masing dataset kelompok I ............................................................ 11 9 Hasil pengolahan dataset kelompok II............................................................................................... 12 10 Pemakaian memori oleh masing-masing dataset kelompok II ........................................................ 12 11 Hasil pengolahan dataset kelompok III ........................................................................................... 12 12 Pemakaian memori oleh masing-masing dataset kelompok III ....................................................... 13

DAFTAR GAMBAR Halaman 1 Semua interpretasi terhadap program . ........................................................................................... 3 2 Peta Kota Natar, Metro, Batanghari, dan Pubian. ................................................................................ 4 3 Ilustrasi answer set pertama pada kasus tambahan pertama. ............................................................... 5 4 Ilustrasi answer set pertama pada kasus tambahan kedua. ................................................................... 5 5 Ilustrasi answer set pertama. ................................................................................................................ 5 6 Pengelompokkan data KRS mahasiswa. .............................................................................................. 6 7 Diagram alir Sistem Penjadwalan Ujian IPB. ...................................................................................... 8 8 Grafik hubungan antara banyaknya pengambilan terhadap memori. ................................................. 13 9 Grafik hubungan antara banyaknya pengambilan terhadap lama proses. .......................................... 14 DAFTAR LAMPIRAN Halaman 1 Antarmuka Sistem Penjadwalan Ujian IPB. ...................................................................................... 17 2 Data jumlah mahasiswa pengambil mata kuliah Mayor, Minor, Interdept, dan Supporting Course. 19 3 Kode DLV fakta pengambilan oleh grup mahasiswa (ambil.dl). ....................................................... 19 4 Kode DLV ruangan ujian mata kuliah beserta slot waktunya (ruang.dl). ......................................... 20 5 Kode DLV aturan (rule.dl). ............................................................................................................... 20 6 Kode DLV kendala (constraint.dl). ................................................................................................... 20 7 Analisis regresi antara pengambilan mata kuliah oleh grup mahasiswa terhadap memori ................ 21 8 Analisis regresi antara banyaknya pengambilan terhadap lama proses.............................................. 22

vi

PENDAHULUAN Latar Belakang Penjadwalan merupakan pengalokasian kegiatan ke dalam slot waktu yang telah disediakan. Permasalahan dalam penjadwalan saat ini masih menjadi suatu permasalahan yang rumit untuk diselesaikan secara manual. Kesulitan semakin kompleks ketika persyaratan-persyaratan harus dipenuhi dalam menentukan penjadwalan.

Manfaat Penelitian ini diharapkan memberikan gambaran mengenai sistem penjadwalan ujian Program Studi S1 Sistem Mayor-Minor IPB sehingga menjadi dasar untuk pengembangan sistem penjadwalan ujian lebih lanjut.

TINJAUAN PUSTAKA Logic Programming

Penelitian yang dilakukan oleh Tamba (2004) menghasilkan sebuah sistem yang mampu menyelesaikan masalah penjadwalan perkuliahan menggunakan Algoritme Genetika (studi kasus FMIPA IPB). Penelitian tersebut dilanjutkan oleh Syadid (2008) yang telah berhasil menyempurnakan kekurangan pada penelitian sebelumnya dalam hal pengakomodasian masalah penjadwalan ruangan.

Kowalski (1979) menyatakan bahwa sebuah algoritme A terdiri atas 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:

Penelitian Hunt (2010) telah berhasil mengimplentasikan Answer Set Programming untuk permasalahan penjadwalan perkuliahan. Pada penelitian tersebut dilakukan pendaftaran mahasiswa terhadap mata kuliah dan kemudian ditempatkan dengan jadwal yang sesuai. Pada penelitian ini juga diharapkan Answer Set Programming mampu diimplementasikan untuk permasalahan penjadwalan ujian di Institut Pertanian Bogor.

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.

Tujuan Tujuan dari penelitian ini adalah: 1. Mengembangkan model penyelesaian permasalahan penjadwalan ujian Program Studi S1 Sistem Mayor-Minor Institut Pertanian Bogor dengan menggunakan Answer Set Programming. 2. Membangun prototipe sistem penjadwalan ujian Program Studi S1 Sistem MayorMinor IPB yang berbasis ASP. 3. Menguji efektivitas dan efisiensi sistem penjadwalan ujian terhadap data KRS Program Studi S1 Sistem Mayor-Minor IPB. Ruang Lingkup Penelitian ini dibatasi pada penjadwalan ujian Program Studi S1 Sistem Mayor-Minor Institut Pertanian Bogor pada satu masa ujian semester. Sistem penjadwalan ujian dikembangkan dengan answer set programming dan C# .Net.

Answer Set Programming Answer set programming (ASP) diawali dengan diperkenalkannya stable model semantic oleh Gelfond dan Lifschitz pada tahun 1988. ASP membuka paradigma baru terhadap pemrograman logika, dengan meningkatkan semantik dari pemrograman berbasis Prolog tradisional. Selanjutnya terdapat penambahan fitur-fitur baru, seperti classical negation dan disjungsi pada bagian head (Gelfond & Lifschitz 1991). Saat ini dikenal sebagai answer set programming. Lifschitz (2008) menjelaskan bahwa Answer set programming (ASP) adalah bentuk formalisme dari pemrograman deklaratif yang berorientasi terhadap sulitnya masalah pencarian. Masalah pencarian di ASP telah dikurangi dengan menentukan stable model dan answer set solver. Telah banyak pengembangan pada answer set programming dibanding dengan pemrograman logika berbasis Prolog. Prolog tidaklah murni deklaratif, semantik pada Prolog masih menggantungkan pada aspek prosedural, seperti urutan pada literal tubuh pada sebuah aturan (rule) dan urutan klausa-klausa dalam program tersebut. Adanya operator cut pada Prolog (“!”) juga merupakan bukti properti prosedural Prolog (Mushthofa 2010).

1

1. Sintaks Aturan (rule) adalah sebuah ekspresi yang mengikuti bentuk:

dengan nilai

,

,

dan adalah classical literal. Himpunan { } disebut kepala (head) dari aturan (rule) , ( ) dinotasikan dengan Himpunan { } disebut tubuh (body) dari aturan dan dinotasikan dengan ( ). Tubuh (body) ada dua jenis, yaitu positive body literal yang dinotasikan dengan ( ) dan negative body literal yang dinotasikan dengan ( ). ( ) dari aturan r tersebut adalah himpunan { } dan ( ) adalah himpunan{ }. Bentuk aturan tanpa kepala ( ) disebut integrity constraint atau hard constraint. Aturan dengan minimal satu buah kepala ( ) disebut normal rule. Bentuk aturan dengan disebut disjunctive rule. Jika bagian tubuh (body) kosong ( ) maka disebut fakta (fact), dalam penulisan simbol “ ” biasanya dihilangkan. Himpunan dari aturanaturan tersebut disebut dengan extended disjunctive logic program (EDLP) atau biasa disebut program . 2. Semantik Semantik dari program 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 maka * +, dengan merupakan simbol konstanta yang diambil semena-mena dari , dengan adalah himpunan semua konstanta. Herbrand Base ( ) 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 aturan-aturan di dalam . Sebuah model dari program merupakan sebuah interpretasi dengan memenuhi . Sebuah answer set dari program positif ground 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 ini dilambangkan dengan , yang dilakukan 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 ( ).

2

Sebagai contoh, di bawah ini adalah sebuah program :

Kemungkinan model-model yang sesuai untuk program di atas dapat dilihat dari interpretasi pada gambar di bawah ini: a, b, c, p

a,b,c

a,b

a,b,p

a,c

a

a,c,p

a,p

b,c

b

c

b,c,p

b,p

c,p

p

Ø

Gambar 1 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

Fixpoint dari ( ( )) adalah {a,b,c,p}, sehingga diperoleh ( ). Hal berarti bahwa bukan merupakan stable model, * + diperoleh sedangkan untuk :

Dengan cara yang sama untuk semua interpretasi , maka diperoleh * + dan * + sebagai stable model dari program dan juga merupakan answer set dari program . 3. Answer Set Programming Solver Answer set programming solver atau answer set solver dikembangkan untuk mengevaluasi input pemrograman logika berbasis answer set programming. Beberapa answer set solver yang telah dikembangkan adalah Lparse (Gelfond & Lifschitz 1991), DLV (Eiter et al. 2006), clasp/claspD (Gebser et al. 2009 & Drescher et al. 2008), SMODELS (Simons et al. 2002), dan ASSAT (Lin & Zao 2002). Penelitian ini menggunakan DLV sebagai answer set solver dalam pengembangan sistem. Menurut Eiter et al. (2006), Disjunctive Logic Programming (DLP) adalah formalisme canggih untuk representasi pengetahuan dan penalaran (knowledge representation and reasoning), yang sangat ekspresif dalam arti matematis. DLV merupakan sebuah sistem KRR (Knowledge Representation and Reasoning) yang didasarkan pada Disjunctive Logic Programming (DLP) di bawah stabel model semantic (disebut juga Answer Set Programming). Mengikuti ketentuan Prolog, string yang dimulai dengan huruf besar menunjukkan variabel, sedangkan string yang dimulai dengan huruf kecil adalah konstanta. Selain itu, DLV juga mendukung konstanta bilangan bulat positif dan konstanta string. Sebuah term adalah variabel atau konstanta. Sebuah atom adalah ekspresi p(t1,...,tn), dengan p adalah predikat n, dan t1,...,tn adalah term. Sebuah literal klasik (classical literal) l adalah sebuah atom p (positif) atau sebuah negasi atom ¬p (negatif). Negation as failure (NAF) literal l adalah sebuah bentuk l (positif) atau not l (negatif), dengan l adalah classical literal. Mengingat sebuah classical literal l, pelengkap literal l didefinisikan sebagai ¬p jika l = p dan p jika l = ¬p. Sebuah himpunan L literal dikatakan konsisten jika untuk setiap l ϵ L yang saling melengkapi literal yang tidak terkandung dalam L. Rule disjungsi (atau disebut rule saja) r dirumuskan sebagai berikut:

Kemudian diperoleh sehingga ( ). merupakan stable model.

( Jadi

)

* *

+, +

a1 v … v an :- b1,…,bk,not bk+1,…,not bm.

3

dengan a1 v … v an, b1,…,bk adalah classical literal dan n ≥ 0, m ≥ k ≥ 0. Konjungsi a1 v … v an adalah head (kepala) dari b1,…,bk,not bk+1,…,not bm adalah body (tubuh) dari r. Sebuah rule tanpa literal kepala (yaitu n = 0) biasanya disebut sebagai integrity constraint. Rule memiliki tepat satu head (yaitu n = 1, tanpa tanda “v”) disebut aturan normal (normal rule). Jika body kosong (yaitu k = m = 0) disebut fakta (fact), biasanya tanda “:-“ dihilangkan.

predicate. Selain itu bahasa DLV juga sudah support ODBC (Open Database Connectifity). Sebagai contoh ASP digunakan untuk menyelesaikan permasalahan pewarnaan kota. Misalnya terdapat empat kota, yaitu Kota Natar, Metro, Batanghari, dan Pubian. Terdapat empat jembatan yang menghubungkan keempat kota tersebut. Kota-kota yang dihubungkan oleh jembatan itu adalah Kota Natar dengan Kota Metro, Kota Metro dengan Kota Batanghari, dan Kota Metro dengan Kota Pubian.

Jika r adalah rule mengikuti rumus di atas, maka H(r) = {a1 v … v an} adalah himpunan literal kepala dan B(r) = B+(r) U B−(r) adalah himpunan literal tubuh, dengan B+(r) (tubuh positif) adalah {b1,…,bk} dan B−(r) (tubuh negatif) adalah {bk+1,…,bm}. Bahasa DLV diperluas dengan adanya weak constraint. Eiter et al. (2006) menyatakan bahwa weak constraint sebagai varian dari integrity constraint. Untuk membedakan secara jelas, weak constraint menggunakan simbol “:~” bukan “:-”. Selain itu bobot (weight) dan tingkat prioritas (priority level) ditentukan secara eksplisit. Weak constraint wc diekspresikan dengan bentuk berikut: :~ b1,…,bk,not bk+1,…,not bm.[w∶l] dengan m ≥ k ≥ 0, b1,...,bm adalah classical literal, w (weight) dan l (level atau layer) adalah konstanta atau variabel bilangan bulat positif. Himpunan B+(wc), B(wc), B-(wc)dari weak constraint wc didefinisikan dengan cara yang sama seperti integrity constraint biasa. Sebuah program adalah himpunan berhingga dari rule (mungkin termasuk integrity constraint) dan weak constraint. Dengan kata lain, program P adalah disjunctive datalog program yang mungkin berisi weak constraint. Untuk program P, WC(P) menandakan himpunan dari weak constraint di dalam P dan Rules(P) menandakan himpunan dari rule (termasuk integrity constraint) di dalam P. Rule dikatakan aman (safe) jika setiap variabel di dalam rule muncul setidaknya satu literal positif di dalam body itu yang bukan komparatif built-in. Suatu program dikatakan aman jika setiap rule adalah aman, hanya program-program yang aman yang dipertimbangkan. Bahasa DLV juga mempunyai predikat built-in, seperti aggregate predicate, comparative predicate, dan arithmatic

Pubian

Metro Batanghari

Natar

Gambar 2 Peta Kota Natar, Metro, Batanghari, dan Pubian. Dalam kode DLV dituliskan seperti di bawah ini: kota(natar). kota(metro). kota(batanghari). kota(pubian). jembatan(natar,metro). jembatan(metro,batanghari). jembatan(metro,pubian). warna(X,merah) v warna(X,hijau) v warna(X,biru) :- kota(X).

Answer set yang dibentuk adalah sebanyak 81 answer set. Answer set tersebut adalah sebagai berikut: {warna(natar,biru), warna(metro,biru), warna(batanghari,biru), warna(pubian,biru)} {warna(natar,hijau), warna(metro,biru), warna(batanghari,biru), warna(pubian,biru)} . . . {warna(natar,merah), warna(metro,merah), warna(batanghari,merah), warna(pubian,merah)}

Answer set pertama menunjukkan bahwa Kota Natar diberi warna biru, Kota Metro diberi warna biru, Kota Batanghari diberi warna biru, dan Kota Pubian diberi warna biru.

4

Pubian

minimal. Fakta yang ditambahkan adalah sebagai berikut:

Biru

Metro Biru

Batanghari Biru

harga(merah,100). harga(hijau,200). harga(biru,100).

Kendala dalam ditambahkan adalah:

kode

DLV

yang

:~ warna(X,W), harga(W,H). [H:1]

Biru

Terbentuk dua answer set dengan biaya paling kecil, yaitu:

Natar

Gambar 3 Ilustrasi answer set pertama pada kasus tambahan pertama. Kemudian kasus di atas ditambah dengan kendala yang menyatakan bahwa warna kota yang terhubung oleh jembatan harus berbeda. Kendala tersebut dituliskan dalam kode DLV seperti di bawah ini: :- warna(X,W), warna(Y,W), jembatan(X,Y).

Best model: {warna(natar,merah), warna(metro,biru), warna(batanghari,merah), warna(pubian,merah)} Cost ([Weight:Level]): <[400:1]> Best model: {warna(natar,biru), warna(metro,merah), warna(batanghari,biru), warna(pubian,biru)} Cost ([Weight:Level]): <[400:1]>

Answer set yang sesuai dengan kendala di atas ada sebanyak 24. Answer set tersebut adalah sebagai berikut: {warna(natar,hijau), warna(metro,biru), warna(batanghari,hijau), warna(pubian,hijau)} . . .

Answer set pertama berarti bahwa Kota Natar diberi warna merah, Kota Metro diberi warna biru, Kota Batanghari diberi warna merah, dan Kota Pubian diberi warna merah. Pubian Merah

Metro

{warna(natar,hijau), warna(metro,merah), warna(batanghari,hijau), warna(pubian,hijau)}

Answer set pertama menunjukkan bahwa Kota Natar diberi warna hijau, Kota Metro diberi warna biru, Kota Batanghari diberi warna Hijau, dan Kota Pubian diberi warna hijau. Pubian

Biru

Batanghari Merah

Merah

Natar

Gambar 5 Ilustrasi answer set pertama.

Biru

Metro Hijau

METODE PENELITIAN Batanghari Biru

Biru

Natar

Gambar 4 Ilustrasi answer set pertama pada kasus tambahan kedua. Selanjutnya kasus di atas ditambah fakta bahwa masing-masing warna memiliki harga, warna merah sebesar 100, hijau sebesar 200, dan biru sebesar 100. Dengan demikian, melahirkan penambahan kendala yang menyatakan bahwa biaya pewarnaan kota harus

Penelitian ini dibagi dalam beberapa tahapan, yaitu analisis permasalahan, pembentukan data, pembentukan program DLV, pengembangan sistem, dan evaluasi. Analisis Permasalahan IPB memberlakukan Sistem Mayor-Minor untuk Program Sarjana. Perkuliahan mayor adalah kegiatan perkuliahan yang diadakan di departemen masing-masing mahasiswa, sedangkan perkuliahan minor adalah kegiatan perkuliahan terhadap satu paket mata kuliah minor yang disediakan oleh departemen lain sebagai bidang keahlian tambahan mahasiswa. Selain perkuliahan mayor-minor, mahasiswa

5

IPB juga bisa mengambil mata kuliah Supporting Course. Sistem Supporting Course memungkinkan mahasiswa mengambil mata kuliah dari departemen lain yang telah disediakan. Beberapa persyaratan yang harus dipenuhi dalam permasalahan penjadwalan ujian pada Sistem Mayor-Minor IPB yaitu: 1. Hanya ada satu ujian yang dapat berlangsung dalam satu ruangan dalam satu waktu tertentu. 2. Setiap ruangan memiliki keterbatasan kapasitas daya tampung mahasiswa. 3. Satu kelompok mahasiswa hanya mengikuti satu ujian dalam satu waktu tertentu. 4. Dalam satu hari mahasiswa diutamakan hanya satu kali ujian.

Tabel 1 Dataset dengan banyak pengambilan per fakultas Nama Fakultas

Ukuran Data KRS

Banyak Mahasiswa

FAPERTA

4236

1506

FKH

3990

705

FPIK

5384

1513

FAPET

3226

877

FAHUTAN

6307

1717

FATETA

6557

1558

11726

3668

Pembentukan Data

FMIPA

Data KRS mahasiswa dikelompokkan berdasarkan pengambilan mata kuliah yang sama. Misalnya, kelompok G1 adalah semua mahasiswa yang mengambil mata kuliah MK001 dan MK002, kelompok G2 adalah semua mahasiswa yang mengambil mata kuliah MK002 dan MK003, dan kelompok G3 adalah semua mahasiswa yang hanya mengambil mata kuliah MK003. Contoh ini diperjelas dengan Gambar 6.

FEM

8415

2885

FEMA

5198

2014

Ukuran data KRS merupakan banyaknya baris pada tabel data KRS yang telah dipisahkan berdasarkan mata kuliah per fakultas. Ukuran data KRS pada Gambar 6 adalah 11. Tabel 2 sampai dengan Tabel 4 adalah 3 kelompok dataset yang dibentuk pada penelitian ini. Banyaknya mahasiswa merupakan jumlah seluruh mahasiswa yang mengambil mata kuliah di fakultas tersebut. Tabel 2 Dataset kelompok I

Fakultas

Mata kuliah dijadwalkan

Mata kuliah ruangan tetap

FAPERTA

29

9

Data KRS pada Gambar 6 diubah menjadi data KRS oleh kelompok mahasiswa. Data KRS oleh kelompok mahasiswa pada penelitian ini disebut sebagai data ambil atau data pengambilan. Tujuan pembentukan kelompokkelompok pengambilan mata kuliah ini adalah untuk memperkecil ukuran data.

FKH

29

17

FPIK

39

5

FAPET

18

14

FAHUTAN

37

1

Pada penelitian ini dibuat sebanyak sembilan buah data berdasarkan fakultas. Masing-masing data tersebut masih terdapat mahasiswa dari fakultas lain (mahasiswa pengambil mata kuliah minor atau Supporting Course). Ukuran kesembilan data tersebut dapat dilihat pada Tabel 1.

FATETA

52

18

FMIPA

92

9

FEM

45

5

FEMA

39

9

Gambar 6 Pengelompokkan data KRS mahasiswa.

6

Mata kuliah yang dijadwalkan pada Tabel 2 merupakan mata kuliah di dalam suatu departemen yang harus dijadwalkan ujiannya pada penelitian ini. Data mata kuliah yang dijadwalkan ini sudah dikurangi dengan mata kuliah Tingkat Persiapan Bersama dan mata kuliah yang tidak diujiankan. Pada dataset kelompok I masih terdapat beberapa mata kuliah yang belum ditetapkan ruangan ujiannya, sehingga masih harus ditentukan ruangan ujiannya oleh sistem pada penelitian ini. Dataset kelompok II yang dibentuk pada penelitian ini adalah sebagai berikut: Tabel 3 Dataset kelompok II

Fakultas

Mata kuliah dijadwalkan


FAPERTA

29

29

FKH

29

29

FPIK

39

39

FAPET

18

18

FAHUTAN

37

37

FATETA

52

52

FMIPA

92

92

FEM

45

45

FEMA

39

39

Dataset kelompok II pada Tabel 3 berisi jumlah keseluruhan mata kuliah yang dijadwalkan ujiannya dan semua mata kuliah tersebut sudah ditetapkan ruangan ujiannya. Dengan demikian, sistem sudah tidak perlu menentukan jadwal ruangan untuk masingmasing mata kuliah tersebut. Dataset kelompok III pada Tabel 4, masingmasing dataset tersebut merupakan gabungan dari beberapa dataset per fakultas. Penggabungan ini dibentuk berdasarkan banyaknya mahasiswa yang mengambil mata kuliah minor dan Supporting Course di fakultas lain. Dataset kelompok III dapat dilihat pada tabel di bawah ini:

Tabel 4 Dataset kelompok III Mata kuliah dijadwalkan


FAPERTA dan FMIPA

121

121

FAPERTA, FMIPA, dan FEM

166

166

FKH dan FAPET

47

47

FKH, FAPET, dan FAHUTAN

84

84

FPIK dan FMIPA

131

131

FPIK, FMIPA, dan FEM

176

176

86

86

FAPET, FKH, FEMA, dan FEM

131

131

FAHUTAN dan FEM

82

82

FATETA dan FMIPA

144

144

FATETA, FMIPA, dan FEMA

183

183

FMIPA dan FEM

137

137

84

84

Fakultas

FAPET, FKH, dan FEMA

FEM dan FEMA

Banyaknya mahasiswa yang mengambil mata kuliah minor dan Supporting Course dapat dilihat pada Lampiran 2. Lampiran 2 menunjukkan bahwa mahasiswa FAPERTA umumnya mengambil mata kuliah minor dan

7

Supporting Course paling banyak di FMIPA. Dengan demikian, dataset FAPERTA digabungkan dengan dataset FMIPA. Selanjutnya, dataset gabungan FAPERTA dan FMIPA digabungkan lagi dengan dataset FEM sebagai fakultas terbanyak kedua setelah FMIPA dalam hal banyaknya pengambil mata kuliah minor dan Supporting Course oleh mahasiswa FAPERTA. Tabel-tabel yang terdapat dalam masingmasing dataset adalah tabel KRS (tabel krs), lama ujian (tabel mk_lama_ujian), mata kuliah TPB (tabel mk_tpb), mata kuliah yang dijadwalkan ujiannya (tabel mk_ujian), ruangan ujian (tabel ruangan), ruangan ujian khusus (tabel ruang_khusus), dan mata kuliah dengan ruangan tetap (tabel ujian_tetap).

Lingkungan perangkat keras dalam pengembangan sistem penjadwalan ujian IPB adalah: a. Prosesor: Intel Core 2 Duo T5500 @ 1.66 GHz b. RAM: 3 GB c. Graphic card: Intel GMA 950 d. HDD: 120 GB Selain pembuatan fakta-fakta, pada antarmuka sistem penjadwalan ujian IPB juga dilakukan pembuatan aturan-aturan dan kendala-kendala. Selanjutnya output program DLV ditampilkan oleh antarmuka dalam bentuk tabel. Sistem Penjadwalan Ujian IPB secara garis besar digambarkan dengan diagram alir pada Gambar 7. Mulai

Dataset dilengkapi dengan dua tabel sebagai data pelengkap yaitu tabel data mata kuliah (tabel data_mk) yang berisi kode mata kuliah, nama mata kuliah, dan dosen dan tabel data ruangan (tabel data_ruangan) yang berisi kode ruangan, nama ruangan, lokasi, kapasitas, dan kapasitas ujian.

Data

Jalankan sistem

Dalam proses sistem juga dibentu tabel-tabel tambahan, yaitu tabel mata kuliah pada KRS yang dijadwalkan (tabel mk_krs_ujian) dan tabel peserta mata kuliah dari KRS (tabel krs_peserta). Selanjutnya, jika sistem berhasil maka tabel terakhir yang dibentuk adalah tabel jadwal.

Kode DLV

Eksekusi kode DLV

Pengembangan Sistem Pada Sistem Penjadwalan Ujian IPB, pengguna memberikan masukan satu berkas data yang sesuai dengan kebutuhan sistem. Pengguna memberikan masukan berupa tanggal ujian dan kendala-kendala yang ada. Selanjutnya pengguna memperoleh keluaran berupa jadwal ringkas dan data lengkap, serta pengguna dapat memperoleh detail peserta ujian dan jadwal ujian yang tersimpan dalam Microsoft Access. Lingkungan perangkat lunak dalam pengembangan sistem penjadwalan ujian IPB adalah: a. b. c. d. e. f. g.

Sistem operasi: Windows 7 Enterprise IDE: Visual Studio 2010 Ultimate Bahasa pemrograman: C# .Net Framework: .Net Framework 4 Answer set solver: DLV (Eiter et al. 2006) Office Tools: Microsoft Excel 2010 DBMS: Microsoft Access 2010

Ada answer set?

Ya

Tampilkan ke tabel

Tidak Selesai

Tabel jadwal

Gambar 7 Diagram alir Sistem Penjadwalan Ujian IPB. Pembentukan Kode DLV Pembentukan kode DLV pada penelitian ini sesuai dengan kode DLV oleh Eiter et al. (2006). Program DLV terdiri atas fakta-fakta (facts), aturan-aturan (rules) dan kendalakendala (constraints). Data yang sudah dibentuk akan dilanjutkan dengan pembentukan faktafakta dan aturan-aturan. Selanjutnya dibentuk kendala-kendala yang diperoleh dari persyaratan penjadwalan ujian.

8

Untuk pembentukan fakta waktu, pada penelitian ini ditetapkan 4 slot waktu dalam satu hari dengan lama ujian 2 jam. Pembagian slot waktu dapat dilihat pada Tabel 5. Tabel 5 Pembagian slot waktu Waktu

Dalam Program DLV

8.00-10.00

slot1_2jam

10.00-12.00

slot2_2jam

13.00-15.00

slot3_2jam

15.00-17.00

slot4_2jam

Selajutnya semua pasangan mata kuliah dengan ruangannya (misal mata kuliah AGH 211 shift pertama dan dengan ruangan A144401A) didisjungsikan terhadap slot waktu. Kode DLV yang dibentuk adalah: ruang(agh211,shift_1,a144401a,slot1_2jam ) v ruang(agh211,shift_1,a144401a,slot2_2jam ) v ruang(agh211,shift_1,a144401a,slot3_2jam ) v ruang(agh211,shift_1,a144401a,slot4_2jam ).

Untuk pembentukan rule ruangan beserta slot waktu (ruang.dl), sebelumnya dibentuk pasangan antara mata kuliah dengan ruangan ujiannya dengan memperhatikan kapasitas ruangan untuk ujian. Suatu mata kuliah akan dipasangkan dengan ruangan-ruangan ujian yang memenuhi persyaratan penempatan, yaitu jumlah peserta tidak boleh melebihi kapasitas ujian ruangan tersebut. Untuk mata kuliah yang memiliki peserta di atas 95 mahasiswa dibagi menjadi beberapa shift sesuai dengan ketentuan pembagian shift (lihat Tabel 6). Tabel 6 Ketentuan pembagian shift Jumlah Peserta

Pembagian shift hanya dilakukan pada dataset kelompok I, sedangkan dataset kelompok II dan III sudah tidak perlu dilakukan pembagian shift karena sudah ditetapkan ruangan ujiannya dan sudah ditetapkan berdasarkan shift-nya.

Aturan-aturan yang dibentuk (rule.dl) adalah sebagai berikut: jadwal1(G,M,S,R,J,senin__18_7_2011) v jadwal1(G,M,S,R,J,selasa__19_7_2011) v jadwal1(G,M,S,R,J,rabu__20_7_2011) v jadwal1(G,M,S,R,J,kamis__21_7_2011) v jadwal1(G,M,S,R,J,jumat__22_7_2011) v jadwal1(G,M,S,R,J,sabtu__23_7_2011) v jadwal1(G,M,S,R,J,minggu__24_7_2011) v jadwal1(G,M,S,R,J,senin__25_7_2011) v jadwal1(G,M,S,R,J,selasa__26_7_2011) v jadwal1(G,M,S,R,J,rabu__27_7_2011) v jadwal1(G,M,S,R,J,kamis__28_7_2011) v jadwal1(G,M,S,R,J,jumat__29_7_2011) v jadwal1(G,M,S,R,J,sabtu__30_7_2011) :ambil(G,M), ruang(M,S,R). jadwal(M,S,R,J,H) :jadwal1(_,M,S,R,J,H).

Banyak Shift

Kendala-kendala yang dibentuk secara default (constraint.dl) adalah sebagai berikut:

peserta < 95

1

95 ≤ peserta < 120

2

120 ≤ peserta < 180

3

180 ≤ peserta < 240

4

240 ≤ peserta < 300

5

300 ≤ peserta < 360

6

:- jadwal(M,S1,R,J,H), jadwal(M,S2,R,J,H), S1 != S2.

360 ≤ peserta < 420

7

420 ≤ peserta < 480

:- jadwal(M,_,_,J1,H1), jadwal(M,_,_,J2,H2), J1 != J2, H1 != H2.

8

480 ≤ peserta < 540

9

540 ≤ peserta < 600

10

Pembagian shift ujian hanya akan dilakukan jika dataset yang dibentuk masih terdapat mata kuliah yang belum ditetapkan ruangan ujiannya.

a. Mata kuliah tidak boleh bentrok :- jadwal(M1,_,R,J,H), jadwal(M2,_,R,J,H), M1 != M2.

b. Mahasiswa tidak boleh bentrok jadwal ujian :- jadwal1(G,M1,_,_,J,H), jadwal1(G,M2,_,_,J,H), M1 != M2.

c. Setiap mata kuliah dan shift-nya dijadwalkan ujiannya pada waktu yang sama

:- jadwal(M,_,_,_,H1), jadwal(M,_,_,_,H2), H1 != H2.

Answer set pertama yang dibentuk untuk dataset FAPERTA adalah sebagai berikut: {jadwal(tsl251,semua,a00000bd,slot2_2jam ,jumat__29_7_2011), jadwal(tsl360,semua,a00000bd,slot3_2jam, kamis__28_7_2011), jadwal(tsl301,semua,a000gmkl,slot3_2jam,

9

jumat__29_7_2011), jadwal(agh331,shift_1,a0003b21,slot4_2ja m,senin__25_7_2011), jadwal(agh331,shift_2,a00000bd,slot4_2ja m,senin__25_7_2011), jadwal(tsl331,semua,a00000bd,slot4_2jam, kamis__28_7_2011), jadwal(tsl350,semua,a000gmkl,slot4_2jam, jumat__29_7_2011), jadwal(tsl321,semua,a00000bd,slot3_2jam, selasa__26_7_2011), jadwal(tsl311,semua,a00000bd,slot1_2jam, kamis__28_7_2011), jadwal(arl313,shift_1,a144401b,slot4_2ja m,jumat__22_7_2011), jadwal(arl313,shift_2,a000gmkl,slot4_2ja m,jumat__22_7_2011), jadwal(arl313,shift_3,a144401a,slot4_2ja m,jumat__22_7_2011), jadwal(arl313,shift_4,a164401b,slot4_2ja m,jumat__22_7_2011), jadwal(arl313,shift_5,a164401a,slot4_2ja m,jumat__22_7_2011), jadwal(agh241,shift_1,a164401e,slot4_2ja m,rabu__20_7_2011), jadwal(agh241,shift_2,a153301b,slot4_2ja m,rabu__20_7_2011), jadwal(agh241,shift_3,a153301a,slot4_2ja m,rabu__20_7_2011), jadwal(agh241,shift_4,a144401c,slot4_2ja m,rabu__20_7_2011), jadwal(agh240,shift_1,a000b1c2,slot4_2ja m,selasa__19_7_2011), jadwal(agh240,shift_2,a00000bd,slot4_2ja m,selasa__19_7_2011), jadwal(agh240,shift_3,a000b1c1,slot4_2ja m,selasa__19_7_2011), jadwal(agh250,shift_1,a0004b11,slot4_2ja m,kamis__21_7_2011), jadwal(agh250,shift_2,a0004b12,slot4_2ja m,kamis__21_7_2011), jadwal(agh250,shift_3,a0003b22,slot4_2ja m,kamis__21_7_2011), jadwal(agh250,shift_4,a0003b21,slot4_2ja m,kamis__21_7_2011), jadwal(arl212,shift_1,a153301b,slot4_2ja m,rabu__27_7_2011), jadwal(arl212,shift_2,a153301a,slot4_2ja m,rabu__27_7_2011), jadwal(agh341,shift_1,a000b1c2,slot4_2ja m,selasa__26_7_2011), jadwal(agh341,shift_2,a000b1c1,slot4_2ja m,selasa__26_7_2011), jadwal(agh341,shift_3,a000gmkl,slot4_2ja m,selasa__26_7_2011), jadwal(tsl230,semua,a00000bd,slot2_2jam, kamis__28_7_2011), jadwal(tsl220,semua,a00000bd,slot4_2jam, selasa__26_7_2011), jadwal(tsl240,shift_1,a153301b,slot4_2ja m,jumat__29_7_2011), jadwal(tsl240,shift_2,a153301a,slot4_2ja m,jumat__29_7_2011), jadwal(agh211,shift_1,a144401a,slot3_2ja m,selasa__26_7_2011), jadwal(agh211,shift_2,a000gmkl,slot3_2ja m,selasa__26_7_2011), jadwal(agh211,shift_3,a144401b,slot3_2ja m,selasa__26_7_2011), jadwal(agh211,shift_4,a0003b21,slot3_2ja m,selasa__26_7_2011), jadwal(agh343,semua,a0440404,slot4_2jam, rabu__27_7_2011), jadwal(agh344,semua,a0003b21,slot4_2jam,

kamis__28_7_2011), jadwal(agh398,shift_1,a144401c,slot3_2ja m,jumat__22_7_2011), jadwal(agh398,shift_2,a144401a,slot3_2ja m,jumat__22_7_2011), jadwal(agh398,shift_3,a144401b,slot3_2ja m,jumat__22_7_2011), jadwal(agh342,semua,a0003b21,slot2_2jam, jumat__29_7_2011), jadwal(agh350,semua,a0003b21,slot3_2jam, kamis__28_7_2011), jadwal(arl321,semua,a000gmkl,slot2_2jam, kamis__28_7_2011), jadwal(arl312,semua,a0630301,slot3_2jam, rabu__27_7_2011), jadwal(arl398,semua,a042202a,slot4_2jam, rabu__27_7_2011), jadwal(arl213,semua,a0630301,slot4_2jam, kamis__28_7_2011), jadwal(arl211,semua,a000b1c3,slot2_2jam, jumat__29_7_2011), jadwal(arl214,semua,a000b1c1,slot3_2jam, jumat__29_7_2011)}

Evaluasi Pada penelitian ini dilakukan pencatatan lama proses untuk ketiga kelompok dataset tersebut sampai menghasilkan answer set atau tidak ada answer set. Lama proses dinyatakan time out jika dataset tersebut membutuhkan lama proses melebihi dua jam. Pada penelitian ini juga dilakukan pencatatan memori maksimum yang digunakan dalam pemrosesan kode DLV. Dengan demikian dapat dilakukan analisis terhadap hubungan antara banyaknya pengambilan mata kuliah oleh grup terhadap memori yang diperlukan dan hubungan antara pengambilan mata kuliah oleh grup terhadap lama pemrosesan kode DLV.

HASIL DAN PEMBAHASAN Pada penelitian ini telah dibuat model-model untuk permasalahan penjadwalan ujian Program Studi S1 Sistem Mayor-Minor Institut Pertanian Bogor dengan menggunakan Answer Set Programming dan telah dibangun prototipe sistem penjadwalan ujian Program Studi S1 Sistem Mayor-Minor IPB yang berbasis bahasa ASP dan bahasa C# .Net. Hasil dari sistem penjadwalan ujian tersebut berupa tabel jadwal ujian yang ditampilkan pada antarmuka sistem. Pada penelitian ini, bagian input data, pengolahan data, eksekusi kode DLV, dan output berupa jadwal ditangani oleh sistem dengan bahasa C# .Net. Eksekusi kode DLV ditangani oleh kode program C# .Net pada kelas DLVHandler. Hal ini sesuai dengan penelitian Ricca (2003) yang telah mengimplementasikan

10

Java Wrapper dengan proses eksekusi kode DLV ditangani oleh bahasa pemrograman Java. Untuk pengolahan pada dataset kelompok pertama memiliki ukuran data KRS oleh kelompok mahasiswa atau data pengambilan mata kuliah oleh kelompok mahasiswa (pada penelitian ini disebut ambil), rata-rata lama proses yang diperlukan, dan berhasil atau tidaknya pembuatan jadwal. Perulangan yang dilakukan untuk masing-masing dataset adalah tiga kali. Dikatakan berhasil jika sistem tersebut menghasilkan jadwal ujian terhadap dataset yang diproses dan dikatakan tidak berhasil jika sitem tidak menghasilkan jadwal ujian atau waktu melebihi batas (time out). Data tersebut dapat dilihat pada tabel di bawah ini:

Fakultas

Ambil

Tabel 8 Pemakaian memori oleh masingmasing dataset kelompok I

Fakultas

Rataan maks. pemakaian memori (MB)

FAPERTA

595.359

FKH

590.125

FPIK

1631.445

FAPET

Tabel 7 Hasil pengolahan dataset kelompok I Rataan lama proses (menit)

Pencatatan pemakaian memori maksimum untuk setiap percobaan pada tiap-tiap dataset dapat dilihat pada Tabel 8.

Berhasil (Ya/Tidak)

FAPERTA

1316

8.05

Ya

FKH

2657

8.53

Ya

FPIK

3386

77.85

Tidak

FAPET

2039

13.53

Ya

FAHUTAN

3855

1.86

Tidak

FATETA

4104

5.39

Tidak

FMIPA

5927

2.15

Tidak

FEM

5172

1.95

Tidak

FEMA

2588

11.61

Ya

Ambil merupakan ukuran data KRS oleh kelompok mahasiswa terhadap mata kuliah pada fakultas tertentu. Rataan lama proses merupakan rata-rata lama pemrosesan sistem dalam pengolahan data sampai eksekusi kode DLV yang dilakukan sebanyak tiga kali perulangan. Pada Tabel 7 diketahui bahwa hanya empat dataset yang menghasilkan jadwal ujian. Keempat dataset tersebut adalah FAPERTA, FKH, FAPET, dan FEMA. Selain keempat dataset tersebut tidak menghasilkan jadwal ujian atau juga dikatakan tidak berhasil menghasilkan answer set.

540.473

FAHUTAN

1613.163

FATETA

1904.883

FMIPA

1446.098

FEM

1992.586

FEMA

797.223

Dari Tabel 7 dan Tabel 8 dapat diketahui bahwa dataset yang mengalami kegagalan dalam pembuatan jadwal merupakan dataset yang menggunakan memori mulai dari 1446.098 MB. Ukuran RAM yang digunakan pada penelitian ini adalah 3 GB. RAM ini sudah digunakan oleh sistem operasi sendiri sekitar 11.5 GB dengan penggunaan yang tidak tetap. Dengan demikian, untuk dataset yang menggunakan memori maksimum mendekati 2 GB tidak akan menghasilkan jadwal ujian atau dikatakan gagal. Kemungkinan besar penyebab besarnya pemakaian memori adalah penentuan ruangan ujian untuk masing-masing mata kuliah yang belum ditetapkan ruangan ujiannya. Penetapan ruangan ujian tersebut menghasilkan rule penetapan ruangan yang sangat banyak, sehingga DLV membutuhkan memori yang sangat besar sampai DLV menemukan answer set. Pada dataset kelompok II, ukuran data KRS oleh kelompok mahasiswa, rata-rata lama proses dan berhasil atau tidaknya pembuatan jadwal dapat dilihat pada Tabel 9. Tabel 9 menunjukkan bahwa dataset kelompok II telah berhasil memperoleh answer set atau jadwal ujian sesuai dengan kendala yang diberikan.

11

Tabel 9 Hasil pengolahan dataset kelompok II

Fakultas

Ambil

FAPERTA

1316

Rataan lama proses (menit)

Berhasil (Ya/Tidak)

1.68

Tabel 10 menunjukkan bahwa penggunaan memori lebih kecil dibandingkan dengan memori yang digunakan oleh dataset kelompok I. Tabel 11 Hasil pengolahan dataset kelompok III

Ya Fakultas

FKH

2657

4.12

Ya

FPIK

3386

6.34

Ya

FAPET

2039

9.15

Ya

FAHUTAN

3855

16.26

Ya

FATETA

4104

10.43

Ya

FMIPA

5927

8.21

Ya

FEM

5172

19.59

Ya

FEMA

2588

3.58

Ya

Hasil pengolahan dataset kelompok II menunjukkan bahwa seluruh dataset berhasil menghasilkan jadwal ujian atau dapat dikatakan bahwa dataset berhasil dijadwalkan oleh sistem. Data pencatatan maksimum pemakaian RAM untuk dataset kelompok II adalah: Tabel 10 Pemakaian memori oleh masingmasing dataset kelompok II

Fakultas


FAPERTA

159.026

FKH

291.337

FPIK

396.336

FAPET

327.988

FAHUTAN

700.797

FATETA

520.502

FMIPA

779.547

FEM

918.336

FEMA

319.574

Ambil

Rataan lama proses (menit)

Berhasil (Ya/Tidak)

FAPERTA dan FMIPA

15962

7.13

Ya


24377

TO

Tidak

7216

5.58

Ya


13523

6.40

Ya

FPIK dan FMIPA

17110

8.57

Ya

FPIK, FMIPA, dan FEM

25525

17.49

Ya

FAPET, FKH, dan FEMA

12414

6.62

Ya


20829

15.77

Ya

FAHUTAN dan FEM

14722

25.65

Ya

FATETA dan FMIPA

18283

9.36

Ya


23481

13.61

Ya

FMIPA dan FEM

20141

24.35

Ya

FEM dan FEMA

13613

20.57

Ya

FKH dan FAPET

12

Pada Tabel 11 terdapat dua dataset dengan rata-rata lama proses melebihi dua jam sehingga dinyatakan time out (TO). Berikut pemakaian maksimum RAM untuk dataset kelompok III: Tabel 12 Pemakaian memori oleh masingmasing dataset kelompok III

Fakultas


FAPERTA dan FMIPA

493.988


1019.301

FKH dan FAPET

388.672


565.219

Dari Tabel 11 dan 12 dapat diketahui bahwa dataset yang tidak menghasilkan answer set membutuhkan memori yang cukup besar dalam proses eksekusi kode DLV untuk menghasilkan answer set. Ditambah lagi dengan banyaknya pengambilan dalam masing-masing dataset menambah lama proses eksekusi program DLV menjadi lebih lama. Penggunaan memori sebesar 1218.063 MB adalah penggunaan memori terbesar dari dataset kelompok III yang masih mampu menghasilkan answer set dengan lama proses sekitar 24 menit dengan banyak pengambilan sebanyak 20141 pengambilan. Semakin besar ukuran dataset ternyata semakin tidak efektif untuk menghasilkan jadwal ujian. Untuk dataset kelompok II dan III dihitung masing-masing banyaknya data pengambilan ( ) oleh grup. Hasil analisis regresi menunjukkan bahwa berpengaruh nyata terhadap pemakaian memori ( ). Hubungan antara dan digambarkan dengan scatter plot pada Gambar 8. 1400

FPIK, FMIPA, dan FEM FAPET, FKH, dan FEMA

y = 0.0615x1,0977 R² = 0.9299

1200

650.184

1000

1134.387

Memori

FPIK dan FMIPA

800 600 400 200

521.469

0 0

2000

4000

6000

8000

10000

Ambil


1024.625

FAHUTAN dan FEM

1072.410

FATETA dan FMIPA

766.688


1009.277

FMIPA dan FEM

1218.063

FEM dan FEMA

1190.523

Memori

Power (Memori)

Gambar 8 Grafik hubungan antara banyaknya pengambilan terhadap memori. Berdasarkan scatter plot pada Gambar 8, diketahui bahwa terdapat hubungan antara banyaknya pengambilan terhadap memori yang dibutuhkan dalam eksekusi kode DLV. Trend dengan terbaik dari beberapa trend lainnya pada scatter plot Microsoft Excel 2010 adalah power. Persamaan power ini sudah sangat baik menggambarkan hubungan antara pengambilan dan memori yang digunakan. Selanjutnya grafik yang menggambarkan hubungan antara pengambilan terhadap lama proses dapat dilihat pada Gambar 9.

13

2. Menggunakan spesifikasi komputer yang lebih tinggi untuk proses pengolahan data dan eksekusi kode DLV.

30,00 y = 0.0004x1.1934 R² = 0.6712

Lama Proses

25,00 20,00 15,00

DAFTAR PUSTAKA

10,00 5,00 0,00 0

2000

4000

6000

8000

10000

Ambil Waktu

Power (Waktu)

Gambar 9 Grafik hubungan antara banyaknya pengambilan terhadap lama proses. Berdasarkan scatter plot Gambar 9, hubungan antara banyaknya pengambilan terhadap lama proses membentuk persamaan power.

KESIMPULAN DAN SARAN Kesimpulan Pada penelitian ini dapat disimpulkan bahwa ASP telah mampu memodelkan penyelesaian permasalahan penjadwalan ujian Program Studi S1 Sistem Mayor-Minor Institut Pertanian Bogor. Pemodelan penyelesaian permasalahan penjadwalan berhasil untuk dataset yang dibuat per Fakultas dan belum berhasil dilakukan untuk data keseluruhan. Pada penelitian ini juga telah dikembangkan prototipe sistem penjadwalan ujian Program Studi S1 Sistem Mayor-Minor IPB yang berbasis ASP. Pemodelan penyelesaian permasalahan penjadwalan ujian Program Studi S1 Sistem Mayor-Minor IPB menggunakan ASP efektif dan efisien untuk data per fakultas dengan mata kuliah sudah ditetapkan untuk masing-masing mata kuliah yang akan dijadwalkan ujiannya. Namun, penelitian ini masih perlu peningkatan untuk dataset yang berukuran lebih besar. Hal ini terkait dengan kekurangan terhadap kapasitas memori yang dibutuhkan dalam pemrosesan kode DLV. Saran Saran yang dapat dilakukan untuk penelitian lebih lanjut adalah: 1. Menggunakan answer set solver yang lain, seperti SMODEL, Lparse, ASSAT, dan sebagainya.

Drescher C, Gebser M, Grote T, Kaufmann B, König A, Ostrowski M, Schaub T. 2008. Conflict-Driven Disjunctive Answer Set Solving. Di dalam: Brewka G dan Lang J, editor. Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning; Sydney, 16 – 19 September 2008. AAAI Press. Hlm 422-432. 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, Kaufmann B, Schaub T. 2009. The Conflict-Driven Answer Set Solver Clasp: Progress Report. Di dalam: Erdem E, Lin F, Schaub T, editor. Logic Programming and Nonmonotonic Reasoning; Postdam, 14 – 18 September 2009. Hlm 509 – 514. Gelfond M, Lifschitz V. 1988. The Stable Model Semantic For Logic Programming. Di dalam: Proceedings of the Fifth International Conference on Logic Programming; Seattle, 15 – 19 Agustus 1988. Cambridge: MIT Press. Hlm 1070 – 1080. 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. 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. Mushthofa M. 2010. Evaluation of Answer Set Programs with Bounded Predicate Arities

14

[tesis]. Wien: Faculty of Informatics, Vienna University of Technology. Ricca F. 2003. A Java Wrapper for DLV. Di dalam: Marina De Vos, Provetti A, editor. Answer Set Programming Advances in Theory and Implementation. Messina, 26 – 28 September 2003. http://CEURWS.org/Vol-78. hlm 305 – 316. Simons P, Niemelä I, Soininen T. 2002. Extending and Implementing the Stable Model Semantics. Artificial Intelligent. 138(1-2):181-234. Syadid M. 2008. Penjadwalan Perkuliahan Menggunakan Algoritme Genetika [skripsi]. Bogor: Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Tamba GMP. 2004. Sistem Penjadwalan Perkuliahan Menggunakan Algoritma Genetika (Studi Kasus Fakultas Matematika dan IPA IPB) [skripsi]. Bogor: Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor.

15

LAMPIRAN

16

Lampiran 1 Antarmuka Sistem Penjadwalan Ujian IPB.

17

Lampiran 1 lanjutan

18

Lampiran 2 Data jumlah mahasiswa pengambil mata kuliah Mayor, Minor, Interdept, dan Supporting Course.

Fakultas

FAPERTA

FKH

FAPET

FAHUTAN

FATETA

1151

0

34

0

142

12

699

369

206

FKH

1

490

0

165

102

0

31

9

2

FPIK

11

0

1080

0

67

39

187

180

115

6

214

12

696

20

15

37

118

144

116

0

92

0

1189

18

175

207

87

FATETA

69

0

69

12

60

1212

261

135

179

FMIPA

45

0

190

2

85

191

1985

302

202

FEM

81

0

17

1

43

5

84

1288

239

FEMA

24

0

15

0

8

63

204

275

839

FAPERTA

FAPET FAHUTAN

FPIK

FMIPA

FEM

FEMA

Lampiran 3 Kode DLV fakta pengambilan oleh grup mahasiswa (ambil.dl). ambil(g1,tsl251). ambil(g1,tsl360). ambil(g1,tsl301). ambil(g1,agh331). ambil(g2,tsl331). ambil(g3,tsl301). ambil(g3,tsl360). ambil(g3,tsl331). ambil(g3,tsl350). ambil(g3,tsl321). ambil(g4,tsl311). ambil(g4,arl313). ambil(g5,tsl321). ambil(g6,agh241). ambil(g7,tsl331). ambil(g7,tsl301). ambil(g7,tsl311). ambil(g8,agh240). ambil(g8,agh250). . . . ambil(g307,agh341).

19

Lampiran 3 lanjutan ambil(g307,agh250). ambil(g308,tsl240). ambil(g309,tsl220). ambil(g310,arl321). ambil(g311,arl321). ambil(g311,arl313).

Lampiran 4 Kode DLV ruangan ujian mata kuliah beserta slot waktunya (ruang.dl). ruang(agh211,shift_1,a144401a,slot1_2jam) v ruang(agh211,shift_1,a144401a,slot2_2jam) v ruang(agh211,shift_1,a144401a,slot3_2jam) v ruang(agh211,shift_1,a144401a,slot4_2jam). ruang(agh211,shift_2,a000gmkl,slot1_2jam) v ruang(agh211,shift_2,a000gmkl,slot2_2jam) v ruang(agh211,shift_2,a000gmkl,slot3_2jam) v ruang(agh211,shift_2,a000gmkl,slot4_2jam). ruang(agh211,shift_3,a144401b,slot1_2jam) v ruang(agh211,shift_3,a144401b,slot2_2jam) v ruang(agh211,shift_3,a144401b,slot3_2jam) v ruang(agh211,shift_3,a144401b,slot4_2jam). ruang(agh211,shift_4,a0003b21,slot1_2jam) v ruang(agh211,shift_4,a0003b21,slot2_2jam) v ruang(agh211,shift_4,a0003b21,slot3_2jam) v ruang(agh211,shift_4,a0003b21,slot4_2jam). . . . ruang(tsl360,semua,a00000bd,slot1_2jam) v ruang(tsl360,semua,a00000bd,slot2_2jam) v ruang(tsl360,semua,a00000bd,slot3_2jam) v ruang(tsl360,semua,a00000bd,slot4_2jam).

Lampiran 5 Kode DLV aturan (rule.dl). jadwal1(G,M,S,R,J,senin__18_7_2011) v jadwal1(G,M,S,R,J,selasa__19_7_2011) v jadwal1(G,M,S,R,J,rabu__20_7_2011) v jadwal1(G,M,S,R,J,kamis__21_7_2011) v jadwal1(G,M,S,R,J,jumat__22_7_2011) v jadwal1(G,M,S,R,J,senin__25_7_2011) v jadwal1(G,M,S,R,J,selasa__26_7_2011) v jadwal1(G,M,S,R,J,rabu__27_7_2011) v jadwal1(G,M,S,R,J,kamis__28_7_2011) v jadwal1(G,M,S,R,J,jumat__29_7_2011) :ambil(G,M), ruang(M,S,R,J). jadwal(M,S,R,J,H) :- jadwal1(_,M,S,R,J,H).

Lampiran 6 Kode DLV kendala (constraint.dl). :- jadwal(M1,_,R,J,H), jadwal(M2,_,R,J,H), M1 != M2. :- jadwal1(G,M1,_,_,J,H), jadwal1(G,M2,_,_,J,H), M1 != M2. :- jadwal(M,_,_,J1,H1), jadwal(M,_,_,J2,H2), J1 != J2, H1 != H2. :- jadwal(M,_,_,J1,_), jadwal(M,_,_,J2,_), J1 != J2. :- jadwal(M,S1,R,J,H), jadwal(M,S2,R,J,H), S1 != S2. :- jadwal(M,_,_,_,H1), jadwal(M,_,_,_,H2), H1 != H2.

20

Lampiran 7 Analisis regresi antara pengambilan mata kuliah oleh grup mahasiswa terhadap memori SUMMARY OUTPUT

Regression Statistics Multiple R

0,950554266

R Square

0,903553413

Adjusted R Square

0,898477277

Standard Error

104,5161196

Observations

21

ANOVA df Regression

SS

MS

F 178,0002

1

1944406,757

1944407

Residual

19

207548,7659

10923,62

Total

20

2151955,523

Intercept Ambil

Coefficients

Standard Error

-43,84792461 0,152535215

t Stat

P-value

59,40989621

-0,73806

0,469498

0,01143299

13,34167

4,24E-11

Significance F 4,2405E-11

Upper 95%

Lower 95,0%

Upper 95,0%

-168,194266

80,49841723

168,194266

80,49841723

0,128605691

0,176464739

0,12860569

0,176464739

Lower 95%

21

Lampiran 8 Analisis regresi antara banyaknya pengambilan terhadap lama proses SUMMARY OUTPUT

Regression Statistics Multiple R

0,74574753

R Square

0,55613938

Adjusted R Square

0,53277829

Standard Error

4,77089131

Observations

21

ANOVA df Regression

SS

MS

1

541,8632235

541,8632235

Residual

19

432,4666736

22,76140387

Total

20

974,3298971

Coefficient s

Standard Error

t Stat

F 23,80623034

P-value

Significance F 0,000104189

Lower 95%

Upper 95%

Lower 95,0%

Upper 95,0%

Intercept

-0,8759051

2,711908541

-0,322984752

0,750234302

-6,551994918

4,80018 5

-6,55199

4,80018470 3

Ambil

0,00254637

0,000521887

4,879162873

0,000104189

0,001454048

0,00363 9

0,001454

0,00363869

22

SISTEM PENJADWALAN UJIAN MENGGUNAKAN ANSWER SET PROGRAMMING EKO ZULKARYANTO

Recommend Documents