penjadwalan matakuliah dengan menggunakan algoritma genetika

Buliali, Penjadwalan Mata Kuliah dengan Menggunakan Algoritma Genetika dan Metode Constraint Satisfaction

PENJADWALAN MATAKULIAH DENGAN MENGGUNAKANALGORITMA GENETIKA DAN METODE CONSTRAINT

SATISFACTION

Joko Lianto Buliali Darlis Herumurti Giri WiriapradjaJurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember

Email: [email protected]

ABSTRACTCourse scheduling problem has gained attention from many researchers. A number of methods have been produced toget optimum schedule. Classical definition of course scheduling cannot fulfill the special needs of lecture scheduling inuniversities, therefore several additional rules have to be added to this problem. Lecture scheduling is computationallyNP-hard problem, therefore a number of researches apply heuristic methods to do automation to this problem.This research applied Genetic Algorithm combined with Constraint Satisfaction Problem, with chromosomes generatedby Genetic Algorithm processed by Constraint Satisfaction Problem. By using this combination, constraints in lecturescheduling that must be fulfilled can be guaranteed not violated. This will make heuristic process in Genetic Algorithmfocused and make the entire process more efficient. The case study is the case in Informatics Department, Faculty ofInformation Technology, ITS.From the analysis of testing results, it is concluded that the system can handle specific requested time slot for a lecture,that the system can process all the offered lectures, and that the system can produce schedules without violating the givenconstraints. It is also seen that Genetic Algorithm in the system has done optimation in finding the minimum studentwaiting time between lectures.

keywords: genetic algorithm, constraint satisfaction problem, optimation, lecture scheduling

ABSTRAKPermasalahan penjadwalan untuk pengajaran mendapatkan perhatian dari banyak peneliti. Sejumlah metode telah di-hasilkan untuk mendapatkan jadwal yang optimum. Definisi klasik untuk penjadwalan ini belum dapat memenuhi sejumlahkebutuhan khusus pada masalah penjadwalan perkuliahan di Perguruan Tinggi, sehingga sejumlah aturan tambahan perludiberikan pada masalah ini. Mengingat masalah penjadwalan perkuliahan di Perguruan Tinggi merupakan masalah NP-hard secara komputasi, sejumlah penelitian menerapkan metode heuristic untuk melakukan otomasi terhadap masalahini.Pada penelitian ini metode Algoritma Genetika dipadukan dengan metode Constraint Satisfaction Problem, dengan kro-mosom yang dihasilkan metode Algoritma Genetika diproses dengan metode Constraint Satisfaction Problem. Dengancari ini dapat batasan-batasan pada penjadwalan yang harus dipenuhi dapat dijamin tidak terlanggar. Hal ini akan mem-buat proses heuristic pada Algoritma Genetika menjadi terarah dan membuat keseluruhan proses menjadi lebih efisien.Studi kasus yang diambil pada penelitian ini adalah pada jurusan penulis, yaitu Jurusan Teknik Informatika, FakultasTeknologi Informasi, ITS.Dari analisis hasil uji coba sistem, disimpulkan bahwa sistem telah mampu menangani pemesanan jadwal pada waktutertentu, sistem telah mampu mengolah data matakuliah yang ditawarkan, dan sistem telah mampu menghasilkan jadwaltanpa ada constraint yang terlanggar. Selain itu juga terbukti bahwa algoritma genetika pada sistem telah melakukanoptimasi dalam hal mencari waktu tunggu antar kuliah mahasiswa yang minimal.

kata kunci: algoritma genetika, constraint satisfaction problem, optimasi, penjadwalan matakuliah

Permasalahan penjadwalan untuk pengajaran menda-patkan perhatian dari banyak peneliti. Sejumlah metodetelah dihasilkan untuk mendapatkan jadwal yang optimum.Permasalahan penjadwalan pengajaran klasik didefinisikansebagai berikut [1]:

Terdapat sejumlah m kelas c1, ..., cm, n guru t1, ..., tn,dan p periode 1, ..., p. Terdapat pula matriks integer non-negatif Rm×n, yang disebut matriks requirements, denganrij adalah jumlah pelajaran yang diberikan oleh guru tjpada kelas ci. Permasalahan penjadwalan adalah men-galokasikan kelas pada periode sedemikian sehingga tidakada pengajar dan kelas yang dijadwalkan terjadi pada satupelajaran pada saat yang sama.

Definisi klasik ini belum dapat memenuhi kebutuhan

penjadwalan perkuliahan di Perguruan Tinggi seperti:

• seorang dosen terkadang hanya dapat mengajar padajam-jam dan hari-hari tertentu.

• setiap matakuliah yang diajarkan memiliki alokasisemester sehingga perlu pengaturan agar penjadwal-an matakuliah pada semester yang sama tidak bersa-maan dan mahasiswa pada semester tersebut da -pat mengikuti semua matakuliah yang dialokasikankepadanya.

• dalam satu hari seorang dosen seharusnya maksimalmengajar dua kelas.

Masalah penjadwalan perkuliahan di Perguruan Tinggi

25

Volume 7, Nomor 1, Januari 2008 : 25–34

merupakan masalah NP-hard secara komputasi, sehinggasejumlah penelitian (seperti pada [2, 3, 4, 5]) menerap-kan metode heuristic untuk melakukan otomasi terhadapmasalah penjadwalan.

