perancangan dan implementasi finite...

4

1. Pendahuluan

Jadwal mata kuliah menjadi salah satu bagian terpenting dalam proses belajar

mengajar suatu lembaga pendidikan, termasuk Fakultas Psikologi Universitas

Kristen Satya Wacana. Banyaknya jumlah mata kuliah dan dosen yang terlibat,

mengakibatkan sering terjadinya bentrokan jadwal mata kuliah atau pun dalam

pemakaian ruang perkuliahan.

Terdapat beberapa aspek yang perlu dipertimbangkan dalam menyusun jadwal

mata kuliah yang baik. Pada Aspek dosen perlu dihindari adanya jadwal mengajar

2 (dua) mata kuliah yang berbeda pada hari dan jam yang sama. Pada aspek ruang,

ketersediaan ruang pun menjadi pertimbangan tersendiri dan menjadi poin penting

yang tidak dapat diabaikan dalam pembuatan jadwal mata kuliah, di mana dalam

pembuatan setiap jadwal mata kuliah, harus melihat ketersediaan ruang yang ada

serta kapasitas maksimal masing-masing ruang. Proses penyusunan jadwal mata

kuliah atau yang dalam istilah asing disebut university timetabling problem ini

bukanlah pekerjaan mudah dan kerap kali terjadi kesalahan. Sejauh ini Fakultas

Psikologi Universitas Kristen Satya Wacana masih melakukan penyusunan jadwal

mata kuliah secara manual. Selain rentan terjadi kesalahan dalam pelaksanaannya,

proses penyusunan jadwal mata kuliah tersebut juga merepotkan serta kurang

efektif dan efisien, sehingga diperlukan sebuah aplikasi guna mempermudah

proses penyusunan jadwal mata kuliah tersebut. Dalam aplikasi tersebut

diperlukan pula metode optimasi untuk memperoleh hasil yang terbaik, mengingat

banyaknya aspek yang harus dipertimbangkan. Sehingga dibutuhkan algoritma

yang dapat menyelesaikan masalah multi-kriteria dan multi-objektif, seperti

penyusunan jadwal mata kuliah. Salah satu algoritma yang dapat digunakan

adalah steepest ascent hill climbing. Berdasarkan latar belakang tersebut, muncul

sebuah ide untuk membuat sebuah penjadwalan mata kuliah menggunakan

algoritma steepest ascent hill climbing.

2. Kajian Pustaka

Penelitian tentang penjadwalan mata kuliah telah cukup banyak dilakukan.

Pada penelitian berjudul Aplikasi Algoritma Genetik untuk Optimasi Penjadwalan

Kegiatan Belajar Mengajar, diperoleh hasil bahwa aplikasi penjadwalan mata

kuliah dapat menyusun jadwal mata kuliah secara optimal, selain itu dapat

meminimalkan frekuensi mengajar seorang dosen, frekuensi kuliah suatu kelas

dan faktor pengaruh lainnya [1]. Penelitian lainnya, yaitu Penggunaan Tabu

Search dalam Penjadwalan Kuliah dan Ujian Perguruan Tinggi (Studi Kasus :

Sekolah Tinggi Manajemen Bandung) diperoleh kesimpulan bahwa aplikasi

penjadwalan ini mempermudah bagian sekretariat dalam menyusun jadwal kuliah

dan ujian pada tiap semesternya [2].

Demikian pula dengan penerapan algoritma steepest ascent hill climbing

dalam suatu aplikasi atau pun penelitian mengenai algoritma tersebut telah cukup

banyak dilakukan. Penelitian yang membahas tentang Implementasi Metode

Steepest Ascent Hill Climbing pada Mikrokontroler MCS51 untuk Robot Mobil

Pencari Jalan Terpendek diperoleh kesimpulan bahwa algoritma steepest ascent

5

hill climbing dapat diterapkan pada masalah pencarian jarak terpendek serta dapat

bekerja dengan cukup baik [3]. Penelitian lain tentang Algoritma Steepest Ascent

Hill Climbing untuk Menyelesaikan Masalah Penugasan menunjukkan bahwa

algoritma steepest ascent hill climbing dapat melakukan perhitungan yang akurat

pada kasus penugasan [4].

Berdasarkan penelitian sebelumnya terkait penjadwalan mata kuliah, dan

penelitian penerapan algoritma steepest ascent hill climbing, maka melalui

penelitian ini akan dirancang sebuah penjadwalan mata kuliah menggunakan

algoritma steepest ascent hill climbing. Algoritma steepest ascent hill climbing

memiliki keunggulan di mana semua solusi yang mungkin akan dibangkitkan

kemudian akan diperiksa satu persatu, sehingga akan diperoleh solusi terbaik dan

mendekati hasil optimasi yang diharapkan.

Algoritma Steepest Ascent Hill Climbing Algoritma steepest ascent hill climbing adalah salah satu algoritma yang

sering digunakan untuk memecahkan masalah optimasi. Secara harafiah steepest

berarti tertinggi, sedangkan ascent adalah kenaikan. Sehingga steepest ascent

dapat diartikan sebagai kenaikan tertinggi, di mana prinsip dasar dari algoritma ini

adalah mencari kenaikan tertinggi dari solusi-solusi yang mungkin terjadi, untuk

mencapai nilai yang paling optimal [5].

Algoritma steepest ascent hill climbing merupakan pengembangan dari

algoritma simple hill climbing. Perbedaan kedua algoritma ini adalah, pada simple

hill climbing, next state akan ditentukan dengan membandingkan current state

dengan satu successor saja. Proses pembandingan ini dimulai dari sebelah kiri.

Apabila ditemukan successor baru yang lebih baik dari current state maka

successor tersebut akan menjadi next state. Sedangkan pada steepest ascent hill

climbing dalam menentukan next state, current state akan dibandingkan dengan

semua successor yang ada di dekatnya, sehingga next state yang diperoleh

