Jurnal Shandy :
APLIKASI PENERAPAN TEKNIK PEWARNAAN GRAF PADA PENJADWALAN MATA
KULIAH BERBASIS WEB
(Studi
Kasus Fakultas Ilmu Komputer Universitas Kuningan)
Shandy Sukma Gayunalapraya(1)
NIM
: 20080810660
Fahmi
Yusuf(2), Agus Wahyudin(3)
ABSTRACT
The allocation of classroom and time is the process of
lecture scheduling at a university and the expected result is optimally
arranged to avoid the clash with certain condition and requirement. In
determining counting based scheduling, we can use some methods. One of them is
colouring graph method. It is the simplest method and it can be used to
determine complicated sceduling process. In this research, the writer tries to
develop method of Coloring Graph to make
optimal lecture scheduling by deciding various problems. The developing of this
method is tried out at the Faculty of Computer Sciences Kuningan University.
Keywords: allocation of classroom and
time, coloring graph
I. PENDAHULUAN
Penjadwalan adalah pengaturan waktu dan tempat dari suatu kegiatan operasi. Penjadwalan
mencakup kegiatan mengalokasikan fasilitas, peralatan ataupun tenaga kerja bagi
suatu kegiatan operasi dan menetukan urutan pelaksanaan kegiatan operasi. Dalam
hirarki pengambilan keputusan, penjadwalan
merupakan langkah terakhir sebelum dimulainya operasi. Penjadwalan yang
menyeluruh menjabarkan perencanaan kapasitas dan jadwal induk ke dalam
perencanaan jangka pendek yang meliputi penugasan khusus untuk tenaga kerja, bahan, dan mesin.
(1) Penulis
(2) Pembimbing I
(3) Pembimbing II
Permasalahan
penjadwalan kuliah terkait
erat dengan masalah optimasi. Oleh
karena itu, pengembangan sistem
penjadwalan kuliah dilakukan
dengan melalui beberapa iterasi perbaikan. Fungsi dan tujuannya adalah memenuhi sejumlah
constraint penjadwalan, seperti
menghindari terjadinya bentrok jadwal.
Berdasarkan
pemikiran diatas maka diperlukan adanya metode yang dapat menyelesaikan
permasalahan, salah satunya adalah dengan memberikan pewarnaan pada penjadwalan
mata kuliah. Oleh karena itu penulis mengambil judul skripsi “Aplikasi
Penerapan Teknik Pewarnaan Graf Pada Penjadwalan Matakuliah Berbasis Web (Studi
Kasus Fakultas Ilmu Komputer)”.
II. LANDASAN TEORI
2.1. Teori Graf
2.1.1 Definisi Graf
Definisi graf menurut Robin J.Wilson dan
John J. Watkins (1992:7 dan 9), graf adalah diagram yang terdiri dari
noktah-noktah yang disebut titik dan dihubungkan oleh garis-garis yang disebut
sisi, serta setiap sisi menghubungkan tepat dua titik.
Secara geometri graf digambarkan sebagai sekumpulan
noktah (titik) di dalam bidang dwimatra yang dihubungkan dengan sekumpulan
garis (sisi).
2.1.2 Jenis-Jenis Graf
Graf dapat dikelompokkan menjadi beberapa
kategori (jenis) bergantung pada sudut pandang pengelompokannya. Pengelompokan
graf dapat dipandang berdasarkan ada tidaknya sisi ganda atau sisi kalang.
Berdasarkan jumlah titik, atau berdasarkan orientasi arah pada sisi (Munir,
2003:293).
Berdasarkan ada tidaknya gelang atau sisi
ganda pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua
jenis:
1. Graf Sederhana (Simple Graph).
Graf yang tidak mengandung gelang maupun
sisi ganda dinamakan graf sederhana. G1 pada gambar 2.1
adalah contoh graf sederhana. Adapun graf sederhana khusus, yaitu:
2. Graf Tak Sederhana (Unsimple Graph).
Graf yang mengandung sisi ganda atau gelang
dinamakan graf tak sederhana (Unsimple Graph). Ada dua macam graf tak
sederhana, yaitu Graf Ganda (multigraph) dan Graf Semu (Pseudograph).
Graf ganda adalah graf yang mengandung sisi ganda. Sisi ganda yang
menghubungkan sepasang titik dapat lebih dari dua. G2 pada
gambar 2.1 adalah graf ganda. Graf semu adalah graf yang mengandung gelang. G3
adalah graf semu (termasuk bila memiliki sisi ganda sekalipun). Graf semu
lebih umum daripada graf ganda, karena sisi pada graf dapat terhubung ke
dirinya sendiri.
Jumlah titik pada graf disebut sebagai
kardinalitas graf, dan dinyatakan dengan n = |V|, dan jumlah sisi dinyatakan
dengan m = |E|. Pada gambar 2.1 diatas, G1 mempunyai n =
4, m = 4, sedangkan G2 mempunyai n = 3 dan m = 4. Berdasarkan
jumlah titik pada suatu graf, maka secara umum graf dapat digolongkan menjadi
dua jenis:
2.1.3. Terminologi Dasar
a. Bertetangga (Adjacent)
Dua buah titik pada graf tak berarah G
dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah
sisi. Dengan kata lain, vj bertetangga dengan vk
jika ( vj , vk ) adalah sebuah sisi
pada graf G.
b. Bersisian (Incident)
Untuk sembarang sisi e = ( vj
, vk ), sisi e dikatatakan bersisian dengan
titik vj dan titik vk .
c. Titik Terpencil (Isolated Vertex)
Titik terpencil ialah titik yang tidak mempunyai sisi yang
bersisian dengannya. Dapat juga dinyatakan bahwa titik terpencil adalah titik
yang tidak satupun bertetangga dengan titik-titik lainnya.
d. Graf Kosong (Null Graph atau Empty Graph)
Graf yang himpunan sisinya merupakan
himpunan kosong disebut sebagai Graf Kosong dan ditulis sebagai Nn
, yang dalam hal ini n adalah jumlah titik.
e. Derajat (Degree)
Derajat suatu titik pada graf tak berarah adalah jumlah
sisi yang bersisian dengan titik tersebut.
f. Terhubung (Connected)
Graf tak-berarah G disebut graf
terhubung (Connected Graph) jika
untuk setiap pasang titik vi dan vj di
dalam himpunan V terdapat lintasan dari vi ke vj
(yang juga harus berarti ada lintasan dari vi ke vj).
Jika tidak, maka G disebut graf tak-terhubung (disconnected
graph).
2.1.4. Pewarnaan Graf
Ada tiga macam pewarnaan graf, yaitu
pewarnaan titik, pewarnaan sisi, dan pewarnaan wilayah (region). Dalam hal ini
pembahasan hanya pada pewarnaan titik dan sisi.
2.1.4.1 Pewarnaan Titik
Pewarnaan titik adalah memberi warna pada
titk-titik suatu graf sedemikian sehingga tidak ada dua titik bertetangga
mempunyai warna yang sama. Pemberikan sembarang warna pada titik-titik
diperbolehkan asalkan berbeda dengan titik-titik tetangganya.
2.1.4.2 Pewarnaan Sisi
Sisi-k untuk G adalah pemberian k warna
pada sisi-sisi G sedemikian hingga setiap dua sisi yang bertemu pada
titik yang sama mendapatkan warna berbeda (Watkins dan Wilson, 1992:262). Jika G
memiliki pewarnaan sisi k, maka G dikatakan dapat diwarna sisi k.
Indeks kromatik G dinotasikan dengan X '(G)
adalah bilangan k terkecil sehingga G dapat diwarna sisi-k.
III. METODE PENELITIAN
3.1 Metode Analisis
Didalam proses penjadwalan terdapat
beberapa dokumen yang terlibat. Berikut ini adalah dokumen-dokumen yang
dibutuhkan dalam sistem penjadwalan :
1. KMK ( Kurikulum Mata Kuliah )
Fungsi : KMK merupakan Daftar Mata kuliah
dari setiap semester pada setiap jurusan yang di pakai sebagai acuan dalam
pembuatan jadwal kuliah per semester.
Sumber : Prodi
2. Daftar Dosen
Fungsi : Di gunakan untuk mengetahui
identitas dari setiap Dosen per jurusan yang nantinya akan di pakai dalam
proses pembuatan jadwal kuliah.
Sumber : Dosen
3. Data Jurusan
Fungsi : Untuk mengetahui jurusan yang ada
di Fakultas Ilmu Komputer Universitas Kuningan.
Sumber : Prodi
4. Data Ruang
Fungsi : Untuk mengetahui kelas yang ada
pada setiap jurusan.
Sumber : Prodi
5. Nama Dokumen : JK ( Jadwal Kuliah )
Fungsi : Untuk mengetahui jadwal kuliah
setiap jurusan , setiap kelas dan setiap dosen.
Sumber : Tata Usaha ( TU )
3.2 Metode Pewarnaan Graf
Salah satu aplikasi
penerapan pewarnaan graf dalam
kehidupan sehari-hari adalah dalam penyusunan sebuah
jadwal. Sebuah jadwal yang ada mula-mula
dipetakan menjadi bentuk graf
terlebih dahulu. Proses pewarnaan graf ini nantinya akan dilakukan pada graf yang terbentuk. Pemetaan dilakukan
dengan mengasumsikan bahwa setiap
jadwal adalah sebuah vertex (simpul) dan urutan jadwal atau dua jadwal
yang tidak bisa diadakan bersamaan dipetakan dengan
membuat
edge(sisi) antara
dua
titik
tersebut. Untuk
kapasitas
ruang
yang ada
akan dimodelkan dengan batasan jumlah warna sama
yang
bisa
digunakan
untuk mewarnai simpul.
Setelah
proses pewarnaan
graf
telah
selesai, setiap simpul pada graf hasil pewarnaan tersebut
akan
memiliki warna sama yang berbeda-beda. Dari warna- warna tersebut akan diketahui bahwa simpul
dengan warna
yang
sama bisa dijadwalkan bersamaan sedangkan untuk simpul dengan warna yang berlainan harus
dijadwalkan berbeda. Jumlah warna yang digunakan menunjukkan banyaknya jadwal yang harus disusun dalam melakukan penyusunan jadwal.
3.3 Metode Perancangan
3.3.1 Flowchart
(Flowchart Input) (Flowchart prosedur
coloring)
3.3.2 DFD
3.3.2.1 Diagram konteks
3.3.2.2 DFD Level 0
IV. HASIL DAN PEMBAHASAN
4.1 Implementasi
Implementasi
yang dilakukan antara lain adalah menerapkan perancangan antarmuka ke dalam
bentuk halaman web, perancangan struktur data kedalam bentuk tabel database,
pembuatan kode program dan sebagainya.
4.2 Pengujian
Pengujian merupakan hal yang tidak dapat dihindari dalam proses perancangan
maupun pengembangan sistem. Pada saat aplikasi dijalankan, mungkin akan
menemukan error atau aplikasi tidak berjalan sebagaimana yang diharapkan.
Hasil Pengujian White Box
Pengujian
white box berfokus pada struktural kontrol program. Test case dilakukan untuk
memastikan bahwa semua statement pada program telah dieksekusi paling tidak
satu kali selama pengujian dan bahwa kondisi logis telah diuji. Dengan metode
ini analisa bisa memperoleh test case sebagai berikut :
1.
Menjamin
semua independent path (jalur bebas) telah dijalankan minimal satu kali.
2.
Melakukan
struktural data internal untuk menjamin validitas
Berikut ini adalah bentuk
pengujian white box.
function save($values)
{
$sql=mysql_query("insert into
$_GET[tab] values $values");
$link=$_GET['tab'];
$ext=".php";
$page="$link$ext";
if($sql>0)
{
echo"<a
href=\"javascript:page('$page')\"><br>Data Berhasil
Disimpan..<br><br></a>";
}
else
{
echo"<a
href=\"javascript:page('$page')\"><br>Ada Duplikasi
Data<br><br></a>";
}
}
V. KESIMPULAN DAN SARAN
5.1
Kesimpulan
Adapun kesimpulan yang diperoleh
dari hasil penelitian yang telah dilakukan adalah sebagai berikut :
1.
Sistem
yang dibuat memberikan kemudahan terhadap proses pengelolaan jadwal mata kuliah sehingga lebih efektif dan efisien di
Fakultas Ilmu Komputer Universitas Kuningan.
2.
Sistem
yang dibuat mampu memberikan dapat meminimalkan kesalahan terjadinya duplikasi jadwal
yang ada serta terjadinya bentrokan jadwal.
3.
Sistem
dapat melakukan simulasi penjadwalan menggunakan graph coloring sehingga dapat
dibuatkan dalam bentuk graph.
4.
Sistem
yang dibuat memudahkan didalam pengelolaan laporan jadwal.
5.2 Saran
Setelah penulis mengadakan penelitian, maka ada beberapa saran yang ingin
penulis kemukakan agar sistem berjalan maksimal, antara lain:
1.
Untuk
mengoperasikan program aplikasi ini, diperlukan adanya pelatihan khusus
terlebih dahulu
terhadap user.
2.
Untuk
menghasilkan program aplikasi yang baik, diperlukan ketelitian dalam
penelitian, perancangan, dan pengkodean.
3.
Data
yang telah terkomputerisasi diharapkan merupakan data yang up to date.
4.
Pengisian
data untuk semua format masukan harus dilakukan dengan teliti sehingga informasi
yang dihasilkan sesuai dengan yang diharapkan.
5.
Dalam
pembuatan aplikasi ini masih banyak sekali kekurangan, oleh karena itu diperlukan adanya pengembangan yang lebih
lanjut.
DAFTAR PUSTAKA
1.
Al-Audah, Sulaiman Bin Hamid. 2003. Bagaimana Muslimah Memanfaatkan
Waktu. Jakarta: Gema Insani.
2. Lipschutz, Seymour dan Lipson,
Marc Lars (diterjemahkan oleh Tim Editor Penerbit Salemba Teknika). Matematika
Diskrit 2. Jakarta: Salemba Teknika.
3.
Munawwir, Ahmad Warson. 2002. Kamus Al-Munawwir Arab-Indonesia
Terlengkap. Surabaya: Pustaka Progressif.
4.
Munir, Rinaldi. 2003. Matematika Diskrit. Bandung: Murty dan Bondy.
1976. Graph Theory with Applications. Canada: The Macmillan Press LTD
5.
Poerwadarmita. 1976. Kamus Umum Bahasa Indonesia. Jakarta: PN Balai Pustaka.
6.
Qardhawi, Yusuf. 2007. Time is Up! Manajemen Waktu Islami. Yogyakarta:
Qudsi Media.
7.
Wilson, Robin J dan Watkins, John J (diterjemahkan oleh Dra. Theresia MH
Tirta Seputro, M.Pd). 1990. Graph An Introductory Approach. Canada:
Wiley.
8.
Low, Ricard M and Lee, SinMin. 2004. On the IntegerMagic Spectra Of
9.
Wilson, Robin J dan Watkins John J. 1989. Graphs: An Introductory approach: A
First Course in Discrete Mathematics. Canada: John Wiley and Sons, Inc.