Masalah penjadwalan perkuliahan berbeda dari satu uni-versitas ke universitas, bahkan dari satu jurusan ke jurusanlain pada universitas yang sama. Pada penelitian ini studikasus yang dipilih adalah masalah penjadwalan pada ju-rusan penulis, yaitu Jurusan Teknik Informatika, FakultasTeknologi Informasi, ITS. Pembuatan jadwal pada Jurusanini harus dilakukan pada setiap pergantian semester. Pada-hal pembuatan jadwal ini membutuhkan waktu, tenaga danketelitian untuk membuatnya. Oleh karena itu diperlukanpenjadwalan otomatis untuk membuat jadwal dengan cepatdan mudah, sehingga masalah pembuatan jadwal mataku-liah dapat diselesaikan dengan lebih efisien. Pembuatanjadwal tersebut harus memperhatikan aturan-aturan pen-jadwalan yang sudah ditentukan.

Pada penelitian ini metode Algoritma Genetika dipadu-kan dengan metode Constraint Satisfaction Problem karenakromosom yang dihasilkan pada metode Algoritma Ge-netika dapat diproses dengan metode Constraint Satisfac-tion Problem sehingga dapat ditemukan batasan-batasanpada penjadwalan yang harus dipenuhi dengan cepat danakurat. Hal ini akan membuat proses heuristic pada Algo-ritma Genetika menjadi terarah dan membuat keseluruhanproses menjadi lebih efisien.

ALGORITMA GENETIKA PADA CONSTRAINT SAT-ISFACTION PROBLEM

Dasar teori yang digunakan dalam sistem ini meliputiConstraint Satisfaction Problem (CSP) dan Algoritma Ge-netika. CSP adalah suatu permasalahan seseorang harusmencari nilai untuk set variabel (finite) yang memenuhiset constraint (finite) [6, 7]. CSP terdiri dari komponen-komponen berikut:

• Variabel, yang merupakan penampung dapat diisi ber-bagai nilai.

• Constraint yang merupakan suatu aturan yang diten-tukan untuk mengatur nilai boleh diisikan ke vari-abel, atau kombinasi variabel.

• Domain yang merupakan kumpulan nilai legal dapatdiisi ke variabel.

• Solusi yang merupakan assignment nilai-nilai daridomain ke setiap variabel tidak ada constraint yangdilanggar.

CSP dimulai dari solusi kosong dan diakhiri dengan se-buah solusi yang memenuhi semua constraint (consistent).Pencarian solusi dilakukan dengan mencoba mengisi nilaidomain pada setiap variabel satu demi satu tanpa melang-gar constraint, sampai solusi ditemukan.

Algoritma yang paling banyak dipakai untuk melakukanpencarian sistematik untuk menyelesaikan CSP adalah back-tracking. Algoritma backtracking search (penelusuran kem-bali) adalah suatu bentuk algoritma depth-first-search. Back-tracking dapat dilihat sebagaimana searching dalam tree,karena setiap node mewakili state dan turunan dari setiapnode mewakili ekstensi dari state tersebut.

Pada metode backtracking, variabel diisi secara sequen-tial selagi semua variabel relevan dengan constraint yangsudah diinisialisasi. Jika solusi partial melanggar constraint,backtracking melakukan langkah kembali ke solusi partialsebelumnya dan memilih nilai lain yang belum dicoba un-tuk variabel yang ingin diisikan. Langkah tersebut bergunauntuk menghindari eksplorasi lebih lanjut dari solusi par-tial yang salah. Keuntungan backtracking adalah pemerik-saan consistency hanya perlu dilakukan terhadap assign-ment yang terakhir dilakukan karena pemeriksaan terhadapassignment yang sebelumnya sudah dilakukan sebelum-nya.

Pada algoritma backtracking, teknik look ahead digu-nakan untuk meramalkan efek pemilihan variabel branch-ing untuk mengevaluasi nilai-nilai variabel tersebut. For-ward checking adalah salah satu cara untuk melakukan lookahead. Forward checking mencegah terjadinya konflik de-ngan melarang nilai-nilai yang belum diisikan ke variabeluntuk dipakai. Ketika suatu nilai diisikan ke suatu variabel,nilai yang berada di domain dari variabel yang konflik de-ngan assignment tersebut akan dihilangkan dari domain.

Minimum Remaining Value (MRV) adalah suatu teknikyang dikembangkan untuk menangani masalah kemungki-nan besar gagal pada pencarian menggunakan CSP.MRV berkerja dengan memilih variabel yang memiliki do-main legal dan paling sedikit (memiliki kemungkinan un-tuk membuat suatu dead-end paling besar) untuk diisikanterlebih dulu.

Algoritma Genetika adalah algoritma pencarian heuris-tik yang didasarkan atas mekanisme evolusi biologis. Se-tiap masalah yang berbentuk adaptasi (alami maupun bu-atan) dapat diformulasikan dalam terminologi genetika. Al-goritma ini adalah simulasi dari proses evolusi Darwin danoperasi genetika atas kromosom.

Metode yang dapat disebut algoritma genetika adalahmetode yang setidaknya memiliki komponen seperti popu-lasi dari kromosom, seleksi berdasarkan fitness, crossoveruntuk memproduksi offspring baru, dan random mutasi pa-da offspring [8].

