ABSTRAKSI: Masalah penjadwalan kuliah merupakan masalah penjadwalan yang perlu diselesaikan pada setiap universitas agar setiap jadwal dapat dialokasikan sesuai dengan slot waktu, ruangan, pengajar, dsb. Terdapat juga beberapa batasan-batasan yang perlu diperhatikan ketika kita menyelesaikan masalah penjadwalan ini. Adanya batasan-batasan ini menjadikan penjadwalan pada suatu universitas mempunyai kompleksitivitas yang berbeda dengan universitas yang lainnya.
Tugas Akhir ini akan mencoba menyelesaikan masalah penjadwalan kuliah ini dengan menerapkan Algoritma Genetika dengan Local Search. Algoritma Genetika merupakan algoritma yang sudah cukup populer dan efektif untuk diterapkan pada banyak masalah optimasi kombinatorial termasuk masalah penjadwalan. Algoritma Genetika yang dipakai akan menerapkan mutasi terarah dimana hasil dari setiap generasi kualitasnya sama atau lebih baik dari generasi sebelumnya.
Selain dengan mutasi terarah, Algoritma Genetika yang dipakai akan dipadukan dengan Local Search agar hasil yang didapat bisa cepat mencapai fitness masksimum. Dataset yang digunakan untuk melakukan pengujian adalah data akademik semester 1 dan semester 2 IT Telkom tahun ajaran 2010/2011. Analisis yang dilakukan akan mengujikan bagaimana pengaruh ukuran populasi dan algoritma Local Search terhadap kualitas kromosom yang dihasilkan pada data yang diujikan. Kualitas kromosom diukur berdasarkan nilai fitness yang dihasilkan tiap kromosom dalam suatu populasi.
Kata Kunci : penjadwalan kuliah, Algoritma Genetika (AG), mutasi terarah, Algoritma Local Search, ukuran populasi, nilai fitnessABSTRACT: The university timetabling problem is a scheduling problem that many educational institutions need to solve in order to plan their courses and/or exams by allocating these events to specific timeslots, rooms, lecturers…etc. There are also a number of constraints that must be observed while solving this problem. The existence of these constraints make scheduling at a university has a different complexivity with other universities.
This final project will try to resolve the scheduling problem by applying Genetic Algorithm with Local Search. Genetic algorithm is an algorithm that has been popular and effective enough to be applied to many combinatorial optimization problems including scheduling problem. Genetic algorithms are used to implement directed mutation in which the results of each generation are the same or better quality than previous generations.
Beside directed mutation, which is used Genetic Algorithm with Local Search will be integrated so that the results obtained can quickly reach maximum fitness. Datasets being used for testing the system are Academic data from odd semester and from even semester of ITTelkom Bandung. The analysis carried out will be testing how the influence of population size and the Local Search algorithm on the quality of the resulting chromosomes in the data tested. Quality is measured by the fitness of chromosomes generated per chromosome in a population.
Keyword: university timetabling, genetic algorithm, directed mutation, local search algorithm, population size, fitness value