Vol. 5, No. 1 (2023), pp. 53-57 p-ISSN 2656-6303 – e-ISSN 2656-9876 URL:http://journal.unirow.ac.id/index.php/mv
Bidang Penelitian : Tanggal Masuk: 08–05-2023; Revisi: 08-08-2023 Diterima: 23-09-2023

## PENYUSUNAN JADWAL MATA  KULIAH DI PROGRAM STUDI MATEMATIKA UNIVERSITAS PGRI RONGGOLAWE MENGGUNAKAN PEWARNAAN GRAF
Ahmad Zaenal Arifin 1* , Saeful Mizan 2
1 Prodi Matematika, Universitas PGRI Ronggolawe
2 Prodi Matematika, Universitas PGRI Ronggolawe Email: az_arifin@unirow.ac.id *
Abstrak – Dalam  pekerjaan  yang  melibatkan banyak  orang,  tentunya  penjadwalan  kerja menjadi  suatu  kebutuhan  yang  mutlak diperlukan,  Hal  ini  karena  dengan  adanya penjadwalan, sebuah perusahaan atau lembaga  dapat  mengalokasikan  sumber  daya berupa  fasilitas,  tenaga  kerja,  peralatan maupun urutan pekerjaan yang akan dilakukan.  Jika  tidak  ada  penjadwalan  yang baik  maka  akan  terjadi  kekacauan  dalam pekerjaan.  Tidak  jauh  berbeda  dengan  yang dialami  oleh  beberapa  Prodi  yang  ada  di lingkungan  Universitas  PGRI  Ronggolawe. Permasalahan yang sering muncul antara lain: ruangan  yang  bentrok  antar  Program  Studi dan  beberapa  dosen  memiliki  permintaan ngajar  di  jam-jam  tertentu.  Tujuan  dari penelitian  ini  adalah  memberikan  solusi  pada permasalahan  tersebut  agar  tidak  terjadi bentrok  ruangan  antar  program  studi  dan dapat  mengakomodir  permintaan  ngajar dosen di jam-jam tertentu. Metode matematika yang efisien untuk masalah penjadwalan mata kuliah  ini  adalah  pewarnaan  graf,  karena pewarnaan  graf  ini  dapat  menghubungkan antar parameter yang akan digunakan antara lain:  Dosen,  mata  kuliah  persemester,  waktu, ruang kuliah, hari efektif.
Kata  Kunci  – Jadwal,  Mata  Kuliah,  Teori Graf, Algoritma Well Powel, Bilangan Kromatik.

