焊接的影响在一维下料问题:固定消防系统的情况下在建筑行业

文摘

安全是最重要的在建筑业和固定喷水灭火系统和水喷雾系统用于消防涉及网络不同长度的管道。制造商的固定灭火系统需要把现有的股票长(一维)下料问题延长现有的股票或剩余的部分通过焊接,焊接的(一维)下料问题。最好的工业实践安全要求只允许一焊管的长度。匈牙利的情况下制造商的固定灭火系统本文的动机,认为,下料问题的焊接(与单或多尺度股票)可以转化为一个等价的下料问题与多尺度(股票)。现成的算法和软件可能会被用来生成一个最优削减计划相当于下料问题。受到一定的限制,最优削减计划可能会被转换成等价的下料问题切割焊接模式最初的下料问题。

1。介绍

安全是最重要的在建筑业和固定用于消防喷水灭火系统和水喷雾系统不可或缺的各种各样的建筑从仓库、超市、教育机构。固定消防系统集成是在许多情况下强制性的,由欧盟成员国的欧洲标准EN 12845年,目前注册的,例如,在匈牙利和BS EN标准MSZ EN 12845:2015 12845:2015在英国。

固定消防系统管道的现场组装和涉及网络(从今以后,管道)各种长度(从今以后,大小从管道的股票)制造(从今以后,股票)。通常情况下,制造商需要将现有的股票大小(例如,从一个股票,从6米到4米2米剩下的部分)或延长现有的股票或剩余的部分焊透(例如,从6米到8米从两股,剩下的四段)。剩下的部分可能是焊接其他股票或对方,但最佳行业实践安全要求只允许一焊管。

在匈牙利的情况下固定消防系统的制造商,该公司使用单一尺寸,层高高达6米股票产生管道;表1说明了尺寸(14)和数量(31日)需要一个特定的网络。只有一个管大小伴随着股票大小;11人是短的,两个是更长时间。

制造管道固定灭火系统与单一或多尺度一维下料问题的股票和焊接一个焊管(从今以后,下料焊接的问题)。本文力图找到其最优解(即,最佳切割和焊接计划),并认为,现成的算法和软件的下料问题多尺度股票(从今以后,下料问题)可能被用于焊接的下料问题。数值测试发现本文提出的算法(见部分5匈牙利)足够的情况下固定消防系统的制造商。

这个简短的介绍后,部分2本文回顾了相关文献和立场的争论加剧下料问题的研究。部分3制定下料问题和下料焊接为一个混合整数线性规划的问题,讨论了切割和焊接模式性质,并证明了最优切割和焊接计划由最小切割和焊接模式。这一特点的最优切割和焊接计划在下一节中提出的算法的基础。部分4讨论了实际困难引起的高切割和焊接的股票数量和不连续的切割和焊接模式。接下来需要限制切割和焊接的数量的股票,从而限制焊接形状的下料问题算法建议在这一节中。生成最小切割和焊接模式和最佳的切割和焊接计划可能造成困难,也探讨了在这一节中,与程序运行时间,顺序模式和决策者的偏好。节5我们将前一节所提出的算法应用于匈牙利的情况下制造商的固定灭火系统与令人满意的结果。最后,部分6总结研究结果,并建议开展进一步研究的方向。

2。背景

的下料问题的问题,如何优化股票或如何削减股票先减少成本调查Kantorovich [1]和Kantorovich [2]。吉尔摩和Gomory[建议的列生成算法3]和吉尔摩Gomory [4超过二十年后成为研究者和实践者都广泛使用;吉尔摩和Gomory3]和吉尔摩Gomory [4]“是第一个提出技术几乎应用于困难的现实问题”(《理发师陶德》和咒文(5])。复杂的下料问题生成复杂的削减计划非常大量的可行模式。而不是试图一次性生成和调查,Gillmore Gomory算法首先生成和调查只有几个。随后生成切割模式取代现有的如果被证明更有效的调查,并通过迭代过程算法到达最优的解决方案。

Gillmore和Gomory算法的力量在于它能够产生最优解;其疲软无力生成最优削减计划,削减模式权重是整数。往往四舍五入小数点切割模式权重到最近的整数结果不可行或次优的削减计划和/或制造出有些订单和生产供不应求。生成最优削减计划下料问题因此成为进一步研究的重点;鲁德曼(6),沃斯切尔一如既往和高斯7],和Gradisar Trkman [8]提出的启发式方法,而•迪克霍夫头(9],Scheithauer和Terno [10),万斯等。11],Vanderbeck [12],和别洛夫Scheithauer [13提出进一步的算法。《理发师陶德》和咒文5和沃斯切尔一如既往等。14)提供全面的文学评论这些和其他一些heuristic-methodologies。

