There is a special type of machine sequence-dependent setup times existed in hot-rolled seamless steel tube production, which depends on the difference in specifications between adjacent batches, and has a linear function relationship with batch specification. For this kind of hot-rolled batch scheduling problems with sequence-dependent setup times, the constraint of order delivery requirements is further considered, and the property between adjustment time and delivery time is explored. Aiming at minimizing the total adjustment time and tardiness, a fast reordering neighborhood search multi-objective algorithm (FRNSM) is designed based on evolutionary algorithms. At initial stage of the algorithm, based on the characteristic of sequence-dependent setup times, the specification optimization rule and delivery time optimization rule are proposed to locally optimize the initial solution. At the neighborhood search stage, the fast reordering neighborhood search strategy is designed based on the specification optimization between the same delivery time to optimize the setup times and tardiness; for the problem with multiple objectives, the acceptance criteria of solution is designed based on the Pareto improvement strategy. The experimental results based on actual production data show that the FRNSM has obvious effect on solving this kind of problems.