IMPLEMENTASI ALGORITMA WELSH POWELL PADA PENJADWALAN SIDANG SKRIPSI DENGAN CONSTRAINT KESIBUKAN DOSEN - M. Arief Budiman, - (2018)
Penjadwalan sidang skripsi telah menjadi sebuah permasalahan yang berulang secara berkala. Faktor-faktor yang mempengaruhi penjadwalan adalah jumlah mahasiswa, jumlah dosen, jumlah waktu, dan kesibukan dosen. Permasalahan ini dikategorikan dalam model permasalahan constraint satisfaction problem (CSP). Tiap sidang menjadi sebuah variabel yang akan diisi dengan waktu dari domain yang telah diberikan. Pemberian waktu akan dibatasi dengan kesibukan dosen. Penyelesaian model dilakukan dengan algoritma pewarnaan graf Welsh-Powell. Masalah digambarkan dengan constraint graph dan diselesaikan dengan iterasi pemberian warna terurut sesuai dengan derajat tiap vertex hingga seluruh sidang terjadwal atau tidak ada waktu yang sesuai. Implementasi menggunakan aplikasi yang dibuat dengan Java dan format data JSON. Hasil dari skenario pengujian penjadwalan sidang yang sudah pernah berhasil dijadwalkan menunjukan bahwa algoritma berhasil menjadwalkan 80% set sidang. Kegagalan 20% disebabkan oleh sedikitnya waktu yang diberikan sehingga tidak memungkinkan dijadwalkan secara sempurna. Sedangkan berdasarkan pengujian dengan kesibukan dosen menunjukan keberhasilan yang rendah pada tingkat kesibukan dosen yang tinggi. ;---Scheduling thesis trial has become a recurring problem on a regular basis. Factors affecting the scheduling are the number of students, the number of lecturers, the amount of time, and the busyness of the lecturer. This problem is categorized in the constraint satisfaction problem (CSP) model. Each trial becomes a variable that will be filled with time from the given domain. Giving time will be limited with the busyness of the lecturer. Model solved by Welsh-Powell graph coloring algorithm. Problems are delineated with constraint graph and completed by iterating colored assignments according to the degree of each vertex until the whole trial is scheduled or there is no corresponding time. Implementation using applications made with Java and JSON data formats. The results of trial scheduling test scenarios that have been successfully scheduled indicate that the algorithm successfully schedules 80% of the trial. The 20% failure caused by insufficient time that make complete scheduling impossible. While based on the test with the busyness of the lecturer showed a low success at high busyness level.