Perancangan dan Implementasi Penjadwalan Mata Kuliah Menggunakan Algoritma Steepest Ascent Hill Climbing (Studi Kasus : Fakultas Psikologi UKSW)
Artikel Ilmiah
Peneliti: Klaudius Nikotino Putranto (672008192) M. A. Ineke Pakereng, M.Kom. Ramos Somya, S.Kom., M.Cs.
Program Studi Teknik Informatika Fakultas Teknologi Informasi Universitas Kristen SatyaWacana Salatiga Mei 2012
1
2
3
Perancangan dan Implementasi Penjadwalan Mata Kuliah Menggunakan Algoritma Steepest Ascent Hill Climbing (Studi Kasus : Fakultas Psikologi UKSW) 1)
Klaudius Nikotino P., 2) M. A. Ineke Pakereng, 3) Ramos Somya Fakultas Teknologi Informasi Universitas Kristen Satya Wacana Jl. Diponegoro 52-60, Salatiga 50771, Indonesia Email: 1)
[email protected], 2)
[email protected] 3)
[email protected] Abstract
Schedule of courses has been one of the most important part in a university’s teaching and learning activity. The large number of courses and lecturers that are involved, make some clashes on course’s schedule or class room’s schedule could happens frequently, so it requires an application to simplify the process of developing the course schedule. Steepest ascent hill climbing algorithm is an algorithm that generates all possible solutions, and then checks every solution to obtain optimum solution. The result of this research is this course scheduling system can facilitate courses schedulling, in addition steepest ascent hill climbing algorithm is able to obtain optimum scheduling courses solutions. Keywords : Course Schedulling, Steepest Ascent Hill Climbing Abstrak Jadwal mata kuliah telah menjadi salah satu bagian terpenting dalam proses belajar mengajar sebuah universitas. Banyaknya jumlah mata kuliah dan dosen yang terlibat, mengakibatkan sering terjadinya bentrokan jadwal mata kuliah atau pun dalam pemakaian ruang perkuliahan, sehingga diperlukan sebuah aplikasi guna mempermudah proses penyusunan jadwal mata kuliah tersebut. Algoritma steepest ascent hill climbing adalah algoritma yang mengumpulkan seluruh solusi yang mungkin, dan mengecek setiap solusi untuk memperoleh solusi yang optimal. Hasil dari penelitian ini adalah aplikasi yang dibangun dapat digunakan untuk memudahkan penjadwalan mata kuliah selain itu algoritma steepest ascent hill climbing mampu memperoleh solusi penjadwalan mata kuliah yang optimal. Kata Kunci : Penjadwalan Mata Kuliah, Steepest Ascent Hill Climbing. 1)
Mahasiswa Fakultas Teknologi Informasi Jurusan Teknik Informatika, Universitas Kristen Satya Wacana Salatiga. 2) Staff Pengajar Fakultas Teknologi Informasi, Universitas Kristen Satya Wacana Salatiga. 3) Staff Pengajar Fakultas Teknologi Informasi, Universitas Kristen Satya Wacana Salatiga.
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 : n! 2!(n-2)! 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
Mata Kuliah
Tenaga Pengajar Ruang Perkuliahan
Jumlah Mahasiswa
Keterangan 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 Terdapat 18 dosen tetap, dengan beberapa tambahan dosen luar GXY 102, E 134, ABX 104, GXY 101, GX 204 Stiba H2, Stiba H3, Stiba H4 (khusus Mata Kuliah Bhs. Inggris) 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
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) Pertamatama 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 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.jamselesaie.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;}
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.
14
Kode Program 3 Script Pengecekan Solusi Algoritma Steepest Ascent Hill Climbing pada Sistem 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) {
== ==
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 1720 adalah perintah untuk mengambil data beban mengajar tiap dosen. Data beban berkaitan dengan beban maksimal mengajar tiap dosen sebanyak 9 SKS. Baris 2124 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
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 1. if($sksCurrent==3) { 2. $idDosenMengajarSUCC=$idDosenMengajarSUCC." ".$iddosenmengajar.” ".$iddosenmengajarexception1; $idPakaiRuangSUCC=$idPakaiRuangSUCC." ".$idpakairuang." ".$idpakairuangexception1; }
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.
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
50
Senin
14
16
2011
50
Jumat
11
13
2011
50
Jumat
9
11
2011
70
Kamis
13
16
2011
10
13
2011
Angkatan 2011 1
PI 108 A
Bahasa Inggris II A
2
0
FBS
2
PI 108 B
Bahasa Inggris II B
2
0
FBS
3
PI 108 C
Bahasa Inggris II C
2
0
FBS
4
PI 109 A
Psikologi Umum II A
3
80513
Krismi Diah Ambarwati, S.Psi.
Stiba H3 Stiba H3 Stiba H3 E 134
5
PI 109 B
Psikologi Umum II B
3
80513
Krismi Diah Ambarwati, S.Psi.
E 134
70
Senin
6
PI 111 A
80004
Prof. Dr. Sutriyono, M.Sc.
Senin
7
10
2011
3
80004
Prof. Dr. Sutriyono, M.Sc.
75
Rabu
12
15
2011
8
PI 112 A
3
80002
75
Selasa
9
12
2011
9
PI 112 B
3
80504
E 134
75
Rabu
11
14
2011
10
PI 113 A
3
80514
Rabu
9
12
2011
PI 113 B
Psikologi Sosial I B
3
80514
ABX 104 E 134
75
11
75
Kamis
10
13
2011
12
PI 114 A
3
80522
E 134
75
Selasa
13
16
2011
13
PI 114 B
3
80522
E 134
75
Kamis
7
10
2011
14
PI 208 A
2
80520
E 134
80
Selasa
7
9
2011
15
PI 208 B
2
80520
Novita Utami, S.Psi., M.Si.
Jumat
11
13
2011
PI 209 A
2
80504
Ratriana Yuliastuti Endang Kusumiati, Psi., M.Si.
ABX 104 GX 204
80
16
Assesmen Psikologi A Assesmen Psikologi B Psikologi Industri dan Organisasi A Psikologi Industri dan Organisasi B Kesehatan Mental A
Dr. Christina Hari Soetjiningsih, M.S. Ratriana Yuliastuti Endang Kusumiati, Psi., M.Si. Jusuf Tjahjo Purnomo, Psi., M.Si. Jusuf Tjahjo Purnomo, Psi., M.Si. Margaretha Erna Setyaningrum, Psi. Margaretha Erna Setyaningrum, Psi. Novita Utami, S.Psi., M.Si.
ABX 104 ABX 104 E 134
75
PI 111 B
Statistika (Statistik I) A Statistika (Statistik I) B Psikologi Perkembangan II A Psikologi Perkembangan II B Psikologi Sosial I A
3
7
80
Kamis
7
9
2011
19
17
PI 209 B
Kesehatan Mental B
2
80516
18
PI 210 A
2
13809
19
PI 210 B
2
80508
20
PI 206 A
2
80503
21
PI 206 B
2
80503
22
PI 212 A
3
80004
23
PI 214 A
Psikologi Konseling A Psikologi Konseling B Psikologi Pendidikan A Psikologi Pendidikan B Metodologi Penelitian II A Psikologi Faal II A
2
0
24
PI 214 B
Psikologi Faal II B
2
25
PI 215 A
26
PI 215 B
27
PI 217 A
28
PI 217 B
29
PI 218 A
Tes Bakat dan Minat A Tes Bakat dan Minat B Psikologi Kepribadian II A Psikologi Kepribadian II B Psikologi Kognitif A
30
PI 218 B
31
PI 219 A
32
PI 219 B
33
PI 221 A
34
Rr. Indrastuti SS, Psi.
ABX 104
80
Selasa
10
12
2011
GX 204
40
Selasa
11
13
2010
ABX 104 GX 204
40
Senin
11
13
2010
80
Selasa
7
9
2010
GX 204
80
Jumat
10
12
2010
GXY 101 GX 204
50
Jumat
12
15
2010
Dr. Epsilon Dewanto, MM
80
Rabu
14
16
2010
0
Dr. Epsilon Dewanto, MM
GX 204
80
Kamis
14
16
2010
2
80519
Heru Astikasari S.M., S.Psi.
75
Jumat
7
9
2010
2
80504
75
Kamis
13
15
2010
3
80503
80
Kamis
10
13
2010
3
80522
Ratriana Yuliastuti Endang Kusumiati, Psi., M.Si. Berta Esti Ari Prasetyo, S.Psi., MA Rr. Indrastuti SS, Psi.
ABX 104 ABX 104 ABX 104 GX 204
80
Selasa
13
16
2010
2
80508
GX 204
75
Kamis
10
12
2010
Psikologi Kognitif B
2
80524
Sri Aryanti Kristianingsih, Psi, M.Si. Maria A. Tobing, S.Psi.
GX 204
75
Senin
11
13
2010
2
80510
75
Rabu
9
11
2010
2
80510
GX 204
75
Rabu
12
14
2010
2
80514
E 134
80
Rabu
7
9
2010
2
80502
GX 204
75
Selasa
9
11
2010
35
PI 301 B
Psikologi Klinis B
2
80513
Rudangta Arianti Sembiring, Psi., M.Si. Rudangta Arianti Sembiring, Psi., M.Si. Jusuf Tjahjo Purnomo, Psi., M.Si. Wahyuni Kristinawati, Psi., M.si. Krismi Diah Ambarwati, S.Psi.
E 134
PI 301 A
Psikologi Eksperimen A Psikologi Eksperimen B Psikologi Manajemen A Psikologi Klinis A
75
Selasa
12
14
2010
36
PI 311 A
Interviu A
3
80518
30
Selasa
7
10
37
PI 311 B
Interviu B
3
0
30
Kamis
10
13
38
PI 311 C
Interviu C
3
80518
Enjang Wahyuningrum, Psi.
30
Jumat
7
10
39
PI 312 A
Tes Roschach A
2
80522
70
Jumat
9
11
40
PI 313 A
3
80508
Kamis
7
10
PI 313 B
3
0
ABX 104 E 134
25
41
25
Senin
13
16
42
PI 411
Konseling dan psikoterapi A Konseling dan psikoterapi B Skripsi
Margaretha Erna Setyaningrum, Psi. Sri Aryanti Kristianingsih, Psi, M.Si. Maria Herlina I, M.Si., Psi,
ABX 104 GXY 102 GXY 101 E 134
6
-
-
-
0
-
0
0
2009 dan sebelumnya 2009 dan sebelumnya 2009 dan sebelumnya 2009 dan sebelumnya 2009 dan sebelumnya 2009 dan sebelumnya 2009 dan sebelumnya
43
PI 414
Skripsi Lanjut
4
-
-
-
0
-
0
0
2009 dan sebelumnya
44
PI 503 A
2
0
Jusuf W.H., SH
Rabu
7
9
PI 507 A
2
0
50
Senin
14
16
46
PI 511 A
2
80001
Mianto N. Agung, S.Pd., S.Si., M.Th Dr. Sutarto Wijono, MA
50
Senin
13
15
47
PI 515 A
Kapita Selekta PIO A
2
80520
Novita Utami, S.Psi., M.Si.
50
Jumat
7
9
48
PI 518 A
2
80516
Rr. Indrastuti SS, Psi.
50
Jumat
9
11
49
PI 520 A
2
13809
Kamis
14
16
PI 523 A
2
80002
50
Senin
9
11
51
PI 528 A
2
0
50
Senin
7
9
52
PI 534 A
Psikologi Public Relation A Psi. Pendidikan Anak berbakat A
Drs.Aloysius Lukas Soenarjo Soesilo,MA. Dr. Christina Hari Soetjiningsih, M.S. Rini Darmastuti, S.Sos., M.Si.
25
50
Psi. Pendidikan Khusus A Psikologi Kesehatan A Psikogerontologi A
GXY 102 ABX 104 GXY 101 GXY 102 GXY 102 GXY 102 GXY 101 E 134
50
45
Hukum Perburuhan A Psikologi Lintas Budaya A Ergonomik A
2
80518
Enjang Wahyuningrum, Psi.
E 134
50
Jumat
14
16
2009 dan sebelumnya 2009 dan sebelumnya 2009 dan sebelumnya 2009 dan sebelumnya 2009 dan sebelumnya 2009 dan sebelumnya 2009 dan sebelumnya 2009 dan sebelumnya 2009 dan sebelumnya
Angkatan 2010 Drs.Aloysius Lukas Soenarjo Soesilo,MA. Sri Aryanti Kristianingsih, Psi, M.Si. Berta Esti Ari Prasetyo, S.Psi., MA Berta Esti Ari Prasetyo, S.Psi., MA Prof. Dr. Sutriyono, M.Sc.
ABX 104 Angkatan 2009 dan Sebelumnya Enjang Wahyuningrum, Psi. Wiwiet Prasetyanti, Psi.
Mata Kuliah Pilihan
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 SteepestAscent 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.
21