Seleksi bertujuan untuk memberikan kesempatan re-produksi yang lebih besar bagi anggota populasi yang pa-ling fit [9, 8]. Seleksi akan menentukan individu-individumana saja yang akan dipilih untuk mendapatkan generasibaru.

Crossover adalah proses pertukaran dua kromosom yangmenciptakan offspring yang mewarisi karakter dari keduaparent. Dengan mewarisi karakter parent tersebut, tujuanmelakukan crossover adalah untuk mencari kombinasi genterbaik dari parent.

Operator Mutasi mengubah field individual (gen) di-dalam kromosom berdasarkan pada probabilitas. Mutasidipakai untuk menghindari kecenderungan suatu populasiuntuk menjadi mirip [8].

Fitness adalah suatu nilai yang dipakai untuk tolak ukurkualitas kromosom [9]. Nilai fitness ini digunakan untukmenentukan kromosom yang berkualitas lebih baik dari-pada kromosom yang lain.

Algoritma Genetika memiliki algoritma umum dalammencari solusi melalui pembangkitan populasi kromosom,mekanisme seleksi berdasarkan fitness, crossover untukmemproduksi offspring baru, dan mutasi acak pada off-

26


spring. Namun, algoritma tersebut perlu penyesuaian un-tuk permasalahan yang dihadapi. Pada penelitian ini, Al-goritma Genetika digunakan karena memiliki keunggulanutama, yaitu efisiensi waktu dalam pencarian solusi. Na-mun, algoritma ini juga memiliki kekurangan utama, yaitutidak adanya jaminan solusi yang dihasilkan adalah solusiterbaik (bila dibandingkan dengan pencarian melalui eva-luasi lengkap pada semua kemungkinan solusi).

PERANCANGAN SISTEM PENJADWALANSeperti yang telah dituliskan pada Pendahuluan, studi

kasus yang diambil pada penelitian ini adalah jurusan penu-lis, yaitu Jurusan Teknik Informatika, Fakultas TeknologiInformasi, ITS. Hasil (output) uji coba dari aplikasi diveri-fikasi secara manual untuk membuktikan tidak ada jadwalyang melanggar aturan yang telah ditetapkan.

Agar suatu jadwal dapat dibuat dengan benar, terda-pat sejumlah faktor dan aturan penjadwalan harus diper-hatikan. Faktor-faktor yang berpengaruh dalam pemben-tukan jadwal meliputi:

1. DosenSeorang dosen tidak dapat mengajar beberapa matakuliah pada jam yang sama. Selain itu, seorang dosenterkadang hanya dapat mengajar pada jam-jam danhari-hari tertentu saja, sehingga perlu untuk meme-san jadwal khusus yang tidak dapat diganggu matakuliah yang lain.

2. RuangMengingat jumlah ruang yang dimiliki terbatas, ma-ka perlu diperhatikan ruang yang tersedia agar tidakmenggangu jalannya perkuliahan. Jadwal harus ha-nya mengakomodasi ruang yang ada.

3. WaktuWaktu merupakan batasan berapa menit yang diper-lukan untuk satu jam kuliah. Selain itu, ada hari-hariyang jam kuliah dibatasi sampai dengan jam tertentu(misalnya jam kuliah hari Jumat dibatasi mulai jam07.30 sampai jam 11.00 dan dimulai kembali jam13.00). Dengan batasan-batasan waktu ini, jadwalhanya akan berada pada waktu yang ditentukan.

4. MatakuliahMengingat setiap matakuliah memiliki semester matakuliah itu diajarkan, maka perlu adanya aturan yangmembatasi penjadwalan matakuliah, agar mata-kuliahitu sesuai dengan aturan-aturan penjadwalan.

Aturan-aturan yang harus diperhatikan dalam membuatjadwal meliputi:

• Tidak boleh ada satu ruang yang diisi dua kali dalamsatu waktu yang sama.

• Tidak boleh ada Nomor Induk Pegawai (NIP) dosenyang sama pada hari dan jam yang sama.

• Kemunculan matakuliah pada semester yang samadibatasi maksimal dua kali pada satu hari.

• Pada masing-masing semester, mahasiswa harus da-pat mengambil matakuliah sesuai dengan kurikulumyang ditentukan jurusan sehingga jika mahasiswamengambil matakuliah sesuai kurikulum tidak adamatakuliah yang tidak bisa diambil karena jadwalyang bersamaan dengan jadwal matakuliah lain padasemester yang sama.

• Matakuliah dengan kode matakuliah yang sama (ke-las paralel) harus ada pada hari yang sama, kecualijika dosennya sama.

• Jarak matakuliah antarsemester dengan semester be-rikutnya pada jam yang sama harus lebih besar darijarak yang ditetapkan pengguna. Ini berguna un-tuk memberikan keleluasaan mahasiswa mengambilmatakuliah yang tidak berada pada semester maha-siswa tersebut, misalnya kasus mahasiswa mengu-lang suatu matakuliah atau mahasiswa yang memi-liki Indeks Prestasi tinggi mengambil suatu mataku-liah lain di semester lebih tinggi.

• Dalam satu hari, dosen mengajar maksimal dua ke-las.

