Terakreditasi Peringkat Sinta 4 berdasarkan Petikan dari Keputusan Menteri Riset dan Teknologi/ Kepala Badan Riset dan Inovasi Nasional Nomor 200/M/KPT/2020, masa berlaku mulai Vol.3 No.1 tahun 2018 s.d Vol.7 No.2 tahun 2022
Perbandingan Algoritma Welch Powell dan Algoritma Greedy dalam Optimasi Penjadwalan Ruang Kuliah Semester Genap
Fakultas Teknik
Yohana Christela Oktaviani 1 , Yosefina Finsensia Riti 2
1,2 Informatika, Fakultas Teknik, Universitas Katolik Darma Cendika, Indonesia
1 yohana.oktaviani@student.ukdc.ac.id
2 yosefina.riti@ukdc.ac.id
Received: 07-07-2022; Accepted: 27-08-2023; Published: 12-09-2023
Abstrak — Penjadwalan merupakan suatu proses yang dilaksanakan secara  terstruktur  untuk  mengefisiensikan  waktu  kerja  serta menghindari  terjadinya  constraint    dalam  suatu  permasalahan. Penjadwalan ini banyak diterapkan dalam dunia pendidikan, salah satunya ialah penyusunan penjadwalan mata kuliah.  Penyusunan penjadwalan sendiri perlu dioptimalisasikan agar proses perkuliahan dapat berjalan dengan lancar tanpa adanya constraint antar  mata  kuliah.  Seperti  yang  terjadi  pada  Fakultas  Teknik, Universitas  Katolik  Darma  Cendika,  dimana  dalam  penyusunan penjadwalan  ini  belum  terdapat  informasi  ruangan  kuliah.  Oleh sebab  itu,  penulis  menyusun  jurnal  optimasi  penjadwalan  ruang kuliah  dengan  membandingkan  kinerja  antara  algoritma  Welch Powell  dengan  algoritma  Greedy.  Data  yang  digunakan  dalam penelitian ini ialah sejumlah 109 mata kuliah yang tersebar dari 4 Prodi  Fakultas  Teknik,  yakni  Prodi  Teknik  Industri,  Prodi Arsitektur,  Prodi  Ilmu  Informatika,  serta  Prodi  Akupuntur  dan Pengobatan  Herbal.  Metode  yang  digunakan  dalam penelitian  ini ialah  metode  komparatif  yang diterapkan pada  pewarnaan simpul graf,  dimana    parameter  yang  digunakan  ialah  waktu pengeksekusian,  kompleksitas  algoritma,  serta  perhitungan algoritma    secara  manual.  Berdasarkan  penelitian  yang  telah dilakukan,  diperoleh  hasil  7  warna  kromatik  yang  selanjutnya diterapkan pada 7 ruang perkuliahan Fakultas Teknik.
Kata kunci — Penjadwalan, Optimasi, Algoritma Welch Powell, Algoritma Greedy, Constraint
Abstract— Scheduling is a process that is carried out in a structured manner  to  streamline  work  time  and  avoid  the  occurrence  of constraint s in a problem. This scheduling is widely applied in the world  of  education,  one  of  which  is  the  preparation  of  course scheduling. The scheduling itself needs to be optimized so that the lecture process can run smoothly without any constraint s between courses.  As  happened  at  the  Faculty  of  Engineering,  Darma Cendika  Catholic  University,  where  in  the  preparation  of  this schedule  there  is  no information  on lecture rooms.  Therefore,  the authors  compiled  a  journal  of  lecture  scheduling  optimization  by comparing the performance of the Welch Powell Algorithm with the Greedy Algorithm. The data used in this research are 109 courses spread  from  4  Engineering  Faculty  Study  Programs,  namely Industrial  Engineering  Study  Program,  Architecture  Study Program,  Informatics  Science  Study  Program,  and  Acupuncture and Herbal Medicine Study Program. This research was conducted by applying a comparative method in coloring graph vertices, where the parameters used were execution time, algorithm complexity, and
manual calculation of the algorithm. Based on the research that has been  done,  the  results  obtained  are  7  chromatic  colors  which  are then applied to 7 lecture rooms of the Faculty of Engineering. Keywords—Scheduling,  Optimization,  Welch  Powell  Algorithm, Greedy Algorithm, Constraint

