SBIR PHASE I: MultiFACET - An Approach for Solving Large Scale Planning and Scheduling Problems

DMI-9561853米勒这个小型企业创新研究的第一阶段开发了新的软件，用于解决灵活制造设施中的计划和调度问题。该软件设计针对大规模工业计划和调度的解决方案。@enefits预计将在增加产能、减少浪费、降低运营成本、减少库存和缩短对客户订单的响应时间方面发挥作用。该方法是对计划和调度问题的严格数学表述，并依赖于一种新的问题分解方法。分解方案使用包含详细模型的滑动时间窗口，与用于剩余时间范围的粗粒度计划模型相耦合。该方法的核心是一种自动机制，用于以迭代的方式沿时间轴传播详细窗口，很像数值积分。时间轴被分解成细粒和粗粒两部分。在细粒度部分，将调度问题建模为混合整数线性规划进行求解。选择细粒度时间窗口的长度，以便可以使用定制的算法来解决调度子问题。时间范围的其余部分(在细粒度窗口之外)将使用聚合约束来建模，并通过放松完整性条件来求解。这使得工厂产能和预期产品需求等宏观特征可以传播到每个详细的调度子问题中。如果研究成功，将为流程工业中的调度工具提供一个新的引擎。现有的软件安装和维护起来既困难又昂贵，而且不能提供高质量的解决方案。新软件预计将减少定制和安装时间，但仍能提供高质量的结果。

DMI-9561853 Miller This Small Business Innovation Research (SBIR) Phase I develops new software for solving planning, and scheduling problems in flexible manufacturing facilities. The software design is directed to solutions for large-scale industrial planning and scheduling. @enefits are expected in increased production capacity, reduced waste, lower operating costs, reduced inventories, and shorter response time to customer orders. The approach is a rigorous mathematical formulation of planning and scheduling problems and relies on a novel problem decomposition methodology. The decomposition scheme uses a sliding time window containing a detailed model, coupled to a coarse-grained planning model for the remainder of the time horizon. The heart of the method is an automated mechanism for propagating a detailed window along the time axis in an iterative fashion, much like numerical integration. The time axis is decomposed into fine and coarse grained sections. In the fine grained section, the scheduling problem will be modeled and solved as a mixed-integer linear program. The length of the fine-grained time window is chosen so that the scheduling subproblem may be solved using a customized algorythm. The remainder of the time horizon (outside the fine grained window) will be modeled using aggregate constraints and solved by relaxing integrality conditions. This allows such macroscopic features as plant capacity and anticipated product demand to be propagated into each detailed scheduling subproblem. If successful, this research will provide a new engine for scheduling tools useful in process industries. Available software is difficult and expensive to install and maintain and does not provide high quality solutions. The new software is expected to reduce customization and installation time and yet provide high quality results.