Untuk penyimpanan pada sistem digunakan data mas-ter yang tersimpan pada database. Data ini merupakandata untuk membuat jadwal yang diambil dari FRS-onlineJurusan Teknik Informatika ITS (entitas-entitas yang di-ambil adalah entitas dosen, entitas matakuliah, dan entitasmatakuliah yang ditawarkan). Data inisialisasi AlgoritmaGenetika dan Constraint Satisfaction Problem meliputi datasetting_csp, setting_ga, wt_tg, kelas, hari_jam, hasil, hard_c.Hubungan antarentitas ditunjukkan dengan Entity Relation-ship Diagram (ERD) pada Gambar 1.

Data proses adalah data yang digunakan selama pro-ses pembuatan jadwal. Data ini diolah dari data masukandan digunakan untuk menghasilkan data keluaran. Ada-pun data utama pada proses yaitu Pemrosesan AlgoritmaGenetika, dan Pemrosesan Constraint Satisfaction.

Data keluaran adalah informasi yang dihasilkan olehsistem untuk pengguna. Pada tahapan ini akan diperolehjadwal yang telah dioptimasi terhadap waktu tunggu antarkuliah mahasiswa. Jadwal yang dihasilkan tersebut meru-pakan hasil yang dianggap paling baik setelah proses sele-sai. Dengan kata lain, jadwal yang dihasilkan memilikikromosom-kromosom yang memiliki nilai fitness palingbaik.

Pada Gambar 2 dapat dilihat hubungan dan aliran datadalam bentuk Data-Flow Diagram (DFD) level 0 dari sis-tem yang dirancang.

Dekomposisi terhadap DFD level 0 menghasilkan DFDlevel 1 seperti ditunjukkan pada Gambar 3. Terdapat enamproses utama untuk sistem penjadwalan, yaitu: proses Set-ting CSP, proses Setting GA, proses Pemesanan Jadwal,proses Penjadwalan Menggunakan GA, proses Penjadwal-an dengan CSP, dan proses Lihat Jadwal.

Fungsi masing-masing proses pada Gambar 3 adalahsebagai berikut:

1. Proses Setting GA.Proses ini melakukan perubahan nilai setting Algo-ritma Genetika agar algoritma berjalan sesuai yangdiharapkan oleh pengguna.

27


Gambar 1: ERD Sistem Penjadwalan

2. Proses Setting CSP.Proses ini melakukan perubahan nilai setting atauconstraint pada CSP, agar jadwal yang terbentuk se-suai dengan keinginan pengguna. Jika dalam settingterjadi perubahan tahun atau semester, secara lang-sung data pemesanan jadwal pada database akan di-hapus.

3. Proses Pemesanan Jadwal.Proses ini melakukan pemilihan terhadap jadwal ma-takuliah yang memesan waktu dan tempat tertentu

4. Proses Penjadwalan Menggunakan GA.Proses ini melakukan proses pembuatan jadwal de-ngan menggunakan Algoritma Genetika sebagaipengatur arah pencarian nilai yang optimal.

5. Proses Penjadwalan dengan CSP.Proses ini melakukan proses pembuatan jadwal de-ngan menggunakan CSP.

6. Proses Lihat Jadwal.Proses ini menampilkan jadwal yang terbentuk.

Tahapan pada proses Penjadwalan Menggunakan GAdimulai dengan mempersiapkan tabel hasil. Jika tabel hasilsudah diinisialisasi, prosedur Algoritma Genetika akan di-mulai, selanjutnya terjadi pembentukan kromosom padaAlgoritma Genetika. Kromosom dibentuk berdasarkan datakromosom yang datanya tersimpan pada database. Se-telah proses inisialisasi selesai, maka proses mengambilsetting GA untuk mengatur jalannya Algoritma Genetika

sehingga sesuai dengan kebutuhan pengguna. Setelah itu,Algoritma Genetika dijalankan untuk mendapatkan jad -wal matakuliah yang optimal. Pada Gambar 4 ditunjukkanflow-chart proses yang dilakukan Algoritma Genetika.

Proses yang terjadi dalam Algoritma Genetika adalahseperti yang terlihat dalam Gambar 4, yaitu:

1. Mengambil data yang dibutuhkan Algoritma Genetika.

2. Memilih kromosom untuk dilakukan crossover danmutasi. Kemudian hasilnya ditambahkan ke dalampopulasi.

3. Membuat jadwal setiap data kromosom baru denganmenggunakan constraint satisfaction.

4. Mencari nilai waktu tunggu antar kuliah rata-rata ma-hasiswa dari setiap data baru.

5. Menyeleksi jika nilai fitness yang dicari belum ter-capai dan waktu belum habis kembali ke langkah 2.

6. Mengambil kromosom dengan nilai fitness terbaiksebagai solusi dan buat jadwalnya.

Hal-hal yang dilakukan pada proses inisialisasi Algo-ritma Genetika adalah:

1. Menginisialisasi tabel hasil dengan menghapus datayang lama dan mengisikan data default.

2. Mendata setting paramater Algoritma Genetika daridatabase.

28


Gambar 2: DFD Level 0 Sistem Penjadwalan

Gambar 3: DFD Level 1 Sistem Penjadwalan

29


Gambar 4: Flowchart Proses Algoritma Genetika

3. Mendata matakuliah yang ditawarkan dan mataku-liah dari database sebagai data kromosom.

4. Membentuk kromosom sebagai populasi awal.

