## Penerapan Metode Pewarnaan Graf Untuk Penjadwalan Mata Kuliah
Amelia Yusnita 1 , Hanifah Ekawati 2 , Nila Ratna Sari 3
1 Sistem Informasi, STMIK Widya Cipta Dharma, Samarinda, Indonesia
2 Manajemen Informatika, STMIK Widya Cipta Dharma, Samarinda, Indonesia
3 Teknik Informatika, STMIK Widya Cipta Dharma, Samarinda, Indonesia Email: 1 amelia@wicida.ac.id, 2 hanifahekawati.mus88@gmail.com, 3 nila.ratna47@gmail.com

## Abstrak
Penjadwalan  matakuliah  merupakan  agenda  yang  rutin  setiap  semester  dikerjakan  oleh  program  studi,  dalam  proses pembuatannya  sering  mengalami  kesulitan  misalnya  sering  terjadi  bentrok  jadwal  mata  kuliah,  dosen  dan  waktu  yang  lain dalam satu periode jadwal perkuliahan. Metode pewarnaan graf yang digunakan adalah algoritma pewarnaan barisan sederhana pada sisi. Algoritma ini  dapat digunakan dalam pembentukan jadwal agar tidak terjadinya tumpang tindih antara mata kuliah, dosen, ruangan  dan  waktu.  Alat bantu perancangan sistem  yang  digunakan adalah flowchrt . Hasil dari penelitian ini adalah berupa aplikasi yang dibuat secara otomatis tanpa ada bentrok jadwal. Pengguna dapat memasukkan data awal penjadwalan sesuai dengan kebutuhan kemudian aplikasi akan menyusul penjadwalan dengan menggunakan algoritma pewarnaan barisan sederhana pada sisi, dan hasil outputnya akan menampilkan hasil penjadwalan tersebut. pengujian menggunakan black box , pengujian ini akan menguji secara detail dari tombol tambah dan tombol proses, hasil yang diharapkan adalah keberhasilan.
Kata Kunci: Penjadwalan, Metode Pewarnaan Graf

## Abstract
Scheduling courses is a routine agenda every semester carried out by the study program, in the manufacturing process it often experiences difficulties such as frequent clashes between courses, lecturers and other times in one period of the lecture schedule. The graph coloring method used is a simple row coloring algorithm on the side. This algorithm can be used in scheduling so that there is no overlap between courses, lecturers, room and time. The system design tool used is a flowchart. The results of this study are in the form of applications that are made automatically without any conflicting schedules. Users can enter the initial  scheduling  data  according  to  their  needs,  then  the  application  will  follow  scheduling  using  a  simple  line  coloring algorithm on the side, and the output results will display the scheduling results. testing using black box, this test will test in detail the plus button and process button, the expected result is a success
Keywords : Scheduling, Graph Coloring Method

## 1. PENDAHULUAN
Pemanfaatan  sumber  daya  manusia  dalam  sebuah  aplikasi  yang  tepat  dapat  mempermudah  pengguna  untuk menyelesaikan  pekerjaan  dalam  skala  kecil  atau  besar,  pemanfaatan  yang  tepat  akan  sangat  membantu  dalam kelancaran atau kecepatan penyelesaian berbagai macam pekerjaan.
Penjadwalan  merupakan  kegiatan  yang  harus  dimiliki  oleh  setiap  orang,  kegiatan  rutin  yang  tersusun dengan rapi dapat membantu dalam aktivitas sehari-hari. Dalam sebuah Instansi atau lembaga khususnya misalnya STMIK Widya Cipta Dharma, memiliki agenda-agenda yang harus diselesaikan dengan cepat dan tepat, salah satu agendanya adalah jadwal perkuliahan yang dikerjakan oleh program studi. Masalah yang harus dihindari dalam pembuatan jadwal perkuliahan salah satunya adalah pada waktu dan ruangan yang sama terdapat mata kuliah lebih dari satu. Untuk menghindari terjadinya tumpang tindih antara mata kuliah, dosen, ruangan dan waktu. Salah satu metode yang dapat digunakan untuk menyelesaikan permasalahan tersebut adalah dengan menggunakan metode pewarnaan graf dengan algoritma pewarnaan barisan-sederhana pada sisi.
Berdasarkan latar belakan masalah tersebut. Aplikasi yang dibuat dengan penerapan metode pewarnaan graf untuk penjadwalan  mata kuliah, diharapkan dapat mempermudah program  studi dalam  menyusun  jadwal  perkuliahan tiap semesternya.

