## PENERAPAN ALGORITMA GRAF WELCH POWEL PADA PENJADWALAN MATA KULIAH DAN JADWAL ASISTEN STUDY KASUS FORUM ASISTEN STMIK AMIKOM PURWOKERTO
Fajar Mahardika Program Studi Teknik Informatika STMIK Amikom Purwokerto Email: putrafajardika@gmail.com

## Hendra Marcos
Program Studi Teknik Informatika STMIK Amikom Purwokerto Email: hendra.marcos@amikompurwokerto.ac.id

## ABSTRAK
Forum asisten merupakan sebuah organisasi yang dibentuk oleh lembaga STMIK Amikom Purwokerto yang bertugas untuk membantu dosen dalam kegiatan praktikum yang ada di STMIK Amikom Purwokerto. Setiap anggota  masih menempuh perkuliahan yang di lakukan dengan mengambil jadwal asisten setiap harinya. Pendjadwalan ini sangat diperlukan agar setiap anggota tidak terganggu baik itu dalam menjalankan perkulihan yang sedang diambil maupun kegiatan asisten yang menjadi tanggung jawab anggota tersebut. Seseorang anggota pernah mengalami bentrok antara jadwal asisten dengan jadwal perkuliahan yang di jalani anggota tersebut. Permasalahan ini yang membuat penulis angkat untuk bisa membantu agar antara jadwal perkuliahan dengan jadwal asisten tidak bentrok dan lebih optimal. Hal ini penulis mengkaitkan dengan kajian ilmu yang ada di matematika diskrit pada teori graf untuk membantu mengatasi permasalahan ini. Penulis menggunakan sebuah metode algoritma welch-Powell dengan membentuk flowchat. Pada penelitian ini menghasilkan penjadwalan yang dilakukan oleh anggota forum asisten sangat efektif untuk mengatur jadwal asisten dengan jadwal perkuliahan, algoritma welch-powell sangat baik digunakan untuk menguji dan menganalisa dalam penjadwalan anggota forum asisten.
Kata kunci: forum asisten, penjadwalan, algoritma welch-powell , efektif.

## ABSTRACT
Assistant forum is an established organization by STMIK Amikom Purwokerto who is assigned to assist the lecturer in the practicum activities that are on STMIK Amikom Purwokerto. Each member is still studying which is done by taking an assistant's schedule every day. This scheduling is necessary for each member not bothered either in running lectures which is being taken as well as the activities of the assistant to which the member is responsible. A member has experienced a clash between the assistant's schedule and the lecture schedule in which the member lives. This problem that makes writers lift to be able to help so that between schedule of schedule with schedule of assistant not clashing and more best. This authors associate with the study of existing science in discrete mathematics on graph theory to help overcome this problem. The author uses a welch-Powell algorithm method by forming a flowchart. In this research, the scheduling done by the assistant forum member is very effective to arrange the schedule of assistant with lecture schedule, the welch-powell algorithm is very well used to test and analyze in the scheduling of assistant forum members.
Keywords: forum assistant, scheduling, welch-powell algorithm, effective.

