Effective decomposition algorithm for multistage batch plant scheduling

This paper presents a new algorithm for the scheduling of batch plants with a large number of orders and sequence-dependent changeovers. Such problems are either intractable or yield poor solutions with full-space approaches. We use decomposition on the entire set of orders and derive the complete schedule in several iterations. The key idea is to allow for partial rescheduling without altering the main decisions in terms of unit assignments and sequencing, so that the complexity is kept at a manageable level. It has been implemented with a unit-specific continuous-time model and tested for different decomposition settings. The results show that a real-life 50-order, 17-unit, 6-stage problem can effectively be solved in roughly 6 minutes of computational time.