This paper presents a new decomposition algorithm for the optimal scheduling of large-scale multiproduct plants containing a large number of orders. Rather than tackling highly complex, full-space problems that cannot be solved in reasonable time, the complete set of orders is scheduled sequentially by considering one, or a couple of them, at a time. As we proceed through the iterations, previously scheduled orders can be partly rescheduled to allow for some flexibility while keeping the combinatorial complexity at a manageable level. Once a complete schedule is obtained, the same concept is applied to improve the schedule locally. The user can choose to rely on either a unit-specific or a sequencing variable based continuous-time mixedinteger linear programming model. In addition, there are other parameters that affect how the decomposition is carried out, so the algorithm is highly versatile and adaptable to problems of varying sizes. The largest problem solved is a real-life, 50-order, 17-unit, 6-stage problem, for which a very good solution can be found in less than 1 min of computational time.