Prosiding
ISSN :9 772407 749004
Algoritma Penjadwalan Perkuliahan dengan Kasus Team Teaching dengan Metode Vertex Coloring Graph Nelly Oktavia Adiwijayaa, Slaminb Program Studi Sistem Informasi Universitas Jember Jl. Kalimantan 37 Jember,
[email protected] b Program Studi Sistem Informasi Universitas Jember Jl. Kalimantan 37 Jember,
[email protected] a
ABSTRAK Permasalahan mengenai penjadwalan matakuliah di universitas (UCTP) memerlukan cara yang efektif dan efisien untuk menyelesaikannya agar didapat hasil yang optimal sesuai dengan kebutuhan. Penelitian ini akan menyelesaikan permasalahan penjadwalan yang cukup kompleks yaitu tentang penjadwalan pelaksanaan perkuliahan dengan kasus setiap matakuliah diampu oleh team teaching (2 orang atau lebih). Permasalahan yang terjadi adalah sering adanya benturan jadwal dikarenakan salah satu pengajar dari setiap matakuliah mengampu dua atau lebih mata kuliah yang berbeda dalam satu waktu yang sama. Metode yang digunakan untuk menyelesaikan permasalahan ini adalah teknik pewarnaan titik pada graf. Metode ini dapat menghasilkan jumlah jumlah warna seminimal mungkin. Hasil pewarnaan titik ini yang akan menjadi dasar pembagian waktu pada jadwal perkuliahan agar tidak terjadi benturan pada setiap pengajar. Hasil dari penelitian ini berupa algoritma yang bersifat lebih umum untuk digunakan baik untuk kasus team teaching sekaligus pengampu tunggal serta algoritma yang dihasilkan siap diterjemahkan ke dalam program untuk dikembangkan menjadi sebuah aplikasi system penjadwalan.
Kata Kunci : vertex coloring graph, team teaching, penjadwalan matakuliah universitas, algoritma
diselesaikan dengan karakteristik proses
Pendahuluan Permasalahan penjadwalan telah banyak
dibahas
Beberapa
dalam
penelitian.
diantaranya
adalah
produksi beragam (Azmi & dkk, 2012). Permasalahan
penjadwalan
matakuliah di Universitas (University
penjadwalan dalam produksi yang dapat
Course
menentukan jadwal produksi dengan
menjadi
tepat (Santoso, Guntara, & Sandjaja,
habisnya dibahas hal ini disebabkan
2012), juga penjadwalan pesanan yang
perbedaan struktur keseluruhan jadwal
terintegrasi dengan proses manajemen
yang dibutuhkan masing-masing kasus
pemesanan
berbeda.
perusahaan
yang
dapat
memperkirakan kapan pesanan dapat
Timetabling topik
yang
Berbagai
Problem)
juga
seolah
tiada
metode
dicoba
diterapkan guna mendapatkan hasil yang optimal dan sesuai dengan syarat
Seminar Nasional Pendidikan Matematika Ahmad Dahlan (SENDIKMAD 2014) Yogyakarta, 27 Desember 2014
1458
Prosiding
ISSN :9 772407 749004
atau constraint yang ada. Syarat utama
particle
dalam
constraint
permasalahan
menghindari
UCTP
terjadinya
adalah
swarm
optimization
based
dan
reasoning,
bentrokan
menggunakan recursive largest first
jadwal, yang biasanya dijadikan sebagai
algorithm‖ (Thio & Hiryanto, 2013) dan
hard constraint. Salah satunya adalah
penggabungan
penggunaan metode algoritma genetika
Simulated
yang dalam optimasi penjadwalannya
lanjutannya(Mariana
melalui beberapa tahap yaitu seleksi,
2013). Namun pada penelitian tersebut
crossover,
tingkat
dan
mutasi
(Yunantara,
dengan
Annealing
derajat
metode
pada &
pada
proses
Hiryanto,
graf
yang
Astawa, & Sanjaya, 2012). Teknik
digunakan telah ditentukan sebagai
hibridisasi dalam bee colony algorithm
masukan.
Padahal
(ABC) baru-baru ini juga telah dicoba
kegunaan
dari
penerapan
diterapkan pada permasalahan UCTP
algoritma
yang
dapat
untuk
kelemahan
pekerjaan manual menjadi otomatis.
yang banyak terjadi dalam proses
Sehingga data yang menjadi masukan
pencariannya
benar-benar
menyempurnakan
(Fong,
Asmuni,
McCollum, & McMullan, 2014).
misalnya
Salah satu metode yang dinilai terbukti mampu menghasilkan solusi jadwal cepat adalah penerapan metode Vertex Graph Coloring. Metode ini juga banyak
dilakukan,
disitulah
berupa
dosen
bekerja sepenuhnya dalam program yang dibuat berdasar algoritma tersebut.
menggabungkan bersama metode lain
mengangkat
untuk
dengan menerapkan
proses
dan
Vertex Graph Coloring yang akan
Pada
hasil
mentah
pengampu saja. Selanjutnya Algoritma
dengan
melanjutkan
suatu
membantu
data
matakuliah
letak
penelitian
ini
permasalahan
juga UCTP
metode vertex
pewarnaannya karena dianggap metode
Graph Coloring. Constraint tambahan
ini masih mempunyai kecenderungan
dalam penelitian ini adalah dosen
terjadi
soft
pengampu matakuliah tidak tunggal
constraint seperti hasil jadwal yang
melainkan setiap matakuliah diampu
melebihi kuota ruang yang tersedia.
oleh beberapa dosen (team teaching).
Contoh
pada
Hal ini menambah tingkat kompleksitas
beberapa penelitian yang menggunakan
proses pewarnaan yang akan dilakukan.
teknik pewarnaan titik pada graf adalah
Jika
Implementasi Vertex graph coloring,
dosen
pelanggaran
kombinasi
terhadap
metode
biasanya tunggal
permasalahan melekat
di
UCTP setiap
Seminar Nasional Pendidikan Matematika Ahmad Dahlan (SENDIKMAD 2014) Yogyakarta, 27 Desember 2014
1459
Prosiding
ISSN :9 772407 749004
matakuliah, maka dalam permasalahan
merupakan bagian dari V ke subset k
kali ini tidak hanya satu dosen saja yang
Ci, i=1…k, sehingga tidak ada simpul
dipertimbangkan di setiap matakuliah,
yang berdekatan dimiliki subset yang
melainkan beberapa dosen lain yang
sama. Masalah optimasi pewarnaan k
menjadi anggota team teaching juga
adalah untuk menemukan warna k pada
harus menjadi Hard constraint.
G dengan k sekecil mungkin. K terkecil
Tujuan dari penelitian ini adalah untuk mendapatkan solusi penjadwalan matakuliah
universitas
dengan
constraint team teaching menggunakan metode vertex graph coloring yang dapat
mengatasi
masalah
benturan
ini sesuai dengan jumlah kromatik dari graf G. Sebuah pewarnaan k-simpul dari sembarang
graf
adalah
sebuah
penugasan dari k-warna 1,2,3,…k ke simpul dari G (Pal, Ray, Zakaria, & Sarma, 2012).
jadwal pada dosen pengampu. Yaitu
Dalam permasalahan ini Vertex
dengan menempatkan warna yang sama
Graph Coloring menjadi penting karena
pada ruang yang berbeda dengan waktu
kemampuan untuk mewarnai sebuah
yang sama atau sebaliknya pada ruang
graf dengan jumlah warna seminimal
yang sama dengan waktu yang berbeda.
mungkin memiliki pengaruh langsung
Untuk
harus
pada seberapa efisien masalah sasaran
menempati ruang dan waktu yang
dapat diselesaikan. Gambar 1- gambar 4
berbeda.
menyajikan
warna
yang
berbeda
graf
penjadwalan
yang dihasilkan dari analisis penelitian
Hasil dan Pembahasan Sebuah
algoritma
ini menggunakan metode vertex graph linier
(graf
coloring dengan kasus team teaching.
sederhana) G = (V,E) terdiri dari satu set objek V = {v1, v2, v3, …} disebut sebagai simpul di G, dan satu set E = {e1, e2, e3, …} disebut sebagai sisi di G sedemikian hingga setiap sisi dapat diidentifikasikan
dengan
pasangan
terurut simpul (vi, vj). Pewarnaan graf sederhana,
simetris
dan
terhubung
secara tepat adalah masalah klasik dari teori graf. Sebuah warna k dari G Seminar Nasional Pendidikan Matematika Ahmad Dahlan (SENDIKMAD 2014) Yogyakarta, 27 Desember 2014
1460
Prosiding
ISSN :9 772407 749004
Gambar.1 Bagian penentuan tetangga Gambar 1 merupakan alur untuk tahap
Gambar 2. Bagian pembuatan matriks
pertama yaitu pembuatan matriks (Mx)
derajat dan pengurutannya
hubungan antar matakuliah (MKb dan MKk) yang masing-masing mempunyai dosen pengampu team teaching (DSb dan DSk). Matriks akan diberi nilai 1 jika terdapat dosen yang sama, jika tidak diberi nilai 0. Dalam hal ini artinya
terdapat
matakuliah.
Pada
sisi
antar
bagian
ini
simpul pula
sekaligus dihitung jumlah derajat (Der) pada masing-masing matakuliah.
Seminar Nasional Pendidikan Matematika Ahmad Dahlan (SENDIKMAD 2014) Yogyakarta, 27 Desember 2014
1461
Prosiding
ISSN :9 772407 749004 selanjutnya yaitu proses pengurutan matrik derajat (Mder) mulai dari nilai yang terbesar. Matriks
derajat ini
berikutnya akan digunakan sebagai acuan urutan pewarnaan pada bagian proses pewarnaan pada gambar 4. Untuk dapat mewarnai setiap simpul, derajat harus tentang
dari
masing-masing
memiliki indeks
atribut
simpul
(informasi)
matakuliah
yang
bersesuaian.
Gambar 3. Bagian pembuatan matriks indexGambar 2 adalah tahap Gambar 4. Bagian Pewarnaan Seminar Nasional Pendidikan Matematika Ahmad Dahlan (SENDIKMAD 2014) Yogyakarta, 27 Desember 2014
1462
Prosiding
ISSN :9 772407 749004
Pemberian
informasi
indeks
Dari
algoritma
keseluruhan
matakuliah (IdxDer) yang bersesuaian
dapat dilihat bahwa algoritma ini hanya
dilakukan pada tahap berikutnya yaitu
membutuhkan masukan berupa data
pada gambar 3. Disini bagian paling
mentah berupa daftar matakuliah dan
rumit dalam pengembangan algoritma
daftar dosen.
ini yaitu saat pembuatan matriks yang
matakuliah tidak dimasukkan secara
berisi index matakuliah pada matriks
manual
derajat. Kesulitannya adalah ketika
proses dalam algoritma di atas. Jika
algoritma dibuat untuk menghadapi data
diterapkan
derajat dengan nilai yang sama. Hal ini
simpul ini akan termasuk hal yang
diperhitungkan karena dianggap akan
dikerjakan secara otomatis. Hal ini
sangat
diasumsikan bahwa pembuat jadwal
jarang
terjadi
nilai
derajat
berbeda semua nilainya. Setelah derajat
didapatkan
beserta
matakuliah
tidak
informasi
yang
matriks index
bersesuaian,
berikutnya tahap pewarnaan dilakukan seperti pada gambar 4. Pada tahap ini simpul pertama otomatis diberi warna (color) pertama. Berikutnya pemberian warna ditentukan berdasarkan aturan Vertex Graph Coloring yaitu dari derajat yang terbesar dilihat status ketetanggaannya juga dilihat nomor warna yang digunakan, sehingga disini tampak beberapa kali pengecekan guna
Kemudian seluruh nomor warna itu akan disimpan dalam sebuah matriks pewarnaan matakuliah.
(vColor)
untuk
setiap
melainkan
dalam
harus
mencari
derajat simpul
didapatkan
program
memahami
derajat
melakukan
dari
derajat
bagaimana
simpul
pewarnaan.
Hasil
untuk dari
penelitian ini dapat digunakan secara lebih general tidak hanya untuk kasus team teaching tapi juga sekaligus dapat mengatasi untuk kasus dosen tunggal. Hasil dari penelitian ini juga dapat dilanjutkan
kemudian
untuk
menentukan jumlah ruang minimal yang dibutuhkan jika asumsi waktu yang tersedia adalah 6 slot setiap hari dalam 5 hari kerja. Kesimpulan
mendapatkan nomor warna seminimal mungkin sesuai teori Pewarnaan graf.
Data
Permasalahan
penjadwalan
matakuliah di universitas (UCTP) dapat diselesaikan dengan penerapan metode vertex graph coloring. Pada penelitian ini diberikan kasus tambahan yaitu dosen
pengampu
matakuliah
tidak
Seminar Nasional Pendidikan Matematika Ahmad Dahlan (SENDIKMAD 2014) Yogyakarta, 27 Desember 2014
1463
Prosiding
ISSN :9 772407 749004
tunggal melainkan team teaching. Hasil
Mariana,
&
Hiryanto,
L.
(2013).
dari penelitian ini dapat digunakan
Program Aplikasi Penjadwalan
secara lebih luas tidak hanya khusus
Kelas
untuk kasus team teaching melainkan
Metode Vertex Graph Coloring
dapat sekaligus untuk menyelesaikan
dan
kasus dosen tunggal.
Jurnal
Penelitian yang akan dilakukan berikutnya adalah pencarian ruang dan waktu
yang
matakuliah
tepat
serta
dengan
peserta
diberikan
soft
Matakuliah
Simulated Ilmu
Dengan
Annealing.
Komputer
dan
Sistem Informasi, vol 1, No. 1, 125-132. Pal, A. J., Ray, B., Zakaria, N., & Sarma,
S.
S.
(2012).
constraint berupa intensitas persebaran
Comparative
jadwal mengajar masing-masing dosen
Modified Simulated Annealing
merata tidak menumpuk di satu hari
with
tertentu.
Annealing for Graph Coloring
Berikutnya
pembangunan
Performance
Simple
of
Simulated
perangkat lunak yang menerapkan hasil
Problem.
dari penelitian ini.
Conference on Computational Science (pp. 321327). Procedia
Pustaka
Computer Science 9 Elsevier
Azmi, N., & dkk. (2012). Penjadwalan Pesanan
Menggunakan
Algoritma Genetika untuk Tipe Produksi Hybrid and Flexible Flowshop
pada
Industri
Kemasan Karton. Jurnal Teknik Industri, 176-188.
B., & McMullan, P. (2014). A New Hybrid Imperialist SwarmBased Optimization Algorithm University
Timetabling
Problems. Information Sciences 283, 1-21.
Ltd. Santoso, L. W., Guntara, J., & Sandjaja, I.
N.
(2012,
September).
Penjadwalan Produksi dengan Menggunakan Simulated
Algoritma
Annealing.
Jurnal
Ilmiah Ilmu Komputer, vol. 9
Fong, C. W., Asmuni, H., McCollum,
for
International
No.1. Thio, J. S., & Hiryanto, L. (2013). Implementasi Colouring,
Particle
Optimization, Based
Vertex
dan
Graph Swarm
Constraint
Reasoning
untuk
University Timetabling Problem
Seminar Nasional Pendidikan Matematika Ahmad Dahlan (SENDIKMAD 2014) Yogyakarta, 27 Desember 2014
1464
Prosiding
ISSN :9 772407 749004
(Studi Kasus: FTI UNTAR).
dan Implementasi Penjadwalan
Jurnal
dengan
Ilmu
Komputer
dan
Menggunakan
Sistem Informasi, Vol. 1, No. 1,
Pengembangan
97-104.
Crossover
Yunantara, M. D., Astawa, I. G., & Sanjaya, N. A. (2012). Analisis
dalam
Model Algoritma
Genetika. Jurnal Elektronik dan Ilmu
Komputer
Universitas
Udayanan, vol. 1, No. 2, 14-23.
Seminar Nasional Pendidikan Matematika Ahmad Dahlan (SENDIKMAD 2014) Yogyakarta, 27 Desember 2014
1465