## I. PENDAHULUAN
Permasalahan  yang  menuntut  untuk membuat  perencanaan  yang  matang  sering  kali
muncul dalam keseharian manusia, seperti dalam hal  penjadwalan,  penjadwalan  akan  menentukan keteraturan  dalam  kegiatan,  penjadwalan  yang baik  akan  membuat  kegiatan  yang  baik  juga  dan begitu  juga  sebaliknya    [1],  [2].  Hal-hal  yang menjadi  Batasan  dalam  penjadwalan  diantaranya adalah ketersediaan waktu, ketersediaan ruang.[3].
Penyusunan jadwal sering dilakukan oleh Lembaga atau perusahaan, tak terkecuali Lembaga Pendidikan [4]–[6]. Contohnya penjadwalan mata pelajaran/mata kuliah [7]–[9].. Proses penjadwalan yang terjadi seringkali menggunakan manual  dan  dianggap  rumit  [10].  Keterbatasan penjadwalan secara manual adalah terlalu banyak pertimbangan  yang  harus  dimasukkan.  Beberapa faktor  yang  memperngaruhi  proses  penjadwalan matakuliah antara lain jumlah matakuliah, jumlah dosen,  jumlah  ruangan,  kebutuhan  mahasiswa, dan permintaan jam ngajar [10]–[12].
Pendistribusian  jadwal  matakuliah  yang baik  diharapkan  mampu  menjadi  solusi  terhadap faktor-faktor  yang  mempengaruhi  penjadwalan tersebut  [13],  [14].  Sebuah  jadwal  dibentuk sedemikian  rupa  agar  tidak  terjadi  penumpukan jadwal mengajar matakuliah yang berbeda di hari dan  jam  yang  sama.  Permasalahan  penjadwalan matakuliah  juga  muncul  pada  Universitas  yang menjadi  tempat  untuk  menyelenggarakan  proses kegiatan  belajar  mengajar.  Universitas  PGRI Ronggolawe  yang  memiliki  18  Program  Studi tentunya  tidak  terlepas  dari  permasalahan  yang serupa.  Beberapa  Program  Studi  seringkali mengalami bentrok ruangan. Hal tersebut tentunya berasal  dari  penjadwalan  yang  belum  tertata dengan  baik.  Program  Studi  Matematika  adalah salah  satu  program  studi  yang  mengalami
permasalahan  serupa.  Permasalahan  yang  terjadi adalah sering bentrok ruangan dan juga kesulitan dalam mengakomodir penjadwalan yang disesuaikan  dengan  permintaan  dosen.  Dalam penelitian  ini  permasalahan  semacam  ini  akan diselesaikan  menggunakan  salah  satu  ilmu matematika yaitu Teori Graf [15], [16].
Salah satu cabang ilmu matematika yang memiliki  peranan  penting  dalam  penyelesaian masalah penjadwalan adalah Teori Graf [15], [16]. Keunikan  dari  teori  graf  adalah  kesederhanaan, Hal  tersebut  karena  graf  dapat  disajikan  dalam titik  ( vertex )  dan  sisi  ( edge ).  Salah  satu  metode yang  sering  digunakan  adalah  pewarnaan  graf. Pewarnaan graf ini dapat digunakan sebagai acuan dalam  menyusun  jadwal  yang  hasilnya  dapat menghindarkan  bentrokan  jadwal  antar  dosen maupun antar Program Studi [17], [18].
Sistem penjadwalan dapat diselesaikan dengan metode  pewarnaan  graf  [16].  Berdasarkan  hasil peninjauan  permasalahan,  Prodi  Matematika Universitas  PGRI  Ronggolawe  dapat  dijadikan objek  penelitian  karena  memiliki  permasalahan dalam  penjadwalan.  Hasil  penelitian  berupa jadwal  alternatif  yang  nantinya  dapat  digunakan sebagai  acuan  dalam  penjadwalan  disemester berikutnya .

