DISTRIBUTION REQUIREMENTS AND COMPACTNESS CONSTRAINTS IN SCHOOL TIMETABLING

This paper provides the following contributions: First, distribution r equirements for lessons of different lengths are modelled in a novel w ay by the use of the so-called multiple mode concept with mode identit y constraints. Second, we show that several types of constraints may b e modelled using the unifying framework of partially renewable resourc es. Among these constraints are: No class, subject, room, and teacher overlaps; class, subject, room, and teacher unavailabilities; compactn ess constraints; preassignment constraints; lectures to be given simul taneously; lunch breaks, etc. Third, we present two-phase parallel gre edy randomized and genetic methods. Fourth, we provide an instance gen erator for the generation of a representative set of instances. Fifth, the generator along with a statistical model is used for a thorough e xperimental evaluation of the methods. Computational results show that the methods solve the instances investigated close to optimality. (C) 1997 Elsevier Science B.V.