Penjadwalan Ujian pada metode greedy


Penjadwalan Ujian

Kali ini kita akan mencoba memecahkan masalah penjadwalan dengan cara melakukan pewarnaan pada sebuah graf.Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek. Representasi visual dari graf adalah dengan menyatakan objek dengan simpul, noktah, bulatan, titik, atau vertex, sedangkan hubungan antara objek dinyatakan dengan garis , edge atau ruas.

Pewarnaan graf adalah proses pelabelan setiap simpul dalam graf dengan label tertentu (warna) sehingga tidak ada dua simpul bertetangga yang memiliki warna sama. Warna yang kita gunakan untuk mewarnai objek diusahakan seminimal mungkin. Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul disebut bilangan kromatik

Tabel berikut adalah contoh penjadwalan kuliah dalam graf:

Tabel 1 Contoh tabel penjadwalan kuliah 
 
Gambar 1
Pada tabel diatas 6 kolom yang dilambangkan dengan huruf menunjukan nama mata kuliah, sedangkan 8 baris yang ditunjukan dengan angka menunjukan mahasiswa, sedangkan angka 1 menandakan mata kuliah yang diambil, 0 berarti mata kuliah yg tdk diambil.
Pada tabel diatas menunjukan adanya mahasiswa yang mengambil 2 mata kuliah sekaligus.
Maka berdasarkan tabel diatas, tim pembuat jadwal harus membuat jadwal, dimana siswa harus dapat mengikuti semua ujian dari mata kuliah yang diambil, berarti mata kuliah yang diambil bersamaan oleh seorang mahasiswa tidak boleh dijadwalkan pada waktu yang sama.
Maka untuk menyelesaikan permasalahan tersebut, hal yang dilakukan adalah
  1. Menggambarkan Simpul yang menunjukan mata kuliah
  2. Membuat ruas atau garis penghubung menyatakan ada mahasiswa yang memilih kedua mata kuliah itu.
  3. Memilih simpul yang berwarna sama, simpul yang berwarna sama menunjukan tidak ada mahasiswa yang mengambil mata kuliah tersebut secara bersamaan, berarti boleh dijadwalkan pada waktu yang sama
untuk lebih jelasnya lihat gambar berikut
Graphic1
Berdasarkan graf tersebut kita menyimpulkan, bahwa apabila terdapat dua buah simpul dihubungkan oleh sisi atau ruas, maka ujian kedua mata kuliah itu tidak dapat dibuat pada waktu yang sama. Maka untuk mempermudah kita bisa memberi warna pada masing-masing simpul, dimana warna yang berbeda dapat diberikan pada simpul graf yang menunjukkan bahwa waktu ujiannya berbeda, warna yang digunakan harus seminimal mungkin dengan ketentuan simpul yang berdampingan atau bertetangga tidak boleh berwarna sama, berikut cara pemberian warnanya.
GRAPH
M = Merah

P = Putih
H = Hijau
Dari gambar diatas kita memulai memberikan pewarnaan pada simpul F dengan warna merah, kemudian kita memberi warna pada simpul A dengan warna putih, selanjutnya kita memberi warna simpul E dengan warna merah, dilanjutkan ke simpul B kita beri warna Putih, kemudian kita lanjutkan ke simpul D, kembali kita beri warna Merah, terakhir kita mewarnai simpul C dengan warna hijau, mengapa simpul C berwarna hijau, ini dikarenakan ketentuan yang telah kita bahas diatas, bahwa setiap simpul yang bertetangga tidak boleh berwarna sama, kita lihat simpul C bertetangga dengan simpul B yang berwarna putih, dan simpul D yang berwarna merah, maka simpul C harus diberi warna selain warna Merah dan Putih.
Kemudian kita kelompokan simpul yang mempunyai warna sama, simpul dengan warna sama berarti bisa dijadwalkan dalam waktu yang bersamaan karena tidak ada mahasiswa yang mengambil mata kuliah tersebut secara bersamaan, dari gambar 3 diperoleh hasil:
  1. Simpul merah = F, E, D
  2. Simpul Putih = A, B
  3. Simpul hijau = C
Catatan:
Untuk posisi peletakan Simpul Bisa Bebas
Awal pemberian warna boleh bebas
Warna yang digunakan Bebas
Awal pemberian warna mempengaruhi susunan Jadwal

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s