Algorithms for university course scheduling problems

Rad se bavi problemom planiranja predavanja gdje postoji niz kolegija, predavača i učionica. Kolegiji se dodjeljuju i planiraju tako da se maksimalno zadovolje preferencije. Razvijamo matematički model problema u obliku linearnog programa cijelih brojeva. Manji se problem može optimalno riješiti primjenom komercijalnog softvera. Zatim razvijamo tri različite metaheuristike na temelju umjetnih imunih, genetičkih i algoritama simuliranog kaljenje. Te tri metode rješenja opremljene su novim postupcima kao što su operatori kretanja i križanja. Parametri predložene metaheuristike najprije se usklađuju, a zatim procjenjuju optimalnim rješenjima koje je model pronašao. Nadalje se procjenjuju usporedbom njihovih performansi. Eksperimenti pokazuju da je umjetni imuni algoritam uspješniji od drugih algoritama.This paper deals with the problem of course scheduling where we have a set of courses, lecturers and classrooms. Courses are assigned and scheduled in such a way that the total preference is maximized. We develop the mathematical model of the problem in form of a linear integer program. The small sized problem can be solved to optimality using commercial software. We then develop three different metaheuristics based on artificial immune, genetic and simulated annealing algorithms. These three solution methods are equipped with novel procedures such as move and crossing operators. The parameters of the proposed metaheuristics are first tuned, and then they are evaluated with optimal solutions found by the model. They are, furthermore, evaluated by comparing their performance. The experiments demonstrate that the artificial immune algorithm performs better than the other algorithms