## II. METODE PENELITIAN
Objek  Penelitian  dalam  penelitian  ini adalah  matakuliah  semester  genap  tahun  ajaran 2022/2023, Data ruang kelas yang digunakan, data dosen pengampu mata kuliah dan data slot waktu mengajar  yang  diterapkan  di  Program  Studi Matematika  Universitas  PGRI  Ronggolawe Tuban.  Jenis  penelitian  yang  digunakan  dalam penelitian ini adalah deskriptif kuantitatif, karena memiliki tujuan untuk memberikan gambaran atau lukisan  secara  sistematis,  faktual  dan  akurat mengenai  fenomena  yang  diteliti.  Data  yang digunakan  dalam  penelitian  ini  adalah  data sekunder  yang  diperoleh  dari  Program  Studi Matematika  Universitas  PGRI  Ronggolawe Tuban.  Data  yang  akan  dikumpulkan  adalah matakuliah semester genap tahun ajaran 2022/2023, data ruang kelas yang digunakan, data dosen pengampu mata kuliah dan data slot waktu mengajar yang diterapkan.
Langkah  dalam  melakukan  penelitian  ini adalah 1. Tahap Persiapan Pada tahap persiapan ini dilakukan persiapan alat yang dibutuhkan. Pada tahap ini, mahasiswa yang terlibat berperan sebagai surveyor untuk pengambilan  data.  Dari  perijinan  pengambilan
data Data yang akan diambil adalah data sekunder dari Program Studi Matematika berupa Matakuliah semester genap tahun ajaran 2022/2023, Data ruang kelas yang digunakan, data dosen pengampu mata kuliah dan data slot waktu mengajar yang diterapkan.
2. Tahap Pelaksanaan Setelah  memperoleh  data  tersebut  kemudian data  diolah  untuk  mempermudah  dalam menganalisisnya.  Tahap  pengolahan  data adalah sebagai berikut
1. Menggambarkan  hubungan  dari  parameter matakuliah, dosen pengampu, jumlah mahasiswa,  ruang  kuliah,slot  waktu  kedalam bentuk tabel.
2. Menggambarkan  hubungan  dari  parameter matakuliah, dosen pengampu, jumlah mahasiswa,  ruang  kuliah,slot  waktu  kedalam bentuk graf sederhana.
3. Menganalisis serta membagi setiap matakuliah    di  tiap-tiap  semester  kedalam bentuk  tabel,  Tabel  tersebut  merupakan representasi  dari  graf  sederhana  yang terbentuk.
4. Memberi  warna  pada  houngan  dari  dosen pengampu,  matakuliah,  jumlah  mahasiswa, ruang kuliah menggunakan prinsip pewarnaan graf.
5. Mentabulasikan  hasil  dari  pewarnaan  graf kedalam bentuk tabel
6. Menggambarkan jadwal matakuliah
berdasarkan  slot  waktu  yang  digunakan, banyaknya tingkat semester, banyaknya kelas,yang  digunakan  dan  membagi  dari  hari efektif.  Kemudian  memberikan  warna  pada setiap  ruangan  dan  mengatur  warna  yang sesuai untuk tiap-tiap tingkatan semester.
7. Mengambarkan  bentuk  hasil  penyusunan jadwal untuk tiap tingkatan semester’
III. HASIL DAN PEMBAHASAN
a) Data
Berdasarkan data hasil penelitian yaitu daftar mata kuliah, dosen pengampu,waktu
i) Banyaknya mata kuliah pada semester genap digambarkan pada tabel 1 berikut

