(240c) Heuristic Decomposition Methods for Complex Sequential Industrial Scheduling Problems

An increasingly competitive environment and the widespread use of batch and semi-continuous processes have focused attention on the need of efficient scheduling models and tools as basic building blocks in the decision making process for planning and scheduling activities that are involved in enterprise-wide optimization. In the last 15 years several approaches have appeared in the literature that can efficiently solve small to medium size scheduling problems but become intractable for large problems. In addition, most of the times, they are tailored to specific types of problems and cannot handle all the features of an industrial plant.

State Task Network (Kondili et al., 1993, Comp. Chem. Eng., 211) or Resource Task Network (Pantelides, 1994, Proc. FOCAPO, 253) formulations are probably the most general for solving industrial problems. They can handle general multipurpose plants and features like shared resources and due dates rather easily. The use of a discrete-time grid means that a large number of time intervals may be required to represent the exact problem data. Most of the times, and to maintain problem tractability, we can only solve approximate versions of the problem that are usually enough for finding very good solutions. A major disadvantage of discrete-time formulations are their limitation in handling sequence dependent changeovers, which can only be performed through additional tasks that greatly increase the size and complexity of trhe model. Equivalent STN or RTN continuous-time formulations can handle exact data, variable duration tasks and some can effectively handle sequence-dependent changeovers. However, despite recent developments by several research groups (e.g. Castro et al., 2004, Ind. Eng. Chem. Res., 105; Maravelias & Grossmann, 2003, Ind. Eng. Chem. Res., 3056; Janak et al., 2004, Ind. Eng. Chem. Res., 2516), the resulting MILP models are very complex and only small problems can be solved to optimality.

The industrial problem considered in this paper, which is part of a pharmaceutical supply chain optimization problem, consists of a multistage multiproduct plant featuring 30 orders, 17 equipment units and 6 stages, with sequence dependent changeovers in some stages and with several complex operational constraints. The objective is to find a schedule that minimizes the makespan. Due to the large number of orders, the discrete-time formulation cannot handle sequence dependent changeovers and hence can only be used to predict an upper bound on the makespan by considering the worst case scenario in terms of changeovers. Unfortunately, this bound is very loose. Event-based continuous-time formulations or those using sequencing variables, either with global precedence (Harjunkoski & Grossmann 2002, Comp. Chem. Eng., 1533) or immediate precedence (Méndez et al. 2001, Comp. Chem. Eng., 701), can find reasonably good solutions to the problem but due to the very large integrality gap, optimality cannot be proved and hence it is very difficult to know how good these solutions are.

This paper describes several fast heuristic decomposition strategies that can be used to find good solutions in multistage problems. These include solving single stage problems sequentially, for all 30 orders, and solving sequentially a subset of orders at a time when considering the full 6-stage problem. The latter strategy was found to be particulary efficient since it was able to find good schedules in 2 minutes of computational time, while the former generated worse solutions but they featured very good assignments of orders to machines. When these were fixed in the continuous-time sequential models, this decreased significantly the complexity of the MILP and its integrality gap. As a result of this strategy, very good solutions were generated in one hour of computational time. We also present approximate methods for estimating good lower bounds for the makespan in order to assess solutions from the decomposition methods. Finally, we also present comparisons with several exact discrete and continuous time models, which require very large computational times. However, as will be shown these times can be reduced significantly by exploiting through simplifications and additional constraints, the multistage structure and the fact that the sizes of the batches are fixed.