下料问题因此在运筹学焦点即使在最简单的,原始的,一维的定义;近年来,例如,Levine和Ducatelle [15)和Araujo et al。16进化算法用于下料问题。特别是与这篇文章相关的作品虽然是崔和杨17),剩下的部分回收调查。

削减股票是一个不确定性多项式时间——(NP)难题(Cheng et al。18),这可能需要指数软件运行时间;然而,在实践中,即使是大样本可能追究最优解(见Goulimis [19];别洛夫和Scheithauer13])。因此本文假设有算法和软件获取准确的(全球)节中定义的下料问题的解决方案1(见沃斯切尔一如既往et al。14类型学),包括MSSCSP)。如果我们的目标是设计业务应用程序非最优解决方案是可以接受的,然后准确的(全球)解决方案不是必要的,因为好的(启发式)解决方案是充分的。

Zak [20.)定义了切片库存问题,对应的下料问题,是“发现和最小长度的最大条目数可以通过连接构造给定长度较小的项目”(Martinovic和供应Scheithauer [21])。

切片存量的问题,连接项的数量没有限制。在我们的例子中,这是至关重要的,每项最多可以由两块。调查切割和焊接的问题是一个组合的下料问题和刮削股票的问题。Tanir et al。22)检查焊接的可能性在一个下料问题,提出了一个启发式方法。没有限制的数量每管焊接,而本文每个管道的焊缝数量是受限制的。

3所示。理论

3.1。制定下料问题

下料问题包括生成optimal-minimal成本削减计划。不同大小的管道(= 1,2, )需要各数量减少从不同大小的股票( , , )。可行的切割模式可能是由套整数( , , , ),在哪里股票指数和吗是管道的数量的大小从股票 。显然, 和 。

例如, - - - - - -, - - - - - -,和 - - - - - -计管道可以从单一尺寸, - - - - - -计的股票在各种可行的模式( , , , )。图1说明了5个这样的切割模式:6米库存削减到一个2米管和一个四管( ),在模式(1,- 1,0,1);为三个2米管道( ),在模式(1,3,0,0);成一个2米管,一个3米的管道,一个1米剩下的段( ),在模式(1,1,1,0);成一个2米管,一个3米管,两个0.5米剩下的部分( ),在模式(1,1,1,0);和一个2米管和一个四米剩下的段( ),在模式(1,- 1,0,0)切割模式反映了生产,不生产;因此,模式和是等价和模式是浪费。

如果代表所有可行的切割模式,然后切割模式 生产管道的大小价格模式 ,股票价格,也就是说,如果削减成本和很小的忽视。

因此,下料问题可能被制定为混合整数线性规划如下: 其中每一个可行解表示削减计划,一个最优削减计划以最小的成本,是一种可行的解决方案和决策变量 显示多少次使用切割模式削减计划 。

由于其指数大小,解决混合整数线性规划为大型实例来说是不现实的。在实践中,这应该与和和列生成(见别洛夫和Scheithauer [13]branch-and-price和列生成)。

最优削减计划不排除浪费的切割模式等模式在图1;和下料问题可能有多个最优削减计划。例如,如果四个2米管道需要从单一尺寸,层高高达6米的股票,那么一个最优削减计划可能使用两种模式削减一层高高达6米的股票三用2米高的管道( )和另一个6米的股票在一个2米管和一个四米剩下的部分( )。另一个最优的计划可以使用第一种模式两次削减两层高高达6米的股票6用2米高的管道( ),两个2米管太多。额外的注意事项,如数量的减少,大量的浪费和生产过剩,决策者可能更喜欢一个最佳削减计划到另一个。

3.2。制定焊接的下料问题

同样的下料问题,焊接的下料问题包括生成optimal-minimal cost-cutting-and-welding计划。可行的切割和焊接模式的数量就比可行的切割模式的数量。例如,如果四管道需要从单一尺寸,层高高达6米的股票,然后只有一个切割模式是可行的,下料问题,而不是两个切割和焊接模式可行的焊接的下料问题。下料问题,6米的股票只能切成2米四管道和浪费剩下的部分。在焊接的下料问题,“浪费”用2米高的剩余部分可能是焊接在一起,额外四管道(见模式和在图2)。但是,是否模式比模式取决于价格每焊缝相对于价格的股票,如果高,那么模式生活的全部。