merupakan successor yang paling baik serta mendekati hasil optimasi yang

diharapkan. Selain itu pada steepest ascent hill climbing urutan penggunaan

operator tidak berpengaruh terhadap solusi, sedangkan pada simple hill climbing

urutan penggunaan operator sangat berpengaruh.

Adapun urutan atau langkah dari algoritma steepest ascent hill climbing

[5] adalah sebagai berikut : (1) Pada keadaan awal dilakukan pengujian: jika

merupakan tujuan maka berhenti; dan jika tidak maka lanjutkan pencarian dengan

keadaan sekarang sebagai keadaan awal; (2) Lakukan proses berikut tujuan

tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang :;

(a) Tentukan SUCC sebagai nilai heuristik terbaik dari successor-successornya;

(b) Lakukan proses berikut untuk tiap operator yang digunakan oleh keadaan

sekarang :; (i) Gunakan operator tersebut dan bentuk keadaan baru.; (ii) Evaluasi

keadaan baru yang diperoleh. Jika merupakan tujuan, keluar. Jika bukan,

bandingkan nilai heuristik yang ada dengan SUCC, apabila lebih baik, jadikan

nilai heuristik keadaan baru sebagai SUCC. Namun apabila tidak lebih baik, maka

nilai SUCC tetap.; (c) Jika SUCC lebih baik dari nilai heuristik keadaan sekarang,

ubah node SUCC menjadi keadaan sekarang.

6

Algoritma steepest ascent hill climbing mempunyai rumus untuk memperoleh

banyaknya solusi yang diperoleh apabila terdapat n operator yaitu :

Profil Fakultas Psikologi UKSW

Fakultas Psikologi UKSW merupakan salah satu fakultas yang bisa

dibilang cukup favorit di UKSW, terlihat dari jumlah mahasiswa baru tiap

tahunnya yang cukup banyak. Pada sisi pelayanan dan kegiatan operasional

fakultas, Fakultas Psikologi UKSW bisa dibilang belum banyak menerapkan

sistem yang dapat mempermudah proses yang ada, demikian juga dengan proses

pembuatan jadwal mata kuliah. Pihak Fakultas Psikologi UKSW selama ini dalam

pembuatan jadwal mata kuliah masih menggunakan cara konvensional, di mana

petugas menyusun jadwal menggunakan software Microsoft Excel. Informasi

yang terkait penjadwalan mata kuliah Fakultas Psikologi UKSW ditunjukkan oleh

tabel 1. Tabel 1 Informasi Terkait Penjadwalan Mata Kuliah Fakultas Psikologi UKSW

Keterangan

Mata Kuliah Total 85 mata kuliah, di mana pada setiap

semesternya dibuka sekitar 40 mata kuliah

Berbobot 2-3 SKS, namun terdapat satu mata

kuliah yaitu Kode Etik Psikologi yang

berbobot 1 SKS

Tenaga Pengajar Terdapat 18 dosen tetap, dengan beberapa

tambahan dosen luar

Ruang

Perkuliahan

GXY 102, E 134, ABX 104, GXY 101, GX

204

Stiba H2, Stiba H3, Stiba H4 (khusus Mata

Kuliah Bhs. Inggris)

Jumlah

Mahasiswa

700 orang (per tahun ajaran 2011-2012)

Terdapat beberapa aspek yang perlu dipenuhi dalam menyusun jadwal

mata kuliah Fakultas Psikologi UKSW, di mana aspek tersebut menentukan

kualitas dari jadwal mata kuliah yang dihasilkan. Aspek tersebut adalah : (1)

Dosen dapat mengajar lebih dari satu mata kuliah, namun tidak boleh terjadi

tabrakan pada dosen yang bersangkutan. Misalnya seorang dosen mengajar dua

mata kuliah yang berbeda namun pada jam yang sama; (2) Satu mata kuliah dapat

diampu oleh 2 orang dosen; (3) Beban maksimal mengajar seorang dosen adalah 9

SKS; (4) Satu ruang perkuliahan tidak dapat digunakan untuk 2 mata kuliah atau

lebih pada waktu yang bersamaan atau bertabrakan; (5) Ketersediaan ruang

dengan kapasitas yang cukup untuk setiap mata kuliah yang ada; (6) Kegiatan

belajar mengajar berlangsung dari pukul 7 pagi hingga pukul 4 sore.

Pembuatan jadwal mata kuliah Fakultas Psikologi UKSW membutuhkan

ketelitian yang lebih, mengingat banyaknya aspek yang perlu diperhatikan.

Kerumitan inilah yang sering kali menyebabkan terjadinya kesalahan dalam

pengaturan jadwal sehingga memungkinkan satu ruang perkuliahan digunakan

n!

2!(n-2)!

7

pada waktu yang bersamaan untuk 2 mata kuliah yang berbeda ataupun dosen

yang mengajar mata kuliah yang berbeda pada waktu yang bersamaan. Selain itu

diperlukan waktu yang cukup lama sampai benar-benar memperoleh jadwal mata

kuliah yang optimal, sehingga kurang efisien.

3. Metode dan Perancangan Sistem

Metode penelitian yang digunakan dalam pengembangan sistem adalah

Prototype Model. Prototype Model adalah metode pengembangan perangkat lunak

yang banyak digunakan. Metode ini memungkinkan adanya interaksi antara

pengembang sistem dengan pengguna sistem nantinya, sehingga dapat mengatasi

ketidakserasian antara pengembang dan pengguna. Bagan mengenai prototype

model dapat dilihat pada Gambar 1.

Gambar 1 Bagan Prototype Model [6]

Tahap-tahap dalam Prototype Model adalah sebagai berikut: (1) Listen to

Costumer, di mana dilakukan analisis mengenai kebutuhan pengguna sistem

dilakukan berdasar proses bisnis yang ada. Hanya terdapat 2 (dua) pengguna yaitu

