To remain competitive in todays global environment, US chemical companies have moved towards product customization and diversification, which in turn have resulted in a large number of low-volume, high-value products. Furthermore, in an effort to achieve higher utilization of resources, chemical manufacturers have started to employ multiproduct/multipurpose facilities. In addition to higher resource utilization, the flexibility of these facilities allows for lower inventory costs and better responsiveness to demand fluctuations. However, these advantages can be achieved only if effective optimization-based production scheduling methodologies, which could uncork the hidden potential of multiproduct manufacturing, are developed. The two major bottlenecks in the development and adoption of such methods appear to be: a) the lack of an unambiguous problem statement, which prohibits the development of a unified information technology framework; and b) the computational performance of existing optimization-based methods. The goal of this research is the development of new theory and solution methods that will address the second challenge.
Intellectual Merit
The intellectual merit is in the analysis of existing frameworks, the development of the underlying optimization theory, and the formulation of advanced solution strategies for chemical production scheduling. This project will focus on the following five areas: a) Method classification formulate a systematic classification of general scheduling approaches and modeling techniques. b) Computational study perform an extensive computational study of various approaches using more than 5,000 problem instances. c) Theory development develop mathematical properties regarding the tightness of scheduling mixed-integer programming formulations. d) Novel Modeling Methods use the inherent structure of scheduling models and our theoretical results to explore ways of strengthening these formulations. e) Solution algorithms based on the computational and theoretical results, study new decomposition schemes and explore new search methods and design algorithms that harness the new capabilities offered by parallel computing and cyberinfrastructure.
Broader Impact
This research will advance the state of the art in the use of optimization methodologies in process operations, thereby opening new avenues of research in process systems engineering (PSE). Through the involvement of the graduate student working on this project, the results of will be used to develop educational material for a graduate level course the PI teaches. Furthermore, this material will be evaluated for effectiveness and disseminated through the Engineering Pathway and the National Science Digital Library. Both the codes and the library of problems developed during this project will be made publicly available so that others in the field can replicate (or improve upon) the results. This project will also offer the PI an opportunity to further develop his undergraduate research program. Specifically, undergraduate students will use some of the cyber-infrastructure tools developed in this effort to carry out computational studies.
Potentially Transformative Research
This research is a major departure from previous work in this area in that it will be based upon a theoretical study of the structure of mixed-integer programming formulations and the derivation of mathematical properties on their polyhedral properties. This is a subject that has received practically no attention to this point in the PSE literature. Therefore, if successful, the research will lay the foundations of a new, theoretically rigorous approach to production scheduling, which could lead to significant advances in solving broad families of operational problems.
While it remains one of the largest manufacturing sectors of the US economy, the chemical industry faces a number of major challenges such as migration of customer industries, saturation of US markets, and increased global competition. To remain competitive in this environment, chemical companies have moved towards product customization and diversification, which have consequently resulted in a large number of low-volume, high-value final products. To achieve higher utilization of resources, in this capital intensive industrial sector, chemical companies have started to employ facilities where multiple products compete for limited resources (equipment units and utilities) and which can be operated in multiple modes. The flexibility of these so called multiproduct facilities allows for higher resource utilization, lower inventory costs, and better responsiveness to demand fluctuations. Nevertheless, these advantages can materialize only if the production is planned well, a task which is challenging due to the multiplicity of production modes. To address this challenge, researchers in the area of process systems engineering (PSE) have developed a number of scheduling methods, typically mixed-integer programming (MIP) models. However, despite all the effort that has gone into developing new MIP models, the scheduling of real-world chemical processes remains an open challenge. Accordingly, the goal of this research was the development of new theory and solution methods that will advance our ability to solve production planning and scheduling problems of practical interest. The proposed research was a major departure from previous work in this area in that it was based on a theoretical study of the MIP scheduling models and the subsequent formulation of new improved and more general models, as well as the development of advanced solution methods. The project started with a theoretical study of the structure of discrete-time MIP scheduling models followed by the development of a model that can be used to address problems in all types of production environments under a wide range of processing constraints. Next, we developed four solution methods: (1) a branch-and-bound (B&B) algorithm designed to harness parallel computational resources; (2) models that rely on multiple and nonuniform discrete time grids; (3) a constraint propagation algorithm for the generation of tightening constraints; and (4) reformulation and branching methods. The methods we developed in this project led to dramatic improvements in our ability to solve MIP chemical production scheduling problems, arguably changing the landscape in the area. They resulted in speedups of two to four orders of magnitude, allowing us to solve to optimality large-scale instances that were intractable previously. Importantly, all proposed methods are applicable to a wide range of MIP models because they rely on binary variables which are employed in all time-indexed models. Furthermore, because the models we developed account for various processing characteristics and constraints and can be used to address problems in all production environments, our methods are applicable to a wide range of problems. To give an example, the tightening methods are most effective for cost minimization problems, where they reduce the solution time by about two orders of magnitude. For makespan minimization, the tightening methods improve the solution time by about a factor of three. The reformulation is effective for cost minimization, profit maximization, and makespan minimization, reducing the solution time by an average of three, two, and one orders of magnitude respectively. Several large problems that could not be solved to optimality in a day can now be solved in within a few minutes using the reformulation. When used individually, the reformulation has a bigger impact on the solution time, but there is often some benefit to using both methods together. Finally, in terms of publications, the present grant was highly successful – it led to 13 journal publications and more than 20 conference presentations, and we expect to submit at least two more journal papers within the next six months. Also, the PI has been invited to give numerous keynote presentations on the research resulting from this grant (e.g., in the 15th International Conference on Process Systems Engineering). Finally, the present award led to an invited review paper in the prestigious Annual Review of Chemical and Biomolecular Engineering journal and allowed the PI to co-author an extensive review on industrial applications of scheduling methods.