在焊接的下料问题,可行的切割和焊接模式可能由整数集 和独特的赋值矩阵与行,列,只有0和1的元素。代表的股票数量的大小 , ,用于生产管道的大小 , ,通过切割和焊接。因此,第一行代表的第一个股票大小 ,第二行第二个股票的大小 ,…,这些行th的大小 。类似地, )行代表第一的大小 ,的 行第二个股票的大小 ,…, 这些行th的大小 ,等等。同时,第一列表示第一管道的大小 ,第二列的第二管尺寸 ,…,th列的th管的大小 。类似地, 列表示的第一管尺寸 ,的 列的第二管尺寸 ,…, th列的th管的大小 ,等等。如果行索引 ,列的 ,和元素的 ,然后 意味着至少有一些部分的管道生产至少有一些部分的股票吗 。本文假设没有股票大小和股票是多余的,因此 至少一次在每一行,每一列。因为任何一个股票可能是分配给任意数量的管道,但任何一个管可能只是从两个股票最多, 在每一列不超过两次。

的一组整数( )和赋值矩阵代表了一种可行的切割和焊接模式如果只有焊接矩阵可以提供一个可行的焊接方法。如果行索引 ,列的 ,和元素的 ,然后 当且仅当 。同样,如果股票的大小由行吗和管的大小由列 ,然后在任何一行的所有元素的总和小于和任何一个列中的元素的总和等于 。此外, 和 。此外,一个有以下:(我)管道尺寸小于股票的总和大小本身是不够的。例如,如果 米, 米, 米,然后( )= ( )需要三个焊接和不是一个有效的切割和焊接模式。(2)切割和焊接模式反映了生产什么,而不是如何产生。例如,从焊接的下料问题的角度来看,模式和在图1有相同的整数(集 )=(1,- 1,0,1)和分配矩阵 和焊接矩阵 )(见部分3所示。1)。的另一个例子,3.6米的管道可以从单一尺寸,层高高达6米的股票在不同切割和焊接模式,例如,通过削减一个股票在一个3.6米的管道,一个2.4米段( ),通过削减另一个股票3.6米管和两个1.2米段( ),通过焊接的两个1.2米2.4米段段( ),( )= ( ), ,和 ,通过减少每个两只股票在一个3.6米的管道,一个1.8米部分,一个0.6米的段( ),通过焊接两个1.8米段( ),与相同的 )= ( )和 和之前一样,但不同 ,等等。(3)冗余可以出现在切割和焊接模式,但这些不影响最优解。例如,通过减少每个两层高高达6米的股票在一个3.6米的管道,一个1.8米部分,一个0.6米的段( ),三分之一的3.6米的管道焊接。六个相同的整数(集 )= ( )——六个不同的赋值矩阵 , , , , ,和 对应六种不同的切割和焊接模式相同的实际结果。(iv)焊接不是一个强制性的切割和焊接模式的组件。例如,两个5米管道可以由两层高高达6米股票通过减少每个两层高高达6米的股票在一个5米管和一个1米剩下的部分( ),( )= ( )和 好像切割模式( )= ( )和=(1)使用两次。(v)切割和焊接模式的数量是有限的,由于管道的数量和库存的数量都是有限的。(vi)任何一个管只能产生两股最多,但切割和焊接模式可能涉及两个以上的股票,这可能是用不同的方法切割和焊接。

例如,六5米管道可以从五层高高达6米的股票通过削减每两层高高达6米的股票在一个5米管和一个1米段( ),通过减少每个两层高高达6米的股票在一个四段2米一段( ),通过削减一层高高达6米的股票两个3米段( ),通过焊接的两个1米段的两个四段( ),2米和焊接的两段的两个3米段( )(见图3)。因此这个切割和焊接模式是由( )= ( ),

如果代表所有可行的切割和焊接模式,然后切割和焊接模式生产管道的大小价格模式 ,股票价格和焊接,也就是说,如果削减成本和很小的忽视。

类似于下料问题,焊接的下料问题可以制定以下混合整数线性规划: 其中每一个可行解表示一个切割和焊接计划,一个最佳的切割和焊接计划以最小的成本,是一种可行的解决方案和决策变量 显示多少次切割和焊接计划使用切割和焊接模式 。

类似于下料问题,由于其指数的大小,这种方法是不切实际的解决大型实例。在实践中,这应该是替换和和列生成技术的组合(参见别洛夫和Scheithauer [13),例如,对于branch-and-price和列生成技术)。

3.3。最佳的切割和焊接计划之间的关系和最小切割和焊接模式

