基于多阶排样方式的矩形件二维板材下料算法

针对二维剪切下料的特点,提出一种基于多阶排样方式的优化算法。递归构造多阶排样方式,称若干行若干列同种矩形件按照相同方向排列在一起形成的排样方式为0阶排样方式,n(n为正整数)阶排样方式由两个n-1阶排样方式沿着水平方向或竖直方向拼合而成。设计多阶排样方式的递归生成算法,按照阶数从小到大顺序生成多阶排样方式。将列生成算法与多阶排样方式生成算法相结合得到下料方案,按照板材使用张数最少原则确定下料方案中每个排样方式的使用次数。将这里排样方式分别与文献中的匀质条带三块排样方式、双排多段排样方式、简单块占角排样方式和递归四块排样方式进行对比,实验计算结果表明,多阶排样方式的排样价值高于以上4种排样方式。进一步地,将该下料算法与文献下料算法进行对比,实验结果表明该下料算法可提高板材利用率。     

有限制二维板材启发式下料算法研究

橱柜及板式家具生产都涉及二维板材下料,材料利用率的最大化一直是该类企业追求的目标。本文提出了基于启发式规则的有限制二维板材下料算法。通过在橱柜生产过程中自动下料系统的实施和理论分析,该算法是实用有效的。     

二维板材圆形下料的邻居关系算法

二维圆形排样问题是工业设计与生产中经常遇到的问题.常规下料问题主要针对矩形或圆形等规则板材,常用算法包括模拟退火、遗传算法等.本文在分析规则板材下料算法的基础上,针对实际生产应用中更为复杂的、具有不规则边界板材下料问题,提出了一种基于人工下料思维的仿生下料算法--邻居关系算法.该算法具有很好的利用率和时效性,较好地满足了实际应用的需要.实际板材下料结果表明,平均面积利用率为75.56％,平均计算时间为13.84s.所得排样利用率与模拟退火算法相当,但排样运算时间大大缩小,适应了实际下料需求,已应用于某跨国企业优化下料中.     

基于混合演化算法的二维下料问题

介绍了将二维下料问题建模成旅行商问题的方法,指出单纯旅行商问题模型的局限性,认为其是一种启发式方法,理论上找不到全局最优解。针对于此,在原有模型的基础上引入旋转变换,提出了两种混合演化算法捆绑式深化算法和元算法。实例仿表明,该算法可以获得比普通经算法好的结果。     

改进PSO算法在二维下料问题中的研究

粒子群优化（PSO）算法是一种基于集群智能的进化计算方法,在该方法中粒子通过追随自己找到的最优解和种群最优解完成优化。文章将PSO算法应用到三角形优化下料问题的研究中,给出了具体的实施流程,为了提高PSO算法的收敛精度,避免早熟现象的产生,对PSO进行了改进,提出一种启发式PSO算法。通过对三角形的优化下料进行仿真,仿真结果显示改进后的启发式粒子群优化算法在收敛效果和材料的利用率方面均有显著的提高。     

一种有效的求解一维下料问题的启发式算法

使用了一种改进的顺序启发式算法,在排样方式的生成过程中不断修正当前排入毛坯的价值,使之趋于合理,依次选取求解背包函数获得的最大单位价值的排样方式组成当前排样方案,迭代调用该过程多次,最终选取最优的排样方案。在保证较高材料利用率的同时考虑减少排样方式,增加最后一根材料余料长度等多个优化目标。通过多组实验结果比较,证实了算法的有效性。     

无限制二维下料问题的改进动态规划算法

本文给出了一种求解无限制板材下料问题的动态规划解法，对该算法的计算复杂度 进行了分析．并针对算法的特点提出了改进方案．通过理论分析得到改进方案的适用范围， 并描述了这一改进动态规划算法的应用前景．数值实验表明，该算法可以缩简传统动态规划 算法的计算时间和空间，同时得到解的最优值．     

解决二维下料问题的顺序启发式算法

求解二维下料问题即求解如何用最少的板材排入所需的全部毛坯的问题。一种基于价值修正策略的顺序启发式算法被用来生成排样方案,方案中的排样方式按单位面积价值最大生成,在各排样方式顺序生成的过程中不断修正方式中使用到的毛坯的价值。迭代调用该过程多次生成多个排样方案,从中选择最优的排样方案。通过实验证明算法的有效性。     

二维板材优化下料快速搜索法

本文针对生产实际中切割下料方案问题，在原有提出矩形综合法的基础上，探索了一 种快速搜索法，较好地处理了二维板材下料的优化方案问题。     

冲裁件条料最优四块剪切下料方案的生成算法

讨论冲裁件条料剪切下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成条料最优四块排样方式的背包算法,然后采用基于列生成的线性规划算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并确定各种冲裁件的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用例题将该排样方式生成算法和文献中多段排样方式生成算法进行比较,实验计算结果表明,该算法得到的排样方式排样价值较高。最后通过文献中实例的下料方案求解,可以看出该算法解决实际下料问题是有效的。     

