译文--离散优化方法及其在规划调度集成中的作用(编辑修改稿)

译文--离散优化方法及其在规划调度集成中的作用(编辑修改稿)内容摘要：

Marsten et al， 1990） 由于 他们 能 解决非常大的问题，日益受到注意。 混合整数线性规划方法主要 依赖基于分支定界方法 （ Nemhauser and Wolsey, 1988） ，这种方法包括 枚举树子在每个节点 得到线性规划的 解。 这些方法通过 割平面法 正在改进（ Balas et ， 1993），这种方法为得到最优解而产生下界。 线性规划 和混合整数线性规划被广泛使用 ， 最 出名的包括 ： CLEX（ ILOG， 2020）， OSL（ IBM， 1992）及 XPRESS（ Dash Associates，1999）， 他们解决问题的 功能 取得了令人瞩目 的成就。 值得注意的是，由于混合整数线性规划问题是 NP 问题 ，能够解决有大量 01 变量的问题。 非线性规划 非线性规划模型优于线性规划模型， 可以 清晰的描述非线性而且主要用于实时优化。 这些模型仅涉及连续变量 并且对于 规划和调度 是有限制的。 对应的 非线性规划 可以表达问题如下： Min Z = f (x) 条件 h (x) = 0 g (x) =0 x∈ X Karush Kuhn Tucker（ Minoux， 1983） 给出了非线性规划的条件，包括函数是连续的、可微的、确定的制约条件。 非线性规划问题的解决依耐与 连续二次规划算法 （ SQP）（ Han， 1976。 Powell， 1978。 Schittkowski， 1981），或减少梯度法（ Murtagh 和 Saunders，1978， 1982）。 混合整数非线性规划 混合整数非线性规划模型一般发生 这样的 规划和调度 ，其 使用连续时间， 尤其 是循环 策略 和非线性性能模型。 混合整数非线性规划问题 通常是混合整数规划的一 特例 ，其中 01 变量 是 线性而连续变量 是 非线性： Min Z = cTy + f(x) (MINLP) 条件 By+ g(x)=0 x∈ X,y∈ {0,1}m 对混合整数非线性规划问题的主要方法包括 分支定界法（ BB）（ Gupta 和 Ravindran， 9 1985。 Borchers 和 Mitchell， 1994。 Stubbs 和 Mehrotra， 1996）， 其为线性规划例子的扩展。 3 基于逻 辑的优化 近年来，一个新的趋 势已经出现 ，就 是 探索 解决离散 /连续优化问题 的方法。 这些方法，有利于问题的表述而且往往降低组合搜索， 正在对规划与调度问题研究产生重大影响。 两个主要方法是广义析编程总值（ GD）（拉曼和格罗斯曼， 1994 年）和约束规划（范Hentenryck， 1989）。 广义析取规划 广义析取规划的基本思路是用 持续变量 来形成一个目标函数 ，但三个类型的约束：（一） 离散决策是非独立的。 （二） 包括运筹学运算的析取命题。 （三 ） 只有布尔变量的纯逻辑约束。 更具体地说，问题如下： Min Z = ∑ ck + f (x) (GDP) 条件 其中 x 是连续变量和 y 是布尔变量。 目标函数涉及项 f（ x）的为连续变量（如营运成本）， ck 值 依赖于离散选择。 对于非线性问题的情况（ GDP），李和格罗斯曼（ 1999）重新拟订 开发 和算法 ，其依赖于代数描述。 重新拟订导致 紧的 混合整数非线性规划问题，同时 10 图 4：边寻找车间作业调度技术 该算法一般涉及分支定界方法 ，该方法由析取方法执行。 对于流程网络问题 ， Turkay和 Grossmann（ 1996）提出了一个 以 逻辑为基础的外逼近算法。 该算法包括 解决 减少空间的非线性规划。 约束规划 作为新近出现的基于逻辑优化的领域，对于调度问题的确定类型被证明是成功的。 规划的基本理念（ Van Hentenryck， 1989。 Puget， 1994）是使用 严密的 语言表达优化问题 ，其 变量是连续的整数，而且可以表示约束代数形式（如 H（工） = 0），（例如， [A1x《 =b1] _ [A2x《 =b2]），或作为条件逻辑（例如如果 g（ x） 《 =0 则 r（ x） = 0）。 此外 该语言能支持特殊的明确的函数，例如所有的不同的约束。 该语言包括 C + +的程序，虽然最近的趋势 ， 为社会提供更高水平的语言如 OPL。 其他商业 C 软件套件包括 ILOG的求解。 而不是依靠传统的数学规划方法， CP 依赖于使用 隐枚举 搜索树。 这种树通常是列举部分解决方案。 在树中的每个节点搜索，约束传播是通过域名进行减少的变量。 这包括例如在 问题 范围不断减少变量和 /或网域的情况下离散变量 ， 前者使用更严格的程序单调的线性和职能范围，而后者则要么是进行推理技术 或者是 专门程序。 一个很好的例子是 “边调查 ”车间作业调度方法。 图 4 给出一个简单的这种方法的例子，以解决析对工作相对加工 i 和 j。 一种通用析取模型的集成规划和调度 在过去，规划和调度模式已在很大程度上分别得到了解决。 最近 才出现 同时规划和 11 调度模型（如 Papageorgiou 和 Pantelides， Birewar 和 Grossmann， 1990）。 但是 进展表明 同时规划与调度模型 问题 是棘手的。 这是由于由此产生 的规模与 规划和调度 的时间不匹配。 这表明，有必要获取有效的综合规划和调度模型和算法。 在这一节我们提出了一个模型，反映了决策层次可利用的潜在有效解决方案。 上一节的 论述 ， 可以得出 结论， 广泛应用于规划与调度的线性规划和 混合整数线性规划 方法 ，已成为相当强大。 此外，自然语言处理 方法，能够面对越来越大的问题，正在通过严格的全局优化算法。 总之， 这些发展有助于更快速的解决 混合整数线性规划问题。 一个新的激动人心的新方向，是逻辑的优化 ， 如广义析 取 编程方法和约束规划，这将会保证制定以促进问题的解决和改善效率和稳健性。 为了说明使用基于逻辑的方法，我们目前在本节一 展示了 一般的 混合整数线性规划 模型。 正如我们所看到的模型 ，给出引起了普遍的析取程序，包括嵌入式，反映的等级性质在整合的问题作出决定。 我们使用的规划离散时间 ， 表示安排时间域。 此外，我们假设该调度模型对应于国家的任务网络（ STN）（ Kondili， 1993）。 建立规划和优化调度模型， H 是分为若干规划期间，吨 = 1 .. T 和一个调度周期数，一个规划期的长短，通常是在在几个星期或几个月秩序。 我们定义集合（吨）来表示它的调度期间，属于规划期内吨完整设置参数和变量的定义如下： 集： 指数： 参数： 12 基于以上的定义，非线性问题模型如图所示： 我们的目标（ 1） 是 尽量减少整个 周期的 成本，包括经营成本，扩大成本 ,以及资源成本。 销售额包括由负值分配到相应的成本系数。 特定的规划期的全局约束 ，如超过混合器的大量平衡， 如库存的限制 ,为代表（ 3）。 注意，这两个（ 2）及（ 3）可 一般涉及，196。 244。 ass 上，从以前的专卖变量期间，引起连接限制。 此外，全局调度的限制（ 3），一般也涉及的调度时间延迟，运输署，由于加工次，清理倍，转换时间。 约束（ 5） （ 16）被分为一组嵌套每个单元析限制 J 室设计或不，这是一个战略规划的决定。 如果单位 j 是包含在设计，（系列 YJ = True），则在限制设置的析取左侧应用，否则（系列 YJ =假），状态变量子集 J 室与相关设置为零的各个时期通过在（ 4）矩阵DJT 的。 中间析代表的决定，在规划期内的经营 J 室 t 或不 要，只适用于如果系列 YJ =真。 如果 单位 j 管理，在时期吨（ wjt =真），它可以 被解释为任何行动或战术计划离。