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

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

二维优化排样方法及实现技术

在工业应用领域中存在大量的二维下料问题,其中应用最多的是矩形件下料问题.矩形件下料问题的关键是寻找二维平面的优化布局.针对工业生产中实际存在的问题与约束条件,给出了新的规则设计理论和数据模型,利用覆盖率和有效覆盖率的概念来控制余料合并操作的执行,运用布局规则、组合规则和切割规则给出了一种新的启发式算法.实验分析和工业应用证明,该启发式算法可以有效地提高板材的整体利用率,极大地减少了板材损耗.     

考虑余料价值的三阶段二维剪切下料算法

余料再利用是企业降低成本、减少环境污染的一个重要途径。在二维剪切下料问题中考虑余料的二次利用价值,采用束搜索优化材料利用率高、加工复杂度低的三阶段同质排样方式。束搜索节点既考虑板材中排入的毛坯价值,又考虑余料的二次利用价值,较好地兼顾当前生产周期的下料成本和余料在未来周期中的可用性。演示了排样方式的优化排样过程,给出了考虑余料价值的排样方案与已有文献算法的对比,说明文中算法可有效节省板材成本、生成可用标准余料。     

基于遗传算法的二维下料的仿真与实现

利用遗传算法抽象了它们的通用编码,对简单的管材和板材下料问题进行了模拟实验,进行了一维和二维下料问题的软件设计和仿真。本文的研究为求解简单的一维管材下料和二维板材下料问题提供了一种有效的思路,也为相关下料行业,如机械、建筑、船舶、服装、皮革、车辆等行业提供了解决方案。     

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

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

二维板材切割下料问题的一种确定性算法

研究二维板材切割下料问题,即使用最少板材切割出一定数量的若干种矩形件。 提出一种结合背包算法和线性规划算法的确定性求解算法。首先构造生成均匀条带四块排样方 式的背包算法;然后采用线性规划算法迭代调用上述背包算法,每次均根据生产成本最小原则 改善目标函数并修正各种矩形件的当前价值,按照当前价值生成新的排样方式;最后选择最优 的一组排样方式组成排样方案。采用基准测题,将该算法与著名的T 型下料算法进行比较,实 验结果表明,该算法比T 型下料算法更能节省板材,计算时间能够满足实际应用需要。     

应用精确两阶段排样图的板材下料算法

求解基于精确两阶段排样图的二维下料问题,用最小的板材成本,生产出所需要的全部毛坯。将顺序启发式算法和排样图生成算法相结合,顺序生成排样方案中的各个排样图;采用顺序价值修正策略,在生成每个排样图后修正其中所含各种毛坯的价值。经过多次迭代生成多个排样方案,从中选择最好者。实验计算时与商业软件和文献算法相比较,结果表明所述算法可以更为有效地减少板材消耗。     

矩形毛坯最优三块排样的新算法

针对矩形毛坯二维下料问题,提出采用三块排样的下料算法,以达到最小化板材消耗量和简化切割工艺的目标。该算法将列生成法和排样方式生成算法相结合,生成一个含多个排样方式(排样图)的集合,然后通过解整数规划问题获得各个排样方式的使用次数。排样方式生成算法通过构造并求解整数规划模型,求出最优三块排样。采用的三块排样,切割工艺简单,能有效提高切割效率。实验结果表明,该算法可以明显减少板材消耗。     

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

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

玻璃板材下料优选算法设计及实现

玻璃板材按等级优选技术在全自动玻璃产线的下料工艺中起重要作用，优选的结果优劣直接影响玻璃板材出材率及综合利用率，而优选的结果优劣取决于玻璃板材考虑等级的下料优选算法。针对全自动玻璃板材下料设备优选算法实现的问题，提出适用于自动扫描的玻璃板材及矩形件规范化量化方法，并结合量化方法给出规范化矩形件订单定义，作为任务输入给优选算法；提出适用于下料设备自动下料的矩形件优选下料的三种矩形件优选方式，即加权优选方式、数量优选方式及价值优选方式，并结合等级优选以适应自动化生产线的要求，解决如何优选的问题。然后，建立数量优选系数及矩形件优选的数学模型；设计下料优选算法软件实现的智能化架构及编制相应优选实现软件。选取实例对所建立的数学模型进行综合评价，评价结果表明，运用所提优选算法的出材率提高约10%,能明显提高生产效率，能实现矩形件产品的精确统计。所建立的三种矩形件优选方式的数学模型能有效地提高玻璃板材出材率和综合利用率。     

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

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

一维下料的改进遗传算法优化

