Comparison of neural and heuristic methods for a timetabling problem

We compare the performance of an annealed neural network to that of graph colouring and pricing heuristics in solving a timetabling problem. The problem is to schedule a set of interviews subject to contiguity and availability constraints. The methods are applied to randomly generated problems of varying size and difficulty and compared based on solution quality and execution time. We find that the neural network generally yields slightly better results in terms of the best solutions found over all parameter settings, but at extensive computational cost. The average performance of the annealed neural network using a single parameter setting is less impressive, failing to exceed that of the best heuristic solutions for any of the problem sets studied. Thus, while the annealed neural network has the potential to find very good solutions, the heuristic procedures appear to be more effective for practical purposes.