Reheating furnace production is one of the important procedures that affect the utilization rate of hot rolling mills and the quality of rolling plans. By analyzing the influence of reheating furnace on hot rolling production, two key factors of slab, standard time in furnace and discharge temperature, are extracted. The integer programming model of hot-rolled slab rolling plans is established, and an adaptive neighborhood search algorithm is proposed. The constraint satisfaction strategy, the adaptive search strategy and the reverse learning neighborhood search strategy are designed in the algorithm. Two value selection rules of the constraint satisfaction strategy are designed for target characteristics and furnace factors to generate high-quality initial solutions. Using the adaptive search strategy can select neighborhood structure and terminate neighborhood search autonomously, and optimize the neighborhood structure selection process and algorithm convergence speed effectively. The reverse learning neighborhood search strategy enhances the diversity of the solution space based on the reverse learning technology, which can improve the global search ability. Based on actual production data, experiments of various scales are designed to verify the effectiveness of the proposed algorithm.