## 2. TEORITIS
Metode pengumpulan data yang digunakan untuk mengolah informasi dibagi menjadi 2 (dua) yaitu :

## 2.1 Studi Lapangan
Metode yang digunakan dalam studi lapangan adalah:
a. Wawancara,  pengumpulan data dengan melakukan tanya jawab sepihak yang dilakukan secara sistematik dan berlandaskan kepada tujuan penelitian, yaitu dengan mewawancarai beberapa pihak yang terlibat pada proses penjadwalan
b. Observasi,  pengumpulan  data  dengan  cara  melakukan  pengamatan  melalui  kelayakan  terhadap  objek  yang ingin diteliti dan dilakukan dalam situasi khusus.
2.2 Studi Pustaka
Metode  yang  digunakan  untuk  mendapatkan  informasi  adalah  dengan  mempelajari  dari  beberapa  sumber  yang berkaitan dengan judul penelitian sebagai referensi dan dijadikan sebagai bahan perbandingan, adapun referensi yang digunakan sebagai berikut : 1. Kajian Empiris Penelitian tentang pewarnaan graf yang sama telah banyak dilakukan antara lain:
1) Perancangan  Sistem  Penjadualan  Kuliah  di  Jurusan  Teknik  Elektro  Ft.Untrirta  Menggunakan  Teknik Pewarnaan Graph  Algoritma  Backtracking  Welch-Powell .  Pada  penelitian  ini,  menjelaskan  bahwa penjadwalan kuliah menggunakan teori graph, data yang berhubungan dengan jadwal diubah dalam bentuk graph,  kemudian  untuk  mengetahui  banyaknya  warna  untuk  solusi  awal  digunakan  bilangan  khromatik, untuk menyelesaikan masalah pewarnaan graph digunakan algoritma backtracking Welch-Powell [1].
2) Penerapan  Pewarnaan  Simpul  Graf  untuk  Menentukan  Jadwal  Ujian  Skripsi  Pada  STMIK  Amik  Riau Menggunakan  Algoritma Welch-Powell .  Pada  penelitian  ini,  penjadwalan  ujian  skripsi  menggunakan teknik  pewarnaan  simpul  graf  dengan  menggunakan  algoritma Welch-powell ,  hasil  penelitian memperlihatkan bahwa algoritma ini dapat diterapkan dalam pembuatan jadwal skripsi dengan memberikan hasil penjadwalan yang lebih baik dari metode sebelumnya [2].
2. Pewarnaan Graf adalah sebuah metode pelebelan pada sebuah graf. Pelebelan tersebut merupakan pemberuan warna pada simpul, sisi ataupun wilayah ( region ). Dalam pewarnaan pada indeks kromatik atau angka kromatik sisi yang disimbolkan x’ (G) yaitu angka terkecil yang diperlukan untuk pewarnaan sisi graf G [3]. Ada beberapa macam teknik pewarnaan dalam graf yaitu
1) Pewarnaan Simpul, merupakan cara mewarnai simpul-simpul suatu graf sedemikian hingga tidak ada dua simpul  bertetangga  yang  berwarna  sama  dengan  kata  lain  warna  pada  simpul  boleh  sembarang  asalkan berbeda dengan simpul tetangganya
2) Pewarnaan  Sisi,  merupakan  suatu  proses  mewarnai  pada  garis  ( edges )  dengan  warna-warna  tertentu sehingga setiap titik ( vertex ) yang bertemu pada titik ( vertex ) yang sama mempunyai warna yang berbeda. Cara mewarnai sisi k dinamakan pewarnaan sisi k.
3) Pewarnaan Wilayah, merupakan teknik mewarnai masing-masing wilayah graf sehingga tidak ada warna yang sama pada wilayah graf yang bersebelahan.

