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.