Volume 3, Nomor 1, Desember 2019 e-ISSN : 2598-2567 p-ISSN : 2614-0195 DOI : https://doi.org/10.31539/spej.v3i1.915

## ALGORITMA WELCH-POWELL UNTUK PEWARNAAN GRAF PADA PENJADWALAN PERKULIAHAN
Yulianti Rusdiana 1 , Alfi Maulani 2 Universitas Pamulang 1,2
yulianti.rusdiana@gmail.com 1
Submit , 31-10-2019 Accepted , 27-12-2019 Publish , 28-12-2019
Abstract: scheduling  is  a  principal  administrative  activity  in  most  universities.  The  problem  that  often faced is the lecture timetable and course distribution are still manually and have not fully paid attention to the field of science that matches the interests of the lecturer. To overcome these problems, the authors use  Welch-Powell's  algorithm  to  arrange  lecture  arrangement  schedules  with  expectations  that  the scheduling  will  be  faster  and  optimal  and  more  satisfying  to  various  parties.  The  results  of  applying Welch-Powell's Algorithm to the willingness of lecturers to teach available courses provide four colors. The results are used to map lecturers and subjects that are supported by class availability to ensure that lecturers  with the same course choices must  be placed in  different  classes. In meeting class needs, one lecturer can handle several subjects, and several lecturers can teach one subject. The results of applying the Welch-Powell Algorithm to the suitability of teaching time give 29 colours. These results are used to map  lecture  time  to  ensure  that  lecturers  with  the  same  choice  of  time  should  be  provided  in  different classes.
Keywords: Vertex, Colouring,  Welch-Powell's algorithm
Abstrak: Penjadwalan  adalah  kegiatan  administratif  utama  di  sebagian  besar  universitas. Permasalahan yang sering dihadapi adalah pengaturan waktu perkuliahan dan pembagian mata kuliah masih dilakukan secara manual dan belum sepenuhnya memperhatikan bidang ilmu yang diminati dosen dan kesediaan dosen. Untuk mengatasi permasalahan tersebut, penulis menggunakan algoritma Welch- Powell  untuk  menyusun  jadwal  pengaturan  perkuliahan  dengan  harapan  penjadwalan  yang  dilakukan nantinya  akan  lebih  cepat  dan  optimal  serta  lebih  memuaskan  berbagai  pihak.  Hasil  penerapan Algoritma Welch-Powell terhadap kesediaan dosen mengampu matakuliah yang tersedia memberikan 4 warna  Hasil  tersebut  digunakan  untuk  memetakan  dosen  dan  matakuliah  yang  diampu  dengan ketersediaan  kelas  untuk  memastikan  bahwa  dosen  dengan  pilihan  matakuliah  yang  sama  harus ditempatkan  di  kelas  yang  berbeda.  Dalam  pemenuhan  kebutuhan  kelas,  satu  dosen  dapat  mengampu beberapa  mata  kuliah  dan  satu  mata  kuliah  dapat  diampu  oleh  beberapa  dosen.  Hasil  penerapan Algoritma Welch-Powell terhadap kesediaan waktu mengajardosen memberikan 29 warna Hasil tersebut digunakan untuk memetakan  waktu  perkuliahan untuk memastikan bahwa dosen dengan pilihan  waktu yang sama harus ditempatkan di kelas yang berbeda.
Kata Kunci: Vertex, Colouring,  Welch-Powell's Algorithm