## 3. ANALISA DAN PEMBAHASAN
Pada tahapan ini proses yang dilakukan untuk pengembangan dan menganalisa adalah :
a. Analisis Data adalah mengenai data apa saja yang akan diproses, baik sebagai masukan maupun keluaran. Data yang di perlukan antara lain :
1) Data  Dosen,  data  yang  berisikan  nama    dosen  yang  mengajar  pada  STMIK  Widya  Cipta  Dharma Samarinda.
2) Data Mata Kuliah, data mata kuliah berisi daftar mata kuliah yang ada pada STMIK Widya Cipta Dharma Samarinda. Daftar mata kuliah untuk prodi teknik informatika, prodi sistem informasi dan mata kuliah yang ada pada manajemen informatika.
3) Data Ruangan, data ruangan berisi daftar ruangan yang ada pada STMIK Widya Cipta Dharma Samarinda. Dimana untuk ruangan yang biasa digunakan untuk prodi teknik informatika adalah ada 5 ruangan yaitu ruang 2, 4/6, 12, 14 dan 15. Untuk prodi sistem  informasi ruangan  yang  biasa digunakan ada 5 ruangan yaitu  ruang  1,  3/5,  11,  16  dan  17.  Sedangkan  untuk  prodi  manajemen  informatika  ruangan  yang  biasa digunakan ada 4 ruangan yaitu ruang 7, 8, 9 dan 10.
4) Data Kelas, data kelas berisi tentang daftar kelas yang ada pada prodi teknik informatika, sistem informasi dan manajemen informatika pada STMIK Widya Cipta Dharma Samarinda.
5) Data Waktu, data waktu berisi tentang waktu-waktu yang digunakan dalam proses mengajar yang dilakukan pada STMIK Widya Cipta Dharma Samarinda. Dimana  untuk mata kuliah 2 sks kelas pagi dimulai pada jam 08.00-11.40, untuk mata kuliah 3 sks pada jam 13.00-15.30. Sedangkan untuk kelas malam, mata kuliah 3 sks ditempatkan pada hari senin dan selasa pada jam 19.00-20.15, sedangkan mata kuliah 2 sks dimulai dari jam 16.30-22.00 tiap harinya kecuali hari senin dan selasa hanya ada pada jam 16.30.
b. Analisis Sistem
Pada  tahap  ini  bertujuan  untuk  memberikan  gambaran  umum  kepada  pemakai  tentang  sistem  teknologi informasi yang baru dengan menggunakan alat bantu perancangannya adalah Flowchart .
Gambar 1 . Flowchat Algoritma Pewarnaan Barisan Sederhana Pada Sisi
Pada gambar 1 merupakan alur flowchart dari sistem penjadwalan pada STMIK Widya Cipta Dharma Samarinda menggunakan metode pewarnaan graf pada sisi. Dimulai dari menginputkan banyaknya sisi yang ada pada graf G dan dilanjutkan pada step-step sebagai berikut : 1. Step 1   : Memberikan label kepada setiap sisi yang ada pada graf G dengan label E 1 , E 2 ,…E n . Dan warna yang disediakan sama dengan banyaknya sisi yang ada pada graf G.
2. Step 2   : i sama dengan banyaknya sisi yang ada pada graf G. Dan C i adalah daftar warna yang disediakan untuk memberikan warna pada graf G.
3. Step 3   : i sama dengan I, I dimulai dari 1 atau sisi 1 (E 1 )
4. Step 4   :  Warna  pertama  yang  disediakan  pada  step  2  (C i ),  maka  warna  tersebut  adalah  warna  yang  akan diberikan pada E i
5. Step 5   : Yang berhubungan langsung dengan sisi yang sedang dieksekusi, maka sisi yang berhubungan tidak dapat menggunakan warna yang sama dengan sisi yang sedang dieksekusi. Dan  i = I + 1. Apabila hasil i lebih dari banyaknya sisi yang ada pada graf G maka lanjut pada step 6, jika kurang atau sama dengan sisi yang ada pada graf G maka kembali melakukan step 4.
6. Step 6   : Membuat tabel hasil pewarnaan sisi pada graf G.

