Subcost-guided search – experiments with timetabling problems

This paper reports on experiments with ‘subcost-guided’ heuristic search processes for some modified school timetabling problems where several subobjectives are combined into a single overall objective. Subcost guidance is incorporated into two methods: a Simulated Annealing method and a Threshold Acceptance method. Significant improvements are achieved in both cases, especially for the hardest problem.