Penerapan Pewarnaan Graf pada Penjadwalan Mengajar Dosen Pendidikan Matematika Universitas Nurul Jadid
on
Jurnal Matematika Vol. 11, No.1, Juni 2021, pp. 10-19
Article DOI: 10.24843/JMAT.2021.v11.i01.p132
ISSN: 1693-1394
Penerapan Pewarnaan Graf pada Penjadwalan Mengajar Dosen Pendidikan Matematika Universitas Nurul Jadid
Olief Ilmandira Ratu Farisi
Universitas Nurul Jadid, Paiton-Probolinggo, Indonesia e-mail: [email protected]
Siti Maysyaroh
Universitas Nurul Jadid, Paiton-Probolinggo, Indonesia
Eka Fitriana Dewi
Universitas Nurul Jadid, Paiton-Probolinggo, Indonesia
Abstract: Learning schedules arrangement of lecturers in Department of Mathematics Education Nurul Jadid University is still done manually by inserting lecturers' schedules one by one. Consequently, there are overlapping schedules that led to ineffective lecture preparation and cause confusion among lecturers and students. Besides, our Study Program only has two rooms which cause limited scheduling. In this paper, we proposed graph coloring technique to arrange the schedule in Department of Mathematics Eduation. Each vertex represents the course while the edge represents the course taught by the same lecturers or chosen by the same classes. By using the graph coloring, the 22 courses can be colored using 11 different colors. Classes can be held for four days and leave one day off. It is showed that the graph coloring can get the optimal schedule arrangement. In addition, the schedule is easily changed and reassembled in accordance with the group of colors.
Keywords: graph coloring, vertex coloring, teaching schedule.
Setiap semester, jadwal mengajar dosen matematika di Universitas Nurul Jadid mengalami tumpang tindih. Kasus tumpang tindih ini berupa dosen mengajar dua mata kuliah berbeda di jam yang sama dan/atau dosen berbeda menggunakan ruangan yang sama dan/atau dosen berbeda mengajar di angkatan yang sama. Hal ini dikarenakan penjadwalan dikelola oleh pihak fakultas dan masih dilakukan secara manual, yaitu dengan memasukkan satu per satu jadwal setiap dosen di fakultas. Selain itu, program studi Pendidikan Matematika hanya dapat menggunakan dua ruangan setiap hari untuk pembelajaran. Jadwal yang tumpang tindih ini akan diketahui setelah jadwal tersebut dibagikan ke dosen dan mahasiswa sebelum awal semester. Beberapa dosen dan mahasiswa akan melaporkan jika terdapat jadwal yang salah. Pihak fakultas pun akan merevi-
si beberapa kali sampai tidak ada lagi laporan kesalahan dari dosen atau mahasiswa. Hal ini menyebabkan persiapan perkuliahan menjadi tidak efektif dan menimbulkan kebingungan di kalangan dosen dan mahasiswa. Oleh karena itu, diperlukan suatu teknik penyusunan jadwal kuliah yang optimal, yang dapat mengakomodasi semua batasan yang ada, salah satunya dengan menggunakan teori graf.
Graf merupakan salah satu cabang matematika terapan yang dapat digunakan dalam menyelesaikan permasalahan optimasi, seperti penentuan lintasan terpendek (Salaki, 2011), pembuatan jaringan komputer (Aziz, 2014), pemampatan (Siahaan, 2016), dan lain sebagainya. Graf merupakan himpunan objek-objek yang berhingga dan tak kosong, disebut dengan simpul dan himpunan pasangan tak berurut (yang mungkin kosong) dari simpul-simpul tersebut, yang disebut dengan sisi (Gross & Yellen, 2005). Gambar 1 merupakan contoh dari graf G dengan 5 simpul dan 7 sisi dengan himpunan simpulnya {A, B, C, D, E} dan himpunan sisi {(A, B), (A, D), ( A, E), (B, C), (C, D), (C, E), (C, D)} . Simpul pada suatu graf memiliki derajat simpul, yaitu banyak sisi yang melekat pada simpul tersebut. Pada graf G, derajat simpul A, B, C, D, dan E berturut-turut adalah 3, 2, 3, 3, 3.
Gambar 1. Graf G dan representasi matriksnya
Graf juga dapat direpresentasikan dalam bentuk matriks. Pada Gambar 1, matriks AG merupakan matriks ketetanggan dari graf G. Matriks ketetanggan adalah matriks yang baris dan kolomnya disusun berdasarkan urutan simpulnya dengan pemberian 1 jika dua simpul terhubung oleh sisi, dan 0 jika sebaliknya (Mukherjee & Mukherjee, 2014).
Salah satu subbagian dari teori graf adalah pewarnaan graf. Beberapa peneliti telah menggunakan pewarnaan graf untuk menyelesaikan permasalahan optimalisasi distribusi (Azizah, 2018), penjadwalan ujian (Mahmudah & Irawati, 2018), dan pengaturan lampu lalu lintas (Sagala & Mekar Sari, 2018). Dari hasil penelitian-penelitian tersebut, pewarnaan graf terbukti efektif dalam permasalahan yang berkaitan dengan penjadwalan, penugasan, dan lain penyusunan. Oleh karena itu, pada penelitian ini, diusulkan teknik pewarnaan graf untuk menyelesaikan permasalahan jadwal mengajar dosen matematika Universitas Nurul Jadid yang tumpang tindih. dengan merepresentasikan simpul sebagai nama mata kuliah dan sisi sebagai dosen yang sama atau kelas yang sama.
Pewarnaan graf adalah mewarnai bagian dari graf. Ada berbagai jenis pewarnaan graf antara lain pewarnaan simpul, pewarnaan sisi, pewarnaan peta, dan sebagainya (Formanowicz & Tanaś, 2012). Pewarnaan simpul merupakan pewarnaan yang banyak digunakan. Pewarnaan simpul adalah mewarnai simpul suatu graf dengan penggunaan warna seminimal mungkin sedemikian hingga simpul yang terhubung oleh satu sisi atau lebih diberi warna berbeda. Gambar 2 merupakan pewarnaan simpul dari graf G.
Gambar 2. Pewarnaan simpul graf G
Salah satu algoritma yang digunakan dalam pewarnaan simpul adalah algoritma Welsh Powell. Berdasarkan algoritma tersebut, pewarnaan simpul dimulai dari simpul yang memiliki derajat terbesar hingga terkecil (Welsh, 1967). Algoritma 1 menjelaskan langkah-langkah dari algoritma Welsh Powell.
Algoritma 1: Algoritma Welsh Powell
Input: graf G dengan Jl simpul
While ada simpul di tr yang belum diberi warna
Pilih simpul V yang mempunyai derajat terbesar
Warnai simpul V dengan warna yang sama dengan simpul berderajat tinggi sebelumnya jika kedua simpul tidak bertetangga.
Return graf (r dengan pewarnaan simpul
Output: pewarnaan simpul dari graf (r
Pewarnaan graf untuk graf G pada Gambar 1 dimulai dari simpul dengan derajat terbesar, yaitu A, C, D, dan E. Pilih salah satu, misalkan A, beri A dengan warna 1. Tersisa C, D, E yang merupakan simpul berderajat terbesar. Karena C tidak terhubung dengan A, maka C dapat diwarnai dengan warna yang sama dengan A, yaitu warna 1. Selanjutnya, simpul D diberi warna 2 dan E diberi warna 3. Terakhir, simpul B diberi warna 2 karena tidak terhubung dengan D.
Pada penelitian ini, data yang digunakan adalah sebaran mengajar dosen program studi Pendidikan Matematika Semester Genap 2020/2021. Program studi Matematika Universitas Nurul Jadid saat ini baru memiliki tiga angkatan. Terdapat 22 matakuliah untuk angkatan semester II, IV, dan VI yang diampu oleh 10 dosen seperti yang ditunjukkan pada Tabel 1.
Tabel 1. Sebaran Matakuliah Program Studi Pendidikan Matematika Semester Genap 2020/2021
|
No |
Mata Kuliah |
Semester |
Nama Dosen |
|
1 |
Kepesantrenan |
II |
Dr. Hasyim Syamhudi, M.Si. |
|
2 |
Keaswajaan |
II |
Thufail Muttaqien, M.Pd. |
|
3 |
Telaah Matematika SMP |
II |
Moh. Syadidul Itqan, M.Pd. |
|
4 |
Statistika Inferensial |
IV |
Moh. Syadidul Itqan, M.Pd. |
|
5 |
Daspros. Pembelajaran Matematika |
IV |
Moh. Syadidul Itqan, M.Pd. |
|
6 |
Kalkulus II |
II |
Shofia Hidayah, M.Pd. |
|
7 |
Telaah Matematika SMU I |
IV |
Shofia Hidayah, M.Pd. |
|
8 |
Micro Teaching |
VI |
Shofia Hidayah, M.Pd. |
|
9 |
Geometri Analitik |
VI |
Shofia Hidayah, M.Pd. |
|
10 |
Aljabar Linier Elementer |
II |
Nur Hamid, Ph.D. |
|
11 |
Struktur Aljabar I |
IV |
Nur Hamid, Ph.D. |
|
12 |
Metode Numerik |
VI |
Nur Hamid, Ph.D. |
|
13 |
Matematika Diskrit |
II |
Arini Hidayati, S.Si., M.Pd. |
|
14 |
Persamaan Differensial |
IV |
Arini Hidayati, S.Si., M.Pd. |
|
15 |
Teori Bilangan |
VI |
Arini Hidayati, S.Si., M.Pd. |
|
16 |
Bahasa Indonesia |
II |
Faizatul Widad, M.Pd. |
|
17 |
Psikologi pendidikan |
II |
Zaini Gunawan, M.Pd. |
|
18 |
Analisis Real |
IV |
Olief Ilmandira R.F, S.Pd., M.Si. |
|
19 |
Analisis Variabel |
IV |
Olief Ilmandira R.F, S.Pd., M.Si. |
|
20 |
Pengantar Komputer |
IV |
Olief Ilmandira R.F, S.Pd., M.Si. |
|
21 |
Komputer II |
VI |
Olief Ilmandira R.F, S.Pd., M.Si. |
|
22 |
Kewirausahaan |
VI |
Lely Widyawati A.Md, S.I.P, M.A. |
Langkah-langkah pewarnaan graf pada penjadwalan mengajar dosen Pendidikan Matematika di Universitas Nurul Jadid adalah sebagai berikut.
-
1. Memodelkan data sebaran mata kuliah mejadi suatu graf dengan urutan penomoran simpul seperti pada penomoran tabel. Simpul merepresentasikan nama matakuliah. Matakuliah yang diampu oleh dosen yang sama atau diambil oleh angkatan yang sama, dua simpul yang mewakili matakuliah tersebut terhubung oleh sisi.
-
2. Membuat representasi matriks dari graf tersebut untuk memudahkan dalam menentukan derajat simpul dan pemberian warna.
-
3. Menentukan derajat dari masing-masing simpul untuk digunakan dalam pewarnaan simpul.
-
4. Mewarnai simpul pada graf dengan Algoritma Welsh Powell dimulai dari simpul tertinggi.
Untuk menyusun jadwal mengajar dosen Pendidikan Matematika di Universitas Nurul Jadid, data sebaran mata kuliah pada Tabel 1 terlebih dahulu diubah menjadi graf dengan urutan penomoran simpul seperti pada penomoran tabel. Simpul merepresentasikan nama matakuliah. Matakuliah yang diampu oleh dosen yang sama atau diambil oleh angkatan yang sama, dua simpul yang mewakili matakuliah tersebut terhubung oleh sisi. Hasil pemodelan graf ditunjukkan pada Gambar 3.
Gambar 5: Pewarnaan Simpul dari Graf Sebaran Matakuliah
Pemodelan graf dari sebaran mata kuliah pada Gambar 3 dinyatakan dalam bentuk matriks seperti disajikan pada Gambar 4. Pada matriks ini bagian kolom dan baris menyatakan mata kuliah. Nilai nol berarti kedua mata kuliah tersebut merupakan mata kuliah yang saling bertetangga pada Gambar 3 sehingga kedua mata kuliah tersebut tidak dapat diletakkan pada waktu dan hari yang sama, sedangkan nilai satu berarti kedua
mata kuliah tersebut tidak saling bertetangga sehingga dapat diletakkan pada waktu dan hari yang sama. Dengan demikian entri aij pada matriks A menyatakan kebertetanggaan
|
dua mata kuliah. | ||||||||||||||||||||||
|
'0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 ^ | |
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 | |
|
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 | |
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 | |
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 | |
|
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 | |
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 | |
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 | |
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 | |
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 | |
|
A = |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 | |
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 | |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 | |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 | |
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 | |
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 | |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 | |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 | |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 | |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 | |
|
.0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0. | |
Gambar 4. Representasi Matriks dari Graf Sebaran Matakuliah
Langkah selanjutnya adalah menentukan derajat dari masing-masing simpul. Tabel 2 menunjukkan derajat simpul dari graf pada Gambar 3. Derajat simpul ini digunakan dalam menentukan urutan warna yang akan digunakan dalam pewarnaan simpul. Selanjutnya, dilakukan pewarnaan simpul pada graf pada Gambar 3 menggunakan algoritma Welsh Powell. Karena program studi Pendidikan Matematika hanya dapat menggunakan dua ruangan, maka setiap warna hanya dapat digunakan maksimal dua kali saja. Hasil dari pewarnaan graf ditunjukkan oleh Gambar 5.
Tabel 2. Derajat Simpul dari Setiap Matakuliah
|
Simpul |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
|
Derajat |
7 |
7 |
9 |
8 |
8 |
10 |
10 |
7 |
7 |
9 |
9 |
7 |
9 |
9 |
7 |
7 |
7 |
8 |
8 |
8 |
8 |
5 |
Gambar 5: Pewarnaan Simpul dari Graf Sebaran Matakuliah
Tabel 3. Tabel Hubungan antara Kelompok Warna dengan Simpul
|
Warna |
Simpul |
Matakuliah |
Dosen Pengampu |
|
A |
1 |
Kepesantrenan |
Dr. Hasyim Syamhudi, M.Si. |
|
12 |
Metode Numerik |
Nur Hamid, Ph.D. | |
|
B |
2 |
Keaswajaan |
Thufail Muttaqien, M.Pd. |
|
9 |
Geometri Analitik |
Shofia Hidayah, M.Pd. | |
|
C |
3 |
Telaah Matematika SMP |
Moh. Syadidul Itqan, M.Pd. |
|
11 |
Struktur Aljabar I |
Nur Hamid, Ph.D. | |
|
D |
4 |
Statistika Inferensial |
Moh. Syadidul Itqan, M.Pd. |
|
21 |
Komputer II |
Olief Ilmandira R.F, S.Pd., M.Si. | |
|
E |
5 |
Daspros. Pembelajaran Matematika |
Moh. Syadidul Itqan, M.Pd. |
|
6 |
Kalkulus II |
Shofia Hidayah, M.Pd. | |
|
F |
7 |
Telaah Matematika SMU I |
Shofia Hidayah, M.Pd. |
|
10 |
Aljabar Linier Elementer |
Nur Hamid, Ph.D. | |
|
G |
8 |
Micro Teaching |
Shofia Hidayah, M.Pd. |
|
13 |
Matematika Diskrit |
Arini Hidayati, S.Si., M.Pd. | |
|
H |
14 |
Persamaan Differensial |
Arini Hidayati, S.Si., M.Pd. |
|
16 |
Bahasa Indonesia |
Faizatul Widad, M.Pd. | |
|
I |
15 |
Teori Bilangan |
Arini Hidayati, S.Si., M.Pd. |
|
20 |
Pengantar Komputer |
Olief Ilmandira R.F, S.Pd., M.Si. | |
|
J |
17 |
Psikologi Pendidikan |
Zaini Gunawan, M.Pd. |
|
19 |
Analisis Variabel |
Olief Ilmandira R.F, S.Pd., M.Si. | |
|
K |
18 |
Analisis Real |
Olief Ilmandira R.F, S.Pd., M.Si. |
|
22 |
Kewirausahaan |
Lely Widyawati A.Md, S.I.P, M.A. |
Berdasarkan hasil dari pewarnaan graf pada Gambar 5, dapat dipetakan pasangan
antara warna simpul dan matakuliah seperti yang ditunjukkan pada Tabel 3. Terdapat 11 warna yang dibutuhkan dalam mewarnai 22 simpul matakuliah dengan ketentuan hanya dua ruangan yang dapat digunakan. Warna yang sama menunjukkan bahwa dua matakuliah tersebut dapat dijadwalkan pada waktu yang sama.
Berdasarkan pewarnaan simpul pada Gambar 5 dan Tabel 3, salah satu kemungkinan jadwal mengajar dosen progam studi Pendidikan Matematika Universitas Nurul Jadid dapat disusun seperti pada Tabel 4. Perkuliahan dimulai dari Sabtu sampai dengan Rabu dengan waktu 50 menit/sks. Dengan memenuhi jadwal setiap harinya, perkuliahan dapat berlangsung dari Sabtu sampai dengan Selasa saja dengan menyisakan satu hari kosong, yaitu Rabu.
Tabel 4. Jadwal Mengajar Dosen Progam Studi Pendidikan Matematika Semester Genap 2020/2021
|
Hari |
Jam |
Ruang | |
|
B2.02 |
B2.03 | ||
|
Sabtu |
07.00-07.50 |
Kepesantrenan (II) Dr. Hasyim Syamhudi, M.Si. |
Metode Numerik (VI) Nur Hamid, Ph.D. |
|
07.50-08.40 | |||
|
08.40-09.30 | |||
|
09.30-10.20 |
Keaswajaan (II) Thufail Muttaqien, M.Pd. |
Geometri Analitik(VI) Shofia Hidayah, M.Pd. | |
|
10.20-11.10 | |||
|
11.00-12.00 | |||
|
13.00-13.50 |
Telaah Matematika SMU I (IV) Shofia Hidayah, M.Pd. |
Aljabar Linier Elementer (II) Nur Hamid, Ph.D. | |
|
13.50-14.40 | |||
|
14.40-15.30 | |||
|
Minggu |
07.00-07.50 |
Telaah Matematika SMP (II) Moh. Syadidul Itqan, M.Pd. |
Struktur Aljabar I (IV) Nur Hamid, Ph.D. |
|
07.50-08.40 | |||
|
08.40-09.30 | |||
|
09.30-10.20 |
Daspros. Pembelajaran Mat (IV) Moh. Syadidul Itqan, M.Pd. |
Kalkulus II (II) Shofia Hidayah, M.Pd. | |
|
10.20-11.10 | |||
|
11.00-12.00 | |||
|
13.00-13.50 |
Teori Bilangan (VI) Arini Hidayati, S.Si., M.Pd. |
Pengantar Komputer (II) Olief Ilmandira R.F, S.Pd., M.Si. | |
|
13.50-14.40 | |||
|
14.40-15.30 | |||
|
Senin |
07.00-07.50 |
Micro Teaching (VI) Shofia Hidayah, M.Pd. |
Matematika Diskrit (II) Arini Hidayati, S.Si., M.Pd. |
|
07.50-08.40 | |||
|
08.40-09.30 | |||
|
09.30-10.20 |
Persamaan Differensial (IV) Arini Hidayati, S.Si., M.Pd. |
Bahasa Indonesia (II) Faizatul Widad, M.Pd. | |
|
10.20-11.10 | |||
|
11.00-12.00 | |||
|
13.00-13.50 |
Analisis Real (IV) Olief Ilmandira R.F, S.Pd., M.Si. |
Kewirausahaan (VI) Lely Widyawati A.Md, S.I.P, M.A. | |
|
13.50-14.40 | |||
|
14.40-15.30 | |||
|
Selasa |
07.00-07.50 |
Psikologi Pendidikan (II) Zaini Gunawan, M.Pd. |
Analisis Variabel (IV) Olief Ilmandira R.F, S.Pd., M.Si. |
|
07.50-08.40 | |||
|
08.40-09.30 | |||
|
09.30-10.20 |
Statistika Inferensial (IV) Moh. Syadidul Itqan, M.Pd. |
Komputer II (VI) Olief Ilmandira R.F, S.Pd., M.Si. | |
|
10.20-11.10 | |||
|
11.00-12.00 | |||
Dengan susunan tersebut, jadwal menjadi lebih optimal karena semua kelas digunakan setiap hari dan terdapat satu hari libur dari lima hari efektif. Selain itu, tidak ditemukan lagi jadwal yang tumpang tindih. Hal ini membuktikan bahwa pewarnaan simpul dengan algoritma Welsh Powell dapat digunakan untuk penyusunan jadwal mengajar dosen program studi Pendidikan Matematika Universitas Nurul Jadid. Dengan berpedoman pada kelompok hasil pewarnaan simpulnya, jadwal mengajar dapat dengan mudah diubah dan disusun kembali jika terdapat permintaan hari mengajar oleh dosen.
Pewarnaan graf dapat menjadi solusi dari permasalahan penjadwalan mengajar dosen Pendidikan Matematika Universitas Nurul Jadid yang selama ini mengalami tumpang tindih karena penyusunan jadwal masih dilakukan secara manual oleh pihak fakultas dan keterbatasan penggunaan ruangan. Dengan pewarnaan simpul menggunakan algoritma Welsh Powell, didapat jadwal mengajar yang optimal dan tidak tumpang tindih. Selain itu, jadwal juga dengan mudah diubah dan disusun kembali jika ada permintaan dari dosen.
Daftar Pustaka
Aziz, A. (2014). Desain Sistem Jaringan Komputer Dengan Menggunakan Metode
Graph Dan Algoritma Greedy. Explore IT!: Jurnal Keilmuan Dan Aplikasi Teknik Informatika, 6(2).
Azizah, N. L. (2018). Aplikasi Pewarnaan Graf untuk Optimalisasi Distribusi Raskin di
Kabupaten Sidoarjo. Jurnal Riset Dan Aplikasi Matematika (JRAM), 2(1), 31.
https://doi.org/10.26740/jram.v2n1.p31-40
Formanowicz, P., & Tanas, K. (2012). A survey of graph coloring - Its types, methods and applications. In Foundations of Computing and Decision Sciences (Vol. 37, Issue 3, pp. 223-238). Sciendo. https://doi.org/10.2478/v10209-011-0012-y
Gross, J. L., & Yellen, J. (2005). Graph Theory and Its Applications, Second Edition
(Discrete Mathematics and Its Applications). Chapman & Hall/CRC.
Mahmudah, M., & Irawati, T. N. (2018). Aplikasi Pewarnaan Graf Terhadap Pembuatan
Jadwal Ujian Semester Di Jurusan Pendidikan Matematika Universitas Islam
Jember. KadikmA, 9 (2), 12-21. https://doi.org/10.19184/KDMA.V9I2.8530
Mukherjee, C., & Mukherjee, D. G. (2014). Role of Adjacency Matrix in Graph Theory.
IOSR Journal of Computer Engineering, 16(2), 58-63.
https://doi.org/10.9790/0661-16235863
Sagala, V., & Mekar Sari, F. (2018). Optimasi Pengaturan Lalulintas Raya Gedangan dengan Penerapan Algoritma Welch-Powel dan Bilangan Khromatik. In J. Math. and Its Appl. E-ISSN (Vol. 15, Issue 1).
https://doi.org/10.12962/LIMITS.V15I1.3370
Salaki, D. T. (2011). Penentuan Lintasan Terpendek Dari Fmipa Ke Rektorat Dan
Fakultas Lain Di Unsrat Manado Menggunakan Algoritma Djikstra. Jurnal Ilmiah Sains, 11(1), 73. https://doi.org/10.35799/jis.11.1.2011.46
Siahaan, A. P. U. (2016). Implementasi Teknik Kompresi Teks Huffman. Jurnal
Informatika, 10(2). https://doi.org/10.26555/jifo.v10i2.a5070
Welsh, D. J. A. (1967). An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1), 85–86. https://doi.org/10.1093/comjnl/10.1.85
19
Discussion and feedback