## 4. IMPLEMENTASI
Setelah semua dianalisis, maka tahap selanjutnya adalah implementasi

## 4.1 Proses Pewarnaan Graf
Proses pewarnaan graf antara vertex kelas dan vertex mata kuliah pada kelas dan mata kuliah 2 sks di semester I pada prodi teknik informatika kelas pagi
Pada gambar 2 dijelaskan bahwa : V 1 = PA V 2 = PB A = Agama Islam B = Alpro Dasar C = Bahasa Inggris I D = Fisika E = Bahasa Indonesia
1 = Biru, 2 = Merah, 3 = Hijau, 4 = Ungu, 5 = Hitam, 6 = Orange, 7 = Hitam, 8 = Biru Laut, 9 = Coklat, 10 = Abu- Abu.
Diketahui: E 1 = V 1 – A, E 2 = V 1 – B, E 3 = V 1 – C, E 4 = V 1 – D, E 5 = V 1 – E, E 6 = V 2 – A, E 7 = V 2 – B, E 8 = V 2 - C, E 9 = V 2 – D, E 10 = V 2 – E.
Langkah-langkah penyelesaian : Step 1 : Label warna yang tersedia adalah 1,2,3,4,5,6,7,8,9,10. Step 2 : C 1 ={1}, C 2 ={1,2}, C 3 ={1,2,3}, C 4 ={1,2,3,4}, C 5 ={1,2,3,4,5}, C 6 ={1,2,3,4,5,6} C 7 ={1,2,3,4,5,6,7}, C 8 ={1,2,3,4,5,6,7,8}, C 9 ={1,2,3,4,5,6,7,8,9} C 10 ={1,2,3,4,5,6,7,8,9,10} Step 3 : i = 1 Step 4 : 1 adalah warna pertama di C 1 . Jadi warna sisi E 1 dengan warna 1 Step 5 : sisi yang berhubungan langsung dengan titik yang ada di E 1 adalah E 2 , E 3 , E 4 , E 5 , E 6 . C 2 = {1,2}-{1} = {2} C 3 = {1,2,3}-{1}= {2,3} C 4 = {1,2,3,4}-{1}= {2,3,4} C 5 = {1,2,3,4,5}-{1}= {2,3,4,5} C 6 = {1,2,3,4,5,6}-{1}= {2,3,4,5,6} i = 1+1 = 2 Step 4 : E 2 = 2 Step 5 : sisi yang berhubungan langsung dengan titik yang ada di E 2 adalah E 3 , E 4 , E 5 , E 7 . C 3 = {2,3}-{2} = {3} C 4 = {2,3,4}-{2}= {3,4} C 5 = {2,3,4,5}-{2}= {3,4,5} C 7 = {1,2,3,4,5,6,7}-{2}= {1,3,4,5,6,7} i = 2+1 = 3 Step 4 : E 3 = 3 Step 5 : sisi yang berhubungan langsung dengan titik yang ada di E 3 adalah E 4 , E 5 , E 8 . C 4 = {3,4}-{3}= {4} C 5 = {3,4,5}-{3}= {4,5} C 8 = {1,2,3,4,5,6,7,8}-{3}= {1,2,4,5,6,7,8} i = 3+1 = 4 Step 4 : E 4 = 4 Step 5 : sisi yang berhubungan langsung dengan titik yang ada di E 4 adalah E 5 , E 9 . C 5 = {4,5}-{4}= {5} C 9 = {1,2,3,4,5,6,7,8,9}-{4}= {1,2,3,5,6,7,8,9} i = 4+1 = 5 Step 4 : E 5 = 5 Step 5 : sisi yang berhubungan langsung dengan titik yang ada di E 5 adalah E 10 . C 10 = {1,2,3,4,5,6,7,8,9,10}-{5}= {1,2,3,4,6,7,8,9,10} i = 5+1 = 6 Step 4 : E 6 = 2 Step 5 : sisi yang berhubungan langsung dengan titik yang ada di E 6 adalah E 7 , E 8 , E 9 , E 10 . C 7 = {1,3,4,5,6,7}-{2}= {1,3,4,5,6,7} C 8 = {1,2,4,5,6,7,8}-{2}= {1,4,5,6,7,8} C 9 = {1,2,3,5,6,7,8,9}-{2}= {1,3,5,6,7,8,9} C 10 = {1,2,3,4,6,7,8,9,10}-{2}= {1,3,4,6,7,8,9,10} i = 6+1 = 7 Step 4 : E 7 = 1 Step 5 : sisi yang berhubungan langsung dengan titik yang ada di E 7 adalah E 8 , E 9 , E 10 .
C 8 = {1,4,5,6,7,8}-{1}= {4,5,6,7,8}
C 9 = {1,3,5,6,7,8,9}-{1}= {3,5,6,7,8,9} C 10 = {1,3,4,6,7,8,9,10}-{1}= {3,4,6,7,8,9,10} i = 7+1 = 8 Step 4 : E 8 = 4 Step 5 : sisi yang berhubungan langsung dengan titik yang ada di E 8 adalah E 9 , E 10 . C 9 = {3,5,6,7,8,9}-{4}= {3,5,6,7,8,9} C 10 = {3,4,6,7,8,9,10}-{4}= {3,6,7,8,9,10} i = 8+1 = 9 Step 4 : E 9 = 3 Step 5 : sisi yang berhubungan langsung dengan titik yang ada di E 9 adalah E 10 . C 10 = {3,6,7,8,9,10}-{3}= {6,7,8,9,10} i = 9+1 = 10 Step 4 : E 10 = 6 Step 5 : sisi yang berhubungan langsung dengan titik yang ada di E 10 semua sudah di eksekusi jadi lanjut ke step 6. Step 6 : Table titik titik G dan warnanya
Tabel 1. Hasil Pewarnaan E(G) E 1 E 2 E 3 E 4 E 5 E 6 E 7 E 8 E 9 E 10 Warna E i 1 2 3 4 5 2 1 4 3 6
Hasil dari pewarnaan graf sebagai brikut :
Gambar 3 . Hasil Pewarnaan
Pada gambar 2, adalah hasil hari pewarnaan antara vertex kelas dan mata kuliah 2 sks yang ada pada semester I prodi teknik  informatika kelas pagi. Jadi, untuk slot  waktu yang digunakan adalah 6 waktu. Untuk waktu pada kelas pagi yaitu dari jam 08.00-15.30. Untuk warna yang sama bisa menggunakan waktu yang sama tetapi ruangan yang berbeda.
1. Warna Biru untuk (PA,Agama Islam), (PB,Alpro Dasar)
2. Warna Merah untuk (PA,Alpro Dasar), (PB,Agama Islam)
3. Warna Hijau untuk (PA, Bahasa Inggris I), (PB,Fisika)
4. Warna Ungu untuk (PA,Fisika), (PB,Bahasa Inggris I)
5. Warna Hitam untuk (PA, Bahasa Indonesia)
6. Warna Orange untuk (PB, Bahasa Indonesia)
Adapun hasil dari pewarnaan graf untuk mata kuliah 2 sks pada semester 1 kelas pagi prodi teknik informatika yaitu ada 6 warna yang di dapatkan pada gambar 3, 6 warna yang didapatkan pada graf G pada penjadwalan ini digunakan untuk waktu pada penjadwalan mata kuliah. Jadi, 6 warna adalah 6 waktu yang dapat digunakan pada mata kuliah 2 sks semester 1 kelas pagi teknik informatika. Untuk penjadwalan mata kuliah ini, pada warna yang sama  maka dapat menggunakan waktu yang sama tetapi untuk ruangan  yang berbeda.  Hasil penjadwalan  dapat dilihat pada tabel 2 sebagai berikut :
Tabel 2 . Hasil Jadwal Warna Jam Ruangan Hari Matkul Kelas Biru 08.00-09.40 7 Senin Agama Islam PA Biru 08.00-09.40 9 Senin Alpro Dasar PB Merah 08.00-09.40 9 Selasa Alpro Dasar PA Merah 08.00-09.40 12 Selasa Agama Islam PB Hijau 08.00-09.40 1 Rabu Bahasa Inggris I PA Hijau 08.00-09.40 12 Rabu Fisika PB
Warna Jam Ruangan Hari Matkul Kelas Ungu 10.00-11.40 4/6 Senin Fisika PA Ungu 10.00-11.40 10 Senin Bahasa Inggris I PB Hitam 10.00-11.40 12 Selasa Bahasa Indonesia PA Orange 10.00-11.40 10 Rabu Bahasa Indonesia PB