## PENDAHULUAN
Penjadwalan adalah
bentuk pengambilan  keputusan  yang  memainkan peran  penting  dalam  banyak  disiplin  ilmu.
Penjadwalan  yang  dimaksudkan  dalam tulisan ini dimaksudkan sebagai pengaturan waktu  (timetabling).  Petrovic  &  Burke menyatakan pengatur waktu sebagai masalah penempatan sumber daya tertentu, tunduk  pada  kendala,  ke  dalam  sejumlah slot  waktu  terbatas  dan  tempat-tempat
dengan tujuan untuk memenuhi serangkaian tujuan yang dinyatakan sampai batas yang setinggi mungkin.
Di  dunia  pendidikan,  penjadwalan atau  pengaturan  waktu  penting  untuk dilakukan dengan tujuan untuk mengoptimalkan  organisasi  proses  belajar mengajar  berkaitan  dengan  pengalokasian sumber  daya  yang  sesuai  dengan  bidang ilmu  dan  kesediaan  waktu  yang  dimiliki oleh  sumber  daya  tersebut  sebagai
kendalanya. Pengaturan waktu perkuliahan terdiri dari dua jenis kendala, yakni kendala keras  dan  kendala  lunak.  Kendala-kendala keras  ditegakkan  secara  kaku  oleh universitas  dan  karenanya,  harus  dipenuhi. Solusi yang tidak melanggar batasan keras disebut  solusi  yang  layak  ( feasible ). Kendala  keras  yang  umum  adalah  sebagai berikut:  1)  tidak  ada  orang  yang  dapat dialokasikan  untuk  berada  di  lebih  dari satu  tempat  pada  satu  waktu,  2)  total sumber  daya  yang  dibutuhkan  dalam setiap  periode  harus  dapat  dipenuhi  oleh sumber daya yang tersedia.
Kendala  lunak  adalah  hal-hal  yang diinginkan  untuk  memuaskan,  tetapi  hal tersebut  tidak  terlalu  penting.  Dalam masalah  pengaturan  jadwal  universitas  di dunia nyata, biasanya tidak mungkin untuk memenuhi  semua  kendala  lunak.  Kualitas jadwal yang layak dapat dinilai berdasarkan  pada  seberapa  baik  kendala lunak dipenuhi. Namun, beberapa masalah sangat rumit sehingga sulit untuk menemukan  bahkan  solusi  yang  layak. (Petrovic & Burke, 2004)
Penjadwalan adalah kegiatan administratif  utama  di  sebagian  besar universitas.  Tak  terkecuali  di  Universitas pamulang khususnya program studi Matematika, pengaturan waktu perkuliahan selalu dihadapi manajemen setiap semester. Selama ini, meskipun  kendala  keras  selalu terpenuhi,  pengaturan  waktu  perkuliahan dan  pembagian  mata  kuliah  masih dilakukan  secara  manual  dan  belum sepenuhnya  memperhatikan  bidang  ilmu yang  diminati  dosen  dan  kesediaan  waktu dosen  sehingga  belum  memperhatikan kendala lunak. Hal tersebut mengakibatkan jadwal yang dihasilkan kurang efektif yang dibuktikan  dengan  adanya  beberapa  dosen yang  meminta  mundur  dari  tugas  yang diberikan dan digantikan dengan dosen lain disebabkan  oleh  ketidaksesuaian  dengan bidang  minat  dosen  maupun  kesediaan waktu dosen. Selain itu, adanya perubahan jadwal  perkuliahan  yang  dibuat  dan disepakati sendiri oleh dosen dan
mahasiswa pada mata kuliah yang diampu di  minggu  pertama  perkuliahan  untuk memindahkan  waktu  perkuliahan  sesuai dengan  kesediaan  waktu  yang  dimiliki dosen.
Untuk  mengatasi  permasalahan tersebut, diperlukan langkah atau mekanisme  penjadwalan  yang  tepat  dan optimal. Banyak metode maupun algoritma yang  dapat  digunakan  untuk  membuat penjadwalan. Penelitian tentang penjadwalan  kuliah  dengan  menggunakan metode  constrains  programming  dan simulated annealing pernah dilakukan oleh (Rochman,  2012);  penelitian  tentang penyusunan  jadwal  kuliah  di  perguruan tinggi dengan metode tabu search (pencarian  terlarang)  disusun  oleh  (Sahid, 1998);  dan penelitian tentang Penjadwalan Matakuliah Menggunakan Pewarnaan Titik Pada  Graf  oleh  (Syauqi  &  Syafwan). Beberapa  penelitian  yang  telah  disebutkan tersebut berasal dari berbagai disiplin ilmu seperti  riset  operasi, artificial  intelegence maupun computational intelegence (Rochman, 2012).
Dalam  disiplin  ilmu  komputasi, terdapat pewarnaan graf sebagai salah satu metode  penjadwalan.  Salah  satu  algoritma yang  dapat  digunakan  adalah  algoritma Welch-Powell.“Algoritma  Welch  Powell merupakan salah satu algoritma pewarnaan graf yang melakukan pewarnaan berdasarkan  derajat  tertinggi  dari  simpul- simpulnya  atau  disebut  Largest  Degree Ordering  (LDO)  yaitu  dengan  melakukan pewarnaan  berdasarkan  derajat  besar  ke derajat kecil dan menggunakan satu warna untuk  mewarnai  simpul  pertama  dan simpul berikutnya yang tidak berdampingan  dengan  simpul  pertama  dan seterusnya”  (S,  Rosely,  &  Mayadewi, 2016)
Dalam tulisan ini, penulis menggunakan  algoritma  Welch  Powell untuk  menyusun  jadwal  pengaturan  waktu perkuliahan pada program studi Matematika  Universitas  Pamulang  dengan harapan  penjadwalan  yang  dilakukan
nantinya akan lebih cepat dan optimal serta lebih  memuaskan  berbagai  pihak  yang menggunakan hasil dari penelitian ini.

