Abstract: The complexity of production scheduling problem in cold rolling line is analyzed, which is formulated as two parts, namely, the coil-merging optimization and the rolling batch planning. The optimization of steel coil merging is constructed as a multiple container packing problem (MCPP) that is computed by a new proposed algorithm, discrete differential evolution (DDE), in this paper. A specific double traveling salesman problem (DTSP) is modeled for the rolling batch planning, and a hybrid heuristic method on the basis of evolutionary mechanism and local search is presented to solve this model. The experimental results with real production data from Shanghai Baosteel Co. Ltd. show that the production scheduling method suggested in this paper is effective.