英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
运筹学，23卷， 1975年3月 - 5月，第3号
控制切割模式改变一维下料问题
ROBERT W. HAESSLER
怀特州立大学，俄亥俄州代顿
（原件1973年5月15日，最后，1974年9月20日）
本文提出一维修剪问题的一个公式，即固定的费用与使用切割模式有关。固定费用的目的是限制必要的模式变化的数量。由于可能的切割模式数量众多，所导致的问题是远远超出了现有算法的能力的组合程序。因此，我们制定了一个启发式程序，可以通过实验调整来平衡潜在的相互冲突的目标，即尽量减少修剪损失和模式变化。启发式程序是围绕一个顺序搜索来组织的，该搜索依赖于未计划订单的描述符，以便为下一个进入解决方案的模式（如修剪损失和模式用法）设置目标。提出一个示例问题，并讨论启发式过程的应用范围。
诸如钢铁和纸张等许多行业的一个重要问题是如何确定生产管料或管料应如何切割成用户所需产品的宽度。由于与生产材料相关的明显的经济效益比用户要求的大得多，所以会发生切割原料或修剪等问题。
在这个问题中最明显的经济考虑是修剪损失，即由于尺寸考虑而未使用的那部分管材。目前在很多情况下可以找到最小修剪损失的解决方案。虽然这是一个重要的进步，但管材修剪问题并未得到解决。由于所涉及的材料通常每单位重量的价值较低并且需要许多处理操作，因此将判定标准定义为修剪损失的最小化通常是不恰当的。一个更好的标准是所有可控成本的最小化。这不仅包括修边损失的成本，还包括各种操作（如分切）所产生的成本，产品在重新形成之前必须符合用户提出要求。这些成本是可控的，因为选择切割模式可控制完成每个操作所需的时间长短。
除修剪损失以外的其他因素可能会引入非线性，使得找到最优解更加困难，甚至不可能。因此，文献中很少有非线性问题的解决方案。尽管如此，非线性问题还是存在的，并在很大程度上阻止了电脑化修整程序的实施。手工生成的解决方案（至少隐含考虑这些非线性因素）通常优于由不完整的计算机模型生成的解决方案。
除了希望找到更好的解决方案之外，还有很大的动机来开发用于解决修剪问题的计算机程序，以减少出错的机会，缩短从接收客户订单到订单开始制造的时间滞后，一般是增加处理最后的订单变化的能力。毫无疑问，在某些情况下，这种需求决定了接受一个不完整的模型。但是，仍然有许多情况下计算机是几乎影响不到这个生产调度过程。
本文的目的是提出一种有效的计算机化程序，用于解决与模式变化相关的固定费用的一维修剪问题。介绍了一个样本问题及其解决方案，并讨论了启发式程序的应用范围。在参考文献6中，我们处理了只有当切割模式的使用水平低于某个最小值时才产生的非线性亏损。在这种情况下，生产管材被切成两半并送到再加工卷绕机进行进一步分切。由于时间限制和存储过程中的库存空间有限，所以必须进行后处理。使用率高的模式可以有足够的时间设置卷绕机来切断整个管，从而避免任何后处理。本文提出的解决方案程序是对参考文献6中提出的解决方案进行修改，以解决更常见的固定费用类型问题。
1，回顾过去的发展
许多作者认识到，一维或滚切损失最小化问题可以用下面的公式来描述为线性规划问题：
#39; #39;
min ,
属于 ,
,
这里，R是订货需求量的向量，是具有元素，i=1，...，n，的切割模式向量，其中是从生产管中获得的管度W的数。
是按照模式J处理的生产管的数量，是模式J引起的修剪损失的英寸数。如果W是最大可用宽度，则
为了使成为可行的切割模式，必须满足以下限制条件:
,
整数
中等大小的问题中可能存在大量的裁剪模式，从而排除了用标准线性编程代码解决这些问题的可能性。直到1961年,Gilmore和Gomory开发了他们的延迟模式生成技术，可以有效地解决可能出现的任意模式的问题。
像这样的新开发项目出现的时候，很多尝试都是用这个模型来解决一维的切削库存问题。直到花费了大量的努力，生产经营者继续拒绝接受最优的解决方案时，才终于认识到，在大多数情况下，只考虑到减少损失的最低限度并不是一个适当的标准。在大多数现实库存问题中，还必须考虑其他因素。例如，
1.解决方案必须是有价值的。关于这个要求的讨论是在Woolsey(10)中给出的.
2.现有的手动解决方案程序通常会生成解决方案，其中活动模式的数目远远小于所需数目的大小。除退化性外，线性规划理论规定活动变量的数目与所需数目的大小相等。在许多情况下，与改变切割模式相关联的设置成本或固定费用使的一维切割库存问题不是非线性编程问题，而是具有与模式变化相关的固定费用的整数特征问题。
第二种情况可能以多种方式出现。如果管材在生产过程中被切开，频繁的模式变化可能使分切机无法跟上。因此，如果模式变换的次数不受控制，则可能导致处理成本增加或关闭生产设施。即使分切机能够继续运行，由于增加的分切改变所引起的时间压力可能会导致产生错误尺寸而造成更的高代价。如果该管材被切断线没有从生产设施的直接压力，增加模式的变化将导致增加总的所需的时间来处理一个给定的订单增加的时间等于额外的格局变化时代的预期时间的数量来改变切割机。
2.数学模型
一维下料问题的更好的表述是： min,
主体为,
,取整
是每英寸修剪损失的美元值，
是以美元为单位改变模式的成本，
和是客户订单要求的上限和下限，反映了一般行业常规允许有限的超支或欠款，且
， 和 0 除外。
上面提出的数学编程问题显然远远超出了现有整数编程代码的能力。 Pierce提出了一种方法来生成所有不受控制的切割模式，并证明这个数字可以非常大，他给出了一个具有800多种切割模式的七种尺寸的示例，以及一种具有超过900,000切割模式的示例。解决像这样的问题的唯一现实方法是开发一个启发式程序，在合理的时间内生成好的但不一定是最佳的解决方案。这些问题目前正在人工解决，并且在任何特定情况下都可以测量手动解决方案的质量以及开发它们的相关成本。为了在经济上合理，计算机化的启发式程序必须能够以合理的成本产生较好的解决方案，使得启发式程序的可控生产成本加上获得解决方案的成本的总和比手动程序少。
启发式解决方案的开发依赖于确定重要的解决方案特征，然后构建搜索过程和决策规则，这些规则将生成具有这些期望特征的解决方案。 显然，关键是要找到修剪损失小，使用率高的切割模式。 具有较低修剪损失的模式将根据需求控制修剪损失，而具有较高使用频率的模式将倾向于减少方案中不同模式的总数。 此外，还需要控制模式中管材的数量，以防止在解决方案过程的某个未来阶段出现宽或窄管的不平衡。下面描述的面向目标的顺序搜索过程，在为一维的切削库存问题生成高质量的解决方案方面是非常有效的。
该程序首先分析未计划的客户订单，以提供当前问题情况的两个简单描述符。 第一个描述符是满足剩余需求所需的生产管数量的估计值。这是, 其中W是生产管的可用宽度, 是第i个订单所需的尺寸，而是仍然需要安排的管材数。第二个描述符是从每个生产管材中获得的平均管材数。这个,是 仍然需要预定的总管数除以所需的生产管数。这些剩余需求的描述符用于为下一个模式设置一个期望级别，以进入解决方案。期望水平只是一个目标，它必须满足在评估一个模式可能进入解决方案时所考虑的每一个重要特征。这些特征包括：修剪的损失，图案的数量，以及可以根据模式切割的生产辊的数量，而不超过订单的要求。具体来说，目标是为每个重要的模式特征设定的
1, 最大允许修剪损失MAXTL
2，MINR和MAXR是模式允许的最小和最大卷筒数量
3，根据模式MINU处理的生产卷的最小数量
这些数量的实际值取决于剩余的订单需求。MAXTL的典型值为0.006W ~ 0.03w。当完成订单要求所需的生产管数量减少时，允许的修剪损失更大。在此情况下，MINU的价值从0.5到0.9不等，在本例中，由于生产管材的数量下降，MAXR的产量通常等于设备最大的切割能力。通常情况下，MINR将比每个剩余的生产管的平均管数少一个，然后进行搜索，以确定是否存在满足或超过上述目标的可行切割模式，即包含非负整数元素的切割模式；
1，（修剪损失不超过最大允许值。）
2,。（模式中的总卷数落在界限范围内。）
3，,对于所有的。（在模式中出现大小的次数是有限的，所以模式至少可以满足使用需求。）
为了完成对满足于当前期望水平的模式的搜索，订单按预定的数量从最大到最小进行排。搜索是通过在字典式下降顺序中生成的模式来进行的，并且限制了仍然要调度的最大数量的订单大小必须在非零级别的范围内。在使用目标MINU上，搜索只执行那些可行的模式。这仅需要对给定尺寸在模式中出现的次数设置上限。例如，如果是轴的数量对于i尚未安排的订单，以及使用模式的次数的大小是MINU，则可以使用大小为i的最大卷数。在模式中考虑的是[/ MINU]，其中[a]表示小于或等于a的最大整数。
如果搜索不成功，期望值就是MINU的值。这种减少扩大了搜索所执行的模式的子集。如果搜索对MINU大于1的所有值都不成功，MINU将被设置为1，并接受最小修剪的模式。这一步确保了程序将以可行的解决方案终止。
所选模式将以最大使用级别输入到解决方案中。确定该最大使用级别，使得每个尺寸的预定管数不超过订购的数量。在此模式下，按预定的数量减少订单需求，并重复这个过程，直到满足所有订单需求为止。图1是这个过程的流程图。
这种程序的优点是没有舍入问题，如果需要，可以安排精确的数量。当然，允许超运行会允许更大的模式使用值，并且会减少使用的模式的数量，超跑也可以用来填充最后的模式使用，并且会减少模式的数量。
由于所使用的解决方案程序仅以顺序方式生成一个解决方案，因此不需要显式输入的值（成本变化模式）。当然，这个值和修剪损失的成本是比较两个或两个以上的解决方案，以确定哪个是最优的。对启发式程序的模式变化和修剪损耗进行了权衡，通过改变输入参数，控制最大允许的修剪损失。相反地，如果减少了修剪损失的因素，所产生的解决方案就会减少;所以需要更多的模式来满足订单。这一事实可以通过查阅搜索过程来很容易地看到。高强度损失的模式更容易在高使用率中找到因为它们的数量很多。
3，计算结果
表I包含了来自造纸工业的示例问题及其通过上述程序的计算机化版本的解决方案。 这个问题涉及27个不同尺寸的相对较窄的辊子，从141英寸宽的生产管上切割下来。 为了满足总订单要求，总共使用了仅根据八种不同图案加工的25个生产管材。 整体修剪损失为14.6英寸，即0.4％。表1中问题的解决时间在IBM 360/50A线性编程解决方案上小于3秒会导致修剪损失降低，但模式数量会大幅增加。
线性编程解决方案会导致较低的修剪损失，但模式数量会大幅增加。作者开发了一种线性编程程序，设计了一种只有3.9英寸的修剪方法，但有16种模式。在许多情况下，要求进行16次模式更改以处理25个生产辊，这在生产车间是不可接受的。
如参考文献6中所报告的，当在实际调度条件下对类似的启发式程序应用于一系列问题时，与手动解决方案相比，其导致修剪损失减少25％并且所需模式的数量没有明显增加。 其他应用程序导致修剪损失的更大节省，而不会增加生成的模式数量。 当然，节约成本取决于目前正在使用的程序的质量。
4，应用范围
显然，一个连续的启发式程序，例如这一种试图控制模式数量的方法，取决于有大量的方法来组合大小，最终有相对较小的损耗。但这恰恰是存在于各种各样的滚切问题中的条件。相反地，这种启发式程序在处理相对较少的大小问题时不会成功，在这些问题中，平均滚动宽度与生产辊的宽度有关。
在小的问题上，计算机的修剪几乎没有什么回报，因为经常可以通过检查得到最好的答案。对于那些订单平均的宽度大于生产管材宽度1/4的问题，一般情况下会有大量的方法来组合尺寸以获得较低的剪切损耗。在这种情况下，特定的尺寸用特定的方式组合起来是非常重要的。当然，这只能通过使用一个迭代的过程来控制，比如线性规划，同时考虑所有的大小。另外，通常不可能有相同类型的减少这些问题的模式，这些问题用我们的启发式程序解决了。对于表1中的示例，模式的数目小于尺寸的1/3。对于大尺寸的问题，由启发式程序产生的模式的数量可能是0.7倍的大小。
从总操作效率的实际角度来看，在我们的启发式程序中包含一个线性编程子程序很简单。线性编程子程序可以根据需要或根据修剪损失标准自动调用。 如果修剪损失过高，则可以通过使用线性编程获得非整数解决方案立即解决问题。 该解决方案然后为问题的修剪损失提供下限。 如果决定使用由线性编程子程序生成的解决方案，那么整数需求可以通过在必要时四舍五入来处理，然后使用启发式过程来完成剩余的需求。
5,结论
到目前为止，人们一直关注解决方案的质量。 显然，使用计算机化的修剪程序的最大动机是有更好的答案。 使用这个程序还有其他的好处。最重要的之一是消除错误，例如在编写或键入创建制造订单所需的信息时发生的错误。如果事后才发现这些错误，则成本可能非常高。
另一个优点是可以生成解决方案的速度和准备的制造订单。此速度允许调度器等待最后时刻的订单，并在订单更改时快速解决问题。等到最后一分钟再解决一些问题的能力应该从订单周期中减少24到48小时，从而提供更好的客户服务。解决问题的速度也提供了另一种可能非常重要的选择。在某些情况下，客户可以指定一系列参数，例如直径，这是可以接受的。然后由调度器决定要按哪个直径进行排序。做出这个决定的一个很明显的方法是用包含和排除的顺序来解决适当的问题，并在此基
全文共6080字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[9525]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
