Efficient MILP-based solution strategies for large-scale industrial batch scheduling problems

This paper presents two alternative decomposition approaches for the efficient solution of multistage, multiproduct batch scheduling problems comprising hundreds of batch operations. Both approaches follow the principle of first obtaining a good schedule (constructive stage), by considering only a subset of the full set of orders at a time, and then improving it (improvement stage) by applying a rescheduling technique. The core of both approaches consists on the solution of mixed integer linear programming problems that, on each step, are variations of the scheduling model with global precedence sequencing variables of Harjunkoski & Grossmann (2002). The results for the solution of a 30-order problem show that the proposed decomposition methods are able to obtain solutions that are 35% better than those obtained by the solution of the full problem, on a fraction of the compulational time.