Integer Programming Methods for Short Term Scheduling of Batch Operations in Process Industries

点击翻译按钮获取中文摘要

The goal of this project is to develop a robust methodological framework for solving some multistage batch production scheduling problems in process industries, particularly chemical industries. These are encountered when standardized products are produced in high volumes. A batch is the process of transforming some product or mix of products on a machine into a different product. In the flow of products one occasionally sees lines merging or dividing, as well as loops, as some products may have to be reprocessed. One may be able to temporarily store some products, and some machines may need to be cleaned according to predetermined schedules. The objective is either the minimization of the total time necessary to producecertain amounts of final products, or the corresponding costs, or the determination of appropriate inventory capacities and production rates. The research will concentrate on modeling and solving these problems as integer programming problems. Discrete time simulation can generate feasible schedules extremely rapidly. Lagrangean substitution, a flexible scheme that artificially induces a block-diagonal structure in the model, will be developed, as a means of obtaining strong bounds. Column generation will be considered as an alternative way of generating these bounds. The Lagrangean solutions will be used as starting points for Lagrangean heuristics. The last step will be a Lagrangean probing scheme for fixing variables based on strong bounds and good feasible solutions. If successful, this research will lead to improved optimization tools for chemical processes. More generally, this research will provide improved computational tools and methodologies for solving hard combinatorial problems. It will in particular lead to a more effective use of good feasible solutions within Lagrangean relaxation and branch-and-bound. New insight into the design of column generation schemes equivalent to complex Lagrangean substitutions will be gained, providing more options for thecomputation of strong bounds.