英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料
整合二维下料和生产批量问题
E Silva1 , F Alvelos1,2 and JM Valeacute;rio de Carvalho1,2
1 Centro de Investigaccedil;atilde;o Algoritmi da Universidade do Minho, Braga, Portugal; and 2 Escola de Engenharia, Universidade do Minho, Braga, Portugal
二维下料问题（The two-dimensional cutting stock problem ，2DCSP）的目的在于最大程度地减少了用于切割一组毛坯的板材的数量。在工业中，通常在每个计划时间段的开始都考虑此问题的一个实例，当考虑一组计划时间段时，这可能导致解决方案质量低下，即浪费过多。为了解决此问题，我们先考虑一个整体的问题，其中二维下料问题从仅单个生产计划期间的解决方案扩展到多个生产计划期间的解决方案。该方法与文献中方法的主要区别在于，此方法允许在计划展望期的后续阶段中存储和切割足够大的残留板材（余料），进而可能有助于最大程度地减少浪费。我们提出了两个完整的整数规划模型，以优化组合的二维下料和批量问题，从而将包括材料，废物和存储成本在内的总成本降至最低。还提出了两种基于工业实践的启发式方法来解决该问题。得出并讨论了所提出的模型和启发式方法的计算结果。
关键词：下料；生产批量；计划生产； 整数规划
1． 简介
由于其大量的实际应用，在过去的50年中对二维下料料问题（2DCSP）进行了广泛的研究。在大多数行业中，并未将其作为集成过程的一部分进行研究（Erjavec 等人, 2009）。在每个时间段开始时都会重复进行下料方案，从而满足该时间段客户的需求。
在计划展望期的每个阶段中为2DCSP寻找最优解的过程都不同于完整的计划展望期评估。预测毛坯的生产并将其存储起来，以便在规划期的后续阶段使用，对应于从局部策略到全局最佳策略的转变。以解决更困难的问题为代价，提高了生产效率并降低了成本。
在本文中，我们研究了二维下料问题和批量问题（2DCS–LSP）的集成。给定计划展望期内给定的矩形毛坯需求，求在计划展望期的每个时间段内要从矩形板材切下的毛坯数量，以使整体成本，即板材成本之和，将存储成本和浪费成本最小化。2DCS是一个非确定多项式（NP）难题，因此它与批量问题的集成也是非确定多项式难题。
在集成于2DCS-LSP中的2DCSP中，有一组大小相同，即宽度和高度相同的矩形板材原料，从中切出了一组较小的矩形板材（毛坯）。较大的板材（假设）无限个可用，要切割的毛坯组根据其大小（宽度和高度）按类型分组。目的是最大程度地减少使用的板材原料的数量或浪费。在嵌入式多毛坯LSP中，目的是确定给定时间段内每个毛坯的生产数量，以满足每个周期内毛坯的需求，从而最大程度地减少存储和生产成本。
分别求解这两个问题可能导致组合问题的非最优解。将2DCSP和LSP集成可以看作是在预期某些毛坯的生产，在矩形板材原料中获得更好的毛坯组合和较小的浪费之间，在非预期毛坯的生产和较小的存储成本之间寻求平衡。
如下所述，在第2节中，有些作者已经考虑过预期生产或存储完整的板材或毛坯。但是，在某些情况下，由于没有考虑材料的存储，因此必须浪费给定时间的毛坯剩余（leftovers）。在本文中，我们基于不同的决策变量提供了新模型，该模型允许存储毛坯和余料（以及完整的板材），因此余料可以在后续阶段中以两阶段非精确布局图使用。显然，该模型可以为解决方案提供更好的原材料利用。
提出了两种方法来获得针对此集成2DCS-LSP的最佳解决方案。第一个整数规划模型（MIP）是Silva等人（2010）提出的2DCSP整数规划模型的扩展。第二个整数规划模型可以看作是Dyckhoff（1981）的整数规划模型的扩展，用于一维下料问题（1DCSP）。
所提出的模型可以通过对某些毛坯的生产预期进行建模，并且还可以在计划展望期的每个时间段结束时存储毛坯余料，从而优化求解集成的2DCS-LSP。它们不是基于布局图的生成。
为了将实际解决方案与实际使用的解决方案进行比较，开发了两种基于工业实践的启发式方法。一个可以使所使用的板材的成本最小化，而另一个可以使存储成本最小化。
本文的结构如下。在下一部分中，将介绍集成的2DCS-LSP的文献综述。然后在第3节中，描述了所解决问题的整数规划模型。在第4节中，给出了启发式方法和示例。在第5节中对计算结果进行了报告和分析。最后在第6节中介绍了本文的主要结论。
2. 文献综述
关于2DCS-LSP集成的论文很少，而且大多数工作与工业应用密切相关。
解决合并问题的第一项工作来自制衣业（Farley，1988）。提出了一个整数模型和一个二次模型，其主要目的是在考虑切割，缝纫和存储成本以及过度生产和生产不足成本的情况下，使总体生产成本最小化。虽然考虑了多个生产周期，但集成切削料和批量问题并未明确解决，而是将这些问题表述为在单个周期内计划生产的问题。
在铜工业中，Hendry等人（1996）也以综合的方式分析了生产过程。提出了一个两阶段的解决程序：在第一阶段，确定1DCSP的汇总解决方案，在第二阶段，确定该时间段内每天的生产计划。启发式程序用于求解第一阶段，而整数规划模型用于第二阶段。
Nona˚s和Thorstenson（2000）以组合模式解决了自卸卡车公司中出现的形状不规则且批量需求随机的2DCSP问题。主要目标是最大程度地减少浪费，存储成本和设置成本。该问题被公式化为具有凹目标函数和线性约束的非线性模型。使用启发式方法和列生成程序来解决该问题。后来，在Nona˚s和Thorstenson（2008）的研究中，提出了与Haessler（1971）提出的顺序试探法相结合的方法。
在Menon和Schrage（2002）的一项研究中，一维下料问题似乎嵌入了并行机的订单分配中。利用问题的对偶角结构，针对对称性的降低，提出了一种基于紧子问题边界构造的方法。在Arbib和Marinelli（2005）的研究中，1DCSP与库存计划相结合。提出了一种整数规划模型和一种用于集成分层生产计划系统的方法。该模型是逐日优化器的扩展，可以包括运输和存储成本，还可以用于管理热订单（当生产计划完成后订单到达时）。
在造纸工业中出现的一个问题中，Poltroniere等人（2008年）处理了集成的纸下料和批量大小问题。提出了一种整数规划模型，并采用两种分解启发式算法作为求解方法。所提出的整数规划模型的拉格朗日松弛法得到的第一个启发式结果包括：首先解决批量问题，先解决一元的纸箱的生产批量问题，然后解决下料问题。提出的第二种启发式方法首先解决了下料问题，假设一元的纸箱的数量不受限制，则该问题的解决方案提出了每种时期每种纸张的卷数要求，然后下料问题也就解决了。
Gramani和Franccedil;a（2006）解决了合并的2DCSP和批量问题。问题是要确定在计划展望期的每个时期要生产的毛坯数量，以使所使用的板材数量，存储成本和安装成本最小化。提出了在锯床容量中具有时间限制的整数规划模型，但是未涵盖计划展望期的后续期间要使用的余料的存储。即使提出了整数规划模型，也只进行了使用网络最短路径表示的启发式计算实验。网络的弧与容量关联的2DCSP由Gilmore and Gomory（1965）通过列生成程序解决。在解决了与每个弧相关的2DCSP之后，解决了最短路径问题。在这种方法中，不是预测单个毛坯类型的产量，而是预测给定客户的所有毛坯的总产量。该方法包括首先解决批量问题，然后在第二阶段解决库存问题，将这个启发式方法与工业上通常使用的方法进行比较。作者得出的结论是，解决组合版本的问题可能会带来高达28％的收益。
Gramani等人（2009）的研究考虑了不同的变体。在这种情况下，保留了Gramani和Franccedil;a（2006）提出的时限能力和建立成本；不允许剩余料的存储，并且需求以最终毛坯表示，并且只允许存储最终毛坯，而不是单个毛坯。并采用了基于拉格朗日松弛的启发式程序提出了整数规划模型。
Gramani等人（2010年）的研究提出了另一种变体。在这种情况下，不考虑安装成本，也不考虑布局图的整数频率。但是，它考虑了最终毛坯和单个毛坯的存储。使用线性规划模型，该模型基于Gramani等人（2009）研究中使用的模型，并通过列生成进行求解。
Poldi（2007）的一项研究解决了类似的问题，即多期切割库存问题，该问题考虑了在计划展望期内预期和不预期某些毛坯的生产之间的权衡。在每个时间段内可以使用不同尺寸和有限的数量的初始板材，在给定时间段内未使用的初始板材将保留在库存中，并可在下个时间段内使用。但是，没有考虑在随后的时间段中存储要切割的残余物体。以此提出了整数规划模型，通过列生成求线性松弛的解，并通过启发式方法求整数解。
本文中提出的整数规划模型解决了集成的切削料和批量问题，其中可以将剩余的物体存储在库存中并在随后的时间段中使用，从而获得两阶段的非精确切削模式。本工作中考虑的公式与Gramani和Franccedil;a（2006）提出的公式之间的主要区别在于，可以存储余料，以及所提出的模型紧凑且不依赖于切削模型的产生这一事实。由Gramani和Franccedil;a（2006）撰写。
3. 整数规划模型
在本节中，提出了两个用于2DCS-LSP的整数规划模型。这两个模型都具有Dyckhoff（1981）为1DCSP提出的模型作为灵感：Silva等人（2010）在研究中提出的模型2是先前对2DCSP模型的扩展而产生的，模型II是新的扩展1DCSP。
Dyckhoff（1981）提出的模型是灵活的，考虑到了可能与实际问题相关的扩展问题。Silva等人（2010年）提出了切削刀具问题的二维版本的扩展，它解决了来自“现实世界”或文献中的实例，并取得了很好的结果。
开发两个整数规划模型的主要理由在于，它们适合于处理残差件的存储。
3.1. 模型I
提出的模型是Silva等人（2010）为2DCSP提出的整数规划模型的扩展，这是Dyckhoff（1981）为1DCSP提出的“一刀切”模型的扩展。
模型的中心概念是一组基本操作（一个或两个裁切机切口），在此用切口表示，该步骤可从板材上获得毛坯。通常，切割会导致一件毛坯和两块板可以进一步切割（板材余料）。
剩余板有两种类型：顶部矩形和右侧矩形。顾名思义，如果残板在要切割的毛坯的顶部，则将其视为顶部矩形；如果残板在要切割的毛坯的右侧，则将其视为右侧矩形。板材中毛坯的布局必须符合与产生切口的切割机有关的限制（从板材的一个边界到另一边）。切口也仅限于两个阶段，这意味着切割机切口的方向只能进行一次更改（水平和垂直）。所考虑的布局图，即板材中毛坯的布局，是两阶段不精确的类型。这意味着这些毛坯是通过一组水平切口从板材中获得的，该切口将板材分成条板，随后是一组垂直切口，分离不同的毛坯。可以进行额外的水平切割，以将毛坯与废品或残板分开。
在图1中，显示了两阶段的非精确布局图，粗线表示水平和垂直切割。
从图中可以看出，首先执行水平切割并得到两个板条，一个板条具有两个第二类型的毛坯，另一个板条具有一个第一类型的毛坯和一个第二类型的毛坯。第二组中的切口具有垂直方向，将板条分开。在顶部的板条中，有两个毛坯
图1 两阶段非精确切削料模式
图2 剪切示例
该模型基于所有可能的切口和残板类型的枚举。Silva等人（2010年）的研究给出了生成所有切口和所有残余板材的算法，以及残余板材和切口类型数目的上限。整数规划模型的主要思想是为每个切割关联一个决策变量，即与切割的次数相关联。
使用简单的规则来计算切口，从而计算所得残板的宽度，高度和阶段。在图2中，显示了两种可能的切割类型。
在情况A中，出现的切口（粗线）可以在第一阶段的初始板中或残留板中进行。情况B中出现的切口类型只能在第二阶段的残留板材上进行。由于这项工作中考虑的布局图是两阶段不精确的，因此在当前计划期间将不考虑案例B中的第三阶段的残余板材来获得工件。但是，可以将它们保留为库存，作为下一个时间段中要切割的毛坯余料，然后视为初始板材。
因此，如果第一阶段或第二阶段中的剩余板材不用于满足当前计划期间的需求，则将其视为剩余板材。第三阶段的顶部剩余板材是一种特殊情况，因为它们在获得它们的时间段内被直接视为剩余板材。但是，这些残板可在获得残板的那段时间内用于切割。
为2DCS–LSP提出的整数规划模型基于2DCSP的整数规划模型，主要区别在于对时间段的考虑，与物料和残料板的存储相关的决策变量的使用以及与花费。
从现在开始，假定每个时间段都知道所有可能的切割和相应类型的残余板材（有关算法，请参见Silva等，2010）。
公式：在2DCS-LSP中，初始矩形板的宽度为W，高度为H，订购毛坯类型i的宽度为w i，高度为h i，t时期内对i型需求为d ti。毛坯类型的数量为n，剩余板材的类型数量为m，时间段的数量为T。板材类型由j表示，j=0,... ,m，其中j=0 对应于初始板材，j=1 ,... ,m ，对应于剩余板材的类型。参数和变量定义为：
参数：
d ti 时间段t中毛坯i的需求
c t
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[235862]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