生成矩形毛坯最优两段排样方式的确定型算法

排样价值、切割工艺和计算时间是排样问题主要考虑的3个因素.文中提出一个新的基于排样模式的确定型排样算法——同质块两段排样算法,此算法适合剪冲下料工艺,在实现工艺简化的同时提高了排样价值时间比.首先通过动态规划算法生成最优同质块,然后求解一维背包问题生成块在级中的最优排样方式和级在段中的最优排样方式,最后选择两个段生成最优的两段排样方式.通过3组经典测题对该文算法进行了测试,将算法与4种著名算法进行了比较.实验结果表明,该文算法的优化结果好于以上4种著名算法,有效地提高了板材利用率,并且计算时间合理.     

Two-Dimensional Rectangular Stock Cutting Problem and Solution Methods

Optimal layout of rectangular stock cutting is still in great demand from industry for diversified applications. This paper introduces four basic solution methods to the problem linear programming, dynamic programming, tree search and heuristic approach. A prototype of application software is developed to verify the pros and cons of various approaches     

基于价值修正的圆片下料顺序启发式算法

讨论圆片剪冲下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成圆片条带最优四块排样方式的背包算法,然后采用基于价值修正的顺序启发式算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并修正各种圆片的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用文献中的基准测题将文中下料算法与文献中T 型下料算法和启发式下料算法分别进行比较。实验计算结果表明,该算法的材料利用率比T 型下料算法和启发式下料算法分别高0.83%和3.63%,且计算时间在实际应用中合理。     

Optimization of Wafer Exposure Patterns Using a Two-Dimensional Cutting Algorithm

The semiconductor industry plays an integral role in Taiwan's manufacturing sector. Although defect reduction has received considerable attention to improve the yield rate, the problem of optimizing wafer exposure patterns has seldom been addressed. This study formulates the wafer exposure-patterning problem into a cutting and packing problem by adopting an innovative approach. We developed a two-dimensional cutting algorithm to maximize the number of dies that can be produced from a wafer to increase the gross die yield. The proposed algorithm is successfully implemented in a wafer fabrication factory. Experimental results validate the effectiveness of the proposed algorithm.     

Efficient Algorithm for the Constrained Two-dimensional Cutting Stock Problem

This paper considers the constrained two-dimensional cutting stock problem. Some properties of the problem are derived leading to the development of a new algorithm, which uses a very efficient branching strategy for the solution of this problem. This strategy enables the early rejection of partial solutions that cannot lead to optimality. Computational results are given and compared with those produced by a leading alternative method. These results show that the new algorithm is far superior in terms of the computer time needed to solve such problems.     

基于零件相似性特征的大规模下料分组优化方法

针对诸多优化算法在处理大规模下料问题时易于陷入局部最优解和时间效率低下的问题,提出基于零件相似性特征的分组优化方法.该方法利用HCM算法进行零件聚类,产生若干相似组,然后通过分析计算机硬件水平和算法处理问题能力将相似组重组为若干分组,再对各分组依次优化.在相邻分组的优化中,采用补偿策略动态修正零件在分组间的分布,优化完毕后合并各组优化结果得到原问题的下料方案.实验结果表明,相对于不分组优化,该方法处理大规模下料问题的效率高,且可以维持和提高材料利用率.     

面向可加工性的矩形件优化下料算法

针对目前矩形件优化下料算法侧重追求高材料利用率,而对实际切割成本考虑不足的现状,提出一种既维持高材料利用率,又使下料方案具有较低切割成本的矩形件优化下料算法。算法采用SVC框架和同质条带多级规范方式求解矩形件下料问题。利用条带共边排样的路径优化设计进行切割路径长度的计算,以生产成本（材料成本与切割成本之和）为优化目标得到高材料利用率、低切割成本的下料方案,最后通过实验证实该算法的可行性与有效性。     

面向可制造性的两阶段一维优化下料方法

针对诸多优化下料方法片面追求高原材料利用率,而对实际切割加工成本考虑不足的现状,提出一种既维持高原材料利用率又使下料方案可制造性好的一维优化下料方法.下料方案的可制造性从切割方式种类数和每种切割方式中套裁零件种类数两方面来衡量,基于此提出了非定长优化和定长优化相结合的两阶段一维优化下料方法,并采用两阶段列生成算法实现.最后通过实例验证了文中方法的实用性和有效性.     

优化切纸问题的近似算法

对印刷厂常遇到的切纸问题进行了数学描述,并提出了一个近似算法。利用该算法编写的程序可输出优化的结果,包括切纸方式、切纸张数和切纸利用率。所提出的算法具有较强的实用价值。     

矩形毛料无约束二维剪切排样的递归算法

将板材分成一系列的板块.对于每一板块,通过优化选择一个毛料放在其左下角,并确定剪切线的方向;沿着该毛料的上边界或右边界将剩余区域分成2个更小的板块以待进一步排样.实验结果表明：该算法的时间效率可满足实际应用的需要,与其他算法相比,所给出的排样方式材料利用率较高.