## 1. PENDAHULUAN
Forum asisten merupakan sebuah organisasi yang dibentuk oleh lembaga STMIK Amikom Purwokerto yang bertugas untuk membantu dosen dalam kegiataan praktikum yang ada di STMIK Amikom Purwokerto. Forum asisten memiliki banyak anggota yang berasal dari semua angkatan yang membantu dosen disemua mata kuliah yang terdapat kegiatan praktikum. Setiap anggota masih menempuh kuliah yang di lakukan sambil  mengambil jadwal asisten setiap harinya. Kebanyak asisten mendapatkan penjadwalan yang bentrok antara jadwal kuliah dan jadwal asisten. Penjadwalan merupakan
suatu pekerjaan rutin yang selalu dilakukan oleh para asisten yang bergabung dalam forum asisten agar tidak ada jadwal yang bentrok antara jadwal kuliah dan jadwal asisten.
Dalam melakukan penjadwalan semua asisten, diperlukan pemikiran yang cukup rumit untuk bisa melaksanakan kedua kegiatan tersebut dengan pertimbangkan atau mentitik beratkan pada kewajiban kuliah dan tidak mengkesampingkan kewajiban untuk berbagi ilmu dan membantu dosen dalam kegiatan praktikum. Dalam melakukan penjadwalan jika dilakukan dengan manual pasti akan membutuhkan waktu yang cukup lama untuk dapat melakukan hal ini dengan kemungkinan terjadi bentrok antara jadwal kuliah dan jadwal asisten akbiat human eror.
Permasalahan penjadwalan kuliah dan asisten sangat erat dengan masalah optimasi. Oleh karena itu pengembangan sistem penjadwalan dilakukan dengan melalui proses iterasi perbaikan. Fungsi prosers iterasi perbaikan ini untuk meminimalisis bentrok jadwal yang diakibatkan oleh human eror. Dalam kajian ilmu di Matematika Diskrit, teori graf sangat membantu untuk pembuatan sistem penjadwalan diharapkan teori ini dapat menjawab permasalahan yang terjadi dalam penganturan jadwal asisten dan jadwal kuliah yang dilakukan oleh anggota Forum Asisten STMIK Amikom Purwokerto.
Penelitian Terdahulu 1. Penyusunan Jadwal ujian mata kuliah dengan algoritma pewarnaan graf welch powell yang ditulis oleh Setia Astuti dari fakultas ilmu komputer Universitas dian Nuswantoro Semarang dengan kesimpulan Berdasarkan analisa dan pembahasan diatas dapat diambil kesimpulan sebagai berikut: a) Algoritma Pewarnaan Graph Welch Powell bisa digunakan untuk menentukan jadwal ujian semester pada sistem informasi akademik Perguruan Tinggi sehingga tidak terjadi bentrokan jadwal ujian untuk semua mahasiswa. b) Algoritma Pewarnaan Graph Welch Powellbisa digunakan untuk menentukan minimaljumlah hari ujian yang dibutuhkan dalam mengadakan ujian tersebut sehingga bisa menghemat waktu[1]. 2. Aplikasi Pewarnaan simpul dengan algoritma welch powell pada traffic light di yogyakarta. Ditulis oleh Ana Mardiatus Soimah dari Universitas Islam Negeri Sunan Kalijaga. Dengan kesimpulan atau hasil. a. Pewarnaan simpul dengan algoritma Welch-Powell dapat diaplikasikan untuk menyelesaikan perhitungan durasi waktu pada traffic light. b. Penyelesaian perhitungan durasi waktu pada traffic light dengan pewarnaan simpul memberikan alternatif hasil yang lebih efektif 78.64% daripada data sekunder Dinas Perhubungan Yogyakarta tahun 2011[2].

## 1.1 Landasan Teori

## 1.1.1 Teori Graf
Leigthon dan Rubinfeld (2006) menyatakan bahwa dalam matematika dan ilmu komputer, teori graf adalah ilmu mengenai graf struktur matematika. Suatu graf G dapat dinyatakan sebagai G = <V, E>. Graf G terdiri atas himpunan V yang berisikan titik (vertek atau node) dan himpunan E yang berisi sisi (edge) pada graf tersebut. Himpunan E dinyatakan sebagai pasangan dari vertek yang ada dalam V. Sebagai contoh definisi graf disajikan pada Gambar 1[3].
V = {1,2,3,4,5,6} E = {{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}

## Gambar 1. Gambaran Mengenai Definisi Graf
Banyak struktur yang dapat direpresentasikan dengan graf. Ekstensi lain pada graf adalah dengan membuat sisinya berarah, yang secara teknis disebut graf berarah atau digraph (directed graph). Graf berarah dengan isi yang berbobot disebut jaringan. Jaringan banyak digunakan pada cabang praktis teori graf, yaitu analisis jaringan. Namun pada analisis jaringan, definisi “jaringan” bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah) (Harary 1969).

## 1.1.2 Perwarnaan Graf
Dalam teori graf perwanaan merupakan suatu bentuk perlabrlan graf dengan cara memberikan warna pada elemen graf yang akan dijadikan subjek dalam memahami constraint permasalahan. Dengan cara ada tiga macam persoalan perwarnaan graf (Graph Colouring) yaitu perwarnaan simpul, perwarnaan sisi, dan perwarnaan wilayah atau region[4].

## 2. METODOLOGI PENELITIAN

## 2.1 Rancangan Penelitian
Dalam perancangan penelitian ini penulis melakukan pembuatan rancangan terlebih dahulu untuk melakukan sebuah penelitian dengan melakukan konsep sebuah penelitian serta melakukan pencarian kasus yang ada. Dalam perancangan penulis juga melakukan pengumpulan data berbagai data kasus. Penulis juga mencari metode yang tepat untuk setiap kasus yang penulis dapatkan.
Perancangan ini penulis memilih study kasus pada sebuah organisasi forum asisten dengan metode algoritma welch-power dimana dalam kasus ini masalah utama yaitu bentroknya jadwal perkuliahan dan jadwal asisten pada anggota forum asisten.