5. Memproses preprocessing untuk memperkirakan apa-kah jadwal dapat dibuat. Proses ini melakukan penghi-tungan jumlah data yang dibutuhkan untuk mem-buat jadwal dan membandingkannya dengan jumlahdomain yang tersedia. Jika domain tersebut men-cukupi, proses pembuatan jadwal dapat dilanjutkan;sedangkan jika domain tidak mencukupi, jadwal di-anggap tidak dapat dibuat dan proses dibatalkan.

Model Algoritma Genetika yang akan digunakan untukmelakukan optimasi adalah sebagai berikut:

1. Seleksi.Pada seleksi, dilakukan penilaian atas nilai fitness.Akibatnya, fitness yang memiliki kualitas kromosom

paling baik memiliki kemungkinan terpilih ke dalamgenerasi selanjutnya lebih besar. Seleksi yang di-pakai di sini adalah seleksi yang menggunakan meto-de roulette wheel. Pada seleksi ini perlu diperhatikanjumlah maksimal populasi sebagai input, agar popu-lasi tidak menjadi terlalu besar dan memakan banyakwaktu, dan populasi juga tidak menjadi terlalu ke-cil dan mengakibatkan kromosom terlalu mirip se-hingga operasi kromosom tidak akan banyak ber-pengaruh.

2. Crossover.Crossover yang digunakan adalah penyilangan duatitik dengan permutasi. Pemilihan kromosom yangakan di-crossover-kan ditentukan oleh probabilitasyang ditentukan dalam setting parameter AlgoritmaGenetika. Banyak gen yang ditukar juga mengikutisetting parameter Algoritma Genetika. Dalam mela-kukan penyilangan, setiap dua kromosom akan meng-hasilkan dua offspring baru hasil penyilangan.

3. Mutasi.Mutasi dilakukan setelah operasi kromosom ini di-lakukan dengan menukar gen secara random. Dalamproses ini perlu diperhatikan tingkat mutasi dan ting-kat probabilitas terjadi mutasi. Jika sering terjadimutasi, antar generasi selanjutnya akan kehilangankemiripan dan pencarian akan menjadi acak. Tetapi,jika mutasi terlalu sedikit, kromosom akan menjaditerlalu mirip dan kromosom baru akan muncul ter-lalu lama pada populasi.

4. Penentuan Fitness.Penentuan fitness pada dasarnya adalah pemberiannilai kuantitatif yang mewakili kualitas dari kromo-som. Hal pertama yang dilakukan proses ini adalahproses Pembuatan Jadwal sesuai kromosom yang di-pilih dengan memprosesnya dengan Constraint Sat-isfaction Problem, dan hasilnya akan diberi nilai fit-ness.Fungsi fitness yang dibuat merupakan rata-rata waktutunggu antarkuliah mahasiswa dalam satu minggusehingga semakin kecil waktu tunggu maka akan se-makin baik (waktu tunggu antar kuliah mahasiswamenjadi minimal). Rumusan fungsi fitness f(fit)ditunjukkan pada Persamaan (1)

f(fit) =

∑ni=1

R(i)n +

∑mj=1

X(j)m

2(1)

dengan R(i) adalah waktu tunggu antarkuliah ma-hasiswa reguler dalam satu hari, dan X(j) adalahwaktu tunggu antar kuliah mahasiswa ekstensi dalamsatu hari. Nilai n adalah jumlah mahasiswa regulerdalam satu minggu dan m adalah jumlah mahasiswaeks-tensi dalam satu minggu.

Adapun proses yang terjadi pada proses Penjadwalandengan CSP dijelaskan pada uraian berikut. Proses per-tama yang dilakukan adalah mengambil data setting CSPyang dipakai untuk mengatur pembentukan jadwal. Sete-lah itu dilakukan inisialisasi Constraint Satisfaction Prob-lem, yaitu pembentukan solusi awal yang dibentuk dari

30


Gambar 5: Flowchart Pembuatan Jadwal dengan Menggu-nakan CSP

data pesan jadwal yang sudah dibuat. Setelah data pesanjadwal valid maka dilakukan pembuatan jadwal menggu-nakan CSP. Gambar 5 menunjukkan flowchart pembuatanjadwal dengan menggunakan CSP yang dilakukan.Proses yang terjadi dalam pembuatan jadwal pada Gambar5 dapat diuraikan sebagai berikut:

1. Menginisialisasi, yaitu persiapan data yang dibutuh-kan oleh Constraint Satisfaction.

2. Memilih variabel yang ingin diisikan, jika melakukanpemilihan dengan menggunakan MRV maka diam-bil variabel yang memiliki domain paling sedikit,jika tidak menggunakan MRV akan diambil secaraberurutan sesuai urutan pada variabel.

3. Memilih nilai yang masih valid dari domain untukvariabel yang dipilih.

4. Meng-assignment variabel dan domain ke dalam so-lusi, kemudian mengurangi domain valid dari setiapvariabel berdasarkan constraint yang dimiliki vari-abel yang di-assign.

5. Jika solusi sudah terbentuk, dilanjutkan ke langkah6. Jika solusi belum ditemukan kembali ke langkah2.

Tabel 1: Pemesanan Matakuliah pada Semester GenapTahun Ajaran 2006/2007

Id_mk NIP SMT Kelas Hari Jam Ruang

CI1307 130816212 2 A 4 1 1CI1504 051100002 3 XRA 5 4 1CI1205 131996151 8 B 3 1 1CI1422 51100013 6 XA 5 5 1

