Capacity-oriented production scheduling can be described as the assignment of competing products to several single level, capacitated production lines over a given planning horizon. This study was initially motivated by the production planning of various types of tiles by a tile manufacturing company. We considered different integer programming formulations and found that a disaggregated model, while increasing the size of the model, lends itself best to Lagrangian techniques and produces the strongest bounds. Additionally, from every Lagrangian solution, we can generate a feasible production schedule by systematically reassigning lines from products whose production exceeded demand to products with unsatisfied demands. The technique is not specific to tile companies, but can be used by any firm where product setups on production lines can be scheduled between consecutive periods with changeover cost, but without production loss. Our computational experience with real data from the tile company and randomly generated problem instances gave excellent lower and upper bounds.