This study addresses the short-term scheduling problem for the batch annealing process in the heat treatment of steel coils. Scheduling in the batch annealing process has the following objective: determine the optimal movement plan for satisfying high utilization of shared equipment (a crane, furnaces, and coolers) among parallel bases. This process is a multipurpose batch plant which may contain re-entrant flows in the batch annealing cycles and units in parallel, including sequence-dependent setup time and transfer time. A novel mixed-integer linear programming (MILP) model for the scheduling of the batch annealing process is proposed. For large size problems of the batch annealing process, a scheduling solution can be obtained by using a novel algorithm. Although this procedure does not guarantee optimality of the solution, the computational efficiency was improved and feasible solutions for large problems can be obtained in a reasonable CPU time. Application of the proposed model and algorithm is illustrated with several example problems including a problem that consists of 29 pieces of equipment and up to 24 bases.