## PENYUSUNAN JADWAL MATA  KULIAH DI PROGRAM STUDI MATEMATIKA….
Tabel 1. Sampel Daftar Mata Kuliah Prodi Matematika Mata Kuliah Kode Mata Kuliah Kode Angka SKS Teori Graf MAT3230 1 3 Teori dan Logika Fuzzy MAT4243 2 3 Struktur Aljabar 2 MAT4127 3 3 Sistem Linear MAT4119 4 3 Metode Numerik MAT4129 5 3 Karir dalam Matematik a MAT2113 6 2 Kapita Selekta MAT4241 7 3 Fungsi Kompleks MAT3143 8 3 ii) Banyaknya dosen yang mengajar mata kuliah semeser ganjil pada Program Studi
Matematika digambarkan pada tabel 2 berikut
Tabel 2. Sampel Daftar Mata Kuliah
Prodi Matematika Nama Dosen Kode Dosen Kresna Oktafianto, M.Si. A1 Eriska Fitri K.,S.Pd., M.Si. A2 Lilik Muzdalifah, S.Pd., M.Si. A3 Ahmad Zaenal Arifin, M.Si. A4 Nia Nurfitria, M.Si. A5 Andik Adi Suryanto, M.Kom. A6 Riska Andriani, M.Si. A7 Sumarno, M.Pd. A8 iii) Ruang yang digunakan adalah Gedung G1, G2,dan G3
iv) Waktu yang digunakan dengan rentang waktu yang digunakan dalam 1 SKS =
50 menit. Adapun waktu yang digunakan oleh penuls dalam penelitian ini adalah
Tabel 3 . Waktu yang digunakan
Program Studi Matematika Semester Genap Tahun 2023
No  Rentang waktu
1 07.00-08.00 WIB 2 08.00-08.50 WIB 3 08.50-09.40 WIB 4 09.40-10.30 WIB 5 10.30-11.20 WIB 6 11.20-12.10 WIB 7 12.10-13.00 WIB
8 13.00-13.50 WIB
9 13.50-14.40 WIB
10 14.40-15.30 WIB 11 15.30-16.20 WIB 12 16.20-17.10 WIB b) Representasi Graf hubungan antara matakuliah dengan dosen pengampu matakuliah meggunakan matriks ketetanggaan
Tabel 4 Sampel representasi graf dalam Bentuk Tabel Hubungan Dosen dengan Mata Kuliah yang Diampu
Dosen/MK  1  2  3  4  5  6  7  8  9  10  11  12
A1 1 1 1 A2 1 1 1 A3 1 A4 1 1 A5 1 1
c) Menggambarkan Graf sederhana hubungan antara Dosen dengan Matakuliah yang diampu
Gambar 1. Graf Hubungan antara dosen dengan mata kuliah
Gambar 2. Pewarnaan Graf Hubungan antara dosen dengan mata kuliah
Jumlah warna kromatik (𝛾(𝐺)) yang didapatkan adalah 5. Dari gambar 4.2 dapat diperoleh jadwal mata kuliahdengan ketentuan titik yang sewarna dapat melakukan jadwal perkuliahan bersama.
Tabel 5 Jadwal Mata Kuliah jika hari efektif
semua digunakan Hari Tk Smt Slot wak tu Ruang Nama MK Dosen MK Seni n IV 07.1 0- 09.4 0 G1 Metod e Matem atika Ahma d Zaena l Arifin VI 07.1 0- 09.4 0 G2 Teori Graf Eriska Fitri K 09.4 0- G2 Teori dan Kresn a 12.1 0 Logika Fuzzy Oktafi anto 12.1 0- 14.4 0 G2 Karir dalam Matem atika Nia Nurfit ria Selas a IV 07.1 0- 09.4 0 G1 Sistem linear Kresn a Oktafi anto VI 07.1 0- 09.4 0 G2 Bahasa Ingris Matem atika Nia Nurfit ria 09.4 0- 12.1 0 G2 Pengan tar Probab ilitas Eriska Fitri K 12.1 0- 14.4 0 G2 Progra m Linear Lilik Muzd alifah Rab u II 07. 10- 09. 40 G1 Fungsi Komp leks Kresn a Oktaf ianto IV 07. 10- 09. 40 G2 Aljaba r Linear Eleme nter Lilik Muzd alifah 09. 40- 12. 10 G2 Geom etri Analit ik Ahma d Zaena l Arifin 12. 10- 14. 40 G2 Bahas a Indon esia Nia Nurfit ria Kami s II 07.1 0- 08.5 0 G1 Biolog i dasar Riska Andri ani 09.4 0- 12.1 0 G1 Fisika Dasar Sri Cacik 12.1 0- 14.4 0 G1 Pendid ikan Kewar ganega raan Sumar no

## PENYUSUNAN JADWAL MATA  KULIAH DI PROGRAM STUDI MATEMATIKA….
IV 07.1 0- 09.4 0 G2 Analisi s Real I Kresn a Oktafi anto 09.4 0- 12.1 0 G2 Pengan tar Teknol ogi inform asi Andik Adi Surya nto Juma t II 07.1 0- 09.4 0 G1 Kalkul us 2 Ahma d Zaena l Arifin VI 07.1 0- 09.4 0 G3 Kapita Selekta Eriska Fitri K

## IV. KESIMPULAN
Metode  pewarnaan  graf  merupakan  metode yang  efektif  dalam  penyusunan  jadwal,  seperti penerapan  pada  penyusunan  jadwal  di  Program Studi Matematika Universitas PGRI Ronggolawe. Berdasarkan  penelitian  yang dilakukan  diperoleh jadwal  mulai  hari  senin  sampai  hari  jumat  tanpa adanya bentrok. Untuk selanjutnya  dapat dikembangkan dengan memperhatikan permintaan  jadawal  dari  beberapa  dosen.  Akan tetapi  harus  menerapkan  beberapa  aturan  agar metode  pewarnaan  graf  dapat  berjalan  dengan baik..

