TIMETABLE CONSTRUCTION USING GENERAL HEURISTIC TECHNIQUES

Barbara Koroušić-Seljak

   This paper investigates the use of a Hopfield-type neural network for timetable construction problems. This general heuristic method has provided good results in school timetabling. The main purpose of the paper is to describe the way we applied the neural network to produce feasible school timetables, which are polynomialtime in the length of the input. When mapping a school timetabling problem onto a Hopfield-type neural network, the complexity of the network can become quite large. The incorporation of a genetic algorithm allows more complex scheduling problems to be solved more efficiently. Two examples, first on a simple and second on a 'real' data set, are used to demonstrate the potential on neural networks and genetic algorithms that seem to outperform traditional Operational Research methods in solving some NP-complete problems.

Keywords: School timetabling, combinatorial optimization, Hopfield-type neural network, Liapunov function, genetic algorithm

[full-paper]