Penjadwalan matakuliah otomatis pada perguruan tinggi menggunakan simulated annealing dan vertex graph coloring dengan algoritma largest degree ordering dan saturated degree ordering

INDONESIA:

Penjadwalan merupakan proses menempatkan data penjadwalan pada hari, ruang dan waktu yang sesuai bobot SKS. Penempatan posisi tersebut tidak boleh melanggar hard constraints dan soft constraints. Aplikasi ini menggunakan dua algoritma yaitu vertex graph coloring dan simulated annealing. Pembentukan solusi awal dengan simulated annealing masih terdapat kemungkinan matakuliah yang belum terjadwal, karena simulated annealing akan menggunakan bilangan acak untuk membentuk solusi tersebut. Kelemahan ini akan ditutupi oleh vertex graph coloring. Vertex graph coloring akan digunakan untuk membuat jadwal sehingga jadwal yang dihasilkan tidak melanggar hard constraint dan tidak ada matakuliah yang terlewatkan. Hasil penjadwalan dengan vertex graph coloring akan digunakan oleh simulated annealing sebagai solusi awal. Vertex graph coloring akan digunakan untuk membentuk jadwal yang tidak melanggar hard constraints. Simulated annealing pada aplikasi ini digunakan untuk memenuhi soft constraints. Pada algoritma ini solusi awal tidak akan dibangkitkan dengan bilangan acak, melainkan solusi awal didapatkan dari hasil penjadwalan menggunakan vertex graph coloring. Hasil uji coba penjadwalan yang dihasilkan oleh vertex graph coloring tidak ada matakuliah yang melanggar hard constraints. Namun, pada saat pengisian slot waktu terdapat beberapa matakuliah yang belum terjadwal. Sedangkan penjadwalan dengan simulated annealing yang menggunakan temperatur 1000, pereduksi 0,9 dan jumlah iterasi untuk pembentukan solusi baru adalah 20, masih terdapat beberapa matakuliah yang melanggar soft constraints. Pada simulated annealing pada aplikasi ini ruang keadaan sangat sempit sehingga kualitas dari solusi sendiri kurang bagus karena akan sering berada pada optimum local. Namun, walaupun masih terdapat jadwal yang melanggar soft constraints jadwal tersebut masih dikatakan jadwal kuliah yang valid.

ENGLISH:

Scheduling is the process of putting the scheduling data subject on day, space and time corresponding weights credits. The placement must not violate hard constraints and soft constraints. This application uses two algorithms, vertex graph coloring and simulated annealing. The formation of the initial solution with simulated annealing is still a possibility that the course has not been scheduled, because the simulated annealing will use random numbers to form the solution. This shortcoming will be covered by the vertex graph coloring. Vertex graph coloring is used to make the schedule so that resulting schedule does not violate the hard constraints and no subject missed. The result of the scheduling vertex graph coloring will be used by the simulated annealing as an initial solution. Vertex graph coloring will be uses to establish a schedule that does not violate the hard constraints Simulated annealing will explore an empty time slot and put the subjects that violate into the time slot. Trial results of scheduling generated by the vertex graph coloring there is no hard constraints are violated. However, at the time filling time slot there are some subjects that have not been scheduled. This is because the slot on the day and checked the space already used by another course grade. Scheduling by simulated annealing that uses the temperature of 1000, reducing 0,9 and the number of iterations to form the new solution is 20, there are some subjects that violates soft constraints. In simulated annealing on this application the state space is very narrow so that the quality of the solution is not good because it will often be at a local optimum. However, although there are schedule that violates soft constraints that schedule is said to be a valid class schedules.