We consider the capacitated lot-sizing and scheduling problem for a paper remanufacturing system that produces several types of corrugated cardboards. The problem is to determine the lot sizes as well as the sequence of lots for the objective of minimizing the sum of setup and inventory holding costs while satisfying the demand and the machine capacity over a given planning horizon. In particular, the paper remanufacturing system has sequence-dependent setup costs that depend on the type of product just completed and on the product to be processed. Also, the setup state at one period can be carried over to the next period. An integer programming model is presented to describe the problem. Due to the complexity of the problem, we modify the existing two-stage heuristics in which an initial solution is obtained and then it is improved using a multi-pass interchange method. To show the performances of the heuristics, computational experiments were done using the real data, and a significant amount of improvement is reported.