pembuat jadwal itu sendiri serta administrator. Kebutuhan dari pembuat jadwal

adalah sebagai berikut : membuat jadwal mata kuliah, dapat memperoleh

informasi mengenai mata kuliah-mata kuliah yang ada, dapat memperoleh

informasi mengenai dosen, serta mata kuliah yang diampu oleh masing-masing

dosen pada jadwal mata kuliah, dapat memperoleh informasi mengenai ruang

perkuliahan yang tersedia, serta jadwal penggunaan ruang berdasar jadwal mata

kuliah, dapat menentukan mata kuliah apa saja yang ada pada jadwal yang dibuat,

dapat menentukan banyak kelas untuk setiap mata kuliah yang ada pada jadwal

yang dibuat, dapat menentukan jumlah dosen pengampu mata kuliah pada jadwal

yang dibuat. Sedangkan untuk Administrator : dapat melakukan manipulasi data

mata kuliah, dapat melakukan manipulasi data dosen, dapat melakukan manipulasi

data ruang kelas; (2) Build, setelah memperoleh informasi dan kebutuhan lainnya

guna merancang sebuah aplikasi web penjadwalan mata kuliah dengan algoritma

steepest ascent hill climbing, langkah berikutnya adalah membangun perancangan

dengan menggunakan UML atau Unified Modelling Languange mengenai sistem

yang akan dibangun nantinya. Selain itu dilakukan pula perancangan pada user

interface dan algoritma. Kemudian rancangan sistem akan diterjemahkan ke

dalam bahasa pemrograman PHP 5 dan untuk interface sistem dibangun dengan

8

menggunakan bahasa pemrograman HTML dan CSS; (3) Costumer Test, tahap ini

dilakukan guna melihat apakah dari prototype yang dibuat sudah memenuhi

ekspektasi dan kriteria sistem yang akan dikembangkan. Apabila sudah memenuhi

maka akan dilanjutkan ke tahap berikutnya, namun apabila belum maka akan

kembali ke tahap awal yaitu pengumpulan kebutuhan, membangun prototype dan

melakukan evaluasi kembali sampai prototype sesuai dengan apa yang

diharapkan.

Perancangan Sistem

Sistem dirancang dengan menggunakan UML (Unified Modelling

Language) yang terdiri dari use case diagram, activity diagram, class diagram

dan deployment diagram.

Pada use case diagram, seorang user harus melakukan login terlebih

dahulu ke dalam sistem, di mana login akan menentukan hak akses dari seorang

user. Terdapat dua akses yaitu administrator dan pembuat jadwal seperti pada

Gambar 2.

Gambar 2 Use Case Diagram

Pada sistem terdapat beberapa fungsi yang tersedia dalam hak akses

sebagai pembuat jadwal. Selain dapat membuat jadwal, seorang pembuat jadwal

juga dapat memperoleh informasi mengenai mata kuliah, memperoleh informasi

mengenai dosen, memperoleh data ruang kuliah, menentukan mata kuliah yang

ada pada jadwal, menentukan banyak kelas untuk setiap mata kuliah pada jadwal,

menentukan banyak dosen pengampu masing-masing mata kuliah, serta melihat

jadwal yang telah dibuat. Sedangkan fungsi yang ada pada hak akses sebagai

administrator adalah dapat melakukan manipulasi data mata kuliah, dosen atau

