Jurnal Shandy :

APLIKASI PENERAPAN TEKNIK PEWARNAAN GRAF PADA PENJADWALAN MATA KULIAH BERBASIS WEB

(Studi Kasus Fakultas Ilmu Komputer Universitas Kuningan)

Shandy Sukma Gayunalapraya⁽¹⁾

NIM : 20080810660

Fahmi Yusuf⁽²⁾, Agus Wahyudin⁽³⁾

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. G₁ 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. G₂ pada gambar 2.1 adalah graf ganda. Graf semu adalah graf yang mengandung gelang. G₃ 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, G₁ mempunyai n = 4, m = 4, sedangkan G₂ 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, v_j bertetangga dengan v_k jika ( v_j , v_k ) adalah sebuah sisi pada graf G.

b. Bersisian (Incident)

Untuk sembarang sisi e = ( v_j , v_k ), sisi e dikatatakan bersisian dengan titik v_j dan titik v_k .

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 N_n , 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 v_i dan v_j di dalam himpunan V terdapat lintasan dari v_i ke v_j (yang juga harus berarti ada lintasan dari v_i ke v_j). 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.