针对一维下料优化问题,在对一维下料方案数学模型分析的基础上,提出了基于改进遗传算法的优化求解方案。主要思想是把零件的一个顺序作为一种下料方案,定义了遗传算法中的关键问题:编码、解码方法、遗传算子和适应度函数的定义。该算法设计了一种新颖的遗传算子,包括顺序交叉算子、线性变异算子、扩展选择算子。根据这一算法开发出了一维下料方案的优化系统。实际应用表明,该算法逼近理论最优值,而且收敛速度快,较好地解决了一维下料问题。     

An Innovative Genetic Algorithm for a Multi-Objective Optimization of Two-Dimensional Cutting-Stock Problem

This paper addressed an important variant of two-dimensional cutting stock problem. The objective was not only to minimize trim loss, as in traditional cutting stock problems, but rather to minimize the number of machine setups. This additional objective is crucial for the life of the machines and affects both the time and the cost of cutting operations. Since cutting stock problems are well known to be NP-hard, we proposed an approximate method to solve this problem in a reasonable time. This approach differs from the previous works by generating a front with many interesting solutions. By this way, the decision maker or production manager can choose the best one from the set based on other additional constraints. This approach combined a genetic algorithm with a linear programming model to estimate the optimal Pareto front of these two objectives. The effectiveness of this approach was evaluated through a set of instances collected from the literature. The experimental results for different-size problems show that this algorithm provides Pareto fronts very near to the optimal ones.     

考虑库存余材利用的杆材下料方案

本文应用典型的杆材下料算法（如列生成算法）,提出一个考虑库存余材利用的杆材下料方案,在不增加计算复杂性情况下,解决更切实际的杆材下料问题。     

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

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

Using Wang's two-dimensional cutting stock algorithm to optimally solve difficult problems

P. Y. Wang's classic bottom-up two-dimensional cutting stock algorithm generates cutting patterns by building rectangles both horizontally and vertically. This algorithm uses a parameter β ₁ to tradeoff the number of rectangles generated by the algorithm and hence the quality of the cutting pattern solution obtained versus the amount of computer resources required. Several researchers have made relatively straightforward modifications to Wang's basic algorithm resulting in improved computational times. However, even with these modifications, Wang's approach tends to require large amounts of computer resources in order to optimally or near-optimally solve difficult two-dimensional guillotine cutting stock problems. In this paper, we present an iterative approach that judiciously uses Wang's basic algorithm (with some previously defined modifications) to obtain optimal cutting patterns to difficult two-dimensional cutting stock problems in reasonable computer run times.     

基于动态分割与合一的排样算法

提出一种于动态分割与合一的优化排样算法,基本思想是分割之后,尽量将相邻的余料合并成较大的余料参与下一轮排祥,这不仅增加了排祥大件的可能性,而且也增加排样优化的机会,同时减少零件之间的空隙余料碎片,从而提高了切割速度。     

On the one-dimensional stock cutting problem in the paper tube industry

The one-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems which arises in many industrial applications. Although the primary objective of 1D-CSP is to minimize the total length of used stock rolls, the efficiency of cutting processes has become more important in recent years. The crucial bottleneck of the cutting process often occurs at handling operations in semiautomated manufacturers such as those in the paper tube industry. To reduce interruptions and errors at handling operations in the paper tube industry, we consider a variant of 1D-CSP that minimizes the total length of used stock rolls while constraining (C1) the number of setups of each stock roll type, (C2) the combination of piece lengths occurring in open stacks simultaneously, and (C3) the number of open stacks. For this problem, we propose a generalization of the cutting pattern called the “cutting group,” which is a sequence of cutting patterns that satisfies the given upper bounds of setups of each stock roll type and open stacks. To generate good cutting groups, we decompose the 1D-CSP into a number of auxiliary bin packing problems. We develop a tabu search algorithm based on a shift neighborhood that solves the auxiliary bin packing problems by the first-fit decreasing heuristic algorithm. Experimental results show that our algorithm improves the quality of solutions compared to the existing algorithm used in a paper tube factory.     

An integrated algorithm for cutting stock problems in the thin-film transistor liquid crystal display industry

The cutting stock problem (CSP) is a critical issue in the manufacturing of thin film transistor liquid crystal display (TFT-LCD) products. Two manufacturing processes are utilized in this industry: (1) various TFT-LCD plates are cut from a glass substrate based on cutting patterns, and (2) the number of glass substrates required to satisfy customer requirements is minimized. The current algorithm used to select the cutting pattern is defined as a mixed integer program (MIP). Although the current MIP method yields an optimal solution, but the computation time is unacceptable when the problem scale is large. To accelerate the computation and improve the current method, this study proposes an integrated algorithm that incorporates a genetic algorithm, a corner arrangement method, and a production plan model to solve CSPs in the TFT-LCD industry. The results of numerical experiments demonstrate that the proposed algorithm is significantly more efficient than the current method, especially when applied to large-scale problems.