英语原文共 21 页，剩余内容已隐藏，支付完成后下载完整资料

文献翻译：

两阶段二维剩余物料的板材下料问题

R. Andrade E. G. Birgin R. Morabito

July 11, 2013

摘要

在这篇文章里，我们着重研究的是非精确的两阶二维剩余物料的板材下料问题。在这种切割模式中的板材剩余物（废弃的材料或边角余料），如果足够大到能够满足未来项目（较小的有规则板材）的需要，就可以再利用。这种切割问题可以视为一种剩余装箱问题，是因为有把剩余物料重新储存的可能。每种切割或打包模式中的边角余料不一定都代表材料的浪费，这取决于它们的大小。有两个代表这种非精确两阶二维剩余装箱问题的二维数学规划模型已经被提出。这些模型基本上包括使用一套最低成本的板材来切割/包装有序物料项目，以及从所有可能的最低成本方案中，选择一种能够将生成的可用剩余物料的价值最大化的方案。由于这些二维模型的特殊性，它们可以重新构建为一级混合整数规划模型。一些实验数值的结果表明这些模型恰当地表现了问题，并且说明了它们的性能。

关键词：两阶二维切割，剩余装箱问题，剩余切割问题，二维编程，MIP模型，剩余物料。

1介绍

切割问题通常发生在不同的工业过程中。在这些过程中，纸和铝卷，玻璃和玻璃板，金属条和金属板，硬质板，皮革和布等被切割，以生产更小的具有规则尺寸和数量的材料。这些问题与包装问题密切相关，它们基本上决定了切割大型库存物品、以生产小型物品的“最佳”方式，从而优化一个或多个目标。切割和包装问题在过去几十年的文献中得到了广泛的研究。

在一些工业切割过程中，例如在家具和硬纸板公司中，切割设备能够仅在板材上进行一刀切割（Gilmore＆Gomory 1965，Farley 1983，Yanasse等，1991，Carnieri等，1994，Morabito＆Arenales 2000，Morabito＆Belluzzo 2005）。一刀切割是从板材的一个边缘到相对边缘的切割，平行于其他的边缘。换句话说，如果当它应用于矩形，会产生两个新的矩形，则这种切割是一刀切割。根据切割设备，板材的可行的二维切割图案可以通过一刀切割的至多两个阶段来生产。在第一阶段，在板材上产生平行的纵向（水平）一刀切割，而不移动，以产生一组条带。在第二阶段中，一个接一个地推动这些条带，并且在每个条带上形成剩余的平行的横向（垂直）一刀切割（见图1）。如果不需要额外的修剪（即每个条带中的所有物品具有相同的高度），则切割图案被称为精确的两级一刀切割（图1a）;否则称为非精确（图1b）。

24times;10 24times;10

1. (b)

在这项研究中，我们解决了如何切割一套具有已知尺寸和数量的矩形物体的非精确两阶二维切割问题，从而制作出一组具有规定尺寸和要求的矩形材料。我们假设有序项目的分类可以是具有非常大的异质性的，即可以通过事实证明这一组项目，其中只有很少的项目具有相同的大小。我们尤其关心的问题的特殊情况是，切割图样中的未使用的材料（剩余部分或边角余料）可以在未来使用，如果它足够大以满足未来的项目要求。换句话说，我们认为切割图样的修剪损失不一定代表材料的浪费。如果这种修整损失尺寸合理，则可以在随后的切割过程中储存并再次用作添加物（然后称为剩余零件或剩余物料）。相对地，如果修剪损失被认为太小以至于将来不能使用，则表示材料浪费，并作为废料丢弃。因此，该问题被看作是可用剩余物料的非精确的两阶二维切割问题。请注意，这个问题中的库存物品的种类被认为是异质的，因为以前的切割过程的剩余物料被重新储存。

