PEWARNAAN GRAF WELCH-POWELL PADA
PENYUSUNAN JADWAL PERKULIAHAN DI PROGRAM
STUDI AKUNTANSI UNIVERSITAS BALI DWIPA
Ida Bagus Kade Puja Arimbawa K.
Ketut Queena Fredlina.
Agung Sedayu.
Universitas Bali Dwipa.
Universitas Primakara.
puja@balidwipa.
queena@primakara.
gplayus@gmail.
ABSTRACT
The scheduling of courses at the beginning of an academic semester can become complex because there is often a clash of schedules between courses.
While scheduling individually is not difficult, it can become complicated when involving many people with different schedules.
To solve this problem, one solution is to use the Graph Coloring technique that utilizes the Welch-Powell algorithm to obtain an optimal solution in scheduling courses.
Thus, the routine problem at the beginning of the semester can be addressed more effectively.
Keywords: graph, coloring, schedule.
Welch-Powell ABSTRAK Penyusunan jadwal di awal semester akademik menjadi kompleks karena sering kali terjadi bentrok jadwal antar mata kuliah.
Walaupun penyusunan jadwal secara individu tidaklah sulit, namun hal tersebut dapat menjadi rumit Ketika melibatkan banyak orang dengan kesibukan yang berbeda-beda.
Untuk mengatasi permasalahan tersebut, salah satu solusinya adalah dengan menggunakan Teknik pewarnaan graf yang memanfaatkan algoritma Welch-Powell untuk mendapat solusi yang optimal dalam penyusunan jadwal kuliah.
Dengan demikian, permasalahan rutinitas di awal semester dapat diatasi dengan lebih efektif.
Kata Kunci : kunci: graf, pewarnaan, jadwal.
Welch-Powell memberikan warna pada elemen graf yang akan menjadi subjek dalam memahami constraint permasalahan.
Terdapat tiga macam pewarnaan graf yaitu pewarnaan simpul .
, pewarnaan sisi .
dan pewarnaan wilayah .
Pewarnaan simpul digunakan untuk memberikan warna pada setiap simpul pada graf sehingga tidak ada dua simpul yang berhubungan langsung yang memiliki warna yang sama.
Pewarnaan sisi mengacu pada pemberian warna pada himpunan sisi dalam suatu graf dengan ketentuan bahwa setiap sisi yang bertetangga diberi warna yang berbeda.
Pewarnaan wilayah mengacu pada pemetaan warna ke wilayah-wilayah dalam suatu graf dengan PENDAHULUAN Teori graf merupakan suatu bidang ilmu matematika yang menarik untuk dibahas karena berkaitan dengan kehidupan seharihari.
Saat ini, perkembangan teori graf sangat pesat karena memiliki banyak penerapan yang Salah keunikan teori graf terletak pada kesederhanaan pokok bahasan yang dipelajari dan sering digunakan sebagai model permasalahan dimana informasi dapat diwakili sebagai simpul .
dan sisi .
Salah satu cabang dalam teori graf yang umumnya digunakan untuk memodelkan permasalahan adalah pewarnaan graf .
raph Pewarnaan graf digunakan untuk 473 Jurnal Teknologi Informasi dan Komputer.
Volume 9.
Nomor 4.
Juni 2023 ketentuan bahwa setiap wilayah yang bertetangga memiliki warna yang berbeda.
Pewarnaan graf ini telah banyak diaplikasikan dalam berbagai bidang, termasuk dalam penyusunan jadwal perkuliahan.
Setiap awal semester, bagian akademik Universitas Bali Dwipa seing disibukan dengan permasalahan penyusunan jadwal perkuliahan karena adanya beberapa masalah keterbatasan ruang kuliah, dosen mengajar lebih dari satu matakuliah, dan matakuliah dalam satu semester.
Untuk Teknik penjadwalan dengan pewarnaan graf dapat Dalam konteks ini, setiap perkuliahan yang mencangkup mata kuliah, dosen dan ruang kuliah diwakili oleh simpul dalam graf.
Simpul-simpul ini dihubungkan oleh sisi jika matakuliahnya diajarkan yang sama atau diadakan diruang yang sama, menandakan bahwa pekuliahan tersebut tidak dapat dilaukan secara bersamaan.
Fungsi objektif dalam pewarnaan simpul graf adalah meminimalkan konflik pewarnaan, yaitu simpul-simpul yang bertetangga yang diberi warna yang sama.
Hasil dari proses pewarnaan graf dapat digunakan sebagai solusi dalam penyusunan jadwal perkuliahan, di mana simpul-simpul yang diberi warna yang sama merepresentasikan pertemuan-pertemuan yang dapat dilakukan pada waktu yang sama dan merepresentasikan jumlah sesi perkuliahan.
Metode pewarnaan graf dengan algoritma Welsh-Powell merupakan salah satu metode yang digunakan dalam memecahkan masalah penjadwalan.
Algoritma WelchPowell digunakan untuk mewarnai graf dengan jumlah warna sedikit dengan mengurutkan semua simpul berdasarkan derajat, dari derajat paling besar ke derajat paling kecil.
TINJAUAN PUSTAKA
Graf Sebuah graf ya terdiri dari suatu himpunan tak kosong yang terdiri dari objek-objek yang disebut simpul .
dan himpunan pasangan ta berurutan dari simpul-simpul yang disebut dengan sisi .
Himpunan simpul di graf ya dinyatakan dengan ycO.
dan himpunan sisi dinyatakan dengan ya.
Graf ya disebut graf berhingga jika banyak simpul dan sisi berhingga.
Jika dan yc dan yc adalah simpul di ya dan yce = ycyc merupakan sisi di ya maka simpul yc dan yc dihubungkan oleh yce, yc dan yc terhubung langsung .
serta yc, yc terkait .
dengan yce .
Sebagai contoh, graf ya adalah graf sederhana dengan ycO.
= .
c, yc, yc, ycu, y.
= .
cyc, ycycu, ycyc, ycycu, ycycu, ycyc, ycy.
| = 5, ya.
= 7.
Gambar 1.
Graf ya Derajat simpul pada suatu graf ya dengan simpul yc dilambangkan dengan ycc.
yaitu banyaknya sisi graf ya yang terkait dengan simpul yc atau derajat simpul merupakan banyaknya sisi bertemu pada suatu simpul.
Pewarnaan Graf Pewarnaan graf merupakan bagian dari pelabelan graf yaitu memberikan warna pada simpul-simpil pada batas tertentu.
Ada tiga macam pewarnaan graf yaitu Pewarnaan simpul .
ertex colorin.
Pewarnaan sisi .
dge colorin.
dan Pewarnaan wilayah .
egion Pewarnaan simpul atau vertex Arimbawa.
Fredlina.
Sedayu.
Pewarnaan Graf Welch-Powell Pada Penyusunan JadwalA 474 coloring merupakan pelabelan dengan memberi warna pada setiap simpul yang bertetangga dengan ketentuan dua simpul yang bertetangga tidak memiliki warna yang sama.
Pewarnaan sisi atau edge coloring merupakan pelabelan dengan memberi warna pada setiap sisi pada suatu graf dengan ketentuan dua sisi yang bersesuaian tidak memiliki warna yang Pewarnaan wilayah atau region coloring merupakan pelabelan dengan memberi warna setiap wilayah pada suatu graf dengan ketentuan tidak ada wilayah yang bersebelahan tidak memiliki warna yang sama .
Jumlah warna minimum yang dapat digunakan untuk melabeli simpul suatu graf ya disebut dengan bilangan kromatik yang dilambangkan dengan yue.
Suatu graf dengan yue.
= yco artinya graf ya mempunyai yco bilangan terkecil sehingga graf tersebut dapat diwarnai dengan yco warna .
Algoritma Welch-Powell Algoritma Welch-Powell mewarnai graf dengan cara memberi label pada simpulsimpul sesuai dengan derajatnya.
Algoritma Welch-Powell menggunakan urutan derajat tertinggi dari simpul-simpul graf ya untuk Meskipun algoritma ini tidak selalu memberikan jumlah warna minimum yang diperlukan untuk mewarnai graf ya tetapi cukup praktis untuk digunakan dalam pewarnaan simpul suatu graf .
Adapun Langkah-langkah algoritma Welch-Powell untuk suatu graf ya terlihat seperti pada diagram alir berikut :
Gambar 2.
Algoritma Welch-Powell METODE PENELITIAN Tempat dan waktu penelitian Penitian ini dilakukan di Kampus Universitas Bali Dwipa (Program Studi Akuntansi.
Fakultas Humaniora dan Ilmu Sosia.
beralamat di Jalan Pulau Flores No 5 Denpasar.
Penelitian dilakukan selama 6 bulan, mulai dari Agustus 2022 sampai dengan Januari 2023.
Sumber dan jenis data Data yang digunakan dalam penelitian ini adalah data primer dan skunder dimana data primer diperoleh langsung dari Fakultas Humaniora dan Ilmu Sosial Universitas Bali Dwipa dengan cara wawancara dengan Dekan serta dokumentasi dari perkuliahan.
Data skunder dari penelitian ini berupa data yang diperoleh secara tidak langsung yaitu jurnal penelitian serta buku.
Adapun data yang diperoleh berupa Nama dosen.
Kode Matakuliah.
Nama matakuliah dan jumlah sks masing-masing matakuliah.
475 Jurnal Teknologi Informasi dan Komputer.
Volume 9.
Nomor 4.
Juni 2023 Alur Penelitian Penelitian ini dilakukan mengikuti Langkahlangkah sebagai berikut :
Identifikasi masalah, langkah ini permasalahan dalam penyusunan jadwal Proses penjadwalan yang dilakukan saat ini memerlukan waktu yang lama karena harus memastikan satu per satu jadwal dan memastikan tidak ada jadwal yang bentrok.
Studi pustaka.
Langkah ni dilakukan dengan cara mencari literatur untuk memperoleh solusi dari masalah yang dihadapi yaitu penerapan pewarnaan graf dalam penjadwalan.
Pengumpulan Langkah dilakukan dengan cara mengumpulkan data dalam bentuk nama dosen, kode mata kuliah, nama mata kuliah, dan jumlah sks.
Analisis data, data yang telah ada ditranspormasikan dalam bentuk graf serta menentukan representasi graf dalam bentuk matriks ketetanggaan.
Pewarnaan graf, langkah ini dilakukan dengan menerapkan algoritma WelshPowell dengan menentukan derajat simpul yang paling besar sampai dengan simpul dengan derajat paling kecil.
Kesimpulan.
Langkah terakhir dalam kesimpulan dari hasil pewarnaan graf.
Pada Langkah ini juga diperoleh jadwal perkuliahan yang paling efektif.
Data Sebaran Mata Kuliah Sebaran mata kuliah pada Program Studi Akuntansi.
Fakultas Humaniora dan Ilmu Sosial dengan terlihat pada tabel berikut.
Tabel 1.
Sebaran Mata Kuliah Berdasarkan tabel 1, terdapat 26 mata kuliah pada semester I, i.
V dan VII semester Ganjil Tahun Akademik 2022/2023 yang diampu oleh 12 dosen.
Transformasi Graf Komponen penjadwalan adalah kelompok mata kuliah, kelompok dosen, kelompok mahasiswa, ketersediaan ruangan dan waktu dengan batasan setiap mata kuliah hanya ada 1 kelas.
Ketentuan pembentukan graf adalah sebagai Simpul : Kelompok matakuliah sebagai simpul dalam graf Sisi : sisi yang menghubungkan antar simpul dengan ketentuan mata kuliah yang diambil mahasiswa pada semester yang sama dan mata kuliah yang diampu oleh dosen yang sama.
Untuk mempermudah pengamatan, keterkaitan dosen dengan mata kuliah yang diampu dapat dilihat pada Tabel 2.
Apabila dosen mengajar pada matakuliah tersebut maka akan diberikan angka 1, sedangkan apabila tidak maka akan diberikan angka 0.
Arimbawa.
Fredlina.
Sedayu.
Pewarnaan Graf Welch-Powell Pada Penyusunan JadwalA 476
SMT
Nama Mata kuliah Pancasila Bahasa Indonesia Pengantar Akuntansi Pengantar Teknologi Informasi I(Sat.
Pengantar Manajemen Pengantar Bisnis Matematika Ekonomi Statistika Bisnis Bahasa Inggris I Manajemen Keuangan Hukum Pajak Akuntansi Manajemen Sistem Informasi Akuntansi i(Tig.
Akuntansi Keuangan Menengah II Manajemen Operasional Komunikasi Bisnis Etika Bisnis dan Profesi Bank dan Lembaga Keuangan Lainnya Akuntansi Perpajakan Analisa Laporan Keuangan V(Lim.
Pemeriksaan Akuntansi/Audit II Metode Penelitian Perpajakan II Akuntansi Perbankan VII(Tuju.
Audit Internal
Ekonomi Pembangunan Dosen Pengampu AGC
IKS
IWA KSH
GAN IBK
IBU
IBP
LAJ
NMG NNT YPS
Tabel 2.
Keterkaitan dosen dengan mata Gambar 3.
Matriks Adjacency Berdasarkan matriks adjacency pada Gambar transformasi menjadi bentuk graf seperti yang terlihat pada Gambar 4.
Pada tabel 2 terlihat bahwa 1 dosen dapat mengajar lebih dari 1 mata kuliah.
Mata kuliah yang diampu oleh dosen yang sama serta mata kuliah yang diambil mahasiswa pada semester yang sama tidak boleh dalam waktu yang sama mata kuliah tersebut harus saling Mata kuliah sebagai simpul diberi nama dari ycO1, ycO2, ycO3.
A , ycO26 secara Daftar penerapan simpul dan simpul tetangga disajikan pada Tabel 3.
Simpul
V10
V11
V12
V13
V14
V15
V16
V17
V18
V19
V20
V21
V22
V23
V24
V25
V26
Simpul tetangga V2.
V3.
V4.
V5.
V6.
V7.
V8.
V1.
V3.
V4.
V5.
V6.
V7.
V8.
V1.
V2.
V4.
V5.
V6.
V7.
V8.
V9.
V13.
V25
V1.
V2.
V3.
V5.
V6.
V7.
V8.
V1.
V2.
V3.
V4.
V6.
V7.
V8.
V9.
V13.
V25
V1.
V2.
V3.
V4.
V5.
V7.
V8.
V9.
V18.
V20.
V21
V1.
V2.
V3.
V4.
V5.
V6.
V8.
V9.
V14.
V16
V1.
V2.
V3.
V4.
V5.
V6.
V7.
V1.
V2.
V3.
V4.
V5.
V6.
V7.
V11.
V12.
V13.
V14.
V15.
V16.
V17.
V18.
V19
V10.
V12.
V13.
V14.
V15.
V16.
V17.
V18.
V26
V7.
V10.
V11.
V13.
V14.
V15.
V16.
V17.
V18
V3.
V5.
V10.
V11.
V12.
V14.
V15.
V16.
V17.
V18.
V25
V7.
V10.
V11.
V12.
V13.
V15,V16.
V17.
V18
V10.
V11.
V12.
V13.
V14,V16.
V17.
V18
V10.
V11.
V12.
V13.
V14,V15.
V17.
V18.
V26
V10.
V11.
V12.
V13.
V14,V15.
V16.
V18
V6.
V10.
V11.
V12.
V13.
V14.
V15.
V16.
V17.
V20.
V21
V10.
V12.
V15.
V20.
V21.
V22.
V23
V6.
V18.
V19.
V21.
V22.
V23
V6.
V18.
V20.
V22.
V23
V19.
V20.
V21.
V23
V19.
V20.
V21.
V22
V23.
V25.
V26
V3.
V5.
V13.
V24.
V26
V11.
V16.
V24.
V25
Gambar 4.
Graf Keterkaitan antar Berdasarkan gambar 4, derajat masing-masing simpul dapat dihitung dan diurutkan dari derajat terbesar sampai derajat terkecil.
Derajat Simpul V13.
V18.
V3.
V5.
V12.
V11.
V10.
V16.
V14
V1.
V2.
V4.
V8.
V9.
V15.
V17
V19
V20
V21.
V25
V22.
V23.
V26
V24
Tabel 3.
Simpul dan Simpul Tetangga Tabel 4.
Derajat Simpul Kemudian Matriks Adjacency dibentuk untuk menyatakan hubungan antar mata kuliah dan disesuaikan dengan Tabel 1.
Pewarnaan Graf Program Studi Akuntansi memiliki 2 ruangan kelas .
elas A dan kelas B) yang dipakai untuk proses belajar mengajar sehingga dalam 477 Jurnal Teknologi Informasi dan Komputer.
Volume 9.
Nomor 4.
Juni 2023 pewarnaan graf, warna yang sama hanya dapat digunakan maksimal pada 2 simpul.
Selanjutnya setiap simpul diwarnai dengan Welch-Powell mengikuti Tabel 3 dan Tabel 4.
Hasil pewarnaan graf dapat dilihat pada Gambar 5.
Gambar 5.
Pewarnaan Graf Berdasarkan Gambar 5, setiap simpul dengan warna sama dipisahkan dan dikelompokan menjadi 2 yaitu ruangan A dan ruangan B.
Kelompok simpul dapat dilihat pada tabel 5.
Ruangan V10
V16
V18
V14
V12
Simpul
V13 V11 V15
V17
V19
V25
V20
V26
V21
V24
V22
V23
Tabel 6.
Pengelompokan Simpul Berdasarkan Ruangan Selanjutnya dibentuk jadwal perkuliahan untuk ruangan A dan ruangan B berdasarkan tabel 6.
Hari Senin Senin Senin Senin Selasa Selasa Selasa Selasa Rabu Rabu Kamis Kamis Jumat Jam 00 - 09.
30 - 12.
00 - 15.
00 - 18.
00 - 09.
30 - 12.
00 - 15.
00 - 18.
00 - 10.
00 - 15.
00 - 10.
00 - 15.
00 - 09.
Kode Mata Kuliah AKN071001 Pancasila AKW071001 Pengantar Akuntansi AKP071001 Akuntansi Perpajakan AKP071002 Analisa Laporan Keuangan AKN071002 Bahasa Indonesia AKW071002 Pengantar Teknologi Informasi AKW071032 Pemeriksaan Akuntansi/Audit II AKW071033 Metode Penelitian AKW071003 Pengantar Manajemen AKW071004 Pengantar Bisnis AKW071005 Matematika Ekonomi AKW071006 Statistika Bisnis AKW071007 Bahasa Inggris I Dosen Semester Dr.
Ir.
I Wayan Adnyana.
SH.
Kn.
I Gusti Ayu Novitasari.
Si.
Ni Made Galih Masari.
SE.
SH.
,Ak.
Si.
Ni Nyoman Tri Wahyuni.
SE.
MM.
Yoga Putra Semadi.
Pd.
Pd.
Ayu Gde Chrisna Udayanie.
Pd.
Pd.
Ni Nyoman Tri Wahyuni.
SE.
MM.
Dr.
Ir.
Ketut Suriasih.
App.
Sc.
I Gusti Ayu Novitasari.
Si.
Ni Nyoman Tri Wahyuni.
SE.
MM.
Ida Bagus Putra Yogismara.
SE.
Si.
Ida Bagus Kade Puja Arimbawa K.
Si.
Si.
Dr.
I Ketut Suardana.
Hum.
Tabel 7.
Jadwal Perkuliahan di Ruangan A Hari Senin Senin Senin Senin Selasa Selasa Rabu Rabu Kamis Kamis Jumat Jumat Jumat Jam 00 - 09.
30 - 12.
00 - 15.
00 - 18.
00 - 10.
00 - 15.
00 - 10.
00 - 15.
00 - 09.
00 - 15.
00 - 09.
30 - 10.
00 - 14.
Kode Mata Kuliah AKW071015 Manajemen Keuangan AKW071017 Akuntansi Manajemen AKP071010 Akuntansi Perbankan AKP071012 Ekonomi Pembangunan AKW071017 Akuntansi Manajemen AKW071018 Sistem Informasi Akuntansi AKW071019 Akuntansi Keuangan Menengah II AKW071018 Sistem Informasi Akuntansi AKW071020 Manajemen Operasional AKW071019 Perpajakan II AKW071021 Komunikasi Bisnis AKW071022 Etika Bisnis dan Profesi AKW071007 Bank dan Lembaga Keuangan Lainnya Dosen Ni Made Galih Masari.
SE.
SH.
,Ak.
Si.
Ida Bagus Putra Yogismara.
SE.
Si.
Luh Asri Jatmika.
Si.
Ida Bagus Made Utama.
SE.
SH.
MH.
Ida Bagus Putra Yogismara.
SE.
Si.
I Gusti Ayu Novitasari.
Si.
Ida Bagus Putra Yogismara.
SE.
Si.
I Gusti Ayu Novitasari.
Si.
Ni Made Galih Masari.
SE.
SH.
,Ak.
Si.
Luh Asri Jatmika.
Si.
Ida Bagus Made Utama.
SE.
SH.
MH.
Ni Made Galih Masari.
SE.
SH.
,Ak.
Si.
Ni Nyoman Tri Wahyuni.
SE.
MM.
Semester i i VII
VII
i i i i i i i i Tabel 8.
Jadwal Perkuliahan di Ruangan B
SIMPULAN
Berdasarkan hasil penelitian, algoritma Welch-Powell menentukan jadwal kuliah dengan cara melakukan pewarnaan graf.
Dalam penelitian ini, kelompok mata kuliah dan dosen pada Program Studi Akuntansi.
Fakultas Humaniora dan Ilmu Sosial.
Universitas Bali Dwipa pada semester ganjil tahun akademik 2022/2023 direpresentasikan dalam bentuk graf dengan 26 simpul.
Setelah dilakukan pewarnaan graf dengan algoritma Welch-Powell, 13 warna digunakan untuk mewarnai simpul pada graf.
Warna-warna tersebut kemudian digunakan untuk mengelompokkan mata kuliah ke dalam 2 kelompok sesuai dengan ketersediaan Dari hasil pengelompokan tersebut, jadwal kuliah yang efektif berhasil disusun tanpa terjadi tumpang tindih pada hari, jam, atau dosen.
DAFTAR PUSTAKA