## KAJIAN PUSTAKA Graf
Berikut  ini  diberikan  pengertian dasar graf  yang meliputi pengertian graf itu sendiri, sifat bertetangga, walk, trail, path,  lingkaran,  jarak serta derajat. Deﬁnisi  2.1. (Chartrand & Lesniak,  1996) Suatu  graf adalah himpunan  tak  kosong  berhingga  simpul yang  disebut simpul dan himpunan merupakan  himpunan pasangan  tidak  berurutan  dari  anggota- anggota yang disebut busur. Setiap graf harus memuat minimal sebuah simpul, tetapi dimungkinkan  tidak  mempunyai  busur. Graf  yang  himpunan  busurnya  adalah himpunan kosong dinamakan graf kosong  atau  null  graph.  Banyaknya simpul  pada  suatu  graf  disebut  dengan order,  sedangkan  banyaknya  busur  pada suatu graf disebut dengan size.
Deﬁnisi 2.2. (Chartrand.G, 1977)
Jika dan adalah  sembarang  dua simpul  dari  graf yang  dihubungkan oleh  busur ,  dinotasikan , maka  dikatakan dan adalah  simpul yang saling bertetangga.
Gambar 1 Graf
Gambar 1 menunjukkan  bahwa simpul dan saling  bertetangga, sedangkan simpul dan tidak saling bertetangga. Deﬁnisi  2.3. (Chartrand  & Lesniak,  1996)  Suatu walk  dari
graf adalah  barisan  bergantian  antara simpul  dan  busur  yang  dimulai  dari simpul dan  berakhir  di  simpul , sehingga untuk dengan . Suatu trail  adalah walk  dengan tidak mengulang sembarang busur. Suatu path adalah walk yang tidak mengulang sembarang simpul. Contoh walk  dari  graf pada Gambar 1 yaitu . Contoh trail adalah .  Contoh path adalah . Deﬁnisi 2.4. (Chartrand.G, 1977) Suatu trail dengan , paling
sedikit  terdiri  dari simpul  disebut sirkuit.  Sirkuit  yang  tidak  mengulang sembarang simpul disebut lingkaran.
Contoh  sirkuit  pada  Gambar  1 yaitu
. Sedangkan contoh lingkaran dari graf yaitu
.
Deﬁnisi  2.5. (Kusmayadi,  2011)
Jarak  dari  simpul ke di adalah panjang  lintasan  (path)  terpendek  dari simpul ke ,  dinotasikan  dengan .  Jika  tidak  ada  lintasan  yang menghubungkan  simpul dan ,  maka .  Berdasarkan  Deﬁnisi  2.5, jarak  simpul ke dalam  Gambar  1 adalah . Deﬁnisi  2.6. (Chartrand  & Lesniak,  1996)  Derajat  dari  simpul di graf adalah  banyaknya  sisi  di yang bersisian ( incident ) dengan , dinotasikan dengan
Simpul  yang  berderajat  genap disebut  simpul  genap  dan  simpul  yang berderajat  ganjil  disebut  simpul  ganjil. Simpul  yang  berderajat  nol  disebut isolated  vertices dan  simpul  yang
berderajat  satu  disebut  simpul  ujung. Berikut  diberikan  contoh  graf yang akan ditentukan derajat simpulnya.
Gambar 2 Graf Berdasarkan Gambar 2, diperoleh bahwa
. Simpul dan adalah  simpul  ujung,  simpul dan adalah simpul genap.
Pewarnaan Graf Misalkan adalah  graf  dan 𝑘 adalah  bilangan  bulat  positif.  Suatu pewarnaan- 𝑘 untuk  graf adalah  cara mewarnai  setiap  simpul  pada  graf dengan 𝑘 warna  sedemikian  sehingga setiap dua simpul yang bertetangga tidak mempunyai warna yang sama.
Bilangan Kromatik ( Chromatic Number ) Suatu graf dikatakan mempunyai bilangan kromatik
( chromatic  number ) 𝑘 atau  kromatik- 𝑘 ( 𝑘 - chromatic )  apabila  graf dapat diwarnai  dengan 𝑘 -warna,  tetapi  tidak dengan 𝑘 -warna. Bilangan
Kromatik  ( chromatic  number )  dari  graf dinyatakan  dengan  symbol  ( )  adalah jumlah warna minimum yang digunakan untuk  mewarnai  setiap  simpul  pada  graf sedemikian sehingga setiap dua simpul yang  bertetangga  tidak  mempunyai warna yang sama. Pada  graf  kosong dapat langsung ditentukan bilangan kromatiknya  yaitu karena setiap  simpul  tidak  bertetangga,  maka simpul-simpul  di  graf  kosong  dapat diwarnai  dengan  satu  warna  saja.  Pada graf  lengkap karena
setiap simpul saling bertetangga sehingga  simpul-simpul  dapat  diwarnai dengan warna.  Sedangkan  pada  graf bipartit , warna pertama  untuk  simpul-simpul  di dan warna kedua untuk simpul-simpul di , karena  semua  simpul-simpul  di dan juga tidak saling bertetangga. Algoritma Welch Powell Algoritma Welch-Powell
diperlukan  dalam  pewarnaan  simpul suatu  graf  berdasarkan  derajat  tertinggi dari semua simpulnya. Algoritma Welch- Powell termasuk dalam algoritma
Greedy. Algoritma Greedy selain algoritma Welch-Powell adalah algoritma  Kruskal’s  dan  algoritma Prim’s. Algoritma Welch-Powell
merupakan  cara  yang  efisien  dalam pewarnaan  graf .  Langkah-langkah
dalam  algoritma Welch-Powell sebagai berikut:
1. Urutkan  simpul-simpul  dari  graf dalam derajat yang menurun. Urutan ini  mungkin  tidak  unik  karena beberapa simpul mungkin mempunyai derajat yang sama.
2. Gunakan satu warna untuk mewarnai simpul  pertama  (yang  mempunyai derajat  tertinggi)  dan  simpul-simpul lain  (dalam  urutan  yang  berurut) yang tidak bertetangga dengan simpul pertama ini.
3. Ulangi  langkah  2  di  atas  untuk simpul  dengan  urutan  tertinggi  yang belum diwarnai.
4. Ulangi  penambahan  warna-warna sampai semua simpul telah diwarnai.

