PROGRAM PEWARNAAN GRAF UNTUK PEMODELAN PENJADWALAN UJIAN SEMESTER DI JURUSAN MATEMATIKA UNIVERSITAS NEGERI MEDAN

Abstract

ABSTRAK

Masalah penjadwalan ujian  mata  kuliah  dalam  dunia  pendidikan adalah masalah yang sangat penting untuk diperhatikan.  Pada dasarnya kegiatan ujian akan berjalan dengan lancar jika penjadwalan ujian sesuai dengan kebutuhan, serta kondisi di  suatu lembaga pendidikan tersebut. Penjadwalan ujian yang dilakukan di jurusan Matematika Universitas Negeri Medan dilakukan dengan menyusun berdasarkan kelas-kelas yang ada di jurusan Matematika sehingga sering terjadi bentrokan jadwal mahasiswa yang mengambil matakuliah di kelas yang berbeda.   Permasalahan itu dapat diselesaikan dengan pewarnaan simpul graf. Penelitian ini bertujuan mengetahui hasil pewarnaan graf dalam menyelesaikan masalah penentuan jadwal ujian semester di Jurusan Matematika Universitas Negeri Medan.  Salah satu algoritma untuk menyelesaikan masalah pewarnaan graf pada penjadwalan kuliah adalah algoritma Welch-Powell. Hasil pewarnaan graf dengan menggunakan algoritma  Welch-Powell yang  diimplementasikan dalam  pemrograman Microsoft Visual Basic Application adalah tidak ada jadwal ujian yang bentrok antara matakuliah yang diambil oleh seorang mahasiswa. Setelah itu, dapat ditentukan ruang dan waktu untuk melaksanakan ujian berdasarkan pengelompokan matakuliah yang telah didapatkan pada program tersebut. Data yang diinput adalah nama matakuliah dan NIM mahasiswa yang mengambil matakuliah tersebut. Output yang dihasilkan program adalah pengelompokan matakuliah yang tidak diambil oleh mahasiswa yang sama.

Kata Kunci : penjadwalan ujian, pewarnaan graf, algoritma Welch-Powell.

ABSTRACT

The problem of scheduling the test subjects in the world of education is a very important issue to consider. Basically the test activity will run smoothly if the exam scheduling according to your needs, as well as the conditions in an institution. Scheduling the test conducted at the State University of Medan majoring Mathematics done with drawing up on the basis of the existing classes in the Department of Mathematics so that clashes are frequent schedule of students who take the class at lesson different. Problems that can be solved by staining the node count. This research aims to know the result of the coloring problem in solving graph determination of schedule examination in Mathematics Department State University of Medan. One of algorithm for graph coloring problem finishing on the scheduling lecture is Welch-Powell algorithm. The results of the colorization graph using Welch-Powell algorithm implemented in programming Microsoft Visual Basic Application is no conflicting exam schedule between lessons that taken by a student. After that, it can be determined the space and time to carry out the test based on the classification of lessons which has been obtained on the program. The inputted data is name of lessons and NIM students who take the lessons. The resulting output of the program is a grouping of lesson which is not taken by the same student.

Keywords: exam scheduling, graph coloring, Welch-Powell algorithm