Tabel 2: Hasil Pembuatan JadwalIdmk Kel NDosen Hari Jam idkel

CI1205 A Joko Lianto B 1 1 1CI1305 C Nunut Priyo J 1 1 2CI1305 B F.X. Arunanto B 1 1 3CI1305 A Nanik Suciati B 1 1 4CI1421 B Ahmad Khoirul Bashori 1 1 5CI1421 A Daniel O. Siahaan 1 1 6CI1307 B Esther Hanaya 1 2 1CI1412 C Ary Mazharuddin Shiddiqi 1 2 2CI1412 A Royyana Muslim I 1 2 3CI1412 B Muchammad Husni 1 2 4CI1424 A Dwi Sunaryono 1 2 5CI1414 A Victor Hariadi 1 3 1CI1414 C Yudhi Purwananto 1 3 2CI1414 B Bilqis Amaliah 1 3 3CI1424 B Dwi Sunaryono 1 3 4CI1501 XRA Handayani Tjandrasa 1 4 1CI1502 XRA Nanik Suciati 1 4 2CI1423 XA Chastine Fatichah 1 5 1CI1205 XA Joko Lianto B 1 5 2CI1202 A Nunut Priyo J 2 1 1CI1202 B Ary Mazharuddin Shiddiqi 2 1 2CI1409 A Darlis Heru Murti 2 1 3CI1423 A Rully Soelaiman 2 1 4CI1202 C Ary Mazharuddin Shiddiqi 2 2 1CI1409 B Darlis Heru Murti 2 2 2CI1423 B Rully Soelaiman 2 2 3CI1203 B Arif Bramantoro 2 3 1CI1203 A Dwi Sunaryono 2 3 2CI1203 C Ahmad Khoirul Bashori 2 3 3CI1422 B Siti Rochimah 2 3 4CI1422 A Isye Ariesanti 2 3 5CI1512 XRA Waskitho Wibisono 2 4 1CI1516 XRA FX.Arunanto 2 4 2CI1421 XA Ahmad Khoirul Bashori 2 5 1CI1205 B Joko Lianto B 3 1 1CI1409 C Darlis Heru Murti 3 1 2CI1422 C Siti Rochimah 3 1 3CI1410 A Imam Kuswardayan 3 2 1CI1410 B Umi Laili Yuhana 3 2 2CI1410 C Umi Laili Yuhana 3 3 1CI1521 XRA Suhadi Lili 3 4 1CI1523 XRA Riyanarto Sarno 3 4 2CI1424 XA Imam Kuswardayan 3 5 1CI1307 A Esther Hanaya 4 1 1CI1307 C Chastine Fatichah 4 1 2CI1411 A Arif Bramantoro 4 1 3CI1411 B Fajar Baskoro 4 1 4CI1411 C Fajar Baskoro 4 2 1CI1522 XRA Suhadi Lili 4 4 1CI1513 XRA Wahyu Suadi 4 4 2CI1504 XRA Irfan Subakti 5 4 1CI1422 XA Isye Ariesanti 5 5 1

6. Jika setiap variabel sudah terisi, solusi sudah terben-tuk, kemudian CSP akan memberikan hasilnya kem-bali ke Algoritma Genetika untuk dievaluasi.

Hal-hal yang dilakukan pada proses inisialisasi CSPadalah:

31


1. Men-setting CSP dari database untuk menentukanconstraint dan metode yang dipakai.

2. Mengalokasikan data matakuliah yang ditawarkan(yang diberikan dari Algoritma Genetika) menjadivariabel yang harus diselesaikan.

3. Mendata hard_c untuk inisialisasi variabel yang dipe-san terlebih dahulu sebelum melakukan penjadwalanpada variabel yang lain.

Model Constraint Satisfaction yang digunakan untukmenyelesaikan masalah penjadwalan adalah sebagai berikut:

1. Penelusuran dengan Backtracking (BT).Algoritma backtracking menggunakan Constructivemethods, yang berarti mengembangkan solusi par-tial sedikit demi sedikit dengan tetap menjaga con-sistency, sehingga mencapai consistent complete as-signment.

2. Forward Checking (FC).Forward checking berkerja dengan membuat suatutabel yang menyatakan nilai domain yang masih ter-sedia untuk setiap variabel. Kemudian pada tabel inidihilangkan domain yang sudah tidak boleh diambillagi.

3. Minimum Remaining Value (MRV).Minimum remaining value dapat bekerja bersamaandengan FC dengan memilihkan variabel yang diisi-kan. Variabel yang dipilih adalah variabel yang me-miliki domain paling sedikit. Pertimbangan yang di-gunakan adalah variabel yang jumlah domain-nyapaling sedikit mempunyai kesempatan gagal lebihbesar. Hal ini dapat memotong percabangan treeyang tidak perlu dan mempercepat waktu pembuatanjadwal.

Pembuatan sistem penjadwalan ini dilakukan denganmenggunakan ASP untuk pembuatan antarmuka dan Ora-cle 9.2.0.1.2 untuk pembuatan proses penjadwalan. Pem-buatan dengan ASP meliputi (i)form halaman depan,(ii)form setting GA, (iii)form setting CSP, (iv)form peme-sanan jadwal, dan (v)form pembuatan jadwal. Sedangkanpembuatan dengan Oracle meliputi implementasi prosesAlgoritma genetika dan implementasi proses ConstraintSatisfaction Problem.

