Timetabling By Gas Por Zoltran Petres

Genetic Algorithms in Timetabling. A New Approach.
S´ ndor Gy˝ ri a o gyori@szit.bme.hu Zolt´ n Petres a petres@szit.bme.hu Budapest University of Technology and Economics Department of Measurement and Information Systems M˝ egyetem rkp. 9., Budapest, Hungary, H-1521 u Abstract — The timetabling problem comes up every year in educational institutions, which has been solved by leveraging humanresource for a long time. The problem is a special version of the optimization problems, it is computationally NP-hard. Although, there are some attempts to apply computer based methods, their use is limited by the problem’s complexity, therefore Genetic Algorithms were applied, because they are robust enough in such a huge problem space. In this paper a new and more flexible timetablerepresentation, the set representation is introduced which meets the demands better than former ones. The proposed method proved to be efficient in real life application of a secondary school, as well. I. INTRODUCTION The timetabling problem, which has an important role typically in education, is a special version of the optimization problems found in real life situations. The timetabling problem has always beensolved by leveraging human resource in educational institutions. During the process, numerous aspects have to be taken into consideration. Almost a week of work of an experienced person is needed to produce a timetable for an average institution and the result is often not satisfactory; it does not meet all the requirements. What is more, when the preconditions change, the whole work becomesunusable, and has to be restarted from scratch. The problem—as almost all optimization problem—is computationally NP-hard. Therefore, only the important conditions can be considered during the manual arrangement process, but it is still extremely complex to find the optimal solution of this reduced problem. Thus, a good timetable generator software that would take into consideration not only theessential conditions necessary for a usable timetable, but also other important didactic and organizational requirements would be very useful. This became reality by the tremendous growth of computing capacity. In case of optimization problems [1, 2]—as the problem described in this paper—genetic algorithms (GA) [3, 4] proved to be sufficient. The paper is organized as follows: In Section II. thetimetabling problem including hard and soft constraints and classical representations is discussed. Then the set representation is introduced in Section III. Genetic Algorithms are presented as a solution for the problem in Section IV. and various operators and improvement technics are analyzed in Section V. Section VI. is devoted to experimental results. II. THE TIMETABLING PROBLEM The timetablingproblem comes up every year in educational institutions. Students, teachers, lessons and classrooms have to be arranged optimally. It is very difficult to define how good a potential timetable is, but much easier is to declare when a timetable is unusable as it is always exact. By consulting to a person experienced in timetabling problem, the situations that should be avoided in order to get a nearlyoptimal result can easily be specified, namely the constraints should be satisfied by the timetables. Hard and soft constraints should be distinguished. A. Hard constraints Hard constraints have to be taken into consideration very strictly, because the timetables that violate just one of these are unusable. The finite “resources” belong to this group. The class clash situation is when a student of aclass should participate in more than one lesson at the same time. Of course, the splitted lessons do not cause class clashes. The teacher clash is similar to the class clash, but in this case a teacher should give more than one lesson at the same time. The lessons held for merged classes by the same teacher do not cause teacher clashes. Finite room capacity: It is not possible to give two or more...