## Pewarnaan  Simpul  dengan  Algoritma
Welch-Powell Seperti pada penjelasan
sebelumnya,  misalkan adalah  graf sederhana.  Suatu  pewarnaan- 𝑘 graf merupakan  pemakaian  sebagian  atau semua 𝑘 warna  untuk  mewarnai  setiap simpul  pada  graf sehingga  setiap  dua simpul  yang  bertetangga  diberi  warna
yang  tidak  sama.  Graf dikatakan dapat  diwarnai  dengan 𝑘 -warna  ( 𝑘 - Colourable )  apabila  graf mempunyai pewarnaan- 𝑘 .  Representasi  pemberian warna  pada  simpul  dapat  menggunakan angka atau warna misalnya merah, hijau, biru, kuning dan lain-lain. Permasalahan utama  dalam  pewarnaan  simpul  adalah menentukan jumlah warna yang seminimal mungkin. Jumlah warna yang paling  minimal  ini  dikatakan  sebagai bilangan kromatik.

## METODE PENELITIAN
Penelitian  ini  akan  dilaksanakan dalam  waktu  kurang  lebih  6  (enam) bulan  sejak  ditanda  tanganinya  kontrak perjanjian  penelitian.  Sebagai  lokasi penelitiannya di Program Studi Matematika Universitas Pamulang.
Adapun  metode  yang  dilakukan  dalam penelitian ini adalah sebagai berikut:
1. Studi  Literatur.  Pada  tahap  ini dilakukan  pengumpulan  materi  yang digunakan  menjadi  dasar  teori  untuk memperoleh  deskripsi  yang  lebih jelas  mengenai  pengaturan  waktu (timetabel), Algoritma Welch Powell, pewarnaan Graph.
2. Pengumpulan Data. Data yang digunakan dalam penelitian ini adalah daftar  pengampu  matakuliah  dan kesediaan  mengajar  dosen  Program Studi Matematika Univesitas Pamulang  untuk  semester  Ganjil 2017-2018. 3. Pemanfaatan Algoritma. Dalam memanfaatkan dan mengimplementasikan metode algoritma  welch  powell  terhadap masalah  yang  dihadapi  diperlukan data  berupa  graf.  Data  yang  ada belum  dalam  bentuk  graf,  sehingga perlu dilakukan konversi data.
Konversi  data  yang  diperoleh  dengan
membentuk  data  tersebut  menjadi tabel daftar pengampu matakuliah dan tabel  kesediaan  mengajar  bernilai dan yang  mengimplementasikan bahwa pada tabel pengampu matakuliah akan bernilai 1 jika dosen bersedia  atau  bidang  keahliannya merupakan  matakuliah  tersebut  dan akan  bernilai  0  jika  dosen  tidak bersedia  atau  bidang  keahlian  dosen bukan matakuliah tersebut.
4. Implementasi Hasil. Selanjutnya,
setelah  terbentuk  tabel  pengampu matakuliah,  tabel  tersebut  dikonversi menjadi matriks dengan vertex berupa nama  dosen.  Hubungan  antar  vertex tersebut  disimbolkan  dengan  angka  1 jika  antara  dua  dosen  mengampu matakuliah  yang  sama  dan  angka  0 jika  antara  dua  dosen  mengampu matakuliah  yang  berbeda.  Hasil penerapan  algoritma Welch-Powell untuk  matriks  pengampu  matakuliah dijadikan  dasar  pertimbangan  untuk menentukan  kombinasi  dosen  dan matakuliah  yang  diampu.  Kombinasi dosen  dan  matakuliah  yang  diperoleh akan dipetakan menjadi jadwal penempatan  kelas  dosen  dengan matakuliah yang diampu.

