With the aim of minimizing the energy consumption cost and taking the billet heating quality as the constraint condition, a mathematical model was established based on the billet heating model to solve the optimum heat institution of the reheating furnace. The tabu search algorithm was employed to solve the model. The results of the industrial production data optimization showed that the proposed mathematical model and the solving method could fully meet the practical production demand of the reheating furnace. In addition to satisfying the heating quality requirements, the energy consumption is reduced and the oxidation loss is decreased. Compared with the original one, the heating institution obtained from the mentioned model and algorithm had a better performance on energy efficiency.