根据Wascher（2007）等人的类型学，根据储存对象的异质性（根据可能性重新投入新的剩余材料）和小项目的强异质性假设，这种切割问题可以被描述为“剩余装箱问题”。否则，如果物品的种类差异很小，那么这个问题将被视为“剩余的切割库存问题”。实际上，本研究中提出的模型适用于这两个问题，因为为了避免对称解，相同的项目和不同的项目有着不同的处理方案。我们观察到，最小化切割物体的成本或修剪损失的简单目标可能不适用于此问题。 Brown（1971）首先讨论了在切割和包装问题中的剩余物料的使用，但是关于这个问题的研究主要是在Dyckhoff（1981）的工作之后开始的。许多作者研究了允许提供残留碎片的一维切割/包装问题，例如Roodman（1986），Scheithauer（1991），Gradisar et al。 （1999），Sinuany-Stern＆Weiner（1994），Gradisar＆Trkman（2005），Trkman＆Gradisar（2007），Cherri et al。 （2009，2013），Dimitriadis＆Kehris（2009），Cui＆Yang（2010），Gradisar等人（2011），Bang-Jensen＆Larsen（2012）。对一维切割可用剩余物料问题应用实例的报道，如纺织业（gradisar等人。1997）、农用轻型飞机制造（abuabara和莫拉比托2009）和木材加工业（科赫等人。2009）。据我们所知，文献中报道的所有研究都集中在一维剩余装箱问题中，除了最近发表的论文（Andrade et al。，2014），涉及二维非一刀切割问题与可用剩余物料。我们不了解涉及两个或多个维度的剩余装箱问题的其他研究。

本文的结构如下。在第二部分中，我们提出两个MIP模型用于两阶段二维仓库包装问题，而不考虑剩余物料。这些模型是基于Lodi＆Monaci（2003）为两阶段二维背包问题引入的模型的高度之上的。然后，在第3节中，我们提出了两个两阶段二维剩余装箱问题的二级模型及其一级MIP重构。在第4节中，我们报告并分析了通过使用CPLEX的分支和切割方法求解模型而获得的数值结果。 最后，在第5节，我们提出结论和讨论未来研究的观点。

2无剩余物料的两阶段装箱问题

在本节中，我们提出了两个MIP模型，用于解决不考虑剩余物料的情况下的，非精确的两阶二维装箱问题。这些模型是对Lodi＆Monaci（2003）为两阶段二维背包问题引入的M1和M2型号的直接扩展。其他两阶段二维背包模型可以被认为是Silva等人提出讨论的。 （2010年），Furini＆Malaguti（2013年）。只有一少部分的文学交流中的研究，讨论了两阶二维装箱问题。大部分研究涉及的都是两阶段二维背包问题或两阶段二维切割问题。举个例子：Gilmore＆Gomory（1965）开发的方法，是基于具有生成两阶段切割模式的列生成过程的单纯形法。该程序涉及两个阶段。在第一阶段中，为每个纵向条确定切割图样，而第二阶段决定每个条带应使用多少次。如果有序物料项目的分类较弱，即小项目可以分为相对较少的类别，并且每个类别中的项目数量“非常”巨大，那么这种方法效果是很好的，就像两阶二维切割问题的情况一样（Wuml;ascher等，2007）。

基于两阶段二维切割问题的解决方案在文献中是很常见的，例如Farley（1983），Riehme等人（1996），Hi fi（1997），Morabito＆Garcia（1998），Yanasse＆Katsurayama（2005）。当具有相同大小的一组物料项目的情况出现时，作者提出了单纯形法的宽松解决方案的舍入方法（Wauml;scher＆Gau 1996，Poldi＆Arenales 2006）或与列生成相结合的贪婪启发式程序（Hinxman 1980，Poldi＆Arenales 2009），对于两阶段二维装箱问题可能无法正常工作。在Beasley（1985），Hadjiconstantinou＆Christo fi des（1995），Morabito＆Arenales（1996），Riehme（1996），Hi fi（1997），Hi fi＆Roucairol（2001），Lodi＆Monaci（2003），Cui （2005），Belov＆Scheithauer（2006），Cintra（2008），Silva et al。 （2010），Morabito＆Pureza（2010），Cui（2013），Cui＆Huang（2012），Cui＆Zhao（2013），Furini＆Malaguti（2013），Furini （2012），Mrad等 （2013），Alvarez-Valdes等人 （2002），Lodi et al。 （2002），Macedo et al。 （2010），等人的文章中也可以找到关于切割问题的其他研究。

