PENJADWALAN PERKULIAHAN MENGGUNAKAN ALGORITMA BREADTH FISRT SEARCH STUDI KASUS SISTEM PERKULIAHAN STMIK PROFESIONAL MAKASSAR Tasrif Hasanuddin Program Studi Sistem Informasi STMIK Profesional Makassar
[email protected] Abstrak Permasalahan pencarian adalah merupakan hal yang sering dijumpai oleh peneliti di bidang Kecerdadasn Buatan.Permasalahan ini merupakan hal penting dalam menentukan keberhasilan system kecerdasan buatan.Algoritma pencarian (searching algorithm) yang digunakan pada tulisan ini digunaka untuk mencari jadwal kuliah sesuai argumen kunci yang diterima. Dengan argumen kunci tersebut, hasil pencarian akan diperoleh salah satu dari dua kemungkinan, yaitu jadwal kuliah yang dicari ditemukan (successful) atau tidak ditemukan (unsuccessful). Penelitian ini menggunakan algoritma Breadth First Search untuk menyelesaikan permasalahan dalam menentukan penjadwalan Kuliah di STMIK Profesional Makassar. Tujuannya adalah untuk membuktikan apakah algoritma tersebut dapat menciptakan jadwal mengajar yang optimal atau tidak.Dari hasil Aplikasi program disimpulkan bahwa algoritma Breadth First Search akan dapat menemukan jadwal perkuliah dosen dan kelas sesuai dengan constraint yang telah ditetapkan Kata kunci: Algoritma, Breadth First Search Profesional Makassar. Dalam A. PENDAHULUAN permasalahan ini constraint yang harus 1.1 Latar Belakang Masalah penjadwalan kuliah merupakan dipenuhi memiliki sejumlah kekhususan masalah yang sangat kompleks, hingga dikarenakan waktu dan ruang yang saat ini masih merupakan sebuah topik terbatas dan kesediaan dosen dalam yang banyak dibahas dalam berbagai mengajar dengan waktu yang ditentukan, jurnal, tesis, desertasi, dan karya ilmiah karena sebagian dosen , khususnya dosen di seluruh penjuru dunia. Inti dari luar biasa mempunyai kegiatan diluar penjadwalan kuliah adalah bagaimana kampus. Pengalokasian dosen, waktu, menjadwalkan sejumlah komponen yang dan ruang terhadap sebuah kelas akan terdiri atas kelas, mata kuliah, dosen, sangat berpengaruh pada kelas-kelas ruang, dan waktu dengan sejumlah lainnya menjadi sebuah rantai yang batasan dan syarat (constraint) tertentu. panjang dan sulit dipecahkan. Masalah Permasalahan penjadwalan kuliah sendiri masih bertambah kompleks dengan memiliki banyak sekali variasi sesuai adanya sejumlah matakuliah yang harus dengan kebijakan lembaga perguruan dialokasikan di ruangan tertentu yang tinggi tempat jadwal kuliah tersebut akan memiliki kriteria tersendiri. digunakan. Sebagai studi kasus, penulis Algoritma Breadth-First-Search (BFS) menggunakan masalah penjadwalan mempunyai kelemahan karena BFS harus kuliah yang dihadapi di STMIK menyimpan semua node yang 1
dibangkitkan , maka metoda ini membutuhkan memori dan waktu yang cukup banyak.Walaupun demikian BFS dikenal sebagai algoritma yang baik dalam mencari solusi suatu masalah karena Algoritma ini menjamin ditemukannya Solusi yang paling baik (Complete and Optimal) . 1.2 Perumusan Masalah Penjadwalan yang dijadikan studi kasus dalam tuilisan ini adalah merupakan penjadwalan kuliah pada STMIK Profesional Makassar. Data-data yang dibutuhkan dalam kasus penjadwalan tersebut adalah data mata kuliah yang 1 Dimensi Permasalahan 2 Atribut Objek Penjadwalan 3 Hard Constraint
4
Soft Constraint
ditawarkan untuk setiap jenjang dan semester, data kelas dari tingkat awal sampai tingkat akhir untuk setiap jenjang ( D3 dan S1), data ruang yang dapat dipergunakan untuk perkuliahan serta data dosen yang mengajar. Banyaknya jumlah dan tingkat kompleksitas constraint yang ada membuat penulis harus melakukan klasifikasi constraint tersebut dalam kategori hard constraint (harus terpenuhi) dan soft constraint (diupayakan untuk terpenuhi). Dimana klasifikasi dari hard constraint dan soft constraint terlihat pada tabel 1. Waktu dan Ruangan, Mata Kuliah Dosen, Kelas - Dosen @ Ruangan/waktu <=1 - Kelas @ Ruagan/waktu <=1 - Maksimum mengajar dosen setiap hari (3 x 100 menit) - Maksimum belajar siswa(kelas) setiap hari (3 x 100 menit) - Jam mengajar dosen tidak berurut jika mengajar selama (3 x 100 menit) - Jam belajar siswa(kelas) tidak berurut jika belajar selama (3 x 100 menit)
Tabel 1.Hard Constraint dan Soft Constraint B. TIJAUAN PUSTAKA
sebuah node khusus, t εT (disebut root
Pohon (Tree)
untuk pohon T) dan T – {t} terpartisi atau
Dalam kehidupan sehari-hari kita telah
terpisah menjadi beberapa sub himpunan
akrab dengan bentuk struktur pohon
T1,T2,…..,Tn, yang masing-masing juga
berjenjang
merupakan sebuah pohon yang disebut
dengan keluarga,
atau
struktur atau
berhirarki.Misalnya organisasi,
sub pohon atau anak pohon.
pertandingan
Dari penjelasan diatas, maka setiap node
dengan sistem gugur.Sebuah pohon T
juga merupakan sebuah root (subroot)
adalah
berhingga
untuk suatu subpohon. Untuk lebih
beranggotakan satu atau lebih data atau
jelasnya, perhatikan contoh bentuk pohon
node, sedemian hingga dapat ditentukan
pada gambar 1.
sebuah
jadwal
silsilah
himpunan
2
Gambar 1. Pohon
Pohon tersebut tersusun atas delapan
pada satu level belum ditemukan solusi,
buah node, T = {a,b,c,d,e,f,g,h}. Pohon
maka pencarian dilanjutkan pada level
T
berikutnya. Demikian seterusnya sampai
mempunyai
root
a. Root
a,
T
terpartisi menjadi dua anak pohon,
ditemukan solusi
yaitu T1= {b,c} dan T2 = {d,e,f,g,h}.
a) Keuntungan Breadth-First Search
Pada
Tidak
pembahasan
tentang
pohon,
akan
menemui
jalan
buntu,
sering digunakan istilah-istilah keluarga
menjamin ditemukannya
(family).Node
solusinya memang ada)dan solusi yang
a
dinamakan
induk
solusi
(jika
(parent) dari node b dan d disebut anak
ditemukan pasti yang paling baik.
(children) dari node a. Berkaitan dengan
Jika ada satu solusi, maka Breadth–
jumlah anak dari suatu node, terdapat
First -Search akan menemukannya, jika
sebuah
sebuah
ada lebih dari satu solusi, maka solusi
degree)
minimum akan ditemukan.
definisi
pohon.Derajat
pada
node(node’s
adalah jumlah anak dari suatu node.
b) Kelemahan Breadth-First Search
Pada pohon diat as: node a berderajat
Membutuhkan memori yang banyak,
2, node b dan g berderajat 1, node d
karena harus menyimpan semua simpul
berderajat 3 dan node c,e,f serta h
yang
pernah dibangkitkan.
berderajat 0. Node-node yang berderajat
harus
dilakukan
0 disebut dengan daun (leaf) atau
Search dapat
terminated nodes,.
simpul-simpul sampai di level bawah.
2.2. Breadth-First Search (BFS)
Membutuhkan waktu yang cukup lama.
Pencarian BFS dilakukan pada semua
2.3. Algoritma
simpul
Kata
dalam
setiap level secara
berurutan dari kiri ke kanan. Jika
agar
melakukan
algoritma
diambil
Hal
ini
Breadth–First penelusuran
dari
nama
ilmuan muslim Abu Ja’far Muhammad 3
bin Musa Al-Khwarizmi (780-846) yang banyak
menghasilkan
karya
C. ANALISA
dalam
ALGORITMA BREADTH FIRST
bidang matematika, disamping
SEARCH
karya-karyanya
bidang
lainnya
musik.
Algoritma
langkah
PENELUSURAN
dalam
seperti geografi dan adalah
deretan
komputasi
yang
Penelusuran
algoritmaBreadth First
Searchmemiliki beberapa tahap. Tahap pertama adalah membuat solusi dalam bentuk pohon (tree). Setelah
tahap
mentransformasikan masukan menjadi
pertama dibuat, maka ditahap kedua
keluaran.Untuk
perlu
adalah penerapan mata kuliah beserta
danrancangan
dosen dan kelas pada kerangka jadwal
adanya
memulainya
perancangan,
tersebut berisi urutan langkah-langkah
kegiatan perkuliahan dosen secara BFS.
pencapaian solusi yang biasanya ditulis
Penelusuran
dalam notasi algoritmik.
mencari kombinasi
2.4 . Penjadwalan
ruangan dimulai dari pada hari senin jam
Penjadwalan (scheduling)
algoritma BFS dimulai hari , jam dan
merupakan
08 pada ruangan 210 selanjutnya pada
salah satu kegiatan yang paling penting
ruangan yang lain setelah semua ruangan
pada
telah terisi penuh di lanjutkan pada jam
perguruan
adalah pengaturan
tinggi.Penjadwalan waktu
dari
suatu
09
dan
seterurusnya
kegiatan perkuliahan, yang mencakup
17.00.Setelah
kegiatan
selanjutnya
mengalokasikan
waktu dan kelas,
ruangan,
ketersediaan waktu
hingga
kelas mencari
pukul
ditemukan, hari yang lain
hingga hari sabtu.
dosen menentukan urutan pelaksanaan
Pada setiap node seperti pada gambar 2
bagi suatu kegiatan perkuliahan. Dalam
adalah merupakan kombinasi antara hari ,
suatu perusahaan industri, penjadwalan
jam dan ruangan , 2 Kode pertama
diperlukan
dalam
menunjukkan hari, kode keketiga dan ke
mengalokasikan tenaga operator, mesin
4 menunjukkan jam dan 3 kode terakhir
dan peralatan produksi, urutan proses,
menunjukkan ruangan , proses pencarian
jenis
tentunya dimulai dari node teratas sesuai
antara
produk,
lain
dan
pembelian
material.Demikian pula, dalam kegiatan
dengan langkah berikut:
perhotelan,
Masukkan node akar ke dalam Queue
penjadwalan
diperlukan
dalam pengaturan kamar hotel, ruang
Ambil node dari awal Queue , lalu cek
seminar atau resepsi, menu makanan,
apakah node merupakan solusi
atau acara entertaintment. 4
Jika node merupakan solusi , pencarian Senin
selesai dan hasil dikembalikan Jika node bukan solusi masukkan seluruh node anak dalam Queue
sn08210
sn08301
sn08302
sn08303
sn09210
sn09301
sn09302
sn09303
sn11210
sn11301
sn11302
sn11303
sn13210
sn13301
sn13302
sn13303
sn15210
sn15301
sn15302
sn15303
sn17210
sn17301
sn17302
sn17303
Jika Queue kosong dan setiap node sudah di cek , pencarian selesai Jika Queue tidak kosong ulangi pencarian dari poin
Gambar 2. Model Pohon Untuk Kerangka Jadwal Penerapan constraint dilakukan pada
belajar lebih dari 1 kali pada jam 8 , dan
setiap node , terutama hard constraint,
ruangan
berikut contoh aplikasi pada Gambar 3,.
Disamping
Misalnya dosen dengan kode DE1 =
dimplementasi
“Elisabeth
mata
dosen DE1 dan Kelas RE21 tidak boleh
kuliah Manajemen Umum untuk kelas
mengajar dan belajar berurut 3 kali pada
RE21 , maka proses pencarian dimulai
hari senin. Terlilhat pada report hari
dari node teratas yaitu hari senin,
senin
kemudian dilanjutkan pada node akar
SH.MH” tiga kali mengajar pada hari
yaitu “SN08210” pada node , maka
tersebut tetapi hanya mengajar pada jam
dimulai
08:00-09:40 kemudian jam kedua 09:50-
sesuai
SH.,MH”
penerapan pada
“Elisabetsh
mengajar
Hard
tabel SH.MH”
1,
Constraint
210
belum hard Soft
walaupun
terisi
dosen.
constraint
juga
Constraint
yaitu
dosen
“Elisabeth
yaitu
dosen
11:30 kemudian istirahat pada jam ke 3
Tidak
boleh
yaitu jam 11:40:13:20, Kelas ke 3 untuk
mengajar lebih dari 1 kali pada jam 08,
dosen
“Elisabeth
SH
MH”
demikian juga kelas RE21 tidak boleh
dilanjutkan pada pukul 13:30-15:10.
nanti
5
Gambar 3. Implementasi Hard Constraintdan Soft Constraintpada aplikasi Penjdawalan Kuliah menunggu waktu yang cukup lama untuk D. SIMPULAN DAN SARAN 4.1 Simpulan
mencari node yang lain , bisa memtuhkan
Berdasarkan analisis yang dilakukan
waktu sekiatar 1 menit.
maka
DAFTAR PUSTAKA
algoritma BFS pada Aplikasi
penjadwalan
kuliah
mennjukkan
[1] .Cynthia Kustanto,Ratna Mutia,Pocut
Algoritma ini bekerja dengan baik,
Viqarunnisa, Penerapan Algoritma
dengan menerapkan constraint yang telah
Breadth-first Search dan Depth-
ditetapkan , dan sesuai dengan kelebihan
first Search Pada
Algoritma
Engine
BFS
adalah
menjamin
for
ITB
FTP Search Network
,
ditemukannya solusi yang paling baik
Laboratorium Ilmu dan Rekayasa
(Complete dan Optimal).
Komputasi
4.2 Saran
Informatika,
Walaupun Algoritma menjamin Solusi
Bandung Jl. Ganesha 10, Bandung
yang paling baik
,
kelemahan yang
Departemen Institut
Teknik Teknologi
[2] Hasanuddin, Tasrif, Model Semantic
sangat fatal dari algoritma ini adalah
Webuntuk
membutuhkan memori dan waktu yang
Kuliah
cukup banyak, karena algoritma ini akan
Profesional Makassar . Jurusan
menyimpan
Sistem
semua
node
yang
dibangkitkan . dan ini terlihat dari
Penyusunan Jadwal
Studi
Kasus
Informasi
:
Stmik
STMIK
Profesional Makassar
aplikasi yang diimplementasikan ketika
[3] Khoirush Sholih Ridhwaana Akbar,
beberapa node sudah terisi, maka akan
Penerapan Teori Pohon Dalam 6
Kajian Struktur Data, Program
Penerbit Andi Offset Yogyakarta,
Studi Teknik Informatika, Institut
2011
Teknologi Bandung Jl. Ganesha 10, Bandung
[6] Tjatur Kandaga, Alvin Hapendi, Evaluasi dan Usaha Optimalisasi
[4] Novriyanto, M. Zaid.S , Penerapan
Algoritma Depth First Search dan
Algoritma Backtracking Berbasis
Breadth
First
Search
Blind Search untuk Menentukan
Penerapan pada Aplikasi Rat Race
Penjadwalan Mengajar , Jurusan
dan Web Peta , Jurusan Teknik
Teknik Informatika, Fakultas Sains
Informatika,
dan Teknologi Universitas Islam
informasi,
Negeri Sultan Syarif Kasim Riau
Maranatha Jl. Prof. Drg. Suria
Pekanbaru, Indonesia .
Sumantri No. 65 Bandung 40164
Fakultas Universitas
dengan
Teknologi Kristen
[5] Sutojo , Edy Mulyanto, Vincent Suhartono,
Kecerdasan
Buatan,
7
