Solving University Scheduling Problem with a Memetic Algorithm

Abstract

Scheduling problem is one of the Non-deterministic Polynomial (NP) problems. This means that using a normal algorithm to solve NP problems is so time-consuming a process (it may take months or even years with available equipment), and thus such an algorithm is regarded as an impracticable way of dealing with NP problems. The method of Memetic Algorithm presented in this paper is different from other available algorithms. In this algorithm the problem of a university class Scheduling is solved through applying a new chromosome structure, modifying the normal genetic methods and adding a local search, which is claimed to considerably improve the solution. We included the teacher, class and course information with their maximal constraints in the proposed algorithm, and it produced an optimized scheduling table for a weekly program of the university after creating the initial population of chromosomes and running genetic operators. The results of the study show a high efficiency for the proposed algorithm compared with other algorithms considering maximum Constraints.

DOI: http://dx.doi.org/10.11591/ij-ai.v1i2.512