## I. P ENDAHULUAN
Penjadwalan  merupakan  alokasi  sumber  daya  terhadap waktu  untuk  menyelesaikan  suatu  pekerjaan  yang  dilakukan secara terstruktur untuk memperoleh hasil yang maksimal [1]. Tujuan  dari  dilakukannnya  penjadwalan  ialah  untuk mengefisiensikan waktu kerja,  meringankan  beban pekerjaan, menghindari constraint dan human  error .  Dalam  dunia pendidikan,  penjadwalan  biasa  diterapkan  untuk  menyusun jadwal  pembelajaran/perkuliahan  yang  harus  dibuat  setiap semester,  jadwal  kuis,  jadwal  ujian  semester,  ujian  skripsi, jadwal mengajar dosen, dan lain sebagainya. Dalam menyusun penjadwalan  perkuliahan,  komponen-komponen  utama  yang diperlukan  ialah  mata  kuliah,  dosen,  mahasiswa,  waktu,  serta ruang  kelas  [2].  Menyusun  penjadwalan  bukanlah  hal  yang mudah, penyusun seringkali dihadapkan pada beberapa kendala. Kendala-kendala  dalam  penjadwalan  ini  terbagi  menjadi  dua jenis,  yakni  kendala  keras  dan  kendala  lunak.  Kendala  keras merupakan  aturan  yang  ditetapkan  oleh  pihak  universitas, seperti dosen atau  pengajar  tidak boleh berada  lebih dari satu tempat  dalam  waktu  yang  sama  dan  sumber  daya  yang dibutuhkan  harus  terpenuhi  dalam  suatu  periode  pengajaran. Sedangkan  kendala  lunak  merupakan  hal-hal  penunjang efisiensi penjadwalan [3].
Untuk  mengatasi  persoalan  yang  sering  terjadi  dalam menyusun  penjadwalan,  maka  perlu  dilakukan  optimasi penjadwalan.  Salah  satu  bidang  ilmu  matematis  yang  biasa digunakan  untuk  memecahkan  permasalahan  optimasi penjadwalan    ialah  teori  graf.  Graf  merupakan  struktur matematis  yang berfungsi untuk merepresentasikan  hubungan di antara objek yang berbeda. Dalam hal ini, graf digambarkan sebagai  suatu  diagram  yang  terdiri  dari  sekumpulan  titik dihubungkan  dengan  garis[4].  Teori  graf  sendiri  merupakan struktur  diskrit  yang  digunakan  untuk  merepresentasikan  dua himpunan,  yakni  himpunan  simpul/vertex  (V)  dan  himpunan
sisi/edges (E) yang biasa dilambangkan dengan G=(V,E). Teori graf  memungkinkan  peneliti  untuk  menguji  hipotesis  suatu permasalahan yang mendefinisikan  karakter hubungan antara satu  simpul  dengan  simpul  yang  lain,  terlepas  dari  apakah simpul tersebut dihubungkan dengan sisi yang sama atau tidak [5].  Penerapan  teori  graf  juga  banyak  diterapkan  untuk memecahkan  permasalahan  penjadwalan  seperti  yang  telah dilakukan oleh beberapa peneliti, antara lain penelitian dengan judul    “Penyusunan  Jadwal  Ujian  Mata  Kuliah  Dengan Algoritma Pewarnaan Graph Welch Powell ”. Dalam penelitian ini, penulis menerapkan teori graf untuk menyusun jadwal ujian mata  kuliah  dengan  menggunakan  metode  pewarnaan  simpul graf [6].
Selain  penelitian  yang  telah  dijelaskan  di  atas,  penerapan algoritma Welch Powell dalam pewarnaan graf juga diterapkan dalam Penjadwalan Piket OSIS pada SMP Negeri 2 Kemranjen [7], Penjadwalan Ujian Skripsi pada  STMIK AMIK Riau  [1], Penjadwalan  perkuliahan  pada  Program  Studi  Teknik Informatika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Tribuana Kalabahi [8], Penjadwalan asisten Study Kasus Forum Asisten STMIK AMIKOM Purwokerto [9], serta Penjadwalan  mata  kuliah  pada  Program  Studi  Pendidikan Matematika FKIP Universitas Muslim Maros [10].
Tidak  hanya  diterapkan  dengan  menggunakan  algoritma Welch Powell , teori graf juga dapat diterapkan  menggunakan algoritma  atau  metode  yang  lainnya.  Penelitian  dengan  judul “Aplikasi Pewarnaan Graf Terhadap Pembuatan Jadwal Ujian Semester di Jurusan Pendidikan Matematika Universitas Islam Jember”  ini  menggunakan  metode  penurunan  aksioma  yang telah  ada  kemudian  diterapkan  pada  pewarnaan  simpul  graf [11].  Penelitian  berikutnya  yang  tidak  menerapkan  algoritma Welch Powell ialah penelitian mengenai Pewarnaan Graf pada Penjadwalan  Mengajar  Dosen  Pendidikan  Matematika Universitas Nurul Jadid yang menggunakan algoritma Greedy . Sama seperti algoritma Welch Powell , algoritma Greedy juga diterapkan untuk menyelesaikan permasalahan optimasi dalam kehidupan  sehari-hari.  Algoritma Greedy memungkinkan peneliti  untuk  memecahkan  permasalahan  komputasi  dengan lebih  efisien  dibandingkan  dengan  algoritma  optimalisasi lainnya  [12].  Algoritma  ini  bersifat heuristic dimana  urutan logisnya  disusun  secara  sistematis  berdasarkan    langkah- langkah  penyelesaian  masalah  [13].  Algoritma Greedy biasanya  digunakan  untuk  menentukan  pilihan  terbaik  dalam setiap  situasi  permasalahan  tertentu.  Secara  umum,  algoritma ini  bekerja  dengan  cara  mengurutkan  terlebih  dahulu  derajat setiap  simpul,  kemudian  menambahkan  satu  simpul  baru  di setiap  langkahnya  [14].  Penambahan  pada  setiap  simpul  baru ini dilakukan dengan mengambil simpul dengan derajat terkecil yang  dimasukkan  ke  dalam  graf  [15].  Algoritma  ini  banyak digunakan  pada  setiap  permasalahan  karena  strateginya  yang intuitif serta efisiensi kinerja yang cukup tinggi [16].
Penelitian  berikutnya  yang  tidak  menggunakan  algoritma Welch  Powell ialah  penelitian  berjudul  “Penjadwalan  Mata Kuliah  Menggunakan  Pewarnaan  Graf  Dengan  Algoritma Largest  First ”  [17]  dan  Penyusunan  jadwal  kuliah  yang dilakukan oleh Fakultas Peternakan UNHAS [18].
Seperti  yang  telah  dipaparkan  dalam  penelitian-penelitian sebelumnya, permasalahan penjadwalan ini banyak ditemukan
dalam  kehidupan  sehari-hari,  terutama  dalam  bidang pendidikan.  Permasalahan  penjadwalan  ini  juga  dialami  oleh Fakultas  Teknik,  Universitas  Katolik  Darma  Cendika. Keterbatasan  ruang  dan  waktu  pengajaran  yang  dimiliki membuat beberapa mata kuliah mengalami ketumpang tindihan antara satu dengan yang lainnya. Selain itu, menurunnya kasus pandemi  Covid-19  membuka  peluang  besar  terjadinya  proses pembelajaran secara tatap muka dimana seluruh Fakultas akan melaksanakan proses pembelajaran di waktu yang sama. Untuk mengatasi  hal  tersebut,  penulis  memfokuskan  penelitian  ini untuk mengoptimasi penjadwalan ruang kuliah semester genap pada  Fakultas  Teknik,  Universitas  Katolik  Darma  Cendika. Penyusunan penjadwalan ini dilakukan dengan membandingkan  efisiensi  waktu  serta  tingkat  kebenaran pengujian manual pada algoritma Welch Powell dan algoritma Greedy .  Dengan  begitu,  kemungkinan  terjadinya  bentrok penggunaan  ruangan  antar  mata  kuliah  dapat  terminimalisir secara  maksimal.  Selain  untuk  menghasilkan  penjadwalan ruang  kuliah  yang  optimal  dengan  membandingkan  kinerja antara  algoritma Welch  Powell dan  algoritma Greedy , penelitian ini juga dilakukan sebagai pemenuhan proyek akhir semester mata kuliah Teori Graf pada Prodi Ilmu Informatika, Universitas Katolik Darma Cendika.

