PENJADWALAN MATAKULIAH DENGAN MENGGUNAKAN ALGORITMA GENETIKA DAN METODE CONSTRAINT SATISFACTION

Abstract

Course scheduling problem has gained attention from many researchers. A number of methods have been produced to get optimum schedule. Classical definition of course scheduling cannot fulfill the special needs of lecture scheduling in universities, therefore several additional rules have to be added to this problem. Lecture scheduling is computationally NP-hard problem, therefore a number of researches apply heuristic methods to do automation to this problem. This research applied Genetic Algorithm combined with Constraint Satisfaction Problem, with chromosomes generated by Genetic Algorithm processed by Constraint Satisfaction Problem. By using this combination, constraints in lecture scheduling that must be fulfilled can be guaranteed not violated. This will make heuristic process in Genetic Algorithm focused and make the entire process more efficient. The case study is the case in Informatics Department, Faculty of Information Technology, ITS. From the analysis of testing results, it is concluded that the system can handle specific requested time slot for a lecture, that the system can process all the offered lectures, and that the system can produce schedules without violating the given constraints. It is also seen that Genetic Algorithm in the system has done optimation in finding the minimum student waiting time between lectures.