命题1。每一个可以构造最佳切割和焊接计划使用切割和焊接模式涉及到焊接的数量比使用的股票数量少一个。我们称这些最小切割和焊接模式。

证明。让我们证明这个命题的矛盾,假设存在一个最佳的切割和焊接切割和焊接模式与计划股票(行 在赋值矩阵 )和焊接, 。这种切割和焊接模式可以表示成一个画一个网络的节点和连接边缘,在节点代表股票和边缘代表welds-where可能没有优势,一个边缘,或两个或两个以上的任意两个节点之间的边。如果 ,那么网络是周期性的;让 是股票,形成循环 。相应的指标(列 在赋值矩阵 )需要被发现,以便所有循环矩阵元素 , , , , , , , ,和是一体的。如果中是最小的 , ,…,在相应的焊接矩阵元素 ,然后减去从所有这些元素和添加所有的元素 , ,…, ,和结果等,零元素,换句话说,一个管没有少一个焊缝焊接和切割和焊接模式。修改在领导当然修改 ;如果 ,然后 ;如果 ,然后 ;如果 ,然后这个过程需要尽可能多的迭代需要获得cycle-free图,一棵树或者一片森林。矛盾,既然是一个树的数量涉及焊接比使用的股票数量少一个代表一个最小切割和焊接模式。

这一特点的最优切割和焊接计划起着基本的作用在本文中提出的算法(见部分4所示。1)。

一定要注意,命题1不,焊缝总是必要的。如果我们避免焊缝,使用股票的数量是1,和焊接的数量是0,所以命题1成立。

4所示。计算

通过增加他们的长度,单一或多尺度的切割和焊接股票可能被转化为一个等价的下料,焊接的下料问题可以转化为一个等价的下料问题。如果价格是每焊接,然后价格相当于削减股票的价格是多少切割和焊接股票+ 。多尺度股票(切割和焊接大小)可以生成大量的等效削减股票,由组合 。如果“+”代表了一种股票和‘/’两个股票之间的边界大小,然后,例如,' + + / + / + + +”表示两个股票从第一大小,第二,第三,第四和三个。为切割和焊接股票和切割和焊接股票大小,有 ' / '和迹象 的地方“+”符号。在上面的示例中, , ,和 。

切割和焊接模式不一定是连续的;例如,第一个股票可以切成两段,一个是焊接一段从第四个股票,另一段从第十的股票。高切割和焊接的股票数量和不连续的切割和焊接模式导致实际困难,通过减少切割和焊接的股票数量可能会减少。

所以我们限制来 ,因此绑定的下料焊接的问题;越小 ,较小的等效切削模式的数量。对单一尺寸切割和焊接股票(如本文案例激励),相当于容忍相当大尺寸的下料问题(见部分4所示。1)。然而,一般来说,寻找最优,最小是明显的重要性(见部分4所示。3)。

4.1。一个算法求解有界的下料焊接问题

解决焊接的有界的下料问题,本文提出了一个三步算法——在那个很好的启发式和best-generates最优切割和焊接计划:(1)把焊接到一个有界的下料问题等价的下料问题如下:(一)选择 单一或多尺度有界的切割和焊接的股票在所有可能的途径;例如,5 - 6米切割和焊接的股票和 3产生了有限的切割和焊接两种股票 1(5和6米);3 2 ( 10日, 11, 12米);和四个 3 ( 15日, 16日, 17日, 18米)。(b)增加他们的长度,将有限的切割和焊接股票相当于削减股票。(c)增加他们的价格 焊接的价格,获得相当于下料的价格。(2)相当于解决下料问题(即生成最优等效削减计划)借助开源或商业软件(见部分3所示。1)。(3)每个等效切削模式转换为一个有界的切割和焊接模式(从今以后,模式转换问题,看到部分4所示。2)。

该算法提出了两种可能的困难。

第一个(参见步骤(1)),多尺度有限的切割和焊接股票可以生成替代等效削减股票。例如,如果多尺度有限切割和焊接股票由4 - 6米的股票,然后三个四股 有两个焊缝和两层高高达6米的股票 与一个焊缝产生两种等效切削的股票相同,12米大小,但不恒等的价格。解决等效下料问题(见步骤(2)),良好的实践表明,算法应考虑最便宜的等效削减股票。

