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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一种求解圆形件下料问题的启发式算法

针对二维圆形件下料问题,提出一种改进的顺序启发式算法。在生成排样方式的过程中,采用价值修正策略不断修正当前排入圆片的价值,使之趋于合理,选取价值最大的排样方式组成当前排样方案,迭代调用该过程多次,从中选取最优的排样方案。实验结果证明,与线性规划算法相比,该算法更有效。     

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

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

Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns

A sequential value correction heuristic is presented for the two-dimensional cutting stock problem with three-staged homogenous patterns, considering both input-minimization and simplicity of the cutting process. The heuristic constructs many cutting plans iteratively and selects the best one as the solution. The patterns in each cutting plan are generated sequentially using simple recursive techniques. The values of the item types are corrected after the generation of each pattern to diversify the cutting plans. Computational results indicate that the proposed heuristic is more effective in input minimization than published algorithms and commercial stock cutting software packages that use three-staged general or exact patterns.     

The skiving stock problem as a counterpart of the cutting stock problem

The cutting stock problem (CSP) is a particular case of the set‐covering problem. Similarly we introduce another class of combinatorial optimization problems called the skiving stock problem (SSP) as a particular case of the set‐packing problem. The SSP shares many properties and solving techniques with the CSP. When these two problem spaces are contrasted they illuminate one another in that they form a ‘dual’ relationship where techniques once thought to be applicable in one domain can be applied in the other. Furthermore the SSP, like the CSP, may have numerous applications in business and industry.     

A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem

Many heuristic approaches have been proposed in the literature for the multiple length cutting stock problem, while only few results have been reported for exact solution algorithms. In this paper, we present a new branch-and-price-and-cut algorithm which outperforms other exact approaches proposed so far. Our conclusions are supported on many computational experiments conducted on instances from the literature. In the second part of the paper, we investigate the use of valid dual inequalities within the previous algorithm. We show how column generation can be accelerated in all the nodes of our branching tree using such inequalities. Until now, dual inequalities have been applied only for original linear programming relaxations. Their validity within a branch-and-bound procedure has never been investigated. Our computational experiments show that extending these inequalities to the whole branch-and-bound tree can significantly improve the convergence of our branch-and-price-and-cut algorithm.     

Models for the two-dimensional two-stage cutting stock problem with multiple stock size

We consider a Two-Dimensional Cutting Stock Problem (2DCSP) where stock of different sizes is available, and a set of rectangular items has to be obtained through two-stage guillotine cuts. We propose and computationally compare three Mixed-Integer Programming models for the 2DCSP developing formulations from the literature. The first two models have a polynomial and pseudo-polynomial number of variables, respectively, and can be solved with a general-purpose MIP solver. The third model, having an exponential number of variables, is solved via branch-and-price techniques. We conclude the paper describing the results of extensive computational experiments on a set of benchmark instances from the literature.     

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

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

Heuristic for the two-dimensional arbitrary stock-size cutting stock problem

A heuristic is presented for the two-dimensional arbitrary stock-size cutting stock problem, where a set of rectangular items with specified demand are cut from plates of arbitrary sizes that confirm to the supplier’s provisions, such that the plate cost is minimized. The supplier’s provisions include: the lengths and widths of the plates must be in the specified ranges; the total area of the plates with the same size must reach the area threshold. The proposed algorithm uses a pattern-generation procedure with all-capacity property to obtain the patterns, and combines it with a sequential heuristic procedure to obtain the cutting plan, from which the purchasing decision can be made. Practical and random instances are used to compare the algorithm with a published approach. The results indicate that the trim loss can be reduced by more than half if the algorithm is used in the purchasing decision of the plates.     

On the generalised stock–cutting problem

In this paper, we formulate the two-stage stock-cutting problem, according to which a set of rectangular pieces of prespecified dimensions are to be cut from an arbitrarily shaped object with arbitrarily shaped holes or defective regions. We show how mathematical morphological operators can be used in order to determine the optimal shifting for a given cutting pattern. It is then proved that the problem of obtaining the optimal cutting pattern is -hard and a solution to the unconstrained problem using mathematical programming is proposed. However, for the general problem, good sub-optimal solutions can be obtained using the technique of simulated annealing. Experimental results are also included. Received: 28 July 1997 / Accepted: 25 August 1999     

矩形件优化排样的一种启发式算法

对大规模矩形件正交排样问题,提出了一种快速高效的启发式排放算法。对当前的可排放位置（水平线）,用贪婪算法从未排矩形件中选择可排放于该水平线的最优矩形件组合块;根据各个排放位置与其对应的矩形件组合块的匹配程度,选择最优的可排放位置（最优水平线）优先排放。在排放时,为了便于后续排放,先将待排放位置对应的矩形件组合块从低到高进行排序,再排放。对E.Hopper提供的规模最大的一类实例进行计算,排样率都在99%以上,平均排样率达到了99.38%,平均计算时间只用了1.12秒。与相关文献最好结果进行了比较,结果表明该文算法解决大规模的矩形件排样具有高效性。