PENJADWALAN KELAS MATAKULIAH MENGGUNAKAN VERTEX GRAPH COLORING DAN SIMULATED ANNEALING

Main Article Content

Mariana Mariana
Lely Hiryanto

Abstract

Makalah ini membahas tentang penggabungan metode vertex graph coloring dan simulated annealing dalam menyusun jadwal matakuliah. Penggabungan ini ditujukan untuk mengetahui seberapa layak dan optimal penjadwalan yang dibuat dari gabungan kedua metode ini. Vertex Graph Coloring adalah metode pemberian warna pada simpul dengan mencari vertex tetangga dan tidak bertetangga, sehingga vertex yang bertetangga akan diberi warna yang sama dan vertex yang tidak bertetangga akan diberi warna baru yang berbeda. Simulated Annealing (SA) adalah teknik optimalisasi numerik dengan prinsip thermo-dynamic. Kinerja SA sangat bergantung pada solusi awal, lingkungan pencarian dan proses pendinginan. Vertex Graph Coloring (VGC) bekerja untuk memenuhi seluruh hard constraints dan Simulated annealing bekerja untuk meneruskan proses penjadwalan dengan mengoptimalkan penjadwalan tersebut.  Hasil penjadwalan yang diperoleh dari penggabungan kedua metode ini adalah menghasilkan penjadwalan yang visible dan optimal meskipun beberapa ketentuan soft constraints masih terlanggar.

 

Article Details

Section
Articles