Abstract: A batch scheduling problem of hot-rolled bars was discussed according to the influences of process conditions and due date on the continuous production of rolling units. A mathematical model with three objectives to minimize the setup time, tardiness penalty and steel grade bounce penalty was constructed, and a method of the variable neighborhood search algorithm embedding the earliest due date first (EDD) rule was proposed to solve the model. In consideration of constraints in the model, an initial solution was generated by constraint satisfaction technology. Then, to meet the actual production needs, a variable neighborhood search method was designed to minimize the setup time, which is considered as a primary objective. In this algorithm, a hybrid operator is applied in sha-king and local search, and the idea of simulated annealing is introduced to take control of the acceptance of new solutions. Meanwhile, in order to minimize the tardiness penalty and the steel grade bounce penalty, the earliest due date first rule and the steel grade sorting rule are applied. Experiment results show that the model and the algorithm are feasible and effective.