## II. M ETODOLOGI PENELITIAN
Penelitian ini merupakan penelitian terapan yang dilakukan dengan  menerapkan  pewarnaan  simpul  graf.  Subyek  dari penelitian ini ialah sejumlah 109 mata kuliah pada 4 program studi Fakultas Teknik, yakni Teknik Industri, Ilmu Informatika, Arsitektur,  serta  Akupuntur  dan  Pengobatan  Herbal  dimana data yang dijadikan sampel adalah mata kuliah semester genap yang  terdiri  dari  semester  II,  IV,  VI,  dan  semester  VIII. Sedangkan  ruangan  yang  tersedia  dan  digunakan  untuk melakukan  proses  perkuliahan  terdiri  dari  16  ruang,  meliputi VL5A,  VL5D,  VL5E,  VL5F,  VL5H,  VL5I,  VL5J,  VL6A, VL6D,  VL6E,  VL6H,  VL6J,  VL6K,  Lab.Komputer, Lab.Industri, serta Studio Arsitektur.
Rincian  lebih  lanjut  mengenai  mata  kuliah  yang  diampu dalam semester genap disajikan dalam tabel berikut ini.
Tabel I Jadwal Teknik Industri No Kode Mata Kuliah Mata Kuliah Hari Jam Teknik Industri Semester II 1 TI18214 Gambar Teknik & Metrologi Senin 08:50- 11:30 2 UN0003 Kepemimpinan Pribadi Selasa 09:40- 11:30 3 TI18213 Mekanika Teknik Selasa 11:30- 13:10 4 UN0006 Bahasa Indonesia Rabu 09:40- 11:30 5 TI18212 Statistik Industri I Rabu 11:30- 14:00 6 TI18210 Fisika II Kamis 08:00- 10:30 7 TI18209 Matematika Optimasi Kamis 11:30- 14:00 8 TI18208 Bahasa Inggris Jumat 09:40- 11:30 Semester IV 9 TI18430 Elektronika Industri Senin 10:40- 12:20 10 TI18426 Ekonomi Teknik Senin 13:10- 15:30 11 TI18318 Penelt Operasional II Selasa 08:50- 11:30 12 TI18431 WasTek&  Kom Ilmiah Selasa 13:10- 14:50 13 TI18425 TTC dan APK Rabu 08:00- 10:30 14 TI8427 Psikologi Industri Kamis 09:40- 11:30 15 TI18429 Sistem Manufaktur Kamis 11:30- 13:10 16 TI18428 Sistem Basis Data Jumat 09:40- 12:20 Semester VI 17 TI18766 Manajemen Strategi Senin 08:00- 10:30 18 TI18644 Metode Penelitian Selasa 08:00- 09:40 19 TI18647 K3 Selasa 09:40- 11:30 20 TI18648 Manajemen Rantai Pasok Rabu 08:50- 10:30 21 TI18539 Perancangan  Tata Letak Fasilitas Rabu 11:30- 14:00 22 TI18646 Simulasi  Sistem Industri Kamis 08:00- 10:30 23 TI18763 Pengambilan Keputusan  Multi Kriteria Kamis 10:40- 13:10 24 TI18751 Sistem ERP Jumat 09:40- 11:30 25 UN18005 Kuliah Kerja Nyata Jumat 12:20- 14:50 Semester VIII 26 TI18754 Kerja Praktek Selasa 08:00- 09:40 27 TI18856 Pemasaran Industri Kamis 14:00- 15:40 28 TI18857 Tugas Akhir Jumat 08:00- 12:20 Tabel II Jadwal Teknik Informatika Kode Mata Kuliah Mata Kuliah Hari Jam Ilmu Informatika Semester II 29 UN18003 Kepemimpinan Pribadi Senin 08:00– 09:40 30 UN18006 Bahasa Indonesia Selasa 08:00– 09:40 31 IF19207 Algoritma Pemrograman 2 Selasa 10:30- 13:00 32 IF19206 Sistem Operasi Rabu 08:00- 10:30 33 IF19208 Matematika Diskrit Rabu 10:30- 13:00 34 IF19209 Pemrograman Visual Kamis 10:30- 13:00 35 IF19210 Bahasa Inggris Jumat 11:20- 13:00 Semester IV 36 IF19422 Sistem Multimedia Senin 09:40- 12:10 37 IF19421 Grafika Komputer Dan Pengolahan Citra Selasa 08:00- 10:30 38 IF21404 Pemrograman  Basis Data Rabu 09:40- 12:10 39 IF19418 Pemrograman Web Rabu 12:10- 14:40 40 IF19420 Metode Numerik Kamis 08:00- 10:30 41 IF19423 Dinamika Kelompok Jumat 08:00- 09:40 42 IF19417 Teori Graft Jumat 10:30- 13:00 Semester VI 43 IF19635 Penambangan Data Senin 08:50- 11:20 44 IF19630 Technopreneurship 2 Senin 12:10- 14:40 45 IF19634 Etika Profesi Selasa 13:00- 14:40 46 IF21608 Manajemen Rantai Pasok Rabu 09:40- 12:10 47 IF21606 Rekayasa  Perangkat Lunak Kamis 09:40- 12:10 48 IF19636 Sistem Enterprise Kamis 12:10- 14:40 49 IF19632 Sistem Tertanam Jumat 08:00- 10:30
Tabel III Jadwal Arsitektur Kode Mata Kuliah Mata Kuliah Hari Jam Arsitektur Semester II 50 UN18003 Kepemimpinan Pribadi Senin 08:00- 09:40 51 AR18234 Teknologi Bahan Senin 09:40- 12:10 52 AR18221 Merancang Arsitektur 2 Senin 13:00- 14:40 53 UN18206 Bahasa Indonesia Selasa 08:00- 09:40 54 AR18214 Arsitektur & Lingkungan Selasa 10:30- 12:10 55 AR18118 Komunikasi Arsitektur 2 Rabu 08:00- 09:40 56 AR18203 Asas  Arsitektur 1 Rabu 10:30- 12:10 57 AR18221 Merancang Arsitektur 2 (Studio) Kamis 08:00- 11:20 58 AR18120 Merancang Arsitektur 1 (Studio) Kamis 12:10- 15:30 59 AR18120 Merancang Arsitektur 1 Jumat 08:00- 09:40 60 AR18229 Struktur Bangunan 1 Jumat 09:40- 12:10 Semester IV 61 AR18409 Sejarah Arsitektur 2 Senin 08:00- 09:40 62 AR18405 Asas  Arsitektur 3 Senin 09:40- 11:20 63 AR18322 / AR18423 Merancang Arsitektur 3&4 Senin 13:00- 14:40 64 AR18419 CAD Drawing Selasa 08:00- 10:30 65 AR18438 Perancangan Tapak Selasa 11:20- 13:50 66 AR18416 Asas  Perkotaan & Permukiman Rabu 08:00- 09:40 67 AR18431 Struktur Bangunan 3 Rabu 09:40- 12:10 68 AR18436 Fisika Bangunan 2 Rabu 13:00- 14:40 69 AR18322 / AR18423 Merancang Arsitektur  3&4 (Studio) Kamis 08:00- 11:20 Semester VI 70 AR18624 Merancang Arsitektur 5 Senin 09:40- 11:20 71 AR18625 Merancang Arsitektur 6 Senin 13:00- 14:40 72 AR18641 Etika dan Profesi Arsitektur Selasa 08:00- 09:40 73 AR18612 Metodologi Penelitian Selasa 09:40- 12:10 74 AR18006 KKN Selasa 13:00- 15:30 75 AR18611 Arsitektur Nusantara Rabu 08:00- 10:30 76 AR18640 Ekonomi Bangunan Rabu 11:20- 13.50
77 AR18625 Merancang Arsitektur 6 (Studio) Kamis 08:00- 11:20 78 AR18624 Merancang Arsitektur 5 (Studio) Kamis 12:10- 15:30 79 AR18648 Pendalaman Perkotaan & Permukiman Jumat 08:50- 11:20 Semester VIII 80 AR18726 Merancang Arsitektur 7 Senin 13:00- 14:40 81 AR18744 / AR18745 Desain  Projek Mandiri  /  KP lapangan Rabu 08:00- 10:30 82 AR18842 Arsitektur Empati-Intuisi Rabu 08:50- 10:30 83 AR18743 Seminar Rabu 11:20- 13:50 84 AR18726 Merancang Arsitektur 7 (Studio) Jumat 08:00- 11:20 Tabel IV Jadwal Akupuntur & Pengobatan Herbal Kode Mata Kuliah Mata Kuliah Hari Jam Akupuntur dan Pengobatan Herbal Semester II 85 UN18003 Kepemimpinan Pribadi Senin 08:00- 09:40 86 UN18206 Bahasa Indonesia Selasa 08:00- 09:40 87 Anatomi II Selasa 10:30- 12:10 88 Fisiologi & Patofisiologi Rabu 08:00- 11:20 89 Kestrad TCM Kamis 08:00- 11:20 90 Farmakognisi & Imunologi Jumat 08:00- 11:20 91 Bahasa Inggris Jumat 13:00- 14:40 Semester IV 92 Qigong 2 Senin 08:00- 09:40 93 Komunikasi Tarapeutik Senin 13:00- 14:40 94 Peresapan I Selasa 08:00- 09:40 95 Etika Profesi Selasa 12:10- 13:50 96 Diagnosa TCM 2 Rabu 08:00- 09:40 97 Biostatistik Rabu 10:30- 12:10 98 Peresapan II Rabu 13:00- 16:20 99 Manajemen Klinik Kamis 13:00- 14:40 100 Herbal Lanjut Jumat 13:00- 14:40 Semester VI
101 Peny.  Dalam  TCM 2 Senin 09:40- 11:20 102 Diagnosa Konv II + Peny. Dalam Konv. II Selasa 10:30- 15:30 103 Peny.  Dalam  TCM 2 Rabu 08:00- 11:20 104 Kop dan Kerokan Rabu 15:30- 17:10 105 Peny. Lansia Kamis 08:00- 09:40 106 Peny. Wanita Kamis 15:30- 16:20 107 Peny. Anak Jumat 08:00- 09:40 108 Akupuntur II Jumat 13:00- 14:40 109 Peny. Wanita Jumat 15:30- 16:20
Berdasarkan  hasil  observasi  dari  data  yang  telah  diperoleh penulis,  belum  terdapat  keterangan  ruangan  yang  akan digunakan untuk perkuliahan, sehingga perlu disusun optimasi penjadwalan penggunaan ruangan perkuliahan untuk menghindari  terjadinya constraint atau  ketumpang  tindihan antara satu mata kuliah dan program studi dengan yang lainnya.
Sebelum  melakukan  penerapan  graf  ke  dalam  algoritma, penulis menyusun alur perancangan penelitian sebagai berikut.

