Differential evolution-based algorithm for solving the department's course-scheduling problem

This paper presents an attempt to use a Differential Evolution algorithm to solve the NP-complete course scheduling problem. The course scheduling problem involves assigning courses, faculty members, and rooms to timeslots, subject to preset constraints. Categorizing the constraints as hard and soft, the goal of this type of problem is satisfying hard constraints and minimizing the violation of the soft constraints. The methods currently used in many educational institutes depend on a manual process that is performed by one or more persons who are experienced in course scheduling. These methods are most likely to be "greedy" in their approach, so they resolve a portion, but not all, of the problem's constraints. Such methods generally require several hours or weeks of negotiation and bargaining to resolve one or more constraints. With the objective of investigating the efficiency of our Differential Evolution based algorithm, a case study is taken from the Computer Engineering (CPE) Department at the College of Engineering and Petroleum in Kuwait University (KU). A wide set of practical constraints are taken into consideration. Moreover, the desired solution is compared to both ad-hoc manual optimization and to some other well-known approaches from the literature. The results show that the proposed method can not only dramatically reduce the execution time, but also improve the quality of the solutions.