## 2.2 Pengumpulan Data
2.2.1 Teknik Pengumpulan Data
a) Observasi
Sukandarrumidi (2012) mendefinisikan observasi adalah pengamatan dan pencatatan suatu objek dengan sistematika fenomena yang diselidiki[5]. Dalam pengumpulan data dengan observasi ini penulis melakukan sebuah pengamatan dan  pengambilan data pada sebuah organisasi forum asisten STMIK Amikom Purwokerto. Dengan melihat data jadwal asisten masing-masing anggota dan jadwal perkuliahan anggota. Dengan melakukan observasi ini penulis melihat banyak anggota yang bentrok jadwalnya.
b) Studi Pustaka
Studi pustaka adalah segala usaha yang dilakukan peneliti untuk menghimpun informasi yang relevan dengan topik atau masalah yang akan atau sedang diteliti. Informasi itu dapat diperoleh dari buku-buku ilmiah, sumber-sumber tertulis baik cetak maupun elektronik lain [6].

## 2.3 Analisa Data
Penulis juga melakukan analisa data yang diperoleh agar mengetahui seberapa valid data yang didapatkan dengan di olah dengan langkah-langkah sebagai berikut:
a) Data di seleksi berdasarkan anggota keseluruhan anggota yang digunakan untuk menyelesaikan penelitian.
b) Data diambil sampel untuk selanjutnya di olah data.
c) Data yang sudah di olah di susun dengan membentuk sebuah graf sesuai dengan penelitian.
d) Langkah terakhir data yang sudah disusun menjadi graf diolah kembali dengan algoritma dan menghasilkan verteks dan membuat graf.

## 3. HASIL DAN PEMBAHASAN
Dalam hasil dan pembahasan ini penulis melakukan sebuah langkah dengan menggunakan flowchat algoritma welch-powell untuk menentukan hasil dari penelitian yang dilakukan. Agar hasil yang dikelurkan sesuai dengan penelitian ini. Untuk flowchat algoritma welch-powell seperti dibawah ini:
Mulai Selesai Cari satu simpil berderajat tertinggi atau simpul utama warna (SUW) Beri warna baru Cari satu simpul yang tidak bertetangga dengan SUW dan berderajat tertinggi Beri warna yang sama dengan SUW Tidak ada ada ada Tidak ada
Gambar 2. Flowchart Algoritma Welch-Powell
Dalam pembahasan ini penulis mengambil sampel 16 mahasiswa yang juga anggota forum asisten. Anggota forum asisten ada 80 anak. Format dari sampel data yang diambil ditunjukkan pada gambar 3 dan gambar 4.
Gambar 3. Format Data Sampel Anggota Forum Asisten

## Gambar 4. Format Isian Data Kehadiran Asisten Praktikum
Dari data yang sudah didapat kemudian dibuat rekap data yang dituangkan pada tabel 1 seperti di bawah ini.
Tabel 1. Penyimpulan dari sampel Senen Selasa Rabu Kamis Jumat Sabtu Luthfiyantun Nur A 1 1 1 1 Herlina 1 1 1 1 Yovie 1 1 1 1 1 Fajar Mahardika 1 1 1 1 1 1 Rilas Agung Pambudi 1 1 1 1 1 Randi Octavian Andriyono 1 1 1 1 1 Uswatun Khasanah 1 1 1 1 1 1 Andri Laksono 1 1 1 1 1 1 Hendrik Arnento 1 1 1 1 1 1 Hasirun 1 1 1 1 1 1 Niam Habibi 1 1 1 1 1 Regi 1 1 1 1 1 Windi 1 1 1 1 1 Ana 1 1 1 1 1 Rizky 1 1 1 1 1
Variasi jadwalan kuliah dan asisten yang dimiliki oleh anggota forum asisten dimodelkan secara matematis dalam bentuk graf. Hari dari jadwal di simbolkan didalam graf berupa simpulyang merupakan subject dari contraint yang akan dipenuhin. Ada pun constraint yang dimaksud merupakan syarat dari sebuah jadwal asisten dan jadwal mata kuliah dari anggota forum asisten STMIK Amikom Purwokerto. Dibawah ini merupakan representasi graf yang terbentuk dari tabel kesimpulan sampel diatas.
Sabtu
10.40 12.30 14.20
12.30 14.20 07.00 08.50 10.40 12.30 14.20 16.15 08.50 10.40 12.30 10.40 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Rabu Kamis Yovie Nim 15.11.0135 Asisten Pem Web PBO Senen Selasa RPn Framework Kripto Sister Multimedia RPL Mata Kuliah Bahasa Inggris II PLS

