In this paper, we focus on solving problems modeled after a real-world high school timetable problem. It includes multiple objectives and a variety of constraints. It mainly involves producing an optimal schedule for each teacher and for each class. The conventional integer programming approach seems to have some difficulties with solving such problems. The versatility of our proposed heuristic based on a modification of the threshold accepting method is exemplified through our problem solving. For comparison sake, simulated annealing was also used to solve the same problems.