没有合适的资源?快使用搜索试试~ 我知道了~
13原始论文EURO Journal on Computational Optimization(2020)8:263https://doi.org/10.1007/s13675-020-00127-8胶合板生产中集成装箱与顺序优化问题海纳·阿克曼1·埃里克·迪塞尔1投稿时间:2019年11月4日/接受时间:2020年6月22日/在线发表时间:2020年7月12日©作者(S)2020摘要集成包装和序列优化问题出现在许多工业应用中。作为这类问题的一个例子,我们考虑在锯木厂生产胶合板(胶合木):木梁必须包装成一系列的压制步骤,受到包装约束的压力机和顺序约束。在本文中,我们提出了一个三阶段的方法来解决这个困难的优化问题:首先,我们确定一个实例的小部分替代包装。其次,我们选择一个最佳的子集,这些包装解决了集覆盖问题。最后,我们应用排序算法,以找到所选序列的最佳顺序。对于层次结构的每一个级别,我们提出了量身定制的算法,分析其性能,并通过全面的数值研究说明了整体方法的有效性关键词生产计划·装箱问题·排程·启发式数学科目分类90B30· 90B90· 90C59· 90B351引言切割和包装问题出现在许多工业应用中,特别是在生产和物流中。这样的问题可以以各种方式来表征,例如通过它们的维度(一维、二维或三维)、通过物品的形状矩形、圆形或不规则形),受包装结构的约束BErik DiesselErik.itwm.fraunhofer.deHeiner Ackermannheiner. itwm.fraunhofer.de1Fraunhofer ITWM,Institute for Industrial Mathematics,Fraunhofer Platz 1,67663Kaiserenstern,Germany13264阿克曼和迪塞尔以及允许的模式(例如,切纸机切割,正交切割,...)和分类的类型(例如,背包、装箱或切割原料)。关于切割和包装问题的全面介绍,我们请读者参阅Dyckhoff(1990)。然而,特别是在生产中,还需要考虑连续包装处理之间的设置时间。一般来说,这种测序问题可以被描述为具有序列依赖性设置时间的调度问题(Allahverdi2015)。同时考虑到这两个方面,集成包装和序列优化问题。在本文中,我们介绍了一个这样的问题,在生产胶合板(集成材)在锯木厂:不同的高度和长度的木梁应包装成一个顺序的压制步骤受到一定的包装约束的压力机和后续压制步骤的要求。装箱问题可以描述为一个二维装箱问题,具有精确的截断切割。目标是最大限度地减少填充整个印刷机所需的材料(废物)量。序列优化问题要求为一个客户按顺序产生目标是最小化后续压制步骤的高度变化的数量,因为每个高度变化需要一些设置时间。在本文中,我们描述了这个问题的三阶段算法。这一办法可归纳如下:1. 使用从最大差异法(Karmarkar and Karp1983)推导出的包装化学方法,确定多达三个订单的各种组合的压制步骤的替代顺序2. 选择一些序列,使每个订单都包含在一个序列中这可以使用集合覆盖方法来实现。3. 使用调度算法计算所选序列的最优顺序我们的动机和理由,我们的方法的结构性见解的问题,并得出结论,一个全面的数值研究。我们的研究表明,该算法可以快速计算出真实世界实例的有效生产计划。1.1 胶合板简介胶合板(胶合木)是一种工程木材产品制成的薄板条在锯木厂。它用于需要高质量的长而厚的木梁(Serrano2003),例如,在屋顶建设中。这样的梁不能从一个单一的树干锯下来,然而,组合薄板条允许规避这种影响。此外,它还可以大幅提高锯木厂的材料效率。胶合板是由标准厚度的薄板条堆叠和胶合而成。通过改变板条的数量和它们的长度,可以产生几乎所有尺寸的梁请注意,板条的宽度决定了梁的宽度。板条从树干上锯下,干燥并最终检查是否有缺陷。通过精细连接板条,可以生产几乎任意长度的板条。之后,板条堆叠与胶水之间和压制。压机完美地对齐板条并触发胶水硬化通过不在两个板条之间插入胶水,一个层次化的方法来解决一个集成的包装26513以在一个压制步骤中产生两个(或甚至更多个)梁然而,印刷机具有以下包装限制:1. 在一个压制步骤中同时处理的所有梁必须具有相同的尺寸,即,相同的宽度和长度。2. 压制步骤的高度,即,所有横梁的总高度,不得低于(超过)最小(最大)压制高度。3. 梁的长度不得低于(超过)最小(最大)压制长度。4. 当两个连续的压制步骤具有不同的高度时,需要一些设置时间这就是为什么人们搜索具有很少高度变化的按压步骤序列,因为高度变化后的设置时间主导整个按压所需的时间为了减少生产工作量,集成材生产是分批进行的。在每个批次中,仅处理相同宽度的板条。然而,注意,在一批中,可以生产不同长度和高度的集成材。这些约束条件尚未引起非常复杂的优化问题。困难来自于客户通常订购不同长度的多个梁的事实。为此,锯木厂可以生产几个标准长度的库存,并根据需求切割所需的长度。然而,事实证明,这将产生大量的废物。因此,更有意义的做法是依靠按订单生产的策略,直接生产所需的长度。这样做会产生各种问题的最佳批量大小,最佳供应的板条等,但在本文中,我们专注于计算最佳序列的压制步骤。也就是说,我们假设已经选择了一组可行的订单(所有订单都要求相同宽度的梁),并且有足够数量的这种宽度的板条可用。接下来的任务是找到一系列紧迫的步骤,这些步骤受到上述限制以及下文所述的其他限制和机会的约束1. 多个客户下订单。每个订单都要求生产具有相同高度但不同长度的梁这就是为什么同一个客户可能会下多个不同高度的订单。2. 在一个批次中,属于一个订单的所有梁必须按顺序生产属于一个指令的波束不应被属于其他指令的波束中断同样,属于一个客户的所有订单也应该按顺序生产,也就是说,在这之间不处理来自其他客户的订单这是因为随后的包装和装载能力有限。3. 由于最小长度约束,将多个订单长度组合成一个生产长度并随后将其切割成订单长度是可能的,并且通常是必需的。4. 为了不违反压力机的包装限制,可以用填充材料延长板条这种材料将被切断后,被视为废物,因为它往往是太短,进一步使用。这就是为什么人们寻找填充材料很少的压制步骤。压制步骤的实例描绘于图1B中1.一、266阿克曼和迪塞尔13·+·=| |M|| ||:= .∈∈M∈ ∈M=∈={个充填材料图 1两个订单的可行压制步骤:高度为80的订单,长度为3000、4000和6000的各两件;高度为160的订单,长度为6000、7000和8000的各一件。总计,填充材料160 9000 80 4000 使用了176万个单位如上所述,有两个目标需要考虑。首先,尽量减少填充材料(废物)的数量,以填满整个印刷机。其次,最小化一批内连续压制步骤之间的高度变化的数量一般来说,两个目标会产生双目标优化问题。然而,下面我们提出了一种方法,找到了同时对两个目标有效的紧迫步骤序列。1.2 问题描述为了描述我们的问题,下面的符号将是有用的。多集是元素的集合,其中元素可以出现多次。我们用X和所有元素的和来表示多重集X的元素数,包含的数字(也用多重数计数)为Xx X x。我们假设多集总是被编码为列表(即,不使用高多重性编码我们用符号表示(S)对于给定集合S上的所有多重集的集合。 为对于条件C的指示函数,我们使用符号1(C)。对于我们的压力参数,我们使用图1所示的以下符号第二章:– 最小挤压长度用4分钟表示,– 最大按压长度增加4max,– 最小压制高度由hmin给出– 最大压下高度为hmax。我们现在给出上述胶合木生产问题的正式定义在下文中,我们使用术语“件”来表示客户订购的木梁定义1(集成材生产问题)输入:集成材生产问题的输入是一组订单,这些订单按相应的客户分组。阶(h,L)是一对高度为h的N和多重集L(N)件长度。在输入中,L是一个没有多重性的列表。输出和包装类型:输出由一系列压制步骤P1,...,包含所有有序块的Pk,其中k可以任意选择。压制步骤由P(h1,L1),.表示,(h m,L m),并且由一组层组成,由一对(h i,L i)描述,i1、......、m在哪里h iN是高度, Li(N)是一个多段长度集。在每一层中,只能包含来自一个订单的件(因此,每一层具有由对应订单的高度给定的统一高度)。160× 6000160× 9000160× 8000160× 700080× 400080× 400080× 300080× 400080× 600080× 600080× 3000一个层次化的方法来解决一个集成的包装26713h,L)∈.图2压制参数及其对压制步骤的影响的图示。如果订购的零件未达到要求的最小长度4min或最小高度hmin,则需要添加填充材料。压制步骤的总长度不能超过最大长度4max,并且高度需要低于最大高度hmax顺序约束:我们对顺序有以下要求:属于客户的所有订单必须按顺序放置。订单的所有部分也必须按顺序放置。包装约束:我们表示为4(P):=max {4min,(maxP||L||}压制步骤P的总长度,通过h总计(P):=h(h, L)∈ P压制步骤的总高度,h(P):=max{hmin−htotal, 0}达到最小高度Hmin所需的附加高度。每个压制步骤P应满足:– 最大高度约束h( P)≤hmax,– 最大长度约束4(P)≤4max.目标:应尽量减少以下两个数量高度达到所需长度的填充材料Lminlmax填充材料达到最低限度HMaxhmin268阿克曼和迪塞尔13KK.≥填充材料:填充材料的总量由下式给出f(P1,.,P k):=. .h(4(P i)−||L||)+的i =1(h,L)∈Pi. 4(P i)h(Pi).i=1填充至最大长度我在灯光下填满了我们希望最大限度地减少填充材料的总量,以减少浪费。高度变化:连续按压步骤之间的高度变化次数由下式给出:k−1c(P1,., P k):= 1(h总(P i)/= h总(P i+1))。i=1我们希望最大限度地减少高度变化的数量,以保持总生产时间较低。我们需要对压力参数进行以下假设,这确保我们总是可以获得总长度介于最小和最大长度之间的可行填充,并且高度也是如此它在实践中得到了充分的体现。假设1(压力机参数的– 最大按压长度至少是最小按压长度的两倍:4max2 4min。– 最大压制高度至少为最小压制高度的两倍:hmax≥2hmin。1.2.1 模型讨论定义1中的两个目标代表优化生产过程时的相关目标。填充材料与废料量相对应,由于所需的设置,高度变化的数量导致生产时间增加在上述定义中建模的包装类型对应于具有两阶段精确截断切割和可变容器尺寸的二维包装问题。这种包装类型是由于印刷机的特点和相应的处理:件需要以自动过程的常规方式切割对这种类型的切割的限制使得作为层的建模比使用二维坐标更简单。高度变化可以解释为序列相关的设置时间。顺序约束来自于物流方面的原因:当订单的所有部分在冲压步骤中按顺序出现时,它们可以直接打包在一起。同样,属于一个客户的所有订单可以立即打包在一起。一个层次化的方法来解决一个集成的包装269131.3 我们的结果所描述的基本方法遵循Ackermann和Dinges(2017)的方法然而,在本文中,我们为每个步骤开发了新的算法,并为它们的效率提供了通过建立连接到其他著名的组合优化问题和技术,我们系统地分析这些算法。我们将问题分为三个独立的步骤:1. 为单个订单和最多三个订单的组合找到一个包装到冲压步骤中。这些组合可以是重叠的,即,订单可以包含在多个组合中。包装单订单讨论节。二、使用理论上的考虑(定理1),我们可以减少包装问题到一个更简单的划分问题,我们解决的最大差异的方法。包装的组合中讨论了节。3 .第三章。2. 使用前一步中找到的填充,计算具有最小总填充材料的阶的集合覆盖,如3.1节所讨论的。为此,可以使用动态规划。3. 找到一个排列的包装(受公正的顺序约束),最大限度地减少发生的高度变化的数量我们制定这作为一个序列依赖的设置时间的问题一个有效的精确算法找到这个置换的基础上欧拉扩展和动态规划节。四、这种分解方法的优点是可以为每一步独立地选择算法,这大大增加了算法的灵活性。一般来说,每个步骤都是NP-难解决的;因此,我们专注于足够快但在实践中产生良好结果的算法阴宗。5,我们总结了我们的算法,并给出了真实世界输入的数值结果。我们表明,我们的方法能够在几分钟内计算出多个月的生产计划计算的解决方案实现了少量的填充材料和少量的高度变化。1.4 相关工作对于我们的问题,Ackermann和Dinges(2017)开发了一种基于各种算法的算法,该算法成功地与锯木厂的企业资源规划系统结合使用尽管它只是一个近似算法,但解决方案的质量超过了人类专家。虽然使用了相同的框架,但我们显著改进了每个步骤中使用的算法,并为它们的效率补充了理论推理Diessel(2018)的学士论文对所用算法和扩展的数值结果进行了一些额外的理论分析。Leoff(2016)开发了一种基于混合整数规划的精确算法,该算法具有专门设计的特别强调的是,放宽了属于一个顺序的所有项目必须连续出现的限制,例如,允许多个未结订单该算法270阿克曼和迪塞尔13然而,其运行时间非常长,对于几乎所有实际输入都超过一小时。集成包装和序列优化问题出现在其他行业,其中也必须最大限度地减少材料浪费和生产时间。Wuttke和Heese(2018)解决了纺织行业中的二维切割问题。他们讨论了一个混合整数规划公式和算法。Song(2006)用启发式方法解决了一家塑料公司遇到的类似问题他们的算法考虑了多个标准:截止日期,材料浪费和处理时间。Zhi-Long和Guruprasad(2009)考虑了此类问题的另一个例子。尽管表面上的问题的相似性,这些算法不能适用于我们的问题。原因在于,所采用的算法是针对非常具体的约束量身定制的,这些约束在很大程度上取决于所考虑的应用。文献中考虑了大量不同的填充问题,参见Dyckhoff(1990)和Wäscher等人。2007年,为总纲。我们的问题与二维装箱问题有关(参见Lodi等人(2002)和Lodi等人(2002)的调查)。与我们的问题不同的是,在装箱问题中,箱子的数量被最小化,而不是箱子中的剩余容量。此外,在我们的问题中,bin的维度不是固定的,而是在某些约束条件下可变的。二维带包装问题也不同于我们的问题,因为有一个上限的最大尺寸的一因此,无法应用条带包装问题的有效近似算法,例如Kenyon和Réemila(2000我们可以把我们的装箱问题看作是Pisinger和Sigurd(2005)分析的二维可变尺寸装箱问题的一个特例,其中有多个箱维可用,每个箱维都有自己的成本。提出了一个整数线性规划模型和一个基于分支价格的算法。然而,他们的算法的运行时间(在具有100个项目的实例上长达一个小时)对于我们的应用程序来说太长了。由于我们还需要找到生成的包装的最佳序列,因此我们面临着一个集成的包装和序列优化问题。Allahverdi(2015)给出了相应类型的具有序列依赖设置时间的调度问题的调查作者在另一篇论文中分析了这个特殊的调度问题(Diessel和Ackermann2019)。2 包装单订单在本节中,我们先处理单个订单的包装情况,然后在后面的章节中考虑可能由不同客户的多个订单组成的完整计划由于属于同一顺序的工件可以任意排列,我们不必处理调度问题,这将在第二节后面讨论四、此外,所有部件的高度都是相同的。一个层次化的方法来解决一个集成的包装27113∈∈联系我们||||} ∈44Maxi = 1 L∈Pii=12.1 问题描述当考虑包装单个订单的特殊情况时,定义1的完整胶合板生产问题简化为以下单个订单的压制包装问题。定义1的顺序约束在只考虑单个顺序时总是满足的。我们能够简化许多约束,因为订单的所有部分共享相同的高度h。通过根据它们的高度将压制步骤分组,高度变化的数量可以减少到压制步骤的发生高度的数量减一。由于所有工件的高度相同,压制步骤的高度与层数成比例。定义2(单个订单的压装问题输入:高度hN和长度的多组L,冲压参数hmin,hmax,4分钟,最多4分钟输出:一系列压制步骤P1,...,其中每个压制步骤是层的多集合。层也是长度的多重集合。约束:对于每个压制步骤Pi,1≤i≤k,最大高度约束|P i|·h ≤ hmax必须持有。对于所有层LPi,总长度必须至多为最大长度,即,:的情况。||L|| ≤ 4最大值标准:应尽量减少以下两个数量填充材料:对于1ik,设4imax 4min,max LPiL是第i个压制步骤的总长度。填充材料的总量由下式给出K Kf(P1,., P k):= h。. (4i− ||L||)+。4i·max {hmin− h·|P i|,0}。c填充至最大长度Ic填充至0.05m的内部高度一(1)高度变化:高度变化的数量取决于在按下步骤中使用的不同数量的层的数量,c(P1,.,P k):=|{|P i|:1 ≤i≤k}|-1。证明了在P/=NP的条件下,在压力机参数hmin≤3.4min+4maxhmin≤hmax的条件下,不存在多项式时间算法它总是返回一个近似的压力包装问题(与这些272阿克曼和迪塞尔13·∈{1,.,=H=≤ ||L|| ≤ 4对于所有1≤i≤i=1≤h·ai≤h对于所有i∈ {1,..., k}I1最多两个不同的≤h·ai≤h对于所有1≤i≤kI1具有附加的特性,minMaxK固定压力参数),其中添加4min+44max hmin(Diessel(2018),Theorem 2.6).2.2 算法方法我们从理论推导我们的分析师使用的方法开始。找到好的冲压步骤的算法是基于以下定理,只要我们找到一个总长度近似相等的层的分区,就可以保证一个体面的解决方案定理1(将层组合成压制步骤)假设每件的高度为h,并且满足假设1。假设以下两个条件成立:(a) 令长度为L= {a1,...,an}被划分为L=stecm1Mmin我Max李仁d(L 1,…,Lm):=iMax∈{1,.,M个文件夹||L i||−iminm}||L i||是层总和的最大差(b) 另外,y,让m∈N和数字r为1, . ,ak∈Nbe,n∈h。Kai= m值出现在1,...,肺炎克雷然后,存在一系列压制步骤P1,..., P k的阶数为(L,h),使得填充材料的总量由下式限定:f(P1,.,P(k)≤h·.,hmax,−1·d(L1,...,L m)≤hmax·d(L1,..., L m)以及高度变化的数量c(P1,...,Pk)最多为1。证明对层L1,...,L m根据它们的总和||L(i)||以递增顺序,得到置换L(1),.,L(m),||L(1)|| ≤ ··· ≤ ||长(米)||.根据定义,最大差,则有d(L1,...,L m)=||长(米)||− ||L(1)||.如果序列是1, . ,ak∈N,其中.kai=m,最多出现2个不同的值我们现在将层按其总和的顺序插入到压制步骤P1 = {L(1),., L(a1)},P2= {L(a1+1),.,L(a1+a2)},...PK = {L(a1+···+ak−1+1),L(a1+···+ak)},同样如图1所示,3 .第三章。层L,..., L使得4m和let和hminMaxHa 1,.,一一个层次化的方法来解决一个集成的包装27313长(米)···≤ ||||=||||≤≤||||≤≤ ≤≤·≤ ≤ ≤-是的a我:=||||-是的..L(2)L(1)L(a1+2)L(a1+1)L(a1+···+ak− 1+2)L(a1+···+ak− 1+1)层的堆积.−−−−−−−−−−−→..···L(a1+a2)L(a1+···+ak−1+ak)“我的天,层``P1x的第二章˛¸x `Pkxx图3 层L(1)、L(2)、. L(m),按其总长度以递增顺序排序,即,L(1)L(m),填充到压制步骤P1,.,PK。数字ai,i1,...,k表示压制步骤Pi因为hminh ai hmax对于所有1i k都成立,所以压制步骤满足对高度的约束,并且因为4minLi所有1个最多保持4个也是对长度的约束。如在每个压制步骤a1,...,ak最多出现2个不同的值,高度变化的数量由c(P1,.,P k)=|{|P i|:1 ≤i≤k}| − 1 =|{a i:1 ≤i≤k}| − 1 ≤ 2 − 1 = 1对于填充材料的量,我们定义为:f(P1, . ,Pk)=h·k .(4i−||)||)⎞K你好,i=1A∈Pi其中4imax A∈PiA是压制步骤Pi中的最大总长度。通过对层L(1),.,L(m)和压制步骤P1,., P k,我们得到||L(1)|| ≤ ||L (2)|| ≤ · · · ≤ ||长(米)||4 i=||L(a1+···+ai)||.因此,对于所有1≤i≤n,我们有:.(4i−||一||)≤。||L(a1+···+ai)|| − ||L(a1+···+ai−1+j)||=A∈ PiJ1≤(ai − 1)·。||−||L(a 1 +···+ a i −1 + 1)||-是的||Σ.将其插入到整个总和中会导致填充材料的期望边界Kf(P 1,.,Pk)= h·.(4i−||)||)⎞⎠≤h·i=1A∈PiK(ai−1)·i=1. ||−|| L(a 1 +···+ a i −1 + 1)||ΣΣ||ΣΣL(a1)压制步骤.L(1)L(2)274阿克曼和迪塞尔13≤h·--然后|||| ≤···≤||||伸缩和≤h·i max(ai1)∈{1,.,k}. ||− ||L(1)||Σ ||Σai·h≤hmax.,hmax,H-1美元·d(L1,..., L m)。第二个不等式直接由h.,hmax,− 1 ≤ h·。hmax− 1 ≤ hmax.H Hп可以证明,上述定理的界是紧的。我们从定理1中得出结论,将工件长度集合划分为层可以用于获得压制步骤的序列。充填材料随层总和的最大差值成因此,找到最大差异体积小的分区就足够了为了将定理1证明中的构造转化为算法,我们需要解决以下两个子问题来满足定理的条件:– 为了满足条件(a),我们需要找到一个将碎片划分成层的分区,使得它们 的长 度 不 会相 差 太 多。 这 是 在下 面 的 节。 2.3、 利用 最 大 差分 法(LDM)。– 为了实现条件(b),必须计算要放入每个压制步骤的可行层数第2.4节讨论了这个问题。然后,我们可以将稍后描述的算法2与定理1的构造性证明组合,以遵循用于填充单个订单的算法1。这个想法是尝试不同大小的分区,并将产生的层按其总长度的递减顺序打包到压制步骤中。通过这种方式,我们可以确保一个冲压步骤中的长度差异尽可能小。算法1:单个订单打包输入:一个订单,由一组正的工件长度S和高度输出:将订单的所有项目打包成可行的冲压步骤对于每个可能的总层数mdo运行LDM(算法2)以将S划分成m个子集L1,., L m如果层总和||L1||,..., ||L m||不超过最大长度4max包装层L(1),.,L(m)在顺序L(1)使用定理1的构造,在每个压制步骤中的层数由算法3计算,储存相应的包装结束结束一个层次化的方法来解决一个集成的包装27513退回发现的填充材料最少的包装算法1的运行时间为O(|S|3个对数|S|)在输入S上。276阿克曼和迪塞尔13∈{1,.,M==||||||||[客户端]HH2.3 包装成层我们现在描述一种找到定理1的条件(a)的好解的方法。这个子问题可以形式化为一个数划分问题。定义3(数划分问题)给定一个正数的多集S和多个binm∈N,找到最小化最大值的分区stecmLi=S,差异d(L 1,…,Lm):=iMax∈{1,.,Mi=1个文件夹||L i||−iminm}||L i||.如果适当地选择数量划分问题中的箱的数量m,则平均值||S||每个子集L1中的和 ,...,L m 大约在4min和4max之间。因此,最大差异的小值d(L1,…,L m)确保所有和都在4min,4max的区间内。因此,长度约束也可以通过专注于数字划分问题来处理由于数划分问题可以看作是经典划分问题(Karp 1972)的一种特殊情况,通过设置m 2并将d的最小值与0进行比较,因此数划分问题是NP-困难的。因此,我们主要研究多项式时间近似算法.因为我们稍后将多次解决数划分问题,具有不同数量的集合m,所以算法必须非常快。 Schreiber和Korf(2014)最近的精确算法以及Schreiber和Korf(2013)针对该问题的其他最先进算法太慢,对于具有n的中型问题,超过一秒的运行时间。 50个项目。解质量的一个小的下降是可以接受的,因为我们只把它作为装箱问题的一个子问题算法2是由Karmarkar和Karp(1983)首先给出的。他们的算法是随机的,以方便性能分析。我们提出了一个确定性的版本的算法,可以更有效地实现,以下介绍的martels(2007)。该算法被称为最大差异法(LDM),因为在每一步中,最大和最小元素之间具有最大差异的两个子集被组合。在这里,一个集合的最大元素被添加到另一个集合的最小元素,第二大元素添加到第二小元素,依此类推。通过这种方式,实现了将多集划分为具有近似相等和的m当将P实现为优先级队列数据结构(例如二进制堆)时,使用d值作为键,LDM的运行时间为O(|S|(日志|S| +m log m))。2.4 计算压制步骤的层数我们现在解决满足定理1的条件(b)的问题:找到放入压制步骤的最佳层数。在一个压制步骤中的层的数量从上面由hmax限定。层数应优选地为至少hmin,使得最小高度为不需要填充材料一个层次化的方法来解决一个集成的包装27713C ˛我HHMax.·HhhH算法2:最大差分法(LDM)输入:一个正数的多集和一个数m∈N输出:分区stecmLi=SP←空列表对于a∈S,i=1添加多重集{{a },{b},.. 、.、m到P的基数m−1次端当P包含一个以上的集合时,设A,Ar是P中具有最大极大差从P中去掉A和Ar,加上它们的组合C,定义如下:Let{B1, . . . ,Bm}=A且{B1r, . ,Bmr}=Ar,||≤ · · ·≤||≤···≤||Bm||和||≤·· ·≤||正在增加。||Bmr||areincreasing.Rrr端则它们的组合为:C= {B1<$Bm,B2<$Bm−1,.,{\fn黑体\fs19\bord1\shad1\1cHD8AFAF\4cHC08000\b0}返回P中最后一个剩余的多重集为了达到少量的高度变化,仅应使用少量不同数量的层理想情况下,只使用一个层数,但这可能是不可能的,例如当片的数量是素数时。然而,在大多数情况下,我们能够找到只有两种不同层数的解决方案。我们可以给出这个问题的以下数论版本定义4(层划分问题)对于给定的层数m,找到一个划分m=s1+ ··· +s k分为数s1,.,s k∈N,使得集合{s1,., s k}最多由两个不同的值组成,另外要求hmin≤si≤hmax 对于i= 1,...,K.一个计算这种划分的数量的公式(不要求s是Tani和Bouroubi(2011)给出了一个特定的范围)我们现在将描述解决层划分问题的算法。该算法以这样一种方式进行,即只有一个层数的理想解决方案优于两个不同层数的解决方案,而这又优于需要填充材料的解决方案然而,在所有情况下,该算法确保仅使用两个不同数量的层,并且仅需要一个压制步骤的填充材料算法3的运行时间以O mh2为界。·最小在假设hmax≥ 2 hmin的条件下,可以证明,在m为偶数的情况下,对于所有i= 1,...,k,这样即h1,..., h k只包含两个不同的值,参见Diessel(2018,Lemma 2.7)。这也意味着只需要增加一层填充材料,因为我们可以通过增加一层来使奇数层变为偶数。算法总是会找到这样的解决方案。实际上,对于奇数m,我们几乎总是可以找到一个没有填充材料的解,只要m不太小。因此,填充材料278阿克曼和迪塞尔13HH一Hmodb算法3:寻找最佳层数输入:m个层,每个层具有高度h,参数hmin,hmax输出:层数h1,...,hk,使得h1+ ··· +hk=m,h1≤hmax,并且优选地hi≥hmin 对于所有i= 1,...,k和h 1中不同值的数量,...,hk很小对于h∈ {“h min,.,hmax]}doH H如果h整除m,则returnh1= ··· =hm/ h=h结束结束对于a∈ {“h min,...,hmax]}do为hhminhb ∈ {”h、...、a}do对于x∈ {1,..., m]} do如果b整除m-x·a,则returnh1=···=hx=a,hx+1=···=h(m-x·a)/ b=b存储最大填充数。“h min −((m-x· a)mod b),0以及a,b,x结束结束结束结束用最小的填充数选择a,b和xreturnh1= ··· =hx=a,hx+1= ··· =h(m-x·a)/ b]=b,h(m-x·a)/ b]+1=(m-x·a)这在大多数情况下是可以避免的否则,最好在待填充的压制步骤中选择具有最小长度的3 多个订单本节的目标是将单个订单打包的算法扩展到订单组合。在某些情况下,如果没有重要的填充材料,订单不能单独包装由于胶合板生产问题的定义1中的包装约束,当订单没有足够的总尺寸来达到最小长度或最小高度时,就会发生这种情况通过将两个或多个订单的组合包装在一起,我们也可以在这种情况下实现更少的填充材料。由于并不直接清楚应合并哪些订单,我们会产生多个组合,并使用SetCover方法找出一组组合,使每个订单只生产一次,并尽量减少总填充材料3.1节中描述了用于计算所发现的组合的最优子集的集合覆盖方法。下面的小节显示了如何压制步骤的组合,两个(节。3.2),分别,三(节。3.3)订单可以形成。其他一个层次化的方法来解决一个集成的包装27913SA.一:A→· |一|· ||3.1 集合覆盖我们对寻找组合子集的问题进行建模,使得每个订单只生产一次,并且总填充材料最小化为加权精确集覆盖问题。要求找到一个确切的封面,确保订单不会产生多次。定义5(加权精确集覆盖问题)输入:有限论域U上具有权函数的非空集族wR+输出:覆盖全域的不相交集合的一个子类,stecS∈SS=U,使得覆盖S∈Sw(S)的权最小。在我们的应用中,集合是订单的组合,重量是由算法4和5计算的包装的相应填充材料。此外,对于每个订单,我们使用算法1单独计算其包装。然后,我们还在Set Cover实例中包含相应的单例集这确保了总是存在至少一个精确覆盖,因为我们可以只选择这些单例集作为覆盖。然而,这可能远非最佳。通过使用标准的动态规划方法,加权精确集覆盖问题可以在O(2 |U|U)。但在考虑集合覆盖之前,我们需要生成具有权重的集合通过计算所有可能的组合良好的填料,以评估其相应的填料。我们将自己限制在最多三个订单的组合组合中的阶数越高,可能组合的数量就会增加一个很大的系数,从而使它们的计算在实践中变得不可行。此外,由于在实践中高度h通常至少是最大高度hmax的五分之一,因此在一个冲压步骤中出现三个以上的订单的情况很少发生我们现在讨论如何获得两个或三个订单的组合的良好压制步骤3.2 两个命令的组合我们试图找到一种图1所示形式的4中的一个压制步骤包含来自两个不同订单的工件。注意,两个订单的组合的所有允许的包装都具有这样的形式,因为来自一个订单的所有件必须连续出现。通过使用两个订单的这种组合,与单独包装每个订单相比,可以减少填充材料:然后更容易实现找到每个总高度在最小和最大高度范围内的包装的目标在下面的算法4中,计算两个阶的这种组合。我们不直接使用算法1打包单个订单。相反,我们使用定理1和LDM的思想来生成全新的包装。该算法首先计算第一阶和第二阶的片段到层中的多个分区对于每个找到的分区,计算填充材料以将除了指定数量的剩余层之外的所有层填充到压制步骤中还有,280阿克曼和迪塞尔1311.,,,,,,K1H1H2K1算法4:两个订单的打包组合输入:阶数(S1,h1)和(S2,h2),具有长度为S1,S2和高度为h1,h2的输出:一系列压制步骤P(1),.,P(1)对于(S1,h1)和一系列压制步骤1KP(2),...,P(2)对于(S2,h2)使得P(1)和P(2)可以合并,即.e.1krk1hmin≤h1·|P(1)|+h2·|P(2)|≤ hmax对于(S1,h1)的每一个可能的层数m1,设L1(m1)是由LDM(Alg. (二)对于s∈ {1,...,hmax]}do设f小(mH1,s)是用于包装除最小s层外的所有层的总填充材料,L1(m1),例如使用定理1设flarge(m1,s)为填充除最大s层外的所有层的总填充材料,L1( m1)结束结束类似地计算(S2,h2)的L2,fsmall和flarge2 2对于(S1,h1)的每一可能层数m1和(S2,h2)的每一可能层数m2,对于s1∈ 1,., hmax和s2∈ 1,..., hmaxdo计算fsmall(m1,s1),fsmall(m2,s2)和所需填充材料的总和,1 2将L1(m1)的最小s1层和L2(m2)的最小s2层一起打包成压合步骤(这是小-小组合的方式)对于其他三种可能的方式小-大、大-小和大-大如果一个可行的计算填充物比先前的最佳填充物具有更小的填充材料,然后存储相应的值m1,m2,s1,s2以及该包装的组合方式结束结束端返回已存储的m1,m2,s1,s2和组合方式的算法5:三个订单的打包组合输入:订单(S1,h1)和(S2,h2),具有长度S1,S2,S3和高度h1,h2,h3,其中(S3,h3)小到足以被填充到一个压制步骤中输出:一系列压制步骤P(1),.,P(1)对于(S1,h1)和一系列压制步骤1KP(2),...,P(2)用于(S2,h2)和一个压制步骤P(3)用于(S3,h3),使得P(1),P(2)1krk1和P(3)可以组合,即。e. hmin≤h1·|P(1)|+h2·|P(2)|+h3·|P(3)|≤ hmax如算法4中那样计算(S1,h1)和(S2,h2)的组合的填充,但是没有限制对的最小高度的的组合按压step用算法1计算(S3,h3)对于(S1,h1)和(S2,h2)的每一个组合填充,将(S3,h3)的适当层数的填料插入(S1,h1)和(S2,h2)的组合压制步骤中, 计算 的 所得 总 充填 如果包装可行端用最小的填充材料返回找到的包装一个层次化的方法来解决一个集成的包装28113H1H2H1H2二阶···一阶c`ombindedpumpingstepsxp···图4两种订单三阶二阶···一阶c`ombindedpumpingstepsxp···图5三种顺序试图将第一和第二顺序的剩余层的多个组合包装到一个压制步骤中。最后,返回填充材料总量最小的包装算法4的运行时间为O.|3 g/L ( |S1| ) + 的 |S1|2 ·log g ( |S1| ) · h max+|S2|3 g/L ( |S2| ) + 的 |S2|2· log(|S2|)· hmax|)·hmaxh1h2+|S1|·|S2|·hmax·hmax·. hmax+ hmax3.3 三个命令如果一个订单特别小,我们可以试着把它放在两个不同的订单之间,通过形成一个压制步骤,由小订单的所有件和其他两个订单的部分组成,如图所示五、由于单独包装如此小的订单不会达到最低高度,因此通过使用这些组合可以显著减少填充材料。在图5中,小阶是第三阶。请注意,只有当其中一个订单的总材料足够小以在一个单一的压制步骤中包装时,才可能在一个压制步骤中存在三个订单。另一种可能的方法是通过使用两个组合的压制步骤来组合三个订单,如图所示六、然而,我们不计算这样的组合,因为这样做会引起很大的运行时间。282阿克曼和迪塞尔13H1H2H1H2H1H2···图6组合三个订单······用于三个订单的包装组合的算法5将小的第三订单与两个大订单组合。 我们的想法是首先找到两个大订单的包装,使用算法4。然后将这两个顺序的剩余层与第三顺序
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++标准程序库:权威指南
- Java解惑:奇数判断误区与改进方法
- C++编程必读:20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程:从入门到精通
- Spring3.0权威指南:JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略:从环境配置到索引创建
- 内存虚拟硬盘技术:提升电脑速度的秘密武器
- Java操作数据库:保存与显示图片到数据库及页面
- ISO14001:2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发:触发器与控制器重定向技术详解
- FPGA开发实战指南:创新设计与进阶技巧
- ShopExV4.8二次开发入门:解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功