## HASIL PENELITIAN
Penyebaran permohonan mengajar dosen memberikan data pengampu  matakuliah  yang  tersedia pada  semester  yang  diteliti  dan  data kesediaan waktu mengajar dosen. Dalam data  tersebut,  terdapat  beberapa  dosen yang pada semester yang diteliti mengajukan  cuti  dan  tidak  mengampu matakuliah apapun, ada pula dosen yang bersedia  menyesuaikan  jadwal  dan ditempatkan  dimanapun  di  semua  waktu yang  tersedia.  Selain  itu,  kesediaan  dan
keahlian  yang  diminati  dosen  terhadap matakuliah juga dipertimbangkan,
dengan mempertimbangkan pula kelengkapan  kebutuhan  matakuliah  di semester  yang  diteliti  dengan  kesediaan dosen. Dosen yang menyatakan kesediaan tanpa menyebutkan jam kesediaan  diartikan  bersedia  di  semua waktu  pada  hari  tersebut  dengan pembagian  waktu  perkuliahan  pagi  dan waktu  perkuliahan  malam.  Dosen  yang sedang  cuti  atau  mengampu  matakuliah yang  tidak  tersedia  pada  semester  yang diteliti tidak ditampilkan. Untuk
mempermudah  pengamatan,  data  yang telah diperoleh disajikan dalam tabel 1 Tabel 1 menyatakan hubungan antara dosen  dengan  matakuliah  yang  diampu. Jika bernilai 1 artinya dosen memberikan kesediaan  mengampu  matakuliah    atau matakuliah tersebut sesuai dengan minat dan  keahlian  dosen.  Sedangkan  apabila bernilai  0  artinya  dosen  tidak  bersedia mengampu  mata  kuliah  tersebut  atau tidak  sesuai  dengan  minat  dan  keahlian dosen.
Tabel 1 Daftar Pengampu Matakuliah Semester Ganjil 2017-2018 Program Studi
Semester Mata Kuliah Pendidikan  Kewarganegaraan 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 Bahasa Indonesia 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 Kalkulus I 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 Kimia Dasar 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 Bahasa Inggris I 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 Fisika Dasar I 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 Praktikum Fisika Dasar I 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
Pengantar Teknologi Informasi
0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Trigonometri 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 Probabilitas 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Teori Bilangan 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 Matematika Diskrit I 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Algoritma & Pemrograman 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Praktikum Algoritma & Pemrograman 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Teknik Lingkungan 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Aljabar Linier & Matriks 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 Geometri Datar 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 Bahasa Inggris III 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 Program Linier 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 Geometri Analitik 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 Statistik Matematika II 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 Aljabar Abstrak Lanjutan 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
Praktikum Pemodelan Matematika
0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 Analisis Nyata I 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 Persamaan Diferensial Parsial 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Teori Graf 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 Pemodelan Matematika 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 Kewirausahaan 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Metode Penelitian 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Sistem Informasi Manajemen 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Statistik Non Parametrik 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Oprasi Riset
0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 Statistik Pengendalian Kualitas 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Asuransi 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Analisis Kompleks 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
3 5
7
Yu lia nt i Ru sd ia na
A gu st in a d ya h s
D iya h I is A nd ria ni
w iw it ku rn ia w an
Ju fr in ald i Re rin M au lin da N un un g K us da niya m a N in a V alen tik a N ur uli ta S ar i R. A dit am a Ta ba h H er i S et ia w an U sep R ah m at Ch oer ul Ba sir D ew i P ur na m a S ar i G er ry Sa st ro
Ilm ad i Ir va na A ro fa h
N an ik Id a R os in i A lfi M au la ni A nd i N ur R ah m an Be ss e A rn aw is ud a N in gs i 1
Tahapan selanjutnya dalam proses  penelitian  adalah  merubah  tabel pengampu  matakuliah  ke  dalam  bentuk matriks graf ketetanggaan dengan vertexnya  adalah  nama  dosen.  Hasil konversi  Tabel  1  adalah  matriks  berikut ini
Sebelum  pemetaan  kombinasi dosen  dan  matakuliah  yang  diampu, terlebih  dahulu  diamati  keterhubungan antara dosen dengan matakuliah. Dengan adanya  pengamatan  ini  akan  menjadi pertimbangan dalam penempatan kombinasi  matakuliah  dan  penempatan kelas. Hasil penerapan Algoritma Welch- Powell terhadap kesediaan  atau keahlian dosen  mengampu  matakuliah  yang tersedia  memberikan  4  warna  dengan pengelompokan  titik  terhadap  warnanya ditampilkan  dalam  Tabel  2.  Hasil tersebut  digunakan  untuk  memetakan dosen  dan    matakuliah  yang  diampu dengan ketersediaan kelas untuk memastikan bahwa dosen dengan pilihan matakuliah yang sama harus ditempatkan di kelas yang berbeda. Tabel 2 Pengelompokan Warna w1 w2 w3 w4 v7 v8 v1 v10 v16 v2 v5 v6 v11 v12 v14 v3 v13 v15 v4 v17 v9 v19 v18 v20
v21
Hasil  pewarnaan  diterapkan  pada tabel kesediaan dosen mengampu matakuliah  disajikan  dalam  Gambar  3. Berdasarkan  pewarnaan  tersebut,  dapat terlihat  bahwa  beberapa  dosen  yang memilih  mengampu  mata  kuliah  yang sama  mendapatkan  perbedaan  warna yang artinya jika dosen tersebut mendapatkan  mata  kuliah  yang  sama maka  tidak  dapat  ditempatkan  dalam kelas  yang  sama.  Jika  dosen  yang bersangkutan  mengajar  di  kelas  yang sama,  harus  mengampu  mata  kuliah yang  berbeda.  Dari  tabel  tersebut,  dapat pula  terlihat  bahwa  pemilihan  nama dosen  yang  mengampu  di  kelas  yang sama  dengan  mata  kuliah  berbeda  dapat dipertimbangkan  dari  nama-nama  dosen yang memiliki kesamaan warna.
Setelah pengamatan terhadap kesediaan  mengampu  mata  kuliah, dibuatlah  kombinasi  dosen  dan  mata kuliah  yang  diampu.  Untuk  memenuhi kebutuhan  kelas,  satu  dosen  dapat mengampu  beberapa  mata  kuliah  dan satu  mata  kuliah  dapat  diampu  oleh beberapa  dosen.  Masing-masing  hasil kombinasi  dosen  dan  mata  kuliah diterapkan  ke  dalam  pembagian  kelas sesuai dengan kelas dan matakuliah yang tersedia.
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 v20 v21 v1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 v2 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 v3 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 v4 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 v5 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 v6 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 v7 1 0 0 0 1 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 v8 1 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 0 0 0 0 0 v9 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 v10 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 v11 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 v12 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
v13 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 v14 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 v15 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 v16 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 v17 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 v18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 v19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 v20 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 v21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Gambar 3 Pewarnaan data dosen pengampu matakuliah
Proses pengelompokan kelas dilakukan  berdasarkan  pertimbangan pewarnaan kesediaan mengampu matakuliah.  Ketersediaan  kelas  terbagi berdasarkan  dua  waktu  perkuliahan, yaitu kelas pagi dan kelas malam. Selain pertimbangan kesamaan warna, pertimbangan  penting  berikutnya  adalah kesesuaian  dengan  bidang  keahlian dosen  dan  kesediaan  waktu  mengajar kelas  pagi  dan/atau  kelas  malam.  Dosen yang  memiliki  keahlian  sesuai  dengan matakuliah yang
dipilih lebih diutamakan.
Hasil kombinasi dosen dan matakuliah  yang  diampu  dari  semua kelas dan berdasarkan kesediaan matakuliah  yang  dipilih  dosen  di
semester  ganjil  diperoleh  sebanyak  67 simpul.
Dari  67  simpul  kombinasi  dosen dan matakuliah dan berdasarkan kesediaan mengajar yang telah diberikan dosen,  terdapat  beberapa  dosen  yang memiliki  waktu  yang  fleskibel  atau menyesuaikan  keputusan  dan  dapat ditempatkan  di  waktu  manapun.  Untuk menyederhanakan  matriks  kesediaan, dosen  yang  memiliki  waktu  fleksibel tersebut  dimunculkan  sebagai  simpul akan  tetapi  kesediaan  mengajarnya sementara  dinolkan  yang  artinya  tidak terkendala  waktu  manapun.  Setelah diterapkan  dalam  algoritma  Welch Powell  diperoleh  29  warna yang disajikan dalam Tabel 3
w3 w2 w1 w1 w3 w4 w1 w2 w1 w4 w1 w2 w2 w3 w3 w1 w2 w1 w2 w2 w1 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 v20 v21 1 Pendidikan  Kewarganegaraan 1 1 Bahasa Indonesia 1 Kalkulus I 1 1 1 Kimia Dasar 1 1 Bahasa Inggris I 1 1 Fisika Dasar I 1 1 Praktikum Fisika Dasar I 1 1 Pengantar Teknologi Informasi 1 1 Trigonometri 1 1 3 Probabilitas 1 1 Teori Bilangan 1 1 Matematika Diskrit I 1 1 Algoritma & Pemrograman 1 1 1 Praktikum Algoritma & Pemrograman 1 1 1 Teknik Lingkungan 1 1 Aljabar Linier & Matriks 1 1 1 1 Geometri Datar 1 1 Bahasa Inggris III 1 5 Program Linier 1 1 Geometri Analitik 1 1 Statistik Matematika II 1 Aljabar Abstrak Lanjutan 1 1 Praktikum Pemodelan Matematika 1 1 1 Analisis Nyata I 1 Persamaan Diferensial Parsial 1 1 Teori Graf 1 1 Pemodelan Matematika 1 1 1 7 Kewirausahaan 1 Metode Penelitian 1 Sistem Informasi Manajemen 1 Statistik Non Parametrik 1 Oprasi Riset 1 1 1 Statistik Pengendalian Kualitas 1 Asuransi 1 Analisis Kompleks 1
semester mata kuliah
Tabel 3 Pengelompokan warna berdasarkan simpul kombinasi dosen dan mata kuliah dengan kesediaan waktu mengajar.
Berdasarkan penyajian warna
tersebut, w1 memiliki anggota terbanyak karena  dosen  dengan  kesediaan  yang fleksibel  atau  yang  nilainya  dinolkan sehingga  tidak  bertetangga  dengan simpul  manapun  akan  masuk  ke  warna w1  (satu  warna  dengan  simpul  yang memiliki derajat tertinggi).
Dengan pertimbangan kesediaan hasil pewarnaan  mata  kuliah  dan  pewarnaan waktu  pemetaan  selanjutnya  adalah melakukan  pengelompokan  semester. Pada  semester  Ganjil  pengelompokan dibagi  menjadi  4  yaitu  semester  1, semester  3,  semester  5,  dan  semester  7. Sebelum pengelompokan kelas,
kesediaan  dosen  yang  memiliki  waktu fleksibel  dikembalikan  lagi  menjadi bernilai  1.  Proses  pengelompokan  kelas
dilakukan  berdasarkan  pertimbangan pewarnaan kesediaan mengampu matakuliah.  Ketersediaan  kelas  terbagi berdasarkan  dua  waktu  perkuliahan, yaitu  kelas  pagi  dan  kelas  malam. Pemilihan kelas diawali dengan penentuan  pengampu  di  kelas  malam terlebih dahulu. Dikarenakan kendalanya lebih  besar  mengingat  dosen  yang memberikan  kesediaan  hanya  kelas malam  lebih  terbatas  jumlahnya.  Selain pertimbangan kesamaan warna, pertimbangan  penting  berikutnya  adalah kesesuaian  dengan  bidang  keahlian dosen.  Dosen  yang  memiliki  keahlian sesuai  dengan  matakuliah  yang  dipilih lebih  diutamakan.  Hasil  pengelompokan kelas disajikan dalam tabel berikut
Tabel 4 Pembagian kelas semester 1 semester 1 01MATP001 01MATP002 01MATM001 Pendidikan  Kewarganegaraan v9 v9 v12 Bahasa Indonesia v21 v21 v21 Kalkulus I v1 v10 v10 Kimia Dasar v20 v20 v20 Bahasa Inggris I v18 v18 v19 Fisika Dasar I v17 v17 v17 Praktikum Fisika Dasar I v17 v17 v17 Pengantar Teknologi Informasi v14 v14 v6 Trigonometri v16 v16 v10
w1 w2 w3 w4 w5 w6 w7 w8 w9 w10 w11 w12 w13 w14 w15 w16 w17 w18 w19 w20 w21 w22 w23 w24 w25 w26 w27 w28 w29 v24 v42 v45 v51 v53 v4 v23 v37 v66 v16 v27 v30 v59 v61 v6 v1 v17 v35 v33 v58 v60 v62 v46 v47 v50 v55 v64 v18 v22
v65 v8 v2 v9 v49 v57 v3 v52 v19 v38 v43 v54 v25 v28 v36 v5 v31 v7 v15 v10 v11 v12 v13 v14 v20 v21 v26 v29 v32 v34 v39 v40 v41 v44 v48 v56 v63 v67
Tabel 5 Pembagian kelas semester 3 semester 3 03MATP001 03MATP002 03MATM001 Probabilitas v5 v5 v7 Teori Bilangan v16 v16 v8 Matematika Diskrit I v2 v1 v2 Algoritma & Pemrograman v7 v7 v6 Praktikum Algoritma & Pemrograman v7 v7 v6 Teknik Lingkungan v5 v5 v7 Aljabar Linier & Matriks v1 v10 v11 Geometri Datar v4 v4 v13 Bahasa Inggris III v19 v19 v19 Tabel 6 Pembagian kelas semester 5 semester 5 05MATP001 05MATP002 05MATM001 Program Linier v7 v7 v8 Geometri Analitik v4 v4 v13 Statistik Matematika II v8 v8 v8 Aljabar Abstrak Lanjutan v16 v16 v2 Praktikum Pemodelan Matematika v3 v3 v15 Analisis Nyata I v16 v16 Persamaan Diferensial Parsial v2 v2 v2 Teori Graf v4 v4 v13 Pemodelan Matematika v3 v3 v15 Tabel 7 Pembagian kelas semester 7 semester 7 07MATP001 07MATM001 07MATM002 Kewirausahaan v5 Metode Penelitian v14 v14 v14 Sistem Informasi Manajemen v5 Statistik Non Parametrik v14 v14 v14 Operasi Riset v16 v8 v8 Statistik Pengendalian Kualitas v7 v7 v7 Asuransi v1 v1 v1 Analisis Kompleks v8 v8 v8