## Gambar 5. Gambar Graf Hasil Dari Tabel 1
Dari gambar graf disusun daftar simpul graf dan ketetanggaannya yang ditunjukkan pada table 2 di bawah ini.
Tabel 2. Tabel simpul dan ketetanggannya Verteks (Simpul) Simpul Tetangga Senen Selasa, Rabu, Kamis, Jumat, Sabtu. Selasa Senen, Selasa. Rabu Senen, Kamis. Kamis Rabu, Sabtu. Jumat Senen Sabtu Senen, Selasa, Kamis.
Dengan Algoritma Welch-Powel , hasil yang didapatkan ditunjukkan pada gambar 6 di bawah ini.
Verteks Senen Sabtu Selasa Rabu Kamis Jumat Derajat 16 13 16 16 16 6 Warna item merah biru merah biru item

## Gambar 6. Tabel Pewarnaan Dengan Algoritma Welch-Powel
Penataan pewarnaan alur kerja sebagai berikut:
a) Pilih verteks senen dengan derajat 5 kemudian diberikan warna iten.
b) Pilih verteks yang tidak bertetangga dengan senen yaitu jumat kemudian diberi warna item juga.
c) Pilih vertek sabtu dengan derajat 3 kemudian diberi warna merah.
d) Pilh vertek yang tidak bertetangga dengan sabtu yaitu rabu kemudian diberi warna merah juga.
e) Pilih vertek selasa dengan derajat 2 kemudian diberikan warna biru.
f) Pilih vertek yang tidak bertetanggan dengan selasa yaitu kamis kemudian diberi warna biru juga.
Gambar graf yang dihasilkan oleh algoritma Welch-Powel ditunjukkan pada gambar 7 di bawah ini

## Gambar 7. Hasil Algoritma Welch-Powel
Berdasarkan graf tersebut terdapat 3 warna yang berbeda untuk 6 sampel dari jadwal kuliah dan jadwal asisten yang menandakan bahawa penjadwalan di forum asisten STMIK Amikom Purwokerto dilakukan dengan baik agar tidak ada bentrok dengan jadwal anggota forum asisten.

## 4. KESIMPULAN
Berdasarkan analisa dan pembahasan diatas dapat disimpulkan sebagai berikut:
a) Penjadwalan yang dilakukan oleh anggota Forum asisten STMIK Amikom Purwokerto sanggat efektif untuk menghindari bentrok antara jadwal kuliah dan jadwal asisten.
b) Algoritma pewarnaan Welch Powel sanggat baik digunakan untuk menguji dan memganalisa pada penjadwalan anggota forum asisten.

## UCAPAN TERIMA KASIH
Penulis mengucapkan terima kasih kepada semua pihak yang telah membantu dalam pembuatan jurnal ini diantaranya:
a) Bapak hendra marcos, S.T, M.Eng yang telah membimbing penulis dan membantu penulis untuk menyusun jurnal ini.
b) Pengurus dan temen-temn forum asisten STMIK Amikom Purwokerto yang telah membantu dan memfasilitasi dalam pembuatan jurnal serta data yang menunjang.
c) Dan kepada semua pihak yang belum di sebutkan penulis mengucapkan banyak terima kasih.

## DAFTAR PUSTAKA
[1] Astuti, S. (2011). Penyusunan Jadwal Ujian Mata Kuliah Dengan Algoritma Pewarnaan Graf Welch   Powell . Jurnal Dian, 11(1)
[2] Soimah, A. M. (2013). Aplikasi Pewarnaan Simpul Dengan Algoritma Welch-Powell Pada Traffic Light Di Yogyakarta (Doctoral Dissertation, Uin Sunan Kalijaga).
[3] Rufaidah, V. W. (2008). Kolaborasi Dan Graf Komunikasi Artikel Ilmiah Peneliti Bidang Pertanian: Studi Kasus pada Jurnal Penelitian dan Pengembangan Pertanian serta Indonesian Journal of Agricultural Science. Jurnal Perpustakaan Pertanian, 17, l.
[4] Munir, Rinaldi. (2005). Matematika Diskrit edisi Ketiga ,l Bandung: Informati.
[5] Sukandarrumidi,  2012. Metodelogi  Penelitian  Petunjuk  Praktis  Untuk pemula. Yogyakarta: Gadjah Mada University Press.
[6] Sugiyono, 2015. Metode Penelitian Pendidikan Pendekatan Kuantitatif, Kualitatif, dan R&D. Bandung: Alfabeta.