## 4.2 Tampilan Interface
Pada gambar 4, merupakan proses penjadwalan matakuliah secara otomatis, data yang harus diinputkan terlebih dahulu  adalah  data  dosen  pengampu  matakuliah,  data  kelas,  data  ruang  dan  data  waktu,  setelah  data  yang diperlukan  sudah  tersedia  maka  klik  tombol  Proses  Jadwal,  dari  proses  jadwal  tersebut  akan  tampil  jadwal matakuliah yang sesuai dengan data dosen yang telah diinputkan sebelumnya.
Gambar 4 . Proses Penjadwalan Mata kuliah

## 4.3 Pengujian
Pengujian menggunakan Black Box Testing . Metode ini dilakukan dengan cara menjalankan atau mengeksekusi program  yang  dihasilkan.  Kemudian  diamati  apakah  hasil  dari  program  tersebut  sesuai  dengan  hasil  yang diinginkan. Pengujian ini akan menguji secara detail dari tombol tambah dan tombol proses, hasil yang diharapkan  adalah  keberhasilan .  Jika  masih  terdapat  kesalahan  atau terdapat  hasil  yang  tidak  sesuai  dengan yang diinginkan, maka kesalahan ataupun ketidaksesuaian tersebut dicatat untuk selanjutnya dicek satu per satu dan diperbaiki.
Table 3 . Pengujian Black Box No Uraian Hasil Yang Diharapkan Hasil Pengujian 1 Tombol Tambah Pada saat ingin tambah data maka klik  tombol  tambah,  maka  akan tampil form  input guna  untuk memasukkan data baru.  Berhasil  Tidak berhasil 2 Tombol Proses Ketika  pengguna  klik  tombol proses,  sistem  akan  langsung melakukan proses penjadwalan.  Berhasil  Tidak berhasil

