Syntax
Literate: Jurnal Ilmiah Indonesia p�ISSN: 2541-0849 e-ISSN: 2548-1398
Vol. 7, No. 12, Desember 2022
OPTIMALISASI
ALGORITMA GREEDY DALAM PENYUSUNAN JADWAL PELAJARAN PADA SMK NURUL ISLAM CIANJUR
Ela Siti Laela, Windu Gata, Jajang Jaya
Purnama
Magister Ilmu Komputer, Teknik Informatika, STMIK Nusa Mandiri
Email [email protected], [email protected], [email protected]@e-mail.com
Abstrak
Algoritma
greedy merupakan algoritma yang bersifat heuristik dan urutan logisnya disusun
berdasarkan langkah-langkah penyelesaian masalah yang disusun secara
sistematis. Dalam penelitian ini algoritma greedy digunakan
untuk mengoptimalisasi penggunaan ruangan kelas yang ada di SMK Nurul Islam Cianjur.
Tujuan dilakukannya penelitian ini adalah untuk mengetahui apakah algoritma
greedy dapat mengoptimalisasi pembuatan Sistem Penjadwalan Mata Pelajaran di
SMK Nurul Islam Cianjur dalam mengetahui jumlah ruangan kelas yang kosong setelah digunakannya algoritma, dan mengetahui
apakah metode menggunakan algoritma greedy lebih baik dari pada sistem manual. Data yang digunakan adalah jadwal mata kuliah tahun ajaran
2018/2019 ganjil genap, dan 2017/2018 ganjil. Hasil
akhir pembuatan sistem berupa suatu jadwal pelajaran yang dapat dilihat ruangan
kosong yang ada dan durasi kosongnya ruangan tersebut. Pengujian
dilakukan dengan cara membandingkan banyaknya ruangan
kosong hasil dari sistem yang menggunakan algoritma greedy dengan sistem
manual. Berdasarkan data jadwal pelajaran yang diinput ke
dalam sistem ditunjukkan bahwa algoritma greedy memiliki ruangan kosong lebih
banyak, hal itu menunjukkan bahwa algoritma greedy mampu mengoptimalisasi
ruangan pada penjadwalanpelajaran di SMK Nurul Islam Cianjur secara baik.
Kata Kunci: Algoritma Greedy, Penjadwalan, Optimalisasi Ruangan.
Abstract
The
greedy algorithm is an algorithm that is heuristic and its logical sequence is
arranged based on systematic problem solving steps. In this study, the Greedy
algorithm is used to optimize the use of classrooms at SMK Nurul Islam Cianjur.
The purpose of this research is to find out whether the Greedy algorithm can
optimize the creation of the Subject Scheduling System at SMK Nurul Islam
Cianjur in knowing the number of empty classrooms after using the algorithm,
and to find out whether the method using the Greedy algorithm is better than
the manual system. The data used is the course schedule for the academic year
2018/2019 odd even, and 2017/2018 odd. The final result of making the system is
in the form of a lesson schedule that can be seen by the available empty space
and the duration of the empty room. Testing is done by comparing the number of
empty rooms resulting from a system that uses the Greedy algorithm with a
manual system. Based on the lesson schedule data that is inputted into the
system, it is shown that the greedy algorithm has more free space, it shows
that the greedy algorithm is able to optimize the space in lesson scheduling at
SMK Nurul Islam Cianjur well.
Keywords: Greedy
Algorithm, Scheduling, Room Optimization.
Pendahuluan
Menciptakan suatu jadwal pelajaran
yang optimal cukup sulit dikarenakan banyak variabel yang saling terkait
sehingga membutuhkan suatu penanganan yang signifikan (Sitinjak,
2018). Penjadwalan
pelajaran merupakan pengaturan penempatan waktu, kelas (kelas siswa), guru,
ruangan kelas. Sistem Penjadwalan dikatakan baik apabila dapat
memberikan solusi terhadap faktor-faktor tertentu, seperti guru tidak boleh
mengajar banyak kelas dalam satu waktu, ruangan tidak boleh diisi oleh banyak
mata pelajaran dalam satu waktu, dan kelas tidak boleh mengikuti banyak mata
pelajaran dalam satu waktu (Mustari,
2022).
Dalam penjadwalan pelajaran di SMK Nurul Islam Cianjur yang ada saat
ini banyak guru yang tidak mendapatkan ruangan untuk jam pengganti. Penyusunan jadwal bisa memakan waktu berminggu-minggu dengan
minimal pengerjaannya sampai dengan 4 minggu. Dibutuhkan
ketelitian yang tinggi karena harus memperhatikan banyak variabel agar jadwal
tidak bentrok. Siswa tidak memiliki ruangan kosong untuk belajar di luar
jam pelajaran
Cara manual yang dilakukan saat ini
juga memungkinkan terjadinya kesalahan dengan intensitas yang cukup banyak. Ketersediaan
ruangan yang sedikit, penjadwalan yang berubah- ubah di awal semester merupakan
isu-isu yang perlu diperhatikan dalam penjadwalan pelajaran di SMK Nurul Islam
Cianjur. Dalam penelitian ini akan diuji
seberapa optimal pemanfaatan ruangan menggunakan algoritma greedy dalam
penerapannya ke jadwal pelajaran di SMK Nurul Islam Cianjur. Sehingga
diharapkan dapat menjadi referensi dalam meminimalisir isu-isu penjadwalan di
SMK Nurul Islam Cianjur
A. Algoritma Greedy
�Algoritma adalah urutan logis
langkah- langkah penyelesaian masalah yang disusun secara sistematis� (Hasibuan,
2022). Awalnya kata
algoritma merupakan istilah yang merujuk kepada aturan-aturan aritmetis untuk
menyelesaikan persoalan dengan menggunakan bilangan numerik Arab, namun pada
abad ke-18 istilah ini telah berkembang sehingga makna algoritma menjadi lebih
luas lagi menjadi suatu urutan langkah atau prosedur yang jelas dan diperlukan
untuk menyelesaikan suatu permasalahan. Kata algoritma berasal dari
latinisasi nama seorang ahli matematika dari Uzbekistan Al Khawārizmi
(hidup sekitar abad ke-9), sebagaimana tercantum pada terjemahan karyanya lam
bahasa latin dari abad ke-12 "Algorithmi de numero Indorum" (Sulasmoro,
2022). Algoritma Greedy merupakan
metode yang paling populer dalam memecahkan persoalan optimasi. Hanya ada dua macam persoalan optimasi, yaitu maksimasi dan
minimasi. Pada penelitian ini, algoritma greedy yang
digunakan menerapkan pendekatan maksimasi. Algoritma
Greedy adalah algoritma yang memecahkan masalah langkah per langkah. Pada setiap langkah terdapat banyak pilihan yang perlu
dieksplorasi. Persoalan optimalisasi dalam konteks algoritma greedy
disusun oleh elemen-elemen sebagai berikut (Subakti
& Gata, 2021):
1. Himpunan
Kandidat, C.
Himpunan ini berisi elemen-elemen
pembentuk solusi. Pada setiap langkah, satu buah kandidat diambil dari
himpunannya (Darnita
& Toyib, 2019).
2. Himpunan
Solusi, S.
Himpunan ini berisi kandidat-kandidat
yang terpilih sebagai solusi persoalan. Dengan kata lain, himpunan solusi
adalah himpunan bagian dari himpunan kandidat (Sunandar
& Pristiwanto, 2019).
3. Fungsi
Seleksi (Selection Function)
Fungsi ini dinyatakan dengan predikat
seleksi. Merupakan fungsi yang pada setiap langkah memilih kandidat yang paling
memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih pada suatu
langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya (Yunata
& Widayati, 2020).
4. Fungsi
Kelayakan (Feasible)
Fungsi ini dinyatakan dengan predikat
layak. Fungsi kelayakan ini merupakan fungsi yang memeriksa apakah suatu
kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat
tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk tidak
melanggar batasan/aturan �(constraints) �yang ada. Kandidat yang �layak dimasukkan �ke dalam himpunan solusi, sedangkan yang tidak
layak dibuang dan tidak pernah dipertimbangkan lagi (Darnita
& Toyib, 2019).
5. Fungsi
Obyektif
Fungsi obyektif
ini merupakan sebuah fungsi yang memaksimumkan atau meminimumkan nilai solusi.
Dengan kata lain, algoritma greedy melibatkan pencarian sebuah himpunan bagian,
S, dari himpunan kandidat, C yang dalam hal ini, S harus memenuhi beberapa
kriteria yang ditentukan, yaitu menyatakan suatu solusi dan S dioptimasi oleh
fungsi obyektif (Sunandar
& Pristiwanto, 2019). Ada
kalanya solusi optimum global yang diperoleh dari algoritma greedy yang
diharapkan sebagai solusi optimum dari persoalan, belum tentu merupakan solusi.
optimum (terbaik), tetapi solusi sub-optimum atau pseudo-optimum. Hal ini
dikarenakan algoritma greedy tidak beroperasi secara menyeluruh terhadap semua
alternatif solusi yang ada dan terdapat beberapa fungsi seleksi yang berbeda,
yaitu jika fungsi seleksi tidak identik dengan fungsi obyektif karena fungsi seleksi
biasanya didasarkan pada fungsi obyektif. Sehingga harus dipilih fungsi yang
tepat jika menginginkan algoritma menghasilkan solusi optimal atau nilai yang
optimum. Jadi, pada sebagian masalah algoritma greedy tidak selalu berhasil memberikan
solusi yang benar-benar optimum, tetapi algoritma greedy pasti memberikan
solusi yang mendekati (approximation)
nilai optimum (Fahmi,
2022).
Menurut Angga & Munir jika
jawaban terbaik mutlak tidak diperlukan, maka algoritma greedy sering berguna
untuk menghasilkan solusi cukup baik (approximation),
daripada menggunakan algoritma yang lebih rumit untuk menghasilkan solusi yang
terbaik (Ramadhani,
2022). Bila algoritma
greedy optimum, maka keoptimalannya itu dapat dibuktikan secara matematis.
Gambar 1. Contoh Skema Algoritma Greedy
B. Penjadwalan
Baker menyatakan bahwa pengertian penjadwalan adalah kegiatan
pengalokasian sumber-sumber atau mesin-mesin yang ada untuk menjalankan
sekumpulan tugas dalam jangka waktu tertentu (Rachman,
Watunglawar, Amperajaya, Adnan, & Sriwana, 2022).
C. Jquery
JQuery adalah library atau kumpulan
kode JavaScript siap pakai. Keunggulan menggunakan JQuery dibandingkan dengan JavaScript
standar, yaitu menyederhanakan kode JavaScript dengan cara memanggil
fungsi-fungsi yang disediakan oleh JQuery (Venata,
2022).
Metode Penelitian
Pada penelitian ini, metode
pengembangan sistem yang digunakan adalah metode prototyping. Hal ini dikarenakan penggunaan prototyping
dalam pembuatan sebuah sistem menjadikan pengembangan lebih dekat dengan user (Hamidy, Surahman,
& Famelia, 2022). Metode ini memiliki beberapa tahapan
diantaranya adalah seperti pada Gambar 2.
Gambar
2. Metode Prototyping
A. Requirements and definition
Pada tahap ini, peneliti melakukan
beberapa hal untuk mengetahui kebutuhan dari sistem yang dibangun. Adapun tahapannya adalah
:
1. Wawancara
dilakukan untuk mengumpulkan semua informasi sebagai bahan untuk melakukan
penelitian kepada ketua Program Studi Teknik Informatika
2. Menganalisa
permasalahan apa yang akan dicari penyelesaiannya.
3. Mencari
data-data, mempelajari jurnal-jurnal, artikel, atau buku dan sumber informasi
dari internet yang digunakan sebagai bahan referensi sebelum memecahkan
permasalahan yang dihadapi.
4.
Menganalisa alat dan bahan yang
dibutuhkan dalam penyelesaian masalah.
B. System and software design
Pada tahap ini, dibuat perancangan dari
sistem:
1. Cara
kerja sistem secara keseluruhan didesain menggunakan notasi diagram flow chart
dan data flow diagram. Diagram sistem dapat dilihat pada Gambar 3 dan Gambar 4.
2. Anggota
himpunan kandidat merupakan suatu array yang terdiri dari data dosen, mata
kuliah, ruangan, jumlah jam, dan kelas.
3. Fungsi
seleksi yang mengecek apakah pasangan data yang didapat dari himpunan kandidat
dapat dinyatakan sebagai bagian dari solusi. Pada fungsi ini dimasukkan
sejumlah aturan yang dimiliki organisasi SMK NURUL ISLAM CIANJUR dalam menyusun
jadwal, seperti aturan pasangan data yang dinyatakan bentrok, aturan jumlah jam
maksimal dosen mengajar, dll
4.
Fungsi Objektif yang digunakan pada
penelitian ini bertujuan menentukan mana solusi paling baik, dari sekumpulan
solusi yang ada.
C.
Implementation and Unit
Testing
Pada tahap ini, semua yang telah
dirancang akan diimplementasikan sesuai hasil rancangan. Berikut adalah
tahapannya:
1. Melakukan
implementasi dan pembangunan sistem sebagai penyelesaian masalah, dengan
membuat sistem penjadwalan dengan algoritma greedy.
2. Uji coba
dengan melakukan perbandingan jumlah ruangan kosong pada sistem manual dengan
sistem yang menggunakan algoritma greedy.
Gambar
3. Flowchart Penjadwalan
D. System Testing
Pada tahap ini,
metode pengujian memanfaatkan data riil dari SMK NURUL ISLAM CIANJUR dengan
data pada Tabel 1. Pengujian dilakukan dengan menggunakan browser Google Chrome
dan Microsoft Excel atau Adobe Reader. Pengujian dilakukan dengan melakukan
pengamatan di kedua alat ini. Metode pengujian ini menggunakan sebuah tabel
yang memiliki 2 kolom utama, kolom yang pertama merupakan metode lama yang
sudah diterapkan, sementara kolom kedua merupakan metode yang menggunakan
algoritma greedy. Pengujian ini menghitung berapa waktu kosong yang dimiliki
oleh setiap ruangan dari jadwal pelajaran yang terbentuk oleh sistem, dimana
waktu kosong tersebut dihitung perhari dalam sepekan.
Tabel 1 Data
Riil Dari Smk Nurul Islam Cianjur
|
No |
Data |
Jumlah |
|
1 |
Ruangan |
27 |
|
2 |
Mata
Pelajaran |
214 |
|
3 |
Kelas |
52 |
|
4 |
Guru |
47 |
|
5 |
Kurikulum |
484 |
Langkah pertama
pengujian adalah memastikan data yang diterapkan pada metode lama yang
digunakan oleh SMK NURUL ISLAM CIANJUR adalah berdasarkan per ruangan. Hal ini
dilakukan untuk mempermudah dalam proses perbandingan.
Langkah kedua
adalah mulai meng-input data dosen, mata kuliah, kelas, ruangan, dan kurikulum berdasarkan
jadwal manual SMK NURUL ISLAM CIANJUR.
Langkah
ketiga adalah mulai membandingkan setiap ruangan setiap harinya antara metode
lama yang digunakan oleh SMK NURUL ISLAM CIANJUR dengan sistem yang telah
dibuat dengan metode algoritma greedy pada modul penjadwalan.
Langkah keempat
adalah menyimpulkan setiap ruangan dengan perhitungan persentase ruangan kosong
dengan rumus (1).
Langkah
kelima adalah menyimpulkan keseluruhan dari setiap kesimpulan per-ruangan dan
dengan rumus (2).
banyaknya ruangan (presentase
ruangan kosong tiap ruangan) �100% (2)
14
Hasil dan Pembahasan
Tabel 2 Hasil Pengujian
|
Tahun Ajaran |
Semester |
Hari |
Ruangan Kosong dengan
Metode Manual |
Ruangan Kosong dengan
Metode Greedy |
||
|
|
|
Senin |
14,81% |
4 |
74,07% |
20 |
|
|
|
Selasa |
18,52% |
5 |
74,07% |
20 |
|
2018/ 2019 |
Genap |
Rabu |
14,81% |
4 |
74,07% |
20 |
|
Kamis |
11,11% |
3 |
77,78% |
21 |
||
|
|
|
Jum�at |
18,52% |
5 |
81,48% |
22 |
|
|
|
Sabtu |
77,78% |
21 |
77,78% |
21 |
|
|
|
Senin |
22,22% |
6 |
81,48% |
22 |
|
|
|
Selasa |
22,22% |
6 |
81,48% |
22 |
|
2018/ 2019 |
Ganjil |
Rabu |
25,93% |
7 |
81,48% |
22 |
|
Kamis |
37,04% |
10 |
81,48% |
22 |
||
|
|
|
Jum�at |
59,26% |
16 |
81,48% |
22 |
|
|
|
Sabtu |
96,30% |
26 |
85,19% |
23 |
|
|
|
Senin |
22,22% |
6 |
74,07% |
20 |
|
|
|
Selasa |
22,22% |
6 |
77,78% |
21 |
|
2017/ 2018 |
Ganjil |
Rabu |
22,22% |
6 |
77,78% |
21 |
|
Kamis |
25,93% |
7 |
77,78% |
21 |
||
|
|
|
Jum�at |
29,63% |
8 |
77,78% |
21 |
|
|
|
Sabtu |
92,59% |
25 |
81,48% |
22 |
Berbeda dengan jadwal riil dengan metode manual yang digunakan oleh SMK Nurul
Islam Cianjur, data cenderung rata per harinya. Ruangan kosong hanya terlihat
di hari Sabtu sehingga akan membuat masalah- masalah seperti dosen tidak
kebagian ruangan di jam pengganti atau mahasiswa tidak memiliki ruangan untuk
belajar diluar jam kuliah. Jika dilihat ruangan kosong di jadwal riil bisa
mencapai lebih dari 50%, itu karena dalam 1 hari total jam aktif adalah 14 jam
tetapi pada kenyataannya jadwal riil aktif hanya 6-12 jam per harinya dan
menimbulkan ruangan kosong di sisa jam ditambah ruangan lain yang benar-benar
tidak terpakai di hari itu.
Kesimpulan
Berdasarkan
pelaksanaan penelitian yang telah dilakukan dapat
disimpulkan bahwa penerapan algoritma greedy terhadap sistem penjadwalan mata
kuliah pada SMK Nurul Islam Cianjur mampu mengatasi optimasi ruangan dilihat
dari banyaknya ruangan yang kosong. Hal tersebut dapat dilihat dari hasil tahap
pengujian yang menunjukkan bahwa pada algoritma greedy setiap ruangan yang
pertama kali dilalui oleh proses algoritma akan dimasukkan oleh kurikulum yang
tersedia saat itu sampai batas maksimum total jam per ruangan, yaitu 14 jam.
Hal tersebut mengakibatkan banyak ruangan lain kosong. Ini berarti menunjukkan
bahwa SMK Nurul Islam Cianjur tidak perlu menambahkan ruangan lagi karena
ruangan yang tersedia saat ini sudah lebih dari cukup apabila SMK Nurul Islam
Cianjur menerapkan algoritma greedy pada sistem penjadwalannya. Lebih jauh dari
itu, ruangan-ruangan yang kosong bisa dimanfaatkan untuk keperluan lain seperti
tempat belajar ataupun lab. Selain itu dengan algoritma greedy pembuatan jadwal
akan lebih cepat sekitar 1 menit, banyaknya hari libur akibat
teroptimalisasinya jadwal pada hari-hari awal di setiap kelas dan meminimalisir
kesalahan- kesalahan seperti bentrok jadwal pelajaran.
Hal yang
perlu diperhatikan lainnya adalah selain memberikan hasil positif, namun
algoritma ini dalam penerapannya ke penjadwalan mata kuliah bersifat tidak
humanis karena beberapa kejanggalan akan ditemukan dalam pengujian, yaitu adanya
guru yang mengajar dari pagi sampai sore, guru wanita mengajar pada sore hari,
dikatakan tidak humanis karena kebanyakan dari guru wanita tidak menginginkan
hal ini, tidak adanya jeda waktu untuk istirahat, serta siswa dituntut untuk
mengikuti pelajaran dari pagi sampai sore.
Darnita, Yulia, & Toyib, Rozali. (2019). Penerapan
Algoritma Greedy Dalam Pencarian Jalur Terpendek Pada Instansi-Instasi Penting
Di Kota Argamakmur Kabupaten Bengkulu Utara. Jurnal Media Infotama, 15(2).
Fahmi, Anisah Nuril. (2022). Sistem penjadwalan
ujian skripsi menggunakan algoritma Greedy. Universitas Islam Negeri
Maulana Malik Ibrahim.
Hamidy, Fikri, Surahman, Ade, & Famelia, Revi
Hikmah. (2022). Perancangan Sistem Informasi Akuntansi Apotek Menggunakan
Metode MPKP (FIFO). Jurnal Tekno Kompak, 16(2), 188�199.
Hasibuan, Tyirmyji Tachir. (2022). Penerapan Algoritma
Adaptif Dalam Mengenali Wajah Manusia Berdasarkan Penjajaran Minutiae. Jurnal
Ilmu Komputer, 1(1), 1�7.
Mustari, Muhamad. (2022). Administrasi dan manajemen
pendidikan sekolah. Prodi S2 Studi Agama-Agama UIN Sunan Gunung Djati
Bandung.
Rachman, Taufiqur, Watunglawar, Darmiolla Natasia,
Amperajaya, M.Derajat, Adnan, Septian Rahmat, & Sriwana, Iphov Kumala.
(2022). Penentuan Interval Waktu Penggantian dan Perbaikan Komponen Kritis
Mesin Bubut Type SS-850 di PT. Hamdan Jaya Makmur Dengan Metode Age
Replacement. Jurnal Metris, 23(1), 52�62.
RAMADHANI, SITI DINAR REZKI. (2022). Optimasi Rute
Distribusi Berdasarkan Vehicle Routing Problem Dengan Fuzzy Time Windows.
Sitinjak, Kardo. (2018). Pengaruh Disiplin Belajar,
dan Variasi Mengajar Guru Terhadap Prestasi Belajar Ekonomi pada Siswa Kelas
VIII SMP Negeri 1 Tigalingga. Tahun Pelajaran 2018/2019.
Subakti, Hani, & Gata, Windu. (2021). Optimasi
Minimum Pola Baju Khas Kain Tenun Sarung Samarinda Menggunakan Algoritma
Greedy. Inspiration: Jurnal Teknologi Informasi Dan Komunikasi, 11(1),
1�6.
Sulasmoro, Arfan Haqiqi. (2022). Buku ajar
algoritma dan pemrograman I. Penerbit P4I.
Sunandar, Hery, & Pristiwanto, Pristiwanto.
(2019). Optimalisasi Implementasi Algoritma Greedy dalam Fungsi Penukaran Mata
Uang Rupiah. Jurnal Teknik Informatika UNIKA Santo Thomas, 4(2),
193�201.
Venata, Sendy Andrian. (2022). Sistem Informasi
Penjualan Dan Pembelian Buah Pada Toko Buah Surman Efendi Berbasis Website.
Univeristas Komputer Indonesia.
Yunata, Ardian, & Widayati, Qoriani. (2020).
Penjadwalan Pembuatan Container Portacamp Menggunakan Algoritma Greedy. Bina
Darma Conference on Computer Science (BDCCS), 2(1), 183�195.
|
Copyright holder: Ela Siti Laela, Windu Gata,
Jajang Jaya Purnama (2022) |
|
First publication right: Syntax Literate:
Jurnal Ilmiah Indonesia |
|
This article is licensed under: |