## Gambar 1. Alur Penelitian
Langkah  awal  yang  dilakukan  dalam  proses  penelitian  ini ialah mengkaji literatur dari berbagai sumber, baik buku, jurnal, maupun sumber yang lainnya. Setelah dilakukan studi literatur, langkah berikutnya ialah mengumpulkan data mata kuliah dari masing-masing  program  studi  Fakultas  Teknik,  Universitas Katolik  Darma  Cendika.  Fakultas  Teknik  memiliki  empat program  studi,  yakni  Teknik  Industri,  Ilmu  Informatika, Arsitektur, serta Akupuntur dan Pengobatan Herbal. Data mata kuliah  pada  masing-masing  program  studi  ini  nantinya  akan diobservasi terlebih dahulu oleh penulis untuk diperoleh mata
kuliah  mana  yang  saling  tumpang  tindih.  Selanjutnya, dilakukan  pewarnaan  simpul  graf  pada  hasil  representasi  dan diterapkan  ke  dalam  algoritma.  Pewarnaan  simpul  graf merupakan  metode  pemberian  label  pada  setiap  simpul  yang terdapat dalam graf, sehingga tidak ada kemungkinan 2 simpul bertetangga memiliki  warna  yang  sama[11]. Dalam kasus  ini, algoritma  yang digunakan oleh penulis  ialah  algoritma Welch Powell dan algoritma Greedy . Berikutnya, hasil pewarnaan dan penerapan  kedua  algoritma  yang  paling  efisien  dalam  graf diterapkan ke dalam penyusunan jadwal mata kuliah semester genap.
Adapun langkah-langkah penerapan algoritma Welch Powell ialah sebagai berikut.
1. Mencari satu simpul berderajat tertinggi
2. Memberi warna baru pada simpul berderajat tertinggi, diikuti  dengan  simpul  lain  yang  tidak  bertetangga dengan simpul berderajat tertinggi
3. Memberi warna baru pada simpul berderajat tertinggi berikutnya
4. Mengulangi pewarnaan simpul hingga selesai [19].
Untuk  penjabaran  lebih  jelas,  langkah-langkah  penerapan algoritma Welch Powell digambarkan pada flowchart sebagai berikut.
Gambar 2. Flowchart algoritma Welch Powell
Sedangkan,  langkah-langkah  penerapan  algoritma Greedy ialah sebagai berikut.
1. Mengurutkan  simpul-simpul  pada  graf  dari  simpul yang  berderajat  tertinggi  hingga  simpul  berderajat terendah
2. Menentukan  urutan  warna  yang  akan  digunakan, contoh {1,2,3, ... , n }
3. Memilih  simpul  berderajat  tertinggi  pertama  dan memberikan warna 1
4. Memilih  simpul  berderajat  tertinggi  berikutnya  dan memberikan  warna  dengan  urutan  berikutnya  yang
belum diberikan kepada simpul lain yang bertetangga terhadap simpul pertama
5. Mengulangi  langkah  keempat  hingga  semua  simpul terwarnai [17].
Metode yang digunakan dalam penelitian ini ialah metode komparatif  atau  dapat  disebut  sebagai  metode  perbandingan antara  dua  algoritma.  Parameter  yang  digunakan  dalam pengujian penjadwalan mata kuliah ialah efisiensi waktu yang digunakan,  kompleksitas  algoritma,  serta  pengujian  manual dari algoritma Welch Powell dan algoritma Greedy .
1. Parameter efisiensi waktu digunakan untuk memperhitungkan  proses  pengeksekusian  algoritma. Semakin  sedikit  waktu  yang  diperlukan,  maka algoritma  yang  digunakan  semakin  efisien  untuk menyusun penjadwalan.
2. Parameter  kompleksitas  algoritma  bekerja  dengan cara  membandingkan  jumlah  baris  program  yang diterapkan  serta  banyak  langkah  yang  harus dijalankan dalam suatu algoritma.
3. Sedangkan  pengujian  manual  dilakukan  untuk mengetahui tingkat kebenaran hasil pengujian hingga tidak ditemukan adanya constraint pada jadwal mata kuliah [20].
Dalam  penelitian  ini,  komponen  utama  yang  dipilih  oleh penulis untuk menyusun penjadwalan semester genap Fakultas Teknik, Universitas Katolik Darma Cendika ialah mata kuliah serta hari dan jam kuliah dimana mata kuliah direpresentasikan sebagai simpul, sedangkan hari dan jam kuliah direpresentasikan  sebagai  sisi.  Hal  tersebut  dilakukan  karena meninjau  jumlah  mata  kuliah  yang  harus  ditempuh  di Universitas  Katolik  Darma  Cendika  cukup  banyak  dengan jumlah ruangan yang terbatas mengingat proses pembelajaran pada  setiap  program  studi  kedepannya  akan  dilaksanakan secara luring.
Data mata kuliah yang telah diperoleh kemudian direpresentasikan  ke  dalam  bentuk  graf  sebagai  penyebaran simpul.  Simpul  graf  tersebut  dijabarkan  lebih  lanjut  sebagai berikut.

