Genetic Algorithms: A New Approach To The Time-Table Problem (Extended Abstract)

this paper we present the results of a research relative to the ascertainment of limits and potentialities of genetic algorithms ([Dorigo, 1989], [DeJong-Spears, 1989], [Goldberg, 1989]) in addressing highly constrained problems, that is optimization problems, where a minimal change to a feasible solution is very likely to generate an unfeasible one. As a test-problem, we have chosen the timetable problem (TTP), a problem that is known to be NP-hard [Even-ItaiShamir, 1976], but which has been intensively investigated, given its great practical relevance [Davis-Ritter,1987], [Chahal-de Werra,1989]. The problem instance we faced consists in the construction of the lesson timetable for an italian high school. This problem may be decomposed in the formulation of several interrelated timetables, one for each pair of sections of the school considered. A pair of sections can be in fact processed as an "atomic unit", not further decomposable given its high internal dependencies, but relatively isolated from the other pairs of sections. Given this premises, the problem is described by: . a list of the teachers of the pair of sections (20 in our case), . a list of the classes involved (10 for the pair of sections), . a list of the weekly teaching hours for each class (30), . the curriculum of each class, that is the list of the frequencies of the teachers working in that class, . some external conditions, for example the hours that the teachers use to teach in other sections. The formal representation of the TTP may be the following: given the 5-tuple <H,T,A,R,f> wher