## REFERENSI
[1] E. Herdiansyah and R. Cahyana, “Pengembangan  Aplikasi  Penyusun  Jadwal Pelajaran Secara Otomatis,” J.  Algoritm. ,  vol. 12, no. 2, pp. 186–191, 2015.
[2] H.  Purwanto,  “Perancangan  Sistem  Informasi Jadwal  Pelatihan  Karyawan  Pt.  Xyz,” JSI (Jurnal Sist. Informasi) Univ. Suryadarma , vol. 6, no. 2, pp. 25–46, 2021.
[3] K.  Hermanto,  R.  Suarantalla,  and  S.  Sahdan, “Aplikasi  Program  Linier  Integer  0-1  Untuk Menyusun  Jadwal  Usulan  Piket  Satpol  Pp,”
BAREKENG J. Ilmu Mat. dan Terap. , vol. 14,
no. 1, pp. 91–100, 2020.
[4] H. A. R. Pananrangi and M. P. SH, Manajemen Pendidikan ,  vol.  1.  Celebes  Media  Perkasa,
2017.
[5] H. B. Uno, Perencanaan pembelajaran . Bumi
Aksara, 2023.
[6] W. Zulkarnain, Manajemen Layanan Khusus di Sekolah . Bumi Aksara, 2022.
[7] D.  D.  Ariembi,  “Rancang  Bangun  Sistem Informasi  Penjadwalan  Mata  Pelajaran  pada SMP Negeri  17 Makassar.” Universitas Islam Negeri Alauddin Makassar, 2017.
[8] T.  Handayani,  D.  H.  Fudholi,  and  S.  Rani, “Kajian  Algoritma  Optimasi  Penjadwalan Mata Kuliah,” 2020.
[9] A.  R.  Mile,  M.  R.  Katili,  and  N.  Nurwan, “Penjadwalan  Mata  Pelajaran  Menggunakan Integer  Nonlinear  Programming,” Res.  Math. Nat. Sci. , vol. 1, no. 1, pp. 12–18, 2022.
[10] A.  Wijaya  and  G.  Gunawan,  “Implementasi
Algoritma Round Robin Pada Sistem Penjadwalan  Mata  Kuliah  (Studi  Kasus: Universitas  Muhammadiyah  Bengkulu),” J. Inform. Upgris , vol. 4, no. 1, 2018.
[11] I.  A.  Ramadhani,  “Pengembangan  sistem informasi  penjadwalan  mata  kuliah  berbasis web  di  fakultas  Teknik  Universitas  Negeri Makassar,” J. Pendidik. , vol. 6, no. 2, pp. 1–15, 2018.
[12] E.  Suhartono,  “Optimasi  penjadwalan  mata kuliah dengan algoritma genetika (studi kasus di amik jtc semarang),” J. Ilm. INFOKAM , vol. 11, no. 5, 2015.
[13] I.  A.  Soenandi,  “Konsep  algoritma  genetik biner  untuk  optimasi  perencanaan  jadwal kegiatan  perkuliahan,” J.  Tek.  dan  Ilmu Komput. , 2013.
[14] E. Sufarnap and S. Sudarto, “Analisis Optimasi Penjadwalan  Jaga  Dokter  Residen  Penyakit Dalam pada Rumah Sakit Pendidikan,” J. SIFO Mikroskil , vol. 12, no. 2, pp. 97–104, 2011.
[15] A.  W.  Bustan  and  M.  R.  Salim,  “Penerapan Pewarnaan  Graf  Menggunakan  Algoritma Welch  Powell  untuk  Menentukan  Jadwal Bimbingan Mahasiswa,” J.  THEOREMS  (The Orig. Res. Math. , vol. 4, no. 1, pp. 79–86, 2019.
[16] T.  P.  Gunawan,  “Aplikasi  Pewarnaan  Graph Untuk  Menyusun  Jadwal,”  in Prosiding Konferensi  Nasional  “Inovasi  dalam  Desain dan  Teknologi”  ‐  IDeaTech  2011 ,  2011,  pp. 24–31.
[17] F.  Daniel  and  P.  N.  L.  Taneo, Teori  Graf . Deepublish, 2019.
[18] A. Widodo, Teori Graf . Universitas Brawijaya Press, 2016.