DECOMPOSING AND SOLVING TIMETABLING CONSTRAINT NETWORKS

The binary version of the school timetabling (STT) problem is a real-w orld example of a constraint network that includes only constraints of inequality. A new and useful representation for this real-world probl em, the STT_Grid, leads to a generic decomposition technique. The pape r presents proofs of necessary and sufficient conditions for the exist ence of a solution to decomposed STT_Grids. The decomposition procedur e is of low enough complexity to be practical for large problems, such as a real-world high school. To test the decomposition approach, a ty pical high school was analyzed and used as a model for generating STT_ Grids of various sizes. Experiments were conducted to test the difficu lty of large STT networks and their solution by decomposition. The exp erimental results show that the decomposition procedure enables the so lution of large STT_Grids (620 variables for areal school) in reasonab le time. The constraint network of a typical STT_Grid is sparse and be longs to the class of easy problems. Still, due to the sizes of STTs, good constraint satisfaction problem search techniques (i.e., BackJump ing and ForwardChecking) do not terminate in reasonable times for STT_ Grids that are larger than 300 variables.