Seminar Nasional Inovasi Teknologi UN PGRI Kediri, 22 Februari 2017
ISBN : 978-602-61393-0-6 e-ISSN : 2549-7952
PERANCANGAN SISTEM PENJADUALAN KULIAH DI JURUSAN TEKNIK ELEKTRO FT.UNTIRTA MENGGUNAKAN TEKNIK PEWARNAAN GRAPH ALGORITMA BACKTRACKING WELCH-POWELL Ri Munarto1, Endi Permata2 Teknik Elektro, Fakultas Teknikn, Universitas Sultan Ageng Tirtayasa Banten 1 Pendidikan Teknik Elektro, Fakultas Keguruan dan Ilmu Pendidikan, Universitas Sultan Ageng Tirtayasa Banten E-mail:
[email protected],
[email protected] 1
Abstrak – Pewarnaan simpul graf adalah teknik mewarnai simpul-simpul pada graf sehingga tidak ada simpul-simpul yang bertetangga, yaitu terhubung langsung dengan minimal sebuah sisi, memiliki warna yang sama. Hal ini juga dikaitkan dengan penggunaan warna seminimal mungkin. Teknik pewarnaan simpul graf merupakan salah satu subjek yang menarik dan terkenal dalam bidang graf. Perencanaan jadwal di sini khususnya diterapkan pada pekerjaanpekerjaan atau hal-hal yang saling terkait, misalnya hal-hal yang berlangsung pada waktu yang sama, atau pekerjaan yang menggunakan sumber daya yang sama. Dalam penelitian ini, permasalahan yang dibahas adalah pewarnaan simpul graph untuk penjadwalan mata kuliah. Pertemuan kuliah yang meliputi mata kuliah, dosen, dan ruang kuliah diidentifikasikan sebagai sebuah simpul (vertices). Setiap simpul dimana mata kuliahnya diajarkan oleh dosen yang sama atau diberikan pada ruang yang sama dihubungkan dengan sebuah busur (edges) yang berarti mata kuliah tersebut tidak dapat dilakukan secara bersamaan. Fungsi objektif dalam pewarnaan simpul graph adalah meminimumkan konflik pewarnaan, yaitu simpul-simpul bertetangga yang berwarna sama.Hasil pewarnaan simpul graph merupakan solusi penjadwalan kuliah dimana simpul-simpul yang berwarna sama merepresentasikan mata kuliah dapat dilaksanakan dalam waktu yang bersamaan dan jumlah warna yang didapat merupakan jumlah sesi perkuliahan.
Kata Kunci — pewarnaan graf, bilangan kromatik, penjadualan kuliah Abstract –Staining node graph is the technique of coloring the vertices in a graph so that no neighboring vertices, are connected directly with at least a side, have the same color. It is also associated with the use of color to a minimum. Graph vertex coloring technique is one of the subjects interesting and famous in the field of graph. Planning the schedule here specifically applied to jobs or things are interrelated, such things are taking place at the same time, or jobs that use the same resources. In this study, the issues discussed are the vertices of graph coloring for scheduling courses. Meeting lectures covering subjects, lecturers and lecture halls identified as a vertex (vertices). Each node where his courses taught by professors of the same or be given the same space connected by an arc (edges) which means the course can not be done simultaneously. The objective function in coloring the vertices of graph coloring is to minimize conflict, namely the vertices adjacent colored graph vertex coloring sama.Hasil a college scheduling solution where the vertices of the same color represents the course can be implemented at the same time and the number of colors are deemed number of sessions lectures Keywords — Graph coloring, chromatic number, scheduling lectures
277
Seminar Nasional Inovasi Teknologi UN PGRI Kediri, 22 Februari 2017 1.
ISBN : 978-602-61393-0-6 e-ISSN : 2549-7952
PENDAHULUAN
Coloring merupakan alternatif metode yang tepat dalam sistem penyusunan jadwal, seperti dalam penelitian ataupun jurnal-jurnal sebelumnya Graph Coloring digunakan sebagai penjadwalan perkuliahan di Program Studi Pendidikan Matematika UNWIDHA Klaten [7], penyusunan jadwal Perkuliahan di Jurusan Pendidikan Matematika FMIPA UNG [9].
Penjadwalan kuliah merupakan suatu pekerjaan rutin dalam system akademik di Perguruan Tinggi yang dilakukan setiap menghadapi semester baru. Pada pelaksaanaannya, seringkali jadwal yang telah dikeluarkan belum fix sehingga membutuhkan adanya penjadwalan ulang. Hal ini mengakibatkan perkuliahan di awal semester berjalan tidak efektif karena harus melakukan penyesuaian jadwal dengan keadaan real setelah jadwal dikeluarkan. Selain itu, kesulitan dalam hal pencarian slot yang masih kosong juga menjadi suatu kendala terutama pada saat mencari jadwal kuliah pengganti atau kuliah tambahan. Dalam melakukan penjadwalan kuliah, diperlukan pemikiran yang cukup rumit untuk dapat memetakan sejumlah komponen penjadwalan (mata kuliah, dosen, mahasiswa, ruang, dan waktu) ke dalam timeslot (matriks ruang dan waktu) dengan mempertimbangkan semua batasan yang ada. Proses manual memerlukan waktu yang cukup lama untuk dapat melakukan hal ini dan memungkinkan terjadinya pelanggaran constraint akibat human error. Pelanggaran constraint dalam penjadwalan menjadikan jadwal tidak valid dan harus direkonstruksi ulang. Jika kejadian seperti ini selalu berulang tiap kali menghadapi semester baru, maka sepatutnya permasalahan ini mendapat prioritas untuk dicari solusinya demi peningkatan mutu sistem akademik di Perguruan Tinggi. Permasalahan penjadwalan kuliah terkait erat dengan masalah optimasi. Oleh karena itu, pengembangan sistem penjadwalan kuliah dilakukan dengan melalui beberapa iterasi perbaikan. Fungsi tujuannya adalah memenuhi sejumlah constraint penjadwalan, seperti menghindari terjadinya bentrok jadwal. Dalam kajian ilmu di Matematika Diskrit, teori graf memberi solusi untuk permasalahan ini melalui bahasannya tentang pewarnaan graf menggunakan algorithma backtracking. Pembangunan sistem penjadwalan kuliah yang menerapkan teori ini diharapkan mampu menjawab permasalahan ini secara jitu sehingga dapat diimplementasikan untuk penjadwalan kuliah. Penelitian tentang penjadwalan perkuliahan telah dilakukan pada beberapa penelitian sebelumnya. Metode Graph
2. METODE PENELITIAN Pada penelitian kali ini akan menggunakan model prototipe sebagai metode untuk mengembangkan sistem. Dapat dilihat pada Gambar 1 dibawah ini:
Gambar 4. Model Pengembangan system Berikut ini penjelasan secara detail prosedur penelitian yang dilakukan dalam penelitian ini : 1.Pada langkah ini data yang telah didapatkan dianalisis dan dikelompokan untuk mendapatkan beberapa model teknologi yang cocok untuk membangun sistem dan faktorfaktor yang berpengaruh pada sistem. Selanjutnya dilakukan tabulasi data dan penentuan faktor yang paling berpengaruh, serta dipilih teknologi yang paling cocok. 2. Merancang sistem penjadwalan kuliah di Jurusan Teknik Elektro FT UNTIRTA Menggunakan Teknik Pewarnaan Graph Algorithma Backtracking Welch-Powell dengan urutan prioritas berdasarkan faktor yang paling berpengaruh. 3. Mengimplementasikan metode yang telah dipilih pada perancangan system yang telah ada. Proses ini dilakukan dengan penelitian dan praktikum di laboratorium 4. Pengujian dilakukan dengan uji validitas dan reliabilitas data dengan variable efisiensi waktu, akurasi informasi, dan otomatisasi data. Selain itu dilakukan pengujian terhadap kecepatan backup dan sinkronisasi data sehingga didapat sebuah tabel pengamatan.
278
Seminar Nasional Inovasi Teknologi UN PGRI Kediri, 22 Februari 2017
ISBN : 978-602-61393-0-6 e-ISSN : 2549-7952
5. Selanjutnya dilakukan evaluasi dan analisis data ulang agar didapatkan rancangan sistem versi final.
2.
Masalah penyusunan jadwal disini adalah masalah penjadwalan kuliah di jurusan teknik elektro Fakultas Teknik UNTIRTA. Karena semester yang tengah berlangsung adalah semester ganjil maka penulis asumsikan bahwa penjadwalan kuliah yang dijadwalkan disini adalah penjadwalan kuliah semester ganjil. Permasalahan yang akan diselesaikan adalah menjadwalkan seluruh mata kuliah yang ada pada semester ganjil dan mencari jumlah hari yang optimal untuk menyelenggarakan perkuliahan.
3.1 Algoritma Backtracking untuk Pewarnaan Graph Untuk menyelesaikan persoalan pewarnaan graph, kita perlu membuat sebuah matriks ketetanggaan GRAPH[1..n][1..n] yang merupakan matrix of Boolean. GRAPH(i,j) bernilai true jika simpul I dan j bertetangga dan bernilai false jika sebaliknya. Jenis warna atau bilangan kromatik direpresentasikan dengan bilangan 1,2,…,m dan solusi akan direpresentasikan dengan ntuple {X(1),X(2),..,X(n)} dimana X(i) bernilai bilangan warna dari simpul i. Masukan: 1. Matriks ketetanggan GRAF[1..n, 1..n] GRAF[i,j] = true jika ada sisi (i,j) GRAF[i,j] = false jika tidak ada sisi (i,j)
2.1 Batasan (Constraints) dalam pembuatan jadwal perkuliahan 1. Mata Kuliah yang akan dijadwalkan adalah seluruh mata kuliah pada semester 1, 3, 5 dan 7. 2. Ruangan yang tersedia untuk penyelenggaraan perkuliahan adalah 11 dengan kapasitas masing-masing ruangan adalah 40 mahasiswa. 3. Tidak ada mahasiswa yang mempunyai lebih dari satu jadwal perkuliahan pada saat yang sama. 4. Mata kuliah pada semester yang sama atau pada spesialisasi yang sama tidak dijadwalkan pada hari yang sama. 5. Ruang perkuliahan harus memuat seluruh mahasiswa. Jika tidak cukup maka mahasiswa dibagi menjadi dua atau lebih grup
2. Warna Dinyatakan dengan integer 1, 2, ..., Keluaran: 1. Tabel X[1..n], yang dalam hal ini, x[i] adalah warna untuk simpul i.
2. Algoritma: { Kamus global } Deklarasi const n = … { jumlah simpul graf } const m = … { jumlah warna yang disediakan } type matriks = array[1..n,1..n] of boolean type tabel = array[1..n] of integer; GRAF : matriks procedure PewarnaanGraf(input k : integer) { Mencari semua solusi solusi pewarnaan graf; rekursif Masukan: k adalah nomor simpul graf. Keluaran: jika solusi ditemukan, solusi dicetak ke piranti keluaran } Deklarasi stop : boolean
3. HASIL DAN PEMBAHASAN Permasalahan penjadwalan diatas akan diselesaikan dengan teknik pewarnaan graph (Graph Coloring) yaitu pewarnaan simpul (vertex coloring). Untuk proses mewarnai simpul, algoritma yang kami pilih adalah algoritma Backtracking. Karena algoritma ini dapat menangani jumlah simpul yang besar. Dan hanya pencarian yang mengarah ke solusi saja yang dikembangkan, sehingga waktu pencarian dapat dihemat. Representasi masalah dalam graph: 1.
-
Mata Kuliah pada semester 3 : 7 Mata Kuliah pada semester 5 : 24 Mata Kuliah pada semester 7 : 30 Sisi (Edge) Sisi disini merepresentasikan mata kuliah berada pada semester sama atau merupakan spesialis yang sama
Simpul (Vertex) Simpul disini adalah Mata Kuliah yang akan diadakan yaitu: Mata Kuliah pada semester 1 : 7
279
Seminar Nasional Inovasi Teknologi UN PGRI Kediri, 22 Februari 2017
ISBN : 978-602-61393-0-6 e-ISSN : 2549-7952
Algoritma: stopfalse while not stop do {tentukan semua nilai untuk x[k] } WarnaBerikutnya(k) {isi x[k] dengan sebuah warna} if x[k] = 0 then {tidak ada warna lagi, habis} stoptrue else if k=n then {apakah seluruh simpul sudah diwarnai?} CetakSolusi(X,n) else PewarnaanGraf(k+1) {warnai simpul berikutnya} endif endif Algoritma: stopfalse while not stop do x[k](x[k]+1) mod (m+1) {warna berikutnya} if x[k]=0 then {semua warna telah terpakai} stoptrue else {periksa warna simpul-simpul tetangganya} j1 keluarfalse while (jn) and (not keluar) do
endif endif endwhile Algoritma Pewarnaan Graph 1. Mulai 2. Buat matrik data admin (matrik antara ruangan dan waktu) 3. Buat matrik adjacency(matrik keterhubungan), yang menyatakan keterhubungan antar ruangan. Matrik A[i,j] dinyatakan sebagai suatu matriks keterhubungan dari graph G, berukuran n x n (matrik bujur sangkar). Matrik A terdiri dari elemen 1 dan 0 dimana Aij = 1, jika ada sisi yang menghubungkan simpul vi dan vj. Aij = 0, jika tidak ada sisi yang hubungkan simpul vi dan vj 4. Gambar bentuk graph yang diinginkan dengan circle (x(i), y(i)), 0.1 sebagai simpul 5. Lakukan sebuah kondisi if A [i,j] = 1 then line (x(i),y(i)) – (x(j),y(j)). Yang menyatakan bahwa jika simpul tersebut saling berhubungan maka hubungkan dengan sebuah sisi 6. Warnai setiap simpul pada graph tersebut dengan menggunakan konsep backtracking. Backtracking 1. Mulai 2. Inisialisasi simpul pertama 3.Cek kondisi Apakah simpul ke 1 berhubungan dengan simpul ke 2..ke n? a. Jika simpul tersebut behubungan maka warna tidak boleh sama b. Ulangi ke langkah 3 sampaai ke n c. Selesai 7. Cetak matriks A[i,j] dan cetak gambar graph yang sudah diwarnai 8. Selesai
if (GRAF[k,j]) {jika ada sisi dari simpul k ke simpul j} and {dan} (x[k] = x[j]) {warna simpul k = warna simpul j } then keluartrue {keluar dari kalang} else jj+1 {periksa simpul berikutnya} endif endwhile { j > n or keluar} if j=n+1 {seluruh simpul tetangga telah diperiksa dan ternyata warnanya berbeda dengan x[k] } then stoptrue {x[k] sudah benar, keluar dari kalang}
280
Seminar Nasional Inovasi Teknologi UN PGRI Kediri, 22 Februari 2017
ISBN : 978-602-61393-0-6 e-ISSN : 2549-7952 dapat diketahui mata kuliah yang mana saja yang dapat dijadwalkan pada slot waktu ( time slot) yang sama. Dari Tabel X[1..n] juga dapat diketahui jumlah warna yang digunakan untuk mewarnai graph. Oleh karena itu, dari jumlah warna tersebut kita dapat mengetahui jumlah hari yang digunakan untuk menyelenggarakan ujian keseluruhan mata kuliah pada semester ganjil yaitu semester 1, 3, 5, dan 7. Berdasarkan analisa diatas, dapat diketahui bahwa menjadwalkan seluruh mata kuliah yang ada pada semester ganjil dan mencari jumlah hari yang optimal untuk menyelenggarakan seluruh perkuliahan dapat diselesaikan. Akan tetapi penentuan ruangan ujian masih harus dilaksanakan secara manual, dan penentuan ruangan dapat digunakan untuk lebih dari satu mata kuliah juga dilaksanakan secara manual. Permasalahan penjadwalan diselesaikan dengan teknik pewarnaan graph (Graph Coloring) yaitu pewarnaan simpul (vertex coloring). Untuk proses mewarnai simpul, algoritma yang kami pilih adalah algoritma Backtracking. Karena algoritma ini dapat menangani jumlah simpul yang besar. Dan hanya pencarian yang mengarah ke solusi saja yang dikembangkan, sehingga waktu pencarian dapat dihemat. Representasi masalah dalam graph: 1. Simpul (Vertex) Simpul disini adalah Mata Kuliah yang akan diadakan yaitu:
Gambar 4. Flowchart Pewarnaan graph
• Mata Kuliah pada semester 1 : 7 • Mata Kuliah pada semester 3 : 7 • Mata Kuliah pada semester 5 : 24 • Mata Kuliah pada semester 7 : 30 2. Sisi (Edge) Sisi disini merepresentasikan mata kuliah berada pada semester sama atau merupakan spesialis yang sama
Gambar 5. Flowchart Prosedur Backtracking 3.2 Hasil Output atau keluaran dari algoritma Backtracking ini adalah Tabel X[1..n], dimana x[i] adalah warna untuk simpul i. Oleh karena itu dari algoritma ini akan menghasilkan beberapa simpul dengan warna sama. Pada teknik pewarnaan graph, simpul dengan warna sama dapat dijadwalkan pada waktu yang sama. Dalam masalah penjadwalan perkuliahan dimana simpul adalah mata kuliah, maka dari Tabel X[1..n]
281
Seminar Nasional Inovasi Teknologi UN PGRI Kediri, 22 Februari 2017
ISBN : 978-602-61393-0-6 e-ISSN : 2549-7952 dibuat menggunakan Implementasi program yang telah dibuat selain menggunakan software Borland Delphi 7, program bisa dikembangakan menggunakan software Java dan Microsoft Visual Basic.
DAFTAR PUSTAKA [1] Astuti, Setia. 2011. Penyusunan Jadwal Ujian Mata Kuliah dengan Algoritma Pewarnaan Graf Welch-Powell, Jurnal Dian Vol.11 No.1 Januari 2011. [2] Astuti, Setia. 2011. Penyusunan Jadwal Ujian Mata Kuliah dengan Algoritma Pewarnaan Graf Welch-Powell, Jurnal Dian Vol.11 No.1 Januari 2011.
4. SIMPULAN
[3] Deo, Narsingh. 1974. Graph theory with application to engineering and computer scienc, McGraw-Hill, New York
1. Dalam menyelesaikan penjadualan kuliah menggunakan teori graph, maka yang harus dilakukan adalah mengubah bentuk data yang ada ke bentuk graph. Kemudian menentukan bilangan khromatik yang digunakan untuk mengetahui banyak warna pada solusi awal. Kemudian menyelesaikan masalah pewarnaan graph dengan algoritma backtracking. 2. Dari hasil pewarnan graph dengan algoritma backtracking titik-titik dikelompokkan berdasarkan warnanya dan akan dibuat jadwal kuliah dengan ketentuan titik-titik yang warnanya sama dipetakan ke waktu kuliah yang sama dan titik-titik yang warnanya sama dipetakan ke ruang kuliah yang berbeda.
[4] Goodaire, E.G dan M. M. Parmenter. 1998. Discrete Mathematics with Graph Theory. New Jersey : Prentice-Hall. [5] Hariyanto, Bambang. 2003 Struktur Data Bandung. Informatika [6] Munir, Rinaldi. 2012. “Matematika Diskrit Revisi ke-5”. Bandung: Informatika [6] Rosen, Kenneth, H 1999), Discrete and Combinatorial Matematics, 8, 495-557. CRC Press. [7] Tasari. Aplikasi Pewarnaan Graf pada Penjadwalan Perkuliahan di Program Perkuliahan Pendidikan Matematika UNWIDHA Klaten. Magistra (2014) No.82. ISSN.0215-9611.
5. SARAN 1. Dalam mengatasi permasalahan penjadualan kuliah menggunakan pewarnaan graph selain dengan menggunakan algoritma backtracking masih banyak algoritma lainnya yang dapat dikembangkan diantaranya adalah algoritma sequential color, algoritma genetika, algoritma mememtika dan algoritma koloni lebah. 2. Pada penelitian ini mengimplementasikan program yang
. [8] Suryadi, Didi, dan Nanang Priatna. “Pengantar Dasar Teori Graph”. [9] Yahya, N.I. dkk. Penerapan Konsep Graf dalam Penyusunan Jadwal Perkuliahan di Jurusan Pendidikan Matematika FMIPA UNG.
282
