ABSTRAKSI: Permasalahan penjadwalan ujian merupakan suatu permasalahan yang memiliki tingkat kompleksitivitas yang berbeda antara permasalahan di satu institusi dengan institusi yang lain tergantung banyak factor seperti misalnya banyaknya mahasiswa, banyaknya mata kuliah, dan banyaknya constrain yang digunakan. Secara umum, jadwal ujian yang memenuhi syarat adalah tidak ada mahasiswa yang mendapat 2 jadwal ujian dalam suatu slot waktu yang sama dan tidak ada ruangan yang digunakan untuk melaksanakan dua ujian dalam suatu waktu yang sama. Oleh karena itu, dua batasan tersebut menjadi syarat minimal yang harus dipenuhi dalam permasalahan penjadwalan ujian.
Pada Tugas Akhir ini, Algoritma Genetika Sub Populasi dengan Mutasi yang teararah digunakan untuk mengatasi permasalahan penjadwalan ujian. Dengan adanya Mutasi Terarah dapat menjamin fitness cenderung menjadi lebih baik dan tidak akan pernah memburuk. Selain itu, juga terdapat perpindahan/migrasi sejumlah kromosom pada selang generasi tertentu yang dapat mempengaruhi fitness sistem.
Dataset yang digunakan untuk melakukan pengujian adalah data akademik semester 1 dan semester 2 IT Telkom Bandung Indonesia dengan parameter yang diujikan adalah Migration Interval, Migration Size, dan Probabilitas Crossover. Berdasarkan observasi yang telah dilakukan dapat diketahui bahwa semakin besarnya probabilitas crossover membuat fitness cenderung menjadi memburuk.Jumlah Migration Size yang semakin mendekati jumlah kromosom per subpopulasi juga membuat fitness system memburuk. Sedangkan, untuk Migration Interval terdapat perbedaan pengaruh parameter tersebut bagi data 1 dan 2.
Dengan menggunakan sistem penjadwalan ujian dengan Algoritma Genetika Sub Populasi dengan kombinasi parameter Migration Interval 2, Migration Size 2, Probabilitas Crossover 0.5, jumlah subpopulasi 3, jumlah kromosom tiap subpopulasi 4, dan generasi 15, didapatkan jadwal ujian untuk data semester 1 memiliki total pelanggaran 0% terhadap seluruh hard-constraint dan 1.05% terhadap seluruh soft constraint. Sedangkan untuk data semester 2, dihasilkan sebuah jadwal ujian yang memiliki total pelanggaran 0% terhadap seluruh hard-constraint dan 0.29% terhadap seluruh soft constraint.Kata Kunci : : penjadwalan ujian, Algoritma Genetika (AG), Island Model Genetic Algorithm, Migration Interval, Migration Size, Probabilitas CrossoverABSTRACT: Exam Timetabling problem is a problem which has different complexivity in every institutions depends on many factors, such as, the number of students, the number of Subjects, dan the number of constraints which are used to solve the problem. Basically, Exam timetable that is acceptable is the one which doesn't have any students who has 2 schedule in a time slot and also doesn't have any room which is used for more than one different schedules in the same time slot. Therefore, those two constraints became the standart constraints that have to be fulfilled in the Exam Timetabling problem.
On this Final Task, Island Model Genetic Algorithm added with Directed Mutation was used to solve the exam timetabling problem. Directed Mutation will guarantee that the mutated chromosome will not have worse fitness and mostly the fitness became better. Beside directed mutation, there is also a migration process for certain chromosome from their own island to the new island at some certain intervals of generations .
Datasets being used for testing the system are Academic data from odd semester and from even semester of ITTelkom Bandung. Based on own observations on some tests, it can be seen that the greater the probability of crossover is, the worse fitness, evaluated from the chromosomes, will more likely be. The Migration Size value which is almost the same with the total chromosome in a island is also more likely worsening the fitness value. As for The Migration Interval, there are differences in affecting the fitness value for dataset 1 and dataset 2.
The exam schedules, which were resulted from the system using parameters : Migration Interval 2, Migration Size 2, Crossover Probability 0.5, Total Islands 3, Total Chromosome on each Island 4, and Evolution Generation 15, had total violations of hard constrains by 0% and total violations of soft constrains by 1.05% using datasets of odd semester from year 2010/2011 IT Telkom. Meanwhile, using datasests of even semester from year 2010/2011 IT Telkom, the exam schedule, generated by the system using same parameters, had total violations of hard constrains by 0% and total violations of soft constrains by 0.29%.Keyword: exam timetabling, Genetic Algorithm, Island Model Genetic Algorithm, Migration Interval, Migration Size, Probabilitas Crossover