第二个(参见步骤(3)),生成一个(最优)有界切割和焊接计划,最优等效削减计划将需要转化为最小的有界切割和焊接模式(见部分4所示。2)。这个难度很简单在大多数情况下,但绝不是在所有。例如,如果需要生产10米管道从单一尺寸,6米切割和焊接的股票,然后五层高高达6米的股票和四个焊接会产生30米相当于削减股票和两个削减会产生三个10米的管道 。之一,然而,由于管道将有两个焊接,而不是最大的一个,这种切割和焊接模式不可行更不用说最小。该算法不仅需要解决(见部分相当于下料问题3所示。1);它也需要解决极端的情况下,没有最小的有界的切割和焊接模式(见部分4所示。2)。

4.2。制定模式转换的问题

让我们考虑等效切削模式之一单一或多尺度股票和单-或多尺度管道 和 生成步骤(2)(见部分4所示。1)。同时,让是股票的大小 , 决策变量的显示段管道的大小从股票 ,和 的二进制变量显示是否是零或积极。

因此,模式转换问题可以制定以下混合整数线性规划:

将等效切削模式转换为最小的有界的切割和焊接模式似乎是微不足道的,并在大多数情况下确实是这样。然而,股票和长管道多尺度所有需要焊接复杂的转换和一个等价的切割模式不可能转换为一个最小的有界的切割和焊接模式。

目标函数的值表明股票的数量和/或股票部分必要的生产管道。每个管子都包含至少一个股票或股票,但不超过两个;因此,目标函数的值的数量是由管道和焊接的数量:(我)因此,如果值是 ,然后有界的切割和焊接模式生成最小(见部分3所示。3)。(2)如果该值小于 ,然后在步骤(2)所使用的软件(见部分4所示。1)是不够的,相当于削减计划是次优的,和有界切割和焊接模式生成是可行的,但不是最小的。在实践中,尽管没有公司声称最优,这个可行的模式可能会被分解成更小的,最小的模式;毕竟,每个管都可以产生最多只有两个股票;树图等部分中讨论的3所示。3noncyclical甚至焊缝数量小于 。由于股票的数量是相同的,但焊接的数量小,这组最小的模式是低于可行模式生成的模式转换的问题。然而,进一步的理论研究已经超出了本文的范围。(3)如果模式转换问题没有可行解,然后在步骤(2)所使用的软件(见部分4所示。1)不一定是不够的。在实践中,尽管没有公司声称最优,一个可行的有界的切割和焊接模式可以通过迭代通过增加股票的数量在模式转换问题来 和 ,等等。在多尺度的情况下股票,增加longest-size股票的数量肯定会导致一个可行的解决方案;在某些情况下,增加shorter-size股票的数量可能会导致一个可行的解决方案。和之前一样,这个可行的模式股票和不足 焊接可能会分解成小,最小的模式。

4.3。最优之间的关系相当于削减计划,优化有界的切割和焊接计划,和最佳的切割和焊接计划

命题2。如果每个等效切削模式最优等效削减计划可以转换为一个最小的有界的切割和焊接模式,那么该算法生成的最优解有界的下料焊接问题。

证明。让我们证明这个命题由矛盾和假设的算法不产生最优解有界下料焊接的问题,虽然每个等效切削模式最优等效削减计划可以转换为一个最小的有界的切割和焊接模式。然后存在有界切割和焊接计划低于有限切割和焊接计划生成的算法。因为所有有界的有界切割和焊接模式切割和焊接计划可以转化为等效切削模式,那么相当于削减计划生成低于最优等效削减计划生成的算法;这是一个矛盾。

命题3。有界的下料问题的最优解焊是焊接的下料问题的最优解也是足够大的。

证明。本文提出的算法求解下料焊接问题依赖于限制可用的切割和焊接股票通过边界下料焊接的问题(见部分4所示。1)。由于每个管可以产生两股最多,有一个上限的 。

然而,这个上限可能仍然太大,实用目的,找到最低的上界是重要的(上界越低,越少的数量相当于削减股票),但是问题甚至对单一尺寸切割和焊接的股票。此外,即使是最低的上限可能会太大,实用的目的。例如,让我们考虑生产从单一尺寸1.001米的管道,1米切割和焊接的股票。如果 1000,那么 1000 = 2000,但是1001年上界显然最低,如果削减成本和很小的忽视。找到最低的上界是可能的,在特殊情况下,但一般的问题,特别是对于多尺度切割和焊接的股票。

4.4。算法运行时间

该算法运行时间的运行时间由相当于下料问题(参见步骤(2),部分4所示。1)和模式转换的运行时间问题(参见步骤(3),部分4所示。1)。

调查等价的下料问题,运行时间的BarCut(2.1版)程序在电脑上运行了一个英特尔双核2.33 GHz处理器,6 GB的随机存取存储器(RAM),和Windows 7操作系统企业。不到9秒,运行时间的情况下促使本文证明可接受(见部分5)。

