This paper uses the simulated annealing algorithm to solve a unique staff workload scheduling problem present in a school that has about 250 academic staff and 4000 students. This paper also examines and compares various types of cooling schedules. Five types of cooling schedules, namely, geometric ratio, hybrid geometric function with reheating, quadratic equation, Huang’s equation and improved quadratic equation are tested for the scheduling problem. For each cooling schedule, ten test runs are conducted. The results show that the hybrid geometric function with reheating, whose value is directly proportional to the cost function, yields best results to the problem.