“PERANCANGAN ALGORITMA PENJADWALAN KULIAH MENGGUNAKAN METODE ALGORITMA BEAM SEARCH” ( STUDI KASUS KAMPUS III UNIVERSITAS GRAHA NUSANTARA)
Muhammad Noor Hasan Siregar
Abstrak
Salah satu kegiatan dalam universitas yang membutuhkan banyak waktu untuk menyelesaikannya adalah membuat jadwal mata kuliah. Jadwal mata kuliah yang baik adalah jadwal yang memperhatikan semua komponen dasar penyusunnya. Komponen dasar terdiri atas dosen, mata kuliah, ruangan, dan jam kuliah. Penulis mencoba mencari alternatif dari penjadwalan dengan menggunakan algoritma beam search, yaitu pencarian solusi optimal dengan membagi permasalahan utama menjadi sub-sub masalah yang lebih kecil (branching) kemudian mencari nilai optimal sementara (lower bound) untuk tiap sub masalah dan dilanjutkan pencarian hingga tidak ada lagi sub masalah yang mungkin menghasilkan nilai lebih baik. Dari penggunaan algoritma beam search dalam penyelesaian masalah ini, diharapkan dapat menjadi alternatif untuk penjadwalan, dan menginspirasi untuk diadakan penelitian mengenai algoritma beam search lebih lanjut, dan pembuatan program berbasis jaringan.
Kata Kunci : Penjadwalan, beam search.
Penyusunan jadwal di Universitas Graha
PENDAHULUAN
Nusantara khususnya di Kampus III Universitas Pertumbuhan
perguruan
tinggi,
yang
Graha Nusantara selama ini dilakukan secara
ditandai dengan peningkatan jumlah mahasiswa
manual, meskipun penyusunan jadwal kuliah dapat
yang diterima dalam satu periode penerimaan
diselesaikan namun memerlukan waktu yang lama
mahasiswa menyebabkan peningkatan jumlah klas
untuk mendapatkannya. Kondisi ini membuat
dan jumlah ruangan yang diperlukan sebagai ruang
sistem
kuliah, sedangkan ruang kuliah yang tersedia relatif
perubahan yang diinginkan saat itu.
yang
lama
tidak
responsif
terhadap
tetap. Kondisi ini menuntut pihak pengelola
Penyusunan jadwal mata kuliah yang
universitas untuk dapat menjadwalkan penggunaan
efektif dan dapat diakses dan diubah secara cepat
ruang kuliah dengan seefisien mungkin agar dapat
memerlukan suatu algoritma penyusunan jadwal
memenuhi kebutuhan terhadap ruang kuliah bagi
yang mampu memberikan teknik penyusunan
seluruh
jadwal yang dapat dilakukan dengan mudah.
mata
kuliah
yang
memerlukan.
Permasalahan ini ditambah dengan pergantian dosen pengajar mata kuliah maupun keinginan pindah jadwal yang diajukan oleh beberapa dosen maupun mahasiswa sehubungan dengan keperluan mereka.
mencari solusi optimal dari 60 job kita hanya
METODE PENELITIAN
menghitung sebanyak 2 x 30 job. Penjadwalan
merupakan
proses
Metode
beam
perhitungan
search
lebih
sedikit
dibandingkan
dengan
pengalokasian sumber-sumber atau mesin-mesin
melakukan
yang tersedia untuk menjalankan sekumpulan tugas
metode branch and bound karena pada tiap level
dalam jangka waktu tertentu (Baker 1991),
akan tersimpan sebanyak b buah penyelesaian
Beam search merupakan salah satu metode
optimal sementara yang akan dianalisa pada level
yang dikembangkan oleh ahli software artificial
berikutnya. Secara grafis proses pencarian solusi
intelligence untuk membentuk pohon keputusan
optimal dengan metode beam search tergambar
secara parsial (Lowrence, 1976; Rubin, 1978; Ow
pada gambar 1 dibawah ini
and Morton, 1988). Metode ini sangat responsif untuk pembuatan program permainan catur yang andal (Anthony and Scafter, 1990). Beam search memiliki dasar pencarian solusi yang sama dengan algoritma
branch
and
bound,
yaitu
dengan
melakukan branching yang dilanjutkan dengan pencarian solusi optimal untuk sub masalah yang terpilih. Perbedan utama antara beam search dengan branch and bound adalah bahwa metode beam search
membuang
cabang-cabang
yang
diperkirakan tidak baik dari pohon keputusan.
Gambar 1, Algoritma Beam Search
Satu yang utama adalah beam search memiliki ukuran yang baik tentang perkiraan solusi
Gambaran Umum Penjadwalan di Kampus III
optimal dari cabang pohon keputusan untuk
Universitas Graha Nusantara
membuang cabang yang kurang baik dengan menyimpan
sejumlah
solusi
optimal
Penyusunan jadwal kuliah yang dilakukan di
tanpa
kampus III Universitas Graha Nusantara saat ini
menanggung resiko yang besar. Jadi beam search
adalah dengan cara coba-coba. Tiap fakultas yang
hanya menyimpan beberapa penyelesaian optimal
ada di kampus tersebut, melakukan penjadwalan
pada tiap level (beam width = b) guna melakukan
terhadap mata kuliah fakultas masing-masing
pencarian solusi optimal pada tiap percabangan
dengan alokasi ruang yang diprioritaskan untuk
pada level berikutnya.
fakultas itu, dan bila terjadi kekurangan ruang atau
Misalkan untuk 30 job pada satu mesin,
terjadi jadwal bersamaan pada satu ruang dilakukan
dengan beam width 4. Pertama kita hanrus
negosiasi dengan dosen mata kuliah tersebut untuk
membentuk satu fungsi evaluasi yang digunakan
dijadwalkan pada waktu atau lokal yang lain.
untuk memilih 4 solusi optimal pada tiap level. Pada level pertama akan didapatkan 30 cabang
Pengumpulan Data
solusi, dipilih 4 cabang yang memiliki nilai fungsi
Teknik pengumpulan data yang digunakan dalam
evaluasi
selanjutnya
penelitian ini adalah metode wawancara dengan
mengembangkan 4 cabang yang terpilih pada level
komponen sistem/pemakai, serta mengamati proses
sebelumnya dan memilih 4 solusi optimal, begitu
penjadwalan secara langsung.
seterusnya hingga level terakhir. Pada level kedua
Wawancara
optimal,
tahap
akan didapatkan 4 x 29 = 166 cabang. Jumlah
Wawancara dilakukan untuk mendapatkan
cabang yang dikembangkan tiap level hanya 4,
informasi mengenai sistem penjadwalan mata
berapapun jumlah job. Untuk 60 job akan terbentuk
kuliah yang sekarang digunakan di Universitas
60 level dan 30 job terbentuk 30 level. Jadi untuk
Graha Nusantara. Wawancara dilakukan dengan
Kepala Bagian Akademik Fakultas Teknik dan
bersamaan antara beberapa fakultas. Pemakaian
Kepala Sub Bagian Perlengkapan dan Sarana
ruangan secara bersamaan ini mungkin terjadi
Umum Universitas Graha Nusantara.
karena tiap ruang diprioritaskan untuk ditempati oleh beberapa jurusan
Wawancara dengan Kepala Bagian Akademik Fakultas Teknik Universitas Graha Nusantara.
Proses penjadwalan yang dilakukan secara manual ini memerlukan waktu penyelesaian lebih
Menurut Kepala Bagian Akademik Fakultas
dari tiga minggu, dan tidak dapat mendeteksi
Teknik Universitas Graha Nusantara (Bp. Sahrul)
kesalahan pengalokasian ruang untuk beberapa
penjadwalan mata kuliah yang digunakan di
mata kuliah pada satu saat secara cepat. Kesalahan
Fakultas Teknik Universitas Graha Nusantara
pengalokasian ruang yang menyebabkan terjadinya
dilakukan secara manual yaitu menggunakan
jadwal bersamaan pada satu ruang dapat terdeteksi
Microsoft Excel secara coba-coba. Teknik yang
secara jelas pada saat jadwal kuliah diterapkan.
digunakan untuk menghindarkan jadwal bersamaan
Penyelesaian yang dilakukan apabila terjadi jadwal
antar mata kuliah berurutan dengan mengikuti
bersamaan
kaidah 1-5, 3-7 artinya mata kuliah semester satu
mencarikan alternatif ruang kosong yang lain yang
dijadwalkan bersamaan dengan semester lima,
layak untuk dipakai (kapasitas ruang memenuhi).
pada
satu
ruang
adalah
dengan
sedangkan mata kuliah semester tiga dijadwalkan bersamaan dengan mata kuliah semester tujuh.
Pengembangan Model
Kaidah 1-5, 3-7 dipakai sebagai salah satu
Penjadwalan
merupakan
proses
aturan prioritas penempatan mata kuliah tiap
pengalokasian sumber-sumber atau mesin-mesin
semester dari algoritma penjadwalan mata kuliah.
yang tersedia untuk menjalankan sekumpulan tugas
Aturan 1-5, 3-7 akan menghindarkan terjadinya
dalam jangka waktu tertentu (Baker, 1991).
jadwal bersamaan antara mata kuliah semester yang
Penjadwalan mata kuliah dapat diartikan sebagai
bersamaan, apabila jumlah sks semester bersamaan
pengalokasian sumber-sumber (ruang, dosen, mata
(1 dan 5, atau 3 dan 7) maksimal sama dengan
kuliah
jumlah sks dalam satu minggu.
sekumpulan
dan
mahasiswa) tugas
untuk
menjalankan
(terlaksananya
proses
perkuliahan dan memenuhi kebutuhan beban sks Wawancara
dengan
Perlengkapan
dan
Kepala Sarana
Sub Umum
Bagian Biro
tiap mata kuliah) dalam jangka waktu tertentu (sesuai dengan jam kuliah yang tersedia).
Akademik Universitas Graha Nusantara. Informasi yang didapatkan dari Kepala Sub Bagian Perlengkapan dan Sarana Umum (ibu Ati) sebagai berikut; mekanisme penjadwalan yang dilakukan di Universitas Graha Nusantara dilakukan dalam dua tahap.
Pembatas Utama Penyusunan jadwal kuliah memiliki beberapa kendala yang harus diperhatikan adalah : 1. Dosen pada satu saat hanya dapat mengajar pada satu ruang
Tahap pertama penjadwalan dilakukan oleh
2. Jadwal kuliah pada satu semester
Biro Akademik tiap fakultas, untuk menjadwalkan
3. Jadwal kuliah dua semester bersamaan
mata kuliah fakultas itu dengan menempatkan
4. Ruang kuliah pada satu saat hanya dapat
ruangan yang diprioritaskan untuk dipakai fakultas
melakukan kegiatan perkuliahan oleh satu
tersebut,
dosen
tanpa
mempertimbangkan
pemakaian
ruangan secara keseluruhan. Tahap kedua Sub Bagian Sarana dan Perlengkapan Umum melakukan validasi terhadap jadwal usulan masing-masing fakultas dan melihat kemungkinan terjadinya pemakaian ruangan secara
Pembatas utama secara grafis diperlihatkan pada gambar dibawah ini
Jam Masuk 1
1
Jam Masuk 2
2 1
Jam Masuk 3
3 2
7).
---
Senin 4 3
1 4
2 1
1
2
3
4
3 2
Pembagian
ini
merupakan
pemberian
Sabtu 4
3
1 4
2 1
1
2
3
4
3 2
prioritas terhadap mata kuliah pada semester itu
4 3
4
1
2
3
4
Semester 1
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
Semester 3
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
Semester 5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
Semester 7
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
Status Ruang
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
Status Dosen
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
Pembatas Penjadwalan Mata kuliah
untuk menempati jam kuliah bagiannya, bila ternyata tidak layak baru dicari pada waktu kuliah bagian yang lain. 2. Meminimalkan jumlah jadwal bersamaan untuk mata kuliah pilihan merupakan kriteria optimal ketiga, sehingga tahapan ini dilakukan setelah kriteria
pertama
dan
dipenuhi.
Kriteria Optimal Jadwal Kuliah
Pencapaian
Kriteria optimal jadwal kuliah
menjadwalkan mata kuliah pilihan setelah mata
Pada tiap prodi terpenuhi :
kuliah wajib.
1. Minimasi jumlah jadwal bersamaan mata kuliah satu semester
kuliah dua semester yang berurutan
dilakukan
dengan
3. Pemerataan jam kuliah perhari-persemester dilakukan
2. Minimasi jumlah jadwal bersamaan mata
kriteria
kedua
dengan
memprioritaskan
untuk
memilih jam kuliah dengan jumlah sks jadwal kuliah perhari terkecil.
3. Minimasi jumlah jadwal bersamaan mata kuliah pilihan
4. Memaksimalkan kesesuaian kapasitas ruang dengan kapasitas ruangan yang diperlukan
4. Maksimasi pemerataan jumlah jam kuliah per semester per hari
dilakukan dengan langkah: 4.1. Ruangan
disusun
berdasarkan
urutan
5. Maksimasi kesesuaian kapasitas ruangan
kapasitas terkecil hingga ruangan dengan
dengan jumlah mahasiswa tiap mata kuliah
kapasitas terbesar. Diberikan prioritas
Urutan
untuk memilih ruang kuliah dari kapasitas
kriteria
menunjukkan
prioritas
pencapaian solusi optimal.
yang terkecil untuk dijadwalkan pada jam kuliah terpilih, bila ternyata kapasitas
Pemenuhan terhadap kriteria diatas secara umum
ruangan tidak mencukupi dipilih ruangan
dilakukan dalam dua langkah :
berikutnya hingga didapatkan ruangan
Langkah pertama, untuk memenuhi seluruh
yang sesuai atau seluruh ruangan telah
kriteria diatas dilakukan dengan memberikan bobot
terpilih.
alternatif
pada
masing-masing
mata
kuliah,
4.2. Bila seluruh ruangan sudah terpilih dan
kemudian dipilih mata kuliah dengan bobot altenatif
belum didapatkan ruangan yang sesuai
minimal untuk dijadwalkan terlebih dahulu.
diulang pencarian ruangan dari kapasitas
Langkah kedua, dilakukan pencarian jam kuliah
terbesar
yang memberikan nilai maksimal dari minimal
dijadwalkan pada jam kuliah terpilih.
hingga
terkecil
yang
dapat
bobot alternatif mata kuliah sisa dan nilai maksimal dari minimal total bobot alternatif mata kuliah sisa.
HASIL DAN ANALISA
Pemilihan jam kuliah untuk memenuhi kriteria optimal dipilih berdasarkan: 1. Meminimalkan jadwal bersamaan antara mata
Penyusunan
Algoritma
Penjadwalan
Mata
dilakukan
survei
lebih
kuliah Setelah
kuliah semester berurutan pada satu jurusan
ditemukan
dilakukan dengan membagi dua sama rata jam
mendalam
kuliah perhari dengan satu bagian diprioritaskan
Universitas Graha Nusantara terdapat beberapa
untuk menjadwalkan mata kuliah semester 1,2,5
aturan
dan 6 dan satu bagian lain untuk menjadwalkan
melakukan penyusunan jadwal mata kuliah. Aturan
mata kuliah semester 3,4,7 dan 8 (kaidah 1-5 3-
tersebut adalah:
yang
berlaku
bahwa
secara
secara
di
Kamus
khusus
III
dalam
1. Fakultas EKONOMI berlaku: jam masuk pertama 14.00 Wib. dan jam keluar terakhir
dipenuhi maka penjadwalan mata kuliah dilakukan secara bersamaan pada tiap fakultas
17.00 Wib. 2. Fakultas TEKNIK jam masuk pertama 13.30 dan jam keluar terakhir 17.00 Wib. 3. Fakultas TEKNIK Extension, EKONOMI Extension jam pertama 8.30 Wib. dan jam keluar terakhir 17.30 Wib. Dan dilakukan
Hasil Algoritma Penjadwalan Mata Kuliah Algoritma yang dihasilkan dari penelitian ini merupakan perancangan
dari Algoritma Beam
Search untuk jadwal mata kuliah, dimana untuk menyelesaikan permasalahan dilakukan dengan
hanya pada hari Jum’at dan Sabtu
membagi permasalahan kedalam sub-sub masalah Disamping ketiga hal di atas pada hampir seluruh fakultas terdapat mata kuliah gabungan (mata kuliah yang dijadwalkan secara bersama, digabung antara beberapa jurusan dalam satu ruang), untuk mata kuliah-mata kuliah umum seperti Bahasa Indonesia dan Pancasila. Beberapa
mata
kuliah
dalam beberapa level dan kemudian mencari beberapa solusi optimal sementara untuk tiap level yang akan digunakan sebagai pencarian solusi optimal pada level berikutnya. Jumlah solusi optimal yang dipilih pada algoritma ini hanya satu. Pemecahan permasalahan ini secara grafis terlihat
dengan
jumlah
mahasiswa banyak dijadwalkan menjadi beberapa lokal dan beberapa dosen penanggung jawab. Hal ini merupakan kendala tambahan yang ditemukan untuk mengimplementasikan algoritma penyusunan mata kuliah di Universitas Graha Nusantara.
pada gambar 2 Fungsi
Evaluasi
dan
Kriteria
Optimal
algoritma disesuaikan dengan kriteria optimal jadwal. Fungsi Evaluasi (minimal jumlah alternatif mata kuliah) dan Kriteria Optimal (maksimal jumlah alternatif mata kuliah sisa).
Pemecahan kendala ini dilakukan dengan langkah : Ide dari algoritma ini adalah : 1. Untuk mengatasi adanya beberapa mata kuliah yang dijadwalkan bersamaan dilakukan dengan memisahkan mata kuliah gabungan dengan mata kuliah biasa, kemudian menjadwalkannya
Kriteria optimal dicapai dengan memberikan jumlah alternatif jadwal tidak bersamaan maksimal yang mungkin untuk mata kuliah yang belum terjadwal. Hal ini akan memberikan kesempatan
secara khusus.
terbesar bagi mata kuliah yang lain untuk dapat 2. Penjadwalan mata kuliah yang dibagi menjadi
dijadwalkan tanpa tumpang tindih.
beberapa ruangan dilakukan dengan mencari beberapa
ruang
yang
‘siap’
(status
=
Fungsi
evaluasi
yang digunakan
untuk
menganggur) dan status dosen = menganggur
menentukan mata kuliah terkritis adalah dengan
serta
itu
memilih mata kuliah yang memiliki jumlah
menganggur pada setiap jam yang layak dan
alternatif jadwal tidak bersamaan minimal sehingga
mencari nilai maksimal dari nilai alternatif
diharapkan akan meminimalkan jumlah mata kuliah
minimal mata kuliah sisa dan total alternatif
dengan jadwal bersamaan.
status
jadwal
jurusan-semester
mata kuliah sisa. Pemecahan Masalah Melihat kendala tambahan di atas terlihat keterkaitan antara mata kuliah dalam satu fakultas, karena sebagian mata kuliah jurusan digabung dengan jurusan lain pada fakultas itu. Agar keterkaitan antar mata kuliah tersebut dapat
Permasalahan Utama
Solusi Optimal
Sub masalah level 1
Dhwm
:
Status jadwal Dosen pada hari keh, jam ke-w dan minggu ke-m untuk mata kuliah K*
Rhwm
:
Status jadwal Ruang pada hari keh, jam ke-w dan minggu ke-m untuk mata kuliah K*
Status
:
‘-‘= menganggur, terpakai / sibuk
sh
:
Jumlah sks yang sudah dijadwalkan untuk semester mata kuliah K* pada jurusan mata kuliah K* pada hari ke-h
dh
:
Jumlah sks yang sudah dijadwalkan untuk dosen mata kuliah K* pada hari ke-h
sh*
:
Jumlah sks yang sudah dijadwalkan untuk semester mata kuliah K* pada jurusan mata kuliah K* pada hari ke-h yang optimal
dh*
:
Jumlah sks yang sudah dijadwalkan untuk dosen mata kuliah K* pada hari ke-h yang optimal
null
:
Tidak menunjukkan angka apapun (tidak bernilai)
Sub masalah level 2
Sub masalah level n Gambar 2 Pemecahan permasalahan
Notasi yang digunakan dalam algoritma ini adalah :
<>’-‘
=
n
:
Jumlah mata kuliah yang akan dijadwalkan
i
:
Urutan mata kuliah (i = 1 .. n)
j
:
Jumlah jurusan yang digabung pada mata kuliah ke-i
k
:
Jumlah kelas paralel pada mata kuliah ke-i
yaitu algoritma untuk mata kuliah non
Algoritma ini terdiri dari dua bagian,
A*
:
Jumlah alternatif optimal
gabungan dan algoritma untuk mata kuliah
Ai
:
Jumlah alternatif mata kuliah ke-i
gabungan
Ai1
:
Jumlah alternatif mata kuliah tiap minggu
Ai2
:
Algoritma
penjadwalan
mata
kuliah
Jumlah altenatif mata kuliah pada minggu minggu ganjil dan minggu genap
gabungan
alternatif minimal / mata kuliah Kritis )
T*
:
Maksimal jumlah seluruh alteratif mata kuliah
Ki
:
Mata kuliah ke-i
K*
:
Mata kuliah terkritis (mata kuliah dengan jumlah alternatif minimal )
ji
:
Jadwal kuliah jurusan semester mata kuliah Ki
dan
di
:
Dosen mata kuliah Ki
ri
:
Ruang dengan kapasitas mata kuliah Ki
non
Tahap 1. ( Pencarian mata kuliah dengan jumlah
1.1. Jika masih ada mata kuliah belum terjadwal maka lanjutkan, bila tidak selesai. Set K* = null, A* = 50, Ai1 = 0, Ai2 = 0, i = 0, h = 0, w = 0; m = 0; 1.2. i = i + 1. jika (Sks Ki = 3 dan Ai1
h
:
Hari kuliah (h = 1 .. 5)
maka (Ai1 = Ai2-1). jika A*> Ai1 maka
h*
:
Hari kuliah optimal
(A* = Ai1, K* = Ki). Set Ai1= 0, Ai2= 0.
w
:
Jam kuliah (w = 1 .. 4)
jika i = (n+1) maka lanjutkan ke
w*
:
Jam kuliah optimal
m
:
Minggu kuliah (m = 1 .. 2)
m*
:
Minggu kuliah optimal
Shwm
:
Status jadwal jurusan-semester pada hari ke-h, jam ke-w dan minggu ke-m untuk mata kuliah K*
langkah 2. 1.3. h = h + 1 jika h = 6 maka (h = 0, kembali ke langkah 1.2) 1.4. w = w + 1 jika w = 5 maka (w = 0, kembali ke langkah 1.3)
1.5. m = m + 1 jika m = 3 maka (m = 0, kembali ke langkah 1.4) 1.6. Jika jam kuliah hwm (ji dan di dan ri)
(T* = T, A* = A, h* = h, w* = w, m* = m, sh* = sh+1, dh* = dh + 1), kembali ke langkah 2.7
status = menganggur maka Ai1 = Ai1+1.
Tahap ke 3. (Memasukkan mata kuliah
jika pada minggu 1 dan minggu 2 status
pilihan pada waktu optimal)
= menganggur maka Ai2 = Ai2 + 2.
3.1. Jika sks K* = 2 maka update status
Kembali ke langkah 1.5. Tahap 2. (Mencari waktu yang memberikan total alternatif mata kuliah dan jumlah minimal alternatif mata kuliah terbesar) 2.1. Keluarkan K* dari daftar mata kuliah 2.2. Hitung sh dan dh
dosen, status ruang, dan status jurusan semester mata kuliah K* pada minggu 1, hari h*, jam w* = K* dan minggu 2, hari h*, jam w* = K* 3.2. Jika sks K* = 1 maka update status dosen, status ruang, dan status jurusansemester mata kuliah K* pada minggu m*, hari h*, jam w* = K*
2.3. Set i = 0, h = 0, w = 0, m = 0, A* = 0, T*= 0, h* = null, w*= null, m* = null. 2.4. i = i + 1, jika i = n dan A* = 0 maka ke simpan K* dalam tabel mata kuliah tak terjadwal, kembali ke tahap 1, jika i = n dan A*<>0 maka ke tahap 3. 2.5. h = h + 1, jika h = 6 maka (h = 0, kembali ke langkah 2.4) 2.6. w = w + 1, jika w = 5 maka (w = 0, kembali ke langkah 2.5) 2.7. m = m + 1, T=0, A=0,jika m = 3 maka (m = 0, kembali ke langkah 2.6) 2.8. Jika jadwal semester sebelumnya <>’-‘ maka A= -1, T=-1 2.9. Jika jadwal semester sesudahnya <>’-‘ maka A= A-1; T= T-1 2.10. Jika jadwal semester sebelumnya =‘-‘ dan jadwal semester sesudahnya = ‘-‘ maka Hitung A dan T 2.11. jika A* < A maka (T* = T, A* = A, h* = h, w* = w, m* = m, sh* = sh+1, dh* = dh + 1), jika (A* < A dan T* < T) maka (T* = T, A* = A, h* = h, w* = w, m* = m, sh* = sh+1, dh* = dh + 1),
3.3. Kembali ke tahap 1: Algoritma penjadwalan mata kuliah gabungan Tahap 1. ( Pencarian mata kuliah dengan jumlah alternatif minimal ) 1.1. Jika masih ada mata kuliah belum terjadwal maka lanjutkan, bila tidak selesai. Set K* = null, A* = 50, Ai1 = 0, Ai2 = 0, i = 0, h = 0, w = 0, m = 0, 1.2. i = i + 1. jika (Sks Ki = 3 dan Ai1 Ai1 maka (A* = Ai1, K* = Ki). Set Ai1= 0, Ai2= 0. jika i = (n+1) maka lanjutkan ke langkah 2. 1.3. h = h + 1 jika h = 6 maka (h = 0, kembali ke langkah 1.2) 1.4. w = w + 1 jika w = 5 maka (w = 0, kembali ke langkah 1.3) 1.5. m = m + 1 jika m = 3 maka (m = 0, kembali ke langkah 1.4) 1.6. Jika (ji ,di dan ri untuk seluruh jurusan yang digabung) status = menganggur maka Ai1 = Ai1+1. Jika (ji ,di dan ri untuk
jika (A* < A dan T* < Tdan sh* > sh +
seluruh jurusan yang digabung) pada
1) maka (T* = T, A* = A, h* = h, w* =
m=1 dan m=2 satatus = menganggur
w, m* = m, sh* = sh+1, dh* = dh + 1),
maka Ai2 = Ai2 + 1. Kembali ke langkah
jika (A* < A dan T* < T dan sh* > sh+1
1.5.
dan dh* > dh + 1) maka
Tahap 2. (mencari waktu yang memberikan total alternatif mata kuliah dan jumlah minimal alternatif mata kuliah terbesar)
Tahap ke 3. (memasukan mata kuliah pilihan pada waktu optimal) 3.1. Jika sks K* = 2 maka update status dosen, status ruang mata kuliah K* pada minggu 1, hari h*, jam w* = K*
2.1. Keluarkan K* dari daftar mata kuliah
dan minggu 2, hari h*, jam w* = K*,
2.2. Untuk Seluruh jurusan yang digabung
update status seluruh jurusan-semester
hitung :
yang digabung pada mata kuliah K*
2.3. Hitung nilai sh dan dh
pada minggu 1, hari h*, jam w* = K*
2.4. Set i = 0, A* = 0, T* = 0, h* = null, w*
dan minggu 2, hari h*, jam w* = K*.
= null, m* = null, w = 0, m = 0. 3.2. Jika sks K* = 1 maka update status 2.5. Set h = 0, i = i + 1, jika i = n dan A* =
dosen dan status ruang mata kuliah K*
0 maka ke simpan K* dalam tabel mata
pada minggu m*, hari h*, jam w* = K*,
kuliah tak terjadwal, kembali ke tahap
update status seluruh jurusan-semester
1, jika i = n dan A*<>0 maka ke tahap
yang digabung pada mata kuliah K*
3. 2.6. h = h + 1, jika h = 6 maka (j = 0,
pada minggu m*, hari h*, jam w* = K*. 3.3. Kembali ke tahap 1
kembali ke langkah 2.5) 2.7. w = w + 1, jika w = 5 maka (w = 0, kembali ke langkah 2.6)
Mata kuliah dengan ruang lebih dari satu dilakukan
dengan
mencari
ruang
status
=
menganggur sebanyak yang dibutuhkan pada 2.8. m = m + 1, A=0, T=0, jika m = 3 maka (m = 0, kembali ke langkah 2.7) 2.9. Jika jadwal semester sebelumnya <>’-‘
langkah 1.6 dan hitung A dan T. Pada tahap ke-3 dilakukan update terhadap seluruh ruangan yang dipilih dan dosen yang mengajar.
maka A= -1, T=-1 Mata kuliah yang lain (ruangan 1 dan tidak
2.10. Jika jadwal semester sesudahnya <>’-‘ maka A= A-1; T= T-1 2.11. Jika jadwal semester sebelumnya =‘-‘
digabung) dijadwalkan seperti alur algoritma pertama.
dan jadwal semester sesudahnya = ‘-‘ maka Hitung A dan T
Analisa Algoritma Apabila jumlah sks mata kuliah satu
2.12. Jika A* < A maka (T* = T, A* = A, h* = h, w* = w, m* = m, sh* = sh+1, dh* = dh + 1), jika (A* < A dan T* < T) maka (T* = T, A* = A, h* = h, w* = w, m* = m, sh* = sh+1, dh* = dh + 1),
semester pada satu jurusan yang akan dijadwalkan lebih besar dari jumlah sks dalam satu minggu, maka akan ada beberapa sks mata kuliah yang tidak terjadwal. Hal ini disebabkan algoritma tidak mengijinkan adanya jadwal bersamaan dalam satu semester pada jurusan yang sama.
jika (A* < A dan T* < T dan sh* > sh Beberapa jurusan menggabungkan mata
+ 1) maka (T* = T, A* = A , h* = h, w* = w, m* = m. sh* = sh+1, dh* = dh + 1), jika (A* < A dan T* < T dan sh* > sh+1 dan dh* > dh + 1) maka
kuliah kedalam satu lokal untuk mata kuliah umum (antara
lain
Pancasila,
Kewiraan,
Bahasa
Indonesia). Dalam algoritma yang dirancang, mata kuliah yang digabungkan harus dijadwalkan lebih dahulu sebelum mata kuliah yang lain. Aturan ini
(T* = T, A* = A, h* = h, w* = w, m*
diambil karena untuk menjadwalkan mata kuliah
= m, sh* = sh+1, dh* = dh + 1), kembali
yang digabungkan memerlukan kesiapan seluruh
ke langkah 2.8
jurusan (status menganggur), sehingga akan sukar
Agustina. Ira Lia, (2005)
mencari jadwal menganggur seluruh jurusan apabila
Penjadwalan Pelajaran
mata kuliah lain telah dijadwalkan.
SMU Negeri Mojoagung dengan Algoritma, Tugas Akhir ITS, Surabaya,
KESIMPULAN DAN SARAN H. Akeba, M. Hifib, and R. MHallah. A
Kesimpulan Berdasarkan hasil yang diperoleh dari perancangan algoritma penjadwalan kuliah, dapat
1. Perancangan algoritma penjadwalan kuliah ini untuk
programmer
membantu
seorang
pembuatan
program
dalam
penjadwalan, sehingga menghasilkan program penjadwalan yang akan memperolah hasil yang optimal dalam perkuliahan khususnya di Fakultas
Teknik
dan
Fakultas
Ekonomi
Universitas Graha Nusantara. 2. Entiti
yang
terkait
dalam
perancangan
algoritma ini adalah, Ruangan, Dosen, Waktu Perkuliahan , mata kuliah dan jumlah SKS per mata kuliah. Saran Perlu dilakukan penelitian lebih lanjut tentang
algoritma
ini
karena
penulis
hanya
melakukan perancangan Algoritma berdasarkan permasalahan penjadwalan matakuliah di Kampus III Universitas Graha Nusantara. dan algoritma ini harus diuji dengan pembuatan program dengan menggunakan
algoritma
packing Research
diambil beberapa kesimpulan
ditujukan
(2009).beam search algorithm for the circular
ini,
sehingga
bisa
mendapatkan hasil optimal dan analisa mendalam terhadap hasil yang diperoleh dari perancangan algoritma penjadwalan ini.
DAFTAR PUSTAKA Baker,K.R. ,(1974), Introduction to Sequencing and Scheduling, John Wileyand Sons, New York.
Morton , T.E dan Pentic o, D.W., (1 993)
J. M. S. Valente and R. A. F. S. Alves. (2005) Filtered and recovering beam search algorithms for the early/tardy scheduling problem with no idle time. Computers & Industrial Engineering
problem.
Computers
&
Operations