调查时间运行模式转换问题,GLPK(4.55版)程序是运行在同一台计算机上(见表2,第二列显示了一个复杂、等效切削patterns-generated假想解决等效下料问题的解决需要转化为可行的切割和焊接模式)。如果模式转换问题没有一个最佳的解决方案,事实证明,运行时间短;如果是,事实证明,运行时间很长的时候,明显需要进一步分析。

中等数量的管道(见第二列在表2)和中等数量的单一尺寸,6米切割和焊接的股票(见第三列在表2)生成可行的解决方案(毫)秒(见G1在表列2)。大量可能需要长时间运行,但可行的解决方案通常可以生成(毫)秒,目标函数的实际价值( )表示可行解的存在(见部分4所示。2)。“正常”,目标函数的最优值 (见部分4所示。2);然而,更高效的切割和焊接模式可能生成的,用不到 焊接(见G表模式2, 焊接)。(H表模式2没有最小的解决方案。)

即使有 作为约束条件,在适当的地方(见部分4.1.1),最优解的算法运行时间通常是一种(毫)秒(见G2表列2)。

4.1.1。决策者的偏好和顺序切割和焊接模式

等效切削模式可能转换为替代切割和焊接模式和决策者可能更喜欢一些。偏好可能容易合并通过改变目标函数(见部分4所示。2) ,在哪里代表决策者的得分(优先级)管 ;较低的值显示更高的偏好焊接。自长管道从股票可能会焊接,不仅削减,我们可能一个逻辑属性 最长的管,一个 第二长的管道, ,和一个 最短的管道。没有 约束模式转换的程序运行时间可能长,另一个问题,两步方法更可取。在第一步中,程序可以运行的一些必要(毫)秒来计算最小数量的焊接;到达目标函数的最优值是一个快速的过程;调查所有可能的选择并不是。

在第二步中,目标函数的改变来和 约束或替代约束,在第一步的基础上,添加到生成一个首选模式希望很快G3(见列在表2)。模式J在表2代表一个异常困难的情况下,最小的模式可以相对迅速地生成只有决策者的偏好是无视。

可以理解的是,决策者偏好顺序切割和焊接模式,管道在哪里放置在相关订单和最终的股票是焊接的开始下一个。在树图中讨论部分3所示。3,序列模式对应的路径。

当所有的管道比最短的股票,短序列模式显然是可能的;事实上,每一个排列收益率序列模式。当一些管道超过最短的股票,序列模式并不总是可能的。例如,如果4 - 5,从单一尺寸,管道需要生产9米,6米的股票,然后排列(9、5、4)生成一个连续的模式而排列(4)5、9日不,因为9米管需要两个焊接。另一个例子,没有顺序模式如果三个客房和三个3米管道需要从单一尺寸,层高高达6米的股票,但有一个最小的,不连续模式涉及七股,(请参见图6焊接,五削减4)。(6股,三个焊接,和三个削减将产生三个客房管道和三个1米段。第七股票将减少2米3段,每个焊接到三个1米段生成三个3米的管道)。

生成顺序切割和焊接模式可以通过添加约束 和 的目标函数(见部分4所示。2)。

额外的限制数量的增加数量的平方的股票。如果决策者偏好被忽略,程序生成可行的顺序切割和焊接模式与适度的跑步时间温和Ks和可能大运行时间大Ks G4表(见专栏2)。如果考虑到决策者的偏好,程序生成最小顺序切割和焊接模式与运行时间不同(毫)秒时间(见J表模式2)。

10/24/11。调整顺序切割和焊接模式的模式转换问题,决策者的偏好

单一尺寸股票(6米,如本文的动机,或不同),连续切割和焊接模式也可能由制定一个assignment-like问题,管道的置换,在哪里 代表管的地方在排列和目标函数是任意的,因为生成一个连续的模式就足够了:

的 约束确保第一个的总大小 至少管道排列的 ;换句话说,至少有股票第一 管道。的 约束确保第一个的总大小管道的置换 最多;换句话说,从股票以及剩余的部分 ,额外的股票可以用于生产管道 。这两组约束确保管道 排列最多有一个焊缝和程序生成一个最小顺序切割和焊接模式,尽管它忽视了决策者的偏好(见专栏S1表2)。程序运行时间对所有模式除了温和J,没有一个最小整数解。

决策者的偏好可能会考虑,但模式转换的问题制定作为一个混合整数线性规划更麻烦;如果 是二进制变量指示是否th管道排列是否焊接和 是二进制变量显示是否th管在最初的索引是否焊接,

