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.