UJI COBAPada tahap uji coba dilakukan dengan tiga skenario

yang ditujukan untuk mengetahui fungsionalitas sistem yangdibuat. Uji coba ini dilakukan dengan menggunakan ling-kungan berspesifikasi sebagai berikut:

Spesifikasi perangkat lunak:

• Microsoft Windows server 2003

• Oracle 9.2.0.2.1

• Quest Software, Toad 7.6

• Microsoft Visual Studio.NET 2003

• ASP.NET

Spesifikasi perangkat keras:

• Athlon XP 1.3 MHz

• RAM 384 MB

• 40 GB Harddisk

Sebelum uji coba dilakukan, terlebih dahulu dipersi-apkan data pada aplikasi (dari database FRS online ITSuntuk mahasiswa Jurusan Teknik Informatika) yaitu datakelas yang ditawarkan. Ada tiga skenario yang akan diuji.

Skenario 1Skenario ini dijalankan untuk menguji kemampuan con-

straint satisfaction dalam membuat jadwal serta menang-ani pemesanan jadwal pada waktu dan kelas tertentu. Da-lam skenario ini, Algoritma Genetika belum difungsikansehingga kemampuan constraint satisfaction dari sistemyang dibuat dapat dibuktikan kebenarannya. Untuk ske-nario ini diambil pemesanan matakuliah pada semester ge-nap tahun ajaran 2006/2007 yang sebagian datanya ditun-jukkan pada Tabel 1.

Constraint utama yang digunakan adalah sebagai beri-kut:

• Tidak ada satu ruangan yang diisikan dua kali dalamsatu waktu yang sama.

• Tidak ada NIP yang sama pada hari dan jam yangsama.

• Tidak ada semester yang sama pada waktu yang sama.

Constraint tambahan yang digunakan adalah sebagaiberikut:

• Pembatasan matakuliah pada semester yang sama ha-nya muncul dua kali pada satu hari.

• Matakuliah dengan kode matakuliah yang sama harusada pada hari yang sama, kecuali jika dosennya sama.

• Jarak antar semester dengan semester berikutnya pa-da jam yang sama harus lebih besar dari jarak yangdiinputkan.

• Dosen yang sama dalam satu hari hanya mengajardua kelas.

Pada Tabel 2 ditunjukkan jadwal yang dihasilkan olehsistem. Waktu proses yang diperlukan untuk menghasilkanjadwal tersebut adalah sekitar 50 detik.

Verifikasi secara manual terhadap hasil pembuatan jad-wal pada Tabel 2 menunjukkan bahwa tidak ada jadwalyang menyalahi constraint yang diberikan sehingga disim-pulkan kemampuan constraint satisfaction pada sistem te-lah bekerja sebagaimana seharusnya.

32


Skenario 2Skenario ini digunakan untuk menguji kemampuan Al-

goritma Genetika untuk mendapatkan jadwal dengan waktutunggu antarkuliah mahasiswa. Setting parameter Algo-ritma Genetika yang digunakan adalah sebagai berikut:

• Populasi maksimum: 10

• Kemungkinan terjadinya crossover: 30

• Kemungkinan terjadinya mutasi: 2

• Jumlah data yang disilangkan: 50

• Nilai fitness yang dituju: 0 (berarti menuju keada-an ideal yaitu tidak ada waktu tunggu antar kuliahmahasiswa).

Pada Tabel 3 ditunjukkan statistik fitness tiap generasi.Waktu yang diperlukan untuk menghasilkan jadwal terse-but adalah sekitar 45 detik.

Dari Tabel 3 terlihat bahwa waktu tunggu mahasiswa(ditunjukkan dengan nilai fitness) semakin lama semakinkecil. Hal ini menunjukkan optimasi pada Algoritma Gene-tika pada sistem telah bekerja sebagaimana seharusnya.

Skenario 3Skenario ini juga dimaksudkan untuk menguji kemam-

puan Algoritma Genetika untuk mendapatkan jadwal de-ngan waktu tunggu antarkuliah mahasiswa seperti Skenario2, tetapi dengan setting parameter Algoritma Genetika yangberbeda, yaitu:

• Maksimum populasi : 10

• Kemungkinan terjadinya crossover : 30

• Kemungkinan terjadinya mutasi : 20

• Jumlah data yang disilangkan : 50

• Waktu maksimal pelaksanaan Algoritma

• Genetika dibatasi maksimal 300 detik

• Nilai fitness yang dicari : 0(berarti menuju keadaan ideal yaitu tidak ada waktutunggu antar kuliah mahasiswa).

Selain itu, pada skenario ini ditetapkan constraint tam-bahan sebagai berikut:

• Pembatasan matakuliah pada semester yang sama ha-nya muncul dua kali pada satu hari.

• Matakuliah dengan kode matakuliah yang sama ha-rus ada pada hari yang sama

• Jarak antarsemester dengan semester berikutnya pa-da jam yang sama harus lebih besar dari jarak yangdiinputkan.

Pada Tabel 4 terlihat statistik fitness tiap generasi yangdihasilkan.