的 约束确保管在排列焊接 。管的“原始”指数是未知的,但 约束确保管是焊接管是在在排列管排列的焊接。

不幸的是,该算法运行时间是大,超过秒来生成一个可行的解决方案(见G5表列2)。

总之,连续切割和焊接模式可能在简单的情况下,可能产生复杂的,尽管决策者的偏好可能考虑在简单的情况下,而不是复杂的。

5。结果与讨论

本文提出的算法(见部分4所示。1)是应用于匈牙利的情况下制造商的固定灭火系统(见部分4所示。4)。该公司使用单一尺寸,层高高达6米股票(见表1节1说明性的管道尺寸和数量),股票价格 ,和焊接价格通常是低。然而,需求的增加导致焊接时间和机会成本的增加,进而导致焊接增加价格。

软件used-BarCut(2.1版)——适合单一和多尺度的股票。股票的数量每切割和焊接模式是有限的 反映了机会成本,被设置为一个百分比(90%,49%,30%)的 ,假定不变;表3,4,5显示最小切割和焊接模式三个焊接的价格。

当高( ),焊接只有当不可避免的,用于管道超过6米。生成最优等效切割计划,程序运行时间是8.45秒,包括30只股票和焊缝(见表43)。

当适中( ),焊接使用限制性地少。生成最优等效切割计划,程序运行时间是8.47秒,包括29个股票和焊缝(见表64)。

当很低( ),焊接使用更慷慨。生成最优等效切割计划,程序运行时间是8.76秒,包括股票和12焊接(见表275)。因为剩下的部分的总长度是5.034米,较低的焊接价格和进一步研究 ——是无用的。

最优等效削减计划需要转换为最小切割和焊接模式。因为所有这些最优等效削减计划的管道是短于6米或涉及股票,只有两个转换很容易;更复杂的病例分析部分4所示。2和4所示。4。

6。结论

由于其实际光谱相关性在整个工业,下料问题继续研究集中在运筹学和生成复杂的算法解决它。其中一些被翻译成开源或商业项目,迎合不同用户需求和情况下,在不同的价格和不同的条款和条件下。

自从第一次在运筹学研究一维下料问题,增加维数和分散方法,成为自然的扩展。这篇文章是一个只有少数关注的影响而不是焊接在一维下料问题;也是第一个的限制焊缝的数量,符合最佳实践安全要求固定消防系统在建筑业。

本文定义了焊接(见部分下料问题3所示。2),认为它可以转化为一个等价的下料问题多尺度股票(见部分4所示。1),一个可以解决的问题与现有的算法和软件部分3所示。1)。可能第一次的文学,它还定义了模式转换的问题,即切割模式转换为切割和焊接模式为一个混合整数线性规划。

最优解的有界的下料焊接问题进行调查与本文提出的算法和约束检查(见部分4所示。1)。对释放的影响下料焊接问题不能确定(见部分4所示。3);然而,发现该算法生成一个启发式方案至少(见部分4所示。4)。

将等效切削模式转换为切割和焊接模式是本文提出的算法的基础。为连续切割和焊接模式和决策者的偏好,这种模式转换问题(重新)制定为一个混合整数线性规划(见部分10/24/11)。

焊接的下料问题本文研究一维;增加维数是一种自然延伸。然而,两个,三维下料焊接存在的问题更加复杂,需要进一步的研究和算法不同的比本文建议;更有可能的是,大型实例不能解决最优。

数据可用性

使用的数据来支持本研究的结果包括在本文中。

信息披露

初步版本已经在欧洲工业会议上数学和20欧元/ ALIO 2018年国际会议上应用组合优化。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

图雷Agoston承认匈牙利科学院的支持下的合作优势格兰特(KEP-6/2017)。作者非常感谢同事在运筹学和精算科学,科维布达佩斯大学最早的有关意见和建议草案,彼得比罗和艾格尼丝Cseh机制设计研究单位,研究所的经济学、经济和区域研究中心,匈牙利科学院的宝贵的意见和建议在另一个中介草案,和Anamaria m . Cristescu-Martin和Marton Benedek,社论援助与许多草稿。

引用