## PEMBAHASAN
Berdasarkan  pembagian  kelas tersebut,  tidak  semua  kendala  terpenuhi, terdapat beberapa simpul yang mendapat kelas  atau  tatap  muka  melebihi  beban kerja  dosen  dan  terdapat  pula  beberapa kelas  yang  belum  mendapatkan  simpul disebabkan  tidak  ada  kesediaan  dosen yang  memenuhi.  Oleh  karena  itu,
sebelum  ke  tahap  selanjutnya  perlu dilakukan  modifikasi  penataan  kelas dengan  melanggar  beberapa  kendala. Adapun beberapa kendala tersebut adalah 1. Menempatkan dosen sesuai
matakuliah  yang  diampu  dengan memaksakan  kesediaan  waktu  yang diberikan; atau
2. Menempatkan dosen sesuai kesediaan waktu dengan memaksakan matakuliah dengan asumsi masih sesuai dengan kemampuan  akademik  dosen  yang bersangkutan. Karena kesediaan waktu termasuk kendala keras, maka kemungkinan kedua yang lebih memungkinkan
untuk dilanggar.
Berdasarkan pembagian kelas dan pewarnaan  kesediaan  waktu  mengajar, dapat disusun jadwal perkuliahan.

## SIMPULAN
Algoritma Welch-Powell dapat diterapkan  dalam  penjadwalan  mata kuliah  semester  ganjil  2017-2018  di Program  Studi  Matematika,  Fakultas Matematika  dan  Ilmu  Pengetahuan Alam,  Universitas  Pamulang  dengan membentuk  matriks  penyesuaian  antara kesediaan  mengampu  matakuliah  dosen simpulnya adalah dosen yang bersangkutan. Berdasarkan matriks kesediaan  mengampu  matakuliah  di semester ganjil, dapat dihasilkan 4 warna yakni  warna  w1  beranggotakan  v7,  v16, v11,  v3,  v4,  v9,  v18,  v21;  warna  w2 beranggotakan  v8,  v2,  v12,  v13,  v17, v19,  v20;  warna  w3  beranggotakan  v1, v5, v14, v15; dan warna w4 beranggotakan  v10,  v6.  Dari  keempat warna tersebut, penerapannya jika simpul berada  dalam  satu  warna,  artinya  simpul tersebut tidak bertetangga sehingga dapat ditempatkan di kelas yang sama, sedangkan  jika  berbeda  warna,  artinya simpul  tersebut  bertetangga  sehingga harus ditempatkan di kelas yang berbeda dan  hanya  dapat  ditempatkan  di  kelas yang  sama  jika  mengampu  matakuliah yang berbeda.
Berdasarkan  matriks  kesediaan waktumengajar  di  semester  ganjil,  dari 67  simpul  dapat  dihasilkan  29  warna. Dengan w1 beranggotakan simpul dengan  derajat  tertinggi  dan  simpul
dosen dengan waktu  yang fleksibel yang diatur tidak bertetangga dengan siapapun.