2.1 两阶段装箱模型M1

让我们考虑p个大的矩形对象，每个对象l宽度为W_l，高度H_l和每单位面积c_l（l= 1，...，p）和n个小矩形项目的成本，每个项目i的宽度wi 和高度hi（i = 1，...，n）。非精确两阶二维装箱问题可以定义为将所有n个项目打包（切割）到（从）所选择的对象子集中的问题，从而得到每个对象获得的包装（切割）图样是可行的（打包的物品不会根据非精确的一刀切割图样在物体内重叠和填充），并且使用的物体的成本最小化。我们只考虑第一阶段在板材上切割的情况是水平的，即它们平行于物体宽度。 不允许项目旋转，并且没有与对象内的项目的定位相关的其他约束。

一般情况下，我们假设h₁ge;h₂ge;...ge;h_n。且我们还假设物体上的切割无限薄，否则，我们认为锯片厚度被添加到物体和物品的尺寸上，从而确保一般性（Gilmore＆Gomory 1965，Morabito＆Arenales 2000）。此外，我们假设对象和项目的所有维度以及对象单位成本都是整数。这不是在实践中处理实例问题的一个非常严格的假设，因为由于切割和测量工具的精度有限，并且由于用于定义对象成本的各种货币的精度也是有限的，可以通过规模的变化，方便的满足条件。下面提出的模型可以看作是Lodi＆Monaci（2003，p.261）中引入的两阶段背包模型M1的简单扩展，以处理两阶段装箱问题的一种模型。模型的原始目标函数被修改为可以适当地考虑多个对象。 为此，我们定义二进制变量u_l（l= 1，...，p），它们指示是否使用对象l：

u_l= （1）

其他二进制变量x_ikl（k = 1，...，n，i = k，...，n，l= 1，...，p）表示从中切割项目的对象：

X_ikl= （2）

图2：货架概念的插图。

根据Lodi＆Monaci（2003）中使用的术语，给定一个对象l，一个搁板被定义为宽度为W的对象的条带，并且高度等于其中包装的最高项目的高度。假设架子中的所有物品在货架上都具有一个底（下侧）。货架的顶部由最大高度的物品的顶部（上侧），决定了下一个货架的出口。货架概念如图2所示。在这个图中，有一个对象和三个架子：1,4和6.项目1,2,3和5在架子1中，项目4和7在架子4中，项目6,8和9在架子6中。请注意，每个货架的数量被定义为包装在其中的第一个物品的编号。 在下面提出的模型中，我们认为我们可以有多达n个货架，每个货架都由一个物品定义。我们说，如果项目k是分配给（或包装在）货架中的最小索引项目，则货架k是打开的（或使用的）。在这种情况下，如果物品k在货架k上，货架k被分配给物体l，则我们有x_kk = 1。请注意，任何最佳两阶段切割图样都具有相同的切割图案，每个货架中最大高度的物品是放在架子左边的第一个项目（如图2所示）。 一个可行的两阶段一刀切割图案由货架组成，分配到货架的每个物品最多切割两个阶段（加上修剪）。 给出了一个非精确两阶段包装问题（不用剩余材料）的M1型模型：

目标函数（3）最小化了所使用对象的总成本（注意，如果c_l = 1，对于所有l，（3）总对象区域切割最小化）。约束（4）确保，对于每个使用的对象，敞开货架的高度之和不大于物体高度，而敞开货架仅归因于已使用的物体。约束（5）确保，对于每个对象，分配给每个

全文共6546字，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[143959]，资料为PDF文档或Word文档，PDF文档可免费转换为Word