1. l . v . Kantorovich组织和计划生产的数学方法》第六卷,出版,列宁格勒州立大学,列宁格勒,俄罗斯,1939年。视图:出版商的网站
2. l . v . Kantorovich“组织和计划生产的数学方法,”管理科学》第六卷,没有。4、366 - 422年,1960页。视图:出版商的网站|谷歌学术搜索|MathSciNet
3. p·c·吉尔摩和r·e·Gomory”的线性规划方法下料问题,“运筹学,9卷,不。6,849 - 859年,1961页。视图:出版商的网站|谷歌学术搜索|MathSciNet
4. p·c·吉尔摩和r . e . Gomory“线性规划方法下料problem-part二世”运筹学,11卷,不。6,863 - 888年,1963页。视图:出版商的网站|谷歌学术搜索|MathSciNet
5. p·e·斯威尼和e . r .符咒”,切割和包装问题:分类,application-orientated研究书目,“运筹学学会》杂志上,43卷,不。7,691 - 706年,1992页。视图:出版商的网站|谷歌学术搜索
6. 通用汽车卢德曼,”算法对一维下料问题的解决方案。”电脑与行动研究,13卷,不。6,713 - 719年,1986页。视图:出版商的网站|谷歌学术搜索
7. g·沃斯切尔一如既往,t·高斯启发式整数的一维下料问题:计算研究中,“或频谱,18卷,不。3、131 - 144年,1996页。视图:出版商的网站|谷歌学术搜索
8. m . Gradisar和p . Trkman”相结合的方法,一般一维下料问题的解决方案,“电脑与行动研究,32卷,不。7,1793 - 1807年,2005页。视图:出版商的网站|谷歌学术搜索|MathSciNet
9. h•迪克霍夫头”,一个新的线性规划的方法来削减库存的问题,“行动研究。美国运筹学学会的期刊卷,29号6,1092 - 1104年,1981页。视图:出版商的网站|谷歌学术搜索|MathSciNet
10. g . Scheithauer和j . Terno branchbound算法求解一维下料问题,“验证Mathematicae,23卷,不。2、151 - 167年,1995页。视图:谷歌学术搜索
11. p·h·万斯,董事长c Barnhart e·l·约翰逊和g . l . Nemhauser”解决二进制削减股票问题列生成和和,“计算优化和应用程序,3卷,不。2、111 - 130年,1994页。视图:出版商的网站|谷歌学术搜索|MathSciNet
12. f . Vanderbeck”计算列生成算法的研究为本包装和削减库存的问题,“数学规划,卷86,不。3、565 - 594年,1999页。视图:出版商的网站|谷歌学术搜索|MathSciNet
13. g .别洛夫和g . Scheithauer branch-and-cut-and-price算法对一维下料和二维两级减少,”欧洲运筹学杂志》上,卷171,不。1,第106 - 85页,2006。视图:出版商的网站|谷歌学术搜索|MathSciNet
14. g·沃斯切尔一如既往,h . Haußner和h·舒曼”一种改进的类型学的切割和包装问题,“欧洲运筹学杂志》上,卷183,不。3、1109 - 1130年,2007页。视图:出版商的网站|谷歌学术搜索
15. j·莱文和f . Ducatelle蚁群优化和本地搜索本包装和削减库存的问题,“运筹学学会》杂志上,55卷,不。7,705 - 716年,2004页。视图:出版商的网站|谷歌学术搜索
16. s . a . Araujo a . a . Constantino说道,k.c.波多尔斯基一蹴而就,“进化算法对一维下料问题,“在运筹学国际交易,18卷,不。1,第127 - 115页,2011。视图:出版商的网站|谷歌学术搜索|MathSciNet
17. 崔y、y杨”,可用一维下料问题的启发式吃剩的,”欧洲运筹学杂志》上,卷204,不。2、245 - 250年,2010页。视图:出版商的网站|谷歌学术搜索|MathSciNet
18. b . r . c . h . Cheng Feiring, t . c . e . Cheng”削减股票问题——一项调查,”国际生产经济学杂志》上,36卷,不。3、291 - 305年,1994页。视图:出版商的网站|谷歌学术搜索
19. c . Goulimis“削减股票的最优解的问题,”欧洲运筹学杂志》上,44卷,不。2、197 - 208年,1990页。视图:出版商的网站|谷歌学术搜索
20. e . j . Zak“刮削股票问题对应的下料问题,“在运筹学国际交易,10卷,不。6,637 - 650年,2003页。视图:出版商的网站|谷歌学术搜索|MathSciNet
21. j . Martinovic和g . Scheithauer整数线性规划模型切片库存问题,“欧洲运筹学杂志》上,卷251,不。2、356 - 368年,2016页。视图:出版商的网站|谷歌学术搜索|MathSciNet
22. d . Tanir o . Ugurlu、a .居尔和美国Nuriyev,“一维下料问题可分项目,2016。视图:谷歌学术搜索

版权

版权©2019年克洛Csaba Agoston。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。