## DAFTAR PUSTAKA
Chartrand,  G.,  &  Lesniak,  L.  (1996).
Graphs  and  Digraphs (Third ed.).  Boca  Raton.  London.  New York.
Washington,
D.C: Chapman and Hall/CRC. Chartrand.G.  (1977). Introductory  of Graph Theory. New York:
Western  Michigan  University.
Dover Publications,inc.
Kusmayadi,  T.  A.  (2011).  Graf  dan Digraf Eksentrik. UNS Press . Petrovic,  S.,  &  Burke,  E.  (2004).
University Timetabling. Dalam J.
Y.-T. Leung, Handbook of Schedulling,  Algorithms,  models, and  Performance  Analysis. Boca
Raton London New York Washington,  D.C.:  CRC  Press Company.
Rochman,  A.  (2012). Penjadwalan Kuliah  dengan  menggunakan Metode  Constrains  Programming dan Simulated Annealing. Seminar nasional Aplikasi Teknologi Informasi 2012. Yogyakarta. S, D. H., Rosely, E., & Mayadewi, R. P. (2016). Penerapan Algoritma Welch Powell Dengan Pewarnaan Graph Pada Penjadwalan Mata Pelajaran Sma. Seminar  Nasional  Sistem Informasi Indonesia.
Sahid. (1998). Penyusunan Jadwal Kuliah  di  Perguruan  Tinggi dengan  Metode  Tabu  Search (Pencarian  Terlarang). Jurnal
Iptek dan Humaniora , 27-45.
Syauqi,  Z.  A.,  &  Syafwan,  M.  (t.thn.). Penjadwalan Matakuliah Menggunakan  Pewarnaan  Titik
Pada  Graf. Jurnal  Matematika UNAND .