A hybrid MILP/CP decomposition approach for the continuous time scheduling of multipurpose batch plants

A hybrid Mixed-Integer Linear Programming (MILP)/Constraint Programming (CP) decomposition algorithm is proposed for the short-term scheduling of batch plants that rely on the State Task Network (STN) representation. The decisions about the type and number of tasks performed, as well as the assignment of units to tasks are made by the MILP master problem (MP). The CP subproblem checks the feasibility of a specific assignment and generates integer cuts for the master problem. A graph-theoretic preprocessing that determines time windows for the tasks and equipment units is also performed to enhance the performance of the algorithm. To exclude as many infeasible configurations as possible, three classes of integer cuts are generated. Various objective functions such as the minimization of assignment cost, the minimization of makespan for fixed demand and the maximization of profit for a fixed time horizon can be accommodated. Variable batch-sizes and durations, different storage policies, and resource constraints are taken into account. The proposed framework is very general and can be used for the solution of almost all batch scheduling problems. Numerical results show that for some classes of problems, the proposed algorithm can be two to three orders of magnitude faster than standalone MILP and CP models. (C) 2004 Elsevier Ltd. All rights reserved.