Advised by Ignacio E. Grossmann
The problem of optimal scheduling of batch plants is very common in chemical industry, and due to its generality many different approaches have been proposed in the literature. Discrete- ([1], [2]) and continuous-time ([3], [4], [5], [6]) State Task Network (STN) and Resource Task Network (RTN) formulations have been proposed for the short-term scheduling of multipurpose batch plants, and several models have also been proposed for the scheduling of multi- and single-stage batch plants. A major difficulty in the application of these optimization models has been that they can become intractable for typical large-scale industrial applications. Furthermore, the computational performance of these models becomes even worse when the more common objective of makespan minimization (i.e. minimization of completion time) is used as opposed to the objective of profit maximization.
In this paper we develop a hybrid MIP/CP model that can address the computational challenges cited above, and that can be readily used for the scheduling of several classes of batch plants. The main idea is to decompose a batch scheduling problem into two parts: a loosely constrained part (master problem) that is suitable for optimization and it is solved using Mixed-Integer Programming (MIP) techniques, and a highly constrained part (subproblem) that is solved using Constraint Programming (CP) techniques. Thus, we exploit the complementary strengths of the two solution paradigms: we use MIP to optimize and CP to check feasibility.
The framework proposed by Maravelias and Grossmann ([7]) is used as a basis: a relaxed MIP master problem is solved to provide a lower bound for the makespan and a set of tasks to be performed (type and number of batches); for a given set of tasks, a CP subproblem is solved to derive a feasible schedule and provide an upper bound (feasible solution); if an infeasibility is detected an integer cut is added to exclude this set of tasks; a graph-theoretic pre-processing is performed to reduce the number of potential assignments, and several classes of "strong" integer cuts are developed in order to reduce the number of iterations needed for convergence. Various objective functions, such as (a) minimization of makespan for fixed demand, (b) maximization of throughput over a fixed time horizon, and (c) minimization of processing cost for fixed demand with due dates, can be accommodated.
The generality of the proposed framework lies on the fact that the MIP
master problem and the CP subproblem can be modified to describe
practically all types of batch plants.
(a) For multistage or single stage plants where the number of batches
needed to satisfy a set of orders is fixed, the number of assignment binary
variables used in the master problem is reduced; we use single indexed
binaries instead of double indexed binaries.
(b) For multistage batch plants where the batch size of the tasks is fixed,
a number of constraints for the bounding of batch-sizes is dropped from
both the master and the subproblem.
(c) When unlimited intermediate storage is available between two stages of
a multistage plant, a number of constraints describing the storage of
intermediates is dropped from the CP subproblem.
(d) When shared storage tanks are available between two stages, a set of
storage activities is introduced in the CP subproblem and the storage tanks
are modeled as units.
(e) When release and due times must be taken into account, a set of
tightening constraints are added into the master problem to reduce the
number of different assignments that can potentially meet the given demand.
(f) Constraints that describe special features of a batch plant (zero-wait
or no intermediate storage policy, infeasible unit-task assignments etc.)
can be easily added in both the master MIP problem (if needed) and the CP
subproblem.
(g) When identical parallel machines are used in all stages of a multistage
batch plant, the problem reduces to a single, standalone CP problem.
Modifications in (a) -- (c) are straightforward simplifications of the MIP/CP hybrid approach of Maravelias and Grossmann. In (d), storage tasks are handled as processing tasks and storage tanks as processing equipment, and thus the structure of the CP subproblem remains the same. In (e) and (f), we add some new constraints that make the MIP master problem more difficult to solve but eliminate redundant or infeasible assignments and thus reduce the number of iterations needed for convergence. The addition of constraints in the CP subproblem makes the model more highly constrained and thus easier to solve. We should also note that previous MIP/CP hybrid approaches are special cases of the proposed framework.
The proposed approach was tested on several problems and the computational
results showed that for some classes of problems the proposed MILP/CP
hybrid algorithm was orders of magnitude faster than other STN or RTN MILP
models, enabling us to solve problems that are practically unsolvable with
existing tools. Specifically, the proposed method is significantly faster
than standalone MIP models for the minimization of makespan; it is better
than standalone MIP or CP models for the minimization of cost; and it is
better than CP models and comparable to MIP models for the maximization of
throughput over a fixed time horizon.
References
[1] Kondili, E.; Pantelides, C. C.; Sargent, R. A General Algorithm for
Short-Term Scheduling of Batch Operations -- I. MILP Formulation. Comput.
Chem. Eng. 1993, 17, 211-227.
[2] Pantelides, C. C. Unified Frameworks for the Optimal Process Planning
and Scheduling. In Proceedings on the Second Conference on Foundations of
Computer Aided Operations. 1994, 253-274.
[3] Schilling, G.; Pantelides, C. C. A Simple Continuous-Time Process
Scheduling Formulation and a Novel Solution Algorithm. Comput. Chem. Eng.,
1996, 20, S1221-1226.
[4] Zhang, X.; Sargent, R. W. H. The Optimal Operation of Mixed Production
Facilities -- General Formulation and Some Approaches for the Solution.
Comput. Chem. Eng., 1996, 20, 897-904.
[5] Ierapetritou, M. G.; Floudas, C. A. Effective Continuous-Time
Formulation for Short-Term Scheduling. 1. Multipurpose Batch Processes.
Ind. Eng. Chem. Res., 1998, 37, 4341-4359.
[6] Maravelias, C.T.; Grossmann, I.E. A New General Continuous-Time
State Task Network Formulation for the Short-Term Scheduling of
Multipurpose Batch Plants. Ind. Eng. Chem. Res., 2003, 42 (13),
3056-3074.
[7] Maravelias, C. T.; Grossmann, I. E. A Hybrid MILP/CP Decomposition
Approach for the Continuous Time Scheduling of Multipurpose Batch
Plants. Submitted for Publication