PENGEMBANGAN SISTEM PENJADWALAN KULIAH MENGGUNAKAN ALGORITMA STEEPEST ASCENT HILL CLIMBING Shoffan Saifullah1, Arief Hermawan2
Abstract— University of Technology Yogyakarta is a private university in Yogyakarta, it has several purposes, one of them is utilizing the maximum potential of technology to improve the effectiveness and efficiency of learning and dissemination of science and technology. One of the factors that can improve academic services are scheduling courses. Scheduling proses isn’t easy because they have to consider the possibility in scheduling, include subjects, times, lecturers, and lecture halls. Now, subject scheduling is still using Ms. Excel, the process is to input lecturer’s name one by one, to teach to the prescribed schedule and also to check whether the data is conflicting or not, so it takes long time. Therefore, we need a system that is able to perform scheduling more quickly, effectively and optimally. Subject scheduling system can be done by using the optimization system. For the case of optimization can be done using the steepest ascent hill climbing algorithm. Steepest ascent hill climbing algorithm is a search algorithm (heuristic), it is able to solve the problems of optimization with estimates to be produced in accordance with the desired criteria or rules. Subject scheduling process produces a schedule that takes less time compared to a system that is currently running. Although it is able to minimize the level of clashing schedules, its application needs to be re-checked on the level of conflicting schedules. Index Terms— Scheduling Lecture, Steepest Ascent Hill Climbing Algorithms, and Schedules.
I. PENDAHULUAN Universitas Teknologi Yogyakarta (UTY) merupakan salah satu universitas swasta di Yogyakarta yang mempunyai beberapa tujuan, salah satunya adalah memanfaatkan sebesarbesarnya potensi teknologi untuk meningkatkan efektifitas dan efisiensi pembelajaran dan penyebarluasan ilmu pengetahuan dan teknologi. Dalam pelaksanaan tujuan tersebut, UTY memiliki keterbatasan pada proses pembelajaran yaitu penjadwalan kuliah yang dilakukan setiap awal semester. Penjadwalan kuliah yang selama ini berjalan masih menimbulkan bentrok, baik pada waktu, ruang maupun dosen mengajar. Untuk meningkatkan pelayanan akademik, penjadwalan kuliah merupakan suatu hal yang penting, karena berhubungan dengan proses pengaturan pembelajaran yaitu mata kuliah, waktu, dosen dan ruang. Proses penjadwal kuliah bukan merupakan suatu kegiatan yang mudah untuk dilakukan, karena dalam melakukan penjadwalan tidak hanya menyusun jadwal antara mata kuliah, waktu, dosen dan ruangan. Akan 1 Shoffan Saifullah, Magister Teknik Informatika, Universitas Ahmad Dahlan, Yogyakarta, Indonesia (phone: +6285725119117; e-mail:
[email protected]). 2 Arief Hermawan, Teknik Informatika, Universitas Teknologi Yogyakarta, Yogyakarta, Indonesia (e-mail:
[email protected]).
tetapi, banyak kemungkinan kombinasi yang perlu diperhatikan. Sehingga perlu dibangun sistem penjadwalan kuliah yang dapat membantu meningkatkan pelayanan akademik dan untuk mewujudkan tujuan dari Universitas Teknologi Yogyakarta. Saat ini sistem pelayanan akademik dalam pembuatan jadwal kuliah kurang efektif, karena memerlukan waktu yang lama, dan sering terjadi bentrok pada jadwal mahasiswa. Ketika jadwal yang diterima mahasiswa terjadi bentrok dengan jadwal yang lainnya, maka mahasiswa perlu waktu revisi dengan proses yang cukup lama yaitu 2 minggu, bahkan lebih. Oleh karena itu perlu dibangun sistem penjadwalan kuliah dengan menggunakan algoritma steepest ascent hill climbing yang lebih cepat, efektif dan optimal sehingga jadwal yang telah diproses tidak akan mengalami bentrok. Tujuan dari penelitian ini yaitu untuk mengembangkan sistem penjadwalan kuliah dengan harapan dapat meningkatkan proses belajar mengajar, sehingga tidak terganggu dengan adanya jadwal yang bentrok. Dan mengetahui bagaimana penggunaan dan penerapan algoritma steepest ascent hill climbing dalam proses penjadwalan yang akan dilakukan sehingga mampu menghasilkan proses yang cepat, efektif dan efisien sesuai dengan pengguna sistem. II. TINJAUAN PUSTAKA Sirken (2013) menjelaskan tentang bagaimana penyelesaian permasalahan pembuatan jadwal mata pelajaran di SMA Negeri 3 Temanggung dengan menggunakan metode algoritma genetika. Disamping itu, sistem yang dibuat dapat melakukan proses penjadwalan mata pelajaran secara otomatis sehingga penjadwalan dapat dilakukan secara cepat dan dapat mengoptimalkan pendistribusian waktu secara otomatis. Putranto (2012) menjelaskan tentang penerapan algoritma steepest ascent hill climbing dalam proses penjadwalan yang optimal sehingga tidak ditemukan bentrok pada jadwal perkuliahan. Dalam proses pengembangan yang mungkin untuk dilakukan, pihak peneliti memberikan masukan untuk menambahkan constraint dalam pembuatan jadwal, dan penambahan fungsi yang mampu menyelesaikan proses penjadwalan tanpa melakukan pengecekan ulang dari solusi jadwal yang telah diproses. Dan juga, untuk memberikan laporan dosen dalam mengajar untuk tiap semesternya. Kumala (2010) menjelaskan tentang bagaimana penerapan algoritma genetika dalam melakukan proses optimasi produksi, dan pada hasilnya didapat bahwa algoritma genetika merupakan metode yang baik dalam proses optimasi. Fahrurozi (2011) menjelaskan mengenai pembuatan sistem informasi penjadwalan mata kuliah dengan memberikan pembatasan waktu pengumpulan kesediaan dosen dalam memberikan pembelajaran dengan jumlah sks yang sesuai
57 – jsiskom JURNAL SISTEM KOMPUTER – Vol. 6, No 2, November 2016, ISSN : 2087-4685, e-ISSN: 2252-3456
dengan status kerjanya. Dengan adanya sistem informasi penjadwalan mata kuliah ini, UIN Syarif Hidayatullah Jakarta dapat mempercepat proses penjadwalan mata kuliah dan penggunaan laboratorium untuk prodi TI dan SI dengan Website. Berdasarkan penelitian-penelitian di atas, menjelaskan bagaimana untuk menyelesaikan penjadwalan, dan membangun sistem penjadwalan dengan berbagai metode. Perbedaan penelitian ini adalah menyelesaikan masalah penjadwalan kuliah teori dengan membatasi jumlah mata kuliah yang diajarkan dalam 1 hari untuk untuk tiap semesternya, dan penambahan constraint yang akan membuat jadwal yang telah dibuat tidak menghasilkan bentrok serta adanya permintaan dosen untuk waktu mengajar. Metode yang digunakan dalam proses penjadwalan adalah algoritma steepest ascent hill climbing. Pada metode ini akan ditambahkan fungsi yang akan mengecek solusi jadwal akhir tanpa melakukan pengecekan ulang atas solusi jadwal yang telah dilakukan. Dan dapat memberikan jadwal yang optimal beserta laporan untuk beban dosen mengajar. III. METODOLOGI Adapun langkah-langkah dalam pengembangan sistem meliputi perencanaan dan seleksi sistem, analisis sistem, desain sistem, dan implementasi. a. Perencanaan dan Seleksi Sistem Langkah awal dalam membangun sebuah sistem yaitu dengan melakukan identifikasi mengenai sistem-sistem yang ada di instansi. Setelah itu, sistem-sistem yang ada di instansi tersebut dikelompokkan sesuai dengan kriteria tertentu, baik berupa analisis nilai sistem, kesejajaran sistem, potensi keuntungan dari sistem tersebut, ketersediaan sumber daya yang dibutuhkan oleh sistem, ukuran dan durasi proyek yang memungkinkan untuk membuat sistem, serta tingkat resiko yang kemungkinan akan terjadi. Kemudian pada penelitian yang dilakukan di Universitas Teknologi Yogyakarta sistem yang dipilih adalah sistem penjadwalan kuliah. Sitem penjadwalan kuliah yang telah dilakukan di UTY masih sederhana yaitu masih menggunakan Ms.Excel.
Entity Relation Diagram (ERD), interface baik untuk input, proses maupun output, dan basis data. d. Implementasi Sistem Pada tahap ini sistem yang dibuat akan diuji cobakan dan diimplementasikan di Fakultas Sains dan Teknologi Universitas Teknologi Yogyakata pada bagian akademik. Tools yang akan digunakan pada sistem ini yaitu menggunakan bahasa pemrograman Borland Delphi 7, dengan menggunakan basis data MySql, dan diharapkan dapat membatu dalam melakukan proses penjadwalan mata kuliah mahasiswa secara efektif dan efisien. IV. HASIL DAN PEMBAHASAN Pada langkah-langkah pengembangan sistem setelah melakukan analisis adalah desain sistem. Desain sistem yang telah dilakukan yaitu menggunakan perancangan DAD, ERD dan Flowchart proses penjadwalan kuliah. adapun perancangannya diantaranya adalah sebagai berikut: DAD Level 0
Gambar 1. DAD Level 0 DAD Level 0 merupakan rancangan desain proses yang menunjukan gambaran secara umum mengenai keseluruhan proses. DAD Level 1
b. Analisis Sistem Metode ini digunakan untuk melakukan analisis mengenai kebutuhan user dalam sistem penjadwalan mata kuliah dengan melakukan wawancara langsung dengan dekan fakultas dan kepala bagian operasional. Disamping itu juga melakukan observasi langsung ke lapangan, dan membaca studi pustaka baik dari buku, e-book, jurnal, makalah, maupun internet yang terkait dengan penulisan proyek tugas akhir yang akan dilakukan. c. Desain Sistem Metode ini digunakan untuk merancang dan membangun sistem penjadwalan mata kuliah mahasiswa Universitas Teknologi Yogyakarta dengan algoritma steepest ascent hill climbing pada Fakultas Sains dan Teknologi dengan analisis kebutuhan yang diperlukan oleh sistem berdasar pada metode analisis sistem. Perancangan sistem akan dibuat menggunakan 58 – jsiskom JURNAL SISTEM KOMPUTER – Vol. 6, No 2, November 2016, ISSN : 2087-4685, e-ISSN: 2252-3456
DAD Level 2 Proses 2 merupakan perancangan proses yang menunjukan tentang penjadwalan yang dilakukan dengan memproses secara otomatis. Sehingga semua kebutuhan sistem sudah siap maka dengan melakukan proses penjadwalan algoritma steepest ascent hill climbing penjadwalan akan dilakukan secara otomatis. Algoritma Steepest Ascent Hill Climbing
Gambar 2. DAD Level 1 DAD Level 1 merupakan rancangan desain proses di level 1 yang bisa dilakukan oleh pengguna dalam menjalankan aplikasi. DAD Level 1 berisi tentang proses awal yang bisa dijalankan pengguna.
Suyanto (2007) menjelaskan algoritma SAHC sebagai berikut: 1. Evaluasi initial state. Jika state ini adalah goal state, maka kembalikan state ini sebagai solusi dan keluar dari fungsi. Jika state ini bukan goal state, lanjutkan proses dengan initial state sebagai current state (keadaan sekarang). 2. Ulangi sampai solusi ditemukan atau sampai tidak ada perubahan terhadap current state: a). Misalkan SUK adalah suatu state yang menjadi suksesor sari current state. b). Untuk setiap operator yang bisa dilakukan terhadap current state, kerjakan: (i) Aplikasikan operator tersebut dan bangkitkan new state. (ii) Evaluasi new state. Jika merupakan goal state, kembalikan state ini sebagai solusi dan keluar dari program. Jika bukan goal state, bandingkan new state dengan SUK. Jika new state lebih baik dari SUK, maka ganti SUK dengan new state. Jika tidak lebih baik, SUK tidak perlu diganti. 3. Jika SUK lebih baik dari current state, maka ganti current state dengan SUK. Flowchart Algoritma Steepest Ascent Hill Climbing pada proses Penjadwalan Kuliah
DAD Level 2 Proses 4
Gambar 3. DAD Level 2 Proses 4
59 – jsiskom JURNAL SISTEM KOMPUTER – Vol. 6, No 2, November 2016, ISSN : 2087-4685, e-ISSN: 2252-3456
menjadi successor dan akan berjalan diketemukan jadwal yang optimal. ERD (Entity Relationship Diagram)
terus
sampai
Gambar 5. ERD (Entity Relationship Diagram) Hasil Implementasi dari aplikasi penjadwalan kuliah dengan algoritma steepest ascent hill climbing adalah sebagai berikut ini: Form Login Sistem
Gambar 6. Form Login Untuk setiap kali aplikasi di running, maka akan tampil form login yang akan menuju ke form utama. Form Proses Penjadwalan Kuliah dengan Menggunakan Steepest Ascent Hill Climbing Gambar 4. Flowchart Steepest Ascent Hill Climbing Algoritma steepest ascent hill climbing dalam menyelesaikan masalah penjadwalan di FST UTY. Algoritma ini merupakan algoritma untuk menyelesaikan masalah optimasi. Langkah-langkah dalam proses penjadwalan ini berdasarkan flowchart di atas yaitu setelah mulai proses algoritma akan melakukan penjadwalan secara acak. Kemudian menentukan jumlah data jadwal yang akan di jadwalkan. Berdasarkan pada jumlah data dan perulangan maka akan digunakan sebagai fungsi perulangan. Pada saat penjadwalan dilakukan langkah pertama adalah menginisialisasi untuk nilai f = 0, dan menentukan successor,yang akan digunakan untuk membandingkan dengan jadwal yang telah dibuat secara acak. Ketika successor itu optimal, tidak terjadi bentrok (sesuai dengan parameter yang dikehendaki) maka successor akan menjadi solusi optimal, akan tetapi jika data jadwal itu lebih baik dibandingkan dengan successor maka data tersebut akan
Gambar 7. Form Proses Penjadwalan Kuliah dengan Menggunakan Steepest Ascent Hill Climbing Pada form Penjadwalan SAHC ini untuk bisa menjadwalkan secara otomatis, maka parameter-parameter yang diatasnya perlu diisikan dan kebutuhan akan jadwal seperti hari, ruang, jam, dosen dengan beban mengajar sudah terpenuhi (terisi). Untuk proses dapat dilakukan dengan sekali klik pada proses Penjadwalan SAHC. Setelah itu akan
60 – jsiskom JURNAL SISTEM KOMPUTER – Vol. 6, No 2, November 2016, ISSN : 2087-4685, e-ISSN: 2252-3456
menampilkan form hasil jadwal yang telah dijadwalkan oleh sistem.
Form Hasil Penjadwalan Proses Penjadwalan Steepest Ascent Hill Climbing
Potongan Listing Proses Penjadwalan SAHC: with dm.qr_jadwal1 do begin active:=false;close; sql.clear; sql.Text:='Select * from jadwal where kd_ruang='+QuotedStr(kd_ruang)+' and kd_hari='+QuotedStr(kd_hr)+''; execsql; open; end; if dm.qr_jadwal1.Eof then begin f:=f+1; with dm.qr_jadwal2 do begin active:=false; close; sql.clear; sql.Text:='select mk_detail.kd_dsn, kd_hari ,waktu_ajar from jadwal,mk_detail where mk_detail.kd_detail=jadwal.kd_detail and kd_dsn='+quotedstr(kd_dsn)+' and kd_hari='+quotedstr(kd_hr)+' and waktu_ajar='+quotedstr(jam)+''; execSQL; open; end; if dm.qr_jadwal2.Eof then begin f:=f+1; with dm.qr_jadwal3 do begin Active:=false; close; sql.Clear; sql.Text:='SELECT matkul.kd_prodi,prodi.nm_prodi, mk_detail.kd_kelas,kelas.nm_kelas,smt, jadwal.kd_hari,hari.nm_hari'+ 'FROM jadwal,matkul,mk_detail,prodi,kelas,hari '+'WHERE jadwal.kd_detail=mk_detail.kd_detail AND mk_detail.kd_mk = matkul.kd_mk AND matkul.kd_prodi=prodi.kd_prodi AND kelas.kd_kelas=mk_detail.kd_kelas '+ 'AND jadwal.kd_hari=hari.kd_hari '+ 'and nm_prodi='+QuotedStr(nm_jur)+' and nm_kelas='+QuotedStr(kelas)+'and smt='+quotedstr(smt)+'and nm_hari = '+QuotedStr(hari); ExecSQL; open; end; if dm.qr_jadwal3.RecordCount<=StrToInt(sedit2.Text) then begin f:=f+1; goto lanjut; end else f:=0; end else f:=0;end
Potongan Listing untuk aturan yang dapat memberikan nilai heuristik dari yang awalnya bernilai 0 (f=0) sampai nilai heuristiknya menjadi 3 (f=3).
Gambar 8. Form Hasil Penjadwalan SAHC Pada form hasil penjadwalan SAHC ini memberikan informasi mengenai random jadwal awal secara acak untuk semua kemungkinan, hasil penjadwalan SAHC setelah proses, semua jadwal yang telah tersimpan sesuai dengan parameter yang diisikan, dan data yang belum terjadwalkan oleh sistem. V. KESIMPULAN Berdasarkan penelitian yang telah dilakukan penulis dapat disimpulkan sebagai berikut: 1. Sistem ini dapat membantu mempercepat dalam proses penjadwalan kuliah Fakultas Sains dan Teknologi Universitas Teknologi Yogyakarta jika dibandingkan dengan proses yang dilakukan saat ini secara manual satu persatu dalam menjadwalkan kuliah. 2. Dengan menggunakan sistem ini diharapkan dapat meminimalkan tingkat bentrokan yang terjadi saat proses penjadwalan dilakukan. 3. Sistem penjadwalan dengan menggunakan algoritma steepest ascent hill climbing mampu untuk membantu dalam proses penjadwalan di Fakultas Sains dan Teknologi Yogyakarta. 4. Proses penjadwalan memerlukan waktu yang cukup lama untuk data yang banyak. Adapun saran dalam pengembangan penelitian adalah sebagai berikut : 1. Untuk pengembangan sistem penjadwalan selanjutnya diharapkan mampu mengembangkan dengan menggunakan kombinasi berbagai metode yang mampu memberikan proses penjadwalan yang lebih cepat. 2. Memanfaatkan sistem yang telah ada dan kemudian merelasikan dengan sistem penjadwalan (misalkan data dosen dan inventori ruang yang sudah terkomputerisasi dan data tersimpan di database yang ada), sehingga tidak melakukan input manual. DAFTAR PUSTAKA Abraham Silberschatz, Henry F. Korth, S. Sudarshan. 2011. “Database System Concepts. Ed. 6. ISBN 978-0-07-352332-3 (alk. paper)
61 – jsiskom JURNAL SISTEM KOMPUTER – Vol. 6, No 2, November 2016, ISSN : 2087-4685, e-ISSN: 2252-3456
Fahrurozi. 2011. “Sistem Informasi Penjadwalan Kuliah Pada International Programs Fakultas Sains dan Teknologi UIN Syarif Hidayatullah Jakarta Berbasis Website”. UIN Syarif Hidayatullah Jakarta: Jakarta. http://www.ilmukomputer.org/wp-content/ uploads/2009/10/anharkubobolserver. pdf. tanggal akses 22 Oktober 2014. Jam 08.13 Jogiyanto HM. 2009. “Sistem Teknologi Informasi”. Yogyakarta: Andi. Kenneth C. Laudon, Jane P.Laudon,. 2008. Sistem Informasi Manajemen. Ed.10. Salemba Empat : Jakarta. Kumala. 2010. “Implementasi Algoritma Genetika untuk Optimasi Produksi”. Universitas Teknologi Yogyakarta. Pressman, R. S. 2002. “Rekayasa Perangkat Lunak Buku I. Andi: Yogyakarta. Putranto, K. N.2012.Perancangan dan Implementasi Penjadwalan Mata Kuliah Menggunakan Algoritma Steepest Ascent Hill Climbing (Studi Kasus : Fakultas Psikologi UKSW). Universitas Kristen Satya Wacana Salatiga. Sidik, Betha,. 2003. MySQL Untuk Pengguna, Administrator, dan Pengembang Aplikasi Web. Informatika Bandung: Bandung.
Sirken, A. S. 2013. “Sistem Penjadwalan Mata Pelajaran Menggunakan Algoritma Genetika (Studi Kasus : SMA NEGERI 3 TEMANGGUNG)”. Universitas Teknologi Yogyakarta: Yogyakarta. Suyanto. 2007. “Artificial Intelligence Searching, Reasoning, Planning, and Learning”. Bandung: Informatika. Sridadi, B. 2009. “Pemodelan dan Simulasi Sistem Teori, Aplikasi, dan Contoh Program dalam Bahasa C”. Bandung: Informatika. Valacich, George, Hoffer. 2012. “Esentials of Systems Analisis & Desain”. Ed. 5 (E-Books) Yuhilda. 2007. “Sistem Pendukung Pengambilan Keputusan Penjadwalan Kuliah Berdasarkan Preferensi Kesediaan Waktu Dosen Untuk Mengajar (Studi Kasus pada STIE SBI Yogyakarta)”. Tesis Sekolah Pasca Sarjana Ilmu Komputer. UGM: Yogyakarta.
62 – jsiskom JURNAL SISTEM KOMPUTER – Vol. 6, No 2, November 2016, ISSN : 2087-4685, e-ISSN: 2252-3456