Dari Tabel 4 juga terlihat bahwa waktu tunggu maha-siswa semakin lama semakin kecil. Hal ini menunjukkanbahwa dengan nilai setting parameter yang berbeda, opti-masi pada Algoritma Genetika pada sistem juga telah be-kerja sebagaimana seharusnya.

Tabel 3: Statistik Fitness Setiap Generasi untuk Skenario 2Generasi Fitness Terbaik Fitness Terburuk Fitness Rata-Rata

1 0,501190476 0,501190476 0,5011904762 0,501190476 0,501190476 0,5011904763 0,501190476 0,501190476 0,5011904764 0,501190476 0,501190476 0,5011904765 0,501190476 0,501190476 0,5011904766 0,501190476 0,601190476 0,534523817 0,501190476 0,601190476 0,534523818 0,476190476 0,601190476 0,5284523819 0,476190476 0,601190476 0,51345238110 0,43452381 0,601190476 0,49428571411 0,419642857 0,648809524 0,49089285712 0,392857143 0,648809524 0,48505952413 0,392857143 0,501190476 0,44803571414 0,392857143 0,601190476 0,45535714315 0,392857143 0,601190476 0,4470238116 0,392857143 0,476190476 0,42619047617 0,392857143 0,476190476 0,42619047618 0,392857143 0,476190476 0,41785714319 0,392857143 0,392857143 0,392857143

Tabel 4: Statistik Fitness Setiap Generasi untuk Skenario 3Generasi Fitness Terbaik Fitness Terburuk Fitness Rata-Rata

1 0,375 0,375 0,3752 0,375 0,375 0,3753 0,375 0,375 0,3754 0,375 0,375 0,3755 0,375 0,375 0,3756 0,375 0,375 0,3757 0,375 0,375 0,3758 0,375 0,375 0,3759 0,375 0,375 0,37510 0,375 0,375 0,37511 0,375 0,402777778 0,38888888912 0,361111111 0,402777778 0,38333333313 0,208333333 0,402777778 0,36284722214 0,208333333 0,516666667 0,38361111115 0,208333333 0,572222222 0,39194444416 0,208333333 0,572222222 0,39194444417 0,208333333 0,516666667 0,36333333318 0,208333333 0,516666667 0,36055555619 0,208333333 0,405555556 0,34666666720 0,208333333 0,405555556 0,32472222221 0,180555556 0,488888889 0,29694444422 0,180555556 0,488888889 0,297777778

SIMPULANBerdasarkan analisis hasil uji coba sistem maka dapat

diambil kesimpulan-kesimpulan berikut:

1. Melalui percobaan skenario 1 dengan mengolah jad-wal pada semester genap tahun ajaran 2006/2007,sistem telah mampu menangani pemesanan jadwalpada waktu tertentu, telah mampu mengolah datamatakuliah yang ditawarkan, dan telah mampu meng-hasilkan jadwal tanpa ada kendala yang terlanggar.

2. Melalui pengamatan statistik yang dihasilkan daripercobaan skenario 2 terlihat bahwa Algoritma Gene-tika pada sistem telah melakukan optimasi dalam halmencari waktu tunggu antarkuliah mahasiswa yangminimal.

3. Studi kasus yang diambil pada penelitian ini adalahpada jurusan penulis, yaitu Jurusan Teknik Informati-ka, Fakultas Teknologi Informasi, ITS. Aplikasi yang

33


dibuat dapat diterapkan pada masalah penjadwalanmatakuliah di Jurusan lain dengan menyesuaikan datamasukan beserta constraint yang berlaku pada Juru-san tersebut.

DAFTAR PUSTAKA

[1] Werra, D.D.: An Introduction to Timetabling. Eu-ropean Journal of Operational Research 19(2) (1985)151–162

[2] Arntzen, H., Løkketangen, A.: A Local SearchHeuristic for a University Timetabling Prob-lem. Technical report, Dalle Molle Institute forArtificial Intelligence (2007) Diakses 31 Au-gust 2007, http://www.idsia.ch/Files/ttcomp2002/arntzen.pdf.

[3] Chiarandini, M., Birattari, M., Socha, K., Rossi-Doria, O.: An Effective Hybrid Algorithm for Univer-sity Course Timetabling. Journal of Scheduling 9(5)(2006) 403–432

[4] Corr, P.H., McCollum, B., McGreevy, M.A.J., Mc-Mullan, P.J.P.: A New Neural Network-based Con-

struction Heuristic for the Examination TimetablingProblem. In: Parallel Problem Solving from Nature- PPSN IX, 9th International Conference, LNCS 4193.(2006) 392–401

[5] Ozcan, E., Alken, A.: Timetabling using a SteadyState Genetic Algorithm. In: The 4th internationalconference on the Practice And Theory of AutomatedTimetabling. (2002)

[6] Barták, R.: On-Line Guide To Constraint Program-ming. http://kti.mff.cuni.cz/~bartak/constraints/ (2007)

[7] Madsen, J.N.: Methods for Interactive Constraint Sat-isfaction. Master’s thesis, Department of ComputerScience, University of Copenhagen (2003)

[8] Mitchell, M.: An Introduction to Genetic Algorithms.The MIT Press (1999)

[9] Kusumadewi, S., Purnomo, H.: Penyelesaian MasalahOptimasi dengan Teknik-teknik Heuristik. Graha Ilmu(2005)

34

penjadwalan matakuliah dengan menggunakan algoritma genetika

Documents