This article presents a new algorithm for scheduling multistage batch plants with a large number of orders and sequence-dependent changeovers. Such problems are either intractable when solved with full-space approaches or poor solutions result. We use decomposition on the entire set of orders and derive the complete schedule in several iterations, by inserting a couple of orders at a time. The key idea is to allow for partial rescheduling without altering the main decisions in terms of unit assignments and sequencing (linked to the binary variables) so that the combinatorial complexity is kept at a manageable level. The algorithm has been implemented for three alternative continuous-time mixed integer linear programing models and tested through the solution of 10 example problems for different decomposition settings. The results show that an industrial-size scheduling problem with 50 orders, 17 units distributed over six stages can effectively be solved in roughly 6 min of computational time. (C) 2010 American Institute of Chemical Engineers AIChE J, 57: 373-387, 2011