## 5. KESIMPULAN
Disimpulkan  bahwa  dengan  menerapkan  metode  pewarnaan  graf  untuk  penjadwalan  matakuliah  dapat mempermudah  program  studi  dalam  menyusun  jadwal  perkuliahan  tiap  semesternya,  sehingga  menghindari terjadinya tumpang tindih antara mata kuliah, dosen, ruangan dan waktu yang bersamaan. Hasil akhirnya sebelum digunakan, dilakukan pengujian black box, dengan menguji apakah fungsi-fungsi dalam aplikasi tersebut berjalan dengan  baik.  Diharapkan  kedepannya  aplikasi  dapat  dikembangkan  dengan  melihat  kapasitas  ruangan  yang tersedia dan tidak berfokus pada satu waktu.

## REFERENCES
[1]  R.  Munarto  and  E.  Permata,  “Perancangan  Sistem  Penjadualan  Kuliah  di  Jurusan  Teknik  Elektro  Ft.Untrirta  Menggunakan  Teknik Pewarnaan Graph Algoritma Backtracking Welch-Powell,” Semin. Nas. Inov. Teknol. UN PGRI Kediri , pp. 277–282, 2017.
[2]  K. Harianto and T. S. E. Fatdha, “Penerapan Pewarnaan Simpul Graf untuk Menentukan Jadwal Ujian Skripsi pada STMIK AMIK Riau Menggunakan Algoritma Welch-Powell,” Sains dan Teknol. Inf. , vol. 1, no. 2, pp. 48–54, 2015.
[3]  N. Yannuansa and R. Ramadhani, “Penggunaan Graf Dalam Penjadwalan Perkuliahan Teknik Elektro Universitas Hasyim Asy’Ari,” J. Reaktom , vol. 1, no. 2, pp. 33–35, 2018.