## Gambar 3 Representasi Simpul

## III. H ASIL DAN PEMBAHASAN
Bahasa pemrograman yang diterapkan dalam penelitian ini ialah bahasa pemrograman C++ dan Python dengan kebutuhan perangkat sebagai berikut.
1. Perangkat Keras ( Hardware )
a. Laptop Lenovo B470
b. Processor Intel Core-i3 2350-M
c. RAM 4Gb
2. Perangkat Lunak ( Software )
a. Dev C++
b. Jupyter Notebook
Penelitian  ini  dilakukan  dengan  membandingkan  kinerja terbaik  di  antara  kedua  algoritma,  yakni  algoritma Welch Powell dan algoritma Greedy . Sebelum merepresentasikan sisi dan  simpul  ke  dalam  bentuk  graf,  penulis  terlebih  dahulu menentukan  matriks  ketetanggaan  antara  satu  simpul  dengan simpul  yang  lainnya.  Baris  dan  kolom  pada  matriks  ini menyatakan  sebaran  mata  kuliah.  Penentuan  matriks ketetanggaan  ini  dilakukan  untuk  mencari  nilai  simpul berderajat  tertinggi  dalam  sebuah  graf.  Hasil  dari  penentuan matriks ketetanggan dari jadwal mata kuliah Fakultas Teknik, Universitas  Katolik  Darma  Cendika  disajikan  dalam  tabel  di bawah ini.
Tabel 5 Matriks Adjecency Mata Kuliah 1
Tabel 6 Matriks Adjecency Mata Kuliah 2
Tabel 7 Matriks Adjecency Mata Kuliah 3
Tabel 8 Matriks Adjecency Mata Kuliah 4
Berdasarkan  proses  pencarian  yang  telah  dilakukan, diperoleh hasil bahwa derajat tertinggi matriks adjacency mata kuliah  Fakultas Teknik berada pada nilai 6 (enam) dan derajat terendah berada pada nilai 0 (nol).

