44050-G9
A Network-Based Approach for the Optimization of Multipurpose Chemical Processes
One of the research directions of our lab is the development of new optimization methods for the production planning and scheduling of chemical processes. Production planning and scheduling applications appear both in continuous batch processing and have substantial economic impact. The goal of this ACS-PRF (Type G) grant is the development of novel mixed-integer programming (MIP) models and solution algorithms for the optimization of batch processing.
The funds provided by this grant during the period between October 2007 and September 2008 were used to partially cover expenses for one graduate student (Arul Sundaramoorthy) and to purchase computer hardware. Arul joined our lab in Jan 2006 and has been working on the development of models for the simultaneous batching and scheduling of multi-stage multi-product processes.
In multistage batch processes, batching and scheduling have long been viewed as two separate problems. The batching problem is first solved to find the number and sizes of batches for given customer orders, and the scheduling problem is solved next for fixed batching decisions. However, such two-step approach can often lead to suboptimal solutions since batching and scheduling decisions do interact with each other. Furthermore, in spite of their significance, storage and utility constraints have not received due consideration in the existing approaches.
First, Arul formulated a Mixed-integer Programming (MIP) formulation for the simultaneous batching and scheduling in multistage processes. The proposed sequence-based formulation addresses limitations of existing approaches where batching and scheduling decisions are carried out sequentially. To account for batching decisions, additional batch selection and batch size variables are used, leading to the introduction to of demand satisfaction and unit capacity constraints. Assignment constraints are active only for the subset of batches that are selected and sequencing is carried out between batches that are assigned on the same processing unit. To enhance the computational performance of the model, numerous methods that allow us to fix a subset of sequencing variables were developed.
Second, Arul developed a general classification of storage policies in multistage processes and proposed a MIP formulation for the simultaneous batching and scheduling of these processes with storage constraints. Storage vessels are modeled as additional processing units for which assignment and sequencing constraints are expressed. It was also shown that the proposed formulation can be readily modified to address different classes of problems. Further, the approach was extended to address problems with sequence-dependent changeover times and costs.
Third, Arul helped in the development of an algorithm to solve problem instances of industrial importance in reasonable time frames. The proposed algorithm first decomposes the original problem into 1st-level subproblems based on batching decisions. The subproblems that remain unsolved within a time limit are then decomposed into 2nd-level subproblems based on batch-unit assignment decisions in one stage. The process can be repeated by identifying subproblems that cannot be solved within a given time limit and decomposing them by batch-unit assignment, until all subproblems are solved. The proposed algorithm was implemented using Grid Computing in collaboration with Professor Ferris from the Computer Sciences Department of UW-Madison.
Finally, Arul formulated a novel MIP model for the scheduling of multi-stage processes under utility constraints, a class of problems that has not been addressed in the literature. Since different tasks often share the limited utilities at the same time, we use a common time-grid approach. Further, the proposed method handles the batching decisions (the number and sizes of batches) seamlessly without the usage of explicit batch-selection variables. To preserve the batch identity in storage vessels, we introduce a new class of inventory variables and constraints.
Our efforts in this area have led to two publications during the reported period and two submitted papers.
