外文翻译--多级下料问题的建模 中文版

多级下料问题的建模 摘要 在多级下料问题（ CSP）的切割过程是分布在几个连续的阶段。每 一个阶段除 了 最后一个生产中间产品 。中间产品清单可给予或任意。我们的目标是尽量减少材料总量减少了产成品库存足以满足采取客户的需求。如果中间的大小，给出了列生成技术可以应用到多级切割问题。如果中间的大小也得不到那么另一个方面是增加了问题的复杂性。我们建议对于这种情况，动态生成两行（中间大小）和列的特别程序模式）。我们把这种为行和列的生成方法。该方法使用一个辅助问题嵌入修订后的单纯形算法框架。这是一个非线性背包问题，可以有效解决 。与此相反对列代方法开发的技术不能保证最优解。然而，结果计算实验是非常有前途，并证明该方法是一种宝贵的工具除了为多级 CSP 的建模和求解。 2002年 Elsevier 科学 B.诉保留所有权利。 关键词： 线性规划 ；多级料问题 ；大规模优化，行和列 代 1 简介 一维下料问题（ CSP）的推广具有重要的现实时，切削过程是分布在几个连续的阶段。这不仅包括多级 CSP 的切割模式和他们的活动，而且中间产品和生产它们的数量每一个阶段 除了最后的切割工艺之一，并在每一个阶段的切割过程消耗除第一一。这些中间产品削减生产规模较小的中间或成 品尺寸。中间产品产量和在切割过程的输入。这种问题发生在 几乎每一个行业，一个典型的 CSP 的发生：纸张，薄膜，皮革，钢铁等虽然本文的结果同样适用于任何行业，多级切割需要为宗旨的地方，学科领域说明，我们将使用的术语在造纸行业所接受。特别是，我们会将向作为其宽度几何定义的产品推出。轧辊直径，展开纸的总长度，纸卡尺不适合目前的调查有关。 图。 1 说明了 三个阶段的切削过程。在这个例子中三种类型的股票中一滚，S2 和 S3 是用于生产九成品卷（的 F1 - F9 键 ）类型。有趣的是，股票辊能提供任何阶段的进程。在这里，中 一去的第一阶段， S2 的进入到第二和 S3 去了三分之一。相反，成品辊可以生产在任何阶段。三种类型的中间辊为 I1， I2 和 I3被切断前两个阶段。显然，我们可能会看到股票种类，中间产品的扩散，即使削减实际问题阶段。 是一个重载多级字，特别是在运筹学和 CSP 领域。吉尔摩和戈莫里 7指的是二维 CSP 的切割沿第一条解决了，然后通过切割带自己的跨越，作为一个多阶段的问题。在我们的情况下，所有削减都是沿（纵向）和问题是一维的CSP。 Dyckhoff3提出的多级 为所谓 的 一切模型切割多级。一切模型是一个极端的例子不是一个常 见的，众所周知的情况下一阶段的问题，无限的削减。有趣的是注意到，这些一切和多切模式只是同一个问题的两个不同的配方，而在现实世界的情况下，一期 CSP 是往往是多级 CSP 的放宽。一阶段放宽提供了一个合理的下界原来的多级 CSP 的。 几位研究人员袭击了多级的 CSP。哈斯勒 9提出了一个以两阶段问题络筒机在第一阶段，在第二条生产复卷。他探索的方法与模式唱片代要么事先或在单纯使用迭代列生成技术。他代表在成品卷筒和检查方面络筒机模式模式是否可以被分解成一中间辊组合合法。如果这样的组合是允许的，该模式被接纳对问题的矩阵。虽 然这种方法是可行的，它有一些缺点。它潜在的，包括不同中间辊数量庞大，并确定是否可以分割的格局是一复杂的装箱问题。此外，这种方法并不容易切削加工规模更以上两个阶段。 费雷拉和其他 4也探讨两阶段的问题，他们称之为两阶段问题。笔者改编哈斯勒的顺序启发式程序 8，最初为一典型的开发总警司，在两个阶段的切削过程。在每一个连续的过程步骤，他们正试图寻找一套 好 中间辊保证了第一阶段和第二好的模式的良好格局。如果在第一阶段的模式被接受，在成品卷筒上残留的问题是更新，减少了下令由模式及其活动定义的金额数量。显然， 这类似于启发式为解决一两个阶段的 CSP 手工操作。与此启发式的主要困难是产生一组 良好的中间辊。 卡瓦略和罗德里格斯 1按照线性规划的方法。他们的问题，但是，是受一个技术限制 ， 完成了一个卷筒，宽度应包括每一个中间辊。的限制允许预定义一个可能的中间辊名单。笔者重新初始 LP 问题成唱片中提出的问题方面，成品辊中间辊的条款。阿列生成与常规的辅助问题背包技术被应用。 一个的中间辊智能一代的想法 10出现时，两个阶段的系统 -削薄和切割 -进行了研究。在本论文中，我们 的思想结晶，并提出一行和列求解多级一维的 CSP发电技术。该技术是一种列生成的精液技术的推广建议的 Gilmore 和戈莫里 5,6为一个典型的 CSP 解决，或在我们的符号，一个单级的 CSP。对于一个多级的问题，更复杂辅助问题可能会导致列进入基础上的候选人，连同组合行相应的新的中间辊。我们扩大在 LP矩阵行和列。一个有限单纯形算法的迭代次数，导致要么最优或接近最优的解决方案。 在接下来的章节中，我们将制订两个阶段的 CSP 两种基本模式，目前行 andcolumn 代方法，然后分析计算实验。结果有些从作者的论文借来的 12。 2 模型的中间辊定列表 有三种辊尺寸名单： 列出股票的大小。 列出的中间尺寸。 列出成品尺寸。 请看图。 2（ 一），这表明辊之间的关系，这三种类型。股票体积可用金额是众所周知的。股票的大小可能会被消耗在切削过程的每一个阶段，可切成中间或成品卷筒。中间辊的输入和输出。该中间辊技术的限制非常严格：每卷的大小所消耗的总人数不能超过生产量。理想情况下应该有一个总的平衡，否则，有些过度无人认领的 中间辊数量应该去库存在仓库里，如果有存储空间可用。但是，这是另一种材料的浪费之间的折衷与相关的成本和仓储问题成本，这超出了目前的调查范围。因此，我们认为 我们正在考虑开放与不等式约束的问题，我们认为浪费无人认领的中间辊。对于成品辊拥有一支管理有序的数量应得到满足。 在这里，我们考虑一项股票辊宽度为两阶段的 CSP 将在第一阶段切成几个（图 2（ b）中间辊。产成品辊在第二阶段削减中间卷。我们假设一个中间辊宽度出来的第一阶段，将第二个满足最低最高限制。每一个中间辊宽度也应包括一个最小边将在第二阶段修整。 让 W 和 Y是成品，中间辊宽度载体，分别为。的切削模式第一阶段和第二阶段为代表的 A11 和 A22 号矩阵分别。为了弥补一个完整的唱片我们定义另一个矩阵矩阵 A12 往，显示两 者之间的关系。每一列连接的 J矩阵的 A12 矢量，其中只有一个非零元素鈥樷 1 鈥欌 出现在 我的位置相对应的中间辊我认为应削减根据裁剪定义列矩阵 A22 座因子。 我们可以制订一个多级 CSP 的线性规划模型： 在这里，向量 x1 和 x2是图案活动的第一和第二个阶段，分别为 B 是向量 要求对成品辊目标函数（ 1）尽量减少所用的股票，是由长期 1Tx1 定义成双数。约束（ 2）保证 中间辊在第二阶段 A12x2 消费应不超过其在生产 A11x1 第一阶段，的 B 卷客户需求应该得到满足。 请注意，整体矩阵具有特殊的结构。有两个对角块 A11 和 A22 号代表两个阶段切割图案，连接 A12 座，以及 0 块在左下方角落。右手边是由由 0 上的中间辊和载体的需求湾模型（ 1） - （ 3）一个两阶段的 CSP 唱片介绍，明确涉及中间辊。该矩阵可能已满如果问题比较小。在这种情况下，对各个阶段的所有模式可呈现在矩阵。否则，是一个列选择适当的技术在网上列生成。但在两种情况下，我们是否提前产生的所有列，或使用列生成，在矩阵的行数保持不变，因为可能的中间大小的列表给出。 2.1 双重问题 在这里，向量 U1 和 U2是双变量向量对应的中间辊和成品辊，分别。对偶问题（ 4） - （ 6） 辅助导致两个问题，应该在解决类型的列选择步骤，修订后的单纯形算法 。 2.2。列生成 在第一类的辅助问题，是关系到第一阶段削减模式生成切削过程。中间辊列表保持不变。显然，这种类型是与第一组问题的双重约束（ 5），辅助问题在本质上是相同的背包问题，因为我们在一个典型或一个阶段的 CSP。辅助问题可以表示为背包以下问题： 在这里， U1 是一个目标函数的系数是主问题的双变量的值向量 ；Y是中间辊宽度载体 ； W0 的是股票辊宽度和向量 a是一个变量的向量。如果目标函数值超过 1.0，一个新列第一阶段产生。这种情况紧跟从第一组的限制（ 5）可作为 UT 斯达康提交一答 1161T。该为解向量进入到矩阵答 11 列对第二类是辅助问题与成品辊切割产生的模式利用现有的中间辊。这种类型是与约束（ 5）第二组。对于每个中间辊系列 YJ 我们应该解决以下背包问题：在这里， U2是目标函数的系数是主对偶变量值的向量问题 ； w 是一个 成品尺寸的载体 ；额敏是一项强制性的最低边缘， eminP0；鹰击是中间宽辊 J和向量 a是一个变量的向量。让 u1j 是一个双变量的值对应于 j的中间尺寸如果目标函数价值超过 u1j，一个新列第二阶段产生。这种状况紧跟从约束第二组（ 5）可作为 UT 斯达康提交2 A22 号 6 UT 斯达康 一答 12。由于矩阵答 12 结构，右边归结为对偶变量对应的中间载体卷。 该解决方案作为载体进入 A22 号为矩阵列。如果我们没有中间辊中的不确定性，上述两种类型的背包 -背包 i和背包第二至足以解决问题最佳状态。 3。模型未知的中间辊 如果中间辊是未知的，我们面临更加复杂的局面。我们可以自由地选择任何合适的从一个给定范围内的中间大小 Ymin 成员 ； yMax 的 。由于每个中间辊和轧辊成品关联用矩阵的唱片，在唱片的不确定性矩阵在两个方向延伸行：列和行。出于这个原因，一列生成技术不能单独解决这个问 题。另一方面，中间辊潜在的巨大数目可能产生的一切可能性预先排除。我们可以估计在现实生活中不同的中间辊潜力。让颐，范围为中间辊宽度。参数镝是依赖于机器的，但通常颐 800毫米。设 d 是至少幅宽的精度。通常情况下 为 0.5毫米。因此，不同 N =4辊这个公式给我们一个估计 1600。当然，对于特殊情况的多级 CSP 的估计可能是少得多。虽然如此，全尺寸的 LP 矩阵往往是非常大的 。 另一种说法，对先进的中间辊代的是一个业务问题。该在一次中间辊的多样性减缓物质流，复杂滚跟踪任务，并提供切割作业少的灵活性。一家造纸厂总是倾向于用 最少的操作一些不同中间辊尺寸。不用说，这将是非常可取的有一个聪明的办法产生中间辊这可以做切割模式 -只在需要时。下一步，我们将目前的行和列的一代技术的两个阶段的问题（ 1） - （ 3） 。 3.1。行与列代 随着背包一，二和背包，我们可能面临的问题与第三类辅助同时产生新的中间辊和切割模式。在这里，我们应该记住矩阵的唱片行目前的中间和成品卷。 （如果我们 对股票的限制，我们辊将包括额外的行卷，以及股票。）的 LP模式矩阵的列切进入中间辊和中间辊到成品的股票名单。 在这里，我们正在努力适应修正单纯到一个任务，是不是它的 典型。据了解，上每一步的修正单纯一列正进入更换的基础和另一列是离开的基础。如果列在事先不知道，我们使用一列生成技术，扩大了 LP矩阵列方向。修订后的单纯没有使我们有能力产生未知行。现在的问题是如何能产生未知的中间辊使用修订后的单纯的步骤？ 让我们限制搜索生成中间辊不超过上一个新的中间辊修订后的每一个单纯的一步。因此，我们应该生成矩阵的新的唱片行，并在非退化的情况下，矩阵的秩的唱片将有效地增加 1。矩阵的基础上，应还可以扩大一行和一列，因为只有一列叶片旋转过程中的基础第一步，我们得出结论，两列实际上应该是在一个单一步骤生成。其中一应添加到矩阵基础上无条件地与其他人都不应取代现有的一个旋转的一步。 让向量 y 为中间辊尺寸已经在模型到目前为止，变量 z是一个新的中间轧辊尺寸和 V是一个相应的对偶变量。我们面临如下非线性整数规划问题： 这里有两个变量新列：列在第一阶段和第二阶段柱 A22 号答 11，中间辊宽度 z 时，为新行 V双变量，而轧辊一个新的中间数宽度在第一阶段削减模式。请注意，约束（ 10）有一个平等的形式。作为解决背包三的结果，我们会找到一个新的中间辊尺寸，及两所切割方式第一和第二阶段，分别为。 从理论上说，上述规定的限制限制了我们的选择产生中间辊。事实上，时可能出现的情况没有新的存在只是一个涉及切割方式新的中间滚。至少有两个新的中间辊应列入一份关于第一阶段削减模式。我们可以可以想象，这种情况更可能是在修正单纯的开始，当初始设置中间辊是稀少。只要程序产生更多的中间辊，这种情况变得不太可能的。正如我们展示后，一次一个 中间辊的限制是正当的广泛的现实世界中的 CSP。 3.2。在经修订单纯形算法的修改后的列选择 让我们证明了以下命题一。 命题 1。设 B是一个 mm，非奇异矩阵，巴将其扩展加入一行，并形成 一列如下所示： 其中 A是一个向量维数 m， 0是一个零鈥檚维向量米然后，逆矩阵 B1一存在，并且被定义为 证明。这是不难验证巴布 1一录 I，其中 I 是单位矩阵。 修改后的列的修正单纯形算法的选择步骤如下： 第 1 步。 i.如果解决背包的功能最优值超过 1.0，解答 11 是一列进入修订后的单纯形算法的基础旋转步。否则，进入下一步骤。 第 2 步。二，解决背包为每个现有的中间辊系列 YJ，强 1。 。 。的 K.如果最优值问题 超过 u1j然后解决 A22号是一列进入修订后的旋转步的基础单纯形算法。否则，进入下一步骤。 第 3 步。解决背包三。如果 功能最优值超过 1.0，我们应 扩大一行和一列的基础矩阵， 选择一列作为进入修订后的单纯形算法的基础上旋转步其他列 第二阶段削减模式。 矩阵的基础上扩大根据（ 14），其中 B 是迄今为止发现的基础矩阵， A是一个新的添加的列。扩大的逆矩阵保留当前的逆矩阵的子矩阵 B 1 和它是 适当微升零点在该行第 1A 和 B 列中所示（ 15）元素。 如果背包第三最优解不超过 1.0，和松弛变量的减少成本非负数，那么当前的解决方案是最佳的。 列选择看起来更比一代的经典案列复杂。其实二 2和 3 个额外的步骤是参与。现在，我们调查的辅助问题本身。 3.3。背包问题的非线性 虽然前两个辅助问题类型 - 背负土地出人附着物背包 II类是传统的和同时涵盖了文学（见 11，或 2），第三类背包第三需要专项调查。 背包 III 是一个有许多额外的限制（ 7）非线性背包 - （ 13）。非线性度是由两个条款规定：在目标函数中弗吉尼亚州（ 7）和约束（ 8）杂。 3.4。字典算法在背包问题 所有问题的参数功能界别 ；一，保函，目标函数系数和单约束参数，假设是积极的。该字典算法中提出了 Chvatal 由 Gilmore 和戈莫里 6 2符号如下： 第 1 步。安排的项目比率依序 为：录一其中 m 为载体维度。不失一般性，我们可以假设为 C1 = a1Pc2= a2P 中成药 =我。初始化索引变量的分支，钾录 0，函数 f的客观录零纪录的价值，以及工作参数该算法的一个背包鈥布列斯特录其余（空缺） B部分（您不能跟踪这方面的工作在原来的文件参数，但它不可避免地出现，一旦你开始编码的算法。） 第 2 步。查找当前分支的最有前途的延伸。 第 3步。是一个改进方案获得？计算出的价值目标函数 fCTX 和 比较的交易记录。 第 4步。回溯到下一个分支。 第 5步。是值得探讨的分支？该分行潜力估计由一个上限背包尾巴的 功能。 这是一个基本的字典算法。对于背包 III0，第 2 步是通过检查补充在双面约束的有效性（ 19）。如果检查失败转到步骤 4。 3.5。找到一个好的初始解 这是可取的开始，一个可行的方案接近最优。回首命题 2 段， 我们的结论是中间辊的初步名单应至少包括 Ymin 成员，因为它可能无法提交 由成品辊宽度的线性组合。此外，为了提供一个温暖的开始 我们产生一 初步清单使用以下过程中间辊。 4。一个样本问题 假设有四个要削减成品卷。两台机器进行两个阶段的连续切割：第一台机器切成中间辊辊股票，而第二个削减到了中间辊成品卷 。输入数据见表 1和 2。 首先，我们将产生一个初步的解决方案。让我们限制了中间辊的初步清单一个强制性辊： Ymin 成员 日圆 1200 毫米。因此，我们有一个在第一阶段生产 1200毫米模式 四辊和第二阶段的模式，每完成滚动。 初始矩阵基础上突出显示于表 3。目标函数值是 60.777。 表 4 显示了解决问题的动力。有趣的是，如何跟踪算法生成新列（模式）和（中间大小）新行。问题是开始出现在初始矩阵大胆的框架。然后图案 9 和第 10 列生成过程中产生的步骤。下一步中间 1900 毫米大小的生成以及两个新模式：模式 11 和模式 12。然后 ，算法利用新的规模优势，并产生 13-16 新列。然后，一个新的中间尺寸 1690 mm 的 生成以及两个新模式， 17 和 18，等等。 该算法发现换句话说与 36 套最佳解决方案的第一阶段， 36 个股票辊有序需要削减量。我们怎样才能证明最优？我们可以通过计算一个下界允许所有成品辊要削减在第一阶段直接。轻松的问题的最佳解决方案，这是一个单级 CSP 的，也是36套。 这是值得注意的解决方案是一种退化，因为只有六非零解的基本变量在 9 个元素的基础。其基本模式是突出于表 4。中间有四个 1200， 1390， 1710 和 1900 毫米轧辊的最佳解 决方案。 下一步，我们将展示如何提高业务质量的解决方案。 5。减少中间辊 照此计算，一个中等大小的不同数量最少的时间表是最可取的。该情况类似的模式在单阶段问题减少。为解决这种情况的精确算法问题仍在等待来自运筹社会的关注。现在是什么我们拥有一，该行为后试图反复优化分析，以取代一中间辊很少启发式另外一个是已经在溶液中，或以取代现有的两个新的中间辊，或三个现有的两个新的等中间辊 在这里，我们演示了如何 二对一的 改建工程。让我们看看我们刚才调查的样本。在该解决方案有四个中间辊： 1200， 1390， 1710 和 1900 毫米。在图谱第一阶段，我们可以看到，对 1390 卷和 1710 毫米 22 只外观模式，都有因子 1卷。让我们尝试下列替代： 根据（ 23），我们将定义一个新的中间辊尺寸一五五毫米 1710 mm1390 毫米 = 2。因此， 22模式将有一个例外，几乎完整的：不是一 139017 时 10 毫米的外观我们会得到两个一五五零毫米亮相。现在，我们也应该转向第二阶段的模式与 1390 毫米和 1710 毫米卷。这些模式是 23和 25。请注意，这两个有一集的模式相同数目 - 22。现在我们可以用一种模式取代这两种模式一五五零毫米 50 毫米 320 毫米 2 500 毫米 340 毫米 44 套。 所以我们没有退化的解决方案的效率，但我们已经降低了中间总数卷筒： 不是四个不同尺寸，我们有三个不同的大小。这是一个很大的进步，从 个业务观点。 中间辊减少技术如上所述证明是简单而有效的工具 提高解的品质。 6。实验 在实验期间，我们追求的主要目标是： 确定是否每次一个规则中间辊提供了一个体面的解决方案的质量， 估计有多少中间尺寸的解决方案，并 估计的热情开始生效。 我们实现了两个扩展与修改单纯形算法：列生成方法，行和列的生成方法使用Microsoft Visual C+。我们已经制定了发生器随机两阶段的问题。此外，我们跑了每个修剪消除了第二个问题松弛通过允许所有成品切割辊要削减在第一阶段直接的阶段。松弛的问题解决了常规列生成技术。 1 找到的解决办法按行和列代几乎完全符合其定义的下限和 50 的订单。随机生成的具体参数列于表 6。我们计算了的差距，其中 f是功能价值，而F 是美国东部时间的估计问题的最优值的功能。在一个随机生成的问题，1000 样品的最大差距为 11.1。它已经达成只有两个实例，并与三个订单都是小问题。只有八个实例有超过 0.5的差距。因此，只有在少数情况下是 最优的解决方案问题 2 在解决中间辊数量不是单调函数的 orders.When 数订单的数量少它增加一些微薄的价值和深远的某一点后启动下降。对于大规模问题的解决方案的不同，大小数都趋于中间是一个非常小。这种现象的最好解释如下：随着订单数量的增长，第二阶段的模式就变得如此多样，只有少数中级尺寸必须提供高效率的第二阶段削减。第一阶段是保证切割效率高选择中间有良好的尺寸合适的股票大小。例如，在许多情况下，只有两个中间为五千毫米股票已经生成尺寸大小： 1585和一八三零毫米提供一个完美的第一阶段格局： 2 一五八五毫米 一八三零毫米。当然，问题可能有一个大数目的中间解决方案卷筒但发展的方法的优点是它可以产生一些解决方案 。 3。 表现也证明是可扩展性。当问题规模相对较小它具有显着增长。迭代的次数的增多，如 Om2，其中 m 是成品尺寸数量。但经过某一点，正如我们以上，生长稳定。 4。 不料，热启动表现不佳。此外，虽然是一个有价值的热启动相对较小的问题，此外，它推动下表现为，凡在大的问题，最后只一些中间辊的使用。正如我们所料，数据粒度或数据的准确性影响的表现。允许所有宽度，四舍五入至整数，而不是维持毫米小到半毫米的精度，提高性能相当 。 7 结论 切割过