## Gambar 4 Representasi Simpul Sisi
Setelah subjek direpresentasikan ke dalam bentuk graf, langkah  berikutnya  ialah  memberi  pewarnaan  pada  setiap simpul.  Representasi  pewarnaan  simpul  graf  dengan menggunakan algoritma Welch Powell ialah sebagai berikut.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1 2 1 3 3 2 1 3 0 5 0 2 3 1 1 3 0 6 2 1 3 2 0 3 0 6 0 0 4 6
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 2 3 2 0 0 1 1 3 0 2 2 0 1 0 2 3 1 1 0 4 1 5 6 2 2 2 3 0 2 3 4 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 2 5 1 1 2 3 0 3 2 5 6 2 2 3 3 3 1 0 5 3 1 3 1 4 6 2 1 3 1 2 4 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 5 6 0 2 2 0 0 2 2 0 1 0 0 0 2 2 0
Gambar 5 Pewarnaan graf Welch Powell
Proses pewarnaan simpul graf menggunakan algoritma Welch Powell diawali dengan,
1. Menentukan  simpul  berderajat  tertinggi  hingga terendah
2. Ambil  salah  satu  LDO  ( Largest  Degree  Ordering ), kemudian  beri  pewarnaan  pada  simpul  tersebut  dan pada simpul lain yang tidak bertetangga dengannya
3. Selanjutnya,  pilih  LDO  kedua,  kemudian  beri pewarnaan  berikutnya  yang  berbeda  dengan  LDO pertama  dan  berikan  pewarnaan  yang  sama  dengan LDO kedua
4. Ulangi langkah ketiga hingga semua simpul terwarnai
Berdasarkan pewarnaan simpul graf  yang telah dilakukan dengan  menggunakan  algoritma Welch  Powell di  atas, diperoleh hasil bahwa warna kromatik subyek terbagi menjadi 7 warna utama, yakni merah, biru, hijau, oranye, ungu, kuning, dan magenta.
Pewarnaan simpul graf pada algoritma Greedy tidak jauh  berbeda  dengan  algoritma Welch  Powell .  Pewarnaan simpul graf dengan algoritma Greedy ialah sebagai berikut.
1. Pilih salah satu LDO (Simpul berderajat tertinggi) dan berikan pewarnaan pada simpul tersebut
2. Pilih LDO kedua, kemudian berikan pewarnaan yang berbeda dengan simpul pertama
3. Ulangi  langkah  pewarnaan  hingga  semua  simpul terwarnai Jika  dalam  algoritma Welch  Powell ,  pewarnaan simpul  graf  dilakukan  berdasarkan  LDO  ( Largest  Degree Ordering )  pertama dan diikuti dengan pemberian warna  yang sama pada simpul yang tidak bertetangga dengan LDO pertama, maka  dalam  algoritma Greedy ,  proses  pewarnaan  graf dilakukan  sesuai  dengan  urutannya  yakni  dimulai  dari  LDO pertama,  LDO  kedua,  LDO  ketiga,  hingga  LDO  terakhir. Dalam  hal  ini,  konsep  tahapan  pada  algoritma Greedy ini bersifat heuristic . Proses  pewarnaan  graf  pada  algoritma Greedy dilakukan berdasarkan LDO pertama. Dalam graf penjadwalan yang  telah  disusun,  derajat  tertinggi  dalam  graf  bernilai  6, dimana simpul-simpulnya terdiri dari simpul 18, 26, 53, 30, 72, 86, dan 94.
1. LDO  pertama  yang  dipilih  oleh  penulis  ialah  simpul 18 yang kemudian diberi warna merah.
2. Proses  pewarnaan  berikutnya  diberikan  pada  LDO kedua yakni simpul 26. Karena simpul 26 bertetangga
dengan  simpul  18,  maka  simpul  26  diberikan  warna yang berbeda, yakni warna biru.
3. Selanjutnya,  ulangi  langkah  kedua  hingga  semua simpul berderajat 6 terwarnai.
4. Apabila  semua  simpul  berderajat  6  telah  habis terwarnai,  proses  berikutnya  ialah  memberikan pewarnaan simpul pada derajat tertinggi setelah 6.
5. Dalam  hal  ini,  simpul  dengan  derajat  tertinggi berikutnya  terdapat  pada  simpul  10  dengan  jumlah derajat 5. Karena simpul 10 tidak bertetangga dengan simpul  18,  maka  simpul  10  boleh  diberikan  warna yang sama dengan LDO pertama, yakni merah.
6. Proses  pewarnaan  terus  dilakukan  hingga  semua simpul dalam graf terwarnai.
Gambar 6 Hasil pewarnaan algoritma Greedy Karena  alur  algoritma Greedy tidak  jauh  berbeda dengan  algoritma Welch  Powell ,  maka  pewarnaan  graf  yang dihasilkan pun juga sama, dimana diperoleh 7 warna utama atau yang biasa  disebut dengan warna kromatik.
Selain melakukan perhitungan manual pada pewarnaan simpul graf, penulis juga menguji kedua algoritma ini  dengan  menggunakan  pemrograman  penjadwalan.  Seperti yang telah dipaparkan sebelumnya bahwa parameter pengujian yang  digunakan  dalam  penelitian  ini  ialah  waktu  eksekusi program, kompleksitas program, serta perhitungan manual.
Gambar 8 Hasil Pewarnaan Welch Powell
Gambar 9 Hasil Pewarnaan Simpul Greedy
Berdasarkan  proses  pengujian  program  yang  telah dilakukan,  diketahui  bahwa  algoritma Welch  Powell dan algoritma Greedy menghasilkan jumlah nilai kromatik dengan simpul  dan  pewarnaan  yang  sama.  Hal  yang  membedakan kedua algortima ini dijabarkan pada Tabel 9 di bawah ini.
Tabel 9 Hasil Pengujian
Proses pengujian program dilakukan sebanyak 3 kali untuk  memperoleh  nilai  rata-rata  maksimum  pada  penerapan algoritma.  Proses  eksekusi  algoritma Welch  Powell dan algoritma Greedy yang  dilakukan  secara  manual  maupun dengan program, memperoleh hasil yang sama dimana bilangan kromatik  yang  dihasilkan  ialah  sebanyak  7  (tujuh)  warna. Berdasarkan perolehan hasil pengujian kedua algoritma, dapat diketahui  bahwa  waktu  pengeksekusian  program  pada algoritma Greedy lebih  cepat  dibandingkan  dengan  algoritma Welch  Powell .  Hal  tersebut  terjadi  karena  dalam  algoritma Welch Powell , inputan data dilakukan setelah program berjalan, sehingga  membutuhkan  waktu  yang  relatif  lebih  lama.  Tidak hanya  dari  segi  waktu,  dari  segi  kompleksitas  program  pun algoritma Greedy lebih unggul  dibandingkan dengan algoritma Welch  Powell dimana  algoritma Greedy terdiri  dari  43  baris program  dan  algoritma Welch  Powell terdiri  dari  147  baris program. Namun, program dari algoritma Welch Powell sendiri dapat menghasilkan luaran yang lebih detail mengenai derajat dari  masing-masing  simpul,  ketetanggan  simpul,  serta informasi  kode  warna  yagn  berfungsi  sebagai  bilangan kromatik.
Ketujuh warna/bilangan kromatik yang telah dihasilkan  dari  pengujian  kedua  algoritma  ini  akan
direpresentasikan  ke  dalam  penggunaan  ruang  kelas  Fakultas Teknik, Universitas Katolik Darma Cendika sebagai berikut.
Tabel 10 Hasil perolehan ruang kelas dengan kedua algoritma Warna Ruang Kelas Merah VL 6A Biru VL 5F Hijau VL 5E Oranye VL 5H Ungu VL 5D
Kuning
VL 6E Magenta VL 5I