pun ruang kuliah, di mana fungsi manipulasi di sini meliputi fungsi untuk`dapat

menambah data (insert), menghapus data (delete), serta mengubah data (update).

Class diagram menggambarkan struktur dan deskripsi, entity, controller,

dan boundry serta hubungannya satu sama lain. Aplikasi yang dibuat memiliki

class diagram seperti yang terlihat pada Gambar 6.

9

Gambar 3 Class Diagram Sistem

Class Diagram sistem ditunjukkan oleh Gambar 3, di mana class diagram

tersebut terdiri 3 bagian utama yaitu entity, controller dan boundry. Terdapat 5

(lima) entity pada class diagram yang ditunjukkan oleh Gambar 6, yaitu entity

tbdosen, tbruang, tbmatakuliah, tbjadwal dan tbuser. Tbdosen terdiri dari 5 (lima)

field yaitu idDosen, KodeDosen, Nama, idMK, BebanSKS. Tbruang terdiri dari 3

(tiga) field yaitu idRuang, KodeRuang, dan Kapasitas. Pada tbmatakuliah terdapat

8 (delapan) field yaitu idMK, KodeMK, MK, SKS, Semester, Keterangan,

Bidang, dan Sem. Sedangkan pada tbjadwal terdapat 12 (dua belas) field yaitu

KodeMK, MK, SKS, KodeDosen, Nama, KodeDosen, Nama, KodeRuang,

Kapasitas, hari, jammulai, jamselesai, thnajaran, Angkatan.

Pada setiap entity terdapat sebuah controller yang bertugas untuk

menampung fungsi-fungsi manipulasi pada database. Fungsi manipulasi tersebut

antara lain adalah insert, update, dan delete. Pada setiap controller juga terdapat

sebuah boundry yang berupa user interface. Deployment diagram berfungsi untuk menampilkan rancangan fisik

jaringan dalam sistem. Gambar 7 menunjukkan bahwa terdapat 4 (Empat)

komponen dalam proses deployment, yaitu Model, Controller, Database, dan

Client sebagai pengakses sistem

10

Gambar 4 Deployment Diagram Sistem

Seperti yang terlihat pada Gambar 4 saat client mengakses sistem dan

mengirimkan request tertentu, maka request akan diproses terlebih dahulu oleh

model yang kemudian akan diteruskan kepada controller. Controller sendiri

menampung fungsi-fungsi manipulasi database yang diperlukan oleh sistem. Saat

request dari client diterima, akan ditentukan fungsi manipulasi yang sesuai dan

kemudian akan diteruskan ke database. Setelah respond diterima selanjutnya

respond akan dikembalikan melalui controller dan model, hingga diterima oleh

client.

11

Rancangan Algoritma Steepest Ascent Hill Climbing

Rancangan algoritma steepest ascent hill climbing pada sistem dalam

bentuk flow chart dapat dilihat pada Gambar 5.

Gambar 5 Flow Chart Algoritma Steepest Ascent Hill Climbing pada Sistem

Langkah-langkah penerapan algoritma steepest ascent hill climbing pada

sistem adalah sebagai berikut : (1) Proses dimulai dengan user memasukkan

parameter pada masing-masing mata kuliah. Parameter yang ada meliputi

kapasitas, jumlah kelas dan dosen pengampu; (2) Memilih mata kuliah apa saja

yang ada pada jadwal; (3) Diperoleh sebuah variabel yaitu JumData yang

12

mengacu pada banyaknya data (mata kuliah); (4) Diperoleh variabel JumlahKelas

yang mengacu pada jumlah kelas pada masing-masing mata kuliah; (5)

Selanjutnya akan dilakukan perulangan sebanyak jumlah data mata kuliah; (6)

Akan dibangkitkan solusi jadwal yang mungkin terjadi pada setiap perulangan

secara random, sebanyak jumlah kelas pada masing-masing mata kuliah. Solusi

jadwal yang diperoleh akan dicek dengan beberapa kriteria untuk menentukan

apakah merupakan sebuah solusi atau tidak. Solusi jadwal yang dibangkitkan

secara random akan memiliki nilai heuristik yang dilambangkan dengan variabel

h dan bernilai 0 (nol) pada awal proses. Pada setiap proses pengecekan solusi,

nilai variabel h akan bertambah seiring dengan hasil yang diperoleh; (7) Pertama-

tama solusi jadwal akan dicek, apakah dosen pengampu memiliki sisa beban SKS

yang cukup yaitu beban SKS kurang dari atau sama dengan 9 (sembilan). Apabila

hasil yang diperoleh adalah ya maka akan berlanjut pada tahap berikut dan nilai

h=1, namun apabila hasil yang diperoleh tidak, maka solusi jadwal bukan

merupakan solusi yang tepat dan akan dibangkitkan solusi jadwal lain secara

random dan kembali ke pengecekan awal; (8) Tahap berikutnya akan dilakukan

pengecekan apakah solusi jadwal yang diperoleh tidak ada tabrakan pada dosen.

Tabrakan yang dimaksud adalah dosen mengajar pada jam dan hari yang sama

untuk 2 (dua) mata kuliah. Apabila hasil yang diperoleh adalah tidak, maka nilai

h=2 dan akan berlanjut pada proses pengecekan berikutnya. Apabila hasil yang

diperoleh adalah ya, maka solusi jadwal bukan merupakan solusi yang tepat dan

akan dibangkitkan solusi jadwal lain secara random dan kembali ke pengecekan

awal; (9) Pada proses pengecekan berikutnya solusi jadwal akan dilihat apakah

ada tabrakan pada pemakaian ruang. Tabrakan pemakaian ruang berarti sebuah

ruang perkuliahan dipakai pada jam dan hari yang sama oleh 2 (dua) mata kuliah.

Apabila hasil yang diperoleh adalah tidak, maka nilai h=3 dan akan berlanjut pada

proses berikutnya. Apabila hasil yang diperoleh adalah ya, maka solusi jadwal

bukan merupakan solusi yang tepat dan akan dibangkitkan solusi jadwal lain

secara random dan kembali ke pengecekan awal; (10) Setelah dilakukan

pengecekan dan nilai h=3, maka solusi jadwal disimpulkan sebagai solusi yang

tepat dan ditampilkan; (11) Solusi jadwal yang diperoleh akan disimpan sebagai

solusi pembanding untuk solusi yang lain; (12) Langkah berikutnya adalah

kembali ke langkah awal untuk membangkitkan solusi secara random; (13)

Apabila nilai j sama dengan JumlahKelas, maka akan kembali ke perulangan awal

dan dimulai proses untuk solusi jadwal mata kuliah yang lain; (14) Proses

berulang terus menerus hingga diperoleh jadwal mata kuliah yang lengkap.

13

4. Hasil dan Pembahasan

Penerapan Algoritma Steepest Ascent Hill Climbing

Kode Program 1 Fungsi Mengenerate Solusi Jadwal Secara Random

Kode Program 1 menunjukkan fungsi untuk mengenerate solusi jadwal

mata kuliah secara random. Solusi jadwal yang diperoleh disesuaikan dengan

mata kuliah pada jadwal yang akan dibuat, serta jumlah SKS dan kapasitas pada

masing-masing mata kuliah. Solusi jadwal akan mengkombinasikan secara acak

mata kuliah dengan dosen pengampu diikuti hari, jam mulai, dan jam selesai

sebagai waktu mengajar dosen sekaligus pemakaian ruang. Baris 1 merupakan

nama dari fungsi yaitu jadwal, serta parameter-parameter yang dibutuhkan untuk

mengambil jadwal. Baris 5-14 adalah query yang dieksekusi saat fungsi jadwal

dijalankan.

1. function jadwal($KodeMK,$SKS,$Kapasitas,$jumlahkelas) { 2. $DOCUMENT_ROOT = $_SERVER["DOCUMENT_ROOT"]; 3. include_once $DOCUMENT_ROOT."/PenjadwalanPsi/connectDB/sqlLib.php"; 4. $sqlLib = new sqlLib(); 5. $sql ="select a.idMK, a.KodeMK, a.MK, a.SKS, a.Semester, a.Keterangan,a.Sem, 6. b.idDosen, b.KodeDosen, b.Nama, b.idMK, b.BebanSKS, 7. c.idRuang, c.KodeRuang, c.Kapasitas, c.Makul, 8. d.idHari,d.hari, 9. e.idMulai, e.jammulai, 10. f.idSelesai,f.jamselesai

11. from tbmatakuliah a, tbdosen b,tbruang c, tbhari d, tbjammulai e,

dbjamselesai f

12. where a.idMK=b.idMK and a.KodeMK = '$KodeMK' and (f.jamselesai-

e.jammulai=$SKS)

13. and c.Kapasitas >= $Kapasitas and c.Makul not like '%Bahasa Inggris%'

14. order by rand()";

15. $rows = $sqlLib->select($sql);

16. return $rows;}

14

Kode Program 3 Script Pengecekan Solusi Algoritma Steepest Ascent Hill Climbing pada Sistem

Kode Program 3 merupakan script untuk mengecek solusi jadwal mata

kuliah apabila dosen pengampu adalah 1. PengeBaris 1 merupakan perintah untuk

menampung hasil fungsi jadwal sebagai row. Baris 2-15 merupakan perintah

untuk memperoleh data-data hasil fungsi jadwal berdasar nama kolom. Baris 17-

20 adalah perintah untuk mengambil data beban mengajar tiap dosen. Data beban

berkaitan dengan beban maksimal mengajar tiap dosen sebanyak 9 SKS. Baris 21-

24 merupakan perintah untuk memperoleh data abjad yang digunakan dalam

penamaan kode mata kuliah dan mata kuliah pada jadwal. Baris 28 merupakan

perintah untuk mengecek apakah jumlah kelas sudah mencukupi atau belum. Baris

27 dan 28 adalah variabel yang menampung kombinasi jadwal mengajar dan

pemakaian ruang kuliah agar dapat dilakukan pengecekan. Baris 31 adalah

inisialisasi nilai heuristik yang dilambangkan dengan variabel h, nilai h pada tahap

awal adalah 0 (nol). Baris 32 adalah perintah untuk melakukan pengecekan

terhadap beban SKS dosen, apabila bernilai beban mengajar dosen mencukupi

maka nilai h akan bertambah 1. Baris 34 merupakan perintah untuk

membandingkan data mengajar yang diperoleh dengan data mengajar successor.

Apabila tidak terjadi tabrakan, maka nilai h akan bertambah 1. Baris 36 adalah

1. foreach ($datajadwal as $row) { 2. $idMKCurent = $row["idMK"]; 3. $KodeMK = $row["KodeMK"]; 4. $MK = $row["MK"]; 5. $namaDosen = $row["Nama"]; 6. $sksCurrent = $row["SKS"]; 7. $idDosen = $row["idDosen"]; 8. $KodeDosen = $row["KodeDosen"]; 9. $idRuang = $row["idRuang"]; 10. $Ruang = $row["KodeRuang"];

11. $idHari = $row["idHari"];

12. $Hari = $row["hari"];

13. $JamMulai = $row["jammulai"];

14. $JamSelesai = $row["jamselesai"];

15. $Sem = $row["Sem"];

16. $Beban=$sksCurrent;

17. $getTotalBeban= selectBeban($KodeDosen);

18. foreach ($getTotalBeban as $row) {

19. $Bebanx=$row["totalbeban"];

20. }

21. $getabjad = getAbjad($j+1);

22. foreach ($getabjad as $row) {

23. $abjad = $row["abjad"];

24. }

25. $totalbeban=$Bebanx+$Beban;

26. if($j<$jumlahkelas) {

27. $iddosenmengajar= $namaDosen.$Hari.$JamMulai.$JamSelesai;

28. $idpakairuang = $Ruang.$Hari.$JamMulai.$JamSelesai;

29. $h=0;

30. if($totalbeban <=9) {

31. $h++;

32. if((strpos($idDosenMengajarSUCC, $iddosenmengajar) ==

NULL)&&(strpos($idDosenMengajarSUCC, $iddosenmengajar) !== 0)) {

33. $h++;

34. if ((strpos($idPakaiRuangSUCC, $idpakairuang) ==

NULL)&&(strpos($idPakaiRuangSUCC, $idpakairuang) !== 0)) {

35. $h++;

36. if($h==3) {

15

perintah untuk membandingkan data pemakain ruang yang diperoleh dengan data

pemakaian ruang successor. Apabila tidak terjadi tabrakan, maka nilai h akan

bertambah 1. Apabila nilai h adalah 3 maka solusi penjadwalan yang diperoleh

akan dianggap sebagai solusi penjadwalan yang optimal dan akan ditampilkan

pada sistem.

Kode Program 9 Script Penyimpanan Solusi

Kode Program 9 merupakan perintah untuk menyimpan solusi yang

diperoleh ke dalam nilai dosen mengajar successor dan nilai pemakaian ruang

kuliah successor. Nilai successor ini akan digunakan sebagai variabel pembanding

solusi jadwal.

Analisis dan Pengujian Aplikasi

Evaluasi Prototype

Setelah prototype pertama selesai, maka dilakukan evaluasi prototype.

Pada evaluasi pertama diperoleh hasil sebagai berikut:

- Dosen hanya boleh mengajar dengan beban maksimal 9 SKS.

- Pada halaman pilih mata kuliah, tambahkan fungsi check all untuk

mempermudah proses pemilihan data mata kuliah.

- Penambahan data ruang kuliah, yaitu Stiba H2, Stiba H3, dan Stiba H4, yang

hanya digunakan untuk mata kuliah Bahasa Inggris.

- Pada halaman pembuat jadwal mata kuliah, ditambahkan halaman untuk

melihat jadwal mengajar dosen dan penggunaan ruang kuliah berdasar jadwal.

Pengujian dan Analisis

Pengujian aplikasi dilakukan oleh developer, di mana developer akan

memasukkan input kemudian akan dilihat output yang diperoleh. Pengujian

aplikasi juga dilakukan oleh user untuk mencoba dan melakukan pengecekan pada

setiap fungsi yang ada untuk mengetahui apakah ada bug dan apakah sudah sesuai

dengan requirement sebelumnya.

1. if($sksCurrent==3) { 2. $idDosenMengajarSUCC=$idDosenMengajarSUCC." ".$iddosenmengajar.”

".$iddosenmengajarexception1; $idPakaiRuangSUCC=$idPakaiRuangSUCC."

".$idpakairuang." ".$idpakairuangexception1; }

16

Gambar 6 Halaman Awal Buat Jadwal Mata Kuliah

Pengujian pada halaman pembuat jadwal dilakukan dengan mencoba

membuat jadwal mata kuliah baru. Gambar 6 menunjukkan halaman awal dalam

proses membuat jadwal mata kuliah. Pembuat jadwal dalam membuat jadwal mata

kuliah, dapat memilih semester serta melakukan input tahun ajaran jadwal yang

akan dibuat. Pada Gambar 6 jadwal yang akan dibuat adalah jadwal pada

Semester Genap Tahun Ajaran 2011-2012.

Gambar 7 Halaman Pilih Mata Kuliah

Setelah menentukan semester serta tahun ajaran jadwal yang akan dibuat,

langkah berikutnya adalah menentukan mata kuliah yang akan terlibat dalam

jadwal. Gambar 7 menunjukkan tampilan pada halaman pembuat jadwal saat

memilih mata kuliah. Selain kode mata kuliah, nama mata kuliah dan jumlah sks,

terdapat text box yang digunakan untuk input kapasitas kelas serta jumlah kelas

masing-masing mata kuliah. Terdapat pula combo box untuk menentukan jumlah

dosen pengampu mata kuliah dan check box untuk memilih mata kuliah.

Sistem kemudian akan mengenerete solusi jadwal yang mungkin untuk

setiap mata kuliah. Gambar 8 menunjukkan solusi jadwal mata kuliah Bahasa

Inggris yang telah di-generate oleh sistem.

17

Gambar 8 Solusi Jadwal untuk Mata Kuliah Bahasa Inggris yang telah Di-generate

Sesuai dengan algoritma steepest ascent hill climbing yang diterapkan

pada sistem, setelah solusi digenerate, langkah berikutnya adalah mengecek setiap

solusi jadwal yang diperoleh untuk menentukan apakah merupakan solusi yang

optimal atau tidak. Proses pengecekan solusi jadwal untuk mata kuliah Bahasa

Inggris seperti yang terlihat pada Gambar 9.

Gambar 9 Proses Pengecekan Solusi Jadwal Mata Kuliah Bahasa Inggris

Solusi jadwal yang diperoleh untuk mata kuliah Bahasa Inggris adalah

dosen FBS, jam mengajar Senin 14-16, ruang Stiba H3. Pertama-tama akan

diperiksa beban mengajar dosen bersangkutan dan diperoleh hasil beban mengajar

dosen FBS mencukupi, sehingga nilai H berubah dari 0 menjadi 1. Langkah

berikutnya akan diperiksa apakah terjadi tabrakan pada jadwal mengajar Dosen

FBS. Diperoleh hasil tidak terjadi tabrakan pada jam mengajar Dosen FBS

sehingga nilai H berubah dari 1 menjadi 2. Terakhir akan diperiksa apakah terjadi

tabrakan pada jadwal pemakaian ruang Stiba H3. Diperoleh hasil tidak terjadi

18

tabrakan pada jadwal pemakaian ruang sehingga nilai H berubah dari 2 menjadi 3

dan solusi penjadwalan merupakan solusi yang optimal.

Langkah berikutnya dilakukan pengecekan pada solusi jadwal mata kuliah

Bahasa Inggris yang lain yaitu pada solusi jadwal dosen FBS, dengan waktu

mengajar Senin 14-16 pada ruang Stiba H4. Setelah dilakukan pengecekan

ternyata terjadi tabrakan pada jam mengajar Dosen FBS, meskipun beban

mengajar dosen masih mencukupi dan jadwal pemakaian ruang tidak bertabrakan.

Nilai H yang diperoleh adalah 2 dan solusi yang diperoleh bukan merupakan

solusi yang optimal. Solusi jadwal yang lain yaitu dosen FBS dengan waktu

mengajar Jumat, 11-13 pada ruang Stiba H3, setelah dilakukan pengecekan selain

beban mengajar dosen mencukupi, ternyata tidak terjadi tabrakan pada jam

mengajar dosen dan tidak terjadi tabrakan pada jadwal pemakaian ruang sehingga

nilai H adalah 3 dan merupakan solusi jadwal yang optimal. Proses akan

berlangsung terus hingga diperoleh solusi jadwal sesuai dengan jumlah kelas pada

setiap mata kuliah.

Tabel 2 merupakan hasil jadwal mata kuliah Fakultas Psikologi UKSW

dengan menggunakan aplikasi penjadwalan mata kuliah. Pada Tabel 2 terlihat

bahwa pada jadwal yang diperoleh, algoritma steepest ascent hill climbing yang

diterapkan dapat memperoleh solusi jadwal yang optimal di mana aturan-aturan

dalam membuat jadwal mata kuliah Fakultas Psikologi UKSW telah terpenuhi.

Pada Jadwal yang dihasilkan, tidak ditemukan tabrakan jam mengajar pada dosen,

tidak ditemukan tabrakan pemakaian ruang perkuliahan, serta tidak ada dosen

yang mengajar lebih dari 9 SKS. Selain itu Hasil penjadwalan mata kuliah dapat

disimpan dalam format Microsoft Excel untuk pemrosesan lebih lanjut.

Tabel 2 Jadwal Mata Kuliah Dengan Aplikasi Penjadwalan Mata Kuliah N

O

Kode

Mata

Kuliah

MK S

K

S

Kode

Dosen

Nama Kode

Ruang

Kapa

sitas

Hari Jam

Mulai

Jam

Selesai

Angkatan

Angkatan 2011

1 PI 108 A Bahasa Inggris II A 2 0 FBS Stiba

H3

50 Senin 14 16 2011

2 PI 108 B Bahasa Inggris II B 2 0 FBS Stiba

H3

50 Jumat 11 13 2011

3 PI 108 C Bahasa Inggris II C 2 0 FBS Stiba

H3

50 Jumat 9 11 2011

4 PI 109 A Psikologi Umum II A 3 80513 Krismi Diah Ambarwati, S.Psi. E 134 70 Kamis 13 16 2011

5 PI 109 B Psikologi Umum II B 3 80513 Krismi Diah Ambarwati, S.Psi. E 134 70 Senin 10 13 2011

6 PI 111 A Statistika (Statistik I)

A

3 80004 Prof. Dr. Sutriyono, M.Sc. ABX

104

75 Senin 7 10 2011

7 PI 111 B Statistika (Statistik I)

B

3 80004 Prof. Dr. Sutriyono, M.Sc. ABX

104

75 Rabu 12 15 2011

8 PI 112 A Psikologi

Perkembangan II A

3 80002 Dr. Christina Hari

Soetjiningsih, M.S.

E 134 75 Selasa 9 12 2011

9 PI 112 B Psikologi

Perkembangan II B

3 80504 Ratriana Yuliastuti Endang

Kusumiati, Psi., M.Si.

E 134 75 Rabu 11 14 2011

10 PI 113 A Psikologi Sosial I A 3 80514 Jusuf Tjahjo Purnomo, Psi.,

M.Si.

ABX

104

75 Rabu 9 12 2011

11 PI 113 B Psikologi Sosial I B 3 80514 Jusuf Tjahjo Purnomo, Psi.,

M.Si.

E 134 75 Kamis 10 13 2011

12 PI 114 A Assesmen Psikologi

A

3 80522 Margaretha Erna Setyaningrum,

Psi.

E 134 75 Selasa 13 16 2011

13 PI 114 B Assesmen Psikologi

B

3 80522 Margaretha Erna Setyaningrum,

Psi.

E 134 75 Kamis 7 10 2011

14 PI 208 A Psikologi Industri

dan Organisasi A

2 80520 Novita Utami, S.Psi., M.Si. E 134 80 Selasa 7 9 2011

15 PI 208 B Psikologi Industri

dan Organisasi B

2 80520 Novita Utami, S.Psi., M.Si. ABX

104

80 Jumat 11 13 2011

16 PI 209 A Kesehatan Mental A 2 80504 Ratriana Yuliastuti Endang


GX 204 80 Kamis 7 9 2011

19

17 PI 209 B Kesehatan Mental B 2 80516 Rr. Indrastuti SS, Psi. ABX

104

80 Selasa 10 12 2011

Angkatan 2010

18 PI 210 A Psikologi Konseling

A

2 13809 Drs.Aloysius Lukas Soenarjo

Soesilo,MA.

GX 204 40 Selasa 11 13 2010

19 PI 210 B Psikologi Konseling

B

2 80508 Sri Aryanti Kristianingsih, Psi,

M.Si.

ABX

104

40 Senin 11 13 2010

20 PI 206 A Psikologi Pendidikan

A

2 80503 Berta Esti Ari Prasetyo, S.Psi.,

MA

GX 204 80 Selasa 7 9 2010

21 PI 206 B Psikologi Pendidikan

B


MA

GX 204 80 Jumat 10 12 2010

22 PI 212 A Metodologi

Penelitian II A

3 80004 Prof. Dr. Sutriyono, M.Sc. GXY

101

50 Jumat 12 15 2010

23 PI 214 A Psikologi Faal II A 2 0 Dr. Epsilon Dewanto, MM GX 204 80 Rabu 14 16 2010

24 PI 214 B Psikologi Faal II B 2 0 Dr. Epsilon Dewanto, MM GX 204 80 Kamis 14 16 2010

25 PI 215 A Tes Bakat dan Minat

A

2 80519 Heru Astikasari S.M., S.Psi. ABX

104

75 Jumat 7 9 2010

26 PI 215 B Tes Bakat dan Minat

B

2 80504 Ratriana Yuliastuti Endang


ABX

104

75 Kamis 13 15 2010


Kepribadian II A


MA

ABX

104

80 Kamis 10 13 2010


Kepribadian II B

3 80522 Rr. Indrastuti SS, Psi. GX 204 80 Selasa 13 16 2010

29 PI 218 A Psikologi Kognitif A 2 80508 Sri Aryanti Kristianingsih, Psi,

M.Si.

GX 204 75 Kamis 10 12 2010

30 PI 218 B Psikologi Kognitif B 2 80524 Maria A. Tobing, S.Psi. GX 204 75 Senin 11 13 2010


Eksperimen A

2 80510 Rudangta Arianti Sembiring,

Psi., M.Si.

E 134 75 Rabu 9 11 2010


Eksperimen B

2 80510 Rudangta Arianti Sembiring,

Psi., M.Si.

GX 204 75 Rabu 12 14 2010


Manajemen A

2 80514 Jusuf Tjahjo Purnomo, Psi.,

M.Si.

E 134 80 Rabu 7 9 2010

34 PI 301 A Psikologi Klinis A 2 80502 Wahyuni Kristinawati, Psi.,

M.si.

GX 204 75 Selasa 9 11 2010

35 PI 301 B Psikologi Klinis B 2 80513 Krismi Diah Ambarwati, S.Psi. ABX

104

75 Selasa 12 14 2010

Angkatan 2009 dan Sebelumnya

36 PI 311 A Interviu A 3 80518 Enjang Wahyuningrum, Psi. ABX

104

30 Selasa 7 10 2009 dan

sebelumnya

37 PI 311 B Interviu B 3 0 Wiwiet Prasetyanti, Psi. GXY

102

30 Kamis 10 13 2009 dan

sebelumnya

38 PI 311 C Interviu C 3 80518 Enjang Wahyuningrum, Psi. GXY

101

30 Jumat 7 10 2009 dan

sebelumnya

39 PI 312 A Tes Roschach A 2 80522 Margaretha Erna Setyaningrum,

Psi.

E 134 70 Jumat 9 11 2009 dan

sebelumnya

40 PI 313 A Konseling dan

psikoterapi A

3 80508 Sri Aryanti Kristianingsih, Psi,

M.Si.

ABX

104

25 Kamis 7 10 2009 dan

sebelumnya

41 PI 313 B Konseling dan

psikoterapi B

3 0 Maria Herlina I, M.Si., Psi, E 134 25 Senin 13 16 2009 dan

sebelumnya

42 PI 411 Skripsi 6 - - - 0 - 0 0 2009 dan

sebelumnya

43 PI 414 Skripsi Lanjut 4 - - - 0 - 0 0 2009 dan

sebelumnya

Mata Kuliah Pilihan

44 PI 503 A Hukum Perburuhan

A

2 0 Jusuf W.H., SH GXY

102

50 Rabu 7 9 2009 dan

sebelumnya

45 PI 507 A Psikologi Lintas

Budaya A

2 0 Mianto N. Agung, S.Pd., S.Si.,

M.Th

ABX

104

50 Senin 14 16 2009 dan

sebelumnya

46 PI 511 A Ergonomik A 2 80001 Dr. Sutarto Wijono, MA GXY

101

50 Senin 13 15 2009 dan

sebelumnya

47 PI 515 A Kapita Selekta PIO A 2 80520 Novita Utami, S.Psi., M.Si. GXY

102

50 Jumat 7 9 2009 dan

sebelumnya

48 PI 518 A Psi. Pendidikan

Khusus A

2 80516 Rr. Indrastuti SS, Psi. GXY

102

50 Jumat 9 11 2009 dan

sebelumnya

49 PI 520 A Psikologi Kesehatan

A

2 13809 Drs.Aloysius Lukas Soenarjo

Soesilo,MA.

GXY

102

25 Kamis 14 16 2009 dan

sebelumnya

50 PI 523 A Psikogerontologi A 2 80002 Dr. Christina Hari

Soetjiningsih, M.S.

GXY

101

50 Senin 9 11 2009 dan

sebelumnya

51 PI 528 A Psikologi Public

Relation A

2 0 Rini Darmastuti, S.Sos., M.Si. E 134 50 Senin 7 9 2009 dan

sebelumnya

52 PI 534 A Psi. Pendidikan Anak

berbakat A

2 80518 Enjang Wahyuningrum, Psi. E 134 50 Jumat 14 16 2009 dan

sebelumnya

20

5. Simpulan

Berdasarkan hasil pembuatan, pembahasan, dan pengujian aplikasi

penjadwalan mata kuliah dapat disimpulkan bahwa penerapan algoritma steepest

ascent hill climbing dalam sistem dapat menghasilkan output berupa jadwal mata

kuliah yang optimal yaitu pada jadwal yang dihasilkan, tidak ditemukan tabrakan

jam mengajar pada dosen, tidak ditemukan tabrakan pemakaian ruang

perkuliahan, serta tidak ada dosen yang mengajar lebih dari beban maksimal

mengajar. Aplikasi yang dibangun dapat membantu Fakultas Psikologi UKSW

dalam menyusun jadwal mata kuliah sesuai dengan ketentuan yang berlaku.

Algoritma steepest ascent hill climbing memiliki keunggulan di mana semua

solusi jadwal yang mungkin akan dibangkitkan kemudian akan diperiksa satu

persatu, sehingga proses cepat karena akan diperoleh solusi terbaik dan mendekati

hasil optimasi yang diharapkan. Saran dan pengembangan aplikasi ini adalah pada

proses pengecekan solusi jadwal ditambahkan fungsi agar tidak dilakukan proses

pengecekan kembali pada solusi jadwal yang sama dan untuk menambahkan

constraint pada proses pengecekan solusi, di luar contsraint yang sudah ada. Pada

sistem dapat pula ditambahkan fungsi untuk laporan beban akademik dosen setiap

semester.

6. Daftar Pustaka

[1] Nugraha, Ivan, 2008, Aplikasi Algoritma Genetik untuk Optimasi

Penjadwalan Kegiatan Belajar Mengajar. Makalah IF2251 Strategi

Algoritmik Tahun 2008.,

http://sutanto.staff.uns.ac.id/files/2008/09/makalahif2251-2008-023.pdf

(diakses tanggal 10 Februari 2012)

[2] Puspitasari, Bunga, 2008, Penggunaan Tabu Search Dalam Penjadwalan

Kuliah dan Ujian Perguruan Tinggi (Studi Kasus : Sekolah Tinggi

Manajemen Bandung), Yogyakarta : Fakultas Teknik Industri UII.

[3] Thiang, Handry Khoswanto, Felix Pasila, Ferdi Ninaber, dkk., 2009,

Implementasi Metode Steepest Ascent Hill Climbing pada Mikrokontroler

MCS51 untuk Robot Mobil Pencari Rute Terpendek, Surabaya : Jurusan

Teknik Elektro Universitas Kristen Petra.

[4] Christiana, D. I., G. Virginia, and J. Purwadi, 2008, Algoritma Steepest-

Ascent Hill Climbing untuk Menyelesaikan Masalah Penugasan, Jurnal

Teknologi Komputer dan Informatika. Yogyakarta, Indonesia, April 2008,

vol.4 no.1, ISSN 1693-7279, pp. 47-53.

[5] Rich, Elaine, 1991, Artificial Intelligence. New York: McGraw-Hill.

[6] Pressman, Roger S., 2001, Software Engineering a Practitioner’s

Approach, New York : McGraw-Hill Higher Education.

http://sutanto.staff.uns.ac.id/files/2008/09/makalahif2251-2008-023.pdf

perancangan dan implementasi finite...

Documents