## IV. K ESIMPULAN
Berdasarkan  penelitian  yang  telah  dilakukan,  dapat disimpulkan  bahwa  algoritma Welch  Powell dan  algoritma Greedy memiliki  alur  kerja  yang  tidak  jauh  berbeda,  namun dapat  memperoleh  hasil  yang  sama  yaitu  diperoleh  7  (tujuh) warna  utama  atau  yang  biasa  disebut  dengan  warna  kromatik yang selanjutnya diterapkan pada penjadwalan ruang yang akan digunakan  pada  proses  perkuliahan  Fakultas  Teknik, Universitas  Katolik  Darma  Cendika.  Dalam  perhitungan manual,  algoritma Greedy memiliki  alur  kerja  yang  sedikit lebih  lama  karena  sifat  kerja  yang heuristic dimana  setiap simpulnya  harus  diwarnai  satu  persatu  berdasarkan  simpul berderajat  tertinggi.  Namun,  dari  segi  program,  algoritma Greedy lebih  unggul  dibandingkan  dengan  algoritma Welch Powell , baik dari segi waktu pengeksekusian program maupun kompleksitas  program.  Hal  tersebut  dapat  terjadi  karena, inputan data dalam algoritma Welch Powell dilakukan setelah program berjalan, sehingga membutuhkan waktu eksekusi yang lebih  lama  dibandingkan  dengan  algoritma Greedy .  Tetapi, luaran  yang  dihasilkan  oleh  algoritma Welch  Powell lebih mendetail dibandingkan dengan algoritma Greedy .

## R EFERENSI
[1]
K.  Harianto and  T. S. Eiva Fatdha, “Penerapan Pewarnaan Simpul Graf  untuk  Menentukan  Jadwal  Ujian  Skripsi  pada  STMIK  Amik Riau  Menggunakan  Algoritma  Welch-powell,” SATIN  -  Sains  dan Teknol. Inf. , vol. 1, no. 2, p. 48, 2016, doi: 10.33372/stn.v1i2.27.
[2] A. N. Silitonga and D. Apdillah, “Penjadwalan Perkuliahan Dengan Metode Vertex  Graph Coloring  Dan  Simulated Annealing,” J.  Ind. Manuf. Eng. , vol. 1, no. 2, p. 56, 2019, doi: 10.31289/jime.v1i2.2328.
[3] Y.  Rusdiana  and  A.  Maulani,  “Algoritma  Welch-Powell  Untuk Pewarnaan Graf pada Penjadwalan Perkuliahan,” Sci. Phys. Educ. J. , vol. 3, no. 1, pp. 37–47, 2019, doi: 10.31539/spej.v3i1.915.
[4] D.  Hendrikx et  al. ,  “Using  graph  theory  to  assess  the  interaction between  cerebral  function,  brain  hemodynamics,  and  systemic variables  in  premature  infants,” Complexity ,  vol.  2018,  2018,  doi: 10.1155/2018/6504039.
[5] a. W. Lund et al. , “Quantification of spatial parameters in 3D cellular constructs  using  graph  theory,” J.  Biomed.  Biotechnol. ,  vol.  2009, 2009, doi: 10.1155/2009/928286.
[6] R.  Oddang  and  H.  Hamrul,  “Pembangunan  Sistem  Penjadwalan Kuliah  Menggunakan  Algoritma  Pewarnaan  Graf,” J.  Ilm. d’ComPuterE , vol. 1, pp. 50–55, 2011.
[7] B.  Muflikhudin  and  D.  Pratama,  “Teknik  Pewarnaan  Graf  Pada Penjadwalan Piket Osis Dengan Algoritma Welch-Powell Pada Smp Negeri 2 Kemranjen,” FUSIOMA (Fundamental Sci. J. Math. , vol. 1, no. 2, pp. 8–13, 2021, [Online]. Available: https://jurnal.unupurwokerto.ac.id/index.php/fusioma/article/view/1 4. Percobaan 1 (detik) Percobaan 2 (detik) Percobaan 3 (detik) Rata-rata (detik) Welch Powell 1164 1311 849.6 1108.2 147 baris Greedy 0.001 0.001 0.00009 0.000696667 43 baris
Algoritma
Parameter Penguji Waktu Pengeksekusian Kompleksitas algoritma
[8] L.  Maro  and  L.  K.  S.  Purab,  “Penerapan  Konsep  Pewarnaan  Graf dalam  Penyusunan  Jadwal  Perkuliahan  Menggunakan  Metode Algoritma  Welch-Powell  pada  Program  Studi  Teknik  Informatika Fakultas  Matematika  dan  Ilmu  Pengetahuan  Alam  Universitas Tribuana Kalabahi,” J. Wahana Pendidik. , vol. 07, no. 06, pp. 193 – 197, 2021, doi: 10.5281/zenodo.5574383.
[9] F.  Mahardika  and  H.  Marcos,  “Penerapan  Algoritma  Graf  Welch Powel  pada  Penjadwalan  Mata  Kuliah  dan  Jadwal  Asisten  Study Kasus Forum Asisten STMIK AMIKOM Purwokerto,” Simetris  J. Tek. Mesin, Elektro dan Ilmu Komput. ,  vol. 8, no. 2, p. 825,  2017, doi: 10.24176/simet.v8i2.1208.
[10] a. M. Nasir, Faisal, and Dedy Setyawan, “Optimalisasi Penjadwalan Mata Kuliah Menggunakan Teori Pewarnaan Graf,” Prox. J. Penelit. Mat.  dan  Pendidik.  Mat. ,  vol.  5,  no.  1,  pp.  57–69,  2022,  doi: 10.30605/proximal.v5i1.1398.
[11] M.  Mahmudah  and  T.  N.  Irawati,  “Aplikasi  Pewarnaan  Graf Terhadap Pembuatan Jadwal Ujian Semester di Jurusan Pendidikan Matematika Universitas Islam Jember,” Kadikma , vol. 9, no. 2, pp. 12–21, 2018.
[12] Y.  Xiao,  G.  Dong,  and  X.  Song,  “Data-Based  Reconstruction  of Chaotic Systems by Stochastic Iterative  Greedy Algorithm,” Math. Probl. Eng. , vol. 2020, 2020, doi: 10.1155/2020/6718304.
[13] E. Al Farisi, Olief Ilmandira Ratu, “Penerapan Pewarnaan Graf pada Penjadwalan  Mengajar  Dosen  Pendidikan  Matematika  Universitas Nurul  Jadid,” J.  Mat. ,  vol.  11,  no.  1,  pp.  10–19,  2021,  doi:
10.24843/JMAT.2021.v11.i01.p132.
[14] Y.  Shao,  S.  Chu,  T.  Zhang,  Y.  J.  Yang,  and  T.  Yu,  “A  Greedy Sampling  Design  Algorithm  for  the  Modal  Calibration  of  Nodal Demand  in  Water  Distribution  Systems,” Math.  Probl.  Eng. ,  vol. 2019, 2019, doi: 10.1155/2019/3917571.
[15] Y.  Zhu,  Q.  Chen,  J.  Liu,  and  X.  Tian,  “Fast  Adaptive  Character Animation Synthesis Based on Greedy Algorithm,” Complexity , vol.
2021, pp. 1–11, 2021, doi: 10.1155/2021/6685861.
[16] P.  Lu,  T.  Hu,  H.  Wang,  R.  Zhang,  and  G.  Wu,  “G-CAS:  Greedy Algorithm-Based  Security  Event  Correlation  System  for  Critical Infrastructure  Network,” Secur.  Commun.  Networks ,  vol.  2021, 2021, doi: 10.1155/2021/3566360.
[17] A. P. Rahadi, “Penjadwalan Mata Kuliah Menggunakan Pewarnaan Graf Dengan Algoritma  Largest First,” J.  Padegogik ,  vol. 2, no. 1, pp. 1–13, 2019.
[18] R. Syam, H. Ihsan, and a. Asman, “Aplikasi Pewarnaan Graf dengan Algoritma Recursive Largest First pada Penjadwalan Mata Kuliah,”
J.  Math.  Comput.  Stat. ,  vol.  2,  no.  1,  p.  63,  2020,  doi: 10.35580/jmathcos.v2i1.12461.
[19] S. Astuti, “Penyusunan Jadwal Ujian Mata Kuliah dengan Algoritma Pewarnaan Graf Welch Powell,” J. Dian , vol. 11, no. 1, pp. 68–74,
2011, [Online]. Available: publikasi.dinus.ac.id.
[20] Niarama,  B.  Pramono,  and  L.  .  Tajidun,  “Aplikasi  penjadwalan menggunakan  algoritma  welch  powell  (studi  kasus :  sma muhammadiyah kendari),” semanTIK , vol. 4, no. 1, pp. 1–6, 2018.
This is an open access article under the CC–BY-SA license.